ปัญหาวันเกิด

**ปัญหาวันเกิด** หรือ **[[ปฏิทรรศน์]]วันเกิด**  ในเรื่องทฤษฎีความน่าจะเป็น เกี่ยวข้องกับความน่าจะเป็นที่กลุ่มคนซึ่งถูกเลือกโดยการสุ่ม *n* คน จะมีบางคู่ในกลุ่มที่มีวันเกิดตรงกัน หากพิจารณาตามหลักรังนกพิราบ ความน่าจะเป็นดังกล่าวจะเป็น 100% ถ้าจำนวนคนในกลุ่มมี 367 คน (เนื่องจากวันที่เป็นไปได้ทั้งหมดมี 366 วัน รวม 29 กุมภาพันธ์ด้วย) อย่างไรก็ตาม ความน่าจะเป็น 99% จะเกิดกับกลุ่มคนเพียง 57 คน และความน่าจะเป็น 50% จะเกิดกับกลุ่มคนเพียง 23 คน การสรุปเหล่านี้ใช้พื้นฐานบนสมมติฐานว่า แต่ละวันของปีมีความเป็นไปได้ที่จะเป็นวันเกิดอย่างเท่าเทียมกัน (ยกเว้น 29 กุมภาพันธ์)

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

thumb|right|300px|กราฟแสดงความน่าจะเป็นโดยการคำนวณ ที่คนอย่างน้อยสองคนจะมีวันเกิดตรงกัน ในระหว่างกลุ่มคนตามจำนวนที่แน่นอน

## ความเข้าใจในตัวปัญหา
ปัญหาวันเกิดถามว่า คนหนึ่งคนใดในกลุ่มที่กำหนด มีวันเกิดตรงกับคนอื่นคนใดหรือไม่ มิได้ถามเฉพาะเจาะจงว่าตรงกับคนหนึ่งเพียงคนเดียวหรือไม่

ตัวอย่างที่ให้มาก่อนหน้านี้คือกลุ่มคน 23 คน การเปรียบเทียบวันเกิดของคนแรกกับวันเกิดของคนอื่นจะมีโอกาส 22 ครั้งเพื่อหาว่าวันเกิดตรงกันหรือไม่ วันเกิดของคนที่สองกับวันเกิดของคนอื่นก็จะมีโอกาส 21 ครั้ง วันเกิดของคนที่สามก็จะมีโอกาส 20 ครั้ง เป็นเช่นนี้ต่อไปเรื่อย ๆ เพราะฉะนั้นโอกาสรวมทั้งหมดที่จะเปรียบเทียบคือ 22 + 21 + 20 + ... + 1 = 253 ครั้ง ดังนั้นการเปรียบเทียบทุก ๆ คนกับคนอื่นทั้งหมดจะทำได้ 253 วิธีที่แตกต่างกัน (การจัดหมู่) หรือกล่าวได้ว่า กลุ่มคน 23 คนสามารถจับคู่ได้ทั้งหมด \textstyle {23 \choose 2} = \frac{23 \cdot 22}{2} = 253 คู่

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

## การคำนวณความน่าจะเป็น
ปัญหาคือการคำนวณความน่าจะเป็นโดยประมาณว่า ในกลุ่มคน *n* คน จะมีอย่างน้อยสองคนที่มีวันเกิดตรงกัน สำหรับกรณีง่ายสุดคือไม่สนใจความแปรปรวนในการแจกแจง เช่นปีอธิกสุรทิน ฝาแฝด ความแปรปรวนเชิงฤดูกาลหรือวันในสัปดาห์ และสมมติว่าวันเกิดที่เป็นไปได้ 365 วันอย่างเท่าเทียมกัน การแจกแจงวันเกิดในชีวิตจริงไม่เป็นเอกรูปเพราะทุกวันมิได้มีโอกาสอย่างเท่าเทียมกัน

ถ้าให้ *P*(*A*) คือความน่าจะเป็นที่อย่างน้อยสองคนในกลุ่มมีวันเกิดตรงกัน เราอาจคำนวณง่ายขึ้นจาก *P*(*A*′) คือความน่าจะเป็นที่ไม่มีสองคนใดเลยที่มีวันเกิดตรงกัน เนื่องจาก *A* และ *A*′ เป็นความน่าจะเป็นเพียงสองประการที่จะเกิดขึ้นได้และเป็นเหตุการณ์ไม่เกิดร่วม ดังนั้นเราจะได้ *P*(*A*) = 1 − *P*(*A*′)

คำตอบของปัญหาที่เผยแพร่อย่างกว้างขวางสรุปว่า กลุ่มคน 23 คนก็เพียงพอที่จะทำให้ *P*(*A*) มีค่ามากกว่า 50% การคำนวณ *P*(*A*) ต่อไปนี้จะใช้กลุ่มคน 23 คนมาเป็นตัวอย่าง

เมื่อเหตุการณ์เป็นอิสระซึ่งกันและกัน ความน่าจะเป็นของเหตุการณ์ทั้งหมดที่เกิดขึ้น จะเท่ากับผลคูณของความน่าจะเป็นของแต่ละเหตุการณ์ที่เกิดขึ้น เพราะฉะนั้น *P*(*A*′) จึงสามารถแยกได้เป็นเหตุการณ์อิสระ 23 เหตุการณ์ และคำนวณได้จาก *P*(1) × *P*(2) × *P*(3) × ... *P*(23)

เหตุการณ์อิสระ 23 เหตุการณ์นี้สอดคล้องกับจำนวนคน 23 คนและสามารถนิยามไปตามลำดับ แต่ละเหตุการณ์สามารถนิยามว่าคนนั้นจะไม่มีวันเกิดตรงกับคนอื่นคนใดที่ได้วิเคราะห์ไปแล้วก่อนหน้า สำหรับเหตุการณ์ที่ 1 คือไม่มีคนอื่นคนใดก่อนหน้านี้ให้วิเคราะห์เลย เพราะฉะนั้นความน่าจะเป็น *P*(1) ซึ่งคนแรกไม่มีวันเกิดตรงกับคนอื่นคนใดที่ได้วิเคราะห์ไปแล้วก่อนหน้าเท่ากับ 1 หรือ 100% หรือเขียนในรูปแบบ  โดยไม่พิจารณาอธิกวารสำหรับการวิเคราะห์นี้ ส่วนเหตุผลจะได้ปรากฏชัดเจนต่อไป

สำหรับเหตุการณ์ที่ 2 คือมีเพียงคนที่หนึ่งที่ได้วิเคราะห์แล้วก่อนหน้านี้ สมมติว่าวันเกิดเป็นไปได้อย่างเท่าเทียมกัน 365 วันเช่นเดิม ความน่าจะเป็น *P*(2) ซึ่งคนที่สองมีวันเกิดต่างกับคนที่หนึ่งเท่ากับ  นั่นเป็นเพราะถ้าคนที่สองเกิดในวันใดก็ได้ในจำนวน 364 วันที่เหลือ ทำให้คนที่หนึ่งกับคนที่สองมีวันเกิดไม่ตรงกัน

ในทางเดียวกัน ถ้าคนที่สามเกิดในวันใดก็ได้ในจำนวน 363 วันที่เหลือ ทำให้ทั้งคนที่หนึ่ง ที่สอง ที่สาม มีวันเกิดไม่ตรงกันเลย จะได้ความน่าจะเป็น *P*(3) เท่ากับ 

การวิเคราะห์เช่นนี้ดำเนินต่อไปจนกระทั่งถึงคนที่ยี่สิบสาม ซึ่งความน่าจะเป็นที่วันเกิดจะไม่ตรงกับคนที่ได้วิเคราะห์ไปแล้วก่อนหน้านี้เลย *P*(23) เท่ากับ 

*P*(*A*′) เท่ากับผลคูณของความน่าจะเป็นรายเหตุการณ์เหล่านี้ นั่นคือ
:: *P*(*A*′) =  ×  ×  ×  × ... × 
สมการดังกล่าวสามารถดึงตัวประกอบร่วมได้เป็น
:: *P*(*A*′) = ()23 × (365 × 364 × 363 × 362 × ... × 343)
ประเมินค่าออกมาจะได้ *P*(*A*′) ≈ 0.492703

ดังนั้น *P*(*A*) ≈ 1 − 0.492703 = 0.507297 หรือ 50.7297%

กระบวนการนี้สามารถทำให้เป็นกรณีทั่วไปสำหรับกลุ่มคน *n* คน เมื่อ *p*(*n*) คือความน่าจะเป็นที่อย่างน้อยสองคนในกลุ่ม *n* คนมีวันเกิดตรงกัน เราคำนวณง่ายขึ้นด้วย *p̅*(*n*) คือความน่าจะเป็นที่วันเกิดของ *n* คนแตกต่างกันทั้งหมด ตามหลักรังนกพิราบ *p̅*(*n*) จะเป็นศูนย์เมื่อ *n* > 365 และเมื่อ *n* ≤ 365 จะได้ว่า
:: \begin{align} \bar p(n) &= 1 \times \left(1-\frac{1}{365}\right) \times \left(1-\frac{2}{365}\right) \times \cdots \times \left(1-\frac{n-1}{365}\right) \\  &= { 365 \times 364 \times \cdots \times (365-n+1) \over 365^n } \\ &= { 365! \over 365^n (365-n)!} = \frac{n!\cdot{365 \choose n}}{365^n} = \frac{^{365}P_n}{365^n}\end{align} 
โดยสัญลักษณ์ ! คือตัวดำเนินการแฟกทอเรียล \textstyle {365 \choose n} คือสัมประสิทธิ์ทวินาม และ {^{k}P_r} หมายถึงการเรียงสับเปลี่ยน

สมการดังกล่าวแสดงข้อเท็จจริงว่า สำหรับคนที่หนึ่งไม่มีคนใดที่มีวันเกิดตรงกัน () สำหรับคนที่สองก็ไม่มีวันเกิดตรงกับคนที่หนึ่ง () สำหรับคนที่สามก็ไม่มีวันเกิดตรงกับคนที่หนึ่งและที่สอง () ฯลฯ และในกรณีทั่วไปวันเกิดของคนที่ *n* ก็จะไม่มีวันเกิดตรงกับ *n* − 1 คนที่อยู่ก่อนหน้า

เหตุการณ์ที่อย่างน้อยสองคนจากกลุ่มคน *n* คนมีวันเกิดตรงกัน คือเหตุการณ์เติมเต็มที่วันเกิดของ *n* คนแตกต่างกันทั้งหมด เพราะฉะนั้นความน่าจะเป็น *p*(*n*) จะมีค่าเท่ากับ
:: p(n) = 1 - \bar p(n) \, 

ความน่าจะเป็นนี้มีค่าเกินกว่า  เมื่อ *n* = 23 (ค่าจริงประมาณ 50.7%) ตารางต่อไปนี้แสดงความน่าจะเป็นสำหรับ *n* อื่น ๆ บางค่า (โดยไม่พิจารณาปีอธิกสุรทินตามที่ได้อธิบายแล้วด้านบน)

thumb|right|300px|กราฟแสดงความน่าจะเป็นโดยประมาณ ที่ไม่มีใครเลยในกลุ่มคน ''n'' คนมีวันเกิดตรงกัน สังเกตว่ามาตราส่วนตามแนวตั้งเป็นลอการิทึม (แต่ละขีดจากบนลงล่างลดลงทีละ 10<sup>20</sup> เท่า)

## การประมาณค่า
thumb|right|300px|กราฟแสดงความน่าจะเป็นโดยประมาณ ที่คนอย่างน้อยสองคนจะมีวันเกิดตรงกัน (แดง) และเหตุการณ์เติมเต็มของมัน (น้ำเงิน)
thumb|right|300px|กราฟแสดงความแม่นยำของการประมาณค่าด้วย <math>1-e^{-n^2/(2 \times 365)}</math> (ขาว)
การกระจายอนุกรมเทย์เลอร์ของฟังก์ชันเลขชี้กำลัง (ค่าคงตัว e ≈ 2.718281828)
:: e^x = 1 + x + \frac{x^2}{2!}+\cdots 
สามารถประมาณค่า *e**x* อันดับที่หนึ่งเมื่อ *x* ≪ 1 ดังนี้
:: e^x \approx 1 + x \ 

เพื่อใช้การประมาณนี้แก่นิพจน์แรกที่มาจาก *p̅*(*n*) กำหนดให้ *x* =  ดังนั้นเราจะได้
:: e^{-i/365} \approx 1 - \frac{i}{365} \ 
จากนั้นแทนที่ *i* ด้วยจำนวนเต็มไม่เป็นลบสำหรับแต่ละพจน์ในสูตรของ *p̅*(*n*) จนกระทั่ง *i* = *n* − 1 ตัวอย่างเช่นเมื่อ *i* = 1 จะได้
:: e^{-1/365} \approx 1 - \frac{1}{365} \ 

นิพจน์แรกที่มาจาก *p̅*(*n*) จึงสามารถประมาณค่าได้ดังนี้
::
\begin{align}
\bar p(n) & \approx 1 \times e^{-1/365} \times e^{-2/365} \cdots e^{-(n-1)/365} \\
& = 1 \times e^{-(1+2+ \cdots +(n-1))/365} \\
& = e^{-(n(n-1)/2) / 365}
\end{align}


เพราะฉะนั้น
:: p(n) = 1-\bar p(n) \approx 1 - e^{- n(n-1)/(2 \times 365)} 

การประมาณที่หยาบกว่าของสูตรดังกล่าวคือ
:: p(n) \approx 1-e^{- n^2/(2 \times 365)} 
ซึ่งยังคงแม่นยำพอใช้ได้ ดังที่เห็นจากกราฟในภาพประกอบ

จากการประมาณค่าดังกล่าว แนวทางที่เหมือนกันสามารถใช้ได้กับ "คน" และ "วัน" จำนวนเท่าใดก็ได้ ถ้าให้จำนวนวันเป็น *n* วันแทนที่จะเป็น 365 วัน ให้จำนวนคน *m* คน และ *m* ≪ *n* จากแนวทางข้างต้นเราจะได้ผลสำเร็จเป็น *Pr*[(*m*, *n*)] คือความน่าจะเป็นที่อย่างน้อยสองคนในกลุ่ม *m* คน มีวันเกิดตรงกันภายใน *n* วันที่กำหนด ดังนี้
:: Pr[(m, n)] \approx 1-e^{-m^2 / 2n} \ 

### การยกกำลังอย่างง่าย
ความน่าจะเป็นที่คนสองคนไม่มีวันเกิดตรงกันเท่ากับ  หากกลุ่มคนมีจำนวน *n* คน จะสามารถจับคู่ได้ *C*(*n*, 2) =  คู่ หรือเรียกได้ว่ามี *C*(*n*, 2) เหตุการณ์ ความน่าจะเป็นที่คนสองคนไม่มีวันเกิดตรงกันในกลุ่มคนดังกล่าว สามารถประมาณได้จากเหตุการณ์เหล่านี้ซึ่งสมมติว่าเป็นอิสระต่อกัน โดยคูณความน่าจะเป็นของพวกมันเข้าด้วยกัน กล่าวอย่างสั้นคือ  สามารถคูณกับตัวเองเป็นจำนวน *C*(*n*, 2) ตัว จะได้
::\bar p(n) \approx \left(\frac{364}{365}\right)^{C(n,2)}

เนื่องจากสิ่งนี้คือความน่าจะเป็นที่ไม่มีใครมีวันเกิดตรงกัน ดังนั้นความน่าจะเป็นที่จะมีใครบางคนมีวันเกิดตรงกันก็คือ
::p(n) \approx 1 - \left(\frac{364}{365}\right)^{C(n,2)}

### การประมาณปัวซง
ใช้การประมาณปัวซงสำหรับทวินามกับกลุ่มคน 23 คน
::\mathrm{Poi}\left(\frac{C(23, 2)}{365}\right) =\mathrm{Poi}\left(\frac{253}{365}\right) \approx \mathrm{Poi}(0.6932)
::\Pr(X>0)=1-\Pr(X=0) \approx 1-e^{-0.6932} \approx 1-0.499998=0.500002
ผลลัพธ์มีค่ามากกว่า 50% เช่นเดียวกับที่ได้อธิบายไว้ก่อนหน้านี้

### การประมาณจำนวนคน
การประมาณจำนวนคนเท่าที่จำเป็นที่จะทำให้เกิดโอกาส 50% เป็นอย่างน้อยที่จะมีวันเกิดตรงกัน โดยแฟรงก์ เอช. แมทิส สามารถหาได้จากสูตรดังนี้
::n \approx \frac{1}{2} + \sqrt{\frac{1}{4} - 2 \times 365 \times \ln(0.5)} = 22.999943
นี่เป็นผลลัพธ์ของการประมาณที่ดี ซึ่งเหตุการณ์ 1 ใน *k* ของความน่าจะเป็นจะมีโอกาสเกิดขึ้น 50% เป็นอย่างน้อย ถ้าเหตุการณ์นั้นเกิดซ้ำ *k* ln 2 ครั้ง 

### ตารางความน่าจะเป็น

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

ยกตัวอย่างเพื่อการเปรียบเทียบ ความน่าจะเป็น  ถึง  คืออัตราความผิดพลาดบิตที่แก้ไขไม่ได้ของฮาร์ดดิสก์ทั่วไป  ฟังก์ชันแฮช 128 บิตอย่างเช่น เอ็มดี5 จึงควรดำรงอยู่ในช่วงนั้นจนกว่าจะแฮชเอกสารไปแล้วประมาณ 8.2 แสนล้านเอกสารในทางทฤษฎี ถึงแม้ว่าผลลัพธ์ที่เป็นไปได้ของมันจะมีได้มากยิ่งกว่านั้น

## ขอบเขตบน
การอ้างเหตุผลด้านล่างดัดแปลงจากการอ้างเหตุผลของพอล ฮาลโมส 

ความน่าจะเป็นที่ไม่มีวันเกิดของคนใดตรงกัน ดังที่ได้อธิบายไว้ด้านบนคือ
::1-p(n) = \bar p(n) = \prod_{k=1}^{n-1}\left(1-{k \over 365}\right)

จากย่อหน้าก่อน ๆ นั้น สิ่งที่สนใจคือค่าของ *n* น้อยสุดที่ทำให้ *p*(*n*) >  หรือกล่าวอีกนัยหนึ่ง ค่าของ *n* น้อยสุดที่ทำให้ *p̅*(*n*) −*x* จากนิพจน์ด้านบนซึ่งเราได้แทนค่า 1 −  ด้วย *e*−*k*/365 จะได้ว่า
::\bar p(n) = \prod_{k=1}^{n-1}\left(1-{k \over 365}\right) 
เพราะฉะนั้น นิพจน์ดังกล่าวมิได้เป็นเพียงแค่การประมาณค่า แต่ยังเป็นขอบเขตบนของ *p̅*(*n*) ด้วย

อสมการนี้
::e^{-(n(n-1))/(2\cdot 365)} 
แสดงนัยถึง *p̅*(*n*) n^2-n > 2\times365\ln 2 \,\!

730 ln 2 มีค่าประมาณ 505.997 ซึ่งน้อยกว่า 506 เล็กน้อย ค่าของ *n*2 − *n* ขึ้นมาถึง 506 เมื่อ *n* = 23 ดังนั้น 23 คนก็เพียงพอที่จะเป็นคำตอบ

อย่างไรก็ดี การแก้สมการ *n*2 − *n* = 2 · 365 ln 2 เพื่อหาค่า *n* ก็จะเป็นสูตรประมาณของแฟรงก์ เอช. แมทิส ดังที่ได้แสดงไว้แล้ว

การได้มานี้แสดงเพียงว่า 23 คนเป็นจำนวนคนที่ *มากสุด* ที่จำเป็นเพื่อให้แน่ใจว่าวันเกิดจะตรงกันด้วยโอกาสครึ่งต่อครึ่ง กล่าวคือมันเปิดโอกาสความเป็นไปได้ว่าหาก *n* เท่ากับ 22 คนหรือน้อยกว่าก็อาจได้ผลเช่นกัน

## อ้างอิงและเชิงอรรถ

หมวดหมู่:Probability theory paradoxes
หมวดหมู่:Named probability problems
หมวดหมู่:ความน่าจะเป็นประยุกต์
หมวดหมู่:วันเกิด
หมวดหมู่:ปัญหาทางคณิตศาสตร์