3 Conditional Probability & Independence

3.1 Conditional Probability

Suppose we have two events E, F. It is reasonable to ask;
How likely is it for E to occur if we know that F has already occurred?

Example 3.1. You roll two dice, one after the other. The sample space may therefore be taken to be
S = {( x, y) : 1 ≤ x, y ≤ 6}. Let E, F be the events

• E = {( x, y) : x + y ≥ 9} = {(3, 6), (4, 5), . . . , (6, 6)} “the sum of the values is at least nine.

• F = {(5, y), ( x, 5) : 1 ≤ x, y ≤ 6} = “one of the dice is a five.

By simple counting, we have

4+3+2+1 10 5 11
P( E ) = = = , P( F ) =
36 36 18 36
Suppose you roll the dice; one lands out of sight but the visible die is a five: what is the probability
that the sum is at least nine? For this new experiment, the set of possible outcomes (the sample space!)
is now F, and we need only count how many of these have a sum of at least nine; we therefore want
the event

E ∩ F = {(5, 4), (5, 5), (5, 6), (4, 5), (6, 5)}
| E∩ F | 5
The required probability is therefore | F|
= 11 .

In general we make this a definition: the idea is that the probability of E happening given F, is the
probability of both events happening relative to that of F itself.

Definition 3.2. Suppose E, F are events and that P( F ) ̸= 0. The conditional probability that E occurs
given that F has already occurred (‘the probability of E given F’) is

P( E ∩ F )
P( E | F ) =
P( F )

To revisit the example in this language, P( E| F ) = = 115

. 5/36
11/36
The other conditional probability represents the chance that one of the dice is a five given that the
sum is at least nine: this would be
P( E ∩ F ) 5/36 1
P( F | E ) = = =
P( E ) 10/36 2

As in the example, when S is a finite set all of whose singleton outcomes are equally likely, this
approach should seem intuitive. We simply view F as a new sample space and count how many
times the event E ∩ F occurs relative to this new sample space:
|E ∩ F| | E ∩ F | |S| P( E ∩ F )
P( E | F ) = = · =
| F| |S| | F| P( F )

1
More generally, recall that we tend to interpret the probability P( F ) as being the (approximate) pro-
portion of times F occurs if we run the experiment a very large number n of times:

number of times F occurs in n trials

P( F ) ≈
n
Over n trials, it follows that

P( E ∩ F ) number of times both E and F occur

P( E | F ) = ≈
P( F ) number of times F occurs

The intuition is that this approximation should become an equality as n → ∞. Before proceeding to
examples, there is one other obvious thing to check.
P( E ∩ F )
Theorem 3.3. Let F be an event in the sample space S. If P( F ) ̸= 0, then P( E| F ) = P( F )
defines a
probability measure on S. More specifically, it satisfies the axioms of probability:

1. 0 ≤ P( E| F ) ≤ 1,

2. P(S| F ) = 1,

3. If E1 , E2 , . . . are mutually exclusive, then P( Ei | F ) = ∑ P( Ei | F )

S

Proof. 1. Since F = ( E ∪ EC ) ∩ F = ( E ∩ F ) ∪ ( EC ∩ F ) is a union of mutually exclusive events,

P( E ∩ F )
P( F ) = P( E ∩ F ) + P( EC ∩ F ) ≥ P( E ∩ F ) =⇒ ≤1
P( F )

P( S ∩ F ) P( F )
2. P(S| F ) = = = 1.
P( F ) P( F )
3. This follows from the distributive law
[  [
Ei ∩ F = ( Ei ∩ F )

If the E I are mutually exclusive, so plainly are the events Ei ∩ F. But then

P( ( Ei ∩ F )) P( Ei ∩ F )
S
P( ∑ ∑ P(Ei | F)
[
Ei | F ) = = =
P( F ) P( F )
Example 3.4. A student estimates that she has a 50% chance of getting an A in Ordinary Differential
Equations (ODE), a 40% chance in geometry and a 30% chance of getting an A in both.

1. If the student receives an A in geometry, what is the probability that she will also do so in ODE?
Let O, G be, respectively, the events that the student receives an A in ODE and geometry. We
therefore want
P(O ∩ G ) 0.3
P(O| G ) = = = 75%
P( G ) 0.4

2
 2. The student decides to take only one of the classes and decides which by a coin flip. What is
the probability that she gets an A in geometry?
This time let E be the event that the student chooses geometry and A that the student gets an A
in whichever class she chooses. This time we require

1 4
P( E ∩ A ) = P( E )P( A | E ) = · = 20%
2 10
This last illustrates a general rule for conditional probabilities:

Theorem 3.5 (Multiplication Rule). Given events Ei with P( E1 ) ̸= 0, we have

P( E1 ∩ E2 ) = P( E1 )P( E2 | E1 )

More generally, if P( E1 ∩ · · · ∩ En−1 ) ̸= 0, then1

P( E1 ∩ · · · ∩ En ) = P( E1 ) P( E2 | E1 ) P( E3 | E1 ∩ E2 ) · · · P( En | E1 ∩ · · · ∩ En−1 )

The general formula is easily checked by multiplying out the right hand side and cancelling:
P( E1 ∩ E2 ) P( E1 ∩ E2 ∩ E3 ) P( E1 ∩ · · · ∩ En )
P( E1 ∩ · · · ∩ En ) = P( E1 ) · · ···
P( E1 ) P( E1 ∩ E2 ) P( E1 ∩ · · · ∩ En−1 )
The multiplication rule makes for an intuitive method of calculation which feels akin to the funda-
mental principle of counting.

Examples 3.6. 1. You estimate your chance of shooting an unpressured basket at 90%. You enter
a competition where the goal is to shoot 5 baskets in a row. Due to nerves, your chance of
shooting a basket is reduced by 10% for each previous successful shot. What is the probability
that you win the competition?
Let E1 , . . . , E5 be the events “shoot the ith basket.” We therefore want
P( E1 ∩ · · · ∩ E5 ) = P( E1 ) P( E2 | E1 ) P( E3 | E1 ∩ E2 ) · · · P( E5 | E1 ∩ E2 ∩ E3 ∩ E4 )
9 8 7 6 5 15120
= · · · · = = 15.12%
10 10 10 10 10 100000
2. Recall the hat-matching problem with n participants. We use the multiplication rule to obtain
the probability that exactly k people match their own hat.
To keep ourselves straight, here are all 24 = 4! equally likely arrangements of hats a, b, c, d for
n = 4 people A, B, C, D; we group these according to all the ways that 4, 2, 1 or no people claim
their own hat (note that if three claim their own hat, the fourth must also!).
A a a a a d c b a a d c d b c b b c d b c d b c d
B b b d c b b a c d b b a d a c a a a d d c c d c
C c d c b c a c d b a d c c b a d d b a a a d b b
D d c b d a d d b c c a b a d d c b c c b b a a a
1 You may prefer the look of this expression if you use the convention of juxtaposition for intersection; i.e.
P( E1 · · · En ) = P( E1 ) P( E2 | E1 ) P( E3 | E1 E2 ) · · · P( En | E1 · · · En−1 )

3
 Consider the events E1 , . . . , En where Ei is the event of the ith person claims their own hat.
Plainly
1 1 1
P( E1 ) = , P( E2 | E1 ) = , P( E3 | E1 ∩ E2 ) = ,...
n n−1 n−2
from which
1 (n − k)!
P( E1 ∩ · · · ∩ Ek ) = = (∗)
n ( n − 1) . . . ( n + 1 − k ) n!
In the context of the concrete example:
• P( E1 ) = 1
= 24
4
6
corresponds to the six a’s in the 1st row.
• P( E2 | E1 ) = 31 = 26 corresponds to the two b’s underneath the six a’s in columns 1 & 2.
• P( E3 | E1 ∩ E2 ) = 21 corresponds to the single c in column 1.
• P( E4 | E1 ∩ E2 ∩ E3 ) = 1 corresponds to the single d in column 1.
At this point,a given that the first k people have their own hat, our earlier discussion tells us that
n−k
(−1) j
the probability of none of the remaining n − k people getting their own hat is ∑ j! . The
j =0
probability that exactly the first k people getting their own hat is therefore
! ! !
k n k n k
(n − k)! n−k (−1) j
P Ei = P
C
Ei P C
∑ j!
\ \ \ \ \
Ei ∩ Ei Ei =
i =1 i = k +1 i =1 i = k +1 i =1
n! j =0

Since there are (nk) subsets of size k, the probability that exactly k people claim their own hat is

n (n − k )! n−k (−1) j 1 n−k (−1) j

 
P(Exactly k claim own hat) =
k n! ∑ j! =
k! j∑ j!
j =0 =0
∞
e −1
As previously, note that this converges to k! as n → ∞, in line with the fact that ∑ 1
k! = e.
k =0
Again, we verify that this matches our complete data when n = 4:
4
1 (−1) j 1 1 1 9
• P( k = 0) =
0! ∑ j!
= 1−1+ − +
2 6 24
=
24
j =0
3
(−1) j
1 1 1 1 8
• P( k = 1) =
j!
1! ∑
= 1−1+ − = =
2 6 3 24
j =0

1 2 (−1) j
 
1 1 1 6
• P( k = 2) = ∑
2! j=0 j!
=
2
1−1+
2
= =
4 24
1
1 (−1) j 1
• P( k = 3) =
3! ∑ j! = 6 (1 − 1) = 0
j =0
0
1 (−1) j 1
• P( k = 4) =
4! ∑ j! = 24
j =0
a It is really tempting to continue the process via
P( EkC+1 | E1 ∩ · · · ∩ Ek ) = n− k −1
n−k , . . .
We leave it to the exercises to explain why this doesn’t work!

4
3.2 Bayes’ Formula
Recall that complementary events are mutually exclusive F ∩ FC = ∅. If follows that we may decom-
pose any event E into mutually exclusive events dependent on the occurrence or non-occurrence of F:
E = ( E ∩ F ) ∪ ( E ∩ FC ). This should be entirely intuitive.

Example 3.7. Let E be the event “Get an A overall in analysis,” and F the event “Score 40/50 on the
midterm.” We plainly have two mutually exclusive events which correspond to all possible ways to
obtain an A:

• E ∩ F “Get an A overall and score 40/50 on the midterm”

• E ∩ FC “Get an A overall and score < 40 on the midterm”

Suppose that P( F ) = 20% of students score ≥ 40 on the midterm. Moreover, suppose that an overall
A is obtained by

• P( E| F ) = 75% of students who get ≥ 40 on the midterm,

• P E| FC = 15% of students who get < 40 on the midterm.

These are conditional probabilities, whence we can use the multiplication rule to obtain the probabil-
ity of a student obtaining an overall A

P( E ) = P( E ∩ F ) + P( E ∩ F C ) (mutually exclusive events)

= P( F )P( E | F ) + P( F )P( E | F )
C C
(multiplication rule (twice))
= P( F )P( E | F ) + 1 − P( F ) P E | F C (complementary events F, FC )

1 3 4 3 15 + 12
= · + · = = 27%
5 4 5 20 100
Now suppose a student gets an overall A in the course. What is the probability that they scored at
least 40 on the midterm?
We use the multiplication rule again to compute
1 3
P( E ∩ F ) P( F )P( E | F ) · 5
P( F | E ) = = = 5 4
= ≈ 55.5%
P( E ) P( E ) 27
100
9

This approaches are completely general:

Theorem 3.8 (Bayes’ Theorem). If E, F are any events for which the conditional probabilities make
sense, then

1. (Law of total probability) P( E) = P( F )P( E| F ) + 1 − P( F ) P E| FC

P( F )P( E | F )
2. (Bayes’ formula) P( F | E) =
P( E )

Bayes’ formula permits us to switch the order of conditional probabilities. Take extra care with this,
since answers are often counter-intuitive, particularly when data is socially loaded and biases come
in to play.

5
Example 3.9. Suppose we have the following data:

• 1% of a population is a millionaire.

• 80% of millionaires drive a luxury car.

• 20% of the entire population drives a luxury car.

If you see a luxury car, what is the probability that the driver is a millionaire?
The gut interpretation is that it is very likely, since such a large majority of millionaires drive a luxury
car. This is to get the implication the wrong way round: if E, F are, respectively, the events “person is
a millionaire” and “person drives a luxury car,” then the probability we want is

P( E )P( F | E ) 0.01 · 0.8

P( E | F ) = = = 4%
P( F ) 0.2

This is still small, since the proportion of millionaires in the overall population is also small.

Problems such as this are very common in medical situations. Suppose a patient is tested for a
particular medical condition. Consider two events:
• C “The patient has the condition”
• T “The patient tests positive.”
If a patient is tested, there are four possible mutually exclusive events, sometimes given names
C ∩ T C ∩ TC true positive false negative
CC ∩ T CC ∩ T C false positive true negative
If a patient takes a test and it comes back positive, they want to know how likely it is that they have
the condition. The important values are the following:
• P( T |C ) (Sensitivity): if a patient has condition, how likely are they to test positive?
• P( T C |CC ) (Specificity): if a patient hasn’t got the condition, how likely are they to test negative?

Example 3.10. A person tests positive for a disease which is known to be present in 1% of the
population. If the test correctly detects 90% of cases and 91% of negatives, how likelya is it that the
person has the disease?
We know P(C ) = 1%, P( T |C ) = 90%, and P( T C |CC ) = 91% and wish to compute
P( C ∩ T ) P( C )P( T | C )
P( C | T ) = =
P( T ) P( T | C )P( C ) + P( T | C C )P( C C )
P( C )P( T | C )
=
P( T |C )P(C ) + (1 − P( T C |CC ))(1 − P(C ))
1 · 90 90 10
= = = ≈ 9.17%
90 · 1 + 9 · 99 981 109
where we used the fact was written using percentages.
a See [Link] for how this exact problem is routinely misunderstood by

experts who should know better!

6
Conditioning on Mutually Exclusive Events
Both parts of Theorem 3.8 extend naturally to finitely many events:
n
S
Corollary 3.11. Suppose the sample space is a union of mutually exclusive events S = Fi .
i =1
1. (Law of total probability) The probability of an event E is a weighted average of the probabil-
ities that E occurs given each of the mutually exclusive events Fi :
!
n n n
P( E ) = P ∑ P(E ∩ Fi ) = ∑ P(E| Fi )P( Fi )
[
E ∩ Fi =
i =1 i =1 i =1

This method of computation is known as conditioning on the events Fi .

P( E ∩ Fj ) P( E| Fj )P( Fj )
2. (Bayes’ formula) P( Fj | E) = = n
P( E ) ∑i=1 P( E| Fi )P( Fi )

The special case of the Theorem was where S = F ∪ FC ; i.e. F2 = F1C .

Examples 3.12. 1. A bin contains three types of flashlight: types I, II, III. Suppose the following
data is known regarding these lights.
Type Number in bin chance of lasting at least 24 hours
I 50 60%
II 100 70%
III 25 90%

(a) What is the probability that a randomly chosen flashlight lasts at least 24 hours?
Let E be “the chosen light lasts at least 24 hours.” We condition on the three mutually
exclusive events Fi “choose a flashlight of type i.”
P( E) = P( E| FI )P( FI ) + P( E| FII )P( FII ) + P( E| FIII )P( FIII )
6 2 7 4 9 1 7
= · + · + · = = 70%
10 7 10 7 10 7 10
(b) If a randomly chosen flashlight lasts at least 24 hours, we find the probability that it was a
flashlight of each type. For each j,

10 12 12
P( Fj )P( E| Fj )  7 · 70 = 49 ≈ 24.5% for type I

P( Fj | E) = = 10 28 28
7 · 70 = 49 ≈ 57.1% for type II
P( E ) 
 10 9 9
7 · 70 = 49 ≈ 18.4% for type III
Note that the three conditional probabilities sum to 1, as they must!
(c) Suppose the chosen flashlight does not last 24 hours. Find the probability that the choice
was not type I. This time we want
P( F1 )P( EC | F1 ) P( F1 )(1 − P( E| F1 ))
P( F1C | EC ) = 1 − P( F1 | EC ) = 1 − = 1−
P( EC ) 1 − P( E )
42
· 10
7 13
= 1− = ≈ 61.9%
3/10 21

7
 2. Recall the example of the problem of points from the introduction, where player A is 3–2 up in a
first-to-five coin flip. If the game continues until someone wins, the outcome tree is as follows.

A 65−2 A 65−3 A 65−4

B / 4−3 B / 4−4 B / 4−5
A 64−2

3−2 65−3 A 65−4

B A
(
3−3
A / 4−3 B / 4−4 B / 4−5
B
(
3−4
A / 4−4 A / 5−4
B B
( (
3−5 4−5

Rememeber that the probability of any particular scoreline depends on which column it lies in;
each time you move one column to the right, the outcomes become half as likely.
Our approach in the introduction was essentially to use conditional probabilities. Here it is a
little more formally. Let Fn be the event “the game finishes in n coin flips”. The possible finishes
are scored. Since the outcome of each coin-flip is equally likely, we easily count the probabilities
of the mutually exclusive events

1 1 3 3 6 3
P( F7 ) = 2
= , P( F8 ) = 3
= , P( F9 ) = 4
=
2 4 2 8 2 8
Let E be the event “Player A wins.” Conditioning on the events Fi , we obtain

P( E) = P( E| F7 )P( F7 ) + P( E| F8 )P( F8 ) + P( E| F9 )P( F9 )

1 2 3 3 3 1 1 3 11
= 1· + · + · = + + =
4 3 8 6 8 4 4 16 16
This isn’t the best way to solve the problem since finding these ingredients becomes much
harder for longer games. Recall that we solved the problem in a different way in chapter 2.

This last example also illustrates a commonly used concept.

P( E ) P( E )
Definition 3.13. The odds of an event E occurring are =
P( E )
C 1 − P( E )

In the previous example, the odds of player A winning are 11 5 . The odds might instead be written
11 : 5 and read “11 to 5,” encapsulating the idea that if the game were repeated 16 = 11 + 5 times,
player A would expect to win 11 times and lose 5 times.
We finish this section with an example of how the odds change on receipt of new information. This
is another straightforward application of Bayes’ formula:
P( E | F ) P( F | E )P( E ) P( F ) P( E ) P( F | E )
= · = ·
P( E | F )
C P( F ) P( F | E )P( E )
C C P( EC ) P( F | EC )
If a new event F occurs, the odds change by multiplication by the relative chance of F occurring given
E and its complement.

8
 P( E )
Example 3.12.1 (cont) The odds that a drawn flashlight lasts 24 hours are P(EC ) = 73 . Now suppose
we know that the chosen light is not of type I. This new information increases the odds

P( E| FIC ) P( E) P( FIC | E) P( E) P( FII | E) + P( FIII | E)

= · = ·
P( EC | FI )
C P( E ) P( FI | EC )
C C P( EC ) P( FIC | EC )
7 40/49 7 120 40
= · = · =
3 13/21 3 91 13
which makes sense, since the type I flashlights are the least likely to last a full 24 hours.
Warning! Gambling Odds In the real world, probabilities are often quoted in odds but written
backwards relative to the mathematical definition. Colloquially, a “million to one” event E occurs once
for every million times it does not; that is

P( E ) 1 1
= ⇐⇒ P( E) =
1 − P( E ) 1000000 1000001

This approach is especially prevalent in gambling, for instance,

The grey horse has odds of 5–2 (or 5/2)

Quoting odds this way helps punters understand what they really care about: winnings (profit). If
you risk $2 on a 5–2 horse and it wins, you’ll get back your $2 stake plus winnings of $5.
To unpack this, imagine the race were run 7 = 5 + 2 times, then the grey horse would be expected to
win twice. The probability p of the grey horse winning therefore satisfies

p 2 2
= ⇐⇒ 5p = 2 − 2p ⇐⇒ p =
1− p 5 7

The expected outcome of betting $2 on this race seven times would be therefore be net zero:

• Lose five times for a total loss of −$10.

• Win twice for a total profit of $10.

Alternatively, we can view the problem symmetrically. You put $2 in the pot and the bookmaker
$5; if the grey horse wins, you take the $7 pot; if it loses, the bookmaker takes the $7. Each of you
risked different amounts and had different potential winnings. Indeed the bookmaker’s odds were
precisely the opposite at 2–5.

9
3.3 Independent events
It is sometimes the case that new information does not change a probability; that P( E| F ) = P( E).
This immediately implies P( E ∩ F ) = P( E)P( F ). We make the latter our definition.

Definition 3.14. Events E, F are independent if P( E ∩ F ) = P( E)P( F ), and dependent otherwise.

More generally, a collection of events En is independent if every finite subcollection satisfies

P( En1 ∩ · · · ∩ Enk ) = P( En1 ) · · · P( Enk )

If an experiment is consists of n independent identical subexperiments, then we call each subexperi-

ment a trial.

Examples 3.15. 1. The events E “roll a 4 on a fair die” and F “roll an even number” are dependent
since P( E| F ) = 13 ̸= 61 = P( E). Equivalently P( E ∩ F ) = P( E) = 16 ̸= 18
1
= P( E )P( F )
2. Let K, C be the events “deal a King” and “deal a club” from a shuffled pack of cards. These
events are independent since
1 4 1
P( K ∩ C ) = = · = P( K )P( C )
52 52 4
3. Suppose we roll a fair die three times. Since a die has no memory, each roll is a separate
experiment. Any events which concern only the values on separate dice are therefore in-
dependent. Consider the events Eij ; “the ith die roll is a j”. If the sample space is the set
S = {( a, b, c) : 1 ≤ a, b, c ≤ 6}, then
6 1
E1x = {( x, b, c) : 1 ≤ b, c ≤ 6} and P( E1x ) = 3
=
6 36
Plainly
6 1
P( E1x ∩ E2y ) = P{( x, y, c) : 1 ≤ c ≤ 6} =
3
= 2 = P( E1x )P( E2y )
6 6
The same holds for any pair of events from E1x , E2y and E3z . Moreover,
1
P( E1x ∩ E2y ∩ E3z ) = P({( x, y, z)}) = = P( E1x )P( E2y )P( E3z )
63
We conclude that the events E1x , E2y and E3z are independent.
4. Roll two fair dice and consider the following events and their probabilities
• E “the sum is 7” has P( E) = 6
= 16
36
• F “the first die is a 3” has P( F ) = 16
• G “the second die is a 5” has P( G ) = 1
6

Plainly F, G are independent since the two dice rolls have nothing to do with each other. E and
F are also independent, since
|{(3, 4)}| 1 1 1
P( E ∩ F ) = = = · = P( E )P( F )
36 36 6 6
E and G are independent similarly. However P( E ∩ F ∩ G ) = 0 ̸= P( E)P( F )P( G ), so the three
events are dependent.

10
Warnings: The definition of independence is purely formulaic, so you must be very careful applying
intuition related to its meaning in English. In particular:
• In the last example, F and G are independent because they are outcomes of entirely unrelated
experiments; this is our intuition about independence, but it is incorrect. The experiments for
E and F are related, but the events are still independent! This is, however, merely a quirk of
numbers: if E were changed to “the sum is 8,” then the events E, F are now dependent
1 5 1
P( E ∩ F ) = ̸= · = P( E )P( F )
36 36 6
• Independence and mutual exclusivity (E ∩ F = ∅) are not the same thing! If E, F are mutually
exclusive events with non-zero probabilities, then
P( E )P( F ) ̸ = 0 = P( ∅ ) = P( E ∩ F )
Mutually exclusive events are essentially never independent!
Independent events combine naturally; for instance, if E, F are independent, so also are E and FC :
P( E ∩ FC ) = P( E) − P( E ∩ F ) = P( E) − P( E)P( F ) = P( E)(1 − P( F )) = P( E)P( FC )

Example 3.16. Independent trials of rolling a fair die are performed. What is the probability of
rolling a 1 before rolling a 5 or 6?
Let En be the event that the first n − 1 rolls are either 2, 3 or 4, and that the nth roll is a 1. Since the
outcome of each roll is an independent trial, we have
  n −1
3 1
P( En ) = ·
6 6
Since the events En are mutually exclusive, it follows that the required probability is
∞ ∞
1 ∞ 1
!
1 1 1
P En = ∑ P( En ) = ∑ n−1 = ·
[
=
n =1 n =1
6 n =1
2 6 1 − 1/2 3

where we used the basic geometric series formula.

Alternatively, we could compute by letting E be the event that a 1 occurs before a 5 or 6 and condi-
tioning on the outcome of the 1st trial: consider events
• F “the first trial is a 1”
• G “the first trial is a 2, 3 or 4”
• H “the first trial is a 5 or 6”
Then
1 1 1
P( E ) = P( E | F )P( F ) + P( E | G )P( G ) + P( E | H )P( H ) = 1 · + P( E ) · + 0 ·
6 2 3
1
=⇒ P( E) =
3
We used the fact that P( E| G ) = P( E) since, if the first trial does not produce a conclusion, it is as if it
never happened.

11
The example illustrates the following.

Lemma 3.17. Suppose A, B are mutually exclusive outcomes of a single trial. If independent trials
are conducted, then the probability of A occurring before B is

P( A ) P( A )
=
P( A ) + P( B ) P( A ∪ B )

This should be intuitive; we care only about the outcomes which end the experiment (A or B), and
count those which produce the desired result (A). Note that this only works because the outcomes
A, B of each trial were mutually exclusive.2

Proof. Let E be the event “A occurs before B.” We condition on the outcome of the first trial, namely
the mutually exclusive events

• A1 “the first trial has outcome A”

• B1 “the first trial has outcome B”
• C = AC1 ∩ BC “the first trial’s outcome is neither A nor B”

We have P( E| A) = 1, P( E| B) = 0 and P( E|C ) = P( E), since if neither of the desired outcomes

occurs in the first trial, it is as if it never happened. Now compute

P( E) = P( E| A1 )P( A1 ) + P( E| B1 )P( B1 ) + P( E|C )P(C )

= 1 · P( A) + 0P( B) + P( E) 1 − P( A) − P( B)

from which the result is read off.

Introduction to the Binomial Distribution

Suppose we have a (biased) coin whose probability of landing heads is p, and suppose that separate
coin flips are independent trials. The probability of tossing three heads, two tails, then one head is

P( HHHTTH ) = p3 (1 − p)2 p = p4 (1 − p)2

Plainly it does not matter in which order the heads and tails appear; the probability of tossing four
heads and two tails from six trials is therefore (64) p4 (1 − p)2 , where the binomial coefficient counts
how many subsets of the six trials have precisely four heads. We can ask this question more generally:

Definition 3.18 (Binomial Distribution). We perform n independent trials, each with probability
of success p. If X is the number of successes from the n trials, then
 
n k
P{ X = k } = p (1 − p ) n − k
k

We say that X is a binomially distributed random variable.

2 Theproblem is more one of English rather than Mathematics: if A and B could occur simultaneously (P( A ∩ B) ̸= 0,
which requires A ∩ B ̸= ∅), what does it mean for A to happen before B? Should we really be asking for A ∩ BC to happen
before B? But these new events are now mutually exclusive, so the lemma applies!

12
To return to the previous example, the probability of rolling two 1’s in five trials is

1 5−2
   2 
53

5 1 625
P{ X = 2} = 1− = 10 · 5 = ≈ 16.1%
2 6 6 6 3888

We’ll return to the binomial distribution more formally in the next chapter. For the present, we return
(again!) to Fermat & Pascal’s problem of points.

Example 3.19. Let Pa,b denote the probability of a successes before b failures: i.e. the probability
that player A wins the game. This requires at least a successes in the first a + b − 1 trials; If we let X
be the number of successes in the first a + b − 1 trials, then the binomial distribution tells us that3
a + b −1 a + b −1 
a+b−1 k

Pa,b = ∑ P{ X = k } = ∑ k
p (1 − p ) a + b −1− k
k= a k= a

The Gambler’s Ruin Problem We finish the chapter with another famous, and related, problem.
We start small.

Example 3.20. Ava and Bruno roll a fair die. On a roll of 1 or 2, Ava pays Bruno $1; on a 3, 4, 5 or 6,
Bruno pays $1 to Ava. If Ava starts with $2, Bruno with $8, and they repeat until one player has $10,
find the probability that Ava wins.
Ava has probability p = 23 of gaining $1 on each roll. Since the rolls (trials) are independent, the prob-
ability that Ava wins depends only on how much money she currently has, not on what happened
previously. Let
Pk be the probability that Ava wins given that she currently has $k
We condition on the outcome of the next coin toss:
2 1
Pk = Pk+1 + Pk−1 , 1≤k≤9
3 3
with initial conditions P0 = 0 and P10 = 1. There is a sneaky trick to this; rewrite symmetrically
1
Pk+1 − Pk = ( P − Pk−1 )
2 k
which becomes a simple recurrence for a new variable Rk := Pk − Pk−1 ;
1
R k +1 = R , 1 ≤ k ≤ 9, R1 = P1 − P0 = P1
2 k
1 k −1


We therefore have Rk = P1 2 , so we can compute Pk by summing a geometric sequence
k k
1
Pk = ( Pk − Pk−1 ) + ( Pk−1 − Pk−2 ) + · · · + ( P1 − P0 ) + P0 = ∑ R j = P1 ∑ 2j−1
"  k # j =1 j =1
1 − ( 21 )k 1
= P1 · 1
= 2P1 1 −
1− 2 2
3 This is much easier than conditioning on the outcome of the first toss and solving a recurrence

Pa,b = P( H ) Pa−1,b + P( T ) Pa,b−1 = pPa−1,b + (1 − p) Pa,b−1

subject to initial conditions Pa,0 = 0 and P0,b = 1. This is similar to how we analyzed the problem in the introduction.

13
Using the initial condition P10 = 1, we obtain the solution

1 k


1− 2
Pk =
1 10


1− 2

The answer to our original problem is that Ava wins with probability

28 (22 − 1) 256 · 3 256

P2 = 10
= = ≈ 75.1%
2 −1 1023 341
It is perhaps surprising that the result is so lopsided, given that Ava started with far less money. In
512
fact, P1 = 1023 ≈ 50.01%, so even if Bruno only needs one more dollar, the outcome is finely balanced!

The general problem can be stated, and solved similarly.

Theorem 3.21 (Gambler’s Ruin). A and B play a game with the following rules.

• A starts with k points and B with N − k points.

• Each round is an independent trial; A pays B one point with probability p; B pays A one point
with probability q = 1 − p.
• The game ends when one player has all N points.

The probability of player A winning the game is

 q k
 1−( qp ) if p ̸= 21
Pk = 1−( p ) N
k
N if p = 21

q
The example had N = 10 and p = 23 , whence p = 12 .
q
Proof. If p ̸= 12 , then p ̸= 1 and the argument proceeds exactly as in the example; the recurrence
becomes symmetric via
q
Pk = pPk+1 + qPk−1 ⇐⇒ Pk+1 − Pk = ( P − Pk−1 ), 1 ≤ k ≤ N−1
p k

This is solved in the same way by summing a geometric sequence and applying the initial conditions
P0 = 0 and PN = 1.
q
If p = q = 21 , then p = 1 and the recurrence is

Pk+1 − Pk = Pk − Pk−1 =⇒ Pk = ( Pk − Pk−1 ) + · · · + ( P1 − P0 ) = k ( P1 − P0 ) = kP1

1
The initial condition PN = 1 forces P1 = N and thus the result.

14