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

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

התופעה היא דוגמה כללית בחקר חזרות (כאשר ערכים מועתקים יותר מפעם אחת). ברמה הכללית, אם בוחרים ערכים שווים סיכוי מתוך n אפשרויות, החזרות הראשונות מופיעות כבר כשהמספר שנבחר הוא מסדר גודל של שורש n (כלומר, בערך √n).

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

יש שלוש גישות פשוטות להבנת התופעה, שמובילות לאותה מסקנה:

אם מסתכלים על כל זוג אנשים בנפרד, הסיכוי ששני בני זוג נתונים חולקים יום הוא 1/n (במקרה של 365 ימים, זה 1/365). יש m(m-1)/2 זוגות מתוך m אנשים. התוחלת (הערך הממוצע) של מספר הזוגות החופפים שווה ל־m(m-1)/(2n). כאשר תוחלת זו קרובה ל־1 מתחילים לצפות להתנגשות ראשונה; זה קורה בקירוב כש m≈√(2n).

הסיכוי שאין אף חזרה (שכל הימים שונים) ניתן ככפל של ההסתברויות שכל אדם חדש נופל ביום חדש שלא נבחר קודם. הנוסחה היא
p_m = 1·(1-1/n)·(1-2/n)·…·(1-(m-1)/n).
באמצעים פשטניים אפשר להראות שהכפל הזה מתקרב לקירוב e^{-m^2/(2n)}. מכך נובע שמתי שמספר האנשים הוא בערך sqrt(2 ln 2 · n) ההסתברות לאי-חזרה היא כחצי.

אם סופרים כמה אנשים נדרשים עד להופעת ההתנגשות הראשונה, התוחלת של משתנה זה (הממוצע של המספר הזה) היא בסדר גודל של √n. בחישוב מדויק יותר עבור n גדול מתקבל E(T)≈√(π n /2).

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

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

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

יש כמה דרכים להבין למה זה קורה.

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

אפשר לחשוב כך: האדם הראשון יכול לבחור כל יום. האדם השני צריך יום אחר, אז הסיכוי שהוא בוחר יום שונה קטן מעט. ככל שמוסיפים אנשים, הסיכוי שכל הימים שונים קטן מאוד.

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

עוד עובדות קצרות: עקרון פשוט שמוודא חזרה אחת לפחות אומר שצריך 366 אנשים כדי להבטיח שני אנשים בעלי אותו יום. אבל סטטיסטית, כבר בקבוצה קטנה, כמו 23 אנשים, סיכוי להתנגשות גבוה.