בעיית המזכירה
מתוך ויקיפדיה, האנציקלופדיה החופשית
בעיית המזכירה היא סוגייה מתמטית בתורת ההסתברות שמתארת מצב שבו צריך לבחור בין מספר אפשרויות שמתגלות זו אחר זו. לאחר שאפשרות מסוימת מתגלה, אפשר לבחור בה או לוותר עליה. אם בוחרים באפשרות, לא ניתן להחליף אותה באפשרות אחרת שמתגלה יותר מאוחר. אם מוותרים על האפשרות, לא ניתן לחזור אליה מאוחר יותר. מכך, הבעיה היא סוג של בעיית עצירה.
תוכן עניינים |
[עריכה] עקרונות הבעיה
סיפור שנועד להמחיש בעיה זו, ושעל שמו היא נקראת, מספר על מעסיק שמחפש מזכירה ומפרסם מודעה בעיתון שעליה עונות מספר N של מועמדות שמגיעות למשרדו (מכיוון שהבעיה נוסחה בשנות החמישים, בעת שמזכירות היו רובן נשים ולא גברים, נהוג לתאר את המועמדים למשרה בלשון נקבה). ברצונו של המעסיק לשכור את המועמדת הטובה ביותר מבין אלו שהופיעו. את המועמדות הוא מראיין אחת אחרי השנייה בסדר אקראי, ואחרי כל ראיון, עליו להחליט אם להציע למועמדת הנוכחית את המשרה או לעבור למועמדת הבאה. בעת שהוא מחליט, הוא יכול לדרג את המועמדות שראה עד עתה, אך אין ביכולתו להשוות אותן למועמדות שטרם ראיין. אם יחליט המעסיק לא להציע למועמדת הנוכחית את המשרה, היא תעלב ולא תסכים לקבל את המשרה אם לאחר שראיין עוד מועמדות יחזור ויציע לה את המשרה. לכן, על כל מועמדת חייב המעסיק או להתחייב להעסיקה או לוותר עליה. תנאי הבעיה קובעים שאם לא נשכרה אף מועמדת לפני המועמדת האחרונה, המעביד יהיה חייב לשכור אותה. בגרסה אחרת של הבעיה מסופר על רווק שחבריו סידרו לו אוסף מועמדות שיוכל לשאת לאישה, ולכן לפעמים מכנים בעיה זו "בעיית הנישואים" או "בעיית הרווק".
השאלה שסביבה כרוכה הבעיה היא כיצד אפשר להגדיל את הסיכוי לשכור את המועמדת הטובה ביותר (או להציע נישואין לאישה הטובה ביותר), ומה ההסתברות שהמועמדת הטובה ביותר תבחר תחת האסטרטגיה האופטימלית.
פתרון הבעיה מראה שעבור ערכים גדולים של N, ההסתברות לבחור במועמדת הטובה ביותר היא קצת יותר משליש, או ליתר דיוק היא קרובה ל-
או אחד חלקי הקבוע ℮ ששווה בערך 2.71828. תוצאה זו נחשבת כמפתיעה, בגלל שממבט ראשון קשה להאמין שמתוך 100 מועמדות, ההסתברות שנצליח לבחור את המועמדת הטובה ביותר תהיה כל כך גבוהה, בפרט שבחירה אקראית (למשל, אם תמיד נשכור את המועמדת החמישית שנראיין, תהיה אשר תהיה) תבחר במועמדת הטובה ביותר רק פעם אחת למאה.
[עריכה] ההיסטוריה של הבעיה
בקרב מתמטיקאים, הבעיה הייתה ידועה מתחילת שנות ה-1950, אך הבעיה והפתרון לא נכתבו או פורסמו. בפעם הראשונה שהבעיה הוזכרה בכתב הייתה בטור של מרטין גרדנר מפברואר 1960 בבטאון Scientific American. כפי שגרדנר ניסח את הבעיה, היא בעצם אינה באופן מדויק זהה לבעיית המזכירה, אך הוא התעלם מההבדלים בפתרונו והתייחס אליה כבעיית המזכירה כפי שהיא ידועה כיום (ראה הסבר מפורט למטה). הפתרון לבעיה פורסם חודש לאחר מכן, ויוחס למתמטיקאים מוזר ופאונדר. ב-1963 הציבו זוג מתמטיקאים, ב. ביסינג'ר וקונרד סיגל, את אותה הבעיה בכתב-העת המתמטי The American Mathematical Monthly כאתגר לפותרים, וכעבור כמה חודשים פורסם הפתרון, עם הערה שגם הבעיה וגם הפתרון כבר פורסמו ב- Scientific American מספר שנים קודם.
[עריכה] ניסוח הבעיה
ישנן N מועמדות למשרה, מספר שידוע מראש.
את המועמדות אפשר לדרג מ-1 עד N לפי המוסכמה שדרוג יותר גבוה ניתן למועמדת מועדפת (כלומר המועמדת המועדפת ביותר תדורג כ-N).
מכיוון שישנן N מועמדות, מספר האפשרויות שאפשר לסדר אותן בתור הוא
כדוגמה, כש-N שווה ל-3, ישנן 6 אפשרויות לסדר את שלושת המועמדות (שמסודרות מימין לשמאל):
ההנחה היא שהסדר בו המועמדות יופיעו נבחר באופן אחיד מבין כל !N הדרכים שניתן לסדר אותן.
ההנחה האחרונה שמנחה את הבעיה היא שניתן להשוות את המועמדות שכבר הופיעו ביניהן, אך לא ניתן לדעת איך הן משתוות למועמדות שעוד לא הופיעו. כלומר, אם ראינו רק חצי מהמועמדות, נוכל לקבוע איזו הטובה ביותר מביניהן, אך לא נדע מאומה איך הטובה ביותר תשתווה למועמדות שתורן עדיין לא הגיע. כדוגמה, נגיד שישנן 3 מועמדות, ונניח שכבר פגשנו את שתי המועמדות הראשונות אך לא את השלישית, ושהמועמדת השנייה הייתה עדיפה על הראשונה. מכך אפשר להסיק שהסדר של המועמדות חייב להיות אחד משלושת הבאים:
מכיוון שכל סדר מופיע בהסתברות שווה, שלושת האפשרויות סבירות באותה מידה. לכן, איננו יודעים אם המועמדת השנייה היא המועמדת הכי טובה מבין השלושה או האם המועמדת השלישית שטרם ראינו עוד יותר עדיפה. עם זאת, ניתן להסיק שההסתברות שהמועמדת האחרונה היא הטובה ביותר היא רק 1/3, משום שרק באחד משלושת האפשריות תהיה מועמדת זו הטובה ביותר, ובאותה מידה ההסתברות שהמועמדת השנייה היא הטובה ביותר הינה 2/3.
השאלה דנה באיך ניתן להגדיל את ההסתברות שנבחר במועמדת העדיפה על כל האחרות, ומהי אותה הסתברות. ניתן להוכיח שהאסטרטגיה שמבטיחה את ההסתברות הגבוהה ביותר היא לפסוח על מספר קבוע מראש של מועמדות (שתלוי במספר N), ואז לבחור את המועמדת הבאה שתבוא שתהיה מועדפת על פני כל אלה שקדמו לה (באם יש כזו – אחרת נגיע למועמדת האחרונה ולא נותר אלא לשכור אותה).
כאמור, מספר המועמדות עליו כדאי לפסוח תלוי ב-N. אבל אפשר להראות שעבור ערכים גדולים של N גדול, מספר המועמדות שעליו כדאי לוותר שואף ל-
. במילים אחרות, עבור מספר גדול של מועמדות, האסטרטגיה האופטימלית היא לפסוח על אחוז קבוע מהמועמדות (בערך 37%) ואז לבחור את המועמדת הראשונה שניקרת שמועדפת על הטובה מבין המועמדות הראשונות הללו.
כפי שכבר הוזכר לעיל, תחת אסטרטגיה זו, ההסתברות שנבחר נכון היא בערך , קרוב שיהיה יותר מדיוק ככל ש-N יותר גדול.
[עריכה] הסבר לפתרון
בהינתן שנפסח על מספר מועמדות, הסיבה מדוע כדאי לבחור במועמדת אך ורק אם היא מועדפת על כל אלה שקדמו לה ברור: אם לא ננהג כך, נבחר במודע מועמדת שאינה המועדפת ביותר, כי כבר קיימת מועמדת שראיינו קודם שמועדפת על פניה.
פחות ברור מדוע עדיף לפסוח על מספר קבוע של מועמדות ורק אז לבחור (בלי קשר לדרוג ביניהם). המקרה שבו N שווה ל-3 שופך קצת אור מדוע עדיף לפסוח על מספר מועמדות. אם נבחר תמיד במועמדת שמקומה בתור קבוע, למשל את הראשונה (או השנייה, או השלישית), ההסתברות שנבחר את המועמדת הטובה ביותר היא שליש. לעומת זאת, אם תמיד נפסח על הראשונה ונבחר את המועמדת הבאה שמועדפת עליה, ההסתברות שנבחר נכון עולה לחצי. את זה אפשר לראות על ידי ניתוח של כל האפשרויות בהן יופיעו המועמדות. במקרים הבאים, שיטה זו תבחר את המועמדת הנכונה:
ובמקרים האלו, השיטה תכשל:
מדוע האסטרטגיה מצליחה לבחור נכון בהסתברות יותר גבוהה? מצד אחד, אם המועמדת הטובה ביותר היא הראשונה, אף פעם לא נבחר בה. זה החסרון באסטרטגיה. לעומת זאת, אם כבר פסחנו על מועמדת ונתעקש לשכור מועמדת רק אם היא יותר טובה מזו שכבר פסחנו עליה, נגדיל את הסיכוי שנבחר בטובה ביותר באם היא תבוא יותר מאוחר בתור. מכך, היתרון בלפסוח על מספר מועמדות הוא שאם המועמדת הטובה ביותר תבוא יותר מאוחר, נוכל לזהות אותה יותר בקלות בגלל שנוכל להשוות אותה למספר מועמדות שכבר קדמו לה.
[עריכה] משחק גוגל
כשלראשונה העלה לכתב מרטין גרדנר את הבעיה, לה קרא "משחק גוגל", הוא ניסח אותה באופן קצת שונה מכפי שתוארה לעיל (וביסינג'ר וסיגל ניסחו את הבעיה באותה צורה כמוהו כשהציבו אותה ב-American Mathematical Monthly). ההבדל מצביע על החשיבות בלהציב בעיה כזו באופן מדויק. בפרט, גרדנר תאר מצב בו אדם כותב מספרים שונים על N פיסות נייר, זורק את כולן לכובע, ושולף אותן בסדר אקראי. הוא שאל כיצד ניתן להגדיל את ההסתברות שנבחר במספר הגבוה ביותר מבין כל הפתקים.
לכאורה, תאור זה נראה זהה לבעיית המזכירה לעיל. אך יש הבדל חשוב: בבעיה הזו, ניתן לראות את הערך של המספרים שכתובים על הפתקים. הבדל זה חשוב, משום שייתכן שנוכל להעזר בערכי המספרים עצמם לשפר את הסיכויים שנבחר נכון. זה תלוי באיך בדיוק האדם שרשם את המספרים בחר אותם. למשל, אם אנחנו יודעים שהוא כתב את המספרים השלמים מ-1 עד N, נוכל בקלות להבטיח שנבחר במספר הגבוה ביותר על ידי זה שנחכה עד המספר N ואז נפסיק. אם אנחנו יודעים שהאדם בחר את המספרים באופן אקראי ובלתי תלוי מהתפלגות קבועה, עדיין ניתן להשתמש בערכים שנראה לשפר את ההסתברות שנבחר במספר הגבוה ביותר. למשל, אם נראה מספר גבוה בפתק הראשון, נוכל להסיק שההסתברות שנראה מספר עוד יותר גבוה בעתיד נמוכה אפילו שטרם ראינו את המספרים הבאים.
להבדיל, בבעיית המזכירה ההנחה היא שניתן לדרג רק את המועמדות שהופיעו עד עתה, ואי אפשר לדעת איך הן משתוות למועמדות שעדיין לא ראינו. בפרט, למועמדת אין ערך כמו בבעיה אותה תאר גרדנר שבו נוכל אולי להעזר ולנחש איך היא תשתווה למועמדות שטרם ראינו.
כשגרדנר הציב את הבעיה, הוא התמקד על פתרונות שמתעלמים מהערכים של המספרים עצמם ומתייחסים רק לדרוג ביניהם, ולכן הפתרון שהציב זהה לפתרון בעיית המזכירה. אך אם לא נציב תנאי זה, הבעיה שהציב גרדנר אינה מוגדרת דיה בלי הסבר מדויק של איך בחר האדם את המספרים אותם הוא טמן בכובע. מבחינה זו דומה הבעיה לפרדוקס המעטפות, שמקורו נעוץ בכך שהבעיה אינה מוגדרת דיה בלי לנקוב בהתפלגות ממנה נבחרים הערכים במעטפות, ולבעיית מונטי הול, שאף היא אינה מוגדרת דיה בלי תאור מפורט של איך בוחר המנחה מתי לפתוח דלתות ואיזו דלתות יבחור.
במאמר של תומאס פרגסון מ-1989, הועלתה השאלה האם יש דרך לבחור מספרים ככה שהפתרון לבעיית המזכירה יהיה אופטימלי, כלומר האם יש דרך לבחור מספרים כך שהבוחר לא יוכל לשפר את הסיכויים שיבחור במספר הגבוה ביותר על ידי זה שהוא יתנה את בחירתו במספרים עצמם ולכן הפתרון של לדלג על מספר קבוע של מועמדות ואז לבחור את הטובה ביותר הוא האופטימלי. במקרה ש-N שווה ל-2, התשובה היא לא: תמיד נוכל לשפר את הסיכוי לבחור נכון אם נעזר בערכים עצמם. במקרה ש-N גדול מ-2, התשובה אינה ידועה. אבל, פרגסון הוכיח במאמרו שהפתרון לבעיית המזכירה הוא כמעט אופטימלי, כלומר תמיד אפשר לבחור את המספרים בדרך כזו שההסתברות שנבחר נכון תחת האסטרטגיה האופטימלית עולה על ההסתברות לפי הפתרון שמתעלם מהערכים עצמם ברמה קטנה עד כמה שנדרש.
[עריכה] הכללות של בעיית המזכירה
מתמטיקאים הציעו מספר הכללות של בעיית המזכירה הקלאסית כפי שהוגדרה כאן. להלן מספר דוגמאות:
- אפשר לחשוב על בעיית המזכירה לעיל כאילו ניתן לחזור למועמדת עליה פסחנו רק בהסתברות אפס. פרוש זה מציע את ההכללה הבאה: במקום להניח שאי אפשר לחזור למועמדת עליה כבר פסחנו, נניח שניתן לחזור אליה בהסתברות מסוימת שלאו דווקא שווה לאפס. כמובן, כשההסתברות היא אחת, הבעיה נהפכת לטריוויאלית, משום שנוכל לעבור על כל המועמדות ונחזור לטובה ביותר. אך כשההסתברות היא בין אפס לאחד, למרות שקיים סיכון שלא נוכל לחזור למועמדת שראיינו קודם, כדאי יהיה להמשיך לחפש אפילו שהפתרון המקורי היה אומר להפסיק.
- אפשר לחשוב על הבעיה של המעסיק באופן הבא: באם יבחר במועמדת הטובה ביותר הוא יזכה בנקודה, ואם יבחר במועמדת אחרת הוא יזכה באפס נקודות. תחת פרוש זה, הבעיה להגדיל את הסיכוי לבחור במועמדת הטובה ביותר שקילה לבעיה של להגדיל את תוחלת הנקודות בהן יזכה המעסיק. פרוש זה מציע את ההכללה הבאה: במקום לתת אפס נקודות לכל מועמדות שאינה המועדפת ביותר, אפשר לתת למועמדת מספר נקודות שתלוי בדרוג שלהן; מועמדת יותר טובה תזכה ביותר נקודות. למשל, המעסיק יזכה ב-N נקודות אם יבחר את המועמדת הטובה ביותר, N − 1 נקודות אם יבחר את המועמדת השנייה הכי טובה, וכן הלאה. כך אפשר לשאול כיצד תשתנה האסטרטגיה האופטימלית אם נשנה את ה"עונש" עבור בחירה לא נכונה.
- במקום להתייחס ל-N כמספר קבוע, אפשר לחשוב שהוא עצמו מספר אקראי שלא נגלה לנו מראש אך שהתפלגותו ידועה. למשל, שנפרסם מודעה בעיתון, אנחנו יודעים בערך, אך לא בדיוק, כמה מועמדות יבואו. עכשיו, כשנפסח על מועמדת, יש את הסיכון שלא תהיה מועמדת נוספת ולא נוכל לשכור מזכירה. בעיית המזכירה לעיל הינה מקרה מיוחד של הכללה זו בה ל-N יש התפלגות דגנרטית.
[עריכה] לקריאה נוספת
T. S. Ferguson. "Who solved the secretary problem?" Statistical science, volume 4, pp.282-296. 1989.
