View source for Chain rule (probability)

{{Short description|Probability theory concept}}
{{distinguish|text=the [[chain rule]] in calculus}}
In [[probability theory]], the '''chain rule'''<ref>{{cite book|first=René L.|last=Schilling|title=Measure, Integral, Probability & Processes - Probab(ilistical)ly the Theoretical Minimum |location=Technische Universität Dresden, Germany |year=2021|isbn=979-8-5991-0488-9|page=136ff}}</ref> (also called the '''general product rule'''<ref>{{cite book|first=David A.|last=Schum|title=The Evidential Foundations of Probabilistic Reasoning|year=1994|publisher=Northwestern University Press|isbn=978-0-8101-1821-8|page=49}}</ref><ref>{{cite book|first=Henry E.|last=Klugh|title=Statistics: The Essentials for Research|year=2013|publisher=Psychology Press|isbn=978-1-134-92862-0|page=149|edition=3rd}}</ref>) describes how to calculate the probability of the intersection of, not necessarily [[Independence (probability theory)|independent]], events or the [[joint distribution]] of [[random variables]] respectively, using [[conditional probabilities]]. This rule allows one to express a joint probability in terms of only conditional probabilities.<ref>{{Cite web |last=Virtue |first=Pat |title=10-606: Mathematical Foundations for Machine Learning |url=https://www.cs.cmu.edu/~10606-f21/recitations/10606_Fa21_Recitation_4_worksheet_solutions.pdf}}</ref> The rule is notably used in the context of discrete [[Stochastic process|stochastic processes]] and in applications, e.g. the study of [[Bayesian network]]s, which describe a [[probability distribution]] in terms of conditional probabilities.

==Chain rule for events==
===Two events===
For two [[Event (probability theory)|events]] <math>A</math> and <math>B</math>, the chain rule states that

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

where <math>\mathbb P(B \mid A)</math> denotes the [[conditional probabilities|conditional probability]] of <math>B</math> given <math>A</math>.

====Example====
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 <math>A</math> be choosing the first urn, i.e. <math>\mathbb P(A) = \mathbb P(\overline{A}) = 1/2</math>, where <math>\overline A</math> is the [[complementary event]] of <math>A</math>. Let event <math>B</math> be the chance we choose a white ball. The chance of choosing a white ball, given that we have chosen the first urn, is <math>\mathbb P(B|A) = 2/3.</math> The intersection <math>A \cap B</math> then describes choosing the first urn and a white ball from it. The probability can be calculated by the chain rule as follows:

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

===Finitely many events===
For events <math>A_1,\ldots,A_n</math> whose intersection has not probability zero, the chain rule states

:<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>

====Example 1====
For <math>n=4</math>, i.e. four events, the chain rule reads

:<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>.

==== Example 2 ====
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 <math display="inline">A_n := \left\{ \text{draw an ace in the } n^{\text{th}} \text{ try} \right\}</math>. Obviously, we get the following probabilities

:<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>.

Applying the chain rule,

:<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} = \frac{24}{6497400}</math>.

=== Statement of the theorem and proof ===
Let <math>(\Omega, \mathcal A, \mathbb P)</math> be a probability space. Recall that the [[conditional probability]] of an <math>A \in \mathcal A</math> given <math>B \in \mathcal A</math> is defined as 

:<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>
Then we have the following theorem.{{math theorem|name = Chain rule| Let <math>(\Omega, \mathcal A, \mathbb P)</math> be a probability space. Let <math>A_1, ..., A_n \in \mathcal A</math>. Then

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

:<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>
where we used the definition of the conditional probability in the first step.}}

==Chain rule for discrete random variables==
===Two random variables===
For two discrete random variables <math>X,Y</math>, we use the events<math>A := \{X = x\}</math> and <math>B := \{Y = y\}</math> in the definition above, and find the joint distribution as

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

or 

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

where <math>\mathbb P_X(x) := \mathbb P(X = x)</math> is the [[probability distribution]] of <math>X</math> and <math>\mathbb P_{X \mid Y}(x\mid y)</math> [[conditional probability distribution]] of <math>X</math> given <math>Y</math>.

===Finitely many random variables===
Let <math>X_1, \ldots , X_n</math> be random variables and <math>x_1, \dots, x_n \in \mathbb R</math>. By the definition of the conditional probability,

:<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>

and using the chain rule, where we set <math>A_k := \{X_k = x_k\}</math>, we can find the joint distribution as

:<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>

===Example===
For <math>n=3</math>, i.e. considering three random variables. Then, the chain rule reads

:<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>

==Bibliography==
* {{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}}<!-- auto-translated by Module:CS1 translator -->
* {{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}}<!-- auto-translated by Module:CS1 translator -->
* {{Russell Norvig 2003}}, p. 496.

==References==
{{reflist}}

[[Category:Bayesian inference]]
[[Category:Bayesian statistics]]
[[Category:Mathematical identities]]
[[Category:Probability theory]]