אוהבים ללעוג למתמטיקאים על כך שהמתמטיקה הנקייה והאידאלית שלהם לא מסתדרת טוב עם העולם האמיתי המלוכלך. גם מדעי המחשב סובלים מבעיה דומה, והראיתי את זה לא מזמן, בפוסט שעסק במאמר שלעג ל"חשיבה המתמטית" שמונעת את ראיית הדרך ה"פשוטה" לפצח את RSA; טענתי אז שגם התאורטיקנים הגדולים ביותר יודעים לטפל – בואפן מתמטי ומדוייק – בבעיות שקשורות לעולם האמיתי. דוגמה מעניינת נוספת לכך היא קודים לתיקון שגיאות – הם באים לטפל בבעיה אמיתית מאוד, ומשתמשים בהם כל הזמן בעולם האמיתי, ומצד שני התורה שלהם יכולה להיות תאורטית מאוד, מתבססת בחלקה הגדול על אלגברה לינארית ומופשטת, והחשוב מכל – יש לה שימושים מפתיעים גם בהוכחת תוצאות תיאורטיות לחלוטין בתחומים אחרים של מדעי המחשב, ובפרט את משפט ה-PCP שהזכרתי בפוסט הקודם.
נחזור לבסיס. במדעי המחשב, אפשר לחשוב על כל אינפורמציה כאילו היא מיוצגת כרצף של סיביות – אפסים ואחדים. גם כשמאחסנים מידע במחשב ועל מדיות שונות ומשונות (כגון דיסקים) וגם כששולחים אותו בקו תקשורת, זה מה שנשלח – אפסים ואחדים. כמובן שבפועל מה שקורה הוא מסובך יותר, אבל זוהי הפשטה שאפשר לבצע ועדיין לקבל תיאור די מדוייק של המציאות; לא ארחיב בנושא מעבר לכך כעת.
אלא שהעולם האמיתי הוא מקום מלוכלך – לקווי תקשורת יש "רעש", דיסקים יכולים להישרט, וכן הלאה. בפועל המשמעות של זה מבחינתנו היא שחלק מהמידע שאנחנו שולחים (מכאן ואילך "לשלוח" פירושו גם "לשים מידע על דיסק"; תחשבו על זה כאילו אנחנו שולחים כך מידע אל גרסה עתידית שלנו שתנסה לקרוא את הדיסק) ייהרס. מה זה "ייהרס" מבחינתנו אם כל מה שיש הוא אפסים ואחדים? שבמקום לקרוא 0 נקרא 1, ולהפך. למשל, נשלח את המילה 0010 ובצעד השני תתקבל המילה 0110. כאן הביט השני "התקלקל". זה יכול לגרום לשינוי עצום במשמעות של המידע שנשלח ולהיות בעל תוצאות הרסניות – בקיצור, אסור להתיר לדברים כאלו לקרות. הבעיה היא שבעולם האמיתי הם קורים כל הזמן. לא סביר לבנות ערוץ ממשי שבו תקלות כאלו לא יתרחשו כל הזמן. בקצרה – אנו נזקקים לפתרון לבעיה שאינו תלוי ערוץ; אנחנו צריכים לקבל את הקלקולים בתור חלק מהחיים ולמצוא דרך לטפל בהם בכל זאת.
גישה נאיבית לבעיה היא זו – במקום לשדר את המידע סיבית-סיבית, נשכפל כל סיבית מספר פעמים כלשהו – נאמר, שלוש – ונשלח את השכפולים ברצף. כך למשל במקום לשלוח את המידע 0010, נשלח 000000111000. מי שמקבל את המידע בצד השני יפרק את הקלט שקיבל לשלשות, ויחליט מה הסיבית שכל שלשה מייצגת על פי "הכרעת רוב". למשל, אם קיבלנו 111, אפשר להניח שהשלשה הזו מייצגת את הסיבית 1; ואם קיבלנו 100, אפשר להניח שהשלשה מייצגת את הסיבית 0. כמובן, ייתכן שנשלח את 000 ובדרך כל שלוש הסיביות יתפקששו, בצד השני יתקבל 111 והמפענח יחשוב שניסיתי לשדר לו 1; אבל הסיכוי לכך שזה יקרה הוא נמוך יחסית. כמובן שכדי לבצע חישוב מדוייק צריך לדעת מהי ההסתברות לכך שסיבית תתפקשש, ובהתאם אפשר לשלוח 5 עותקים של הספרה שרוצים להעביר, או 7, וכו' – איני רוצה להיכנס לניתוחים הללו כעת.
הנה עוד דוגמה לדבר מה שניתן לעשות – אם אני רוצה לשלוח רצף של סיביות, נניח 01010, אני אוסיף לסוף הרצף עוד סיבית אחת, שתתקבל מ"חיבור" כל הסיביות (עם הכלל לפיו \(1+1=0\)). הסיבית הזו נקראת "סיבית הזוגיות", שכן היא 0 אם יש מספר זוגי של 1 ברצף שאני שולח (למשל, ברצף שנתתי בדוגמה) והיא 1 אם יש מספר אי זוגי שלהן (למשל, ברצף 11100). בשביל מה זה טוב? אם בצד השני יקבלו 110001, יבינו שמשהו השתבש, כי סיבית הסימן היא 1 ועם זאת בין שאר חמש הסיביות (שאמורות לייצג את המידע האמיתי) יש רק שתיים שהן מגודל 1. זה טוב לזיהוי השגיאה, אבל לא ממש עוזר לתקן אותה במקרה הזה (כמובן שזיהוי שגיאה הוא חשוב מספיק לכשעצמו – אם שגיאות הן נדירות, אז כשמזוהה שגיאה אפשר לבקש מהשולח שישלח את פיסת המידע שוב).
באופן כללי אפשר לתאר קוד באמצעות שלושה פרמטרים – ראשית, מספר הסיביות שיש בכל מילת קוד; שנית, קבוצת המילים בקוד; שלישית, המרחק המינימלי שבין המילים בקוד. בואו נחזור לרגע לקוד השלשות שתיארתי קודם – זה קוד שהכיל בדיוק שתי מילות קוד, 111 ו-000; כל מילה אחרת הייתה "לא חוקית". אם כן, זה קוד שבו המילים הן מאורך 3 ויש בדיוק שתי מילים. הקוד הזה מאפשר לנו, אם כן, לשלוח שני "סוגי מידע שונים"; אני הגדרתי שרירותית ש-000 ייצג את 0 וש-111 ייצג את 1 אבל זה לא הכרחי; הייתי יכול גם לקבוע ש-000 מייצג את 1 ו-111 מייצג את 0, או שהם מייצגים בכלל את 012 ואת 4325, או כל זוג מוזר אחר. נותר להסביר מהו עניין ה"מרחק".
המילה 000 נראית לנו שונה מהמילה 111 הרבה יותר מאשר 110 שונה מ-111. ההבדל ברור - מספר המקומות השונים בין 000 ו-111 הוא 3, בעוד שמספר המקומות השונים בין 110 ו-111 הוא 1 בלבד. זה מוביל להגדרה של מרחק המינג בין שתי מחרוזות מאורך זהה – מספר המקומות השונים זה מזה במחרוזת, או אם תרצו: מספר השגיאות שצריכות להתרחש כדי שבמקום המחרוזת א' תתקבל המחרוזת ב'.
הסיבה שקוראים להגדרה הזו "מרחק" היא שהתכונות הקלאסיות של מרחק מתקיימות עבורה. המרחק של כל מילה מעצמה הוא 0, ואם יש מרחק 0 בין שתי מילים, זוהי אותה המילה; המרחק של א' מב' זהה למרחק של ב' מא'; והמרחק של א' מג' קטן מסכום המרחקים של א' מב' ומב' לג', לכל מילה ב'. לתכונה האחרונה קוראים "אי שוויון המשולש" בגלל שהיא ניסוח פורמלי של התכונה המוכרת לפיה במשולש סכום אורכי שתי צלעות תמיד גדול או שווה לאורך הצלע השלישית. אם חושבים על צלעות המשולש בתור מסלולים שיש ללכת בהם, אי שוויון המשולש הוא פורמליזציה של האבחנה הפשוטה לפיה עדיף ללכת בקו ישר ולא להתעכב בנקודות ביניים בדרך.
אם כן, המרחק המינימלי בין שתי מילים בקוד הוא מספר השגיאות שצריכות ליפול במהלך השידור כדי שנטעה לחשוב ששום דבר לא השתבש, ונקבל מילת קוד לא נכונה. יותר מזה – חצי מהמרחק המינימלי הוא מספר השגיאות המקסימלי שיכולות ליפול בקוד כך שעדיין נוכל לשחזר את מילת הקוד הנכונה המקורית (למעשה, מספר השגיאות חייב להיות קטן ממש מחצי) – נסו לחשוב מדוע.
כעת אני רוצה לעזוב את הנושא הכללי הזה, שלא התחלתי אפילו לדגדג את קצה-קצהו, ולדבר על קוד מאוד ספציפי, עם תכונה מאוד ספציפית – קוד הדמר (Hadamard), עם תכונה מאוד ספציפית – הוא ניתן לבדיקה מקומית (Locally Testable). הכוונה ב"בדיקה מקומית" היא שבאמצעות דגימה של מספר קטן מאוד – סופי – של ביטים ממילת הקוד ניתן יהיה לזהות בהסתברות טובה האם היא חוקית או לא. ליתר דיוק – אם היא חוקית, תמיד נזהה זאת; אם היא לא חוקית, אז ככל שהיא רחוקה מלהיות מילת קוד חוקית ההסתברות שלנו לזהות זאת תגדל משמעותית (מובן מאליו שאם נפלה שגיאה בביט בודד במילת הקוד אין סיכוי לזהות זאת בהסתברות גדולה על ידי בדיקה של מספר סופי של ביטים – הרי חייבים לקלוע "בול" לביט שהתקלקל כדי שיהיה בכלל סיכוי להבין שמשהו השתבש).
קוד הדמר, כמו רוב הקודים לתיקון שגיאות, הוא קוד לינארי – מילות הקוד מהוות מרחב לינארי מעל שדה סופי כלשהו. אני לא סתם נכנס לעובדה הטכנית הזו – כדי להבין את הרעיון בקוד אין כמעט מנוס מלהכניס לתמונה אלגברה לינארית.
שדה המשחק שלנו הוא מרחבים וקטוריים מעל \(\mathbb{F}_{2}\) – השדה הסופי בן שני איברים (0 ו-1, עם כללי החיבור והכפל הרגילים, כשב"רגילים" הכוונה לכך ש-\(1+1=0\)). "מרחב וקטורי מעל השדה הזה" הוא בסך הכל אוסף של סדרות מאורך נתון כלשהו של איברים מ-\(\mathbb{F}_{2}\); למשל, אם המרחב הוקטורי הוא ממימד 3, אז אברי המרחב הם \(\left(0,0,0\right),\left(0,1,0\right)\) וכן הלאה. בקיצור, טרם חידשנו משהו. כעת יש להכניס לתמונה את שאר התכונות של מרחב וקטורי: אם \(v_{1},v_{2}\) הם איברים של המרחב הוקטורי, כך גם \(v_{1}+v_{2}\) (כשחיבור הוא "רכיב-רכיב", כלומר \(\left(1,0,1\right)+\left(1,1,0\right)=\left(0,1,1\right)\) ). מי שמכיר אלגברה לינארית יודע שיש גם דרישה של כפל בסקלר, אבל במקרה הזה היא לא מעניינת במיוחד (למה?)
בואו נחשוב לרגע שוב על קודים באופן כללי. קוד פשוט יכול להיות קוד שלוקח מילה \(w\) וממיר אותה במילת הקוד \(\left(w,f\left(w\right)\right)\) כש-\(f\) היא פונקציה שמקבלת את \(w\) ופולטת ביט בודד. אם נרצה שהקוד יהיה לינארי (ואנחנו רוצים, שכן קודים לינאריים הם קלים מאוד לניתוח), אז חיבור של שתי מילות קוד צריך לתת בעצמו מילת קוד, כלומר צריך שיתקיים ש-\(\left(w,f\left(w\right)\right)+\left(v,f\left(v\right)\right)=\left(w+v,f\left(w\right)+f\left(v\right)\right)\) יהיה בעצמו מילת קוד חוקית, כלומר שיתקיים \(f\left(w+v\right)=f\left(w\right)+f\left(v\right)\). התכונה הזו נקראת "לינאריות של \(f\)". נסכם – אם אנחנו רוצים לבנות את הקוד שלנו על ידי כך שנוסיף ל-\(w\) עוד ביטים לאחריו, שמחושבים באופן מסויים מ-\(w\), אז כל ביט שכזה חייב להיות מחושב באמצעות פונקציה לינארית.
קוד הדמר לוקח את הגישה הזו עד הסוף – הוא אומר "בואו נוסיף אחרי \(w\) את כל הביטים האפשריים שיכולים להתקבל מחישוב של פונקציה לינארית כלשהי". זה מייד מעלה את השאלה איך בכלל אפשר למצוא ולייצג את כל הפונקציות הלינאריות הללו. זה שוב עניין לסטודנטים לאלגברה לינארית; אבל אפשר להראות שאם \(v=\left(v_{1},v_{2},\dots,v_{n}\right)\) הוא וקטור, אז כל פונקציה לינארית היא מהצורה \(f\left(v\right)=\sum_{i=1}^{n}a_{i}v_{i}\), כשכל \(a_{i}\) הוא או 0 או 1. זו הפשטה נוראית של מה שקורה במקרה הכללי יותר, של מרחב מעל שדה גדול יותר – אבל אני רוצה לא לגלוש לדיון הכללי כרגע.
כעת, הנה אבחנה מעניינת נוספת – \(a=\left(a_{1},a_{2},\dots,a_{n}\right)\) הוא בעצמו איבר המרחב הוקטורי ממימד \(n\) מעל \(\mathbb{F}_{2}\), כלומר אפשר לייצג כל פונקציה לינארית מהמרחב הוקטורי הזה באמצעות איבר מהמרחב הוקטורי הזה! (גם זו תוצאה כללית בהרבה מכפי שאני מציג אותה כאן). כדי לפשט את הסימונים, מגדירים \(a\cdot v=\sum_{i=1}^{n}a_{i}v_{i}\) – לדבר הזה קוראים "מכפלה סקלרית". מכפלה סקלרית דומה למדי לכפל "רגיל", למשל \(a\left(v_{1}+v_{2}\right)=av_{1}+av_{2}\) (התכונה הזו תהיה חשובה בקרוב). נסו להוכיח את התכונה הזו – זה קל למדי, ומסתמך באופן חזק על התכונה הדומה עבור כפל "רגיל".
כעת, אם יש לנו מילה \(w\in\mathbb{F}_{2}^{n}\) (כלומר, רצף של \(n\) ספרות שהן אפס או אחד), אפשר להתעלל קצת בסימונים ולהגיד שנשתמש ב-\(w\) גם כדי לתאר את המילה המקודדת, ולסמן בתור \(w_{a}\) את הביט המתאים במילה המקודדת שמתקבל על ידי חישוב \(a\cdot w\) (ובפירוט יתר: הביט שמתאים להפעלה של הפונקציה הלינארית שמיוצגת על ידי \(a\) על המילה \(w\)). עכשיו אפשר לשים לב לכך שההפרדה המקורית שלנו את מילת הקוד ל"קודם כל המילה המקורית, ואז התוצאה של הפעלת כמה פונקציות לינאריות עליה" היא מלאכותית למדי; גם הביטים של מילת הקוד עצמה יכולים להתקבל מהפעלה של פונקציות לינאריות. למשל, הביט הראשון של \(w\) מתקבל על ידי כפל עם המילה \(e_{1}=\left(1,0,0,\dots,0\right)\), הביט השני על ידי כפל עם \(e_{2}=\left(0,1,0,0,\dots,0\right)\) וכן הלאה. מעתה אמרו – הקידוד של \(w\) הוא פשוט אוסף ההפעלות של כל הפונקציות הלינאריות האפשריות על \(w\). לקידוד הזה יש מחיר – אנחנו מקודדים \(n\) ביטים באמצעות \(2^{n}\) ביטים (כי יש \(2^{n}\) פונקציות לינאריות אפשריות – למה?) – ניפוח אקספוננציאלי של המידע המקורי.
למה זה מועיל? כי במובן מסויים, זה לוקח את המילה \(w\) ו"מורח" את הביטים שלה טוב-טוב. כל קומבינציה אפשרית של ביטים של \(w\) באה לידי ביטוי איפה שהוא במילת הקוד. לכן לדגום באקראי ביט מתוך מילת הקוד בעצם שקול לדגימה אקראית של מספר כלשהו של ביטים מתוך \(w\); יותר במדוייק, אם אני בוחר ביט במילת קוד באקראי, אני בעצם מגריל אינדקס \(a\) באקראי וקורא את \(w_{a}\); והגרלה של \(a\) באופן אקראי (בהתפלגות אחידה) פירושו שכל קוארדינטה של \(a\) מוגרלת בהסתברות \(\frac{1}{2}\) ל-0 ו-\(\frac{1}{2}\) ל-1. כלומר, בדגימה אקראית של ביט ממילת הקוד אנחנו מגרילים כל ביט מ-\(w\) בהסתברות חצי. האבחנה הזו היא המפתח לכך שקוד הדמר ניתן לבדיקה מקומית.
בואו ננסח במדוייק כעת מה מטרתו של בודק מקומי עבור הקוד. הדרישה היא שבהינתן מילת קוד חוקית, הבודק יגיד "כן", ובהינתן מילה שאינה מילת קוד, הבודק יגיד "לא" בהסתברות סבירה, שתלויה במרחק המילה ממילת קוד חוקית. נאמר שהמילה \(w\) רחוקה עד כדי \(\delta\) ממילת קוד חוקית, כש-\(0<\delta\le1\), אם צריך לשנות \(\delta\) מהכניסות של \(w\) כדי לקבל מילת קוד חוקית (למשל, אם \(\delta=\frac{1}{4}\) זה אומר שצריך לשנות רבע מהכניסות של \(w\)). לאלו מכם שרוצים פורמליזם, ההגדרה המדוייקת היא \(\delta=\min_{w^{\prime}\in C}\frac{d\left(w,w^{\prime}\right)}{\left|w\right|}\). זהו בעצם המרחק במשמעותו המקורית כשהוא מנורמל באופן שמתחשב באורך המילים – "המרחק היחסי" שבין המילים. מכניסים אותו לתמונה כי הוא מפשט את הניסוחים הטכניים.
אם כן, מה שאראה הוא בודק מקומי שעל מילה שאיננה מילת קוד חוקית, מזהה זאת בהסתברות של \(\frac{\delta}{2}\) לפחות, אך לא יותר מ-\(\frac{2}{9}\). זאת אומרת שאם \(\delta<\frac{4}{9}\), אז ההסתברות שתתגלה שגיאה היא \(\frac{\delta}{2}\) (ולכן עבור \(\delta\) קטן היא לא גדולה; אבל היא לינארית ב-\(\delta\), וזה טוב), ועבור ערכים גדולים יותר יש הסתברות קבועה של \(\frac{2}{9}\) לגלות שגיאה ולכן על ידי הפעלות נשנות של הבודק אפשר "לנפח" את ההסתברות לגילוי שגיאה עד שתתקרב כרצוננו ל-1. ה"מחיר" יהיה קריאה של בדיוק שלושה ביטים מהקלט; כמובן שה"ניפוח" מצריך קריאה של עוד ביטים, אבל עדיין מספר קבוע שאינו תלוי ב-\(n\). כאן אנחנו מתחילים להרגיש את ה-PCP שהזכרתי בפוסט הקודם; גם שם הרעיון הוא קריאה של מספר קבוע של ביטים.
ואיך הבודק עובד? באופן כמעט מגוחך. הוא בוחר באקראי וקטורים \(a,b\) וקורא את \(w_{a},w_{b}\). כזכור, הערכים הללו הם \(a\cdot w,b\cdot w\), ועל פי כללי הכפל נובע ש-\(aw+bw=\left(a+b\right)w\), מה שמוביל אותנו בקלות לביט הנוסף שיש לדגום – הוא קורא את \(w_{a+b}\) ובודק האם \(w_{a+b}=w_{a}+w_{b}\). אם כן – הוא מקבל (או מתחיל סיבוב בדיקה חדש); אם לא, הוא דוחה. כל כך פשוט.
טוב, אבל למה זה עובד? התשובה הקצרה היא "זה טכני". התשובה הארוכה היא "זה טכני, אבל אראה את זה בכל זאת ובתקווה לא אאבד יותר מדי אנשים, כי זו אחת מההוכחות האהובות עלי". אני מקווה שברור מדוע אם \(w\) היא מילת קוד חוקית הבדיקה עובדת – נימקתי זאת לעיל. השאלה היא מה קורה אם \(w\) אינה מילת קוד חוקית.
הבה ונסמן את ההסתברות שהבודק ידחה את המילה \(w\) ב-\(\varepsilon\). אם \(\varepsilon\ge\frac{2}{9}\), "ניצחנו" – הראנו שהבודק עובד טוב על \(w\). לכן ההנחה היא ש-\(\varepsilon<\frac{2}{9}\). מה שרוצים להראות הוא שמכך נובע שהמרחק היחסי של \(w\) ממילת הקוד החוקית הקרובה ביותר (שהוא, כזכור, \(\delta\)) לא עולה על \(2\varepsilon\) (כלומר – \(\delta\le2\varepsilon\), או \(\varepsilon\ge\frac{\delta}{2}\)). בקיצור – רוצים למצוא איכשהו מילת קוד חוקית שקרובה יחסית ל-\(w\). אה, אבל זה בדיוק מה שקודים לתיקון שגיאות עושים – בהינתן מילה "מקולקלת", מראים כיצד לתקן אותה.
כאן מגיע הרעיון המרכזי בהוכחה, שהוא מקסים. כיצד תיבנה אותה מילת קוד, שאסמן בתור \(v\)? באופן הבא. הכניסה \(v_{a}\) במילה תוגדר בתור "הצבעת הרוב" של \(w\). למה הכוונה? אנחנו יודעים שאם \(w\) הייתה מילה חוקית, אז היה מתקיים \(w_{a}+w_{b}=w_{a+b}\) לכל \(b\) אפשרי, או בניסוח אחר – \(w_{a}=w_{a+b}-w_{b}\). לרוע המזל \(w\) איננה מילת קוד חוקית ולכן זה לא מתקיים עבורה תמיד – כלומר, ייתכן ש-\(w_{a+b}-w_{b}\) לא תמיד מחזיר את אותו ערך, כאשר משנים את הערכים ש-\(b\) מקבל. עם זאת, הערך שמופיע מספר רב יותר של פעמים הוא כנראה הערך ה"נכון" עבור \(w\). אם כן, התיקון של \(w\) יהיה \(v\) כך ש-\(v_{a}=\mbox{majority}_{b}\left\{ w_{a+b}-w_{b}\right\} \), כאשר \(\mbox{majority}\) היא פונקציה שמחזירה את האיבר השכיח יותר ב"קבוצה" שהיא מקבלת ("קבוצה" במרכאות כי בדרך כלל בקבוצות כל איבר נספר פעם אחת, וכאן למספר המופעים יש חשיבות מכרעת).
צריך כעת להראות שני דברים: ראשית ש-\(v\) היא בכלל מילת קוד חוקית; שנית, שהיא קרובה ל-\(w\) עד כדי \(2\varepsilon\) – פורמלית נסמן זאת \(d\left(w,v\right)<\varepsilon\). נתחיל דווקא מהתוצאה השניה. האינטואיציה כאן אינה קשה – אם \(w_{a}\ne v_{a}\), אז אם הבודק המקומי יבחר את \(a\) כאחת משתי הקוארדינטות שהוא בודק, יהיה לו סיכוי של לפחות חצי לעלות על שגיאה, שהרי \(w_{a}\) אינו מתאים לכלל הצבעת הרוב, ולכן עבור רוב הערכים של \(b\) שהבודק יגריל, יתקיים ש-\(w_{a}\ne w_{a+b}-w_{b}\) (כלומר, \(w_{a}+w_{b}\ne w_{a+b}\)). כעת, שימו לב שהסיכוי של הבודק ליפול על \(a\) שמקיים \(w_{a}\ne v_{a}\) הוא בדיוק המרחק היחסי שלהם; ואם הבודק כבר נפל על \(a\) שכזה, ההסתברות שלו ליפול על \(b\) שיכשיל את \(w\) היא לפחות חצי; ולכן ההסתברות של הבודק לדחות את \(w\) היא לפחות \(\frac{1}{2}d\left(w,v\right)\); אבל סימנו ב-\(\varepsilon\) את ההסתברות של הבודק לדחות את \(w\), כלומר \(\frac{1}{2}d\left(w,v\right)\le\varepsilon\), כלומר \(\delta\le d\left(w,v\right)\le2\varepsilon\).
אם כן, נותר אתגר בודד – להראות ש-\(v\) היא מילת קוד חוקית. כפי שניתן לנחש, זה המקום שבו \(\frac{2}{9}\) המסתורי יבוא לידי ביטוי. ברשותכם, ארשה לעצמי להמשיך להיות טכני ולהציג את ההוכחה במלואה. ראשית כל צריך להבהיר לעצמנו כיצד ניתן להוכיח שמילה כלשהי \(v\) היא מילת קוד חוקית. דרך אחת היא להראות איך מילה בת \(n\) ביטים ממופה ל-\(v\) על ידי הקוד; אבל זה די מסורבל. הרבה יותר נחמד להשתמש בקריטריון הבדיקה שכבר הצגנו, ומסתבר שזה אכן מספיק: אם \(v_{a}+v_{b}=v_{a+b}\) לכל \(a,b\), אז \(v\) היא מילת קוד חוקית. האבחנה הזו טבעית למדי – הרי כפי שראינו, גם הביטים של "המילה המקורית" שממנה התקבל הקוד מקודדים בתוך \(v\) (הביט ה-\(i\) מקודד כ-\(v_{e_{i}}\)) ומתכונת החיבוריות הזו נובע שלכל \(a=\sum\alpha_{i}e_{i}\) מתקיים \(v_{a}=v_{\sum\alpha_{i}e_{i}}=\sum\alpha_{i}v_{e_{i}}\), כנדרש.
אם כן, מספיק לקחת \(a,b\) שרירותיים ולהראות שעבורם מתקיים \(v_{a}+v_{b}=v_{a+b}\). באופן די מפתיע, ההוכחה היא כמעט מיידית אם רק נראה עוד משהו אחד – ש"הכרעת הרוב" שמגדירה את \(v_{a}\) היא לא סתם הכרעת רוב, אלא הכרעת רוב מוחץ: שלפחות \(\frac{2}{3}\) מה"הצבעות" \(w_{a+b}-w_{a}\) נתנו את הערך של \(v_{a}\) ולא את הערך השני האפשרי. קודם כל אסביר מדוע זה מסיים את העניין ואז אוכיח זאת.
הטריק הוא להשתמש בשיטה ההסתברותית – להוכיח שמשהו קיים על ידי כך שמראים שההסתברות למציאתו במרחב החיפוש שלנו גדולה מאפס. מה שאנו מחפשים הוא מילה \(c\) שתקיים את שלוש התכונות הבאות בו זמנית:
- \(v_{a}=w_{c}-w_{a+c}\)
- \(v_{b}=w_{b+c}-w_{c}\)
- \(v_{a+b}=w_{b+c}-w_{a+c}\)
אם מצאנו \(c\) כזה, סיימנו. למה? שכן אז \(v_{a}+v_{b} = \left(w_{c}-w_{a+c}\right)+\left(w_{b+c}-w_{c}\right)=w_{b+c}-w_{a+c}=v_{a+b}\) כנדרש. אז למה קיים \(c\) כזה? ובכן, בואו נביט לרגע על המשוואה הראשונה, \(v_{a}=w_{c}-w_{a+c}\). מכיוון שפעולת החיבור מתבצעת מעל \(\mathbb{F}_{2}\) (כלומר, \(1+1=0\), או במילים אחרות \(1=-1\)), זו בדיוק אותה משוואה כמו \(v_{a}=w_{a+c}-w_{c}\)
מה ההסתברות, אם מגרילים \(c\), שהיא לא מתקיימת? בדיוק ההסתברות ש-\(c\) יהיה אחד מקולות המיעוט בהצבעה שקבעה את \(v_{a}\). מכיוון שאמרנו שהרוב בהצבעה היה לפחות \(\frac{2}{3}\), נובע מכך שההסתברות ש-\(c\) יהיה "מקלקל" שכזה היא לכל היותר \(\frac{1}{3}\). באופן דומה גם עבור שני התנאים האחרים אפשר להראות שההסתברות לכך ש-\(c\) לא יקיים אותם היא לכל היותר \(\frac{1}{3}\). כעת, חסם טריוויאלי בהסתברות (שמכונה Union bound) אומר כי אם יש לנו קבוצת מאורעות, אז ההסתברות שלפחות אחד מהם יתרחש היא לכל היותר סכום ההסתברויות של כולם. כאן יש לנו שלושה מאורעות שההסתברות של כל אחד מהם קטנה מ-\(\frac{1}{3}\), ולכן ההסתברות שלפחות אחד מהם יקרה קטנה מ-\(1\) – כלומר, קיים \(c\) שלא מקיים אף אחד מהמאורעות. מכיוון שהמאורעות היו "1 מתקלקל", "2 מתקלקל" ו-"3 מתקלקל", קיבלנו שיש \(c\) שעבורו אף אחד משלושת התנאים אינו מתקלקל – כלומר, סיימנו.
נותר רק להראות שאכן מתקיימת "הכרעת רוב מוחץ", כלומר שעבור לפחות \(\frac{2}{3}\) מה-\(b\)-ים האפשריים מתקיים \(v_{a}=w_{a+b}-w_{b}\).
הבה ונסמן את גודל הרוב ב-\(p\), כלומר \(\mbox{Pr}\left[v_{a}=w_{a+b}-w_{b}\right]=p\) (\(\mbox{Pr}\) הוא סימון סטנדרטי להסתברות של המאורע שבסוגריים; ההסתברות נלקחת על פני הבחירות האקראיות של \(b\)). כעת נשדרג את המשחק – נניח שאנחנו בוחרים באקראי שני "מצביעים", \(b,c\) ושואלים אותם לדעתם; מה ההסתברות שהם יגידו את אותו הדבר? כלומר, מהו \(\mbox{Pr}\left[w_{a+b}-w_{b}=w_{a+c}-w_{c}\right]\)? ובכן, אחד משניים: או ששניהם הצביעו לערך שהרוב בחרו, בהסתברות \(p\) כל אחד ולכן \(p^{2}\) לשניהם יחד; או ששניהם הצביעו עבור הערך השני, בהסתברות \(\left(1-p\right)\) כל אחד ולכן \(\left(1-p\right)^{2}\) לשניהם יחד. סה"כ ההסתברות שהם מסכימים היא \(p^{2}+\left(1-p\right)^{2}\). אם נצליח למצוא חסם תחתון כלשהו על ההסתברות הזו, נוכל לחלץ מהמשוואה (ומכך ש-\(p\ge\frac{1}{2}\)) חסם תחתון על \(p\). כאן גם מתחילה ה"הנדסה לאחור" שלבסוף תניב את ה-\(\frac{2}{9}\) הידוע לשמצה – אנחנו מחפשים חסם תחתון על \(p^{2}+\left(1-p\right)^{2}\) שיגרור \(p>\frac{2}{3}\); קצת משחק בפרמטרים ופתרון משוואה ריבועית יראה כי החסם התחתון הזה הוא \(\frac{5}{9}\) (נסו זאת בבית!).
נסכם: עלינו להראות כי \(\mbox{Pr}\left[w_{a+b}-w_{b}=w_{a+c}-w_{c}\right]>\frac{5}{9}\). הטכניקה דומה לטכניקה שכבר השתמשתי בה. ראשית נשים לב לכך ש-\(\mbox{Pr}\left[w_{a+b}-w_{b}=w_{a+c}-w_{c}\right] = \mbox{Pr}\left[w_{a+b}+w_{c}=w_{a+c}+w_{b}\right]\)
כעת שני האגפים הם "מאוזנים" במידת מה – בכולם מופיעים גם \(a\), גם \(b\) וגם \(c\). יותר מכך – אם \(w\) הייתה מילת קוד חוקית, שני האגפים היו שווים ל-\(w_{a+b+c}\). לכן ההסתברות של המאורע שלמטה היא בעצם ההסתברות שלא חל "קלקול" בחישוב של \(w_{a+b+c}\) לא באמצעות \(w_{a+b}+w_{c}\), וגם לא באמצעות \(w_{a+c}+w_{b}\). לכן שוב נשאל את עצמנו – מה ההסתברות שכן חל קלקול באחד משני המקרים הללו?
אם כן, מה ההסתברות ש-\(w_{a+b}+w_{c}\ne w_{a+b+c}\)? זה טיפה מבלבל מכיוון שהן \(b\) והן \(c\) נבחרו באקראי ואילו \(a\) נקבע מראש, אבל אפשר לפשט קצת את העניינים: אם \(b\) נבחר באקראי ובהתפלגות אחידה מבין כל הערכים האפשריים, ו-\(a\) קבוע, אז גם \(a+b\) מוגרל בהתפלגות אחידה מבין כל הערכים האפשריים (למה?). לכן אפשר לסמן לצורך פשטות \(a^{\prime}=a+b\) ולשאול את עצמנו את השאלה הפשוטה יותר: מהי ההסתברות ש-\(w_{a^{\prime}}+w_{c}\ne w_{a^{\prime}+c}\) כאשר הן \(a^{\prime}\) והן \(c\) נבחרים באקראי? ואת התשובה לשאלה הזו אנחנו יודעים: ההסתברות הזו חסומה על ידי ההסתברות שהבודק ידחה את \(w\) – שהרי זה בדיוק מה שהבודק עושה – מגריל שני אינדקסים ומבצע את בדיקת השוויון שלעיל.
כזכור, בתחילת הדיון הזה הנחנו שהסתברות הדחייה של הבודק היא נמוכה יחסית – נמוכה מ-\(\frac{2}{9}\) (כי במקרה שהיא גבוהה יותר אין מה להראות). מכאן שההסתברות ש-\(w_{a+b}+w_{c}\ne w_{a+b+c}\) קטנה מ-\(\frac{2}{9}\), וגם ההסתברות ש-\(w_{a+c}+w_{b}\ne w_{a+b+c}\) קטנה מ-\(\frac{2}{9}\), ולכן על פי ה-Union bound נקבל שההסתברות שאף אחד משני מאורעות אלו אינו מתרחש, ולכן \(w_{a+b}+w_{c}=w_{a+c}+w_{b}\), היא לפחות \(\frac{5}{9}\), כמו שרצינו. זה מסיים, סוף כל סוף, את ההוכחה כולה.
תרגיל בית למי שרוצה לוודא שהוא אכן הבין את כל החישובים הקטנים והקטנוניים האחרונים, ושה-\(\frac{2}{9}\) שהופיע בהתחלה לא נפל משמיים אלא אפשר להגיע אליו בדרך טבעית: נניח שהיינו רוצים להראות ש-\(p>\frac{3}{4}\) ולא סתם \(p>\frac{2}{3}\); מהו החסם החדש על \(\varepsilon\) שהיה עלינו לדרוש?