כלל השרשרת (הסתברות)

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

כלל השרשרת למאורעות

שני מאורעות

לשני מאורעות <math>A</math> ו <math>B</math>, קובע כלל השרשרת

<math>\mathbb P(A \cap B) = \mathbb P(B \mid A) \mathbb P(A)</math> ,

כאשר <math>\mathbb P(B \mid A)</math> מציין את ההסתברות המותנית של <math>B</math> בהינתן <math>A</math> .

דוגמה

בכד א' יש כדור שחור אחד ו-2 כדורים לבנים, ובכד אחר ב' יש כדור שחור אחד ו-3 כדורים לבנים. נניח שבוחרים כד באקראי ואז מוציאים באקראי כדור מאותו הכד. יהי אירוע <math>A</math> הבחירה בכד א', כלומר <math>\mathbb P(A) = \mathbb P(\overline{A}) = 1/2</math>, כאשר <math>\overline A</math> הוא המאורע המשלים ל <math>A</math> (במקרה זה, המאורע של בחירת כד ב'). יהי אירוע <math>B</math> האפשרות שנוציא כדור לבן. ההסתברות להוצאת כדור לבן, בהינתן שכד א' נבחר, היא <math>\mathbb P(B|A) = 2/3</math> . חיתוך המאורעות, <math>A \cap B</math>, מתאר אם כן את בחירת א' והוצאת כדור לבן מתוכו. ניתן לחשב את ההסתברות למאורע זה על ידי כלל השרשרת באופן הבא:

<math>\mathbb P(A \cap B) = \mathbb P(B \mid A) \mathbb P(A) = \frac 23 \cdot \frac 12 = \frac 13.</math>

מאורעות רבים

למאורעות <math>A_1,\ldots,A_n</math>, שהסתברות החיתוך שלהם אינו אפס, יהיה כלל השרשרת

<math>\begin{align}

\mathbb P\left(A_1 \cap A_2 \cap \ldots \cap A_n\right) &= \mathbb P\left(A_n \mid A_1 \cap \ldots \cap A_{n-1}\right) \mathbb P\left(A_1 \cap \ldots \cap A_{n-1}\right) \\ &= \mathbb P\left(A_n \mid A_1 \cap \ldots \cap A_{n-1}\right) \mathbb P\left(A_{n-1} \mid A_1 \cap \ldots \cap A_{n-2}\right) \mathbb P\left(A_1 \cap \ldots \cap A_{n-2}\right) \\ &= \mathbb P\left(A_n \mid A_1 \cap \ldots \cap A_{n-1}\right) \mathbb P\left(A_{n-1} \mid A_1 \cap \ldots \cap A_{n-2}\right) \cdot \ldots \cdot \mathbb P(A_3 \mid A_1 \cap A_2) \mathbb P(A_2 \mid A_1) \mathbb P(A_1)\\ &= \mathbb P(A_1) \mathbb P(A_2 \mid A_1) \mathbb P(A_3 \mid A_1 \cap A_2) \cdot \ldots \cdot \mathbb P(A_n \mid A_1 \cap \dots \cap A_{n-1})\\ &= \prod_{k=1}^n \mathbb P(A_k \mid A_1 \cap \dots \cap A_{k-1})\\ &= \prod_{k=1}^n \mathbb P\left(A_k \,\Bigg|\, \bigcap_{j=1}^{k-1} A_j\right). \end{align}</math>

מקרה פרטי

עבור <math>n=4</math>, כלומר ארבעה מאורעות, כלל השרשרת יהיה

<math>\begin{align}

\mathbb P(A_1 \cap A_2 \cap A_3 \cap A_4) &= \mathbb P(A_4 \mid A_3 \cap A_2 \cap A_1)\mathbb P(A_3 \cap A_2 \cap A_1) \\ &= \mathbb P(A_4 \mid A_3 \cap A_2 \cap A_1)\mathbb P(A_3 \mid A_2 \cap A_1)\mathbb P(A_2 \cap A_1) \\ &= \mathbb P(A_4 \mid A_3 \cap A_2 \cap A_1)\mathbb P(A_3 \mid A_2 \cap A_1)\mathbb P(A_2 \mid A_1)\mathbb P(A_1) \end{align}</math> .

דוגמה

שולפים באקראי ארבעה קלפים זה אחר זה ללא החזרה מחפיסה סטנדרטית של 52 קלפים. מה ההסתברות שייבחרו 4 אסים?

ראשית, נסמן ב <math display="inline">A_n</math> את המאורע "קבלת אס בשליפה ה <math display="inline">n</math>". ההסתברויות למאורעות <math display="inline">A_1, A_2, A_3, A_4</math> תהינה

<math>\mathbb P(A_1) = \frac 4{52},

\qquad \mathbb P(A_2 \mid A_1) = \frac 3{51}, \qquad \mathbb P(A_3 \mid A_1 \cap A_2) = \frac 2{50}, \qquad \mathbb P(A_4 \mid A_1 \cap A_2 \cap A_3) = \frac 1{49}</math> .

וביישום של כלל השרשרת

<math>\mathbb P(A_1 \cap A_2 \cap A_3 \cap A_4)

= \frac 4{52} \cdot \frac 3{51} \cdot \frac 2{50} \cdot \frac 1{49}</math> .

ניסוח המשפט והוכחתו

יהי <math>(\Omega, \mathcal A, \mathbb P)</math> מרחב הסתברות. נזכיר כי ההסתברות המותנית של <math>A \in \mathcal A</math> בהינתן <math>B \in \mathcal A</math> מוגדר כ

<math>

\begin{align} \mathbb P(A \mid B) := \begin{cases} \frac{\mathbb P(A \cap B)}{\mathbb P(B)}, & \mathbb P(B) > 0,\\ 0 & \mathbb P(B) = 0. \end{cases} \end{align} </math>

יש לנו את המשפט הבא:

משפט: כלל השרשרת

יהי <math>(\Omega, \mathcal A, \mathbb P)</math> מרחב הסתברות. ויהיו <math>A_1, ..., A_n \in \mathcal A</math> אזי

<math>\begin{align}

\mathbb P\left(A_1 \cap A_2 \cap \ldots \cap A_n\right) &= \mathbb P(A_1) \mathbb P(A_2 \mid A_1) \mathbb P(A_3 \mid A_1 \cap A_2) \cdot \ldots \cdot \mathbb P(A_n \mid A_1 \cap \dots \cap A_{n-1})\\ &= \mathbb P(A_1) \prod_{j=2}^n \mathbb P(A_j \mid A_1 \cap \dots \cap A_{j-1}). \end{align}</math>

הוכחה:

ההוכחה היא באמצעות שימוש ברקורסיה הבאה

<math>

\begin{align} (1) && &\mathbb P(A_1) \mathbb P(A_2 \mid A_1) &=&\qquad \mathbb P(A_1 \cap A_2) \\ (2) && &\mathbb P(A_1) \mathbb P(A_2 \mid A_1) \mathbb P(A_3 \mid A_1 \cap A_2) &=&\qquad \mathbb P(A_1 \cap A_2) \mathbb P(A_3 \mid A_1 \cap A_2) \\ &&&&=&\qquad \mathbb P(A_1 \cap A_2 \cap A_3), \end{align} </math> כאשר בצעד הראשון השתמשנו בהגדרה של הסתברות מותנית.

כלל שרשרת למשתנים מקריים בדידים

שני משתנים מקריים

עבור שני משתנים מקריים בדידים <math>X,Y</math>, נעזר במאורעות <math>A := \{X = x\}</math> ו <math>B := \{Y = y\}</math> ובהגדרה לעיל, למציאת ההתפלגות המשותפת

<math>\mathbb P(X = x,Y = y) = \mathbb P(X = x\mid Y = y) \mathbb P(Y = y),</math>

<math>\mathbb P_{(X,Y)}(x,y) = \mathbb P_{X \mid Y}(x\mid y) \mathbb P_Y(y),</math>

כאשר <math>\mathbb P_X(x) := \mathbb P(X = x)</math> היא התפלגות ההסתברות של <math>X</math> ו <math>\mathbb P_{X \mid Y}(x\mid y)</math> התפלגות ההסתברות המותנית של <math>X</math> בהינתן <math>Y</math> .

משתנים מקריים רבים

יהיו <math>X_1, \ldots, X_n</math> משתנים מקריים ו <math>x_1, \dots, x_n \in \mathbb R</math> . לפי הגדרת ההסתברות המותנית,

<math>\mathbb P\left(X_n=x_n, \ldots, X_1=x_1\right) = \mathbb P\left(X_n=x_n | X_{n-1}=x_{n-1}, \ldots, X_1=x_1\right) \mathbb P\left(X_{n-1}=x_{n-1}, \ldots, X_1=x_1\right)</math>

ובאמצעות כלל השרשרת, שבו סימנו <math>A_k := \{X_k = x_k\}</math>, נוכל למצוא את ההתפלגות המשותפת כ

<math>\begin{align}

\mathbb P\left(X_1 = x_1, \ldots X_n = x_n\right) &= \mathbb P\left(X_1 = x_1 \mid X_2 = x_2, \ldots, X_n = x_n\right) \mathbb P\left(X_2 = x_2, \ldots, X_n = x_n\right) \\ &= \mathbb P(X_1 = x_1) \mathbb P(X_2 = x_2 \mid X_1 = x_1) \mathbb P(X_3 = x_3 \mid X_1 = x_1, X_2 = x_2) \cdot \ldots \\ &\qquad \cdot \mathbb P(X_n = x_n \mid X_1 = x_1, \dots, X_{n-1} = x_{n-1})\\ \end{align}</math>

דוגמה

עבור <math>n=3</math>, כלומר עבור שלושה משתנים אקראיים שנסמן ב <math>X_1,X_2,X_3</math>, יהיה כלל השרשרת

<math>\begin{align}

\mathbb P_{(X_1,X_2,X_3)}(x_1,x_2,x_3) &= \mathbb P(X_1=x_1, X_2 = x_2, X_3 = x_3)\\ &= \mathbb P(X_3=x_3 \mid X_2 = x_2, X_1 = x_1) \mathbb P(X_2 = x_2, X_1 = x_1) \\ &= \mathbb P(X_3=x_3 \mid X_2 = x_2, X_1 = x_1) \mathbb P(X_2 = x_2 \mid X_1 = x_1) \mathbb P(X_1 = x_1) \\ &= \mathbb P_{X_3\mid X_2, X_1}(x_3 \mid x_2, x_1) \mathbb P_{X_2\mid X_1}(x_2 \mid x_1) \mathbb P_{X_1}(x_1). \end{align}</math>

קישורים חיצוניים

• , p. 496.