הקיים הנעלם - הדוגמה ההסתברותית - האקשן

טוב, אז יש לנו פסוק לוגי שמורכב מ-\( n \) פסוקיות, שבכל אחת שלושה מופעים של משתנים (או שלילתם). אנחנו רוצים להוכיח שקיימת השמה למשתנים שמספקת לפחות \( \frac{7}{8} \) מהפסוקיות. מה עושים?

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

על המרחב הזה מגדירים משתנים מקריים - פונקציות שמעתיקות אירועים בסיסיים לערכים מספריים כלשהם. במקרה שלנו נתאים משתנה מקרי לכל אחת מהפסוקיות, כך שערכו יהיה 1 אם הפסוקיות מסופקת, ו-0 אם הפסוקית לא מסופקת. את המשתנים המקריים נסמן בתור \( Z_1,\dots,Z_n \) (אני משתמש באות \( Z \) כדי להבדיל את המשתנים המקריים מהמשתנים הלוגיים שבתוך הפסוקיות, ויש \( n \) מהם כי זה מספר הפסוקיות). כלומר - בהינתן השמה כלשהי למשתנים הלוגיים, המשתנה \( Z_i \) שווה 1 אם הפסוקית מספר \( i \) מסופקת בהשמה הזו, ואחרת הוא 0.

כעת מגיעה האבחנה החשובה הראשונה: מספר הפסוקיות בנוסחה שמסופקות על ידי השמה כלשהי נתון על ידי סכום המשתנים המקריים שהגדרנו: \( Z=\sum_{i=1}^n Z_i \). נסו להבהיר לעצמכם מדוע זה נכון.

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

כדי לחשב את התוחלת של \( Z \), אנו מתבססים על כך שקל לחשב את התוחלת של כל אחד מהמשתנים \( Z_i \). משתנים כאלו, שיכולים לקבל רק ערכי 0 ו-1, מכונים אינדיקטורים, והתוחלת שלהם היא פשוט ההסתברות שהם יקבלו 1. מהי ההסתברות הזו במקרה שלנו?

נביט על פסוקית שרירותית. יש בה שלושה משתנים, וכל אחד מהם מקבל את הערך “אמת” בהסתברות חצי, ואת הערך “שקר” בהסתברות חצי. מספיק שאחד מהם יקבל את הערך “אמת” כדי שהפסוקית כולה תסופק, ולכן ההסתברות שהפסוקית לא תסופק היא ההסתברות שכל שלושת המשתנים יקבלו את הערך “שקר” - כלומר \( \frac{1}{2}\cdot\frac{1}{2}\cdot\frac{1}{2}=\frac{1}{8} \).

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

ובכן, אם יש שם משתנה והיפוכו, זה משחק רק לטובתי - כי אז ההסתברות שהפסוקית תסופק היא 1 (מדוע?). אם אותו משתנה חוזר על עצמו באותה פסוקית, אז הטענה המקורית בדבר ה-\( \frac{7}{8} \) אינה נכונה (נסו לבנות דוגמה נגדית - יש כזו עם 2 פסוקיות), אבל ממילא זה מקרה “מנוון” - אם יש לנו את אותו משתנה בפסוקית, אז בפסוקית אין באמת 3 משתנים, אלא רק 2 או 1, ואז זה לא מתאים להגדרת הבעיה שלנו. לכן אני מנפנף ב”אלגנטיות” את שני המקרים הללו הצידה.

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

\( E(Z)=E(\sum_{i=1}^nZ_i)=\sum_{i=1}^nE(Z_i)=\sum_{i=1}^n\frac{7}{8}=\frac{7}{8}n \)

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

לכן, קיימת השמה שבה \( Z \) מקבל ערך שהוא לפחות \( \frac{7}{8}n \) - כלומר, לפחות \( \frac{7}{8} \) מהפסוקיות מסתפקות בהשמה הזו, וגמרנו.

רק שאלה אחת נותרה: איפה לעזאזל ההשמה הזו? איך היא נראית? איך מוצאים אותה?

יש למישהו הצעות?

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