15אלגוריתמים אקראיים: מבוא, בעיית המזכיר ואלגוריתם Freivalds

בקצרה

• אלגוריתם אקראי הוא אלגוריתם שרשאי, בנוסף לקלט, להטיל מטבעות הוגנים ובלתי תלויים ולהשתמש בתוצאתם. כל טענה הסתברותית בשיעור הזה נלקחת אך ורק על המטבעות של האלגוריתם — הקלט נשאר שרירותי, נבחר על ידי "אויב אכזר" שמכיר את קוד האלגוריתם אך לא את תוצאות ההטלות, והערובה נדרשת לכל קלט, לא לקלט אקראי. זו הנקודה שהכי קל להתבלבל בה, וזה הדבר היחיד שחייבים לקחת מהשיעור אם לוקחים ממנו דבר אחד.
• בעיית המזכיר מדגימה מדוע אקראיות עוזרת בכלל: לכל אלגוריתם דטרמיניסטי קיים קלט שעליו הוא נכשל באופן קטסטרופלי, בעוד אלגוריתם אקראי פשוט מוצא את המועמד הטוב ביותר בהסתברות $\ge \tfrac14$ על כל קלט.
• אלגוריתם Freivalds לווידוא $A\cdot B = C$ רץ בזמן $O(n^2)$ במקום $O(n^3)$ ומחזיר תשובה נכונה בהסתברות $\ge \tfrac12$; הטעות שלו היא חד-צדדית — הוא לעולם לא דוחה קלט נכון.
• הגברה (amplification): $t$ הרצות בלתי תלויות עם קבלה רק אם כל ההרצות קיבלו מורידות את הסתברות הטעות ל-$\le 2^{-t}$ במחיר זמן ריצה $O(t\cdot n^2)$. גורם ליניארי בזמן קונה ירידה אקספוננציאלית בשגיאה. עם $t=\log n$ מקבלים זמן $O(n^2\log n)$ ושגיאה $\le 1/n$.
• כל ההסתברויות בשיעור מוכחות בספירה קומבינטורית מפורשת על מרחב המדגם, ולא נטענות. מרחב המדגם הוא אוסף תוצאות הניסוי האקראי (כל התמורות; כל הווקטורים ב-$\{0,1\}^n$) — לא אוסף הפלטים האפשריים של האלגוריתם.
• השיעור אינו מגדיר את המודל הפורמלי ואינו מגדיר מחלקות סיבוכיות אקראיות. מכונת טיורינג אקראית והמחלקות $\mathrm{RP}$, $\mathrm{coRP}$ ו-$\mathrm{BPP}$ מוגדרות בשיעור הבא; שם גם ייאמר שבעיית וידוא כפל המטריצות שייכת ל-$\mathrm{coRP}$.
• הערה על היקף: המרצה אמר במפורש ([00:00:00]) שבעיית המזכיר אינה חלק מחומר המבחן והיא מוצגת בשביל העקרונות; אלגוריתם Freivalds וההגברה כן חלק מהחומר ([00:29:45]).

רקע ותלויות

מהיכן הגענו לכאן. שיעורים 12–14 עסקו בהתמודדות עם קושי חישובי דרך אלגוריתמי קירוב: כאשר בעיה היא NP-hard, במקום לוותר על יעילות מוותרים על אופטימליות ומסתפקים בערובה על יחס הקירוב. השיעור הזה פותח כלי שני מאותה משפחה — ויתור על ודאות במקום ויתור על איכות. המרצה הדגיש ([00:00:00], [00:34:34]) ששני האלגוריתמים שיוצגו כאן אינם קשורים כלל לבעיות NP-קשות; שילוב האקראיות עם אלגוריתמי קירוב יגיע בהמשך.

הסתברות בדידה — כל מה שנשתמש בו. אלה הכלים היחידים הנדרשים, וכולם מהקורס המקדים:

• מרחב מדגם $\Omega$ הוא אוסף התוצאות האפשריות של ניסוי אקראי. מאורע הוא תת-קבוצה $E \subseteq \Omega$.
• אם הדגימה אחידה מ-$\Omega$ סופי, אז $\Pr[E]=\dfrac{|E|}{|\Omega|}$. כלומר חישוב הסתברות מתחת להתפלגות אחידה הוא בדיוק תרגיל בקומבינטוריקה ([00:27:02]).
• מונוטוניות: אם $E \subseteq F$ אז $\Pr[E] \le \Pr[F]$. זהו הכלי שבו נחסום הסתברויות משני הכיוונים: פעם אחת כדי לחסום מלמטה הסתברות הצלחה (משפט 2), ופעם אחת כדי לחסום מלמעלה הסתברות כישלון (משפט 3).
• אי-תלות: מאורעות $E_1,\dots,E_t$ בלתי תלויים אם $\Pr\left[\bigcap_i E_i\right]=\prod_i \Pr[E_i]$. אצלנו אי-התלות לעולם אינה מונחת — היא נבנית בכך שכל הרצה משתמשת בהטלות מטבע טריות.
• ספירה: מספר התמורות של $[n]$ הוא $n!$; מספר הווקטורים ב-$\{0,1\}^n$ הוא $2^n$.

המרצה ביקש במפורש ([00:31:20], [01:21:06]) לחזור לקראת השיעור הבא על תוחלת, ליניאריות התוחלת ופירוק לאינדיקטורים. בשיעור הזה תוחלת מופיעה רק בהערה אחת קצרה (מסקנה 2.1).

אלגברה ליניארית. לכל מטריצות $A,B$ מסדר $n\times n$ ולכל וקטור $r\in\mathbb{R}^n$:

$(A\cdot B)\cdot r = A\cdot(B\cdot r), \qquad (A-C)\cdot r = A\cdot r - C\cdot r .$

הזהות הראשונה (אסוציאטיביות) היא לב האלגוריתם של Freivalds; השנייה (דיסטריביוטיביות) היא לב הניתוח. כמו כן, הקואורדינטה ה-$i$ של $D\cdot r$ היא

$(D\cdot r)_i=\sum_{j=1}^{n} D_{ij}\, r_j .$

חישוב מכפלת מטריצה בווקטור עולה $\Theta(n^2)$ פעולות אריתמטיות; חישוב מכפלת מטריצה במטריצה בשיטה הנאיבית עולה $\Theta(n^3)$. בהקלטה [00:35:46] עלה שקיימים אלגוריתמים מהירים יותר לכפל מטריצות (מעריך כ-$n^{2.37}$), אך הקורס לא נכנס לזה ומשווה מול $n^3$.

המקרה הגרוע ביותר והאויב האכזר. מקורס האלגוריתמים: ניתוח במקרה הגרוע ביותר שקול לחשוב על יריב שמכיר את האלגוריתם ובוחר עבורו את הקלט המזיק ביותר ([00:07:06]). ההבדל המרכזי שנוסף כאן: היריב מכיר את הקוד, אך לא את תוצאות ההטלות, שנבחרות אחרי שהקלט כבר נקבע ([00:08:08]). זהו כל ההסבר לשאלה "למה אקראיות עוזרת".

הגדרות

הגדרה 1: אלגוריתם אקראי

ניסוח. אלגוריתם אקראי $\mathcal{A}$ מקבל שני קלטים: את הקלט "האמיתי" $x$, ומחרוזת ביטים $r$ שכל ביט בה נדגם באופן אחיד ובלתי תלוי מ-$\{0,1\}$. בהינתן $x$ ו-$r$, הריצה של $\mathcal{A}$ דטרמיניסטית לחלוטין, והפלט הוא פונקציה $\mathcal{A}(x,r)$. כל אמירה הסתברותית על $\mathcal{A}$ היא אמירה על

$\Pr_{r}\big[\,\mathcal{A}(x,r)\ \text{has some property}\,\big] \quad \text{for a \textbf{fixed}, arbitrary } x .$

אינטואיציה. תחשבו על $x$ כעל דבר שנתון לנו מבחוץ, ועל $r$ כעל הדבר היחיד שאנחנו מגרילים. המרצה ניסח זאת פעמיים ([00:11:18], [00:16:35]): "האקראיות לא תגיע לי מהקלט. הקלט הוא שרירותי, אני חושב על הקלט הגרוע ביותר, האלגוריתם הוא זה שאקראי". הניסוח האינטואיטיבי שהמרצה נתן בפתיחה ([00:00:34]) הוא: אלגוריתם אקראי הוא אלגוריתם שיכול, בכל רגע ובכמה פעמים שירצה, "לדגום באקראי ביט $0/1$", בלתי תלוי בקודמים.

מופע. האלגוריתם של Freivalds (הגדרה 5 להלן) דוגם וקטור $r\in\{0,1\}^n$; זהו בדיוק $n$ ביטים אקראיים.

אי-מופע (חשוב). משפט מהצורה "$v_1$ הוא המועמד הטוב ביותר" אינו מאורע אקראי בהקשר הזה, כי הוא תלוי רק בקלט ולא ב-$r$. המרצה עצר על כך במפורש ([00:20:16]): "לא לדבר על הסתברות של משהו שהוא לא אקראי — זה חסר משמעות". לעומת זאת "$\sigma(1)$ הוא המועמד הטוב ביותר" כן מאורע אקראי, כי $\sigma$ הוא האובייקט שהוגרל.

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

הגדרה 2: מרחב המדגם של ריצה אקראית

ניסוח. מרחב המדגם $\Omega$ של אלגוריתם אקראי הוא אוסף תוצאות הניסוי האקראי שהאלגוריתם מבצע — לא אוסף הפלטים האפשריים שלו.

אינטואיציה ומדוע זה קריטי. זו הייתה שאלת סטודנטית שהמרצה ציין כשאלה מצוינת ([00:23:52]), כי כאן נופלים הכי הרבה. באלגוריתם המזכיר הניסוי הוא "הגרלת תמורה", ולכן $\Omega=S_n$, קבוצת כל התמורות $\sigma:[n]\to[n]$, ו-$|\Omega|=n!$. לא $\{1,\dots,n\}$, שהיא קבוצת הפלטים. באלגוריתם Freivalds הניסוי הוא "הגרלת וקטור", ולכן $\Omega=\{0,1\}^n$ ו-$|\Omega|=2^n$.

מופע ואי-מופע (הדוגמה שהמרצה נתן, [00:24:55]). מטילים שתי קוביות הוגנות ושואלים מה ההסתברות שהסכום הוא $5$. מרחב המדגם הוא

$\Omega=\{(x,y): x,y\in\{1,\dots,6\}\},\qquad |\Omega|=36,$

כלומר זוגות סדורים. תשובה שגויה נפוצה היא ש-$\Omega$ הוא קבוצת הסכומים האפשריים $\{2,\dots,12\}$ — אבל הסכום הוא מאורע, לא תוצאה של הניסוי. הפתרון המלא מופיע בסעיף הדוגמאות.

הגדרה 3: טעות חד-צדדית, ומטריצת הבלבול

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

זוהי מטריצת הבלבול (confusion matrix) של האלגוריתם ([01:02:43]). לאלגוריתם יש טעות חד-צדדית אם אחת משתי משבצות הטעות ריקה — כלומר הוא יכול לטעות רק לכיוון אחד. אם שתיהן אפשריות, הטעות דו-צדדית.

אינטואיציה. אין תשובה כללית לשאלה איזו טעות גרועה יותר — זה תלוי ביישום ([01:03:14]): בבדיקה אפידמיולוגית עדיף false positive (מישהו יישאר בבית לחינם) על false negative; לפני ניתוח מוח לא רוצים אף אחד מהם.

מופע. אלגוריתם Freivalds: כאשר $AB=C$ הוא תמיד מקבל, ולכן אין לו false negative כלל — טעות חד-צדדית מסוג false positive בלבד ([01:03:46]). זו בדיוק התכונה שתאפשר את ההגברה הפשוטה במשפט 4.

אי-מופע. אלגוריתם שמכריע לפי הצבעת רוב על הרצות שכל אחת מהן טועה בהסתברות $\le 1/3$ בשני הכיוונים הוא בעל טעות דו-צדדית. גם אותו אפשר להגביר, אך לא בכלל "קבל רק אם כולם קיבלו" אלא בהצבעת רוב; המרצה ציין זאת ([01:04:52]) והשאיר לשיעור הבא.

הגדרה 4: בעיית המזכיר (Secretary Problem)

ניסוח (המודל). נתונים $n$ מועמדים, $[n]=\{1,\dots,n\}$, שלמועמד $i$ ערך ממשי $v_i \ge 0$. הערכים שונים זה מזה ו-$n$ זוגי (ראו פערים). המועמדים מרואיינים אחד-אחד, בסדר שהאלגוריתם קובע. הכללים:

1. הערך $v_i$ מתגלה רק בזמן הראיון של מועמד $i$, ולא לפניו.
2. מיד בתום הראיון יש להחליט: לקבל או לדחות.
3. אם קיבלנו — התהליך נעצר, שאר המועמדים הולכים הביתה.
4. אם דחינו — המועמד הולך הביתה ולא ניתן לחזור אליו.

המטרה: לבחור את המועמד בעל הערך המקסימלי.

אינטואיציה. בלי כללים 1–4 זו בעיית "מציאת מקסימום במערך", והאלגוריתם המוכר (שמור את המקסימום עד כה, החלף אם ראית גדול יותר) פותר אותה בוודאות ([00:04:56]). הכללים הופכים את הקלט ממערך לרשימה מקושרת חד-כיוונית שאי אפשר לחזור בה אחורה ([00:14:29]) — מה שנקרא היום בעיה online. כל הקושי נובע מכך שההחלטה חייבת להתקבל לפני שנראתה יתרת הקלט.

מופע. $n=4$ עם ערכים $v=(10,40,20,30)$: המועמד הטוב ביותר הוא $2$ (ערך $40$), השני הכי טוב הוא $4$ (ערך $30$).

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

הגדרה 5: וידוא כפל מטריצות ואלגוריתם Freivalds

ניסוח הבעיה. הקלט הוא שלוש מטריצות $A,B,C$ מסדר $n\times n$, והשאלה היא האם $A\cdot B=C$. זו בעיית הכרעה ("בעיית אחר?" — כן/לא), והיא אינה NP-קשה: אפשר לפתור אותה דטרמיניסטית בזמן $O(n^3)$ פשוט על ידי חישוב $A\cdot B$ והשוואה ל-$C$. נסמן את השפה ב-$\mathrm{MATMUL}$ (סימון שלנו; בסיכום הבעיה אינה מקבלת שם).

המטרה אינה להוציא את הבעיה מ-$\mathrm{P}$ — היא כבר שם — אלא להוריד את המעריך ([00:36:51]).

האלגוריתם (Freivalds). על קלט $A,B,C$:

1. בחר באקראי, באופן אחיד, וקטור $r\in\{0,1\}^n$.
2. חשב $A\cdot(B\cdot r)$ ו-$C\cdot r$.
3. אם $A\cdot(B\cdot r)=C\cdot r$ — קבל; אחרת — דחה.

אינטואיציה. במקום להשוות שתי מטריצות (יקר), משווים את פעולתן על וקטור אקראי אחד (זול). ההצדקה לזמן הריצה היא האסוציאטיביות $(A\cdot B)\cdot r=A\cdot(B\cdot r)$: אף פעם לא כופלים מטריצה במטריצה, רק מטריצה בווקטור ([00:38:59]).

מופע ואי-מופע. אם $AB=C$ אז לכל $r$ ההשוואה מצליחה. אם $AB\ne C$ עדיין ייתכנו וקטורים $r$ ספציפיים שעבורם $ABr=Cr$ — מהאלגברה הליניארית ידוע ששתי מטריצות שונות יכולות להסכים על וקטור מסוים ([00:43:20]). כל מה שצריך להוכיח הוא שאין יותר מדי כאלה.

משפטים והוכחות

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

ניסוח. לכל אלגוריתם דטרמיניסטי $\mathcal{D}$ לבעיית המזכיר קיים קלט (סדרת ערכים) שעליו $\mathcal{D}$ מחזיר את המועמד בעל הערך הנמוך ביותר. בפרט, לכל $\alpha>0$ קיים קלט שעליו הערך שנבחר קטן מ-$\alpha$ כפול המקסימום.

הוכחה. נבנה יריב שמייצר את הערכים תוך כדי ריצה. הנקודה המרכזית: מאחר ש-$\mathcal{D}$ דטרמיניסטי, ההחלטה שלו בשלב $j$ היא פונקציה של הרישא $v_1,\dots,v_j$ בלבד. לכן אם היריב שינה רק ערכים שטרם נחשפו, התנהגות $\mathcal{D}$ על הרישא אינה משתנה.

היריב מזין ערכים עולים: $v_1=1,\ v_2=2,\ v_3=3,\dots$. נבחין בשני מקרים.

מקרה א': $\mathcal{D}$ מקבל בשלב כלשהו $j\le n-1$. בזמן הזה הוא ראה רק את $v_1,\dots,v_j$. עכשיו היריב "משנה את דעתו" לגבי ההמשך וקובע $v_{j+1}=\dots=v_n=M$ עבור $M$ גדול כרצוננו. הרישא לא השתנתה, ולכן $\mathcal{D}$ עדיין מקבל בשלב $j$ ומחזיר ערך $j$, בעוד המקסימום הוא $M$. היחס $j/M$ קטן מכל $\alpha>0$ עבור $M$ גדול מספיק. אם בפרט $j=1$, המועמד שנבחר הוא גם בעל הערך הנמוך ביותר.

מקרה ב': $\mathcal{D}$ דוחה את כל $n-1$ הראשונים. אז הוא חייב לקחת את המועמד האחרון (או להחזיר כלום, מה שגרוע אף יותר). היריב קובע כעת $v_n=0$, כלומר הנמוך מכולם. שוב הרישא $v_1,\dots,v_{n-1}$ לא השתנתה, ולכן ההתנהגות זהה, ו-$\mathcal{D}$ מחזיר את הגרוע ביותר. $\blacksquare$

הערה: בהרצה זה נאמר בקיצור — "לכל אלגוריתם דטרמיניסטי אני יכול לייצר קלט שבו הוא יבחר לא נכון... יותר מזה, אני יכול לדאוג שהוא ימצא מועמד ממש גרוע" ([00:05:28]–[00:06:33]) — בלי לפרט את שני המקרים. הפירוט כאן.

מדוע הניסיון הנאיבי לאקראיות אינו עוזר. סטודנט הציע ([00:07:06]) להגריל את הסף: לצפות במספר אקראי של מועמדים ואז לקחת את הראשון שעובר את המקסימום שנצפה. המרצה הראה מיד שזה נכשל: היריב פשוט ישים את המועמד הטוב ביותר במקום הראשון. אז לא משנה מה הסף שהוגרל (כל עוד הוא לפחות $1$), המועמד הטוב ביותר נמצא בשלב התצפית ונדחה בוודאות, ולכן קיים קלט שעליו האלגוריתם טועה בהסתברות $1$. המסקנה, שהיא הלקח האמיתי של המשפט: לא מספיק "להוסיף אקראיות" — צריך להוסיף אותה במקום הנכון, כלומר לטשטש בדיוק את הדבר שהיריב שולט בו. היריב שולט בסדר, ולכן את הסדר צריך להגריל ([00:09:42]).

משפט 2: האלגוריתם האקראי לבעיית המזכיר

האלגוריתם. על קלט של $n$ מועמדים ($n$ זוגי, ערכים שונים):

1. הגרל תמורה $\sigma:[n]\to[n]$ באופן אחיד מתוך כל $n!$ התמורות.
2. לכל $1\le j\le \tfrac{n}{2}$: ראיין את המועמד $\sigma(j)$ ודחה אותו.
3. סמן ב-$V$ את הערך המקסימלי שנצפה עד כה, כלומר $V=\max_{1\le j\le n/2} v_{\sigma(j)}$.
4. לכל $\tfrac{n}{2}+1\le j\le n-1$: אם $v_{\sigma(j)}>V$ אז קבל את $\sigma(j)$ ועצור.
5. אם הגעת לכאן — קבל את $\sigma(n)$.

ניסוח המשפט. לכל קלט (כלומר לכל וקטור ערכים שונים $v_1,\dots,v_n$), אם $A$ הוא המאורע "האלגוריתם מחזיר את המועמד בעל הערך המקסימלי", אז

$\Pr_{\sigma}[A] \;\ge\; \frac{n}{4(n-1)} \;>\; \frac14 .$

ההסתברות נלקחת רק על התמורה $\sigma$, והחסם תקף לכל קלט.

למה שלב 5 קיים. שאלת סטודנט ([00:17:06]): מדוע הלולאה בשלב 4 נעצרת ב-$n-1$? כי כאשר מגיעים למועמד האחרון אין עוד ברירה — חייבים לקבל אותו, בלי תנאי. אלמלא שלב 5 האלגוריתם היה עלול לא להחזיר דבר ([00:12:22]).

הוכחה. ראשית נשים לב לנקודה המתודולוגית: לאחר שהוגרלה $\sigma$, כל שאר הריצה דטרמיניסטית ([00:19:45]). לכן כל מאורע שאנחנו מגדירים חייב להיות פונקציה של $\sigma$ בלבד, ומרחב המדגם הוא $\Omega=S_n$ עם $|\Omega|=n!$.

נגדיר מאורע שני:

$B=\Big\{\sigma \;:\; \sigma^{-1}(\text{best}) \in \{\tfrac{n}{2}+1,\dots,n\} \ \text{ and } \ \sigma^{-1}(\text{2nd best}) \in \{1,\dots,\tfrac{n}{2}\}\Big\},$

כלומר: התמורה שמה את המועמד הטוב ביותר איפשהו בחצי השני, ואת השני-הכי-טוב איפשהו בחצי הראשון.

שלב 1: $B\subseteq A$. נניח ש-$B$ מתרחש. המועמד השני-הכי-טוב נמצא בחצי הראשון, והמועמד הטוב ביותר אינו שם; לכן המקסימום של החצי הראשון הוא בדיוק ערכו של השני-הכי-טוב, כלומר $V=v_{(2)}$ (כאן $v_{(1)}>v_{(2)}>\dots$ הם הערכים בסדר יורד). כעת בחצי השני: המועמד היחיד בכל הקלט שערכו גדול מ-$v_{(2)}$ הוא המועמד הטוב ביותר. לכן בשלב 4 האלגוריתם דוחה כל מי שאינו הטוב ביותר, ומקבל אותו ברגע שהוא מגיע אליו. שני מקרי קצה:

• אם הטוב ביותר יושב במקום $j$ עבור $\tfrac n2 +1 \le j\le n-1$ — הוא ייבחר בשלב 4.
• אם הטוב ביותר יושב דווקא במקום $n$ — אז שלב 4 לא קיבל אף אחד (איש לא עבר את $V$), ושלב 5 מקבל את $\sigma(n)$, שהוא הטוב ביותר.

בשני המקרים האלגוריתם מחזיר את הטוב ביותר, כלומר $A$ מתרחש. לכן $B\subseteq A$ כקבוצות של תמורות. מכאן, לפי מונוטוניות, $\Pr[A]\ge\Pr[B]$ ([00:22:19]).

שלב 2: ספירת $|B|$. נבנה תמורה ב-$B$ בשלושה שלבים בלתי תלויים:

• בוחרים מקום לשני-הכי-טוב בחצי הראשון: $\tfrac{n}{2}$ אפשרויות.
• בוחרים מקום לטוב ביותר בחצי השני: $\tfrac{n}{2}$ אפשרויות.
• מסדרים את $n-2$ הנותרים ב-$n-2$ המקומות הנותרים: $(n-2)!$ אפשרויות.

כל תמורה ב-$B$ מתקבלת בדיוק פעם אחת בבנייה הזאת, ולכן

$|B|=\frac n2\cdot\frac n2\cdot (n-2)! = \frac{n^2}{4}\,(n-2)! .$

שלב 3: החשבון. מאחר שהדגימה אחידה,

$\Pr[B]=\frac{|B|}{|\Omega|}=\frac{\frac{n^2}{4}(n-2)!}{n!} .$

נשתמש ב-$n!=n\,(n-1)\,(n-2)!$, כלומר $\dfrac{(n-2)!}{n!}=\dfrac{1}{n(n-1)}$, ונקבל

$\Pr[B]=\frac{n^2}{4}\cdot\frac{1}{n(n-1)}=\frac{n}{4(n-1)}=\frac14\cdot\frac{n}{n-1}\;\ge\;\frac14,$

שכן $\frac{n}{n-1}>1$ לכל $n\ge2$. בשילוב עם שלב 1: $\Pr[A]\ge\Pr[B]\ge\frac14$. $\blacksquare$

מסקנה 2.1 (תוחלת). לכל קלט, הערך של המועמד שנבחר מקיים בתוחלת

$\mathbb{E}[\,v_{\text{chosen}}\,] \;\ge\; \Pr[A]\cdot v_{(1)} \;\ge\; \frac{v_{(1)}}{4},$

כלומר לפחות רבע מהמקסימום. הנימוק: כל הערכים אי-שליליים, ולכן התוחלת חסומה מלמטה על ידי התרומה של המאורע $A$ בלבד. המרצה ציין זאת ב-[00:31:20] בלי חישוב; זהו החישוב.

מדוע $\tfrac14$ אינו "גרוע" (שאלת סטודנט, [00:29:45]–[00:30:50]). יש להשוות למשפט 1, לא ל-$1$. דטרמיניסטית אין שום ערובה — קיים קלט שעליו הכישלון ודאי. כאן $\tfrac14$ מתקבל לכל קלט, כולל הגרוע ביותר; האקראיות "פיזרה את הסיכון". יתרה מזו, אם מחליפים את הסף $\tfrac n2$ ב-$\tfrac ne$ מקבלים הסתברות הצלחה $\to \tfrac1e\approx 0.37$, וזהו האופטימום — אין אלגוריתם טוב יותר ([00:12:54], [00:17:38]). הבחירה ב-$\tfrac n2$ נעשתה רק כדי שההוכחה תהיה בת שלוש שורות.

משפט 3: נכונות וזמן ריצה של אלגוריתם Freivalds

ניסוח. יהיו $A,B,C$ מטריצות $n\times n$ קבועות (חלק מהקלט, לא אקראיות). האלגוריתם של הגדרה 5 רץ בזמן $O(n^2)$ פעולות אריתמטיות ומקיים:

1. אם $A\cdot B=C$ אז $\Pr_{r}[\text{the algorithm accepts}]=1$;
2. אם $A\cdot B\ne C$ אז $\Pr_{r}[\text{the algorithm accepts}]\le \tfrac12$, ולכן $\Pr_r[\text{rejects}]\ge\tfrac12$.

ההסתברות נלקחת רק על $r$, והחסם תקף לכל שלשת מטריצות.

הערה מתודולוגית חשובה ([00:41:47]–[00:42:19]): אסור לכתוב "$\Pr[\text{the algorithm is correct}]$" בלי לפצל למקרים. הפיצול ל-yes-instance ו-no-instance הוא פיצול לפי הקלט, והקלט אינו אקראי; לכן הוא חייב להיעשות מחוץ לסימן ההסתברות. זו טעות נפוצה למבחן.

זמן ריצה. מחשבים $B\cdot r$ ($\Theta(n^2)$ כפלים), אחר כך $A\cdot(B\cdot r)$ (שוב $\Theta(n^2)$, כי זו מטריצה כפול וקטור), ובנפרד $C\cdot r$ ($\Theta(n^2)$), ולבסוף משווים שני וקטורים באורך $n$ ($O(n)$). סך הכול $O(n^2)$. הנקודה: בזכות האסוציאטיביות לעולם לא מבצעים כפל מטריצה במטריצה ([00:38:59]).

הוכחת סעיף 1 (שלמות). נניח $A\cdot B=C$. אז לכל $r$ בלי יוצא מן הכלל מתקיים $A\cdot(B\cdot r)=(A\cdot B)\cdot r=C\cdot r$, ולכן התנאי בשלב 3 מתקיים והאלגוריתם מקבל. זהו מאורע שמכיל את כל $\Omega$, ולכן הסתברותו $1$. שימו לב שכאן לא נעשה שום שימוש באקראיות — הטענה נכונה פוינטווייז לכל $r$.

הוכחת סעיף 2 (נאותות). נניח $A\cdot B\ne C$ ונסמן

$D:=A\cdot B-C \;\ne\; 0 .$

צעד א' — תרגום תנאי הקבלה. מדיסטריביוטיביות, $A\cdot(B\cdot r)=C\cdot r$ אם ורק אם $(A\cdot B)\cdot r-C\cdot r=0$ אם ורק אם $D\cdot r=0$. לכן

$\Pr_r[\text{accept}]=\Pr_r[\,D\cdot r=0\,].$

צעד ב' — בחירת איבר לא אפסי. מאחר ש-$D\ne0$, יש בה לפחות איבר אחד שונה מאפס. ללא הגבלת הכלליות נניח שזהו $D_{11}$. הבחירה הזו לגיטימית בתוך חישוב הסתברות משום ש-$A,B,C$ (ולכן $D$) אינן אקראיות — האינדקסים נקבעים לפני ההגרלה ואינם תלויים ב-$r$. אילו היה מדובר באיבר $D_{ik}$ כללי, ההוכחה הייתה זהה מילה במילה עם גרירת שני אינדקסים ([00:45:29]).

צעד ג' — מעבר לקואורדינטה אחת. מתקיימת הכלת מאורעות: אם $D\cdot r$ הוא וקטור האפס אז בפרט הקואורדינטה הראשונה שלו אפס. כלומר

$\{r: D\cdot r=0\}\ \subseteq\ \{r: (D\cdot r)_1=0\},$

ולכן, ממונוטוניות, וזה הכיוון הנכון כי אנחנו חוסמים מלמעלה ([00:48:43]):

$\Pr_r[D\cdot r=0]\ \le\ \Pr_r[(D\cdot r)_1=0]=\Pr_r\Big[\sum_{j=1}^{n}D_{1j}r_j=0\Big].$

צעד ד' — בידוד $r_1$. מעבירים אגפים ומבודדים:

$\sum_{j=1}^{n}D_{1j}r_j=0 \iff D_{11}r_1=-\sum_{j=2}^{n}D_{1j}r_j \iff r_1=\frac{-\sum_{j=2}^{n}D_{1j}r_j}{D_{11}} .$

החלוקה חוקית בדיוק משום שדאגנו ש-$D_{11}\ne0$; זו כל המטרה של צעד ב' ([00:53:37]).

צעד ה' — ספירה. מרחב המדגם הוא $\Omega=\{0,1\}^n$ עם $|\Omega|=2^n$, בהתפלגות אחידה. נספור כמה וקטורים מקיימים את השוויון האחרון. נקבע ערכים כלשהם ל-$r_2,\dots,r_n$; יש $2^{n-1}$ קביעות כאלה. עבור כל קביעה, האגף הימני הוא מספר קבוע $c$, ולכן קיים לכל היותר ערך אחד של $r_1$ שמקיים את השוויון: אם $c\in\{0,1\}$ יש בדיוק אפשרות אחת, ואם $c\notin\{0,1\}$ (למשל $c=-3$ או $c$ לא שלם או אפילו אי-רציונלי) אין אף אפשרות ([00:55:47], [00:56:19]). לכן

$\big|\{r\in\{0,1\}^n:\ D\cdot r=0\}\big| \;\le\; 2^{n-1}\cdot 1 \;=\; 2^{n-1},$

ומכאן

$\Pr_r[\text{accept}]\ \le\ \frac{2^{n-1}}{2^{n}}=\frac12 . \qquad\blacksquare$

האופן שבו כדאי לחשוב על צעד ה'. $r_2,\dots,r_n$ הם $n-1$ "משתנים חופשיים" ו-$r_1$ הוא "משתנה תלוי" שנקבע (לכל היותר) על ידם ([01:00:36]). זהו בדיוק תרגיל ספירה, לא טיעון הסתברותי עמוק.

מסקנה 3.1 (טעות חד-צדדית). לפי סעיף 1 אין לאלגוריתם false negative כלל: הוא לעולם אינו דוחה קלט שבו $AB=C$. לכן כל הטעות שלו היא false positive, והיא חד-צדדית ([01:03:46]). זו התכונה שמפעילה את משפט 4.

משפט 4: הגברה בשתי חזרות

האלגוריתם המשופר. על קלט $A,B,C$:

1. הרץ את האלגוריתם של הגדרה 5 פעמיים, כל פעם עם הגרלה טרייה ובלתי תלויה של $r$.
2. אם בשתי ההרצות האלגוריתם קיבל — קבל; אחרת — דחה.

ניסוח. אם $AB=C$ אז $\Pr[\text{accept}]=1$; אם $AB\ne C$ אז $\Pr[\text{accept}]\le\tfrac14$, ולכן $\Pr[\text{correct}]\ge\tfrac34$. זמן הריצה נשאר $O(n^2)$ אסימפטוטית.

הוכחה. יהיו $E_1,E_2$ המאורעות "ההרצה הראשונה קיבלה" ו"ההרצה השנייה קיבלה".

מקרה $AB=C$: לפי משפט 3.1, $\Pr[E_1]=\Pr[E_2]=1$, ולכן שתי ההרצות מקבלות בוודאות והאלגוריתם המשופר מקבל בהסתברות $1$. זה בדיוק מה שהטעות החד-צדדית קונה לנו: הצד הזה לא נפגע מהחזרה ([01:12:25]).

מקרה $AB\ne C$: לפי הגדרת האלגוריתם, האלגוריתם המשופר מקבל אם ורק אם $E_1$ וגם $E_2$. המאורעות $E_1,E_2$ בלתי תלויים, כי הם פונקציות של שתי מחרוזות אקראיות נפרדות שהוגרלו באופן בלתי תלוי — אי-התלות אינה הנחה, היא מובנית באלגוריתם ([01:06:25]). לכן

$\Pr[\text{accept}]=\Pr[E_1\cap E_2]=\Pr[E_1]\cdot\Pr[E_2]\ \le\ \frac12\cdot\frac12=\frac14,$

ומכאן $\Pr[\text{reject}]\ge 1-\tfrac14=\tfrac34$. $\blacksquare$

הערה על שם התהליך: מרגע שנאמר "באופן בלתי תלוי", אפשר לחשוב על שתי ההרצות כאילו נעשו במקביל; זה נקרא גם parallel repetition ([01:06:25]).

משפט 5: הגברה כללית ל-$t$ חזרות

האלגוריתם. על קלט $A,B,C$:

1. הרץ את האלגוריתם של הגדרה 5 $t$ פעמים עם הגרלות טריות ובלתי תלויות.
2. קבל אם ורק אם בכל ההרצות האלגוריתם קיבל.

ניסוח. זמן הריצה הוא $O(t\cdot n^2)$, ולכל $A,B,C$:

• אם $AB=C$: $\ \Pr[\text{accept}]=1$;
• אם $AB\ne C$: $\ \Pr[\text{accept}]\le \dfrac{1}{2^{t}}$, ולכן $\Pr[\text{correct}]\ge 1-\dfrac{1}{2^{t}}$.

הוכחה. זמן הריצה: $t$ הרצות של $O(n^2)$ כל אחת. שימו לב ש-$t$ עצמו רשאי להיות פונקציה של $n$, ולכן הגורם $t$ נשאר מפורש בחסם ([01:11:39]).

נכונות במקרה $AB=C$: כל הרצה מקבלת בהסתברות $1$ (משפט 3.1), ולכן חיתוך של $t$ מאורעות ודאיים הוא מאורע ודאי.

נכונות במקרה $AB\ne C$: יהי $E_i$ המאורע "ההרצה ה-$i$ קיבלה". המאורעות $E_1,\dots,E_t$ בלתי תלויים, שכן כל אחד מהם תלוי בבלוק ביטים אקראיים נפרד וזר לאחרים. האלגוריתם מקבל אם ורק אם $\bigcap_{i=1}^{t}E_i$, ולכן

$\Pr[\text{accept}]=\Pr\Big[\bigcap_{i=1}^{t}E_i\Big]=\prod_{i=1}^{t}\Pr[E_i]\ \le\ \Big(\frac12\Big)^{t}=\frac{1}{2^{t}} . \qquad\blacksquare$

המקרה המעניין: $t=\log n$ (בסיס $2$). אז

$\Pr[\text{failure}]\ \le\ \frac{1}{2^{\log n}}=\frac1n,\qquad \text{running time}\ =O(n^2\log n).$

זהו הלקח הכמותי המרכזי של השיעור ([01:15:16]): גורם ליניארי בזמן הריצה קונה ירידה אקספוננציאלית בהסתברות הכישלון, וזה בדיוק בגלל שהסתברויות של מאורעות בלתי תלויים מוכפלות. ככל ש-$n$ גדל, הסתברות ההצלחה $1-\tfrac1n$ שואפת ל-$1$.

מסקנה 5.1 (טרייד-אוף). יש כאן שתי מטרות מתחרות ([01:10:37]): הגדלת $t$ משפרת את הסתברות ההצלחה אך מגדילה את זמן הריצה, וגם צורכת יותר ביטים אקראיים ($t\cdot n$ במקום $n$). אין ערך "נכון" ל-$t$ — הוא נקבע לפי היישום.

משפט 6: הגרלה מאלפבית גדול יותר, וחשבון הביטים

רקע. שאלת סטודנט ([01:14:05]): למה להגריל $r$ מ-$\{0,1\}^n$ ולא מ-$\{0,1,2\}^n$?

ניסוח. נריץ את האלגוריתם של הגדרה 5 כאשר $r$ נדגם באופן אחיד מ-$\Sigma^n$ עבור $\Sigma=\{0,1,\dots,k-1\}$. אז אם $AB\ne C$ מתקיים $\Pr_r[\text{accept}]\le \dfrac1k$.

הוכחה. ההוכחה של משפט 3 עוברת מילה במילה עד צעד ה'. שם, $|\Omega|=k^n$; לכל קביעה של $r_2,\dots,r_n$ (יש $k^{n-1}$ כאלה) יש לכל היותר ערך אחד של $r_1$ שמקיים $r_1=-\big(\sum_{j\ge2}D_{1j}r_j\big)/D_{11}$. לכן

$\Pr_r[\text{accept}]\le\frac{k^{n-1}}{k^{n}}=\frac1k . \qquad\blacksquare$

בפרט: $\Sigma=\{0,1,2\}$ נותן $\tfrac13$, ו-$\Sigma=\{0,\dots,7\}$ נותן $\tfrac18$ ([01:17:22]).

החשבון שמראה שזה לא בהכרח משתלם ([01:18:25]–[01:19:30]). ביטים אקראיים אמיתיים הם משאב שעולה כסף — ה-random של המחשב אינו אקראי באמת, ואם רוצים ביטים בלתי תלויים באיכות גבוהה משלמים עליהם; זה משאב שכלל לא נכלל בחשבון זמן הריצה שלנו. נשווה שתי דרכים להוציא הסתברות טעות טובה יותר מ-$\tfrac12$:

באותו מחיר בביטים אקראיים, החזרה הכפולה על האלפבית הבינארי נותנת טעות קטנה יותר ($\tfrac14<\tfrac13$) אך משלמת פי שניים בזמן. אין כאן זוכה מוחלט — יש טרייד-אוף, וההחלטה תלויה במה יקר יותר במערכת הספציפית (זמן מעבד, ביטים אקראיים, זמן מתכנתים). המרצה סיכם: "זה כמו פלסטלינה, צריך לשחק עם זה".

הערה נוספת: הבחירה ב-$\{0,1\}$ בהוכחה המקורית נעשתה מסיבה דידקטית בלבד — כך היה קל למנות את כל האפשרויות על הלוח ([01:17:22]).

דוגמאות ותרגילים מהשיעור

דוגמה 1: שתי קוביות — תרגיל החימום על מרחב מדגם

השאלה ([00:24:55]). מטילים שתי קוביות הוגנות. מה ההסתברות שהסכום הוא $5$?

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

$\Omega=\{(x,y): x,y\in\{1,\dots,6\}\},\qquad |\Omega|=6\cdot6=36 .$

ההתפלגות אחידה על $36$ הזוגות. המאורע המבוקש הוא

$E=\{(1,4),(2,3),(3,2),(4,1)\},\qquad |E|=4 .$

לכן $\Pr[E]=\dfrac{4}{36}=\dfrac19$.

הלקח. התשובה הנפוצה והשגויה היא ש-$\Omega=\{2,3,\dots,12\}$ ולכן ההסתברות היא $\tfrac{1}{11}$. הסכום הוא מאורע, לא תוצאת ניסוי; אילו היה מרחב המדגם, כל הסכומים היו שווי הסתברות, וזה שקר. אותה בדיוק טעות ממתינה בבעיית המזכיר: מרחב המדגם הוא $S_n$ ולא $\{1,\dots,n\}$.

דוגמה 2: מעקב מלא אחר אלגוריתם המזכיר עבור $n=4$

הקלט. $n=4$, ערכים $v=(10,40,20,30)$. הטוב ביותר: מועמד $2$ (ערך $40$). השני-הכי-טוב: מועמד $4$ (ערך $30$).

האלגוריתם על הקלט הזה. מגרילים $\sigma$ מתוך $4!=24$ תמורות; מראיינים ודוחים את $\sigma(1),\sigma(2)$ וקובעים $V=\max(v_{\sigma(1)},v_{\sigma(2)})$; בשלב $j=3$ מקבלים אם $v_{\sigma(3)}>V$; אחרת מקבלים את $\sigma(4)$.

החסם מהמשפט. $|B|=\tfrac42\cdot\tfrac42\cdot 2!=2\cdot2\cdot2=8$, ולכן $\Pr[B]=\tfrac{8}{24}=\tfrac13$, בהתאמה מלאה לנוסחה $\tfrac{n}{4(n-1)}=\tfrac{4}{12}=\tfrac13$.

חישוב מדויק של $\Pr[A]$ (מעבר לנדרש, כדי לראות שההכלה $B\subseteq A$ ממש). נסמן את דירוגי המועמדים $1$ (הטוב ביותר) עד $4$ (הגרוע ביותר) ונספור לפי מיקום הטוב ביותר בתמורה:

• הטוב ביותר במקום $3$: אז $v_{\sigma(3)}>V$ תמיד, והאלגוריתם מקבל אותו. הצלחה. מספר תמורות: $3!=6$.
• הטוב ביותר במקום $4$: מצליחים אם ורק אם המועמד במקום $3$ אינו עובר את $V$, כלומר אם הוא אינו הטוב מבין השלושה הראשונים. שלושת המקומות הראשונים מכילים את הדירוגים $\{2,3,4\}$ ב-$3!=6$ סידורים; הכישלון הוא בדיוק כאשר דירוג $2$ יושב במקום $3$, וזה קורה ב-$2$ סידורים. לכן $6-2=4$ הצלחות.
• הטוב ביותר במקום $1$ או במקום $2$: אז $V$ שווה לערך המקסימלי בכל הקלט, איש בחצי השני לא יעבור אותו, והאלגוריתם ייקח את $\sigma(4)$ שאינו הטוב ביותר. כישלון בכל $2\cdot3!=12$ התמורות.

סך הצלחות: $6+4=10$, כלומר

$\Pr[A]=\frac{10}{24}=\frac{5}{12}\approx 0.4167 .$

ואכן $\dfrac{5}{12}>\dfrac13=\Pr[B]>\dfrac14$. ההכלה $B\subseteq A$ אמיתית וממש — יש הצלחות שאינן ב-$B$ (למשל: הטוב ביותר במקום $3$ בעוד השני-הכי-טוב במקום $4$) — ולכן החסם $\tfrac14$ אינו הדוק, אבל הוא זול מאוד להוכחה.

דוגמה 3: מעקב מלא אחר Freivalds, כולל מקרה שבו החסם $\tfrac12$ הדוק

ניקח

$A=\begin{pmatrix}1&2\\3&4\end{pmatrix},\qquad B=\begin{pmatrix}0&1\\1&0\end{pmatrix},\qquad\text{so } A\cdot B=\begin{pmatrix}2&1\\4&3\end{pmatrix}.$

מקרה yes-instance. אם $C=\begin{pmatrix}2&1\\4&3\end{pmatrix}$ אז לכל אחד מארבעת הווקטורים $r\in\{0,1\}^2$ מתקיים $A(Br)=Cr$, והאלגוריתם מקבל. $\Pr[\text{accept}]=1$, כמובטח.

מקרה no-instance. ניקח $C=\begin{pmatrix}2&1\\4&0\end{pmatrix}$, שנבדל מ-$A\cdot B$ רק באיבר $(2,2)$. אז

$D=A\cdot B-C=\begin{pmatrix}0&0\\0&3\end{pmatrix}.$

כאן $D_{11}=0$, ולכן ה"ללא הגבלת הכלליות" של ההוכחה מחייב לבחור את האיבר הלא-אפסי $D_{22}=3$ ולהריץ את הטיעון על השורה השנייה — בדיוק כפי שנאמר בהקלטה שהיה קורה עם אינדקסים כלליים ([00:45:29]).

נבדוק את ארבעת הווקטורים ידנית:

לכן $\Pr[\text{accept}]=\tfrac24=\tfrac12$ בדיוק — הדוגמה מראה שהחסם של משפט 3 הדוק ואי אפשר לשפרו במקרה הגרוע. ואכן, לפי הניתוח: $(D r)_2=3r_2$, שמתאפס אם ורק אם $r_2=0$, ויש $2^{n-1}=2$ וקטורים כאלה מתוך $2^n=4$.

מה עושה ההגברה כאן. על אותו קלט, $t$ הרצות בלתי תלויות טועות רק אם בכל ההרצות הוגרל $r_2=0$, כלומר בהסתברות $\left(\tfrac12\right)^t=2^{-t}$ בדיוק — התאמה מושלמת למשפט 5.

דוגמה 4: החשבון הכמותי שמצדיק את כל התרגיל

ניקח $n=1024$ ו-$t=\log_2 n=10$:

• דטרמיניסטי נאיבי: $n^3=1024^3\approx 1.07\cdot 10^{9}$ פעולות, תשובה ודאית.
• Freivalds עם $t=10$: $t\cdot n^2=10\cdot 1024^2\approx 1.05\cdot 10^{7}$ פעולות — חיסכון של פי $\approx 100$ — והסתברות טעות $\le 2^{-10}=\tfrac{1}{1024}\approx 0.1\%$, וגם זו רק לכיוון אחד.

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

תרגיל (נשאל בכיתה, [01:14:05]) — פתרון מלא

השאלה. מה קורה אם דוגמים $r$ מ-$\{0,1,2\}^n$ במקום מ-$\{0,1\}^n$, והאם זה עדיף?

פתרון. לפי משפט 6, הסתברות הטעות יורדת ל-$\le\tfrac13$. אבל צריך לספור ביטים אקראיים: כל קואורדינטה ב-$\{0,1,2\}$ דורשת שני ביטים, כלומר $2n$ ביטים לעומת $n$. באותם $2n$ ביטים אפשר במקום זאת להריץ פעמיים את הגרסה הבינארית ולקבל טעות $\le\tfrac14$, שהיא טובה יותר מ-$\tfrac13$ — במחיר של פי שניים בזמן הריצה. מסקנה: מבחינת ניצול ביטים אקראיים, חזרה על האלגוריתם הבינארי עדיפה; מבחינת זמן ריצה, האלפבית הגדול עדיף. אין תשובה אחת נכונה — יש טרייד-אוף.

הערות מהשיעור

• [00:00:00] היקף למבחן. בעיית המזכיר "אינה למבחן ואינה חלק מהחומר של הקורס" — המרצה מציג אותה כי היא מדגימה בדיוק את העקרונות שיחזרו בכל השיעור: הקלט הגרוע ביותר, האויב האכזר, מה אקראי ומה שרירותי, ומהו מרחב המדגם. לעומת זאת, מ-[00:29:45] ואילך ("אלגוריתם שהוא כבר כן חלק מהקורס") החומר הוא חומר מבחן מלא.
• [00:08:08] הסדר שבו הדברים נקבעים. "אני מכיר את האלגוריתם שלך כשאני בונה את הקלט, אבל האקראיות נבחרת אחר כך." זו כל הסיבה שאקראיות עוזרת. אם האויב היה רואה גם את המטבעות, לא היה יתרון.
• [00:10:47] מאיפה מגיעה האקראיות. סטודנט שאל מה ההבדל בין "המנהלת מראיינת בסדר אקראי" לבין "המועמדים מגיעים בסדר אקראי". התשובה: הבדל מהותי. הקלט מגיע בסדר שרירותי ואיננו שולטים בו; רק המנהלת רשאית לערבב. הנחה על התפלגות הקלט היא הנחה שאין לנו זכות להניח.
• [00:20:16] מאורעות חייבים להיות פונקציה של האקראיות. "$v_1$ הוא הטוב ביותר" אינו מאורע אקראי; "$\sigma(1)$ הוא הטוב ביותר" כן. אין משמעות להסתברות של דבר שאינו אקראי. שווה לבדוק את זה לפני כל חישוב הסתברות במבחן.
• [00:31:51] למה זה חשוב. שאלת סטודנט "למה צריך את זה?" קיבלה את התשובה המפורשת ביותר בשיעור: "אם אתה שואל אותי מה מכל הקורס לקחת איתך הלאה — זה החלק הזה של אלגוריתמים אקראיים." הנימוק: היום גם זמן ריצה ליניארי עשוי להיות יקר מדי; אם אין תקציב לקרוא את כל הקלט, בהכרח בודקים רק חלק ממנו — ואם בוחרים את המקומות באופן קבוע, יבוא אויב ויקלקל. לכן בוחרים אותם באקראי.
• [00:39:29] אזהרה מפני "שיפור" ריק. "להוריד את זמן הריצה זה לא חוכמה — יכולתי גם להגיד: תזרוק מטבע, יצא אפס תחזיר כן, יצא אחד תחזיר לא." העניין אינו בזמן הריצה לבדו אלא בזמן ריצה יחד עם ערובת נכונות מוכחת.
• [00:46:38] מתודולוגיה של חסמים. "יש לי הרבה יותר כלים לחסום הסתברות מלמעלה מאשר מלמטה. לכן כשאני מנתח אלגוריתם אקראי אני אחסום מלמעלה את הסתברות הכישלון, ומכך אקבל חסם מלמטה על הסתברות ההצלחה." זה מסביר למה כל הניתוח של Freivalds מנוסח על "האלגוריתם מקבל" ולא על "האלגוריתם צודק".
• [01:13:29] מבנה קבוע לניתוח. כמעט תמיד מפצלים ל-yes-instance ו-no-instance, כי האלגוריתם עשוי להתנהג אחרת לגמרי בשני המקרים — אבל זהו פיצול של הקלטים, לא של הדגימה האקראית.
• [01:17:53] ביטים אקראיים עולים כסף. ה-random של המחשב אינו אקראי ואפילו לא קרוב לזה; ביטים אקראיים איכותיים ובלתי תלויים הם מוצר שמשלמים עליו. זהו משאב שהניתוח שלנו כלל לא תמחר.
• [01:20:34] כמה שגיאה מותרת? אין תשובה מוחלטת: $10\%$ שגיאה בחלוקת עיתונים היא זניחה; $10\%$ שגיאה בניתוח מוח היא בלתי נסבלת. "שערה אחת על הראש זה מעט, שערה אחת במרק זה המון."
• [01:21:06] לקראת השיעור הבא. לחזור על תוחלת, ליניאריות התוחלת, ופירוק לאינדיקטורים. השיעור הבא מגדיר את המודל הפורמלי (מכונת טיורינג אקראית) ואת המחלקות; שם ייאמר ([00:40:58] בהקלטה 21) שבעיית וידוא כפל המטריצות שייכת ל-$\mathrm{coRP}$, בדיוק בגלל הטעות החד-צדדית שהוכחנו כאן.

פערים בין הסיכום להקלטה

• מקור: ההקלטה, [00:04:56]–[00:09:42]. הפער: כל הטיעון שאין אלגוריתם דטרמיניסטי עם ערובה לבעיית המזכיר, כולל טיעון האויב האכזר והניסיון הכושל להגריל את הסף, אינו מופיע בסיכום כלל. ההכרעה: נכתב כאן במלואו כמשפט 1, כולל שני מקרי היריב שנאמרו בעל-פה בקיצור.
• מקור: ההקלטה, [00:23:52]–[00:26:31]. הפער: כל הדיון במרחב המדגם ודוגמת שתי הקוביות אינם בסיכום. ההכרעה: נכתבו כהגדרה 2 וכדוגמה 1, כולל הפתרון המספרי ($1/9$) שלא נאמר בהקלטה.
• מקור: ההקלטה, [01:01:40]–[01:04:52]. הפער: המושגים confusion matrix, false positive/false negative וטעות חד-צדדית אינם מופיעים בסיכום, אף שהם המצדיקים את כלל ההגברה "קבל רק אם כולם קיבלו". ההכרעה: נכתבו כהגדרה 3 וכמסקנה 3.1.
• מקור: ההקלטה, [01:14:05]–[01:19:30]. הפער: ניתוח האלפבית $\{0,1,2\}$ וחשבון הביטים האקראיים אינם בסיכום. ההכרעה: נכתבו כמשפט 6 וכתרגיל בסוף סעיף הדוגמאות; ההוכחה הכללית ל-$\Sigma$ בגודל $k$ היא הכללה שלנו של הטיעון שנאמר עבור $k=3$ ו-$k=8$.
• מקור: עמוד 1 בסיכום. הפער: האות $V$ מופיעה בשלוש משמעויות — קבוצת המועמדים ($V=[1,\dots,n]$), ערכי המועמדים ($V_i$), והסף המקסימלי בשלב 3. ההכרעה: הופרדו כאן ל-$[n]$ (המועמדים), $v_i$ (הערכים) ו-$V$ (הסף). זהו תיקון סימון, לא תיקון מתמטי.
• מקור: עמוד 1 בסיכום, שלב 4. הפער: נכתב "אם $\sigma[j]>V$" — השוואה בין אינדקס לבין ערך. ההכרעה: הכוונה ברורה מן ההקשר ומההקלטה ([00:16:03]) והתנאי נכתב כאן $v_{\sigma(j)}>V$.
• מקור: עמוד 1 בסיכום. הפער: לא נאמר ש-$n$ זוגי (אחרת $\tfrac n2$ אינו שלם) ולא שהערכים שונים זה מזה (אחרת "המועמד הטוב ביותר" ו"השני הכי טוב" אינם מוגדרים היטב, וההכלה $B\subseteq A$ עלולה להיכשל). ההכרעה: שתי ההנחות נוספו במפורש בהגדרה 4 ובמשפט 2.
• מקור: ההקלטה, [00:51:55]. הפער: על הלוח נכתב לרגע $\sum_j D_{1j}r_1$ (עם $r_1$ בתוך הסכום); סטודנטית תיקנה והמרצה אישר "טעיתי". הסיכום כותב נכון $\sum_j D_{1j}r_j$. ההכרעה: הסיכום נכון ומופיע כאן; מדובר בפליטת לוח רגעית ולא בפער אמיתי.
• מקור: עמוד 3 בסיכום. הפער: $t=\log n$ נרשם ללא ציון בסיס. ההכרעה: פורש כ-$\log_2$, שכן רק כך $2^{-t}=1/n$ כפי שרשום מיד אחריו ונאמר ב-[01:14:46].
• מקור: משימת הכתיבה מול שני המקורות. הפער: ההבחנה Las Vegas מול Monte Carlo אינה מופיעה בשום מקום בסיכום או בשתי ההקלטות. ההכרעה: נכתבה כהערת מינוח מסומנת בלבד, בתוך הגדרה 1, כדי לא לייחס לקורס מונחים שלא נאמרו בו.
• מקור: הסיכום וההקלטה מול המוסכמות של הסדרה. הפער: שני המקורות מדברים על "האלגוריתם" ולא על שפות ומחלקות, ולכן אין בשיעור הזה שמות מחלקות או רביעיית מכונה. ההכרעה: שמות המחלקות שכן מוזכרים בהפניות קדימה ($\mathrm{P}$, $\mathrm{RP}$, $\mathrm{coRP}$, $\mathrm{BPP}$) נכתבים לפי מוסכמת הסדרה, ולשפת וידוא כפל המטריצות ניתן כאן השם $\mathrm{MATMUL}$ שאינו מופיע במקורות. סימוני המשתנים ($\sigma$, $V$, $r$, $D$) נלקחו מהסיכום.
• מקור: שם קובץ ההקלטה. הפער: הקובץ מתויג "שיעור 14" בעוד תוכנו הוא בדיוק שיעור 15 בסיכומים; ההקלטה שמתאימה לשיעור 14 (השיעור השני על קירוב) חסרה. ההכרעה: התיוג התעלם ממנו; ההקלטה מכסה את שלושת עמודי הסיכום מתחילתה ועד סופה, ואינה פותחת בחזרה על חומר הקירוב.

סיכום ונקודות למבחן

מה חייבים לזכור.

1. על מה ההסתברות. בכל טענה על אלגוריתם אקראי, ההסתברות היא על המטבעות של האלגוריתם בלבד, לקלט קבוע ושרירותי, והערובה נדרשת לכל קלט. "בהסתברות $\ge\tfrac14$" פירושו: לכל קלט, לפחות רבע מהגרלות $\sigma$ מובילות להצלחה. זה לא אומר "לרבע מהקלטים", ולא אומר משהו על קלט אקראי.
2. בעיית המזכיר: דטרמיניסטית אין ערובה כלל; אקראית — הצלחה בהסתברות $\ge\tfrac{n}{4(n-1)}>\tfrac14$, עם הסף $\tfrac n2$. הסף $\tfrac ne$ נותן $\tfrac1e$ וזה אופטימלי.
3. Freivalds: $O(n^2)$; אם $AB=C$ מקבל בהסתברות $1$; אם $AB\ne C$ מקבל בהסתברות $\le\tfrac12$. טעות חד-צדדית.
4. הגברה: $t$ הרצות בלתי תלויות $\Rightarrow$ שגיאה $\le 2^{-t}$ בזמן $O(t\cdot n^2)$. $t=\log n \Rightarrow$ שגיאה $\le 1/n$.

המלכודות הסטנדרטיות.

• מלכודת מרחב המדגם. לזהות את $\Omega$ עם קבוצת הפלטים במקום עם תוצאות הניסוי. בבעיית המזכיר $|\Omega|=n!$, לא $n$.
• מלכודת "הסתברות שהאלגוריתם צודק". אסור לכתוב ביטוי כזה בלי לפצל קודם לפי סוג הקלט; הפיצול הוא מחוץ להסתברות, כי הקלט אינו אקראי.
• מלכודת "לכל היותר אחד". בספירה של משפט 3, לכל קביעת $r_2,\dots,r_n$ יש לכל היותר ערך אחד תקין ל-$r_1$ — ולא בהכרח בדיוק אחד, כי הערך המבוקש עלול כלל לא להיות ב-$\{0,1\}$. כתיבת "בדיוק אחד" היא טעות (אם כי במקרה הזה היא לא מקלקלת את החסם, כי אנחנו חוסמים מלמעלה).
• מלכודת ה-WLOG. מותר לקבוע ש-$D_{11}\ne0$ בתוך חישוב הסתברות רק משום ש-$D$ קבועה ואינה תלויה ב-$r$. אילו $D$ הייתה אקראית, "ללא הגבלת הכלליות" היה טיעון פסול.
• מלכודת ההגברה. הכלל "קבל רק אם כל ההרצות קיבלו" נכון רק כשהטעות חד-צדדית מסוג false positive. עם טעות דו-צדדית הוא הורס את צד ה-yes-instance, וצריך הצבעת רוב.
• מלכודת מאורע לא אקראי. לא לדבר על הסתברות של מאורע שאינו פונקציה של האקראיות.

צ'ק-ליסט: אחרי השיעור צריך לדעת

• לנסח מהו אלגוריתם אקראי ולציין במדויק, לגבי כל טענה, על מה נלקחת ההסתברות ולאילו קלטים היא תקפה.
• לזהות את מרחב המדגם של אלגוריתם אקראי נתון ולחשב בו הסתברות בספירה קומבינטורית.
• לבנות טיעון אויב שמראה שאלגוריתם דטרמיניסטי נכשל, ולהסביר מדוע האקראיות שוברת אותו.
• לכתוב את אלגוריתם Freivalds, לנמק את זמן הריצה $O(n^2)$ דרך האסוציאטיביות, ולשחזר את שרשרת החסמים $\Pr[Dr=0]\le\Pr[(Dr)_1=0]\le 2^{n-1}/2^n=\tfrac12$ על כל צעדיה.
• לחשב את הסתברות הטעות אחרי $t$ חזרות בלתי תלויות, ולבחור $t$ שמשיג יעד שגיאה נתון (למשל $1/n$ או $1/n^c$).
• להסביר מה טעות חד-צדדית, למה היא הופכת את ההגברה לטריוויאלית, ומה משתנה בלעדיה.