חידת מעטפות

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

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

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

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

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

ובכן, מסתבר ש-\(f\) שכזו עובדת מצויין. בואו נחשב את ההסתברות שאנצח, אם אני נעזר ב-\(f\) הזו. ההסתברות שאנצח היא ההסתברות שאבחר בהתחלה את \(a\) (בהסתברות חצי) ואז בגלל \(f\) אבחר להחליף (בהסתברות \(1-f\left(a\right)\)), ועוד ההסתברות שאבחר בהתחלה את \(b\) (שוב, בהסתברות חצי) ואז בגלל \(f\) אבחר דווקא לא להחליף (בהסתברות \(f\left(b\right)\)). מה ההסתברות שלי לנצח? \(\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)\), והסתברות זו גדולה ממש מחצי כאשר \(a, כי אז \(f\left(a\right), כלומר \(f\left(b\right)-f\left(a\right)>0\) (אם \(a=b\) אז אני מנצח תמיד, כי לא משנה מה אעשה - אסיים עם הסכום הגדול מבין השניים, שבמקרה זה הם שווים).

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

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

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

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

\(= \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)\)
\(= \frac{1}{2}+\frac{1}{2}P\left(a<y\le b\right)\)

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

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