Chain rule (probability)

For two events $A$ and $B$, the chain rule states that

:$\backslash mathbb\; P(A\; \backslash cap\; B)\; =\; \backslash mathbb\; P(B\; \backslash mid\; A)\; \backslash mathbb\; P(A)$,

where $\backslash mathbb\; P(B\; \backslash mid\; A)$ denotes the conditional probability of $B$ given $A$.

An Urn A has 1 black ball and 2 white balls and another Urn B has 1 black ball and 3 white balls. Suppose we pick an urn at random and then select a ball from that urn. Let event $A$ be choosing the first urn, i.e. $\backslash mathbb\; P(A)\; =\; \backslash mathbb\; P(\backslash overline\{A\})\; =\; 1/2$, where $\backslash overline\; A$ is the complementary event of $A$. Let event $B$ be the chance we choose a white ball. The chance of choosing a white ball, given that we have chosen the first urn, is $\backslash mathbb\; P(B|A)\; =\; 2/3.$ The intersection $A\; \backslash cap\; B$ then describes choosing the first urn and a white ball from it. The probability can be calculated by the chain rule as follows:

:$\backslash mathbb\; P(A\; \backslash cap\; B)\; =\; \backslash mathbb\; P(B\; \backslash mid\; A)\; \backslash mathbb\; P(A)\; =\; \backslash frac\; 23\; \backslash cdot\; \backslash frac\; 12\; =\; \backslash frac\; 13.$

For events $A\_1,\backslash ldots,A\_n$ whose intersection has not probability zero, the chain rule states

:$\backslash 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}

For $n=4$, i.e. four events, the chain rule reads

:$\backslash 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}.

We randomly draw 4 cards (one at a time) without replacement from deck with 52 cards. What is the probability that we have picked 4 aces?

First, we set $A\_n\; :=\; \backslash left\backslash \{\; \backslash text\{draw\; an\; ace\; in\; the\; \}\; n^\{\backslash text\{th\}\}\; \backslash text\{\; try\}\; \backslash right\backslash \}$. Obviously, we get the following probabilities

:$\backslash mathbb\; P(A\_1)\; =\; \backslash 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}.

Applying the chain rule,

:$\backslash mathbb\; P(A\_1\; \backslash cap\; A\_2\; \backslash cap\; A\_3\; \backslash cap\; A\_4)$

= \frac 4{52} \cdot \frac 3{51} \cdot \frac 2{50} \cdot \frac 1{49} = \frac{24}{6497400}.

Let $(\backslash Omega,\; \backslash mathcal\; A,\; \backslash mathbb\; P)$ be a probability space. Recall that the conditional probability of an $A\; \backslash in\; \backslash mathcal\; A$ given $B\; \backslash in\; \backslash mathcal\; A$ is defined as

:$$

\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}

Then we have the following theorem.{{math theorem|name = Chain rule| Let $(\backslash Omega,\; \backslash mathcal\; A,\; \backslash mathbb\; P)$ be a probability space. Let $A\_1,\; ...,\; A\_n\; \backslash in\; \backslash mathcal\; A$. Then

:$\backslash 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 proof|The formula follows immediately by recursion

:$$

\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}

where we used the definition of the conditional probability in the first step.}}

For two discrete random variables $X,Y$, we use the events$A\; :=\; \backslash \{X\; =\; x\backslash \}$ and $B\; :=\; \backslash \{Y\; =\; y\backslash \}$ in the definition above, and find the joint distribution as

:$\backslash mathbb\; P(X\; =\; x,Y\; =\; y)\; =\; \backslash mathbb\; P(X\; =\; x\backslash mid\; Y\; =\; y)\; \backslash mathbb\; P(Y\; =\; y),$

or

:$\backslash mathbb\; P\_\{(X,Y)\}(x,y)\; =\; \backslash mathbb\; P\_\{X\; \backslash mid\; Y\}(x\backslash mid\; y)\; \backslash mathbb\; P\_Y(y),$

where $\backslash mathbb\; P\_X(x)\; :=\; \backslash mathbb\; P(X\; =\; x)$ is the probability distribution of $X$ and $\backslash mathbb\; P\_\{X\; \backslash mid\; Y\}(x\backslash mid\; y)$ conditional probability distribution of $X$ given $Y$.

Let $X\_1,\; \backslash ldots\; ,\; X\_n$ be random variables and $x\_1,\; \backslash dots,\; x\_n\; \backslash in\; \backslash mathbb\; R$. By the definition of the conditional probability,

:$\backslash mathbb\; P\backslash left(X\_n=x\_n,\; \backslash ldots\; ,\; X\_1=x\_1\backslash right)\; =\; \backslash mathbb\; P\backslash left(X\_n=x\_n\; |\; X\_\{n-1\}=x\_\{n-1\},\; \backslash ldots\; ,\; X\_1=x\_1\backslash right)\; \backslash mathbb\; P\backslash left(X\_\{n-1\}=x\_\{n-1\},\; \backslash ldots\; ,\; X\_1=x\_1\backslash right)$

and using the chain rule, where we set $A\_k\; :=\; \backslash \{X\_k\; =\; x\_k\backslash \}$, we can find the joint distribution as

:$\backslash 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}

For $n=3$, i.e. considering three random variables. Then, the chain rule reads

:$\backslash 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}

• {{citation|author=René L. Schilling|date=2021|edition=1|isbn=979-8-5991-0488-9|location=Technische Universität Dresden, Germany|title=Measure, Integral, Probability & Processes - Probab(ilistical)ly the Theoretical Minimum}}
• {{citation|author=William Feller|date=1968|edition=3|isbn=978-0-471-25708-0|location=New York / London / Sydney|publisher=Wiley|title=An Introduction to Probability Theory and Its Applications|volume=I}}
• {{Russell Norvig 2003}}, p. 496.

{{reflist}}

Category:Bayesian inference

Category:Bayesian statistics

Category:Mathematical identities

Category:Probability theory