משפט הקופים

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

אפשר לגשת לחידה הזו בכמה צורות.

הגישה ה-“נאיבית”

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

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

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

עכשיו רק צריך לשקלל את האפשרויות בהסתברויות שלהן. כלומר לחשב את זה:

זה דורש קצת אלגברה, ואני אדלג על החישוב ברשותכם. התוצאה היא 4.

גישה שניה: מציאת בעיה דומה

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

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

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

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

• שני הכדורים בסל הימני
• שני הכדורים בסל השמאלי
• כדור א בסל הימני וכדור ב בסל השמאלי
• כדור א בסל השמאלי וכדור ב בסל הימני

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

אז בעצם יכולנו להקל על הקוף ולתת לא להטיל מטבע. אם יצא פלי, מה חבל. אם יצא עץ, הקוף יכול לטפס על העץ ולקטוף לעצמו בננה.

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

גישה שלישית: שרשרת מרקוב – לא להיבהל!

דיברתי כבר על שרשראות מרקוב כאשר דנתי בבעיית המטריות. שאלת הקוף היא עוד דוגמא נחמדה לשרשרת מרקוב.

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

לשרשרת של הקוף יש שלושה מצבים:

1. שני סלים ריקים. נסמן מצב זה ב-00.
2. סל אחד ריק ובשני יש כדור. נסמן מצב זה ב-01.
3. כדור אחד בכל סל. נסמן מצב זה ב-11.

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

אם הקוף במצב 01 יכולים לקרות שני דברים: או שהוא שם את הכדור הבא בסל שכבר יש בו כדור. בסל יש שני כדורים, מרוקנים אותו, והקוף חוזר למצב 00. זה קורה בהסתברות חצי. הדבר השני שיכול לקרות הוא שהקוף ישים את הכדור בסל הריק, יגיע למצב 11, יקבל בננה, והמשחק נגמר. גם זה יכול לקרות בהסתברות חצי.

אם הקוף במצב 11 הוא כבר לא מתעניין בנו, כי יש לו בננה. ההסתברות לעבור ממצב 11 למצב 00 או 01 היא 0. המצב הבא, אם נתעקש, יהיה שוב 11. כלומר, ממצב 11 עוברים למצב 11 בהסתברות 1.

הנה תיאור ציורי של השרשרת:

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

איך כל זה עוזר לנו?

נניח שממוצע מספר הצעדים/כדורים מ-00 ל-11 הוא X.

כפי שראינו קודם, X שווה ל-2 בהסתברות 0.5.

אבל אם בשני הצעדים הראשונים שלו הקוף יצא מ-00 וגם חזר לשם, אז ממוצע מספר הצעדים שנותרו לו מעכשיו הוא גם כן X! וזאת מכיוון שמצבו עכשיו, לאחר שני צעדים לא שונה מהמצב ההתחלתי. כלומר, ממוצע מספר הצעדים אם אנחנו יודעים שהוא כבר עשה סיבוב אחד של 00 ל-01 ל-00 הוא 2+X. ההסתברות שזה יקרה גם כן שווה לחצי. ולכן

פתרון המשוואה הזו הוא X=4.

משפט הקופים

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

רגע? מה?

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

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

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

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

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

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