הבעיה של מונטי הול

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

הסיטואציה הזו אינה בדיונית לגמרי; היא הופיעה, בערך (לא ממש הציעו להחליף דלת) בשעשועון טלוויזיה אותו הנחה מונטי הול, ומכאן שם הבעיה - “הבעיה של מונטי הול”. גם בישראל הייתה תוכנית (בהנחיית אברי גלעד) שכללה סיטואציה כזו (כולל החלפת הדלת). עם זאת, הבעיה עתיקת יומין עוד יותר (עוד מהמאה ה-19) ויש לה גם ניסוח קצת שונה, שאציג בהמשך.

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

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

כשנתקלתי בחידה בזמנו חשבתי שאין הבדל, והגנתי בלהט על עמדת ה-50:50. מה ששכנע אותי היה כתיבת תוכנה ש”מדמה” את המשחק והגילוי שסטטיסטית, מי שמחליף דלת אכן זוכה ב-2/3 מהמקרים. למעוניינים, הנה תוכנית בשפת פייתון שעושה זאת:

from random import randint, choice
NUM_OF_ROUNDS = 10000
PLAYER_STRATEGY = "switch"; #switch/stay/random

def play_round(): #returns 0 for failure, 1 for success
    prize_door = randint(1,3)
    player_door = randint(1,3) 
    monty_door = choice([door for door in [1,2,3] if not door in [prize_door, player_door]]) #if two doors are possible, choose uniformly
    remaining_door = 6 - (player_door + monty_door) #1 + 2 + 3 = 6
    player_door = {"switch": remaining_door, "stay": player_door, "random";: choice([remaining_door, player_door])}[PLAYER_STRATEGY]
    return 1 if (player_door == prize_door) else 0
    
success_count = sum([play_round() for round_num in range(NUM_OF_ROUNDS)])
print("Success: {}%".format((100.0 * success_count) / NUM_OF_ROUNDS))

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

הדרך האהובה עלי ביותר היא זו: נניח שהמשחק היה שונה - במקום שמונטי יפתח דלת וישאל אם אנחנו רוצים לעבור, הוא לא יפתח דלת, וישאל אם אנחנו רוצים לקבל את מה שמאחורי שתי הדלתות שבהן לא בחרנו. די ברור שההסתברות לזכות אם מחליפים מכפילה את עצמה - שתי דלתות במחיר אחת! עם זאת, מה ההבדל בין זה ובין הסיטואציה שבה מונטי מציע את אותה הצעה בדיוק, אבל פותח את הדלת ה”מיותרת” מבין השתיים (כלומר, זו שמכילה עז)? התשובה היא שאין הבדל.

עדיין, קשה להצביע על הסיבה המדוייקת שבגללה ההסתברות מוכפלת, ולכן כדאי לחדד את מה שהולך כאן. כשאנחנו בוחרים את הדלת הראשונה, הסיכוי שלנו לזכות הוא 1/3, כי רק אחת משלוש הדלתות היא הנכונה. כעת, אם בחרנו את הדלת הנכונה ונחליף אותה, מובטח לנו שנפסיד - אבל אם בחרנו את הדלת הלא נכונה ונחליף אותה, מובטח לנו שננצח. מובטח שננצח כי מונטי “נפטר” מהדלת האחרת שהייתה גורמת לנו להפסד; הוא העביר לנו מידע שלא גלוי למי שכרגע נכנס לאולם ולא יודע מה הדלת המקורית שבה בחרנו - המידע הזה הוא “אם בחרת בדלת הלא נכונה, אז כדאי לך לנסות את הדלת שבה לא בחרת ואותה לא פתחתי”. על כן, אם אנחנו תמיד מחליפים, נפסיד רק אם בחרנו את הדלת הנכונה כבר בהתחלה - וההסתברות לכך היא רק 1/3, ולכן ננצח בהסתברות 2/3.

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

למרות שהבעיה הומצאה עוד במאה ה-19, ופורסמה בידי מרטין גרדנר בסוף שנות ה-50, מה שנתן לה תנופה פרסומית היה שערוריה זוטא הקשורה אליה. מקורה בבעלת הטור מרילין ווס סוונט (vos Savant - זה שם אמיתי, מסתבר). מרילין נחשבת ל”בעלת ה-IQ הגבוה בעולם” (למיטב הבנתי, כך טוען ספר השיאים של גינס, אבל לא ברור לגמרי מה הוא - לכל היותר 230) ובאופן כללי כנראה עצבנה לא מעט אנשים לאורך הדורות. השיא הגיע כאשר בטור שאלות ותשובות שהיה לה בעיתון היא התייחסה לבעיית מונטי הול וסיפקה את הפתרון הנכון (עדיף להחליף). התוצאה? לפחות לדבריה, מתקפה המונית של אלפי קוראים לעגניים שמיהרו להוקיע אותה על “טעותה”, כולל מתמטיקאים רציניים. מאוחר יותר, בספר “המקרה המוזר של הכלב בשעת לילה”, תואר כל העניין בתוספת ציטוטים של כמה מכתבים נזעמים שכאלו (הם נשמעים מטופשים למדי), ובספר “האיש שאהב רק מספרים” העוסק בפאול ארדש נטען שארדש עצמו (אחד מהמתמטיקאים המבריקים ביותר של המאה ה-20) לא הבין בתחילה את הבעיה ופתרונה. מה הולך כאן?

לצערי, אין לי את הטור של מרילין בהישג יד, ואשמח אם מישהו יוכל לקשר לציטוט מדוייק שלו. הניחוש שלי? מרילין לא הציגה את התנאים בצורה מדוייקת מספיק, ולא התייחסה לכך שהמנחה חייב לפתוח את הדלת. כאמור, בלי התייחסות לנקודה העדינה הזו, פחות או יותר כל פתרון הוא סביר; אך מתמטיקאי רציני לא צריך להגיד “את טועה! הפתרון הנכון הוא 50:50!” או משהו בסגנון - עליו להגיד “המממ, חסרה לך כאן הנחה, הבעיה הנוכחית לא מוגדרת היטב ויש לה כמה פתרונות שונים”. בסופו של דבר, זה אחד מהדברים המרכזיים שמתמטיקאים עושים לבעיות. ציטוט ידוע אומר שמה שהמתמטיקאי באמת רוצה איננו הוכחה, כי אם הגדרה - ואכן, אחרי שכבר מגדירים במדוייק מושגים מסויימים ומנסחים היטב את התנאים למשפטים מסויימים, ההוכחה נראית קלה למדי. דוגמה נאה אחת לכך היא מושג הקומפקטיות הטופולוגי - אני מקווה להרחיב על כך בפוסט עתידי.

חזרה עכשיו לבעיה עצמה, או ליתר דיוק, לניסוח של מרטין גרדנר אליה. הניסוח אכזרי הרבה יותר - יש לנו שלושה אסירים, ומחר בבוקר יוציאו להורג אחד מהם וישחררו את השאר. אחד מהאסירים בא לסוהר ומתחנן בפניו שיגיד לו את שמו של אחד מהאסירים האחרים שישוחררו, אולם הסוהר מתנגד לכך, בטענה שבכך הוא יגדיל את הסיכוי (הסובייקטיבי) של האסיר שואל השאלה להיות מוצא להורג - מ-1/3 ל-1/2. הסוהר, מצויין במפורש, פועל כך: אם ישחררו את שואל השאלה, הסוהר יגיד את שמו של המשתחרר האחר; אם יוציאו להורג את שואל השאלה, הסוהר בוחר אחד משני האסירים האחרים בהסתברות שווה.

“אה!” אתם אומרים. “זה בדיוק מונטי הול! רק שכאן להיות מוצא להורג זו המכונית, ולכן אנחנו רוצים להפסיד. מכיוון שראינו שגילוי המידע של מונטי לא משאיר הסתברות של 50:50 לשתי האפשרויות הנותרות, הסוהר טועה, ההסתברות תישאר 1/3… רגע, היא לא אמורה לגדול ל-2/3? רגע, הפכת את הכל! מה הולך כאן?!”

טוב, זה לא אתם אומרים; זה מה שאני אמרתי כשראיתי את הבעיה. אכן, למרות שרואים שזה מונטי הול, הקשר לא ברור לי מיידית. הבה ונפתור את הבעיה הזו בצורה הכללית ביותר שלה - אם האסיר שואל השאלה (נסמנו A) מוצא להורג, הסוהר בוחר לומר “B ישוחרר” בהסתברות $latex p$, ו-“C ישוחרר” בהסתברות $latex 1-p$. הסיכוי הסובייקטיבי של האסיר להיות מוצא להורג בהתחלה הוא 1/3; למה הוא הופך אחרי שהשומר עונה? איכשהו, האינסטינקט אומר לנו דווקא שעבור $latex p=\frac{1}{2}$ ההסתברות של A להיות מוצא להורג לא תשתנה - הסוהר לא מגלה לו שום דבר שהאסיר לא יכל לנחש בעצמו (מזכיר, במעורפל, את המושג של “הוכחה באפס ידע”). עם זאת, לכל $latex p$ אחר כן ידלוף “קצת” מידע החוצה. כדי לראות את זה בבירור נלך למקרה קיצוני - $latex p=1$. במקרה כזה, אין שום סיכוי שהסוהר יענה “C” אם A יוצא להורג; מכאן שאם הסוהר ענה “C”, אז A יודע בודאות שהוא ישוחרר (אם לעומת זאת הסוהר ענה “B”, הסיכוי של A צונח פלאים).

למרות שהבעיה היא בעיה הסתברותית פשוטה למדי, לעתים קרובות נותנים אותה כתרגיל וסטודנטים רבים מתקשים; הסיבה לכך היא שמרחב ההסתברות כאן מחוכם, ולא ברור ממבט ראשון (בפרט אם מציגים את גרסת ה”50:50” של השומר בלי לדבר על $latex p$ כללי). העניין הוא בכך שמתבצעות כאן שתי הגרלות, ויש להתחשב בשתיהן - הראשונה, איזה אסיר יוצא להורג (מניחים שכל אחד נבחר בהסתברות 1/3, אחרת באמת אי אפשר לנתח כאן כלום), והשנייה, מה יענה השומר בהינתן שידוע שאסיר מסויים מוצא להורג (לדבר שכזה קוראים “הסתברות מותנית”). בלי להיכנס לעובי הקורה ההסתברותי, אפשר לומר שמרחב התוצאות האפשריות מכיל את 4 התוצאות האפשריות הבאות:

  1. C מוצא להורג והשומר אומר "B" - ההסתברות לכך היא 1/3, כי ההסתברות של "C מוצא להורג" היא 1/3 ובמקרה הזה, השומר חייב לומר "B".
  2. B מוצא להורג והשומר אומר "C" - כמו קודם, הסתברות של 1/3.
  3. A מוצא להורג והשומר אומר "B" - ההסתברות ש-A יוצא להורג היא 1/3, וההסתברות שהשומר יאמר "B" בהינתן ש-A מוצא להורג היא $latex p$, ולכן ההסתברות הכוללת שהתוצאה הזו תתקיים היא $latex \frac{p}{3}$.
  4. A מוצא להורג והשומר אומר "C" - בדומה ל-3, רק עם הסתברות $latex 1-p$ שהשומר יאמר "C", ולכן $latex \frac{1-p}{3}$.

כעת, לניתוח המדוייק - מה ההסתברות של “A מוצא להורג” (3 או 4) בהינתן שהשומר עונה “B”, (כלומר, 1 או 3)? לדבר כזה קוראים חישוב של הסתברות אפוסטריורי, כלומר - למרות שקודם הוגרל המאורע של “מי יוצא להורג” ורק אחר כך המאורע של “מה יגיד השומר”, אנחנו מסיקים מהמאוחר יותר משהו על המוקדם יותר. אחת מהנוסחאות הבסיסיות והנאות ביותר בהסתברות (לטעמי) היא נוסחת בייס, שנותנת את ההסתברות האפוסטריורית על בסיס ההסתברות האפריורית (ההסתברות שהמאורע המאוחר יותר יקרה בהינתן שמאורע מוקדם יותר קרה). ההסתברות שהשומר יאמר “B” בהינתן ש-A מוצא להורג היא, כאמור, $latex p$. על פי בייס, יש “לתקן” אותה על ידי כפל בהסתברות של “A מוצא להורג” חלקי “השומר אומר B”. ההסתברות של “A מוצא להורג” היא 1/3, ואילו ההסתברות של “השומר אומר B” (וכאן החלק ה”עדין) היא $latex \frac{1}{3}+\frac{p}{3}=\frac{1+p}{3}$ - זה סכום ההסתברויות של 1 ו-3 גם יחד. התוצאה הסופית? ההסתברות ש-A יוצא להורג בהינתן שהשומר אמר “B” היא $latex \frac{p}{p+1}$.

כעת אפשר לשחק טיפה עם הנוסחה - מציבים בה 1/2 ומגלים שההסתברות של A לא משתנה אם השומר עונה “B” - היא נותרת 1/3. אם מציבים 1, מקבלים שההסתברות של A להיות מוצא להורג קפצה ל-1/2, ואם מציבים בה 0 - שההסתברות שלו ירדה ל-0; אבל לכל הצבה של ערך שונה מ-1/2 בנוסחה נקבל הסתברות שונה מ-1/3, כלומר כל ערך שונה מ-1/2 אכן נותן אינפורמציה כלשהי.

אבל איפה מונטי הול כאן? איפה ה”כדאי להחליף”? קודם הרי דרשנו בכוח שהמנחה יהיה אובייקטיבי ויפתח דלת בהסתברות 1/2, מה נשתנה? התשובה היא שלא השתנה כלום; פשוט הסתכלנו על הבעיה מזווית ראייה שונה. נסו לחשוב מדוע. אני מקווה שלא אזכה ל-10,000 תגובות נזעמות בשל כך.


נהניתם? התעניינתם? אם תרצו, אתם מוזמנים לתת טיפ:

Buy Me a Coffee at ko-fi.com