בעיית המזכירה, ואיך זה קשור למספרים הרמוניים

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

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

על 4 אין פשרות!

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

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

"הגיעו היום 30 מועמדות שמתוכן אני צריכה לבחור, אז את 10 הראשונות אני דוחה בלי לחשוב בכלל, ומה-11 והלאה אני בודקת אם היא הטובה ביותר מבין כל אלו שהתראיינו עד כה, ואם כן – אני מקבלת אותה".

אתם מתרעמים – מה זו שיטת הבחירה המטופשת הזו? למה לדחות אוטומטית את 10 הראשונות? מה אם המזכירה הכי טובה היא בין 10 הראשונות? למה לא לחכות עד המזכירה ה-20? אין דרך חכמה יותר לבחור? חיש קל אתם מפטרים את המראיינת הסוררת. הבעיה היא בוודאי בכך שהיא עצמה לא נבחרה על פי כללי נזיר השאולין שלכם.

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

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

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

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

אם כן, מהשהסכמנו שהכלל שמוביל לבחירת מזכירה הוא "היא הטובה ביותר מבין מי שראיינו עד כה", נשאלת רק השאלה מתי להפעיל אותו. הרי ברור שיהיה מטופש להפעיל אותו כבר מהרגע הראשון – המזכירה הראשונה שאנחנו מראיינים היא הטובה ביותר מבין מי שראיינו עד כה, אבל אם המזכירות באות בסדר אקראי, ההסתברות שלנו לבחור במזכירה הטובה ביותר באופן הזה היא $latex \frac{1}{n}$. בדוגמה של ה-30 מזכירות שלנו, זו הסתברות של $latex \frac{1}{30}$, כלומר קצת פחות מ-4 אחוזים. אם יש 1000 מזכירות אז ההסתברות צונחת לה ל-0.1 אחוזים מביכים. ואנחנו אמרנו שבשיטה האופטימלית אפשר להצליח ב-37 אחוז מהפעמים בלי קשר בכלל למספר המזכירות – אני מקווה שאחוזי ההצלחה הללו (ובעיקר, האופן שבו הם לא תלויים בכלל במספר המזכירות) נראים כבר יותר מרשימים מאשר אולי נראו במבט ראשון.

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

אם כן, תוך כמה צעדים כדאי להתחיל להפעיל את הכלל? התוצאה המפתיעה (?) היא שמדובר על $latex \frac{n}{e}$ צעדים, כאשר $latex e=2.71828183\dots$ הוא בסיס הלוגריתם הטבעי – הקבוע המפורסם ביותר במתמטיקה חוץ מ-$latex \pi$. אמרתי כבר בבלוג שאני אוהב את $latex e$ יותר, והבעיה הזו היא דוגמה נוספת לסיבה לכך – $latex e$ צץ במקומות עוד יותר מגוונים מאשר $latex \pi$ לטעמי.

אוקיי, החימום נגמר – כדי להוכיח שמספר הצעדים האופטימלי הוא $latex \frac{n}{e}$ אין מנוס מהפשלת שרוולים וחישוב טיפה טכני, אבל יפה מאוד לטעמי ולא קשה כל כך. הגישה שלנו תהיה של "מבט מלמעלה" – ננסה להבין מה קורה כאשר מפעילים את השיטה עם $latex k$ צעדים שאחריהם מתחילים להפעיל את הכלל, ונחשב עבור $latex k$ זה מה הסתברות ההצלחה שלנו.

אז שוב, כדי שכולם יהיו איתי: עבור $latex k$ טבעי כלשהו ו-$latex n$ מזכירות, אנו בודקים מה ההסתברות לבחור את המזכירה הטובה ביותר אם את $latex k-1$ הראשונות אנו דוחים, ומקבלים את המזכירה הראשונה אחרי אותן $latex k$ שהיא טובה יותר מכל מי שהיו עד כה (אם אין כזו, אכלנו אותה).

כאשר דיברתי בבלוג על הסתברות מותנית הזכרתי מושג שנקרא "נוסחת ההסתברות השלמה". בואו נזכיר אותה: אם $latex A$ הוא מאורע כלשהו – במקרה שלנו, "המזכירה הטובה ביותר נבחרה", ואם $latex B_{1},\dots,B_{n}$ היא סדרה של מאורעות זרים שמתארים את מרחב ההסתברות כולו – במקרה שלנו, $latex B_{i}$ הוא המאורע "המזכירה ה-$latex i$ מבין המרואיינות היא הטובה ביותר" – אז מתקיים $latex P\left(A\right)=\sum_{i=1}^{n}P\left(A|B_{i}\right)P\left(B_{i}\right)$, כאשר $latex P\left(A|B_{i}\right)$ מייצג את ההסתברות שהמזכירה הטובה ביותר נבחרה בהינתן שהמזכירה ה-$latex i$ הייתה הטובה ביותר.

בפוסט ההוא אמרתי: "על פניו היא נראית כמו דרך מסובכת יותר לכתוב את $latex P\left(A\right)$, אך כאמור – לעתים קרובות הדרך הנוחה ביותר לחשב את $latex P\left(A\right)$ היא על ידי חלוקה למקרים שמיוצגים על ידי ה-$latex B_{i}$". זו אכן דוגמה קלאסית לכך.

את $latex P\left(B_{i}\right)$ קל לחשב; מה ההסתברות לכך שהמזכירה ה-$latex i$ היא הטובה ביותר? זה קל – מכיוון שהסדר שבו המזכירות נכנסות נבחר באקראי ובהתפלגות אחידה מכל הסדרים האפשריים, כל מקום סביר באותה מידה עבור המזכירה הטובה ביותר, ולכן $latex P\left(B_{i}\right)=\frac{1}{n}$.

ומהו $latex P\left(A|B_{i}\right)$? אם $latex i\le k$ אז $latex P\left(A|B_{i}\right)=0$, על פי החוק שלנו של לדחות אוטומטית את $latex k$ הראשונות (אם הטובה ביותר הייתה בין $latex k$ הראשונות, אין שום סיכוי שנבחר את הטובה ביותר). החלק המעניין הוא כש-$latex i>k$. במקרה זה $latex P\left(A|B_{i}\right)$ הוא ההסתברות שנבחרה המזכירה במקום ה-$latex i$, בהינתן שבמקום ה-$latex i$ אכן נמצאת המזכירה הטובה ביותר. השאלה היא – איך ייתכן שהיא לא תיבחר? זה יקרה רק אם אחת מהמזכירות במקומות $latex k,k+1,\dots,i-1$ הצליחה להידחף איכשהו – כלומר הייתה טובה יותר מכל המזכירות שלפניה.

את הקריטריון המסובך הזה אפשר לנסח בצורה הרבה יותר אלגנטית: מבין $latex i-1$ המזכירות הראשונות, המזכירה הטובה ביותר הייתה בין $latex k$ הראשונות. שכנעו את עצמכם שזה אכן שקול!

את ההסתברות של הקריטריון קל כעת לחשב – למזכירה הטובה ביותר יש $latex i-1$ מקומות אפשריים להיות בהם; כל מקום סביר באותה מידה; ולכן ההסתברות שהיא תהיה באחד מ-$latex k$ המקומות הראשונים היא $latex \frac{k}{i-1}$. לכן $latex P\left(B_{i}\right)=\frac{k}{i-1}$. אם זה התקיים, אז למזכירה במקום ה-$latex i$ לא היו הפרעות והיא נבחרה בודאות (הרי היא הטובה ביותר, ולכן בפרט הייתה טובה מכל המזכירות שלפניה).

נוסחת ההסתברות השלמה כעת נותנת לנו:

$latex P\left(A\right)=\sum_{i=1}^{n}P\left(A|B_{i}\right)P\left(B_{i}\right)=\sum_{i=k+1}^{n}\frac{k}{i-1}\cdot\frac{1}{n}=\frac{k}{n}\sum_{i=k+1}^{n}\frac{1}{i-1}$.

יופי. עכשיו נתקענו. מה עושים עם הסכום $latex \sum_{i=k+1}^{n}\frac{1}{i-1}$ המעצבן? כאן מסתיים החלק היחסית פשוט של הפוסט ואנו עוברים לחלק הטכני, שלטעמי הוא יפה ומעניין לא פחות, אבל אולי לא מיועד לבעלי לב חלש מתמטית.

ראשית, שימו לב לכך שהסכום שלעיל שווה ל-$latex \sum_{i=k}^{n-1}\frac{1}{i}$ בבירור (ביצענו את החלפת המשתנה הפשוטה $latex i\mapsto i+1$). לסכום הזה קשר הדוק לאחד הטורים החשובים במתמטיקה – הטור ההרמוני, $latex \sum_{i=1}^{\infty}\frac{1}{i}$. כפי שכבר הראיתי בעבר בבלוג, הטור הזה מתבדר לאינסוף – ככל שסוכמים בו עוד ועוד איברים, התוצאה גדלה וגדלה באופן בלתי חסום ועוברת כל מספר טבעי בשלב מסויים (אף שיש טענות שהוא דווקא מתכנס ל-137). אבל, הבה ונדבר לרגע על הסכומים החלקיים של הטור, מה שמתקבל אחרי שסוכמים רק את $latex n$ האיברים הראשונים מתוכו, כלומר $latex H_{n}=\sum_{i=1}^{n}\frac{1}{i}$. ל-$latex H_{n}$ קוראים המספר ההרמוני ה-$latex n$-י, ועליו המתמטיקאים יודעים לא מעט. שימו לב ש-$latex \sum_{i=k}^{n-1}\frac{1}{i}=H_{n-1}-H_{k-1}$, ולכן השאלה שאנחנו רוצים לפתור היא בעצם זו: מהו $latex \lim_{n\to\infty}\frac{k}{n}\left(H_{n-1}-H_{k-1}\right)$?

כאן כדאי לשלוף את מה שידוע על המספרים ההרמוניים. למרבה המזל, אנחנו יודעים לקרב אותם מצויין בעזרת פונקציה שאנחנו מכירים היטב – הלוגריתם הטבעי, $latex \ln n$. למעשה, הסדרה ההרמונית $latex H_{n}$ היא מעין אנלוג בדיד של $latex \ln n$; זאת מכיוון ש-$latex H_{n}=\sum_{i=1}^{n}\frac{1}{i}$ ואילו $latex \ln n=\int_{1}^{n}\frac{1}{x}dx$. ניתן להוכיח, ואראה זאת בקרוב, ש-$latex \lim_{n\to\infty}\left(H_{n}-\ln n\right)=\gamma$ כאשר $latex \gamma$ הוא מספר קבוע (קטן למדי, אבל זה לא חשוב לנו) המכונה "קבוע אוילר-מסקרוני" וערכו הוא בערך $latex \gamma=0.5772\dots$. ואני אומר "בערך" כי המספר הזה הוא עדיין תעלומה לא קטנה – עדיין לא ידוע אפילו אם הוא רציונלי או אי רציונלי.

דרך אחרת, אולי קצת יותר נוחה, לתאר את הגבול למעלה היא זו: $latex H_{n}=\ln n+\gamma+o\left(1\right)$. מילולית, זה אומר "המספר ההרמוני ה-$latex n$-י הוא $latex \ln n$ ועוד קבוע אוילר-מסקרוני, ועוד משהו שאני לא יודע איך הוא נראה אבל כש-$latex n$ שואף לאינסוף הוא שואף לאפס" (המשמעות הפורמלית של $latex o\left(1\right)$ היא זו: פונקציה $latex f\left(n\right)$ היא $latex o\left(1\right)$ – או-קטן של $latex 1$ – אם $latex \frac{f\left(n\right)}{n}\to0$).

כעת, מהו $latex H_{n-1}-H_{k-1}$? עם הקירוב שתיארתי זה פשוט:

$latex H_{n-1}-H_{k-1}=\left(\ln\left(n-1\right)+\gamma+o\left(1\right)\right)-\left(\ln\left(k-1\right)+\gamma+o\left(1\right)\right)=\ln\left(\frac{n-1}{k-1}\right)+o\left(1\right)$

המעבר האחרון נובע מזהות סטנדרטית בלוגריתמים: $latex \ln a-\ln b=\ln\left(\frac{a}{b}\right)$ (הרבה מהכוח של לוגריתמים נובע מכך שחיבור וחיסור שלהם מתאימים לכפל וחילוק מספרים).

אני משער שמדגדג לכם בשלב זה להיפטר מהמינוסים המעצבנים שדבוקים ל-$latex n$ ו-$latex k$. ובכן, שימו לב לכך ש-$latex H_{n-1}-H_{n}=\ln\left(\frac{n-1}{n}\right)+o\left(1\right)=\ln\left(1-\frac{1}{n}\right)+o\left(1\right)=o\left(1\right)$, כשהמעבר האחרון נובע מכך ש-$latex \lim_{n\to\infty}\ln\left(1-\frac{1}{n}\right)=\ln\left(1\right)=0$. דרך מסובכת להגיד פורמלית את הרעיון הטריוויאלי ש-$latex H_{n}$ ו-$latex H_{n-1}$ הם אותו הדבר לכל צורך מעשי כאשר $latex n$ שואף לאינסוף, ולכן אפשר להחליף ביניהם. למי שהפורמליות עדיין חשובה לו, הנה הטריק במלואו:

$latex H_{n-1}-H_{k-1}=\left(H_{n-1}-H_{n}+H_{n}\right)-\left(H_{k-1}-H_{k}+H_{k}\right)=H_{n}-H_{k}+o\left(1\right)=\ln\left(\frac{n}{k}\right)+o\left(1\right)$

אם כן, חזרה לעניינו המקורי – צמצמנו את בעיית המזכירה לגבול $latex \lim_{n\to\infty}\frac{k}{n}\ln\left(\frac{n}{k}\right)$. כפי שאפשר לנחש, המפתח לתעלומה הוא היחס $latex \frac{k}{n}$. צריך לזכור ש-$latex k$ אינו קבוע בהכרח, אלא הוא פונקציה כלשהי של $latex n$, ואנחנו רוצים לדעת איזו פונקציה מניבה לנו את הערך המקסימלי – את הסתברות ההצלחה המקסימלית לבחור במזכירה הטובה ביותר. לשם כך, הבה ונסמן $latex x=\frac{k}{n}$, וכעת עלינו לחקור את הפונקציה $latex x\ln\left(\frac{1}{x}\right)=-x\ln x$ עבור הערכים $latex 0<x\le1$. ב"חקירה" אני מתכוון ל"להבין איפה יש לפונקציה מקסימום אם בכלל"

הדרך הסטנדרטית לבצע חקירה שכזו היא באמצעות נגזרות. קל לחשב את הנגזרת של הפונקציה הזו – היא $latex -\ln x-x\cdot\frac{1}{x}=\ln\left(\frac{1}{x}\right)-1$. על כן, הנגזרת מתאפסת כאשר $latex \ln\left(\frac{1}{x}\right)=1$, כלומר $latex \frac{1}{x}=e$, כלומר $latex x=\frac{1}{e}$ – הנה המספר הזה צץ סוף סוף. האם ההתאפסות הזו היא נקודת מינימום או מקסימום של הפונקציה? ובכן, אם תחקרו קצת בעצמכם תגלו שהנגזרת היא פונקציה יורדת, שבהתחלה היא חיובית ואחר כך שלילית. כלומר, הפונקציה המקורית קודם עולה, ואז יורדת – מה שאומר ש-$latex x=\frac{1}{e}$ היא נקודת המקסימום. המסקנה: אם אנחנו רוצים למקסם את הסיכוי שלנו לבחור את המזכירה הטובה ביותר, אנחנו רוצים תמיד לבחור $latex k$ כך ש-$latex \frac{k}{n}=\frac{1}{e}$, כלומר $latex k=\frac{n}{e}$. מכיוון ש-$latex e$ הוא אי רציונלי לעולם לא נוכל לבחור $latex k$ שיקיים את השוויון הזה בדיוק; אבל מכיוון ש-$latex x\ln\left(\frac{1}{x}\right)$ היא פונקציה רציפה, ככל שנבחר $latex k$ שקרוב יותר ל-$latex \frac{n}{e}$ נקבל סיכוי הצלחה גבוה יותר.

זה סוף בעיית המזכירה, אבל נשאר לנו להבין איך מוכיחים את ההערכה על גודל המספרים ההרמוניים, $latex H_{n}=\ln n+\gamma+o\left(1\right)$. לשם כך נכניס לתמונה מושג חדש – פונקצית הזטא של רימן. עבור $latex s>1$ ממשי, פונקצית הזטא של רימן מוגדרת כ-$latex \zeta\left(s\right)=\sum_{n=1}^{\infty}\frac{1}{n^{s}}$ (תיארתי בפירוט רב יותר את הפונקציה והקשר שלה להשערת רימן בעבר). למשל, $latex \zeta\left(2\right)=\sum_{n=1}^{\infty}\frac{1}{n^{2}}=\frac{\pi^{2}}{6}$ (איך מוכיחים את השוויון הזה? גם את זה הראיתי בעבר). בנוסף, נכליל את המספרים ההרמוניים באופן טבעי כדי שיתארו את העניין הזה: $latex H_{n}^{\left(s\right)}=\sum_{i=1}^{n}\frac{1}{i^{s}}$.

לב ההוכחה הוא נעוץ בהיכרות הטובה שלנו עם $latex \ln n$. אנחנו יודעים לתאר את $latex \ln n$ כטור אינסופי: הנוסחה המפורסמת ביותר (שאותה לא אוכיח כאן, יש גבול…) היא $latex \ln\left(\frac{1}{1-x}\right)=\sum_{n=1}^{\infty}\frac{x^{n}}{n}$ שתקפה כאשר $latex -1\le x<1$. ניקח $latex k>1$ טבעי כלשהו וננסה להשתמש בנוסחה כדי לתאר כטור את $latex \ln\left(\frac{k}{k-1}\right)$: מכיוון ש-$latex \frac{k}{k-1}=\frac{1}{1-1/k}$, נקבל ש-$latex \ln\left(\frac{k}{k-1}\right)=\sum_{n=1}^{\infty}\frac{1}{nk^{n}}$. הטור הזה נראה קצת יותר נחמד כשכותבים אותו במפורש: $latex \ln\left(\frac{k}{k-1}\right)=\frac{1}{k}+\frac{1}{2k^{2}}+\frac{1}{3k^{3}}+\dots$.

כעת הבה ונקבע $latex n$ כלשהו, ונסכום את $latex \ln\left(\frac{k}{k-1}\right)$ לכל $latex 1<k\le n$. בזכות התכונה של הפיכת-חיבור-לכפל של לוגריתמים, התוצאה תהיה שרשרת יפה של ביטולים:

$latex \ln\left(\frac{n}{n-1}\right)+\ln\left(\frac{n-1}{n-2}\right)+\dots+\ln\left(\frac{3}{2}\right)+\ln\left(\frac{2}{1}\right)=\ln\left(\frac{n}{n-1}\cdot\frac{n-1}{n-2}\cdots\frac{3}{2}\cdot\frac{2}{1}\right)=\ln n$

מה זה עזר לנו? שכעת אפשר לכתוב את $latex \ln n$ כסכום של טורים:

$latex \ln n=\sum_{k=2}^{n}\left(\frac{1}{k}+\frac{1}{2k^{2}}+\frac{1}{3k^{3}}+\dots\right)$

כל טור שכזה מתכנס, והוא חיובי, ולכן ניתן לשנות את סדר האיברים בסכימה בלי חשש מעיוותים כמו זה של משפט רימן. אם כן, מה קיבלנו? ש-$latex \ln n=\sum_{k=2}^{n}\frac{1}{k}+\frac{1}{2}\sum_{k=2}^{n}\frac{1}{k^{2}}+\frac{1}{3}\sum_{k=2}^{n}\frac{1}{k^{3}}+\dots$

כעת שימו לב ש-$latex \sum_{k=2}^{n}\frac{1}{k}=H_{n}-1$ (כי האיבר הראשון בטור, עבור $latex k=1$, חסר). בדומה, $latex \sum_{k=2}^{n}\frac{1}{k^{s}}=H_{n}^{\left(s\right)}-1$. לכן קיבלנו:

$latex \ln n=\left(H_{n}-1\right)+\frac{1}{2}\left(H_{n}^{\left(2\right)}-1\right)+\frac{1}{3}\left(H_{n}^{\left(3\right)}-1\right)+\dots$

ולכן העברת אגפים זריזה נותנת לנו ש:

$latex H_{n}-\ln n=1-\frac{1}{2}\left(H_{n}^{\left(2\right)}-1\right)-\frac{1}{3}\left(H_{n}^{\left(3\right)}-1\right)+\dots$

עד כאן זוהי תוצאה מדוייקת לחלוטין. הבעיה היא שבאגף ימין יש לנו יצור מסובך ומפחיד למדי שתלוי ב-$latex n$ ואין לנו מושג איך לחשב אותו במדוייק. מה שכן אפשר לעשות הוא להסתכל על הגבול של כל זה כאשר משאיפים את $latex n$ לאינסוף – כאן משתמשים בכך שכל אחד מסדרות המספרים ההרמוניים ה"מוכללים" כן מתכנסת:

$latex \lim_{n\to\infty}\left(H_{n}-\ln n\right)=1-\frac{1}{2}\left(\zeta\left(2\right)-1\right)-\frac{1}{3}\left(\zeta\left(3\right)-1\right)-\dots$

והנה קיבלנו ייצוג נאה של $latex \gamma$: $latex \gamma=1-\frac{1}{2}\left(\zeta\left(2\right)-1\right)-\frac{1}{3}\left(\zeta\left(3\right)-1\right)-\dots$. הספקנים שבכם אולי יתהו למה הטור הזה מתכנס בכלל; לשם כך מספיק להראות שהטור החיובי $latex \sum_{k=2}^{\infty}\left(\zeta\left(k\right)-1\right)$ מתכנס, ואותו אפשר לכתוב כ-$latex \sum_{k=2}^{\infty}\sum_{n=2}^{\infty}\frac{1}{n^{k}}$, להחליף את סדר הסכימה כדי לקבל סכום של טורים גאומטריים $latex \sum_{n=2}^{\infty}\left(\sum_{k=2}^{\infty}\frac{1}{n^{k}}\right)=\sum_{n=2}^{\infty}\frac{1}{n\left(n-1\right)}$ והטור הזה כבר בבירור מתכנס על ידי מבחן השוואה סטנדרטי (המעבר האחרון הוא פשוט שימוש מהיר בנוסחה לטורים גאומטריים אינסופיים).

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

33 תגובות על הפוסט “בעיית המזכירה, ואיך זה קשור למספרים הרמוניים

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

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

    אבל שאלה קצת יותר מהותית לי אליך. מדוע עברת מיד לגבול N שואף לאינסוף אחרי שיסחת את פונקציית המטרה שלך? כלומר, כמתמטיקאי, אני מבין שלהתנהגות אסימפטוטית של פונקציות יש ערך רב, אבל על פניו, בהינתן N יש לנו בעיית אופטימיזציה פשוטה יחסית. אני מבין מדוע הופכים את K לרציף (אז אפשר לגזור לפי K וכו'). האם הפתרון n/e נכון לכל n, או שזהו קירוב שנכון רק עבור ערכים n גדולים מספיק?

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

  4. בעיה חביבה וגם אהבתי את הוכחת ההתכנסות של טור ההפרשים.

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

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

  6. יפה מאוד. פוסט משובח.

    תיקון טעות קטנה: בפיסקה המתחילה במילים "את ההסתברות של הקריטריון קל כעת לחשב", צריך להיות (P(A|Bi ולא (P(Bi.

  7. יש דרך יותר פשוטה להוכיח שהסדרה של גאמא מתכנסת

    אפשר לרשום את הסדרה בתור הטור
    zzz 1/n – ln(1 + 1/n) zzz

    שחיובי מאי השווין

    ln(1 + x) = x – x^2/2

    כלומר

    zzz 1/n – ln(1 + 1/n) <= 1/n – 1/n + 1/(2n^2) = 1/2n^2

  8. יש דרך יותר פשוטה להוכיח שהסדרה של גאמא מתכנסת

    אפשר לרשום את הסדרה בתור הטור
    zzz 1/n – ln(1 + 1/n) zzz

    שחיובי מאי השווין

    ln(1 + x) <= x

    ומתכנסת מאי השוויון

    ln(1 + x) >= x – x^2/2

    כלומר

    zzz 1/n – ln(1 + 1/n) <= 1/n – 1/n + 1/(2n^2) = 1/2n^2

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

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

  11. זה לא נכון. אני אמנם דוחה את כל הקודמות, אבל זה לא אומר שאני לא זוכר את הכישורים שלהן; כשבאה ה-11 אני משווה את הכישורים שלה לאלו של ה-10 הקודמות. ה"בלי לחשוב בכלל" פירושו "בלי לחשוב בכלל אם לקבל או לדחות אותה" – כלומר, אין לי כאן בחירה ואני תמיד דוחה.

  12. בכל מקום שכתבת o(n) צריך להיות o(1).
    o(1) פירושו שואף ל-0.
    o(n) פירושו קטן מגורם לינארי, שזה הרבה מאד כשהגורם המוביל הוא לוגריתמי.

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

  14. באמת פוסט יפה מאד.
    אגב e/1 , הוא מופיע גם בבעיית "המזכירה המבולבלת" (מזכירה שצריכה לסדר n מעטפות בn תיבות, מה הסיכוי שאף מעטפה לא תגיע לתעודתה), ובכלל, כשn גדול n/e הם מספר הפרמוטציות ללא נקודת שבת בקבוצה מגודל n.

  15. בתקופתי קראו לבעיה "בעיית הטרמפיסטית" (אתם מוזמנים לחשוב על התסריט ועל הרכב). ואא"ט הפתרון מופיע ב-Feller.

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

  17. בעיה פשוטה ועקרונית – אתה מניח שk לינארי בn, לכן x (שהגדרת כ k/n) הוא מספר – אבל יכול להיות, למשל, שk=1/n(באופן משונה למדי) ואז אתה כבר נכנס למה שלדעתי קרוי חשבון ווריאציות

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

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

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

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

  22. נ.ב.
    נניח שהיית מתכנת סימולצית מחשב קטנה שתדגים שאכן ב 37% מהפעמים נבחרת המזכירה הטובה ביותר (נניח מתוך 1000 מזכירות). מתוך איזו התפלגות היית בוחר את המזכירות לסימולציה?

  23. התפלגות אחידה על קבוצת הפרמוטציות של מספרים מ-1 עד n.

    כמו כן, למה "נניח"? הנה סימולציה שעובדת ואכן מדגימה את ה-37%:

    from math import *
    from random import *
    def choose_sec(sec_list):
    n = len(sec_list)
    place_to_start = int(n / e)
    for k in range(place_to_start, n):
    if max(sec_list[:(k+1)]) == sec_list[k]:
    return sec_list[k]
    return sec_list[n-1]

    def experiment(n, k):
    sec_list = range(1,n+1)
    success = 0
    for t in range(k):
    shuffle(sec_list)
    if choose_sec(sec_list) == n:
    success = success + 1
    print("Success rate: {}/{} = {}%".format(success, k, 100.0*success / k))

    experiment(30,100000)

  24. ראשית תודה על ההשקעה!
    אם כי לדעתי יש כאן שתי בעיות. אחת פשוטה ואחת מסובכת.
    הפשוטה: אסור שיהיו מזכירות עם אותו הדרוג. כי אחרת יכול להיווצר מצב בו כולן בעלות אותו ציון פרט לאחת עם ציון גבוה יותר. אז כמובן ההסתברות לבחירתה היא כ 63% (היא לא בין הנדחות אוטומתית).
    הבעיה השניה (בצורה אינטואיטיבית):
    למעשה התוצאה שהדגמת היא על התפלגות אחידה של ציוני המזכירות (מקווה שלא צריך להסביר). אבל אם ידוע מראש שהפילוג אחיד, כנראה אפשר היה לבחור את המזכירה הטובה ביותר בהסתברות יותר גבוהה מ 37%.
    לדעתי הטיעון הזה נכון לכל פילוג שתבחר ומספר מספיק גדול של מזכירות.

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

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

  26. היי,
    אם ידוע מראש שהפילוג של הציונים אחיד בין 0 ל 1. אז (אם לא טעיתי) הקריטריון הוא:
    לעצור ברגע שציון המזכירה גדול מ (מספר המזכירות פחות 2) חלקי מס' המזכירות.
    ההסתברות לבחור במזכירה הטובה ביותר הוא 50%.
    למשל אם יש 100 מזכירות לעצור בזאת שציונה מעל 0.98.

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

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

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

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

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

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

כתיבת תגובה

האימייל לא יוצג באתר.