חיפוש באתר

קישורים

RSS סטטיסטיקה ברשת

עמודים

קטגוריות

תגיות

בעיית המטריות: איך לא להירטב?

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

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

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

לדוגמא, נניח שיש לנו שרשרת מרקוב שבה יש שלושה מצבים אפשריים. נסמן אותם בספרות 0, 1, ו-2. השרשרת יכולה להראות כך: 0, 2, 1, 0, 0, 2, 1, 2, … וכן הלאה. פירוש הדבר הוא שהתחלנו במצב 0, משם עברנו למצב 2, משם עברנו למצב 1, וכן הלאה.

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

כלל מעבר אפשרי כאשר נמצאים במצב 0, הוא שעוברים ממנו למצב 1 בהסתברות 1/2, עוברים למצב 2 בהסתברות 1/3, או שנשארים במצב 0 בהסתברות 1/6.[1]. באופן דומה יש לנו כללי מעבר דומים כאשר נמצאים במצב 1 או במצב 2.

עכשיו נראה איך המושג של שרשרת מרקוב עוזר לנו לפתור את בעיית המטריות.

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

איך הוא עובר ממצב למצב? זה תלוי בהסתברות שירד גשם. ההסתברות הזו לו נתונה לנו, ולכן אניח כי ההסתברות שירד גשם במקום בו הוא נמצא ועומד לצאת לדרכו היא קבועה ושווה ל-P כאשר P הוא מספר כלשהו בין 0 ל-1 (לא כולל את 0 ו-1). בכך הגדרנו מודל המתאר את תנאי החידה.[2]

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

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

כמובן, אם הוא נמצא במצב 0 ויורד גשם, אז הוא יירטב.

כעת אטען כי אם נסתכל על כל הפעמים שהוא נמצא במצב 1, בסופו של דבר הוא יעבור בודאות למצב 0. תחשבו על קוביה. אם תטילו אותה פעם אחת, ההסתברות שהיא תראה 6 היא 1/6. אבל ככל שתטילו אותה יותר ויותר פעמים גדל הסיכוי ש-6 יופיע בסופו של דבר. יתרה מזאת, אם נמשיך להטיל את הקוביה עוד ועוד, המספר 6 יופיע עוד ועוד פעמים. אם נטיל את הקוביה אינסוף פעמים, המספר 6 יופיע אינסוף פעמים, וזאת בהסתברות של 100%.[3].

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

מה קורה אם יש לו יותר ממטריה אחת?

כעת המצבים הם 0, 1 , ו-2.

אם יש לו מטריה אחת (מצב 1), הוא יעבור למצב 2, בו יש לו שתי מטריות, בהסתברות P (יורד גשם, והוא לוקח איתו את המטריה למקום שיש בו כבר מטריה אחת) או שיישאר במצב 1 (לא יורד גשם, ולכן הוא הולך בלי מטריה למקום ששיש בו מטריה אחת).

אם יש לו 2 מטריות הוא נמצא במצב 2, ויכול לעבור משם למצב 0 (כאשר לא יורד גשם, ולכן הוא הולך למקום בו אין לא אף מטריה) או לעבור למצב 1 (יורד גשם, הוא לוקח עימו מטריה למקום בו אין מטריות, ולכן תעמוד שם לרשותו מטריה 1.

אם הוא במצב 0 ויורד גשם הוא יירטב.

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

ומה אם יש לו המון מטריות? 4, או 50 או 1000? זזה לא משנה. הטיעון עדיין עובד. בסופו של דבר הוא יגיע למצב 0 כאשר יורד גשם, כלומר בסופו של דבר הוא יירטב.

מסקנה: תמיד תקחו אתכם את המטריה.


הערות
  1. ודאו ששלושת ההסתברויות שציינתי מסתכמות ל-1! []
  2. אני סבור שגם כאשר P משתנה ואינו קבוע כל הזמן אפשר להגדיר שרשרת מרקוב מתאימה, עם מספר אינסופי של מצבים, ולהגיע לאותה תשובה, אך לא אכנס לזה כאן, או בכלל []
  3. אפשר להוכיח זאת באופן מתמטי []

5 תגובות ל“בעיית המטריות: איך לא להירטב?”

  • תגובה מאת איל
    תאריך 3 בנובמבר 2017 10:44

    האמת שזה נכון רק אם ההסתברות לגשם היא לא 1 או 0.

    • תגובה מאת יוסי לוי
      תאריך 3 בנובמבר 2017 17:43

      נכון, וכך כתבתי.

  • תגובה מאת י. פורת
    תאריך 3 בנובמבר 2017 12:20

    *שלוש* ההסתברויות שציינת מסתכמות ל-1.

  • תגובה מאת שמואל
    תאריך 4 בנובמבר 2017 21:33

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

    • תגובה מאת יוסי לוי
      תאריך 7 בנובמבר 2017 06:55

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

תגובה