ในทางคณิตศาสตร์วิธีการเชิงความน่าจะเป็นเป็น วิธีการ ที่ไม่สร้างแบบจำลองขึ้นมาเอง โดยส่วนใหญ่ใช้ในคณิตศาสตร์เชิงการจัดเรียงและริเริ่มโดยพอล แอร์โดสเพื่อพิสูจน์การมีอยู่ของวัตถุทางคณิตศาสตร์ประเภทที่กำหนดไว้ วิธีการนี้ทำงานโดยการแสดงให้เห็นว่า หากเราสุ่มเลือกวัตถุจากกลุ่มที่กำหนดไว้ความน่าจะเป็นที่ผลลัพธ์จะเป็นประเภทที่กำหนดไว้จะต้องมากกว่าศูนย์อย่างแน่นอน แม้ว่าการพิสูจน์จะใช้ความน่าจะเป็น แต่ข้อสรุปสุดท้ายนั้นถูกกำหนดไว้อย่างแน่นอน โดยไม่มีข้อผิดพลาดใดๆ

ปัจจุบัน วิธีการนี้ได้ถูกนำไปประยุกต์ใช้ในสาขาอื่นๆ ของคณิตศาสตร์เช่นทฤษฎีจำนวนพีชคณิตเชิงเส้นและการวิเคราะห์เชิงจริงรวมถึงในวิทยาศาสตร์คอมพิวเตอร์ (เช่นการปัดเศษแบบสุ่ม ) และทฤษฎีสารสนเทศด้วย

ถ้าวัตถุทุกชิ้นในกลุ่มวัตถุไม่มีคุณสมบัติบางอย่าง ความน่าจะเป็นที่วัตถุที่สุ่มเลือกจากกลุ่มวัตถุนั้นจะมีคุณสมบัติดังกล่าวจะเป็นศูนย์ ดังนั้น โดยหลักการแย้งถ้าความน่าจะเป็นที่วัตถุที่สุ่มเลือกจากกลุ่มวัตถุนั้นจะมีคุณสมบัติดังกล่าวไม่เป็นศูนย์ แสดงว่าต้องมีวัตถุบางชิ้นในกลุ่มวัตถุนั้นที่มีคุณสมบัติดังกล่าว

ในทำนองเดียวกัน การแสดงให้เห็นว่าความน่าจะเป็นนั้น (อย่างเคร่งครัด) น้อยกว่า 1 สามารถนำมาใช้พิสูจน์การมีอยู่ของวัตถุที่ไม่ตรงตามคุณสมบัติที่กำหนดไว้ได้

อีกวิธีหนึ่งในการใช้วิธีการทางความน่าจะเป็นคือการคำนวณค่าคาดหวังของตัวแปรสุ่ม บางตัว หากสามารถแสดงได้ว่าตัวแปรสุ่มนั้นสามารถมีค่าต่ำกว่าค่าคาดหวังได้ นั่นแสดงว่าตัวแปรสุ่มนั้นสามารถมีค่ามากกว่าค่าคาดหวังได้เช่นกัน

อีกทางเลือกหนึ่ง วิธีการทางความน่าจะเป็นยังสามารถใช้เพื่อรับประกันการมีอยู่ขององค์ประกอบที่ต้องการในปริภูมิของตัวอย่างที่มีค่ามากกว่าหรือเท่ากับค่าคาดหวังที่คำนวณได้ เนื่องจากหากไม่มีองค์ประกอบดังกล่าว จะหมายความว่าทุกองค์ประกอบในปริภูมิของตัวอย่างมีค่าน้อยกว่าค่าคาดหวัง ซึ่งเป็นข้อขัดแย้ง

เครื่องมือทั่วไปที่ใช้ในวิธีการทางความน่าจะเป็น ได้แก่อสมการของมาร์คอฟขอบเขตของ เชอร์นอฟ และทฤษฎีบทเฉพาะที่ของโลวัสซ์

ถึงแม้ว่านักวิทยาศาสตร์คนอื่นๆ ก่อนหน้าเขาจะพิสูจน์ทฤษฎีบทโดยใช้วิธีความน่าจะเป็น (ตัวอย่างเช่น ผลงานของ Szele ในปี 1943 ที่ระบุว่ามีทัวร์นาเมนต์ ที่มี วงจรแฮมิลโทเนียนจำนวนมาก) แต่บทพิสูจน์ที่เป็นที่รู้จักมากที่สุดหลายบทที่ใช้วิธีนี้เป็นผลงานของ Erdős ตัวอย่างแรกด้านล่างนี้อธิบายถึงผลลัพธ์หนึ่งจากปี 1947 ที่ให้บทพิสูจน์ขอบเขตล่างสำหรับจำนวนแรมซี ย์ ${\displaystyle R(r,r)}$

สมมติว่าเรามีกราฟสมบูรณ์ที่มีจุดยอด n จุดเราต้องการแสดงให้เห็น (สำหรับค่า n ที่เล็กพอ) ว่าเป็นไปได้ที่จะระบายสีขอบของกราฟด้วยสองสี (เช่น สีแดงและสีน้ำเงิน) โดยที่ไม่มีกราฟย่อย สมบูรณ์ ที่มีจุดยอด n จุดใดที่เป็นกราฟสีเดียว (ขอบทุกเส้นมีสีเดียวกัน) ${\displaystyle n}$${\displaystyle n}$${\displaystyle r}$

ในการทำเช่นนั้น เราจะสุ่มระบายสีกราฟ โดยระบายสีขอบแต่ละด้านอย่างอิสระด้วยความน่าจะเป็นที่จะเป็นสีแดงและสีน้ำเงิน เราคำนวณจำนวนกราฟย่อยสีเดียวที่คาดหวังบนจุดยอดดังนี้: ${\displaystyle 1/2}$${\displaystyle 1/2}$${\displaystyle r}$

สำหรับเซตของจุดยอดใดๆ จากกราฟของเรา กำหนดให้ตัวแปรเป็นจริงถ้าขอบทุกเส้นระหว่างจุดยอดเหล่านั้นมีสีเดียวกัน และเป็นเท็จในกรณีอื่นๆ โปรดทราบว่าจำนวนกราฟย่อยแบบโมโนโครมาติก คือผลรวมของ เหนือ เซตย่อยที่เป็นไปได้ทั้งหมดสำหรับเซต ใดๆค่าที่คาดหวังของคือความน่าจะเป็นที่ขอบทั้งหมดในมีสีเดียวกัน: ${\displaystyle S_{r}}$${\displaystyle r}$${\displaystyle X(S_{r})}$${\displaystyle 1}$${\displaystyle r}$${\displaystyle 0}$${\displaystyle r}$${\displaystyle X(S_{r})}$${\displaystyle S_{r}}$${\displaystyle S_{r}^{i}}$${\displaystyle X(S_{r}^{i})}$${\displaystyle C(r,2)}$${\displaystyle S_{r}^{i}}$

${\displaystyle E[X(S_{r}^{i})]=2\cdot 2^{-{r \choose 2}}}$

(ปัจจัยนี้เกิดขึ้นเนื่องจากมีสีที่เป็นไปได้สองสี) ${\displaystyle 2}$

หลักการนี้ใช้ได้กับเซตย่อยที่เป็นไปได้ทั้งหมดที่เราเลือกไว้ กล่าวคือช่วงตั้งแต่ถึงดังนั้นเราจึงได้ว่าผลรวมของเหนือทุกเซตคือ ${\displaystyle C(n,r)}$${\displaystyle i}$${\displaystyle 1}$${\displaystyle C(n,r)}$${\displaystyle E[X(S_{r}^{i})]}$${\displaystyle S_{r}^{i}}$

${\displaystyle \sum _{i=1}^{C(n,r)}E[X(S_{r}^{i})]={n \choose r}2^{1-{r \choose 2}}.}$

ผลรวมของค่าคาดหวังคือค่าคาดหวังของผลรวม ( โดยไม่คำนึงว่าตัวแปรจะเป็นอิสระต่อกัน หรือไม่ ) ดังนั้นค่าคาดหวังของผลรวม (จำนวนที่คาดหวังของกราฟย่อยสีเดียวทั้งหมด) คือ ${\displaystyle r}$

${\displaystyle E[X(S_{r})]={n \choose r}2^{1-{r \choose 2}}.}$

พิจารณาว่าจะเกิดอะไรขึ้นถ้าค่านี้น้อยกว่าเนื่องจากจำนวนกราฟย่อยสีเดียวที่คาดหวังนั้นน้อยกว่า อย่างเคร่งครัดจึงมีการระบายสีที่ตรงตามเงื่อนไขที่ว่าจำนวนกราฟย่อยสีเดียวนั้นน้อยกว่า อย่างเคร่งครัดจำนวนกราฟย่อยสีเดียว ในการระบายสีแบบสุ่มนี้เป็น จำนวนเต็มที่ไม่เป็นลบดังนั้นจึงต้องเป็น( เป็นจำนวนเต็มที่ไม่เป็นลบเพียงจำนวนเดียวที่น้อยกว่า) จึงสรุปได้ว่าถ้า ${\displaystyle 1}$${\displaystyle r}$${\displaystyle 1}$${\displaystyle r}$${\displaystyle 1}$${\displaystyle r}$${\displaystyle 0}$${\displaystyle 0}$${\displaystyle 1}$

${\displaystyle E[X(S_{r})]={n \choose r}2^{1-{r \choose 2}}<1}$

(ซึ่งเป็นจริงสำหรับและ เป็นต้น) จะต้องมีการระบายสีที่ไม่มีซับกราฟ สีเดียว ^{[ a ]}${\displaystyle n=5}$${\displaystyle r=4}$${\displaystyle r}$

ตามนิยามของจำนวนแรมซีย์สิ่งนี้บ่งชี้ว่าจะต้องมีค่ามากกว่าโดยเฉพาะอย่างยิ่งจะต้องเติบโตอย่างน้อย ใน อัตราเลขชี้กำลัง ตาม${\displaystyle R(r,r)}$${\displaystyle n}$${\displaystyle R(r,r)}$${\displaystyle r}$

จุดอ่อนของข้อโต้แย้งนี้คือมันไม่ก่อให้เกิดประโยชน์ ใดๆ เลย ปัญหาการค้นหาการระบายสีดังกล่าวเป็นปัญหาที่ยังไม่ได้รับการแก้ไขมานานกว่า 50 ปีแล้ว

บทความของ Erdős ในปี 1959 (ดูเอกสารอ้างอิงด้านล่าง) ได้กล่าวถึงปัญหาต่อไปนี้ในทฤษฎีกราฟ : เมื่อกำหนดจำนวนเต็มบวกgและkแล้ว จะมีกราฟGที่ประกอบด้วยวัฏจักรที่มีความยาวอย่างน้อยg เท่านั้นหรือไม่ โดยที่จำนวนสีของ กราฟ Gมีค่าอย่างน้อยk ?

สามารถแสดงได้ว่ากราฟดังกล่าวมีอยู่จริงสำหรับgและk ใดๆ และการพิสูจน์นั้นค่อนข้างง่าย ให้nมีขนาดใหญ่มาก และพิจารณากราฟสุ่มGที่มีnจุดยอด โดยที่ขอบทุกเส้นในGมีอยู่ด้วยความน่าจะเป็นp = n ^{1/ g −1}เราจะแสดงว่าด้วยความน่าจะเป็นที่เป็นบวกGจะมีคุณสมบัติสองประการต่อไปนี้:

คุณสมบัติที่ 1. Gประกอบด้วยวัฏจักรที่มีความยาวน้อยกว่า g อย่างมากที่สุดn / 2วัฏจักร

บทพิสูจน์ให้Xเป็นจำนวนวัฏจักรที่มีความยาวน้อยกว่าgจำนวนวัฏจักรที่มีความยาวiในกราฟสมบูรณ์ที่มีnจุดยอดคือ

${\displaystyle {\frac {n!}{2\cdot i\cdot (n-i)!}}\leq {\frac {n^{i}}{2}}}$

และแต่ละตัวจะปรากฏอยู่ในGด้วยความน่าจะเป็นp ⁱดังนั้นโดยอสมการของมาร์คอฟเราจึงได้ว่า

${\displaystyle \Pr \left(X>{\tfrac {n}{2}}\right)\leq {\frac {2}{n}}E[X]\leq {\frac {1}{n}}\sum _{i=3}^{g-1}p^{i}n^{i}={\frac {1}{n}}\sum _{i=3}^{g-1}n^{\frac {i}{g}}\leq {\frac {g}{n}}n^{\frac {g-1}{g}}=gn^{-{\frac {1}{g}}}=o(1).}$

ดังนั้นสำหรับค่า nที่มากพอ คุณสมบัติข้อ 1 จะ เป็นจริงด้วยความน่าจะเป็นมากกว่า1/2

คุณสมบัติข้อ 2. Gไม่มีเซตอิสระที่มีขนาดเท่ากับ.${\displaystyle \lceil {\tfrac {n}{2k}}\rceil }$

บทพิสูจน์ให้Yเป็นขนาดของเซตอิสระที่ใหญ่ที่สุดในGเห็นได้ชัดว่าเรามี

${\displaystyle \Pr(Y\geq y)\leq {n \choose y}(1-p)^{\frac {y(y-1)}{2}}\leq n^{y}e^{-{\frac {py(y-1)}{2}}}=e^{-{\frac {y}{2}}\cdot (py-2\ln n-p)}=o(1),}$

เมื่อไร

${\displaystyle y=\left\lceil {\frac {n}{2k}}\right\rceil \!.}$ดังนั้น สำหรับ ค่า n ที่มากพอ คุณสมบัติข้อ 2 จะเป็น จริงด้วยความน่าจะเป็นมากกว่า1/2

สำหรับค่า nที่มากพอความน่าจะเป็นที่กราฟจากชุดการแจกแจงจะมีคุณสมบัติทั้งสองอย่างจะเป็นค่าบวก เนื่องจากเหตุการณ์สำหรับคุณสมบัติเหล่านี้ไม่สามารถแยกจากกันได้ (หากเป็นเช่นนั้น ผลรวมของความน่าจะเป็นจะมากกว่า 1)

เคล็ดลับอยู่ที่นี่: เนื่องจากG มีคุณสมบัติทั้งสองนี้ เราจึงสามารถลบ จุดยอดออกจากGได้มากที่สุดn /2 จุด เพื่อให้ได้กราฟใหม่G′ที่มีจุดยอดจำนวนหนึ่ง ซึ่งประกอบด้วยวัฏจักรที่มีความยาวอย่างน้อยgเท่านั้น เราจะเห็นได้ว่ากราฟใหม่นี้ไม่มีเซตอิสระที่มีขนาดเท่ากับG′ สามารถแบ่งออกเป็นเซตอิสระได้อย่างน้อย k เซต เท่านั้นและด้วยเหตุนี้ จึงมีจำนวนสีอย่างน้อยk${\displaystyle n'\geq n/2}$${\displaystyle \left\lceil {\frac {n'}{k}}\right\rceil }$

ผลลัพธ์นี้ให้เบาะแสว่าเหตุใดการคำนวณจำนวนสีของกราฟจึงเป็นเรื่องยาก: แม้ว่าจะไม่มีเหตุผลเฉพาะที่ (เช่น วงจรขนาดเล็ก) ที่ทำให้กราฟต้องการสีจำนวนมาก แต่จำนวนสีก็ยังคงมีค่ามากอย่างไม่จำกัด

• ระบบพิสูจน์แบบโต้ตอบ
• อัลกอริทึมลาสเวกัส
• วิธีการอัดไม่ได้
• วิธีความน่าจะเป็นแบบมีเงื่อนไข
• การพิสูจน์เชิงความน่าจะเป็นของทฤษฎีบทที่ไม่ใช่เชิงความน่าจะเป็น
• กราฟสุ่ม

• วิธีการเชิงความน่าจะเป็นในคณิตศาสตร์เชิงการจัดเรียง (Combinatorics) , MIT OpenCourseWare