ההסתברות לרנדומליות

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

for (int i = 0; i < cards.Length; i++)
{
    int n = rand.Next(cards.Length);
    Swap(ref cards[i], ref cards[n]);
}

ג’ף אטווד קורא למתודה הזו “מתודה נאיבית”, ובהמשך הפוסט שלו הוא מראה שיש בה כשל הסתברותי. יש פרמוטציות (שינויים) מסויימות שההסתברות אליהם גבוהה יותר, ולכן השינוי הרנדומלי לא מחולק באופן שווה מבחינה הסתברותית.
מדוע מיצ’ל מספר לנו את זה? מפני שלפני כמה שנים הוא כתב מאמר ב-4GuysFromRolla בדיוק על זה – איך לשנות את סדר האברים במערך באופן רנדומלי – ונתן את המתודה הזו כדוגמה מוצלחת לסידור רנדומלי של אברים במערך (randomizing) מערכים…
אז מה עושים? מיצ’ל אץ-רץ למאמר הישן, וכתב שם אזהרה לגבי המתודה, עם קישור למאמר חדש שכתב , ובמאמר החדש הוא מסביר את הכשל ההסתברותי של האלגוריתם הנאיבי, ונותן פתרון רנדומלי באמת.
אפשר לבחור לקרוא את המאמר החדש של מיצ’ל, או את הפוסט הנוכחי של מיצ’ל, או את המאמר המקורי של אטווד , בכולם מוסבר בפירוט מדוע המתודה הזו אינה מוצלחת מבחינה הסתברותית. אני אחסוך את התיאורים הפילוספיים והגרפיים ואכתוב במילים בלבד, תוך מתן דוגמה על מערך בן 3 אברים (דוגמה הניתנת בכל המאמרים הנ”ל). בסוף הפוסט אכתוב מה הייחוד של כל אחד מ-3 המאמרים הנ”ל, וגם מה מעניין במאמר המקורי של מיצ’ל:
אם רוצים לשנות מיקומים של איברים במערך בן n איברים, יש nⁿ אפשרויות של מיקומים בסה”כ (כי לכל איבר יש n מקומות שבהם הוא יכול להיות ממוקם; ישנם n איברים, אז בסה”כ מספר האפשרויות הכולל למיקומים חדשים הוא nⁿ). אבל למערך בן n איברים יש רק !n) n עצרת) פרמוטציות אפשריות.
[פרמוטציות הן סידורים שונים. למשל: הסדר הראשוני של איברים במערך בן 3 אברים הוא [0,1,2] . זוהי פרמוטציה אחת. אם נחליף את שני האיברים הראשונים זה בזה, הסדר החדש יהיה [1,0,2]. זוהי פרמוטציה נוספת. פרמוטציות אפשריות נוספות הן [2,1,0]; [0,2,1]; [1,2,0]; [2,0,1]. זהו. בסה”כ מצאנו 6 (3 עצרת) פרמוטציות אפשריות למערך בן 3 איברים].
אבל, אם nⁿ אינו מתחלק ב-!n, אזי בהכרח חלק מהפרמוטציות תחזורנה על עצמן יותר מאחרות, ולכן הרנדומליות היא מוטה מבחינה סטטיסטית. בשני המאמרים ישנם תיאורים גרפיים של הפרמוטציות השונות ואיך להגיע אליהן, וגם גרף המראה את החלוקה הלא-שווה של ההסתברות לפרמוטציות (יוצא שהפרמוטציות [0,2,1];[1,0,2]; ו-[1,2,0]; הן סבירות יותר מה-3 האחרות).
מיצ’ל גם מייחד חלק בפוסט שלו לשאלה עד כמה ההסתברות המוטה הזו היא באמת בעייתית. המסקנה היא שצריך לדו כל מקרה לגופו, ולראות אם באמת נזקקים בו לרנדומליות טהורה. למשל: אם יש לנו אתר שהוא חנות אלקטרונית, המראה ב”חלון הראווה” שלה פריטים רנדומליים המלאי, אזי כדאי שהרנדומליות תהיה טהורה, מפני שאחרת חלק מהמוצרים יוצגו יותר פעמים ממוצרים אחרים. אבל אם למשל יש לנו אלגוריתם רנדומלי לבחירת הציטטה היומית – לא נורא אם חלק מהציטטות תופענה יותר מאחרות.
הפתרון שאטווד – ובעקבותיו גם מיצ’ל – מציע במקום האלגוריתם הנאיבי, נקרא אלגוריתם הערבוב של ייטס ופישר, והוא כרוך בתיקון קל בקוד שכתבנו למעלה:

for (int i = cards.Length - 1; i > 0; i--)
{
    int n = rand.Next(i + 1);
    Swap(ref cards[i], ref cards[n]);
}

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

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