Probability Trees and the Chain Rule, introduction to probability lesson

A bag holds five red tokens and three blue tokens, and two tokens are drawn one after the other without replacement. What is the probability that both are red? The chance of red on the second draw depends on what the first draw removed, so the calculation has to keep track of what happened first. A probability tree records every history together with the probabilities that apply after it. This lesson builds such trees, derives the chain rule that multiplies along their paths, and shows how adding complete paths gives the probability of an event.

Key terms

Probability tree

Definition A probability tree describes an experiment carried out in stages. Each node stands for a history, the outcomes of the stages so far, starting from the root before the first stage. The branches leaving a node list the possible outcomes of the next stage, which must be disjoint and exhaustive. When the history at a node has positive probability, each branch leaving it carries the probability of its outcome given that history.

In plain words The tree is a map of the experiment, read from the root outward. Every fork asks what can happen next and how likely each possibility is from that point on.

Example For the bag above, write $R_k$ and $B_k$ for a red or a blue token on draw $k$ . The root splits into $R_1$ with probability $\tfrac58$ and $B_1$ with probability $\tfrac38$ . After $R_1$ the bag holds four red and three blue tokens, and after $B_1$ it holds five red and two blue, so each of these two nodes splits again into red and blue with its own probabilities.

Conditional branch

Definition A branch from a node with history $H$ , where $P(H) > 0$ , to an outcome $C$ of the next stage carries the conditional probability $P(C \mid H)$ . The branches from the root carry unconditional probabilities. Branches with the same outcome can carry different probabilities at different nodes, because their histories differ.

In plain words A branch label answers one question. How likely is this next step, given everything that has already happened on the way to this node?

Example In the token tree the second-draw branches are

\begin{aligned} P(R_2 \mid R_1) &= \frac47, \\[0.4em] P(B_2 \mid R_1) &= \frac37, \\[0.4em] P(R_2 \mid B_1) &= \frac57, \\[0.4em] P(B_2 \mid B_1) &= \frac27. \end{aligned}

Labeling both second-draw forks with $\tfrac58$ for red and $\tfrac38$ for blue would describe a different experiment, such as returning the first token to the bag before the second draw.

Multiplication rule

Definition For events $A$ and $B$ with $P(A) > 0$ , multiplying the definition $P(B \mid A) = P(A \cap B)/P(A)$ through by $P(A)$ gives

P(A \cap B) = P(A)P(B \mid A).

The rule does not need independence. If $A$ and $B$ happen to be independent, then $P(B \mid A) = P(B)$ and the rule becomes the product $P(A)\,P(B)$ . If $P(A) = 0$ , then $P(A \cap B) = 0$ as well, and no conditional probability is needed.

In plain words The chance that both things happen is the chance of the first, times the chance of the second once the first has happened.

Example Both tokens are red with probability

P(R_1 \cap R_2) = \frac58 \cdot \frac47 = \frac{5}{14}.

If instead each token is returned before the next draw and the draws are modeled as independent, the same path has probability $\left(\tfrac58\right)^2 = \tfrac{25}{64}$ . The answers differ because the experiments differ.

Chain rule

Definition Let $A_1, \dots, A_n$ be events. Write $H_k = A_1 \cap \cdots \cap A_k$ for the history after $k$ stages and $H_0 = \Omega$ , and suppose $P(H_{n-1}) > 0$ . Then

P(H_n) = \prod_{k=1}^{n} P(A_k \mid H_{k-1}),

where the first factor is $P(A_1 \mid \Omega) = P(A_1)$ . Every conditioning event has positive probability, since $H_0 \supseteq H_1 \supseteq \cdots \supseteq H_{n-1}$ . The rule follows from the multiplication rule $P(H_k) = P(H_{k-1})\,P(A_k \mid H_{k-1})$ , applied for each $k$ from $1$ to $n$ and started from $P(H_0) = 1$ . For three events it reads

\begin{aligned} &P(A \cap B \cap C) \\[0.4em] &\quad = P(A)\,P(B \mid A) \\[0.4em] &\qquad \times P(C \mid A \cap B). \end{aligned}

If some history $H_k$ has probability $0$ , then $P(H_n) = 0$ because $H_n \subseteq H_k$ , and the later factors are not needed.

In plain words Along a path, multiply the probability of reaching each history by the probability of the next step from there. Each factor conditions on the whole history before it, not only on the previous stage.

Example Draw a third token without replacement. The path red, red, blue passes through the history $R_1 \cap R_2$ , after which three red and three blue tokens remain. So

\begin{aligned} &P(R_1 \cap R_2 \cap B_3) \\[0.4em] &\quad = \frac58 \cdot \frac47 \cdot \frac36 = \frac{5}{28}. \end{aligned}

Terminal path

Definition A terminal path runs from the root to a leaf and records one complete history of the experiment. By the chain rule, its probability is the product of the branch probabilities along it. A path that reaches a history of probability $0$ has probability $0$ , and the product can stop there. Different terminal paths are disjoint events, and together they cover every possible history. So the probability of any event described by the stages is the sum of the probabilities of the terminal paths that make up the event.

In plain words Multiply along a path, then add across the paths that make up the event. Added paths have to be disjoint, and distinct complete paths always are.

Example Write $RB$ for red and then blue, and so on. The four terminal paths of the two-draw tree have probabilities

\begin{gathered} P(RR) = \frac{20}{56}, \quad P(RB) = \frac{15}{56}, \\[0.4em] P(BR) = \frac{15}{56}, \quad P(BB) = \frac{6}{56}. \end{gathered}

Exactly one red token means $RB$ or $BR$ , with probability $\tfrac{30}{56} = \tfrac{15}{28}$ . A red second token means $RR$ or $BR$ , with probability $\tfrac{35}{56} = \tfrac58$ . That equals the red share of the full bag, yet the draws are dependent, since $P(R_2 \mid R_1) = \tfrac47$ while $P(R_2 \mid B_1) = \tfrac57$ . With replacement and independent draws, exactly one red would instead have probability $2 \cdot \tfrac58 \cdot \tfrac38 = \tfrac{15}{32}$ .

Branch normalization

Definition At every node whose history $H$ has $P(H) > 0$ , the outcomes $C_1, \dots, C_m$ of the next stage are disjoint and exhaustive, so the branch probabilities are nonnegative and satisfy

\sum_{j=1}^{m} P(C_j \mid H) = 1.

As a consequence, the probabilities of all terminal paths add to $1$ . A history with probability $0$ needs no branch labels after it, since every path through it has probability $0$ .

In plain words Each fork hands out all of its probability, no more and no less. Checking each fork is a local check on every conditional choice, and checking that the leaves add to $1$ is a global check on the whole model.

Example The three forks of the token tree give $\tfrac58 + \tfrac38 = 1$ , $\tfrac47 + \tfrac37 = 1$ and $\tfrac57 + \tfrac27 = 1$ , and the leaves give $\tfrac{20 + 15 + 15 + 6}{56} = 1$ . A common slip is to label the fork after $R_1$ with $\tfrac48$ and $\tfrac38$ , forgetting that only seven tokens remain. Those labels add to $\tfrac78$ , and the fork check catches the mistake at once.

Check yourself

A box holds three working fuses and two faulty ones. Two fuses are drawn without replacement. Find the probability that both are faulty and the probability that at least one works.

Show the answer

The first fuse is faulty with probability $\tfrac25$ . Given that, one faulty fuse remains among four, so the second is faulty with probability $\tfrac14$ . Both are faulty with probability

\frac25 \cdot \frac14 = \frac{1}{10}.

The event “at least one works” contains every terminal path except faulty, faulty, so its probability is $1 - \tfrac{1}{10} = \tfrac{9}{10}$ .

A bag holds four green tokens and two orange tokens. Three are drawn without replacement. Find the probability of exactly two green tokens, and check the answer with combinations.

Show the answer

The successful terminal paths are $GGO$ , $GOG$ and $OGG$ . Updating the bag along each path gives

\begin{aligned} P(GGO) &= \tfrac46 \cdot \tfrac35 \cdot \tfrac24 = \tfrac15, \\[0.4em] P(GOG) &= \tfrac46 \cdot \tfrac25 \cdot \tfrac34 = \tfrac15, \\[0.4em] P(OGG) &= \tfrac26 \cdot \tfrac45 \cdot \tfrac34 = \tfrac15. \end{aligned}

The paths are disjoint, so the probability is $\tfrac35$ . Counting unordered selections instead, all three-token subsets are equally likely, and the favorable ones contain two of the four green tokens and one of the two orange ones,

\frac{\binom42 \binom21}{\binom63} = \frac{6 \cdot 2}{20} = \frac35.

The tree counts ordered histories and the combinations count unordered subsets, and the two models agree once order is ignored.

For the same bag and three draws, a classmate argues that each draw is orange with probability $\tfrac13$ , so at least one orange token appears with probability $\tfrac13 + \tfrac13 + \tfrac13 = 1$ . Find the mistake and the correct probability.

Show the answer

Each draw on its own is indeed orange with probability $\tfrac13$ . The mistake is adding events that are not disjoint. The path $OOG$ , for example, has orange on both the first and the second draw, so it is counted twice in the sum. The complement of “at least one orange” is the single terminal path $GGG$ , with probability

\frac46 \cdot \frac35 \cdot \frac24 = \frac15.

So at least one orange token appears with probability $1 - \tfrac15 = \tfrac45$ , not $1$ .

Probability Trees and the Chain Rule

Key terms

Probability tree

Conditional branch

Multiplication rule

Chain rule

Terminal path

Branch normalization

Check yourself

How this lesson connects

Builds on

Used later in