בפוסט הקודם נפנפתי קצת ידיים על אחת מהסיבות הנפוצות לקושי שבהוכחה ש-
; העובדה שאחד מרעיונות ההוכחה החזקים והיפים שבמתמטיקה ומדעי המחשב, הלכסון שגורם להפניה עצמית, מה שמככב במשפט אי השלמות של גדל ובהוכחת אי כריעותה של בעית העצירה – רעיון זה פשוט לא יכול לעבוד כאשר עוסקים ב-
וב-
. בפוסט הזה אני רוצה להיות יותר טכני ולפרט גם את האופן שבו עושים זאת, אף שאני משער שחלק מהקוראים לא יצליחו לעקוב אחרי ההוכחה עד סופה. אני מניח כאן ידע מוקדם כלשהו בתורת הסיבוכיות – ספציפית, למה אנחנו מתכוונים ב"מכונת טיורינג", ב"מכונת טיורינג אי דטרמיניסטית" וב"שפה" (אוסף של מחרוזת סופיות) – מי שאינו מכיר מושגים אלו כנראה יתקשה לעקוב אחרי ההמשך.
ראשית, תזכורת לגבי שיטת הפעולה שלנו: אנחנו משתמשים במודל החישובי של מכונת טיורינג עם אורקל, שאולי יותר פשוט לחשוב עליה במונחים מעשיים כ"תוכנית מחשב עם פונקצית ספריה חזקה במיוחד". אותה פונקצית ספריה מקבלת כקלט מחרוזת ואומרת עליה "כן"או "לא" בהתאם לשאלה מסויימת וקבועה מראש. למשל, "האם למשוואה הזו יש פתרון בשלמים" על קלט שהוא בעצמו משוואה פולינומית עם מקדמים שלמים. זו נשמעת כמו פונקצית ספריה נחמדה ופשוטה יחסית במבט ראשון; אך למעשה, אפשר להוכיח שלא קיימת פונקציה שכזו בעולם האמיתי. עם זאת, אין מניעה מלשחק ב"נדמה לי" – נניח שפונקציה שכזו עומדת לרשותנו; אילו תוכניות מחשב נוכל לכתוב באמצעותה?
מכיוון שאנחנו עוסקים בענייני יעילות, עוד הנחה שלנו לגבי האורקל היא שהוא פועל באופן מיידי. כך אפשר לקצר את פרק הזמן שדורשים חישובים, על ידי כך ששואלים את האורקל שאלות שחישוב התשובה להן באופן ידני הוא תובעני, והאורקל עונה עליהן תכף ומייד. למשל, אם נתון לנו גרף ואנו מתבקשים למצוא כיסוי בצמתים שלו מגודל מסויים (כיסוי בצמתים הוא אוסף צמתים שכל קשת בגרף נוגעת באחד מהם לפחות) ויש לנו פונקצית ספריה שאומרת תכף ומייד, בהינתן גרף ומספר, האם קיים בגרף כיסוי קודקודים בגודל הדרוש, אז קל מאוד למצוא את הכיסוי: בוחרים צומת, מסלקים אותה ואת כל הקשתות המחוברות אליה מהגרף, ושואלים את הפונקציה האם קיים כעת כיסוי מהגודל שאנו רוצים פחות 1. אם כן, אז משאירים את הצומת שבחרנו בכיסוי, ואחרת "מתקנים" את הגרף ובודקים את הצומת הבא. הסיבה לכך שהאלגוריתם הוא כעת יעיל היא שהחלק ה"כבד" בו הוא הבדיקה האם בגרפים שמתקבלים במהלך ההרצה יש כיסוי קודקודים.
לא הבנתם כלום? מצויין, ההמשך עוד יותר מבלבל.
הטענה
היא בעצם הטענה "מכונות אי-דטרמיניסטיות פולינומיות יכולות לעשות משהו שמכונות דטרמיניסטיות פולינומיות לא יכולות לעשות". מה שאנו רוצים להראות הוא שאם מחזקים את שני המודלים הללו עם אורקל, אז עבור אורקל אחד המכונות כן ישתוו בכוחן, אבל עבור אורקל אחר אפשר יהיה להראות שהן לא שוות בכוחן (כלומר, להוכיח טענה דמויית
אבל על מחלקה אחרת של מכונות). החלק הקל יותר הוא להרחיב את שני המודלים כך שהם כן יהיו שווים בכוחם – פשוט צריך לתת להם אורקל למשהו שהוא כל כך חזק עד שההבדלים בכוח של שתי המכונות (אם קיימים כאלו) מתפוגגים ונעלמים. דוגמה לאורקל כזה היא אורקל שבהינתן שלשה
של מכונה
, קלט
ומספר
שנתון בבסיס אונרי (למה? מסיבת טכניות – יעילות של אלגוריתמים נמדדת ביחס לגודל הייצוג של קלט, ואם מייצגים מספר שלא בבסיס אונרי אז גודל הייצוג שלו הוא לוגריתמי בגודל של המספר עצמו), אומר האם
עונה "כן"על
תוך
צעדים.
אורקל לשפה הזו מאפשר למכונה דטרמיניסטית לקבל כל שפה שמכונה אי דטרמיניסטית פולינומית יכולה לקבל: אם
היא מכונה אי דטרמיניסטית פולינומית ואנו רוצים לדעת אם היא מקבלת את
, אז נבקש מהאורקל תשובה עבור
כאשר
היא מכונה דטרמיניסטית שמבצעת חיפוש ממצה על כל אפשרויות הריצה של
על
; חיפוש ממצה שכזה לוקח זמן שהוא אקספוננציאלי באורך של
, ולכן בהתאם בוחרים את
להיות בערך הגודל של
(מסיבות טכניות אולי יהיה צורך בקצת יותר).
אלא מה? כל מה שזה מראה הוא ש-
(כש-
היא השפה של האורקל שלנו). אנחנו רוצים להראות ש-
– כלומר, שגם אחרי שמחזקים את המכונות האי-דטרמיניסטיות עם האורקל של
, עדיין מכונות דטרמיניסטיות מצליחות לעשות את אותם הדברים. אלא שזו לא בעיה אמיתית, כי אותה מכונה
שמסמלצת את המכונה האי דטרמיניסטית
יכולה לסמלץ גם קריאות לאורקל – כלומר, לבצע בעצמה את החישוב שהאורקל מבצע, על איזה קלט שלא יהיה ש-
תזרוק עליו, ולענות במקום האורקל. זה לא יגדיל את זמן הריצה של
בצורה משמעותית (כאן צריך לבוא נימוק טכני מפורט יותר, אך אמנע ממנו – זה תרגיל טוב לחשוב מה בדיוק צריך לומר ואיזה עוד סיבוכים עשויים לצוץ; למשל, האם
יכולה לקרוא לאורקל עם קלטים שבהם
הוא "גדול מדי"?).
יפה. אם כן, עבור האורקל החזק הזה, מכונת דטרמיניסטיות ואי דטרמיניסטיות משתוות. החלק הקשה יותר הוא לחשוב על אורקל שעבורו לא רק שהן לא משתוות, אלא שאפילו ניתן להוכיח זאת. במילים אחרות, אנחנו רוצים להוכיח משפט שדומה למשפט
, וצריכים לחפש את ההקלה המתאימה שתאפשר לנו להוכיח משפט שכזה.
בואו ניקח שפה
כלשהי. לשפה הזו ניתן להתאים שפה אחרת,
, של אורכי המילים ב-
(שוב, בייצוג אונרי). במילים אחרות, בהינתן מספר
השאלה היא האם קיימת מילה מאורך
בשפה
. זו שאלה שקל מאוד להכריע אם אנחנו מכונה אי דטרמיניסטית עם אורקל לשפה
: בהינתן
פשוט מנחשים מילה מאורך
, שואלים את האורקל האם היא שייכת ל-
ואם כן – מקבלים. אם כן, לכל שפה
מתקיים ש-
. מצד שני, מכונה דטרמיניסטית פולינומית לא יכולה לנקוט בגישה הזו – אם נותנים לה
, לבדוק את כל המילים מאורך
ייקח לה יותר מדי זמן כי יש
כאלו. זה נותן פתח לתקווה לכך שיתקיים
עבור שפה
שתהונדס בצורה מתאימה. כמו שכל מי שמכיר קצת את תורת הסיבוכיות יודע, להוכיח שמשהו הוא קשה זה עניין קשה, והבניה של
היא יצירתית למדי ומסתמכת – איך לא – על לכסון.
הבה ונמספר את כל מכונות הטיורינג הדטרמיניסטיות עם אורקל הקיימות –
. מה שנעשה יהיה לבנות את
בשלבים, כשבשלב ה-
ננסה לגרום למכונה
לטעות בתשובה שהיא אמורה לתת על מילה כלשהי מ-
.
נתחיל מכך ש-
ריקה. כפי שניתן יהיה לראות מהבניה, בכל שלב תישמר התכונה שב-
רק מספר סופי של מילים. בסיבוב ה-
בבניה, ניקח מספר
שגדול ממספר הסיבוב הנוכחי
ומאורך כל המילים שעד כה הוכנסו ל-
. המטרה שלנו – לגרום ל-
"לטעות"בתשובה שהיא מחזירה על
. בדרך כלל מה שהיינו עושים הוא לומר "נריץ את
על
; אם
דחתה, נוסיף את
ל-
; ואם היא קיבלה לא נוסיף אותו". זה גם הרעיון כאן אבל יש לנו סיבוך –
היא מכונה עם גישה לאורקל. ולא סתם אורקל – אורקל לשפה
שאותה אנו בונים. כלומר,
, במהלך ריצתה על
, עשויה לשאול את האורקל על מילים שבכלל עוד לא החלטנו אם הן כן או לא ב-
. עם זאת, זו לא בעיה של ממש – מה שנעשה הוא להריץ את
על
, בכל פעם שבה
תשאל את האורקל על מילה שכבר החלטנו אם היא שייכת ל-
או לא נענה בהתאם לבחירה שביצענו; ואם
שואלת על מילה שאיננה מהמילים שכבר החלטנו עליהן, נענה (בתור האורקל) שהמילה איננה ב-
ונסמן לנו את זה בצד, למקרה שגם בעתיד ישאלו על המילה הזו.
ה"סכנה" שבדרך הפעולה שלנו היא ש-
עלולה לשאול את האורקל שאלה על כל המילים מאורך
. זה אולי נשמע מוזר קצת בהתחלה – לא אמרנו שנדרש זמן אקספוננציאלי כדי לעשות זאת? אבל זו הנקודה העדינה המרכזית בהוכחות מהסוג הזה – אנחנו תוקפים את
עבור
ספציפי, בעוד שדיבורים על זמן ריצה אקספוננציאלי הם רלוונטיים רק כשמדברים על ההתנהגות האסימפטוטית של
, כלומר על האופן שבו
מתנהגת על אינסוף קלטים. ייתכן שעל כל הקלטים עד גודל זיליארד
דורשת פרק זמן גדול עד להדהים, ורק לאחר מכן היא "נרגעת" ורצה זמן פולינומי – גם אז היא עדיין תיחשב פולינומית. מכאן שהסכנה ש-
תבדוק את כל המילים מאורך
היא מוחשית מאוד, ונדרשים פיתולים טכניים כדי להתגבר עליה. במקרה שלנו, פשוט נגביל את זמן הריצה של
– אם היא רצה יותר מ-
צעדים, פשוט נשכח ממנה ונעבור למכונה הבאה. עוד מעט אסביר איך אפשר להבטיח שזה לא יגרום נזק להוכחה שלנו.
אם
עצרה על
תוך לכל היותר
צעדים, אז בהכרח היא לא הספיקה לשאול את האורקל על כל הקלטים מאורך
. אם
קיבלה, הרי שהיא טוענת שב-
יש מילה מאורך
, אולם כרגע בבניה שלנו אין מילה כזו. זכרו –
היה מספר שגדול מאורך כל המילים שהחלטנו אם הן ב-
או לא בתחילת הסיבוב
, ובמהלך הסיבוב עצמו לא הוספנו אף מילה ל-
– בכל פעם ש-
שאלה את האורקל על מילה חדשה, אמרנו לה שאותה מילה אינה ב-
. מכאן ש-
טועה. אם לעומת זאת
דחתה את
, כלומר טענה שאין ב-
מילה מאורך
, פשוט נוסיף ל-
מילה כלשהי ש-
לא הספיקה לשאול את האורקל עליה (כאמור, יש כזו). ושוב,
טועה, והגדלנו את
במילה אחת בסך הכל, כך ש-
עדיין סופית.
"האמיתית" היא התוצר הסופי של כל שלבי הבניה הללו. פורמלית, אם
מסמנת את השפה שהתקבלה אחרי השלב ה-
, אז
. מבחינה מתמטית זו בניה חוקית לחלוטין והשפה מוגדרת היטב, אבל היא עשויה להיות מבלבלת למדי למי שלא רגיל לדברים כאלו. עכשיו צריך להשתכנע ש-
אכן אינה מתקבלת על ידי אף מכונה דטרמיניסטית פולינומית.
ובכן, נניח ש-
היא מכונה דטרמיניסטית פולינומית שכזו, ושזמן הריצה שלה חסום על ידי הפולינום
. אז קיים
גדול מספיק כך ש-
. במילים אחרות, אם ננסה "לתקוף" את
עבור המילה
או מילים ארוכות יותר, ננצח. איך אפשר להבטיח שאכן נתקוף את
מתישהו עם מילה ארוכה שכזו? תעלול פשוט – במקום לתקוף את
פעם אחת, נתקוף אותה אינסוף פעמים. כלומר, המניה
לא תכיל כל מכונה רק פעם אחת, אלא מספר אינסופי של פעמים. קל להנדס מניה שכזו – למשל, הביטו בסדרה
שבה מובטח שכל מספר טבעי יופיע מספר אינסופי של פעמים. מכאן שאנו נתקלים ב-
בתור
עבור אינסוף ערכים שונים של
, ומכיוון שדרשנו שה-
שאותו בוחרים בסיבוב ה-
יהיה בפרט גדול מ-
, מובטח לנו שהחל מסיבוב מסויים ה-
שאיתו נתקוף את
אכן יביס אותה.
אחרי שמבינים את כל הפרטים הללו, ההוכחה הזו אינה כה מסובכת – ואכן, רוב הרעיונות בה הם סטנדרטיים לגמרי בתורת הסיבוכיות. עיקר היופי בה הוא בבניה ההדרגתית, הכמו-אלגוריתמית של
ובאופן המחוכם שבו היא מצליחה להתגבר על סכנת ההפניה העצמית שנוצרת משאלות האורקל של
. אבל הדבר היפה באמת בהוכחה הזו הוא בכך שההוכחה לכך שלכסון לא מסוגל לעשות דבר מה היא עצמה הוכחה בלכסון!
שבהינתן מכונה אחרת
שעל קלט
(כלומר, שואלת את
של בעיות שניתנות לפתרון, ו
של בעיות שניתנות לפתרון "חד צדדי"- בעיות שעבורן קיימת מכונה שעוצרת ועונה "כן" אם התשובה היא אכן כן, אך אחרת ייתכן שהיא לא תעצור כלל (או שתעצור ותגיד "לא"). אף שזה לא ברור מייד, שאלת
היא האנלוג הקשור ל"זמן ריצה יעיל" של תוצאת ה-
הזו. (אם לוקחים את הגדרת
של שפות ("שפה"היא פשוט אוסף של קלטים – נניח, אוסף הקלטים שעליהם המכונה עוצרת ואומרת "כן") ואנו רוצים להראות כי
, וכמו כן
בבירור מוכל ב-
, אז דרך אחת להראות זאת היא על ידי הצגת מכונה ששפתה נמצאת ב-
ו-
, אז המכונות ששפתן ב-
, מריצה את
עצמו (הסוגריים המשולשים באים לציין שמדובר על הקידוד של
, דהיינו שיש בעיות שניתן להכריע אך אינן פתירות בזמן פולינומי – ההוכחה תעבוד כמעט באותו האופן, למעט תוספת טכנית חשובה אחת. אני מזהיר מראש – ההוכחה אינה פשוטה לגמרי וחלקכם כנראה יאבד אותי – אפשר לעבור לסוף ההוכחה בלי לפגוע מהותית בקריאת הפוסט.
צעדים – שתיים בחזקת האורך של
טבעי כלשהו כך ש-
– זה מכיוון שפונקציה מעריכית כמו
גדלה מהר יותר מכל פולינום (טענה שדורשת הוכחה אך אינה מסובכת). בואו ניקח בתור
אך לא בסיבוכיות זמן
, וכדומה. אפשר להחיל את אותו רעיון גם על מחלקות סיבוכיות אי דטרמיניסטיות (הדבר דורש עוד תעלולים לא פשוטים), וישנן עוד הוכחות לכסון מחוכמות אף יותר – המפורסם ביותר מבין התוצאות המחוכמות הוא ככל הנראה
. איך מוכיחים דבר כזה? להוכחה המדוייקת אקדיש פוסט נפרד וכעת אסתפק בתיאור הרעיון. המושג החדש שהם מכניסים לתמונה הוא זה של
, להגיד מייד אם
, כאשר
אומר, כצפוי, "המחלקה
, כך ש-
, אבל
. זה מראה מייד שלא ניתן להוכיח לא ש-
.
הוא בעל הסתברות חצי בו, וגם
הוא בעל הסתברות חצי בו, וחסל; אלא ששיטת עבודה שכזו, של שינוי מרחב המדגם, היא מסורבלת למדי באופן כללי, ובעייתית מאוד אם אנחנו רוצים לשאול שאלות מורכבות יותר – למשל, "בהינתן שבהטלת שתי קוביות סכום ערכי הקוביות הוא זוגי, מה ההסתברות שגם מכפלתן זוגית?". לכן משתלם להוסיף למשחק את המושג הפשוט של משתנה מקרי. פורמלית, משתנה מקרי הוא פשוט פונקציה ממרחב המדגם אל המספרים הממשיים (כמובן שאפשר גם יותר מכך אבל אני לא נכנס לזה פה), שמייצגת את ה"ערך" של כל תוצאה אפשרית. מסמנים משתנים מקריים לרוב באותיות לטיניות גדולות, ובפרט ב-
. אפשר לחשוב על משתנה מקרי כאילו הוא מקבל ערכים באופן הבא: ראשית מבצעים את ההגרלה הבסיסית של מרחב המדגם, ולאחר מכן מחשבים את הפונקציה על תוצאת ההגרלה, וזהו ערכו של
בתור ההסתברות ש-
. זה כל הבסיס ההגדרתי שאנחנו צריכים כאן.
כי הסכום הוא בין 2 ל-12 (ולכן בעצם
לכל
כאשר
בין 1 ל-6. סך הכל ישנם
זוגות אפשריים (עקרון הכפל הקומבינטורי). מכיוון שכל זוג הוא שווה-הסתברות, ההסתברות שלו הוא
(עקרון ה"הסתברות במרחב סופי היא אחד חלקי קומבי") ולכן כדי לדעת מה ההסתברות לקבל
; שימו לב שיש חשיבות לסדר ו-
ו-
הם זוגות שונים (כי הראשון אומר "בהטלה הראשונה קיבלנו 1 ובשנייה 4" והשני אומר "בהטלה הראשונה קיבלנו 4 ובשנייה 1"). לכן ההסתברות לקבל 5 היא
. את אותו חישוב אפשר לעשות לכל מספר; לא קשה לראות שההסתברות הגדולה ביותר היא לקבל 7, והיא
ואת ההסתברות הנמוכה ביותר חולקים 2 ו-12, עם הסתברות של
, כאשר
. מה ההסתברות שהמטבע תיפול בדיוק
פעמים על עץ? כדי למדל את השאלה הזו אנו מגדירים משתנה מקרי
לכל
טבעי (ברור שלערכים אחרים ההסתברות היא 0 – מדוע?)
". זו חשיבה בכיוון הנכון, אבל היא שגויה כי היא מתעלמת מגורם נוסף –
ההטלות הנותרות אנחנו רוצים לקבל פלי. ההסתברות לקבל פלי היא
(כי מקבלים או עץ או פלי, וסכום ההסתברויות לקבלת שניהם יחד צריך להיות 1), ולכן ההסתברות לקבל
. כדי לפשט טיפה את הסימון נהוג להגדיר
ואז אפשר לכתוב את ההסתברות הזו בתור
.
ו-
והמטבע הוגן, כלומר
. אז הצבה בנוסחה נותנת לנו
, כלומר שההסתברות לקבל עץ באחת משתי הטלות היא רבע. אבל בואו נכתוב רגע את מרחב המדגם באופן מפורש, כש-1 הוא תוצאה של עץ ו-0 היא תוצאה של פלי:
. קל לראות שבדיוק בשתיים מארבע התוצאות מקבלים פעם אחת עץ, כלומר ההסתברות צריכה להיות חצי. מה השתבש?
בחירות אפשריות שכאלו, ולכן
. נראה מוכר? אכן,
היה בדיוק האיבר הכללי בנוסחת
(קרי: "
") כדי לתאר באופן מקוצר את ההתפלגות הזו.
הוא 1. כאן נחלץ הבינום של ניוטון לעזרתנו – הסכום הזה שווה, על פי הבינום של ניוטון, ל-
; אבל
ולכן הסכום אכן שווה ל-1, כנדרש. שימו לב שכאן אנחנו משתמשים בנוסחת הבינום בכיוון שהוא לכאורה ההפוך – במקום "לפתוח" את הסוגריים אנחנו דווקא מצמצמים סכום "אל תוך" הסוגריים. זה שימוש שיותר נדיר לראות כשאתה תיכוניסט ופותר תרגילים טכניים, אבל הוא כנראה יותר נפוץ בעולם המתמטי האמיתי.
(E מהמילה Expectation). כדי לראות איך מחשבים אותו, בואו ונתבונן בדוגמה פשוטה – שוב הטלת מטבע עם הסתברות
משחקים קיבלנו פלי. אז הרווח הממוצע שלנו הוא
– זהו בעצם ממוצע משוקלל שבו המשקולת של התוצאה
היא מספר הפעמים הצפוי שהיא תצוץ בו, וכך עבור התוצאה
. את הממוצע המשוקלל הזה אפשר לכתוב גם כ-
. ככל ש-
ו-
ילכו ויתייצבו – אנו מצפים ש-
). זהו כמובן נפנוף ידיים, אבל חשוב לזכור שאי אפשר להוכיח מתמטית את הטענה הזו, שהיא בסופו של דבר טענה אמפירית, ואפילו הגדרתית; הרי איך אנחנו מפרשים את "ההסתברות שהאירוע יקרה היא
. ושוב, הדרך הנכונה לחשוב על כך היא כעל שקלול של הערכים האפשריים ש-
, ולכן כאשר
התוחלת היא אפס (כלומר, אנחנו לא מצפים לא להרוויח ולא להפסיד מהמשחק בטווח הארוך) וכמובן שעבור ערכי
, כשהסכום נלקח על פני כל הערכים
. אוי ווי. מבט אחד בסכום ובא לבכות. איך בכל זאת מטפלים בסכומים כאלו? ובכן, יש תעלולים שמשתמשים בחשבון דיפרנציאלי בסיסי ומאפשרים לחשב אותו במדוייק, אך זה דורש פוסט משל עצמו ואני מעדיף לא להיכנס לכך כעת. במקום זאת אציג גישה שונה לגמרי לחישוב התוחלת, שתהפוך את פתרון השאלה הזו לטריוויאלי, ובתקווה תתחיל להמחיש עד כמה הדיבורים על משתנים מקריים מועילים לנו.
(למשל –
הוא מכפלתם). כעת אנו מסוגלים להגדיר באמצעותם משתנים מקריים נוספים, למשל
. האם ניתן לתאר את
באופן פשוט באמצעות
? למשל, האם אפשר לקוות למשוואה יפה כמו
? התשובה חיובית. למעשה, למרות שזה אולי לא נראה כך, זו תשובה מפתיעה למדי למי שכבר השתפשף קצת, שכן היא נכונה בלי קשר לשאלה האם יש תלות בין
על ידי הסתכלות על
לא מתקיים תמיד, אבל כן מתקיים בודאות אם הם בלתי תלויים). ההוכחה של הטענה הזו אינה כה קשה אך היא דורשת הכנסת עוד מושג אחד לתמונה (התפלגות משותפת של משתנים מקריים) ולא אכנס לכך כעת.
כך ש-
הוא המשתנה שמקבל 1 אם בהטלת המטבע ה-
, כלומר התוחלת של אינדיקטור שווה להסתברות שהוא יקבל 1.
– לכל סדרת הטלות במרחב המדגם, מספר ההטלות שבהן התקבל עץ באותה סדרה שווה למספר האינדיקטורים שקיבלו 1 עבור סדרה זו. על פי נוסחת התוחלת שלמעלה (שניתנה עבור שני משתנים אבל נכונה באותה המידה גם עבור
). עם זאת, ברור שהחישוב שנתתי כעת קל מהחישוב הטכני שהיינו צריכים לבצע אם היינו משתמשים ישירות בהגדרה. כמו שאוהבים לומר, מתמטיקאים הם עצלנים, ולכן התוצאות התיאורטיות שהם מוכיחים נועדות (לפעמים…) לעשות את החישובים המעצבנים לקלים יותר.
(לכל תוצאה
בין 0 ל-1 שאומר מה ההסתברות של התוצאה הזו, וסכום ההסתברויות של כולם הוא 1. כמו כן אמרתי שמה שמעניין אותנו בדרך כלל הוא מאורעות, שהם תת-קבוצות של
) ומהווים אוסף של כמה תוצאות אפשריות בעלות משמעות "דומה". למשל, בהטלת קוביה התוצאות הבסיסיות הן
ואילו מאורעות אפשריים הם "הקוביה נפלה על מספר זוגי", "הקוביה נפלה על מספר גדול מ-4", "הקוביה נפלה על 2, או על 3, או על 5"וכדומה. ההסתברות של מאורע, שסימנתי
, הייתה פשוט סכום ההסתברויות של איבריו.
. לכן ההסתברות של 2 היא
) ואז לחלק את ההסתברות של כל איבר ב-
את ההסתברות החדשה שנתנו לכל איבר של
לכל
, ועל כן
הם מאורעות כלשהם במרחב המדגם המקורי, ואנחנו רוצים לדעת מה ההסתברות ש-
. לרוע המזל, זה לא נכון כי ייתכן שחלק מאברי
עצמו, אז נקבל את התוצאה הלא הגיונית שההסתברות שהקוביה תיפול על משהו (שהיא כמובן 1) הופכת פתאום ל-
(החיתוך של
. לצורך פשטות נהוג לסמן זאת כ-
(כלומר,
הוא ההסתברות של "
הנוסחה אינה חוקית כי קיבלתי חלוקה באפס; ואכן, אין ממש הגיון בלשאול מה ההסתברות ש-
. כלומר, ההסתברות שגם
, ואז לקבל את השוויון
. על ידי העברת אגפים קלה מקבלים את הנוסחה הבאה, שהיא חשובה ביותר:
, שהיא ההסתברות שעתודאי יקבל 103 במבחן הבלתי אפשרי. מכיוון שלא מדובר בבעיה מתמטית מופשטת ברור שאין לנו דרך אמיתית לקבל את הנתונים הללו, אבל אפשר להעריך אותם סטטיסטית.
.
.
. עכשיו בואו ונדחוף את כל הנתונים לנוסחה ונראה מה נקבל:
. כלומר, קיבלנו הסתברות של כמעט חמישים אחוז. מצד אחד, זה הרבה. מצד שני, אולי זה לא הרבה כפי שציפינו. תחשבו על הפער האדיר הזה: אם ניקח סטודנט מהרחוב, ההסתברות שלו לקבל 103 במבחן היא אפסית –
. מצד שני, לעתודאי ההבטחה כמעט מוצלחת –
. ועם זאת, ההסתברות שמי שקלקל את המבחן היה סתם סטודנט ולא עתודאי היא הגדולה יותר. למה זה קרה? בגלל הנתון (הלא ריאליסטי, המהונדס לצרכי השאלה – אבל כך גם ה-
,
ו-
, תוצאה שנראית מפתיעה ביותר ממבט ראשון – למרות שהבדיקה כל כך טובה ומדוייקת (לכאורה…), רק עשרה אחוז מהאנשים שמקבלים תשובה חיובית אכן חולים במחלה! זו אחת מהנקודות שחשוב לזכור גם בחיי היום יום שלנו: גם אם מבחן נראה לנו טוב במדד של "ההסתברות שהוא טועה היא נמוכה" זה עדיין לא אומר שהוא טוב גם במובן שחשוב לנו באמת, של "כשמפעילים את המבחן שוב ושוב, כמעט ולא יהיו טעויות". כך הדבר בבדיקת מחלות, או בבדיקה האם הודעות הן דואר זבל, או בבדיקה האם מוצר שיצא מקו ייצור הוא פגום, וכדומה. נוסחת בייס היא השיעור הראשון בסקפטיות שיש ללמוד כשבאים להתייחס לתוצאות סטטיסטיות.
ו-
. במילים אחרות,
. הנעלם בכל הסיפור הזה הוא ההסתברות של מילר-רבין לטעות, ואותה אנחנו מסמנים ב-
ו… רגע, רגע, רגע. אי אפשר לעשות את אותה הטעות פעמיים, חייבים כבר להתייחס אליה במפורש. קודם התחמקתי ממנה כדי לא לסבך את הפשטות של ההצגה עם איזו מהומה טכנית, אבל עכשיו אין מנוס מלהוציא את הפרטים המלוכלכים החוצה.
את המאורע ה"משלים" לו וההסתברות שלו היא
? זה בדיוק מה שנשתמש בו כעת. על פי התיאור שנתתי למעלה,
. הנוסחה הזו היא מקרה פרטי של מה שמכונה "נוסחת ההסתברות השלמה", ואתאר אותה במדוייק עוד מעט.
. עכשיו נוכל להציב את הכל בנוסחת בייס ולקבל:
. באופן בלתי מפתיע גילינו שההסתברות תלויה גם ב-
. למשל, אם אנחנו רוצים הצלחה ב-99 אחוז מהמקרים אנחנו רוצים שיתקיים
, כלומר
, כלומר
. באופן כללי כדי להשיג הצלחה ב-
; אפשר לראות כאן היטב כיצד
שתלוי רק באחוז ההצלחה שאנו שואפים אליו; אבל גם במידע נוסף של גודל התחום שעליו מתבצעת ההגרלה, שבא לידי ביטוי ב-
.
. אז ההסתברות של מאורע
יתרחש, כפול ההסתברות ש-
יתרחש, כפול ההסתברות ש-
. על פניו היא נראית כמו דרך מסובכת יותר לכתוב את
.
(ההסתברות ש-
, כלומר אם ההסתברות ששניהם גם יחד יתקיימו היא בדיוק מכפלת ההסתברויות שכל אחד יתקיים בנפרד. למי שזוכר את עקרון הכפל בקומבינטוריקה, זה בדיוק העיקרון הזה, וזה גם ממחיש לנו מתי אי אפשר להשתמש בעקרון הכפל – בדיוק כשיש תלות כלשהי בין שני הדברים שאנו "סופרים".
, כלומר אם אנחנו מסתכלים רק על
(קבוצה ריקה) אז
ומכאן ש-
או
("בקוביה הראשונה התקבל 3 ובשניה 2") היא משותפת לשני המאורעות כך שברור שהם אינם זרים.
. אם יש 100 תוצאות אפשריות בלוטו, אז ההסתברות שלי לזכות בלוטו (בהינתן שמילאתי טופס יחיד) היא
ירד מחר גשם" היא בעייתית – אמנם, אנחנו עוד לא יודעים מה יקרה, אבל אנחנו יודעים שאו שירד גשם, או שלא; אם היינו מסוגלים לחזות את העתיד היינו יודעים בהסתברות 1 שלא יירד גשם מחר – ואז, מה ההגיון מאחורי אמירה כמו "בהסתברות
מהמקרים – מכאן שההסתברות של תוצאה זו היא
(זהו סימון פשוט לקבוצה שאבריה הם המספרים מ-
), וההסתברות היא
לכל
וכן הלאה) אני עוד אוכל לדבר ואעשה זאת בהמשך; אבל הסיבוך שמתקבל ברגע שמרחב המדגם הוא קבוצה אינסופית "גדולה" (למשל, קבוצת כל המספרים הממשיים, שניתן להוכיח שאינה בת מניה) כבר לא אדבר כלל כי התורה הופכת להרבה יותר מורכבת (והרבה יותר מעניינת) בשלב זה, ומפסיקה לחלוטין להיות חומר ברמה תיכונית.
. כאן ההסתברויות מאוד לא אחידות, והתוצאות 4,5,6 מיותרות לחלוטין – אין שום סיכוי שהן יצאו.
.
. דרך אחת לכתוב את הקבוצה הזו היא
("זוגות מהצורה
("זוגות מהצורה
כאשר
שנראה קצר מדי. אני מתעמק על הנקודה הזו כי כך קורה לעתים קרובות במתמטיקה – קבוצות מוגדרות באופנים "מקוצרים" שמשאירים לקורא חלק מההבנה של ההגדרה.
, ועל כן זו ההסתברות שנקלע למטרה בנסיון הראשון. מכאן אפשר כבר להסיק את יתר הניתוח של מונטי הול – אם אנחנו מחליפים דלת תמיד, אז ההסתברות שנזכה שווה להסתברות שהניחוש הראשון שלנו יהיה שגוי; ואם ההסתברות לכך שהוא יהיה נכון היא
(כאן אנו מסתמכים על כך שסכום ההסתברויות של כל האיברים במרחב המדגם הוא
) מסמנים את המאורע המשלים שלו, של כל אברי מרחב המדגם שאינם ב-
.
ומתקיים
(סכום ההסתברויות של כל אברי
. אפשר גם לדבר על המאורע ה"ריק" שלא מכיל שום איברים – מסמנים זאת בסימן הרגיל שבו מסמנים את הקבוצה הריקה,
, ומן הסתם
. זו נקודת המוצא האקסיומטית שמאפשרת דיון מתמטי מדוייק במושגי הסתברות שונים ומשונים שאציג בהמשך. למרות שכל זה פשוט יחסית, האקסיומות הללו הוצעו רק במהלך המאה ה-20 (בעוד שחקר פחות פורמלי של הסתברות בוצע כבר מאות שנים לפני כן).
) כל התורה הזו הולכת לפח; לא קשה להראות שכדי שיתקיים
. כלומר, צריך לזרוק את ההגדרות שאיתן עבדתי עד כה ולהמציא משהו מחוכם יותר. הפתרון הוא לא להגדיר את
מתכנס ל-137, ובקיצור:
(זהו סימון מקובל שכן בתורת המספרים נהוג לסמן ב-
היה סופי ולא יכל להתבדר; למעשה, העובדה שהטור הזה מתכנס מלמדת אותנו משהו על "כמות" הראשוניים. זכרו שטורים כמו
מתכנסים, כך שאנו למדים שהראשוניים נפוצים יותר מאשר מספרים שהם ריבועים. לטעמי זהו רעיון מקסים – היכולת שלנו למדוד "כמות"באמצעות התבדרות של טור.
, באמצעות מכפלה של גורמים שמערבים ראשוניים; כפי שנראה בקרוב, כל עוד אנחנו מנסים להצטמצם לטורים סופיים לא נוכל לתפוס במדוייק את
כל הראשוניים הקטנים מ-
הוא מספרם; זהו סימון סטנדרטי). הפאנץ' המרכזי הוא שכל מספר טבעי עד וכולל
. מה יש לנו כאן?
. חלקכם ודאי שמים לב שהיצור הזה דומה לסכום של סדרה הנדסית אינסופית:
כאשר
. ובכן, כאן
בבירור, שכן
; ולכן
. במילים אחרות, את המכפלה שלעיל אפשר לכתוב גם כ:
לכל וקטור אפשרי
של מספרים שלמים אי שליליים.
וכעת מה שכתוב בתוך הסוגריים הוא פשוט מספר טבעי שהפירוק לגורמים שלו מכיל רק את הראשוניים
. במילים אחרות,
(המכפלה שכתבנו בהתחלה) שווה ל-
כאשר
. מכיוון שהטור ההרמוני מתבדר, כפי שראינו בפוסט הקודם, נובע מכך שכאשר משאיפים את
. שימו לב שאם
כך ש-
(כי
). כעת בואו וננסה להבין אך
כאשר
. כאן
ולכן ניתן להשתמש בתוצאה הזו. מקבלים:
מקבלים באגף שמאל איברים מהצורה
. אם כן, אפשר לכתוב:
. מה קורה כאשר משאיפים את
הוא טור מתכנס (כי
חייב לשאוף לאינסוף, דהיינו
מתבדר, וזה מה שהיה צריך להוכיח.
, אחרי שלושה עברנו
וכן הלאה. הסכומים הללו הם מקרים פרטיים של
הוא המרחק שנעבר עד וכולל הצעד ה-
בנוסחה וישווה זאת לסכומים שכתבתי למעלה). לא קשה לראות שלא משנה איזה ערך של
; אז לא קשה למצוא
ובאופן כללי, בצעד ה-
, שמכונה "
ושואלים מהו סכום הטור הזה – למה הוא שואף באותו מובן של קודם.
שעליו דיברנו קודם מתכנס ל-1 ולא לאינסוף. לכן מי שטוען שהטור אינסופי מסיבה זו פשוט אינו "משתתף במשחק" שלנו ואינו דובר את אותה שפה כמונו; כבר
כאשר
הוא מספר ממשי כלשהו הגדול ממש מ-1 (
), הטור כן מתכנס ("מתכנס"פירושו שסכומו קטן מאינסוף). כלומר,
, שהוא הסכום המשוער שהזכרתי קודם, אפשר לראות שאם נסכום
איברים נקבל תוצאה שגדולה מ-137. איך? למה? מאיפה המספר הזה הגיע? זה מה שנראה עכשיו. ראשית כל, הנה המחשה ציורית של ההוכחה, שמציגה בבירור את הרעיון המרכזי בה – קיבוץ איברים:


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


? ויתרנו על חישוב מדוייק שלו ובמקום זה הלכנו על חסם תחתון. אמרנו שאפשר לקחת את
ולהשתמש בשיקול הבא:
. הצמצום הזה עוזר לנו לחשב את החסם. כדי לראות זאת יותר בבירור הבה ונסתכל על המספר ההרמוני הבא בתור:
שווה בדיוק ל-
עבור
. זה כבר מכתיב לנו את הדרך למקרה הכללי: נניח שהוכחנו ש-
ואנחנו רוצים למצוא חסם על
, מה עושים? ראשית, כותבים
. כעת, הסכום
כולל בדיוק
איברים, והאיבר הקטן ביותר מביניהם הוא
, כך שאנו מקבלים את החסם
. בעצם הוכחנו כאן באינדוקציה שלכל
מקבלים
. כך שלמעשה,
, ובמילים אחרות –
. אם כן, הוכחנו שהטור ההרמוני עובר את 137 ב-
, ובאותה דרך בדיוק נוכל לרמוס כל טענה שהטור ההרמוני מתכנס לסכום סופי אחר.
אז
ולכן
. למעשה, זה חסם תחתון די גרוע – המספרים ההרמוניים מתנהגים בערך כמו
(ועוד תיקון כלשהו).
(כאשר
היא פונקצית האקספוננט ש
לכל
(אי השוויון מובן מאליו אם זוכרים ש-
– פשוט לקחנו את שני האיברים הראשונים).
.
באופן כללי, ולכן כאן מתקבל
וכן הלאה. המעבר האחרון נובע מכך שהמכפלה שקיבלנו היא "מכפלה טלסקופית" שבה כל איבר מצמצם את האיבר הבא:
, ו-
וכן הלאה.
כלשהו, ומשתמשים במניפולציות שמותר לבצע על טורים מתכנסים כדי להגיע לסתירה. הרעיון פשוט: אם
אז אפשר לכפול את שני האגפים בחצי ולקבל
. שימו לב שבאגף שמאל יש לנו בדיוק את האיברים ה"זוגיים"של הטור ההרמוני והם מתכנסים בדיוק למחצית מסכום הטור ההרמוני. מסקנה? גם האיברים הנותרים, האי זוגיים, מתכנסים למחצית הטור ההרמוני, כלומר
. אלא מה? כל איבר בטור האי זוגיים גדול ממש מהאיבר המתאים לו בטור הזוגיים:
,
וכן הלאה. על כן לא ייתכן שסכום שני הטורים זהה – ההפרש חייב להיות לפחות
עבור
(
, כולל מרוכבים). התבדרות הטור ההרמוני מראה כי
, ואפשר לנצל את התופעה הזו, למשל, כדי להוכיח (בצורה מסובכת יחסית, אמנם) את קיומם של אינסוף ראשוניים; ווריאציה מחוכמת על ההוכחה הזו מובילה למשפט דיריכילה על ראשוניים בסדרות חשבוניות. בקיצור, מדובר בנושא מעניין.
הידוע לשמצה אינו מתכנס בהגדרה הקלאסית, אך כן יש משמעות מסויימת לאמירה שסכומו הוא
והממוצע שלהם הוא
לטור פורמלי מקבלים
וכשמציבים
מקבלים את הטור המדובר, וכשמציבים ב-
. דומני שהסימון הזה איננו המצאה של עצבר, אך בכל מקרה הוא איננו סטנדרטי ואין שום טעם להשתמש בו בהקשר הנוכחי. זו המחשה להבדלי הטרמינולוגיות בין המתמטיקאי והטרחן – בין מי שרוצה שיבינו אותו, ובין מי שלא ברור מה הוא רוצה. כמובן שגם הדיבורים על "אגדה" אינם מבשרים טובות.
, ו-
וכן הלאה. עוד אומר עצבר נכון שאם "מספר הדעיכה" של טור הוא קבוע, אז הטור מתכנס – זו דרך מסובכת להציג את המושג המוכר של טור הנדסי מתכנס. למעשה, צריך להיות מדוייקים – "מספר הדעיכה"של הטור צריך להיות קבוע וקטן מ-1 (הטור
הוא טור הנדסי בעל "מספר דעיכה" 2 והוא אינו מתכנס). אלא שעצבר מבצע כעת קפיצה מחשבתית איומה: המחשבה שאם עבור מספר דעיכה קבוע הטור מתכנס תמיד, זה אומר גם שעבור מספר דעיכה משתנה הטור מתכנס תמיד – טענה שגויה לחלוטין. והוא עוד מגדיל לעשות ואומר:
, ומתקיימת התכונה שלכל
, כלומר האינפימום של
מראה זאת בבירור (מה שכן ניתן לעשות הוא לומר שהאינפימום של הקבוצה כולה הוא גדו או שווה לאפס).
– כל המילים ב-
(שהיא בעצם
, שאותו סימנו בקיצור
סבירה בדיוק כמו כל תוצאה אחרת (אגב, האם מישהו מכם מרגיש "מוזר"להמר על תוצאה כמו
וקוראים לזה "צירופים", אך זה הרבה פחות מקובל במתמטיקה ואני לא משתמש בסימונים הללו אף פעם.
. הדרך לחשב את מספר האפשרויות לבחור בלי החזרה ועם חשיבות לסדר
דרכים לסדר אותם, כך שהתוצאה היא
. אפשר גם להגיע לתוצאה הזו בדרך ישירה: בהתחלה יש לנו
איברים, אחר כך
וכן הלאה… עד שבסופו של דבר יש לנו
(ה-
בסוגר האחרון נובע מכך שהבחירה האחרונה מתבצעת רגע לפני שאנו נשארים עם
, אבל היא יותר מסורבלת לכתיבה. שימו לב, אגב, שאם היינו בוחרים
היינו מקבלים את התוצאה
– כלומר, הכללנו גם את הרעיון של סידור
סידורים פנימיים של הכדורים הכחולים, ולכן התוצאה היא
– בדיוק
. קבוצה יכולה להכיל גם איבר בודד; לכן אנחנו יכולים להניח שה-
. על פי אותו הגיון שתיארתי קודם, מספר הסידורים האפשריים בשורה של האיברים הללו, כשאנחנו מתעלמים מהסידורים הפנימיים בין איברים מאותו צבע, הוא
. שימו לב ש-
ואין צורך לכתוב את ה-
). למה הסיטואציה הזו אכן מתארת חליפות? כי ניתן לחשוב על כך שאנחנו מניחים על העצמים שלנו פתקים שבהם או שכתוב מספר כלשהו מ-
אפשרויות שונות. קל להתבלבל ולשכוח מי במעריך החזקה ומי בבסיס (כלומר, האם זה
או
) ולכן אני ממליץ לנקוט בגישה הבאה: כמה מספרים דו ספרתיים יש, אם מרשים גם לאפס להופיע (כלומר,
הוא המספר ה"דו ספרתי"
וכדומה)?
או
? ובכן,
כך שברור שיש כאן בעיה; לעומת זאת
רווחים (ציירו שני כדורים ותראו את שלושת הרווחים: מימין לכדור הימני, משמאל לשמאלי, ובין שניהם). לכן יש לי בחירה של
כדורים ל-
רווחים שבהם ניתן לשים את
, ואת זה ניתן לכתוב גם כ-
. בזאת מצאנו את הנוסחה לשיטת החלוקה הרביעית והאחרונה.
, כאשר