פרדוקס יום ההולדת – הבדלי גרסאות

[[קובץ:Birthday Paradox.svg|ממוזער|300px|ההסתברות לכך ששני אנשים בקבוצה נולדו באותו יום בשנה, כפונקציה של גודל הקבוצה]]

 

 

== תיאור התופעה ==

 

=== מספר ההתנגשויות ===

 

=== ההסתברות לאי-חזרה ===

 

<math>\ p_m=1\cdot \left(1-\tfrac{1}{n}\right)\cdot \left(1-\tfrac{2}{n}\right)\cdot \dots \cdot \left(1-\tfrac{m-1}{n}\right)</math>. כדי להעריך מספר זה, אפשר להיעזר בחסם <math>\ e^{-x}> 1-x</math> (הנובע מפיתוח פונקציית ה[[אקספוננט]] ל[[טור טיילור]], ותקף לכל <math>\ x>0</math>). לפי חסם זה,

<math>\

e^{-\frac{m-1}{n}} = e^{-(\frac{1}{n}+\frac{2}{n}+\dots+\frac{m-1}{n})} = e^{-\frac{m(m-1)}{2n}}</math>, ובקירוב, <math>\ e^{-\frac{m^2}{2n}}</math>. הסיכוי לאי-חזרה יורד לחצי, אם-כן, כאשר <math>\ m \approx \sqrt{2\ln(2)\cdot n}</math>. ככל שה[[יחס (בין מספרים)|יחס]] <math>\ \tfrac{m^2}{n}</math> גדול יותר כך הסיכוי לאי-חזרה קטן יותר, וב[[סימון אסימפטוטי]]: עבור <math>\ m=o(\sqrt{n})</math> ההסתברות לאי חזרה היא <math>\ o(1)</math>. מצד שני, לא קשה להראות שאם <math>\ m=\omega(\sqrt{n})</math> אז ההסתברות היא <math>\ 1-o(\sqrt{n})</math>.

 

נסמן ב- <math>\ T</math> את ה[[משתנה מקרי|משתנה המקרי]] הסופר כמה כדורים נזרקו, באקראי, עד להתנגשות הראשונה. זהו משתנה העשוי לקבל כל ערך שלם מ- <math>\ 1</math> ועד <math>\ n+1</math>. ידוע שהתוחלת של משתנה כזה שווה לסכום ההסתברויות

<math>\ E(T) = \sum_{m=1}^{\infty}P(T\geq m) = \sum_{m=1}^{\infty}p_{m-1} \approx