הסתברות בסיסית - אחד חלקי קומבינטוריקה

בפוסטים קודמים תיארתי כמה מושגי בסיס בקומבינטוריקה, וכעת אני רוצה להציג כמה שימושים שלהם; אלא שהמקום הטוב והמעניין ביותר לטעמי להצגת שימושים של המושגים הבסיסיים שהראיתי היא דווקא תורת ההסתברות - שהיא מה שנלמד כיום בבתי הספר, וגם מתקשרת חזק יותר לחיי היום יום שלנו. תורת ההסתברות היא זו שעונה על שאלות כגון “מה הסיכוי שלי לזכות בלוטו?” או “מה הסיכוי של פול התמנון להצליח ולנחש את תוצאות משחקי המונדיאל?” או “מה כדאי לעשות בבעיה של מונטי הול?” אבל, תשאלו, מה הקשר לקומבינטוריקה? ובכן, תורת ההסתברות המתמטית היא תורה רחבה ועשירה מאוד, שמתקשרת לתחומים רבים של המתמטיקה. הרבה מאוד תלוי בשאלה מה בדיוק ההגרלה שאנחנו מבצעים; הגרלות שונות נחקרות בכלים שונים. לא אכנס כרגע לעובי הקורה אלא רק אסתפק בלהגיד שאני הולך לדבר לעת עתה על הגרלות פשוטות מאוד יחסית, שעבורן הקשר לקומבינטוריקה ברור. הקשר הבסיסי הוא זה: אם יש לי קבוצה של \( n \) אובייקטים ואני בוחר אחד מהם באקראי (כשלכל איבר יש הסתברות שווה להיבחר), אז ההסתברות שלי להגריל אובייקט אחד ספציפי היא \( \frac{1}{n} \). אם יש 100 תוצאות אפשריות בלוטו, אז ההסתברות שלי לזכות בלוטו (בהינתן שמילאתי טופס יחיד) היא \( \frac{1}{100} \). באופן כללי כשיש לנו בעיה הסתברותית פשוטה שכזו, אנחנו משתמשים בקומבינטוריקה כדי למצוא כמה אובייקטים קיימים בסך הכל (“כמה תוצאות אפשריות יש בלוטו?”) ואז ההסתברות שלנו לזכות היא אחד חלקי המספר שמצאנו.

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

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

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

ההגדרה הפורמלית היא של מושג שנקרא “מרחב הסתברות”. מרחב הסתברות בא לתאר “ניסוי” שיכולות להיות לו כמה תוצאות שונות אפשריות; הוא כולל את “מרחב המדגם” שהוא קבוצת כל התוצאות האפשריות, ו”מידת הסתברות”, שהיא ערך מספרי שמותאם לכל איבר במרחב המדגם. הדרישה היחידה היא שסכום ההסתברויות של כל התוצאות האפשריות יהיה בדיוק 1. כך למשל עבור הטלת קוביה מרחב המדגם הוא הקבוצה \( X=\left\{ 1,2,3,4,5,6\right\} \) (זהו סימון פשוט לקבוצה שאבריה הם המספרים מ-\( 1 \) עד \( 6 \)), וההסתברות היא \( p\left(a\right)=\frac{1}{6} \) לכל \( a\in X \). הנחה חשובה אחת שכן אציין במפורש היא שמרחב המדגם \( X \) שלנו הוא סופי; יש רק מספר סופי של תוצאות אפשריות לניסוי. זו דרישה מאוד מגבילה, והסיבה שאני מציין אותה כאן היא שברגע שבו מתירים מרחב מדגם אינסופי התורה מסתבכת פי כמה וכמה. על הסיבוך שמתקבל כשמתירים קבוצה אינסופית “קטנה” (מה שמכונה “קבוצה בת מניה”בניסוח מתמטי יותר מדוייק - קבוצה שאפשר למספר את אבריה ב-\( 1,2,3,\dots \) וכן הלאה) אני עוד אוכל לדבר ואעשה זאת בהמשך; אבל הסיבוך שמתקבל ברגע שמרחב המדגם הוא קבוצה אינסופית “גדולה” (למשל, קבוצת כל המספרים הממשיים, שניתן להוכיח שאינה בת מניה) כבר לא אדבר כלל כי התורה הופכת להרבה יותר מורכבת (והרבה יותר מעניינת) בשלב זה, ומפסיקה לחלוטין להיות חומר ברמה תיכונית.

ההסתברות של כל תוצאה במרחב המדגם לא חייבת להיות זהה. אין בעיה להגדיר מרחב מדגם שמייצג קוביה “מוטה”: \( X=\left\{ 1,2,3,4,5,6\right\} \) אבל \( p\left(1\right)=\frac{1}{2},p\left(2\right)=\frac{1}{3},p\left(3\right)=\frac{1}{6},p\left(4\right)=p\left(5\right)=p\left(6\right)=0 \). כאן ההסתברויות מאוד לא אחידות, והתוצאות 4,5,6 מיותרות לחלוטין - אין שום סיכוי שהן יצאו.

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

אם כן, מהו מרחב המדגם? מה כאן ההגרלה בכלל? די ברור שהגרלה אחת היא של המיקום של המכונית מאחורי הדלתות - אנחנו מניחים (למרות ששימו לב - זה מעולם לא נאמר במפורש!) שההסתברות היא אחידה לכל אחת מהדלתות. באופן דומה אנחנו מניחים שהבחירה שלנו עצמנו בדלת היא הסתברותית ושלכל דלת אותה הסתברות. לכן אפשר לתאר כל תוצאה במרחב המדגם שלנו כזוג \( \left(a,b\right) \) כאשר \( a,b \) שניהם מספרים בין 1 ל-3, וההסתברות של כל תוצאה \( \left(a,b\right) \) שכזו היא בדיוק \( \frac{1}{9} \).

מהי ההסתברות שהניחוש הראשוני שלנו יהיה נכון ונפגע בדלת הנכונה? פורמלית זהו סכום ההסתברויות של כל התוצאות שבהן הניחוש שלנו זהה לדלת שהוגרלה. במילים אחרות, כל הזוגות \( \left(a,b\right) \) שבהם \( a=b \). דרך אחת לכתוב את הקבוצה הזו היא \( \left\{ \left(a,b\right)|a=b\right\} \) (“זוגות מהצורה \( \left(a,b\right) \) שמקיימים את הקריטריון \( a=b \)). דרך אחרת לכתוב את זה היא בתור \( \left\{ \left(a,a\right)|a=1,\dots,3\right\} \) (“זוגות מהצורה \( \left(a,a\right) \) כאשר \( a \) הוא מספר בין 1 ל-3”). שימו לב שבדרך ההצגה הראשונה בכלל לא טרחתי לציין ש-\( a,b \) הם מספרים בין 1 ל-3 אלא השארתי לקורא להבין את זה מההקשר; בדרך ההצגה השניה ציינתי זאת במפורש כי לא נעים לכתוב רק \( \left\{ \left(a,a\right)\right\} \) שנראה קצר מדי. אני מתעמק על הנקודה הזו כי כך קורה לעתים קרובות במתמטיקה - קבוצות מוגדרות באופנים “מקוצרים” שמשאירים לקורא חלק מההבנה של ההגדרה.

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

ההסתברות לכך שמאורע מסויים יתרחש היא בסך הכל סכום ההסתברויות של האיברים שלו. כאן ההסתברות של כל איבר במרחב המדגם היא \( \frac{1}{9} \) ובמאורע שדיברנו עליו יש שלושה איברים, ולכן ההסתברות של המאורע הזה היא \( \frac{1}{9}+\frac{1}{9}+\frac{1}{9}=\frac{1}{3} \), ועל כן זו ההסתברות שנקלע למטרה בנסיון הראשון. מכאן אפשר כבר להסיק את יתר הניתוח של מונטי הול - אם אנחנו מחליפים דלת תמיד, אז ההסתברות שנזכה שווה להסתברות שהניחוש הראשון שלנו יהיה שגוי; ואם ההסתברות לכך שהוא יהיה נכון היא \( \frac{1}{3} \), אז ההסתברות לכך שהוא יהיה שגוי היא \( 1-\frac{1}{3}=\frac{2}{3} \) (כאן אנו מסתמכים על כך שסכום ההסתברויות של כל האיברים במרחב המדגם הוא \( 1 \), ולכן כדי לדעת את ההסתברות של המאורע “הניחוש הראשוני שלנו היה שגוי”מספיק לחסר מ-1 את ההסתברות של כל האיברים של מרחב המדגם שלא שייכים למאורע הזה. מבחינה מתמטית פורמלית מתארים את זה כך: אם מאורע מסומן ב-\( A \), אז ב-\( \overline{A} \) (או לפעמים \( A^{c} \)) מסמנים את המאורע המשלים שלו, של כל אברי מרחב המדגם שאינם ב-\( A \). ואז מתקיימת הנוסחה \( p\left(\overline{A}\right)=1-p\left(A\right) \).

נסכם אם כן את מה שאמרנו עד כה: בהסתברות מגדירים מרחב מדגם שהוא קבוצה \( X \) שמייצגת את התוצאות האפשריות של הגרלה כלשהי, כך שלכל \( a\in X \) מותאם מספר \( 0\le p\left(a\right)\le1 \) ומתקיים \( \sum_{a\in X}p\left(a\right)=1 \) (סכום ההסתברויות של כל אברי \( X \) הוא 1). לתת קבוצות של \( X \), \( A\subseteq X \) קוראים “מאורעות” והסתברותן היא פשוט סכום ההסתברויות של אבריהן: \( p\left(A\right)=\sum_{a\in A}p\left(a\right) \). אפשר גם לדבר על המאורע ה”ריק” שלא מכיל שום איברים - מסמנים זאת בסימן הרגיל שבו מסמנים את הקבוצה הריקה, \( \emptyset \), ומן הסתם \( p\left(\emptyset\right)=0 \). זו נקודת המוצא האקסיומטית שמאפשרת דיון מתמטי מדוייק במושגי הסתברות שונים ומשונים שאציג בהמשך. למרות שכל זה פשוט יחסית, האקסיומות הללו הוצעו רק במהלך המאה ה-20 (בעוד שחקר פחות פורמלי של הסתברות בוצע כבר מאות שנים לפני כן).

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

נניח ש-\( X \) אינה קבוצה סופית אלא אינסופית; איך אפשר לדבר על סכום איבריה? הקריטריון \( \sum_{a\in X}p\left(a\right)=1 \) נהיה בעייתי לניסוח. כל עוד \( X \) היא בת מניה המצב לא גרוע כל כך כי יש לנו מושג קיים של סכום בן מניה של איברים. אבל אם \( X \) היא לא בת מניה (למשל, \( X=\mathbb{R} \)) כל התורה הזו הולכת לפח; לא קשה להראות שכדי שיתקיים \( \sum_{a\in X}p\left(a\right)=1 \) אז בהכרח רק מספר בן מניה של איברים \( a\in X \) יכול לקיים \( p\left(a\right)>0 \). כלומר, צריך לזרוק את ההגדרות שאיתן עבדתי עד כה ולהמציא משהו מחוכם יותר. הפתרון הוא לא להגדיר את \( p \) לכל איבר ב-\( X \) בנפרד, אלא להגדיר את \( p \) מראש על תת קבוצות של \( X \); כלומר, להגדיר את \( p \) על מאורעות, ולא סתם על איברים בודדים. למעשה, בהכרח יתקיים שלמרביתם המוחצת של המאורעות שכוללים רק איבר אחד, ההסתברות תהיה 0; זה לא אומר שהאיבר הזה לעולם לא יכול להיבחר, אלא “כמעט אף פעם לא” ייבחר.

כמובן שאי אפשר להגדיר את \( p \) באופן שרירותי אלא נדרש הגיון מסויים (למשל, שאם מאורע אחד מכיל מאורע אחר, הסתברותו תהיה גדולה יותר). לפונקציה שמקיימת את ההגיון הזה קוראים “פונקצית מידה” והיא מופיעה במתמטיקה בהקשרים רבים, לא רק של תורת ההסתברות. אחת מהתוצאות הבסיסיות של תורת המידה (שכבר תיארתי בעבר) היא שלא ניתן להגדיר פונקצית מידה “מוצלחת” על כל אברי הישר הממשי. גם בתורת ההסתברות יש בעיה דומה - לרוב לא ניתן להגדיר הסתברות באופן מוצלח על כל תת הקבוצות של \( X \), ולכן בהגדרת מרחב ההסתברות מציינים מראש במפורש מהן הקבוצות שעליהן כן מוגדרת מידה - אוסף קבוצות זה נקרא “מרחב המאורעות” של המרחב ההסתברותי והוא חלק בלתי נפרד מההגדרה. במקרה של \( X \) הסופי שעליו דיברתי בפוסט הזה כל הקושי הזה נעלם כי כל תת קבוצה של \( X \) ניתנת למדידה באופן שהצגתי (\( p\left(A\right)=\sum_{a\in A}p\left(a\right) \)) ולכן לא נכנסתי לכל הפרטים הללו.

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