חידת מעטפות

לכבוד סוף השנה, חידה: אתם נמצאים בחדר שבו נמצאות שתי מעטפות, כל אחת עם סכום כסף שנבחר באקראי (לדקדקנים – נבחר מתוך התפלגות כלשהי על המספרים הממשיים – לא ידוע לכם איזו התפלגות). אתם בוחרים באקראי (כלומר, בהסתברות 50:50) את אחת המעטפות, פותחים אותה ורואים את הסכום שבפנים. כעת מאתגרים אתכם – החליטו אם להחליף או לא. המטרה: למצוא שיטת החלטה שבה מובטח שבהסתברות של יותר מ-$latex \frac{1}{2}$ תסיימו עם הסכום הגדול יותר מבין השניים. מה עושים?

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

למעשה, שיטת הפעולה של "תחליף תמיד" בבירור לא תיתן הסתברות גבוהה מחצי; אם מלכתחילה בחרנו את המעטפה בעלת הסכום הגבוה יותר (בהסתברות $latex \frac{1}{2}$), אז נפסיד, ואחרת (גם כן בהסתברות $latex \frac{1}{2}$) ננצח. אם כן, יש לנו כאן חידה ששונה מהותית מפרדוקס המעטפות – ועל פניו לא ברור אם היא פתירה בכלל. קחו עכשיו מספר דקות וחשבו על החידה – לאחר מכן אנסה להציג שני פתרונות שונים עבורה.

האתגר שהחידה הזו מציבה נעוץ בכך שאין לנו מושג אילו סכומים נמצאים במעטפות ועל פי מה נקבע איך הם הגיעו לשם. אנחנו צריכים שיטה שתהיה טובה באופן כללי, לכל זוג אפשרי של מספרים $latex a,b$ שיכולים להיות במעטפות. נבחר את הסימונים לשני הסכומים הללו כך ש-$latex a$ הוא הקטן יותר, כלומר $latex a\le b$. השאלה הראשונה, אם כן, היא מה בעצם ידוע לי ובמה אני יכול להשתמש.

ובכן, כל מה שידוע לי הוא הערך שנמצא במעטפה שפתחתי, אותו אסמן ב-$latex x$. כלל ההחלטה שלי ניתן יהיה לתיאור באופן כללי בתור פונקציה $latex f\left(x\right)$ שלכל $latex x$ מתאימה את ההסתברות שאבחר לא להחליף. עד כאן פורמליסטיקה, וכעת נפנה לפתרון כלשהו. האינטואיציה הראשונה שלי בתרגיל הזה היא שככל ש-$latex x$ גדול יותר, כך אני אתפתה פחות להחליף אותו. הדרך הפורמלית לבצע משהו כזה היא לבחור בתור $latex f$ פונקציה שעולה תמיד (כלומר, אם $latex x<y$ אז $latex f\left(x\right)<f\left(y\right)$) ועם זאת ערכיה נמצאים כל הזמן בתוך התחום $latex \left[0,1\right]$ (אחרת היא לא מייצגת הסתברות). לא קשה לבנות פונקציות כאלו – למשל באמצעות מניפולציה על הפונקציה $latex \arctan$ (הפונקציה ההופכית לטנגנס) – זוהי פונקציה עולה ממש שערכיה נעים בתחום $latex \left[-\pi/2,\pi/2\right]$, כך שרק צריך "לכווץ" אותה מעט ו"להרים" אותה מעט כדי לקבל $latex f$ כמו שרציתי. ברשותכם אפסח על הפרטים הטכניים הללו.

ובכן, מסתבר ש-$latex f$ שכזו עובדת מצויין. בואו נחשב את ההסתברות שאנצח, אם אני נעזר ב-$latex f$ הזו. ההסתברות שאנצח היא ההסתברות שאבחר בהתחלה את $latex a$ (בהסתברות חצי) ואז בגלל $latex f$ אבחר להחליף (בהסתברות $latex 1-f\left(a\right)$), ועוד ההסתברות שאבחר בהתחלה את $latex b$ (שוב, בהסתברות חצי) ואז בגלל $latex f$ אבחר דווקא לא להחליף (בהסתברות $latex f\left(b\right)$). מה ההסתברות שלי לנצח? $latex \frac{1}{2}\cdot\left(1-f\left(a\right)\right)+\frac{1}{2}\cdot f\left(b\right)=\frac{1}{2}\left(1+f\left(b\right)-f\left(a\right)\right)=\frac{1}{2}+\frac{1}{2}\left(f\left(b\right)-f\left(a\right)\right)$, והסתברות זו גדולה ממש מחצי כאשר $latex a<b$, כי אז $latex f\left(a\right)<f\left(b\right)$, כלומר $latex f\left(b\right)-f\left(a\right)>0$ (אם $latex a=b$ אז אני מנצח תמיד, כי לא משנה מה אעשה – אסיים עם הסכום הגדול מבין השניים, שבמקרה זה הם שווים).

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

מה קורה כאן? צריך להבדיל בין שלושה מקרים אפשריים, לפי הזהות של המספר שהגרלתי, שאסמנו $latex y$. אם $latex y\le a<b$, אז לא משנה מה נמצא במעטפה שפתחתי, אני לא הולך להחליף; לכן ההסתברות שלי להצליח היא בדיוק חצי. באופן דומה, אם $latex a<b<y$ אז לא משנה מה נמצא במעטפה שפתחתי, כן אחליף, ולכן שוב ההסתברות שלי להצליח היא חצי. האקשן מתחיל כאשר $latex a<y\le b$; במקרה זה תמיד אנצח. לא משנה אם ראיתי את $latex a$ או $latex b$. אם ראיתי את $latex a$, אז ה-$latex y$ שהגרלתי גדול יותר ממנו, ולכן אחליף ואנצח; ואם ראיתי את $latex b$ אז ה-$latex y$ שלי קטן יותר ממנו ולכן לא אחליף ואנצח.

הבה ונעשה כעת את החישוב הפורמלי. אנחנו צריכים להבדיל בין ההסתברות של שלושה מקרים: $latex P\left(y\le a\right),P\left(y>b\right),P\left(a<y\le b\right)$. אלו שלושת המקרים האפשריים היחידים, ולכן סכום ההסתברויות שלהם הוא 1, וכדי לחשב את ההסתברות שאנצח צריך לכפול כל אחד מהם בהסתברות לנצח בהניתן שהוא קרה. נקבל את הסכום הבא:

$latex \frac{1}{2}P\left(y\le a\right)+\frac{1}{2}P\left(y>b\right)+P\left(a<y\le b\right)$

$latex = \frac{1}{2}\left(P\left(y\le a\right)+P\left(y>b\right)+P\left(a<y\le b\right)\right)+\frac{1}{2}P\left(a<y\le b\right)$
$latex = \frac{1}{2}+\frac{1}{2}P\left(a<y\le b\right)$

אם כן, שוב קיבלתי הסתברות הצלחה של "חצי ועוד קצת". כל מה שנדרש ממני הוא שההתפלגות שבה אני בוחר את $latex y$ תהיה כזו שבה לכל $latex a<b$, ההסתברות שיתקיים $latex a<y\le b$ תהיה חיובית. התפלגות נורמלית היא הדוגמה הקלאסית להתפלגות שבה זה מתקיים, אך כאמור – כל התפלגות עם פונקצית צפיפות הסתברות חיובית תמיד עובדת (ואין בעיה גם עם פונקציות מוגבלות יותר, עם נקודות אי רציפות סליקות – אבל למה לחפור בכך?)

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

26 תגובות על הפוסט “חידת מעטפות

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

  2. וואו.
    כנראה שזה אחד מהדברים הכי יפים שראיתי השנה במתמטיקה.

    תודה רבה ושנה טובה.

  3. עמית, כמו שאמרתי – אפשר לבחור פונקציות יותר מוגבלות, אבל למה לחפור בכך? וכאמור – היופי בפתרון הוא שאני לא מניח שום ידע כלשהו על האופן שבו a,b נבחרים. כלום. אפס.

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

    שנה טובה!

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

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

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

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

    P(x) = 0 אם x=y

    כאשר y הואהמספר שהגרלת.

  9. משהו רע קרה לתגובה שלי.
    לפני השליחה היא נראתה תקין.

    נסיון נוסף:

    p(x) = 0 אם x=x

    אצבעות שלב. שגר.

  10. לא הצליח.

    בעברית:
    פי (איקס) שווה אפס אם איקס קטן מ-ווי.
    פי(איקס) שווה אחד אם איקס גדול שווה ל-ווי.

    ווי הוא המסספר שהגרלת, כמו בפוסט.

  11. מכיוון שחשבתי בעצמי על השיטה הראשונה ושמעתי על השנייה ממקור אחר, אני מאוד מרוצה מהאבחנה שלך :)

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

  13. תודה על המאמר המעניין.

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

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

  15. פוסט מאוד מעניין ונוגד אינטואיציה.

    רק יש לי שאלה –
    בעצם, אם אתה לא מחליף,
    ההסתברות שתגמור עם המעטפה עם הסכום הגדול יותר שווה להסתברות שתבחר את a(חצי) ועוד ההסתברות שa שווה b כפול ההסתברות שתבחר את b.
    כלומר ההסתברות שתקבל את הסכום הגדול יותר גדולה מחצי.
    איפה הטעות שלי?

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

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

  18. אם קשה לכם לדמיין הגרלה של מספרים ממשיים או שקשה לכם עם התחום ה"אינסופי", מה שיכול לעזור להבנה הוא אם תפשטו את המשחק, נניח שהשחקן שבוחר את הסכומים שם במעטפות מספר שלם(!) של שקלים בין אחת למאה, כל מה שעליכם לעשות כעת הוא להטיל קוביה בעלת מאה פאות כך שהסיכוי לקבל כל פאה הוא 1/100, בצעו את החישוב מחדש ותגיעו למסקנה שהסיכוי שנבחר במעטפה הטובה יותר הוא גדול מחצי

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

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

  21. השיטה השנייה היא בעצם להגיד ״נחש בצורה כלשהי מה כמות הכסף במעטפה השנייה ותחליט לפי זה״? ומה שמראים אחרי זה זאת העובדה שלמרות שזה ניראה סתמי לגמרי זה שיש לשיטה הזאת יותר סיכויים לעבוד מאשר לא לעבוד?

כתיבת תגובה

האימייל לא יוצג באתר.