פרדוקס יום ההולדת

פרדוקס יום ההולדת הוא שמה של תוצאה בתורת ההסתברות לפיה בקבוצה של 23 אנשים או יותר, שנבחרו באקראי, הסיכוי לכך שלפחות שניים מהם נולדו באותו יום בשנה עולה על 50%. תוצאה זו אינה פרדוקס במובן המקובל של המילה, שכן אין בה סתירה לוגית, אך היא סותרת את האינטואיציה של מרבית האנשים, הסבורים כי ההסתברות תהיה קטנה בהרבה מחצי משום שמספר הימים שבהם אפשר להיוולד (365) גדול בהרבה מ-23.

תוצאה זו היא מקרה פרטי של עובדה כללית יותר, שיש לה חשיבות רבה ביישומים של תורת ההסתברות, ובפרט בהתקפת יום הולדת בקריפטוגרפיה: אם בוחרים ערכים בעלי סיכוי שווה מבין $\ n$ אפשרויות, אז החזרות הראשונות תופענה כבר כאשר מספר הערכים הוא מסדר גודל של $\ {\sqrt {n}}$ .

פרדוקס יום ההולדת תואר לראשונה במאמר על ידי הסטטיסטיקאי ריצ'רד פון מיזס ב-1939, אם כי סביר להניח שגרסאות קודמות של הבעיה היו ידועות ונחקרו על ידי מתמטיקאים אחרים. הפרדוקס היה נושא למחקר ודיונים רבים בתחומי ההסתברות והסטטיסטיקה, ויש לו יישומים רבים במדעי המחשב, בקריפטוגרפיה ובתחומים נוספים.

תיאור התופעה

פרדוקס יום ההולדת עוסק בסדרה של ערכים אקראיים המוגרלים ממרחב סופי. במקרה של ימי הולדת, הערכים האפשריים הם 365 ימי השנה. בניתוח התופעה נניח שהאוכלוסייה מפוזרת באופן אחיד בין ימי ההולדת האפשריים. לבסוף, מניחים שתאריכי הלידה של האנשים שנבחרו בלתי תלויים זה בזה – הפרדוקס מאבד את עוקצו אם בין הנבחרים זוג תאומים.

כדי להבטיח שני אנשים שנולדו באותו יום, יש לבחור לפחות 366 אנשים – זהו עקרון שובך היונים. אולם, הדרישה הסטטיסטית להימנע מימי הולדת משותפים הולכת ומכבידה. בבחירה של 23 הסיכוי שכל ימי ההולדת שונים יורד ל-49.3%, בבחירה של 41 אנשים הסיכוי שכל ימי ההולדת שונים הוא 9.7%, וסיכוי זה יורד אל מתחת לאחוז אחד כאשר בוחרים 57 אנשים.

ניתוח מפורט

את תופעת יום ההולדת, או החֲזרה בבחירה מתוך מרחב גדול בעל התפלגות אחידה, אפשר לנתח משלוש זוויות שונות, המביאות, בקירוב, לאותה מסקנה. נניח שזורקים $\ m$ כדורים באקראי ל- $\ n$ תאים, שההסתברות ליפול לכל אחד מהם שווה.

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

אפשר להתייחס לכל זוג כדורים כאל ניסוי עצמאי. הסיכוי שזוג הכדורים $\ i,j$ ייפלו לאותו תא הוא בדיוק $\ {\tfrac {1}{n}}$ , ולכן, כשעוברים על פני כל $\ {\tfrac {m(m-1)}{2}}$ הזוגות, התוחלת של מספר הזוגות שיפלו לאותו תא שווה ל- $\ {\tfrac {m(m-1)}{2n}}$ . כל עוד מספר הכדורים $\ m$ הוא קטן, התוחלת קטנה מ-1 ולכן אפשר להניח שלא תהיה אף התנגשות אחת. התוחלת של מספר ההתנגשויות עולה ל-1 כאשר $\ m\approx {\sqrt {2n}}$ .

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

את התנאי לחוסר חזרה אפשר להבין כך: הכדור הראשון אינו מוגבל. הכדור השני יכול ליפול לאחד מבין $\ n-1$ תאים, כדי לא לפגוע בראשון; הסיכוי לכך בזריקה אקראית הוא $\ {\tfrac {n-1}{n}}$ . הכדור השלישי צריך ליפול לאחד מבין $\ n-2$ התאים שנותרו לאחר פסילת שני התאים הראשונים, והסיכוי לכך הוא $\ {\tfrac {n-2}{n}}$ ; וכן הלאה. לאחר שנזרקו $\ k$ כדורים שנכנסו כולם לתאים שונים, הסיכוי לכך שגם הכדור הבא ייפול לתא משלו הוא $\ {\tfrac {n-k}{n}}$ .

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

זמן ההמתנה להתנגשות הראשונה

נסמן ב- $\ T$ את המשתנה המקרי הסופר כמה כדורים נזרקו, באקראי, עד להתנגשות הראשונה. זהו משתנה העשוי לקבל כל ערך שלם מ- $\ 1$ ועד $\ n+1$ . ידוע שהתוחלת של משתנה כזה שווה לסכום ההסתברויות $\ E(T)=\sum _{m=1}^{\infty }P(T\geq m)=\sum _{m=1}^{\infty }p_{m-1}\approx \sum _{m=0}^{n}e^{-{\frac {m(m-1)}{2n}}}$ , שאותו אפשר להעריך בעזרת אינטגרל מתאים. התוצאה מחישוב מדויק היא שכאשר $\ n$ גדול, תוחלת זמן ההמתנה עד להתנגשות הראשונה היא $\ E(T)\approx {\sqrt {\frac {\pi n}{2}}}$ .