בעיית המזכירה

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

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

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

יש N מועמדות שניתן לדרג מ-1 עד N לפי איכות. סדר הופעתן נבחר באופן אחיד מבין כל ה-N! האפשרויות. ההנחה היא שאפשר להשוות רק בין המועמדות שנראו עד כה, ולא לדעת כיצד הן ישוו לאלו שבאו אחר־כך.

ניתן להוכיח שאסטרטגיה מיטבית לדלג על מספר קבוע של מועמדות ואז לבחור את הראשונה שתהיה טובה מכל שקדמו לה. עבור N גדול, גודל ההדלגה שואף ל-N/e. כאן e הוא הקבוע המתמטי ℮, שהוא בערך 2.71828. משמעות הדבר היא שיש לדלג על כ־37% מהמועמדות ואז לבחור לפי הכלל הזה.

תחת אסטרטגיה כזו, ההסתברות לבחור במועמדת הטובה ביותר מתקרבת ל-1/e, כלומר לכ־0.37. התוצאה מרשימה כי אפילו מתוך 100 מועמדות, הסיכוי לבחור את הטובה ביותר גבוה יחסית לכך.

מובן שאם בוחרים מועמדת שאינה הטובה ביותר מבלי להשוות אותה לכולן, זה טעות. לכן כל מועמדת שנבחרת צריכה להיות הטובה ביותר מבין אלה שנראו עד כה. למה כדאי לדלג על מספר קבוע בתחילה? כי כך בונים סף ראשוני שמייצר השוואה משמעותית לאחר מכן. בדוגמה של N=3, אם תמיד בוחרים במקום קבוע ההסתברות להצלחה היא 1/3. אם מדלגים על הראשונה ואז בוחרים את הראשונה שהיא טובה ממנה, ההסתברות עולה ל-1/2.

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

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

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

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

דמיינו מעסיקה שמראיינת N מועמדות. היא רוצה לשכור את הכי טובה. היא יכולה להשוות רק בין מי שכבר ראתה.

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

הדרך הטובה היא לוותר על חלק מהמועמדות בהתחלה. אחרי זה לבחור את הראשונה שהיא טובה מכולן שראינו עד כה. כש-N גדול, כדאי לוותר על בערך 37% מהמועמדות.

אם ננהג כך, הסיכוי שנבחר את הטובה ביותר מתקרב לכ־37% (זהו המספר 1/e). זה נשמע מפתיע אבל נכון גם ל-100 מועמדות.

אם יש 3 מועמדות, חשוב לדלג על הראשונה ואז לבחור את הראשונה שהיא טובה ממנה. כך יגדל הסיכוי לבחור נכון מ-1/3 ל-1/2.

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

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