Solutions Manual

for the book

Introduction to Probability, Second Edition
Joseph K. Blitzstein and Jessica Hwang
c Chapman & Hall/CRC Press, 2019

Joseph K. Blitzstein and Jessica Hwang

Departments of Statistics, Harvard University and Stanford University

September 27, 2019

Contents

1 Probability and counting 1

2 Conditional probability 31

3 Random variables and their distributions 81

4 Expectation 103

5 Continuous random variables 149

6 Moments 181

7 Joint distributions 191

8 Transformations 253

9 Conditional expectation 277

10 Inequalities and limit theorems 313

11 Markov chains 335

12 Markov chain Monte Carlo 357

13 Poisson processes 361

iii
1
Probability and counting

Counting
1. How many ways are there to permute the letters in the word MISSISSIPPI?
Solution:
The word has 4 S’s, 4 I’s, 2 P’s, and 1 M. Let’s choose where to put the S’s, then where
to put the I’s, then where to put the P’s, and then the location of the M is determined.
By the multiplication rule, there are
! ! !
11 7 3
= 34650
4 4 2
possibilities. Alternatively, we can start with 11! and adjust for overcounting:
11!
= 34650.
4!4!2!
2. (a) How many 7-digit phone numbers are possible, assuming that the first digit can’t
be a 0 or a 1?
(b) Re-solve (a), except now assume also that the phone number is not allowed to start
with 911 (since this is reserved for emergency use, and it would not be desirable for the
system to wait to see whether more digits were going to be dialed after someone has
dialed 911).
Solution:
(a) By the multiplication rule, there are 8 · 106 possibilities.
(b) There are 104 phone numbers in (a) that start with 911 (again by the multiplication
rule, since the first 3 digits are 911 and the remaining 4 digits are unconstrained).
Excluding these and using the result of (a), the number of possibilities is
8 · 106 − 104 = 7990000.

3. Fred is planning to go out to dinner each night of a certain week, Monday through
Friday, with each dinner being at one of his ten favorite restaurants.
(a) How many possibilities are there for Fred’s schedule of dinners for that Monday
through Friday, if Fred is not willing to eat at the same restaurant more than once?
(b) How many possibilities are there for Fred’s schedule of dinners for that Monday
through Friday, if Fred is willing to eat at the same restaurant more than once, but is
not willing to eat at the same place twice in a row (or more)?
Solution:
(a) By the multiplication rule, there are 10 · 9 · 8 · 7 · 6 = 30240 possibilities.
(b) By the multiplication rule, there are 10 · 94 = 65610 possibilities, since Monday’s
dinner can be at any of the 10 restaurants, and for Tuesday through Friday, each dinner
can be at any of the 10 restaurants except the one where Fred ate on the previous night.

1
2

4. A round-robin tournament is being held with n tennis players; this means that every
player will play against every other player exactly once.

(a) How many possible outcomes are there for the tournament (the outcome lists out
who won and who lost for each game)?

(b) How many games are played in total?

Solution:
n
(a) For each of the n2 unordered pairs of players, there is 1 game, so there are 2( 2 )

possible outcomes for the tournament.

(b) There are n2 games played, as noted in (a).

5. A knock-out tournament is being held with 2n tennis players. This means that for each
round, the winners move on to the next round and the losers are eliminated, until only
one person remains. For example, if initially there are 24 = 16 players, then there are
8 games in the first round, then the 8 winners move on to round 2, then the 4 winners
move on to round 3, then the 2 winners move on to round 4, the winner of which is
declared the winner of the tournament. (There are various systems for determining who
plays whom within a round, but these do not matter for this problem.)

(a) How many rounds are there?

(b) Count how many games in total are played, by adding up the numbers of games
played in each round.

(c) Count how many games in total are played, this time by directly thinking about it
without doing almost any calculation.
Hint: How many players need to be eliminated?

Solution:

(a) There are n rounds, since each round cuts the number of remaining players in half.

(b) There are 2n /2 = 2n−1 games in the first round, then 2n−2 games in the second
round, and so on, until there are only 2 players left in the final round. Using the formula
for the sum of a finite geometric series (see the math appendix), the total number of
games is
1 − 2n
1 + 2 + 22 + · · · + 2n−1 = = 2n − 1.
1−2

(c) A much easier way to see that the number of games is 2n − 1 is to note that each
game eliminates one player, and 2n −1 players need to be eliminated to leave one winner.

6. There are 20 people at a chess club on a certain day. They each find opponents and
start playing. How many possibilities are there for how they are matched up, assuming
that in each game it does matter who has the white pieces (in a chess game, one player
has the white pieces and the other player has the black pieces)?

Solution: There are 21020!

·10!
ways to determine who plays whom without considering color,
by the multiplication rule or the result of Example 1.5.4 (Partnerships). For each game,
there are 2 choices for who has the white pieces, so overall the number of possibilities is

210 · 20! 20!

= = 670442572800.
210 · 10! 10!

Alternatively, imagine a long table with 10 chessboards in a row, with 10 chairs on each
Probability and counting 3

side of the table (for the chess players to sit in). Chess pieces are set up at each board,
oriented so that the white pieces are all on one side of the table and the black pieces are
all on the other side of the table. There are 20! ways for the chess players to be assigned
to chairs, and once the players are seated in their chairs, a configuration for the chess
games has been determined. This procedure overcounts by a factor of 10! since, after
matching up the players, we can permute the players on one side of the table in any
way, as long as we also permute the players on the other side of the table in the same
20!
way. So again the number of possibilities is 10! .

7. Two chess players, A and B, are going to play 7 games. Each game has three possible
outcomes: a win for A (which is a loss for B), a draw (tie), and a loss for A (which is
a win for B). A win is worth 1 point, a draw is worth 0.5 points, and a loss is worth 0
points.

(a) How many possible outcomes for the individual games are there, such that overall
player A ends up with 3 wins, 2 draws, and 2 losses?

(b) How many possible outcomes for the individual games are there, such that A ends
up with 4 points and B ends up with 3 points?

(c) Now assume that they are playing a best-of-7 match, where the match will end
when either player has 4 points or when 7 games have been played, whichever is first.
For example, if after 6 games the score is 4 to 2 in favor of A, then A wins the match
and they don’t play a 7th game. How many possible outcomes for the individual games
are there, such that the match lasts for 7 games and A wins by a score of 4 to 3?

Solution:

(a) Writing W for win, D for draw, and L for loss (for player A), an outcome of the
desired form is any permutation of WWWDDLL. So there are
7!
= 210
3!2!2!
possible outcomes of the desired form.

(b) To end up with 4 points, A needs to have one of the following results: (i) 4 wins and
3 losses; (ii) 3 wins, 2 draws, and 2 losses; (iii) 2 wins, 4 draws, and 1 loss; or (iv) 1 win
and 6 draws. Reasoning as in (a) and adding up these possibilities, there are
7! 7! 7! 7!
+ + + = 357
4!3! 3!2!2! 2!4!1! 1!6!
possible outcomes of the desired form.

(c) For the desired outcomes, either (i) player A is ahead 3.5 to 2.5 after 6 games and
then draws game 7, or (ii) the match is tied (3 to 3) after 6 games and then player A
wins game 7. Reasoning as in (b), there are
6! 6! 6!
+ + = 126
3!1!2! 2!3!1! 1!5!
possibilities of type (i) and
6! 6! 6!
+ + + 1 = 141
3!3! 2!2!2! 1!4!1!
possibilities of type (ii), so overall there are

126 + 141 = 267

possible outcomes of the desired form.

4

8. s (a) How many ways are there to split a dozen people into 3 teams, where one team
has 2 people, and the other two teams have 5 people each?

(b) How many ways are there to split a dozen people into 3 teams, where each team has
4 people?

Solution:

(a) Pick any 2 of the 12 people to make the 2 person team, and then any 5 of the
remaining 10 for the first team of 5, and then the remaining 5 are on the other team of
5; this overcounts by a factor of 2 though,

10
since there is no designated “first” team of
5. So the number of possibilities is 12
2 5
/2 = 8316. Alternatively, politely ask the 12
people to line up, and then let the first 2 be the team of 2, the next 5 be a team of 5,
and then last 5 be a team of 5. There are 12! ways for them to line up, but it does not
matter which order they line up in within each group, nor does the order of the 2 teams
12!
of 5 matter, so the number of possibilities is 2!5!5!·2 = 8316.
12!
(b) By either of the approaches above, there are 4!4!4! ways to divide the people into a
Team A, a Team B, and a Team C, if we care about which team is which (this is called
a multinomial coefficient). Since here it doesn’t matter which team is which, this over
12!
counts by a factor of 3!, so the number of possibilities is 4!4!4!3! = 5775.

9. s (a) How many paths are there from the point (0, 0) to the point (110, 111) in the
plane such that each step either consists of going one unit up or one unit to the right?

(b) How many paths are there from (0, 0) to (210, 211), where each step consists of going
one unit up or one unit to the right, and the path has to go through (110, 111)?

Solution:

(a) Encode a path as a sequence of U ’s and R’s, like U RU RU RU U U R . . . U R, where

U and R stand for “up” and “right” respectively. The sequence must consist of 110 R’s
and 111 U ’s, and to determine the sequence we just need to specify where the R’s are
located. So there are 221


110
possible paths.

(b) There are 221

110
paths to (110, 111), as above. From there, we need 100 R’s and 100
U ’s
to get
to (210, 211), so by the multiplication rule the number of possible paths is
221
110
· 200
100
.

10. To fulfill the requirements for a certain degree, a student can choose to take any 7 out
of a list of 20 courses, with the constraint that at least 1 of the 7 courses must be a
statistics course. Suppose that 5 of the 20 courses are statistics courses.

(a) How many choices are there for which 7 courses to take?

(b) Explain intuitively why the answer to (a) is not 51 · 19

6
.

Solution:

(a) There are 20 15

7
ways to choose 7 courses if there are no constraints, but 7
of these
have no statistics courses. So there are
! !
20 15
− = 71085
7 7

sets of 7 courses that contain at least one statistics course.

(b) An incorrect argument would be “there are 51 to choose a statistics course (let’s

knock that
requirement out of the way, then we can choose any other 6 courses) and
then 19 6
choices for the remaining 6 courses.” This is incorrect since it’s possible (and
Probability and counting 5

often a good idea!) to take more than one statistics course. A possibility containing,
for example, the statistics courses Stat

110
and Stat 111 together with 5 non-statistics
courses would be counted twice in 51 · 19 6
, once with Stat 110 as the choice for the
5


1
term and once with Stat 111 as the choice. So it makes sense that the true answer
is much less than 51 · 19



6
.

11. Let A and B be sets with |A| = n, |B| = m.

(a) How many functions are there from A to B (i.e., functions with domain A, assigning
an element of B to each element of A)?

(b) How many one-to-one functions are there from A to B (see Section A.2.1 of the
math appendix for information about one-to-one functions)?

Solution:

(a) By the multiplication rule, there are mn functions f from A to B, since for each
a ∈ A there are m possible ways to define f (a).

(b) Now values can’t be repeated, so there are m · (m − 1) · (m − 2) · · · · (m − n + 1)

possibilities for n ≤ m, and there are no possibilities for n > m.

12. Four players, named A, B, C, and D, are playing a card game. A standard, well-shuffled
deck of cards is dealt to the players (so each player receives a 13-card hand).

(a) How many possibilities are there for the hand that player A will get? (Within a
hand, the order in which cards were received doesn’t matter.)

(b) How many possibilities are there overall for what hands everyone will get, assuming
that it matters which player gets which hand, but not the order of cards within a hand?

(c) Explain intuitively why the answer to Part (b) is not the fourth power of the answer
to Part (a).

Solution:

(a) There are 52

13
possibilities since player A gets 13 out of 52 cards, without replacement
and with order not mattering.

(b) There are 52 possibilities for A’s hand. For each of these, there are 39



13 13
possibilities
for B’s hand. For each of these, there are 26


13
possibilities for C’s hand. After 3 hands
have been determined, the 4th is also determined. So the number of possibilities is
! ! !
52 39 26 52!
= ≈ 5.36 × 1028 .
13 13 13 (13!)4

The expression with factorials could have been obtained directly by imagining shuffling
the cards and giving the first 13 to A, the next 13 to B etc., and then adjusting for the
fact that the order of cards within each player’s hand doesn’t matter.
As Wikipedia remarks (at http://en.wikipedia.org/wiki/Bridge_probabilities as
of December 1, 2014), “The immenseness of this number can be understood by answering
the question ‘How large an area would you need to spread all possible bridge deals if
each deal would occupy only one square millimeter? ’. The answer is: an area more than
a hundred million times the total area of Earth.”

(c) The answer to (b), though an extremely large number, is much smaller than the
fourth power of the answer to (a) since

39
the
cards

are dealt without

replacement. This
makes the number of possibilities 52 26 13 52 52 52 52




13 13 13 13
rather than 13 13 13 13
.
6

13. A certain casino uses 10 standard decks of cards mixed together into one big deck, which
we will call a superdeck. Thus, the superdeck has 52 · 10 = 520 cards, with 10 copies
of each card. How many different 10-card hands can be dealt from the superdeck? The
order of the cards does not matter, nor does it matter which of the original 10 decks
the cards came from. Express your answer as a binomial coefficient.
Hint: Bose-Einstein.

Solution: A hand is determined by specifying how many times each of the 52 different
cards occurs. Number the 52 cards in a standard deck as 1, 2, . . . , 52, and let xi be the
number of times card i occurs in a hand (e.g., 3 for the Ace of Spades in the above
example). Then the xi are nonnegative integers with

x1 + x2 + · · · + x52 = 10.

By Bose-Einstein, the number of solutions is

! !
52 + 10 − 1 61
= ≈ 9.018 × 1010 .
10 10

14. You are ordering two pizzas. A pizza can be small, medium, large, or extra large, with
any combination of 8 possible toppings (getting no toppings is allowed, as is getting all
8). How many possibilities are there for your two pizzas?

Solution: For one pizza, there are 4 · 28 = 210 possibilities. For two pizzas, there are
210
ways to choose two distinct kinds of pizza, and 210 possibilities with two copies of


2
the same kind of pizza. So the number of possibilities is
!
210
+ 210 = 524800.
2

Alternatively, think of choosing 2 pizza types with replacement, where order doesn’t
matter. Then Bose-Einstein gives the same answer: the number of possibilities is
!
210 + 2 − 1
= 524800.
2

Story proofs
Pn n
= 2n .


15. s Give a story proof that k=0 k

Solution: Consider picking a subset of n people. There are nk choices with size k, on

the one hand, and on the other hand there are 2n subsets by the multiplication rule.

16. s Show that for all positive integers n and k with n ≥ k,

! ! !
n n n+1
+ = ,
k k−1 k

doing this in two ways: (a) algebraically and (b) with a story, giving an interpretation
for why both sides count the same thing.
Hint for the story proof: Imagine n + 1 people, with one of them pre-designated as
“president”.

Solution:
Probability and counting 7

(a) For the algebraic proof, start with the definition of the binomial coefficients in the
left-hand side, and do some algebraic manipulation as follows:
! !
n n n! n!
+ = +
k k−1 k!(n − k)! (k − 1)!(n − k + 1)!
(n − k + 1)n! + (k)n!
=
k!(n − k + 1)!
n!(n + 1)
=
k!(n − k + 1)!
!
n+1
= .
k

(b) For the story proof, consider n + 1 people, with one of them pre-designated as
“president”. The right-hand side is the number of ways to choose k out of these n + 1
people, with order not mattering. The left-hand side counts the same thing in a different
way, by considering two cases: the president is or isn’t in the chosen group.
n


The number of groups of size k which include the president is k−1 , since once we fix
the president as a member of the group, we only need to choose another k − 1 members
out of the remaining n people. Similarly, there are nk groups of size k that don’t include

the president. Thus, the two sides of the equation are equal.

17. Give a story proof that

n
!2 !
X n 2n
= ,
k n
k=0

for all positive integers n.

Solution: Consider a club consisting of n sophomores and n juniors, from which a com-
mittee of size n will be selected. There are 2n


n
possibilities for the composition of the
committee; this is the right-hand side of the identity. If the committee has exactly k
sophomores, then it must have exactly n − k juniors. The number of possibilities for the
committee with exactly k sophomores is
! ! !2
n n n
= ,
k n−k k

by the multiplication rule and Example 1.5.1. Summing over all possible values of k
yields the left-hand side of the identity. Note that the identity can also be thought of
as a special case of Vandermonde’s identity, after writing
n
!2 n
! !
X n X n n
= .
k k n−k
k=0 k=0

18. Give a story proof that

n
!2 !
X n 2n − 1
k =n ,
k n−1
k=1

for all positive integers n.

Hint: Consider choosing a committee of size n from two groups of size n each, where
only one of the two groups has people eligible to become president.

Solution:

Imagine that there are n juniors and n seniors in a certain club. A committee of size n is
8

chosen, and one of these people becomes president. Suppose though that the president

n
must be a senior. Letting k be the
number

of seniors on the committee, there are k
n n
ways to choose the seniors, n−k = k ways to choose the juniors, and after these
choices are made there are k choices of president. So the overall number of possibilities
is the left-hand side of the identity.
Alternatively, we can choose the president first (as any of the n seniors), and then choose
any n − 1 of the remaining 2n − 1 people to form the rest of the committee. This gives
the right-hand side of the identity.

19. Give a story proof that

n
! ! !
X k n−k+2 n+3
= ,
2 2 5
k=2

for all integers n ≥ 2.

Hint: Consider the middle number in a subset of {1, 2, . . . , n + 3} of size 5.

Solution: There are n+3

5
subsets of {1, 2, . . . , n + 3} of size 5; this is the right-hand side
of the identity. Consider such a subset, and order it from smallest to largest. Let j be the
middle number (i.e., the
third number on the sorted list), and note that 3 ≤ j ≤ n + 1.
Given j, there are j−1 2
choices for the 2 numbers in the subset that are less than j,
since these can be any two numbers in 1, 2, . . . , j −1. Similarly, there are (n+3)−(j+1)+1


2
choices for the 2 numbers in the subset that are greater than j, since these can be any
two numbers in j + 1, . . . , n + 3. Summing over the possible values of j gives
n+1
! ! n
! !
X j−1 (n + 3) − (j + 1) + 1 X k n−k+2
= ,
j=3
2 2 2 2
k=2

which is the left-hand side of the identity.

20. s (a) Show using a story proof that

! ! ! ! !
k k+1 k+2 n n+1
+ + + ··· + = ,
k k k k k+1

where n and k are positive integers with n ≥ k. This is called the hockey stick identity.
Hint: Imagine arranging a group of people by age, and then think about the oldest
person in a chosen subgroup.

(b) Suppose that a large pack of Haribo gummi bears can have anywhere between 30
and 50 gummi bears. There are 5 delicious flavors: pineapple (clear), raspberry (red),
orange (orange), strawberry (green, mysteriously), and lemon (yellow). There are 0 non-
delicious flavors. How many possibilities are there for the composition of such a pack of
gummi bears? You can leave your answer in terms of a couple binomial coefficients, but
not a sum of lots of binomial coefficients.

Solution:

(a) Consider choosing k + 1 people out of a group of n + 1 people. Call the oldest person
in the subgroup “Aemon”. If Aemon is also the oldest person in the full group, then
there are nk choices for the rest of the subgroup. If Aemon is the second oldest in the

full group, then there are n−1

k
choices since the oldest person in the full group can’t be
chosen. In general, if there are j people in the full group who are younger than Aemon,
then there are kj possible choices for the rest of the subgroup. Thus,

n
! !
X j n+1
= .
k k+1
j=k
Probability and counting 9

(b) For a pack of i gummi bears, there are 5+i−1 = i+4 = i+4




i i 4
possibilities since
the situation is equivalent to getting a sample of size i from the n = 5 flavors (with
replacement, and with order not mattering). So the total number of possibilities is
50
! 54
!
X i+4 X j
= .
i=30
4 j=34
4

Applying the previous part, we can simplify this by writing

54
! 54
! 33
! ! !
X j X j X j 55 34
= − = − .
j=34
4 j=4
4 j=4
4 5 5

(This works out to 3200505 possibilities!)

Define nk as the number of ways to partition {1, 2, . . . , n} into k nonempty subsets, or


21.
the number of ways to have n students split up into k groups such that each group has
at least one student. For example, 42 = 7 because we have the following possibilities:


• {1}, {2, 3, 4} • {1, 2}, {3, 4}

• {2}, {1, 3, 4}
• {1, 3}, {2, 4}
• {3}, {1, 2, 4}
• {4}, {1, 2, 3} • {1, 4}, {2, 3}

Prove the following identities:

(a) ( ) ( ) ( )
n+1 n n
= +k .
k k−1 k
Hint: I’m either in a group by myself or I’m not.

(b) !( ) ( )
n
X n j n+1
= .
j k k+1
j=k

Hint: First decide how many people are not going to be in my group.

Solution:
(a) The left-hand side is the number of ways to divide n + 1 people into k nonempty
groups. Now let’s count this a different way. Say I’m the (n + 1)st person. Either
 n I’m in
a group by myself or I’m not. If I’m in a group by myself, then there are k−1 ways
to divide the remaining n people into k − 1 nonempty groups. Otherwise,
n the n people
other than me form k nonempty groups, which can be  ndone inn k ways, and then I
can join any of those k groups. So in total, there are k−1 + k k possibilities, which
is the right-hand side.

(b) The right-hand side is the number of ways to divide n+1 people into k +1 nonempty
groups. Say I’m the (n + 1)st person. Let j be the number of people not in my group.
n

 j k ≤ j ≤ n. The nnumber
Then
of possible divisions with j people not in my group is
j k
since we have j possibilities for which j specific people are not in my group
(and then it’s determined who is in my group) and then kj possibilities for how to


divide those j people into k groups that are not my group. Summing over all possible j
gives the left-hand side.

Note: The quantities nk are known as Stirling numbers of the second kind.

10

22. The Dutch mathematician R.J. Stroeker remarked:

Every beginning student of number theory surely must have marveled at the miraculous
fact that for each natural number n the sum of the first n positive consecutive cubes is
a perfect square. [29]
Furthermore, it is the square of the sum of the first n positive integers! That is,

13 + 23 + · · · + n3 = (1 + 2 + · · · + n)2 .

Usually this identity is proven by induction, but that does not give much insight into
why the result is true, nor does it help much if we wanted to compute the left-hand side
but didn’t already know this result. In this problem, you will give a story proof of the
identity.

(a) Give a story proof of the identity

!
n+1
1 + 2 + ··· + n = .
2

Hint: Consider a round-robin tournament (see Exercise 4).

(b) Give a story proof of the identity

! ! !
3 3 3n+1 n+1 n+1
1 + 2 + ··· + n = 6 +6 + .
4 3 2

It is then just basic algebra (not required for this problem) to check that the square of
the right-hand side in (a) is the right-hand side in (b).
Hint: Imagine choosing a number between 1 and n and then choosing 3 numbers between
0 and n smaller than the original number, with replacement. Then consider cases based
on how many distinct numbers were chosen.

Solution:
(a) Consider a chess tournament
with n + 1 players, where everyone plays against ev-
eryone else once. A total of n+1
2
games are played. Label the players 0, 1, . . . , n. Player
0 plays n games, player 1 plays n − 1 games not already accounted for, player 2 plays
n − 2 games not already accounted for, etc. So
!
n+1
n + (n − 1) + (n − 2) + · · · + 1 = .
2

(b) Following the hint, let us count the number of choices of (i, j, k, l) where i is greater
than j, k, l. Given i, there are i3 choices for (j, k, l), which gives the left-hand side. On the
other
hand, consider 3 cases: there could be 2, 3, or 4 distinct numbers chosen. There are
n+1
2
ways to choose 2 distinct numbers from 0, 1, . . . , n, giving, e.g., (3, 1, 1, 1). There
are n+1


4
ways to choose 4 distinct numbers, giving, e.g., (5, 2, 1, 4), but the (2, 1, 4)
could be permuted in any order so we multiply by 6. There are n+1


3
ways to choose 3
distinct numbers, giving, e.g., (4, 2, 2, 1), but the 2, 2, 1 can be in any order and could
have been 1, 1, 2 in any order also, again giving a factor of 6. Adding these cases gives
the right-hand side.

Naive definition of probability

23. Three people get into an empty elevator at the first floor of a building that has 10
floors. Each presses the button for their desired floor (unless one of the others has
already pressed that button). Assume that they are equally likely to want to go to
Probability and counting 11

floors 2 through 10 (independently of each other). What is the probability that the
buttons for 3 consecutive floors are pressed?

Solution: The number of possible outcomes for who is going to which floor is 93 . There
are 7 possibilities for which buttons are pressed such that there are 3 consecutive floors:
(2, 3, 4), (3, 4, 5), . . . , (8, 9, 10). For each of these 7 possibilities, there are 3! ways to
choose who is going to which floor. So by the naive definition, the probability is
3! · 7 42 14
= = ≈ 0.0576.
93 729 243
24. s A certain family has 6 children, consisting of 3 boys and 3 girls. Assuming that all
birth orders are equally likely, what is the probability that the 3 eldest children are the
3 girls?

Solution: Label the girls as 1, 2, 3 and the boys as 4, 5, 6. Think of the birth order is a
permutation of 1, 2, 3, 4, 5, 6, e.g., we can interpret 314265 as meaning that child 3 was
born first, then child 1, etc. The number of possible permutations of the birth orders
is 6!. Now we need to count how many of these have all of 1, 2, 3 appear before all of
4, 5, 6. This means that the sequence must be a permutation of 1, 2, 3 followed by a
permutation of 4, 5, 6. So with all birth orders equally likely, we have

(3!)2
P (the 3 girls are the 3 eldest children) = = 0.05.
6!

Alternatively, we can use the fact that there are 63 ways to choose where the girls

appear in the birth order (without taking into account the ordering of the girls amongst
themselves). These are all equally likely. Of these possibilities, there is only 1 where the
3 girls are the 3 eldest children. So again the probability is 16 = 0.05.
(3)
25. s A city with 6 districts has 6 robberies in a particular week. Assume the robberies are
located randomly, with all possibilities for which robbery occurred where equally likely.
What is the probability that some district had more than 1 robbery?

Solution: There are 66 possible configurations for which robbery occurred where. There
are 6! configurations where each district had exactly 1 of the 6, so the probability of
the complement of the desired event is 6!/66 . So the probability of some district having
more than 1 robbery is
1 − 6!/66 ≈ 0.9846.
Note that this also says that if a fair die is rolled 6 times, there’s over a 98% chance
that some value is repeated!
26. A survey is being conducted in a city with 1 million residents. It would be far too
expensive to survey all of the residents, so a random sample of size 1000 is chosen
(in practice, there are many challenges with sampling, such as obtaining a complete
list of everyone in the city, and dealing with people who refuse to participate). The
survey is conducted by choosing people one at a time, with replacement and with equal
probabilities.

(a) Explain how sampling with vs. without replacement here relates to the birthday
problem.

(b) Find the probability that at least one person will get chosen more than once.

Solution:

(a) In the survey problem, people are sampled one by one, and each person randomly
is any of the 106 residents in the city; in the birthday problem, people show up at a
party one by one, and each person randomly has any of 365 possible birthdays. The fact
12

that the same person can be chosen more than once when sampling with replacement
is analogous to the fact that more than one person can have the same birthday.

(b) This problem is isomorphic to (has the same structure as) the birthday problem. By
the naive definition of probability, the probability of no match is

106 (106 − 1)(106 − 2) · · · (106 − 999)

    
1 2 999
= 1− 6 1 − 6 ··· 1 − 6 .
(106 )1000 10 10 10
The probability of at least one person being chosen more than once is
    
1 2 999
1− 1− 6 1 − 6 · · · 1 − 6 ≈ 0.393.
10 10 10

27. A hash table is a commonly used data structure in computer science, allowing for fast
information retrieval. For example, suppose we want to store some people’s phone num-
bers. Assume that no two of the people have the same name. For each name x, a hash
function h is used, letting h(x) be the location that will be used to store x’s phone
number. After such a table has been computed, to look up x’s phone number one just
recomputes h(x) and then looks up what is stored in that location.

The hash function h is deterministic, since we don’t want to get different results every
time we compute h(x). But h is often chosen to be pseudorandom. For this problem,
assume that true randomness is used. Let there be k people, with each person’s phone
number stored in a random location (with equal probabilities for each location, inde-
pendently of where the other people’s numbers are stored), represented by an integer
between 1 and n. Find the probability that at least one location has more than one
phone number stored there.

Solution:

This problem has the same structure as the birthday problem. For k > n, the probability
is 1 since then there are more people than locations. For k ≤ n, the probability is
n(n − 1) . . . (n − k + 1)
1− .
nk

28. s A college has 10 (non-overlapping) time slots for its courses, and blithely assigns
courses to time slots randomly and independently. A student randomly chooses 3 of the
courses to enroll in. What is the probability that there is a conflict in the student’s
schedule?

Solution: The probability of no conflict is 10·9·8

103
= 0.72. So the probability of there being
at least one scheduling conflict is 0.28.
29. s For each part, decide whether the blank should be filled in with =, <, or >, and give
a clear explanation.

(a) (probability that the total after rolling 4 fair dice is 21) (probability that the
total after rolling 4 fair dice is 22)

(b) (probability that a random 2-letter word is a palindrome1 ) (probability that a

random 3-letter word is a palindrome)

Solution:
1
A palindrome is an expression such as “A man, a plan, a canal: Panama” that reads the same
backwards as forwards (ignoring spaces, capitalization, and punctuation). Assume for this problem
that all words of the specified length are equally likely, that there are no spaces or punctuation,
and that the alphabet consists of the lowercase letters a,b,. . . ,z.
Probability and counting 13

(a) > . All ordered outcomes are equally likely here. So for example with two dice,
obtaining a total of 11 is more likely than obtaining a total of 12 since there are two
ways to get a 5 and a 6, and only one way to get two 6’s. To get a 21, the outcome must
be a permutation of (6, 6, 6, 3) (4 possibilities), (6, 5, 5, 5) (4 possibilities), or (6, 6, 5, 4)
(4!/2 = 12 possibilities). To get a 22, the outcome must be a permutation of (6, 6, 6, 4)
(4 possibilities), or (6, 6, 5, 5) (4!/22 = 6 possibilities). So getting a 21 is more likely; in
fact, it is exactly twice as likely as getting a 22.

(b) = . The probabilities are equal, since for both 2-letter and 3-letter words, being a
palindrome means that the first and last letter are the same.

30. With definitions as in the previous problem, find the probability that a random n-letter
word is a palindrome for n = 7 and for n = 8.

Solution:

The probability of a random 7-letter word being a palindrome is

264 1
= 3 ≈ 5.69 × 10−5 ,
267 26
since the first 4 letters can be chosen arbitrarily and then the last 3 letters are deter-
mined. Similarly, the probability for a random 8-letter word is

264 1
= 4 ≈ 2.19 × 10−6 .
268 26

31. s Elk dwell in a certain forest. There are N elk, of which a simple random
sample of
size n are captured and tagged (“simple random sample” means that all N n
sets of n
elk are equally likely). The captured elk are returned to the population, and then a new
sample is drawn, this time with size m. This is an important method that is widely used
in ecology, known as capture-recapture. What is the probability that exactly k of the m
elk in the new sample were previously tagged? (Assume that an elk that was captured
before doesn’t become more or less likely to be captured again.)

Solution: We can use the naive definition here since we’re assuming all samples of size m
are equally likely. To have exactly k be tagged elk, we need to choose k of the n tagged
elk, and then m − k from the N − n untagged elk. So the probability is
n

N −n

k
· m−k
N

,
m

for k such that 0 ≤ k ≤ n and 0 ≤ m − k ≤ N − n, and the probability is 0 for all

other values of k (for example, if k > n the probability is 0 since then there aren’t even
k tagged elk in the entire population!). This is known as a Hypergeometric probability;
we will encounter it again in Chapter 3.

32. Four cards are face down on a table. You are told that two are red and two are black, and
you need to guess which two are red and which two are black. You do this by pointing
to the two cards you’re guessing are red (and then implicitly you’re guessing that the
other two are black). Assume that all configurations are equally likely, and that you do
not have psychic powers. Find the probability that exactly j of your guesses are correct,
for j = 0, 1, 2, 3, 4.

Solution:

There are 42 = 6 possibilities for where the two red cards are, all equally likely. So there

is a 1/6 chance that you will pick both locations of red cards correctly (in which case
you also get the locations of the black cards right). And there is a 1/6 chance that both
14

locations you choose actually contain black cards (in which case none of your guesses
are correct). This leaves a 4/6 chance that the locations you picked as having red cards
consist of 1 red card and 1 black card (in which case the other 2 locations also consist
of 1 red card and 1 black card). Thus, for j = 0, 1, 2, 3, 4, the desired probabilities are
1/6, 0, 2/3, 0, 1/6, respectively.

33. s A jar contains r red balls and g green balls, where r and g are fixed positive integers.
A ball is drawn from the jar randomly (with all possibilities equally likely), and then a
second ball is drawn randomly.

(a) Explain intuitively why the probability of the second ball being green is the same
as the probability of the first ball being green.

(b) Define notation for the sample space of the problem, and use this to compute the
probabilities from (a) and show that they are the same.

(c) Suppose that there are 16 balls in total, and that the probability that the two balls
are the same color is the same as the probability that they are different colors. What
are r and g (list all possibilities)?

Solution:

(a) This is true by symmetry. The first ball is equally likely to be any of the g + r balls,
so the probability of it being green is g/(g + r). But the second ball is also equally likely
to be any of the g + r balls (there aren’t certain balls that enjoy being chosen second
and others that have an aversion to being chosen second); once we know whether the
first ball is green we have information that affects our uncertainty about the second
ball, but before we have this information, the second ball is equally likely to be any of
the balls.
Alternatively, intuitively it shouldn’t matter if we pick one ball at a time, or take one
ball with the left hand and one with the right hand at the same time. By symmetry,
the probabilities for the ball drawn with the left hand should be the same as those for
the ball drawn with the right hand.

(b) Label the balls as 1, 2, . . . , g + r, such that 1, 2, . . . , g are green and g + 1, . . . , g + r

are red. The sample space can be taken to be the set of all pairs (a, b) with a, b ∈
{1, . . . , g + r} and a 6= b (there are other possible ways to define the sample space, but it
is important to specify all possible outcomes using clear notation, and it make sense to
be as richly detailed as possible in the specification of possible outcomes, to avoid losing
information). Each of these pairs is equally likely, so we can use the naive definition of
probability. Let Gi be the event that the ith ball drawn is green.
The denominator is (g +r)(g +r −1) by the multiplication rule. For G1 , the numerator is
g(g + r − 1), again by the multiplication rule. For G2 , the numerator is also g(g + r − 1),
since in counting favorable cases, there are g possibilities for the second ball, and for
each of those there are g + r − 1 favorable possibilities for the first ball (note that the
multiplication rule doesn’t require the experiments to be listed in chronological order!);
alternatively, there are g(g − 1) + rg = g(g + r − 1) favorable possibilities for the second
ball being green, as seen by considering 2 cases (first ball green and first ball red). Thus,
g(g + r − 1) g
P (Gi ) = = ,
(g + r)(g + r − 1) g+r
for i ∈ {1, 2}, which concurs with (a).

(c) Let A be the event of getting one ball of each color. In set notation, we can write
A = (G1 ∩ Gc2 ) ∪ (Gc1 ∩ G2 ) . We are given that P (A) = P (Ac ), so P (A) = 1/2. Then

2gr 1
P (A) = = ,
(g + r)(g + r − 1) 2
Probability and counting 15

giving the quadratic equation

g 2 + r2 − 2gr − g − r = 0,
i.e.,
(g − r)2 = g + r.
But g + r = 16, so g − r is 4 or −4. Thus, either g = 10, r = 6, or g = 6, r = 10.
34. s A random 5-card poker hand is dealt from a standard deck of cards. Find the prob-
ability of each of the following possibilities (in terms of binomial coefficients).
(a) A flush (all 5 cards being of the same suit; do not count a royal flush, which is a
flush with an ace, king, queen, jack, and 10).
(b) Two pair (e.g., two 3’s, two 7’s, and an ace).
Solution:
(a) A flush can occur in any of the
4 suits (imagine the tree, and for concreteness suppose
the suit is Hearts); there are 135
ways to choose the cards in that suit, except for one
way to have a royal flush in that suit. So the probability is
4 13



5
−1
52

.
5

(b) Choose the two ranks of the pairs, which specific cards to have for those 4 cards,
and then choose the extraneous card (which can be any of the 52 − 8 cards not of the
two chosen ranks). This gives that the probability of getting two pairs is
13

4
2
2
· 2 · 44
52

.
5

35. A random 13-card hand is dealt from a standard deck of cards. What is the probability
that the hand contains at least 3 cards of every suit?
Solution: The only to have at least 3 cards of every suit is to have exactly 4 cards from
one suit and exactly 3 cards from each of the other suits. Choosing which suit the hand
has 4 of, and then the specific cards from each suit, the probability is

13
3
4 · 13
4
· 3
52

≈ 0.1054.
13

36. A group of 30 dice are thrown. What is the probability that 5 of each of the values
1, 2, 3, 4, 5, 6 appear?
Solution:
To get 5 dice for each of the 6 values, we can choose the 5 out of 30 dice that will be
1’s, then the 5 out of the remaining 25 that will be 2’s, etc. This gives
! ! ! ! ! !
30 25 20 15 10 5 30!
· · · · · =
5 5 5 5 5 5 (5!)6
30


possibilities; this is known as a multinomial coefficient, sometimes denoted as 5,5,5,5,5 .
The right-hand side can also be obtained directly: it is the number of permutations of
the sequence 1111122222 . . . 66666. By the naive definition, the probability is
30!
≈ 0.000402.
(5!)6 · 630
16

37. A deck of cards is shuffled well. The cards are dealt one by one, until the first time an
ace appears.

(a) Find the probability that no kings, queens, or jacks appear before the first ace.

(b) Find the probability that exactly one king, exactly one queen, and exactly one jack
appear (in any order) before the first ace.

Solution:

(a) The 2’s through 10’s are irrelevant, so we can assume the deck consists of aces,
kings, queens, and jacks. The event of interest is that the first card is an ace. This has
probability 1/4 since the first card is equally likely to be any card.

(b) Continue as in (a). The probability that the deck starts as KQJA is

44 · 12! 8
= .
16! 1365
The KQJ could be in any order, so the desired probability is
3! · 8 16
= ≈ 0.0352.
1365 455

Alternatively, note that there are 16 · 15 · 14 · 13 possibilities for the first 4 cards, of
which 12 · 8 · 4 · 4 are favorable. So by the naive definition, the probability is
12 · 8 · 4 · 4
≈ 0.0352.
16 · 15 · 14 · 13

38. Tyrion, Cersei, and ten other people are sitting at a round table, with their seating
arrangement having been randomly assigned. What is the probability that Tyrion and
Cersei are sitting next to each other? Find this in two ways:

(a) using a sample space of size 12!, where an outcome is fully detailed about the seating;

(b) using a much smaller sample space, which focuses on Tyrion and Cersei.

Solution:

(a) Label the seats in clockwise order as 1, 2, . . . , 12, starting from some fixed seat.
Give the people other than Tyrion and Cersei ID numbers 1, 2, . . . , 10. The outcome is
(t, c, s1 , . . . , s10 ), where t is Tyrion’s seat assignment, c is Cersei’s, and sj is person j’s.
To count the number of ways in which Tyrion and Cersei can be seated together, let
Tyrion sit anywhere (12 possibilities), Cersei sit either to Tyrion’s left or to his right (2
possibilities), and let everyone else fill the remaining 10 seats in any way (10! possibili-
ties). By the multiplication rule and the naive definition, the probability is

12 · 2 · 10! 12 · 2 · 10! 2
= = .
12! 12 · 11 · 10! 11

(b) Now let’s just consider the 12

2
possible seat assignments of Tyrion and Cersei, not
worrying about which of these 2 seats goes to Tyrion or the details of where the other
10 people will sit. There are 12 assignments in which they sit together (without caring
about order): {1, 2}, {2, 3}, . . . , {11, 12}, {12, 1}. So the probability is
12 2
12 = ,


2
11

in agreement with (a).

Probability and counting 17

39. An organization with 2n people consists of n married couples. A committee of size k is

selected, with all possibilities equally likely. Find the probability that there are exactly
j married couples within the committee.
Solution: The probability is 0 if j > n (not enough couples) or k − 2j < 0 (not
enough
space on the committee), so assume 0 ≤ j ≤
n and k − 2j ≥ 0. There are 2n k
possible
compositions of the committee. There are nj ways to choose which j married couples
n−j


are on the committee. Once they are chosen, there are k−2j ways to choose which of
the other married couples are represented on the committee. For each of those k − 2j
couples, we then need to choose which person within the couple will be on the committee.
Overall, the probability is
n

n−j
k−2j
j k−2j
2
2n

.
k

40. There are n balls in a jar, labeled with the numbers 1, 2, . . . , n. A total of k balls are
drawn, one by one with replacement, to obtain a sequence of numbers.
(a) What is the probability that the sequence obtained is strictly increasing?
(b) What is the probability that the sequence obtained is increasing? (Note: In this
book, “increasing” means “nondecreasing”.)
Solution:
(a) There is a one-to-one correspondence between strictly increasing sequences
a1 < · · · < ak and subsets {a1 , . . . , ak } of size k, so the probability is nk /nk .

(b) There is a one-to-one correspondence between increasing sequences
of length k and
ways of choosing k balls with replacement, so the probability is n+k−1
k
/nk .
41. Each of n balls is independently placed into one of n boxes, with all boxes equally likely.
What is the probability that exactly one box is empty?
Solution: In order to have exactly one empty box, there must be one empty box, one
box with two balls, and n − 2 boxes with one ball (if two or more boxes each had at
least two balls, then there would not be enough balls left to avoid having more than one
empty box). Choose which box is empty, then which has two balls, then assign balls to
the boxes with one ball, and then it is determined which balls are in the box with two
balls. This gives that the probability is
n(n − 1)n(n − 1)(n − 2) . . . 3 n!(n − 1)
= .
nn 2 · nn−1
42. s A norepeatword is a sequence of at least one (and possibly all) of the usual 26 letters
a,b,c,. . . ,z, with repetitions not allowed. For example, “course” is a norepeatword, but
“statistics” is not. Order matters, e.g., “course” is not the same as “source”.
A norepeatword is chosen randomly, with all norepeatwords equally likely. Show that
the probability that it uses all 26 letters is very close to 1/e.
Solution: The number of norepeatwords having all 26 letters is the number of ordered
arrangements of 26 letters: 26!. To construct
a norepeatword with k ≤ 26 letters, we
first select k letters from the alphabet ( 26
k
selections) and then arrange them into a
word (k! arrangements). Hence there are 26


k
k! norepeatwords with k letters, with k
ranging from 1 to 26. With all norepeatwords equally likely, we have
# norepeatwords having all 26 letters
P (norepeatword having all 26 letters) =
# norepeatwords
26! 26!
= P26 26
= P26 26!
k=1 k k! k=1 k!(26−k)! k!
1
= 1 1 1 .
25!
+ 24!
+ ... + 1!
+1
18

The denominator is the first 26 terms in the Taylor series ex = 1 + x + x2 /2! + . . .,

evaluated at x = 1. Thus the probability is approximately 1/e (this is an extremely
good approximation since the series for e converges very quickly; the approximation for
e differs from the truth by less than 10−26 ).

Axioms of probability
43. Show that for any events A and B,

P (A) + P (B) − 1 ≤ P (A ∩ B) ≤ P (A ∪ B) ≤ P (A) + P (B).

For each of these three inequalities, give a simple criterion for when the inequality is
actually an equality (e.g., give a simple condition such that P (A ∩ B) = P (A ∪ B) if
and only if the condition holds).

Solution: By Theorem 1.6.2, we have P (A ∩ B) ≤ P (A ∪ B) since A ∩ B ⊆ A ∪ B. Using

the fact that P (A ∪ B) = P (A) + P (B) − P (A ∩ B) and the fact that probability is
always between 0 and 1, we have

P (A ∩ B) = P (A) + P (B) − P (A ∪ B) ≥ P (A) + P (B) − 1

and
P (A ∪ B) = P (A) + P (B) − P (A ∩ B) ≤ P (A) + P (B).

Now let us investigate when equality occurs for the above inequalities. Writing

P (A ∪ B) = P (A ∩ B) + P (A ∩ B c ) + P (Ac ∩ B),

we have that P (A ∩ B) = P (A ∪ B) if and only if P (A ∩ B c ) and P (Ac ∩ B) are both 0.

(This says that there is no probability mass in A but not in B or vice versa. The main
example where this will hold is when A and B are the same event.)
Looking at the proof of P (A) + P (B) − 1 ≤ P (A ∩ B), we see that equality will hold if
and only if P (A ∪ B) = 1. And looking at the proof of P (A ∪ B) ≤ P (A) + P (B), we
see that equality will hold if and only if P (A ∩ B) = 0.

44. Let A and B be events. The difference B − A is defined to be the set of all elements of
B that are not in A. Show that if A ⊆ B, then

P (B − A) = P (B) − P (A),

directly using the axioms of probability.

Solution: Let A ⊆ B. The events A and B − A are disjoint and their union is B, so

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

as desired.

45. Let A and B be events. The symmetric difference A4B is defined to be the set of all
elements that are in A or B but not both. In logic and engineering, this event is also
called the XOR (exclusive or ) of A and B. Show that

P (A4B) = P (A) + P (B) − 2P (A ∩ B),

directly using the axioms of probability.

Solution: We have
P (A4B) = P (A ∩ B c ) + P (Ac ∩ B),
Probability and counting 19

since A4B is the union of the disjoint events A ∩ B c and P (Ac ∩ B). Similarly, we have
P (A) = P (A ∩ B c ) + P (A ∩ B),
P (B) = P (B ∩ Ac ) + P (B ∩ A).
Adding the above two equations gives
P (A) + P (B) = P (A ∩ B c ) + P (Ac ∩ B) + 2P (A ∩ B).
Thus,
P (A4B) = P (A ∩ B c ) + P (Ac ∩ B) = P (A) + P (B) − 2P (A ∩ B).

46. Let A1 , A2 , . . . , An be events. Let Bk be the event that exactly k of the Ai occur, and
Ck be the event that at least k of the Ai occur, for 0 ≤ k ≤ n. Find a simple expression
for P (Bk ) in terms of P (Ck ) and P (Ck+1 ).
Solution: Saying that at least k of the Ai occur amounts to saying that either exactly k
of the Ai occur or at least k + 1 occur. These are disjoint possibilities. So
P (Ck ) = P (Bk ) + P (Ck+1 ),
which gives
P (Bk ) = P (Ck ) − P (Ck+1 ).

47. Events A and B are independent if P (A ∩ B) = P (A)P (B) (independence is explored

in detail in the next chapter).
(a) Give an example of independent events A and B in a finite sample space S (with
neither equal to ∅ or S), and illustrate it with a Pebble World diagram.
(b) Consider the experiment of picking a random point in the rectangle
R = {(x, y) : 0 < x < 1, 0 < y < 1},
where the probability of the point being in any particular region contained within R is
the area of that region. Let A1 and B1 be rectangles contained within R, with areas not
equal to 0 or 1. Let A be the event that the random point is in A1 , and B be the event
that the random point is in B1 . Give a geometric description of when it is true that A
and B are independent. Also, give an example where they are independent and another
example where they are not independent.
(c) Show that if A and B are independent, then
P (A ∪ B) = P (A) + P (B) − P (A)P (B) = 1 − P (Ac )P (B c ).

Solution:
(a) Consider a sample space S consisting of 4 pebbles, each with probability 1/4. Let A
consist of two of the pebbles and B consist of two of the pebbles, with A ∩ B consisting
of a single pebble, as illustrated below.

B
20

Then A and B are independent since P (A ∩ B) = 1/4 = P (A)P (B).

(b) Geometrically, independence of A and B says that the area of the intersection of
A1 and B1 is the product of the areas of A1 and B1 . An example where independence
does not hold is when A1 and B1 are disjoint (non-overlapping). An example where
independence holds is when A1 is the left half of R and B1 is the lower half. A more
general example where independence holds is when A1 = {(x, y) ∈ R : x ≤ a} and
B1 = {(x, y) ∈ R : y ≤ b}, where a and b are constants in (0, 1).

(c) Let A and B be independent. Then

P (A ∪ B) = P (A) + P (B) − P (A ∩ B) = P (A) + P (B) − P (A)P (B).

Factoring out P (A) from the terms containing it and later doing likewise with P (B c ),
we can also write P (A ∪ B) as

P (A)(1 − P (B)) + P (B) = (1 − P (Ac ))P (B c ) + 1 − P (B c ) = 1 − P (Ac )P (B c ).

48. s Arby has a belief system assigning a number PArby (A) between 0 and 1 to every event
A (for some sample space). This represents Arby’s degree of belief about how likely A
is to occur. For any event A, Arby is willing to pay a price of 1000 · PArby (A) dollars to
buy a certificate such as the one shown below:

Certificate

The owner of this certificate can redeem it for $1000 if A occurs. No

value if A does not occur, except as required by federal, state, or local
law. No expiration date.

Likewise, Arby is willing to sell such a certificate at the same price. Indeed, Arby is
willing to buy or sell any number of certificates at this price, as Arby considers it the
“fair” price.
Arby stubbornly refuses to accept the axioms of probability. In particular, suppose that
there are two disjoint events A and B with

PArby (A ∪ B) 6= PArby (A) + PArby (B).

Show how to make Arby go bankrupt, by giving a list of transactions Arby is willing
to make that will guarantee that Arby will lose money (you can assume it will be
known whether A occurred and whether B occurred the day after any certificates are
bought/sold).

Solution: Suppose first that

PArby (A ∪ B) < PArby (A) + PArby (B).

Call a certificate like the one show above, with any event C in place of A, a C-certificate.
Measuring money in units of thousands of dollars, Arby is willing to pay PArby (A) +
PArby (B) to buy an A-certificate and a B-certificate, and is willing to sell an (A ∪ B)-
certificate for PArby (A ∪ B). In those transactions, Arby loses PArby (A) + PArby (B) −
PArby (A ∪ B) and will not recoup any of that loss because if A or B occurs, Arby will
have to pay out an amount equal to the amount Arby receives (since it’s impossible for
both A and B to occur).

Now suppose instead that

PArby (A ∪ B) > PArby (A) + PArby (B).

Probability and counting 21

Measuring money in units of thousands of dollars, Arby is willing to sell an A-certificate

for PArby (A), sell a B-certificate for PArby (B), and buy a (A∪B)-certificate for PArby (A∪
B). In so doing, Arby loses PArby (A∪B)−(PArby (A)+PArby (B)), and Arby won’t recoup
any of this loss, similarly to the above. (In fact, in this case, even if A and B are not
disjoint, Arby will not recoup any of the loss, and will lose more money if both A and
B occur.)

By buying/selling a sufficiently large number of certificates from/to Arby as described

above, you can guarantee that you’ll get all of Arby’s money; this is called an arbitrage
opportunity. This problem illustrates the fact that the axioms of probability are not
arbitrary, but rather are essential for coherent thought (at least the first axiom, and
the second with finite unions rather than countably infinite unions).

Arbitrary axioms allow arbitrage attacks; principled properties and perspectives on prob-
ability potentially prevent perdition.

Inclusion-exclusion
49. A fair die is rolled n times. What is the probability that at least 1 of the 6 values never
appears?

Solution: Let Aj be the event that the value j never appears. Then
 n
6−k
P (A1 ∩ A2 ∩ · · · ∩ Ak ) =
6

for 1 ≤ k ≤ 5, since there is a 6−k

6
chance that any particular roll is not in {1, 2, . . . , k}.
By inclusion-exclusion and symmetry
 n !  !  !  ! 
n n n n
5 6 4 6 3 6 2 6 1
P (A1 ∪ · · · ∪ A6 ) = 6 − + − +
6 2 6 3 6 4 6 5 6
 n  n  n  n  n
5 2 1 1 1
=6 − 15 + 20 − 15 +6 .
6 3 2 3 6

Note that this reduces to 1 for n ∈ {1, 2, . . . , 5}, as it must since there is no way to
obtain all 6 possible values in fewer than 6 tosses.

50. s A card player is dealt a 13-card hand from a well-shuffled, standard deck of cards.
What is the probability that the hand is void in at least one suit (“void in a suit” means
having no cards of that suit)?

Solution: Let S, H, D, C be the events of being void in Spades, Hearts, Diamonds, Clubs,
respectively. We want to find P (S ∪ D ∪ H ∪ C). By inclusion-exclusion and symmetry,

P (S ∪ D ∪ H ∪ C) = 4P (S) − 6P (S ∩ H) + 4P (S ∩ H ∩ D) − P (S ∩ H ∩ D ∩ C).

(39
13)
The probability of being void in a specific suit is . The probability of being void in
(52
13)
(26
13) 1
2 specific suits is . The probability of being void in 3 specific suits is 52 . And the
(52
13) (13)
last term is 0 since it’s impossible to be void in everything. So the probability is
39 26



13 13 4
4 52
− 6 52
+ 52
≈ 0.051.
13 13 13
22

51. s For a group of 7 people, find the probability that all 4 seasons (winter, spring,
summer, fall) occur at least once each among their birthdays, assuming that all seasons
are equally likely.

Solution: Let Ai be the event that there are no birthdays in the ith season (with respect
to some ordering of the seasons). The probability that all seasons occur at least once is
1 − P (A1 ∪ A2 ∪ A3 ∪ A4 ). Note that A1 ∩ A2 ∩ A3 ∩ A4 = ∅ (the most extreme case is
when everyone is born in the same season). By inclusion-exclusion and symmetry,
! !
4 4
P (A1 ∪ A2 ∪ A3 ∪ A4 ) = 4P (A1 ) − P (A1 ∩ A2 ) + P (A1 ∩ A2 ∩ A3 ).
2 3

We have P (A1 ) = (3/4)7 , P (A1 ∩ A2 ) = (2/4)7 , P (A1 ∩ A2 ∩ A3 ) = (1/4)7 , so

 7 !
3 6 4
1 − P (A1 ∪ A2 ∪ A3 ∪ A4 ) = 1 − 4 − 7 + 7 ≈ 0.513.
4 2 4

52. A certain class has 20 students, and meets on Mondays and Wednesdays in a classroom
with exactly 20 seats. In a certain week, everyone in the class attends both days. On
both days, the students choose their seats completely randomly (with one student per
seat). Find the probability that no one sits in the same seat on both days of that week.

Solution: This problem is similar to the matching problem (Example 1.6.4). Label the
students from 1 to 20, and then let Ai be the event that student i sits in the same seat
on both days. Then
1 18! 1
P (Ai ) = , P (Ai ∩ Aj ) = =
20 20! 19 · 20
for i 6= j, etc. By inclusion-exclusion, simplifying as in the solution to the matching
problem,
1 1 1
P (A1 ∪ · · · ∪ A20 ) = 1 − + − ··· − .
2! 3! 20!
Thus, the probability that no one sits in the same seat on both days is
1 1 1 1 1 1
− + − + ··· + ≈ ≈ 0.37.
0! 1! 2! 3! 20! e
53. Fred needs to choose a password for a certain website. Assume that he will choose an
8-character password, and that the legal characters are the lowercase letters a, b, c, . . . ,
z, the uppercase letters A, B, C, . . . , Z, and the numbers 0, 1, . . . , 9.

(a) How many possibilities are there if he is required to have at least one lowercase letter
in his password?

(b) How many possibilities are there if he is required to have at least one lowercase
letter and at least one uppercase letter in his password?

(c) How many possibilities are there if he is required to have at least one lowercase
letter, at least one uppercase letter, and at least one number in his password?

Solution:

(a) There are 628 possible passwords if there are no restrictions, but we must exclude
the 368 passwords that consist only of numbers and uppercase letters. So there are

628 − 368 ≈ 2.155 × 1014

possibilities.

(b) Excluding the 368 passwords with no uppercase letters and the 368 passwords with
Probability and counting 23

no lowercase letters, but being careful not to exclude the 108 numerical-only passwords
twice, we have that there are

628 − 368 − 368 + 108 ≈ 2.127 × 1014

possibilities.

(c) Again we use an inclusion-exclusion type argument. We exclude passwords with

no uppercase letters, then with no lowercase letters, then with no numbers, but have
to add back some terms to reflect the fact that some passwords are uppercase- only,
lowercase-only, or numerical-only. This gives that there are

628 − 368 − 368 − 528 + 108 + 268 + 268 ≈ 1.597 × 1014

possibilities.

54. s Alice attends a small college in which each class meets only once a week. She is
deciding between 30 non-overlapping classes. There are 6 classes to choose from for each
day of the week, Monday through Friday. Trusting in the benevolence of randomness,
Alice decides to register for 7 randomly selected classes out of the 30, with all choices
equally likely. What is the probability that she will have classes every day, Monday
through Friday? (This problem can be done either directly using the naive definition of
probability, or using inclusion-exclusion.)

Solution: We will solve this both by direct counting and using inclusion-exclusion.

Direct Counting Method : There are two general ways that Alice can have class every
day: either she has 2 days with 2 classes and 3 days with 1 class, or she has 1 day with 3
classes, and has 1 class on each of the other 4 days. The number of possibilities for the


2
former is 52 62 63 (choose the 2 days when she has 2 classes, and then select 2 classes
on those


days and 1 class for the other days). The number of possibilities for the latter
is 51 63 64 . So the probability is

5

6
2 5

6
4
2 2
63 + 1 3
6 114
30

= ≈ 0.302.
7
377

Inclusion-Exclusion Method : We will use inclusion-exclusion to find the probability of

the complement, which is the event that she has at least one day with no classes. Let
Bi = Aci . Then
X X X
P (B1 ∪ B2 · · · ∪ B5 ) = P (Bi ) − P (Bi ∩ Bj ) + P (Bi ∩ Bj ∩ Bk )
i i<j i<j<k

(terms with the intersection of 4 or more Bi ’s are not needed since Alice must have
classes on at least 2 days). We have
24 18 12




7 7 7
P (B1 ) = 30 , P (B1

∩ B2 ) = 30 , P (B1

∩ B2 ∩ B3 ) = 30


7 7 7

and similarly for the other intersections. So

! !
24 18 12




7 5 7 5 7 263
P (B1 ∪ · · · ∪ B5 ) = 5 30

− 30

+ 30

= .
7
2 7
3 7
377

Therefore,
114
P (A1 ∩ A2 ∩ A3 ∩ A4 ∩ A5 ) = ≈ 0.302.
377
24

55. A club consists of 10 seniors, 12 juniors, and 15 sophomores. An organizing committee

of size 5 is chosen randomly (with all subsets of size 5 equally likely).

(a) Find the probability that there are exactly 3 sophomores in the committee.

(b) Find the probability that the committee has at least one representative from each
of the senior, junior, and sophomore classes.

Solution:

(a) For a favorable outcome, we must choose 3 sophomores and 2 non-sophomores:

15 22



3
P (exactly 3 sophomores) = 37

2 ≈ 0.241.
5

(b) Let A2 , A3 , A4 be the events that there are representatives from the sophomore,
junior, and senior classes respectively. By inclusion-exclusion,

P (Ac2 ∪ Ac3 ∪ Ac4 ) = P (Ac2 ) + P (Ac3 ) + P (Ac4 ) − P (Ac2 ∩ Ac3 ) − P (Ac2 ∩ Ac4 ) − P (Ac3 ∩ Ac4 )
22 25 27 10 12 15







5 5 5 5 5 5 156147
= 37
+ 37
+ 37
− 37
− 37
− 37
= ,
5 5 5 5 5 5
435897
156147
so P (A2 ∩ A3 ∩ A4 ) = 1 − 435897
≈ 0.642.

Mixed practice
56. For each part, decide whether the blank should be filled in with =, <, or >, and give a
clear explanation. In (a) and (b), order doesn’t matter.

(a) (number of ways to choose 5 people out of 10) (number of ways to choose 6
people out of 10)

(b) (number of ways to break 10 people into 2 teams of 5) (number of ways to

break 10 people into a team of 6 and a team of 4)

(c) (probability that all 3 people in a group of 3 were born on January 1) (proba-
bility that in a group of 3 people, 1 was born on each of January 1, 2, and 3)

Martin and Gale play an exciting game of “toss the coin,” where they toss a fair coin
until the pattern HH occurs (two consecutive Heads) or the pattern TH occurs (Tails
followed immediately by Heads). Martin wins the game if and only if HH occurs before
TH occurs.

(d) (probability that Martin wins) 1/2

Solution:

(a) (number of ways to choose 5 people out of 10) > (number of ways to choose 6 people
out of 10)

n! = n · (n − 1)!, we see that 10 10!

> 10 10!



Explanation: Using the fact that 5
= 5!5! 6
= 4!6!
n


reduces to 6 > 5. In general, k is maximized at k = n/2 when n is even.

(b) (number of ways to break 10 people into 2 teams of 5) < (number of ways to break
10 people into a team of 6 and a team of 4)

Explanation: The righthand side is 10

6
since the choice of the team of 6 determines
the team of 4. But the lefthand side is 21 10


5
since choosing a team of 5 is equivalent to
choosing the complementary 5 people. The inequality then reduces to 3 < 5.
Probability and counting 25

(c) (probability that all 3 people in a group of 3 were born on January 1) < (probability
that in a group of 3 people, 1 was born on each of January 1, 2, and 3)

Explanation: The righthand side is 6 times as large as the lefthand side, since there are
3! ways the righthand event can occur, but only 1 way that the people could all be born
on January 1.

Martin and Gale play an exciting game of “toss the coin,” where they toss a fair coin
until the pattern HH occurs (two consecutive Heads) or the pattern TH occurs (Tails
followed immediately by Heads). Martin wins the game if and only if HH occurs before
TH occurs.

(d) (probability that Martin wins) < 1/2

Explanation: Consider the first toss. If it’s Tails, we’re guaranteed to see TH before we
see HH. If it’s Heads, we could still see either TH or HH first. Hence, the probability of
HH occurring sooner than TH is less than 1/2.
Alternatively, consider the first two tosses. If it’s HH, then Martin has already won. If
it’s TH, then Gale has already won. If it’s HT or TT, then Gale will eventually win (she
will win the next time that an H appears). So
1 1
P (Martin wins) = < .
4 2

57. Take a deep breath before attempting this problem. In the book Innumeracy, John Allen
Paulos writes:
Now for better news of a kind of immortal persistence. First, take a deep
breath. Assume Shakespeare’s account is accurate and Julius Caesar gasped
[“Et tu, Brute!”] before breathing his last. What are the chances you just
inhaled a molecule which Caesar exhaled in his dying breath?

Assume that one breath of air contains 1022 molecules, and that there are 1044 molecules
in the atmosphere. (These are slightly simpler numbers than the estimates that Paulos
gives; for the purposes of this problem, assume that these are exact. Of course, in reality
there are many complications such as different types of molecules in the atmosphere,
chemical reactions, variation in lung capacities, etc.)

Suppose that the molecules in the atmosphere now are the same as those in the at-
mosphere when Caesar was alive, and that in the 2000 years or so since Caesar, these
molecules have been scattered completely randomly through the atmosphere. Also as-
sume that Caesar’s last breath was sampled without replacement but that your breathing
is sampled with replacement (without replacement makes more sense but with replace-
ment is easier to work with, and is a good approximation since the number of molecules
in the atmosphere is so much larger than the number of molecules in one breath).

Find the probability that at least one molecule in the breath you just took was shared
with Caesar’s last breath, and give a simple approximation in terms of e.
Hint: As discussed in the math appendix, (1 + nx )n ≈ ex for n large.

Solution: Let N = 1044 and n = 1022 . Each molecule breathed in has probability (N −
n)/N of not being from Caesar’s last breath. The molecules breathed in are independent
if we assume sampling with replacement. So the probability of at least one molecule being
shared with Caesar’s last breath is
1022
(N − n)n

 n n 1 1
1− = 1 − 1 − = 1 − 1 − ≈1− .
Nn N 1022 e
Amazingly, this is about a 63% chance!
26

58. A widget inspector inspects 12 widgets and finds that exactly 3 are defective. Unfortu-
nately, the widgets then get all mixed up and the inspector has to find the 3 defective
widgets again by testing widgets one by one.

(a) Find the probability that the inspector will now have to test at least 9 widgets.

(b) Find the probability that the inspector will now have to test at least 10 widgets.

Solution:

(a) Imagine that the widgets are lined up in a row, ready to be tested (in that order).
Let’s find the probability of the complement. The event that the inspector has to test at
most 8 widgets is the same as the event
that
all 3 defective widgets are among the first 8
widgets in line. This has probability 83 / 12
3
by the naive definition: the denominator is
the number of choices for where to place the defective widgets, and the numerator is the
number of such choices such that the defective widgets are among the first 8 widgets.
So the desired probability is
8


3 41
1 − 12
= ≈ 0.745.
3
55

Alternatively, note that the inspector has to test at most 8 widgets if and only if none
of the last 4 widgets are defective. Choosing which particular widgets are among the
last 4 widgets, the desired probability is
9


4
1− 12

≈ 0.745,
4

which agrees with the result of the earlier approach.

(b) There are two disjoint ways that the inspector could be done after at most 9 widgets:
either all 3 defective widgets have turned up among the first 9 widgets, or none of them
have turned up after inspecting the first 9. So the desired probability is
9


3 1 27
1 − 12
− 12
= ≈ 0.614.
3 3
44

59. There are 15 chocolate bars and 10 children. In how many ways can the chocolate bars
be distributed to the children, in each of the following scenarios?

(a) The chocolate bars are fungible (interchangeable).

(b) The chocolate bars are fungible, and each child must receive at least one.
Hint: First give each child a chocolate bar, and then decide what to do with the rest.
(c) The chocolate bars are not fungible (it matters which particular bar goes where).

(d) The chocolate bars are not fungible, and each child must receive at least one.
Hint: The strategy suggested in (b) does not apply. Instead, consider randomly giving
the chocolate bars to the children, and apply inclusion-exclusion.

Solution:

(a) If we only care how many chocolate bars each child receives, not which specific bars
go where, then we are in the realm of Bose-Einstein (with chocolate bars as indistin-
guishable particles and children as distinguishable boxes). So there are
! !
10 + 15 − 1 24
= = 1307504
15 15
Probability and counting 27

possibilities.

(b) As in the hint, first give each child one chocolate bar (there is only one way to do
this, if the bars are treated as if they were indistinguishable). This leaves 5 bars. So by
Bose-Einstein, there are
! !
10 + 5 − 1 14
= = 2002
5 5

possibilities.

(c) By the multiplication rule, there are 1015 possibilities.

(d) Consider randomly distributing the bars to the children, with all of the 1015 pos-
sibilities equally likely. Let Ai be the event that child i does not receive any chocolate
bars, and note that
 15
10 − k
P (A1 ∩ A2 ∩ · · · ∩ Ak ) = ,
10
for 1 ≤ k ≤ 10. By inclusion-exclusion and symmetry, the probability that at least one
child does not receive a bar is
 15 !  !  ! 
15 15 15
9 10 8 10 7 10 1
10 − + − ··· + .
10 2 10 3 10 9 10

By the naive definition of probability, this is also (1015 − a)/1015 , where a is the number
of possibilities such that each child receives at least one bar. So
! !!
15 15 10 15 10
a = 10 − 10 · 9 − 8 + ··· + ≈ 4.595 × 1013 .
2 9

60. Given n ≥ 2 numbers (a1 , a2 , . . . , an ) with no repetitions, a bootstrap sample is a se-

quence (x1 , x2 , . . . , xn ) formed from the aj ’s by sampling with replacement with equal
probabilities. Bootstrap samples arise in a widely used statistical method known as
the bootstrap. For example, if n = 2 and (a1 , a2 ) = (3, 1), then the possible bootstrap
samples are (3, 3), (3, 1), (1, 3), and (1, 1).
(a) How many possible bootstrap samples are there for (a1 , . . . , an )?
(b) How many possible bootstrap samples are there for (a1 , . . . , an ), if order does not
matter (in the sense that it only matters how many times each aj was chosen, not the
order in which they were chosen)?
(c) One random bootstrap sample is chosen (by sampling from a1 , . . . , an with replace-
ment, as described above). Show that not all unordered bootstrap samples (in the sense
of (b)) are equally likely. Find an unordered bootstrap sample b1 that is as likely as
possible, and an unordered bootstrap sample b2 that is as unlikely as possible. Let p1 be
the probability of getting b1 and p2 be the probability of getting b2 (so pi is the prob-
ability of getting the specific unordered bootstrap sample bi ). What is p1 /p2 ? What is
the ratio of the probability of getting an unordered bootstrap sample whose probability
is p1 to the probability of getting an unordered sample whose probability is p2 ?

Solution:

(a) By the multiplication rule, there are nn possibilities.

(b) By Bose-Einstein, there are n+n−1 = 2n−1

n n
possibilities.

(c) We can take b1 = [a1 , a2 , . . . , an ] and b2 = [a1 , a1 , . . . , a1 ] (using square brackets

to distinguish these unordered lists from the ordered bootstrap samples); these are the
extreme cases since the former has n! orders in which it could have been generated,
28

while the latter only has 1 such order. Then p1 = n!/nn , p2 = 1/nn , so p1 /p2 = n!.
There is only 1 unordered sample of the form of b1 but there are n of the form of b2 , so
the ratio of the probability of getting a sample whose probability is p1 to the probability
of getting a sample whose probability is p2 is (n!/nn )/(n/nn ) = (n − 1)!.
61. s There are 100 passengers lined up to board an airplane with 100 seats (with each seat
assigned to one of the passengers). The first passenger in line crazily decides to sit in
a randomly chosen seat (with all seats equally likely). Each subsequent passenger takes
their assigned seat if available, and otherwise sits in a random available seat. What is
the probability that the last passenger in line gets to sit in their assigned seat? (This is
a common interview problem, and a beautiful example of the power of symmetry.)
Hint: Call the seat assigned to the jth passenger in line “seat j” (regardless of whether
the airline calls it seat 23A or whatever). What are the possibilities for which seats
are available to the last passenger in line, and what is the probability of each of these
possibilities?

Solution: The seat for the last passenger is either seat 1 or seat 100; for example, seat
42 can’t be available to the last passenger since the 42nd passenger in line would have
sat there if possible. Seat 1 and seat 100 are equally likely to be available to the last
passenger, since the previous 99 passengers view these two seats symmetrically. So the
probability that the last passenger gets seat 100 is 1/2.

62. In the birthday problem, we assumed that all 365 days of the year are equally likely
(and excluded February 29). In reality, some days are slightly more likely as birthdays
than others. For example, scientists have long struggled to understand why more babies
are born 9 months after a holiday. Let p = (p1 , p2 , . . . , p365 ) be the vector of birthday
probabilities, with pj the probability of being born on the jth day of the year (February
29 is still excluded, with no offense intended to Leap Dayers).

The kth elementary symmetric polynomial in the variables x1 , . . . , xn is defined by

X
ek (x1 , . . . , xn ) = xj1 . . . xjk .
1≤j1 <j2 <···<jk ≤n

This just says to add up all of the nk terms

we can get by choosing and multiplying
k of the variables. For example, e1 (x1 , x2 , x3 ) = x1 + x2 + x3 , e2 (x1 , x2 , x3 ) = x1 x2 +
x1 x3 + x2 x3 , and e3 (x1 , x2 , x3 ) = x1 x2 x3 .
Now let k ≥ 2 be the number of people.
(a) Find a simple expression for the probability that there is at least one birthday match,
in terms of p and an elementary symmetric polynomial.
(b) Explain intuitively why it makes sense that P (at least one birthday match) is min-
1
imized when pj = 365 for all j, by considering simple and extreme cases.
(c) The famous arithmetic mean-geometric mean inequality says that for x, y ≥ 0,
x+y √
≥ xy.
2
This inequality follows from adding 4xy to both sides of x2 − 2xy + y 2 = (x − y)2 ≥ 0.
Define r = (r1 , . . . , r365 ) by r1 = r2 = (p1 + p2 )/2, rj = pj for 3 ≤ j ≤ 365. Using the
arithmetic mean-geometric mean bound and the fact, which you should verify, that

ek (x1 , . . . , xn ) = x1 x2 ek−2 (x3 , . . . , xn ) + (x1 + x2 )ek−1 (x3 , . . . , xn ) + ek (x3 , . . . , xn ),

show that

P (at least one birthday match|p) ≥ P (at least one birthday match|r),

with strict inequality if p 6= r, where the “given r” notation means that the birthday
Probability and counting 29

probabilities are given by r. Using this, show that the value of p that minimizes the
1
probability of at least one birthday match is given by pj = 365 for all j.

Solution:

(a) One way to have no match is for the birthdays to be on days 1, 2, . . . , k, in any
order. This has probability k!p1 p2 . . . pk . Similarly, we can have any other selection of k
distinct days. Thus,

P (at least one birthday match) = 1 − k!ek (p).

(b) An extremely extreme case would be if pj = 1 for some j, i.e., everyone is always
born on the same day; then a match is guaranteed if there are at least 2 people. For
another simple case, suppose that there are only 2 days in a year, with probabilities p
and q = 1 − p. For 2 people, the probability of a match is p2 + q 2 = p2 + (1 − p)2 , which is
minimized at p = 1/2. In the general case, imagine starting with probabilities 1/365 for
all days and shifting some “probability mass” from some pi to another pj . This makes
it less likely to have a match on day i and more likely for there to be a match on day j,
but from the above it makes sense that the latter outweighs the former.

(c) The identity for ek (x1 , . . . , xn ) is true since it is just partitioning the terms into 3
cases: terms with both x1 and x2 , terms with one but not the other, and terms with
neither x1 nor x2 . Let n = 365. Note that p1 + p2 = r1 + r2 and by the arithmetic
mean-geometric mean inequality, p1 p2 ≤ ((p1 + p2 )/2)2 = r1 r2 . So

ek (p1 , . . . , xn ) = p1 p2 ek−2 (p3 , . . . , pn ) + (p1 + p2 )ek−1 (p3 , . . . , pn ) + ek (p3 , . . . , pn )

≤ r1 r2 ek−2 (r3 , . . . , rn ) + (r1 + r2 )ek−1 (r3 , . . . , rn ) + ek (r3 , . . . , rn )
= ek (r1 , . . . , rn ).

So by (a), the probability of a birthday match when the probabilities are p is at least
as large was when they are r. The inequality is strict unless p1 = p2 .

Now let p0 be a vector of birthday probabilities that minimizes the probability of at

least one birthday match. If two components of p0 are not equal, the above shows that
we could replace those two components by their average in order to obtain a smaller
chance of a match, but this would contradict p0 minimizing the probability of a match.
Thus, p0 has all components equal.