פתרון מקורב ומדויק לפרדוקס יום ההולדת

מחבר:
בתאריך:

מהו המספר המינימלי של אנשים אותם צריך לאסוף לחדר אחד כדי להבטיח הסתברות של לפחות 50% לכך ששני אנשים כלשהם בחדר חולקים בדיוק את אותו תאריך יום הולדת (חודש ויום)? רוב בני האדם לא ינחשו שהתשובה היא 23 אנשים בלבד. זהו פרדוקס יום ההולדת.

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

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

 

מדוע אנשים טועים בהערכה?

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

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

הסבר קומבינטורי קצר:

כדי לחשב כמה זוגות שונים שניתן להשוות ביניהם יש בחדר של $N$ אנשים, אנו משתמשים בנוסחה לבחירת זוג מתוך קבוצה הלקוחה מתחום הקומבינטוריקה:

$$ \binom{N}{2} = \frac{N \times (N - 1)}{2} $$
  • האדם הראשון (אדם א') יכול להרכיב זוג עם כל אחד מ-$N-1$ האנשים האחרים בחדר ($22$ אנשים).
  • האדם השני (אדם ב') רוצה כעת למנות את כל הזוגות שבהם הוא חבר ועדיין לא נספרו. את הזוג (ב', א') כבר ספרנו בשלב הקודם (כשהסתכלנו על אדם א'). לכן, כדי לא לספור את אותם אנשים פעמיים, לאדם ב' נשאר ליצור זוגות חדשים רק עם האנשים אותם טרם ספרנו. כלומר, כל האנשים אחריו שמספרם $ N - 2 $ שהם $21$ אנשים. בסה"כ $21$ זוגות נוספים.
  • לשלישי נשארו $ N - 3 $ או 20 זוגות שהוא יכול ליצור.
  • וכן הלאה...

עבור $23$ אנשים, החישוב הוא:

$$\frac{23 \times 22}{2} = 253$$

כלומר, בחדר של $23$ אנשים בלבד יש $ 253 $ זוגות שונים שלכל אחד מהם יש סיכוי לחלוק יום הולדת!

כאשר מבינים שמדובר ב-$253$ הימורים נפרדים (ולא ב-$23$), פתאום הסיכוי להצלחה של לפחות $50\%$ נראה סביר לחלוטין.

 

פתרון מתמטי מקורב לפרדוקס יום ההולדת

כשאנחנו שואלים: "מה הסיכוי שלפחות זוג אחד בחדר חוגג יום הולדת באותו יום?", לחשב את זה ישירות זה סיוט כי זה כולל המון תרחישים שונים:

  • בדיוק זוג אחד חולק יום הולדת.
  • שני זוגות שונים חולקים יום הולדת.
  • שלישייה חוגגת באותו יום.
  • רביעייה... וכן הלאה.

ממש כאב ראש.

אז איך פותרים את זה?

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

משלים?

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

 

כלל העוגה (עוגת ההסתברות של 100%) שמסביר את המשלים

סך כל האפשרויות בעולם מסתכם תמיד ב-$100\%$ (או $1.0$ במספרים). מה שאומר שהסיכוי לאירוע והמשלים שלו הוא תמיד 100%. לדוגמה, אם הסיכוי ליום הולדת משותף הוא 40% אז הסיכוי המשלים של "אין יום הולדת משותף" הוא 60%. ובמקרה הכללי:

$$ \text{הסיכוי לאין יום הולדת משותף} + \text{הסיכוי ללפחות יום הולדת אחד משותף} = 100\% $$

ואם אנחנו רוצים שהסיכוי ללפחות יום הולדת משותף אחד יהיה לפחות 50%, זה אומר שאנחנו חייבים שהסיכוי לאף לא יום הולדת אחד משותף ירד לפחות מ-50% כי זו הדרך היחידה להשלים ל-100%.

הסיכוי של הראשון הוא בדיוק 365/365 כי לא משנה באיזה יום בשנה הוא יוולד. מה שמותיר לבא אחריו רק 364/365 ימים שבהם הוא יכול להיוולד בלי חפיפה בתאריך לראשון. מה שמותיר לבא אחריהם 363/365 וכן הלאה עד שמגיעים לאדם ה-n בסדרה.

תחת הנחת אי תלות בין האנשים כדי לגלות את ההסתברות המשותפת צריך לכפול בין ההסתברויות.

מכפלת ההסתברויות צריכה להיות קטנה או שווה מ-0.5 כדי להבטיח סיכוי של לפחות 50% לאותו תאריך. נכתוב את זה כך:

$$ \frac{365}{365} \times \frac{364}{365} \times \frac{363}{365} \times ... \times \frac{365-n+1}{365} $$ $$ (1 - \frac{0}{365}) \times (1 - \frac{1}{365}) \times (1 - \frac{2}{365}) \times ... \times (1 - \frac{n-1}{365}) $$

עבור x קטן מאוד ניתן להשתמש בקירוב טיילור:

$$ 1 - x \approx e^{-x} $$

בהנחה ש- $ \frac{1}{365} $ הוא שבר קטן מספיק מתקבל:

$$ 1 - \frac{1}{365} \approx e^{-\frac{1}{365}} $$

נעשה את אותו קירוב עבור יתר השברים כי גם הם קטנים מספיק. מה שיביא אותנו לצורה:

$$ e^{-\frac{0}{365}} \times e^{-\frac{1}{365}} \times e^{-\frac{2}{365}} \times ... \times e^{-\frac{n-1}{365}} $$

חוקי כפל חזקות מאפשרים את חיבור החזקות כאשר הבסיס זהה, ולכן:

סכום של סדרה חשבונית הוא:

$$ S_n = \frac{n(a_1 + a_n)}{2} $$

ולפיכך הסכום של רצף שמתחיל ב-1 ומסתיים ב-$ n-1 $ יהיה:

$$ 1 + 2 + … + (n-1) = \frac{(n-1)(1+n-1)}{2} = \frac{n(n-1)}{2} $$

נציב חזרה בחזקה:

$$ e^{-\frac{n(n-1)}{365 \times 2}} = e^{-\frac{n(n-1)}{730}} $$

אותנו מעניין שלפחות זוג אחד יחלוק יום הולדת בסבירות $ 50% $ לפחות:

$$ e^{-\frac{n(n-1)}{730}} \le 0.5 $$

נוציא לוג משני האגפים:

$$ -\frac{n(n-1)}{730} \le ln(0.5) $$

כדי לפתור את אי-השוויון נכפיל את שני האגפים ב- $-1$ (תוך הפיכת כיוון סימן אי-השוויון):

$$\frac{n(n-1)}{730} \ge -\ln(0.5)$$

מכיוון ש- $-\ln(0.5) = \ln(2)$:

$$\frac{n(n-1)}{730} \ge \ln(2)$$

נכפול ב- $730$:

$$n(n-1) \ge 730 \cdot \ln(2)$$

נציב את הערך המספרי $\ln(2) \approx 0.69315$:

$$730 \cdot \ln(2) \approx 505.997$$

נקבל את אי-השוויון הריבועי:

$$n^2 - n - 506 \ge 0$$

נפתור את המשוואה הריבועית השקולה $n^2 - n - 506 = 0$ באמצעות נוסחת השורשים:

$$n = \frac{1 \pm \sqrt{1 - 4 \cdot 1 \cdot (-506)}}{2} = \frac{1 \pm \sqrt{1 + 2024}}{2} = \frac{1 \pm \sqrt{2025}}{2}$$

מכיוון ש- $\sqrt{2025} = 45$, ועבור גודל קבוצה נתייחס לשורש החיובי בלבד:

$$n = \frac{1 + 45}{2} = 23$$

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

 

פתרון מדויק לבעית יום ההולדת

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

$$ P(\text{שונים}) = \frac{365}{365} \times \frac{364}{365} \times \frac{363}{365} \times \dots \times \frac{365 - n + 1}{365} $$

אלגוריתם החישוב:

  1. הגדרת יעד: מצא את $n$ הקטן ביותר עבורו ההסתברות שללפחות שני אנשים יש יום הולדת משותף קטנה או שווה ל-target_probability (למשל, $0.5$).
  2. העברה למאורע המשלים: כיוון ש-$P(\text{משותפת}) = 1 - P(\text{שונים})$, התנאי שקול לכך ש-$P(\text{שונים}) \le 1 - \text{target\_probability}$.
  3. חישוב מצטבר בלולאה: מתחילים מ-$n=0$ עם הסתברות של $1.0$ ($100\%$). בכל שלב (עבור האדם ה-$n$-י), מכפילים את ההסתברות המצטברת בשבר $\frac{365 - n + 1}{365}$, וממשיכים בלולאה כל עוד ההסתברות $P(\text{שונים})$ עדיין גבוהה מהסף המבוקש.
def exact_number_of_people(target_probability: float):
   # Probability of at least one shared birthday = 1 - P(all distinct birthdays)
   # So we loop until P(all distinct) <= 1 - target_probability
   max_distinct_probability = 1.0 - target_probability


   numerator = 365
   denominator = 365
   p_all_distinct = 1.0
   count_people = 0


   while p_all_distinct > max_distinct_probability:
       count_people += 1
       p_all_distinct *= numerator / denominator
       numerator -= 1


   print(
       f"Number of people required for at least {target_probability:.0%} "
       f"probability of a shared birthday: {count_people}"
   )


exact_number_of_people(0.5)

 

סיכום

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

 

אולי יעניין אותך?

פרדוקס מונטי הול: למה כדאי להחליף גם כשזה לא נראה הגיוני במבט ראשון (או שני)?

מעשה במקטרת: איך הוכחה אשמת עישון סיגריות בסרטן הריאות עוד בטרם נאספו מספיק ראיות

מתאן - הגורם המתעתע בתהליך שינוי האקלים

 

לכל המדריכים בסדרת המסע לתודעת הטבע

 

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים

 

 

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

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

שימו לב! הסקריפטים במדריכים מיועדים למטרות לימוד בלבד. כשאתם עובדים על הפרויקטים שלכם אתם צריכים להשתמש בספריות וסביבות פיתוח מוכחות, מהירות ובטוחות.

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

השימוש שלך באתר מהווה ראייה להסכמתך עם הכללים והתקנות שנוסחו בהסכם תנאי השימוש.

הוסף תגובה חדשה

 

 

ענה על השאלה הפשוטה הבאה כתנאי להוספת תגובה:

מהם שלוש רשויות השלטון בישראל?