A Collection of Dice Problems

with solutions and useful appendices

(a work continually in progress)

version March 25, 2026

Matthew M. Conroy
list2 “at" madandmoonly dot com
[Link]
A Collection of Dice Problems Matthew M. Conroy

Thanks
Many people have sent corrections, comments and suggestions, including Ryan Allen, Julien Beasley,
Rasher Bilbo, Michael Buse, Stephen B, Paul Elvidge, George Fullman, Amit Kumar Goel, Steven
Hanes, Nick Hobson, Marc Holtz, Lin Zi Khang, Manuel Klein, Dimitris Konomis, David Korsnack,
Peter Landweber, Isaac Lee, Jason Cheuk-Man Leung, Matthew Liu, Paul Micelli, Albert Natian,
João Neto, Khizar Qureshi, Micha Stajszczak , Dave TeBokkel, Erik Vigren, Yichuan Xu, Saim Wani
and Elie Wolfe. Thanks, everyone.

Number of problems by year

Here is a rough plot of the growth of this collection, showing the number of problems that were
in a version of this document in some years.
80
70
number of problems

60
50
40
30

2005 2010 2015 2020 2025

year

2
Chapter 1

Introduction and Notes

This is a (slowly) growing collection of dice-related mathematical problems, with accompany-

ing solutions. Some are simple exercises suitable for beginners, while others require more sophis-
ticated techniques.
Many dice problems have an advantage over some other problems of probability in that they
can be investigated experimentally. This gives these types of problems a certain helpful down-to-
earth feel.
Please feel free to comment, criticize, or contribute additional problems.

1.0.1 What are dice?

In the real world, dice (the plural of die) are polyhedra made of plastic, wood, ivory, or other
hard material. Each face of the die is numbered, or marked in some way, so that when the die is
cast onto a smooth, flat surface and allowed to come to rest, a particular number is specified.
Mathematically, we can consider a die to be a random variable that takes on only finitely many
distinct values. Usually, these values will constitute a set of positive integers 1, 2, ..., n; in such
cases, we will refer to the die as n-sided.

1.0.2 Terminology
A fair die is one for which each face appears with equal likelihood. A non-fair die is called fixed.
The phrase standard die will refer to a fair, six-sided die, whose faces are numbered one through
six. If not otherwise specified, the term die will refer to a standard die.

3
Chapter 2

Problems

2.1 Standard Dice

1. On average, how many times must a 6-sided die be rolled until a 6 turns up?

2. On average, how many times must a 6-sided die be rolled until a 6 turns up twice in a row?

3. On average, how many times must a 6-sided die be rolled until the sequence 65 appears (i.e.,
a 6 followed by a 5)?

4. On average, how many times must a 6-sided die be rolled until there are two rolls in a row
that differ by 1 (such as a 2 followed by a 1 or 3, or a 6 followed by a 5)? What if we roll until
there are two rolls in a row that differ by no more than 1 (so we stop at a repeated roll, too)?

5. We roll a 6-sided die n times. What is the probability that all faces have appeared?

6. We roll a 6-sided die n times. What is the probability that all faces have appeared in order, in
some six consecutive rolls (i.e., what is the probability that the subsequence 123456 appears
among the n rolls)?

7. We roll a 6-sided die n times. What is the probability that all faces have appeared in some or-
der in some six consecutive rolls? What is the expected number of rolls until such a sequence
appears?

8. Person A rolls n dice and person B rolls m dice. What is the probability that they have a
common face showing (e.g., person A rolled a 2 and person B also rolled a 2) among all their
dice?

9. On average, how many times must a 6-sided die be rolled until all sides appear at least once?
What about for an n-sided die?

10. On average, how many times must a 6-sided die be rolled until all sides appear at least twice?

11. On average, how many times must a pair of 6-sided dice be rolled until all sides appear at
least once?

12. Suppose we roll n dice. What is the expected number of distinct faces that appear?

4
A Collection of Dice Problems Matthew M. Conroy

13. Suppose we roll n dice and keep the highest one. What is the distribution of values?

14. Suppose we can roll a 6-sided die up to n times. At any point we can stop, and that roll
becomes our “score". Our goal is to get the highest possible score, on average. How should
we decide when to stop?

15. How many dice must be rolled to have at least a 95% chance of rolling a six?

16. How many dice must be rolled to have at least a 95% chance of rolling a one and a two? What
about a one, a two, and a three? What about a one, a two, a three, a four, a five and a six?

17. How many dice should be rolled to maximize the probability of rolling exactly one six? two
sixes? n sixes?

18. Suppose we roll a fair die 100 times. What is the probability of a run of at least 10 sixes?

19. Suppose we roll a fair die until some face has appeared twice. For instance, we might have a
run of rolls 12545 or 636. How many rolls on average would we make? What if we roll until
a face has appeared three times?

20. Suppose we roll a fair die 10 times. What is the probability that the sequence of rolls is non-
decreasing (i.e., the next roll is never less than the current roll)?

21. Suppose a pair of dice are thrown, and then thrown again. What is the probability that the
faces appearing on the second throw are the same as the first?
What if three dice are used? Or six?

22. What is the most probable: rolling at least one six with six dice, at least two sixes with twelve
dice, or at least three sixes with eighteen dice? (This is an old problem, frequently connected
with Isaac Newton.)

23. Suppose we roll n dice, remove all the dice that come up 1, and roll the rest again. If we
repeat this process, eventually all the dice will be eliminated. How many rolls, on average,
will we make? Show, for instance, that on average fewer than O(log n) throws occur.

24. Suppose we roll a die 6k times. What is the probability that each possible face comes up an
equal number of times (i.e., k times)? Find an asymptotic expression for this probability in
terms of k.

25. Call a “consecutive difference" the absolute value of the difference between two consecutive
rolls of a die. For example, the sequence of rolls 14351 has the corresponding sequence of
consecutive differences 3, 1, 2, 4. What is the expected number of times we need to roll a die
until all 6 consecutive differences have appeared?

26. Suppose we roll six dice repeatedly as long as there are repetitions among the rolled faces,
rerolling all non-distinct face dice. For example, our first roll might give 112245, in which
case we would keep the 45 and roll the other four. Suppose those four turn up 1346 so the
set of faces is 134456, and so we re-roll the two 4 dice, and continue. What is the expected
number of rolls until all faces are distinct?

5
A Collection of Dice Problems Matthew M. Conroy

27. Suppose we roll n s-sided dice. Let ai be the number of times face i appears. What is the
s
Y
expected value of ai ?
i=1

28. What is the probability that, if we roll two dice, the product of the faces will start with the
digit ’1’? What if we roll three dice, or, ten dice? What is going on?

29. Suppose we roll an s-sided die repeatedly and multiply the results. What is the expected
number of rolls until the product is a perfect square?

2.2 Dice Sums

30. Show that the probability of rolling 14 is the same whether we throw 3 dice or 5 dice. Are
there other examples of this phenomenon?

31. Show that the probability of rolling a sum of 9 with a pair of 5-sided dice is the same as rolling
a sum of 9 with a pair of 10-sided dice. Are there other examples of this phenomenon? Can
we prove there are infinitely many such?

32. Suppose we roll n dice and sum the highest 3. What is the probability that the sum is 18?

33. Four fair, 6-sided dice are rolled. The highest three are summed. What is the distribution of
the sum?

34. Three fair, n-sided dice are rolled. What is the probability that the sum of two of the faces
rolled equals the value of the other rolled face?

35. A fair, n-sided die is rolled until a roll of k or greater appears. All rolls are summed. What is
the expected value of the sum?

36. A pair of dice is rolled repeatedly. What is the expected number of rolls until all eleven
possible sums have appeared? What if three dice are rolled until all sixteen possible sums
have appeared?

37. A die is rolled repeatedly and summed. What can you say about the expected number of
rolls until the sum is greater than or equal to n?

38. A die is rolled repeatedly and summed. Show that the expected number of rolls until the
sum is a multiple of n is n.

39. A fair, n-sided die is rolled and summed until the sum is at least n. What is the expected
number of rolls?

40. A die is rolled and summed repeatedly. What is the probability that the sum will ever be a
given value x? What is the limit of this probability as x → ∞?

41. A die is rolled and summed repeatedly until the sum is 100 or more. What is the most likely
last roll? What if we roll two dice at time? Three, etc.?

6
A Collection of Dice Problems Matthew M. Conroy

42. A die is rolled and summed repeatedly. Let x be a positive integer. What is the probability
that the sum will ever be x or x + 1? What is the probability that the sum will ever be x, x + 1,
or x + 2? Etc.?

43. A die is rolled once; call the result N . Then N dice are rolled once and summed. What is
the distribution of the sum? What is the expected value of the sum? What is the most likely
value?

What the heck, take it one more step: roll a die; call the result N . Roll N dice once and
sum them; call the result M . Roll M dice once and sum. What’s the distribution of the sum,
expected value, most likely value?

44. A die is rolled once. Call the result N . Then, the die is rolled N times, and those rolls which
are equal to or greater than N are summed (other rolls are not summed). What is the distri-
bution of the resulting sum? What is the expected value of the sum?

45. Suppose n six-sided dice are rolled and summed. For each six that appears, we sum the six,
and reroll that die and sum, and continue to reroll and sum until we roll something other
than a six with that die. What is the expected value of the sum? What is the distribution of
the sum?

46. A die is rolled until all sums from 1 to x are attainable from some subset of rolled faces. For
example, if x = 3, then we might roll until a 1 and 2 are rolled, or until three 1s appear, or
until two 1s and a 3. What is the expected number of rolls?

47. How long, on average, do we need to roll a die and sum the rolls until the sum is a perfect
square (1, 4, 9, 16, . . . )?

48. How long, on average, do we need to roll a die and sum the rolls until the sum is prime?
What if we roll until the sum is composite?

2.3 Non-Standard Dice

49. Show that the probability of rolling doubles with a non-fair (“fixed") die is greater than with
a fair die.

50. Is it possible to have a non-fair six-sided die such that the probability of rolling 2, 3, 4, 5, and
6 is the same whether we roll it once or twice (and sum)? What about for other numbers of
sides?

51. Find a pair of 6-sided dice, labelled with positive integers differently from the standard dice,
so that the sum probabilities are the same as for a pair of standard dice.

52. Is it possible to have two non-fair n-sided dice, with sides numbered 1 through n, with the
property that their sum probabilities are the same as for two fair n-sided dice?

53. Is it possible to have two non-fair 6-sided dice, with sides numbered 1 through 6, with a
uniform sum probability? What about n-sided dice?

7
A Collection of Dice Problems Matthew M. Conroy

54. Suppose that we renumber three fair 6-sided dice (A, B, C) as follows: A = {2, 2, 4, 4, 9, 9},B =
{1, 1, 6, 6, 8, 8}, and C = {3, 3, 5, 5, 7, 7}.

(a) Find the probability that die A beats die B; die B beats die C; die C beats die A.

(b) Discuss.

55. Find every six-sided die with sides numbered from the set {1,2,3,4,5,6} such that rolling the
die twice and summing the values yields all values between 2 and 12 (inclusive). For instance,
the die numbered 1,2,4,5,6,6 is one such die. Consider the sum probabilities of these dice. Do
any of them give sum probabilities that are “more uniform" than the sum probabilities for
a standard die? What if we renumber two dice differently - can we get a uniform (or more
uniform than standard) sum probability?

56. If we roll a standard die twice and sum, the probability that the sum is prime is 15 36 = 12 . If
5

we renumber the faces of the die, with all faces being different, what is the largest probability
of a prime sum that can be achieved?

57. Let’s make pairs of dice that only sum to prime values. If we minimize the sum of all the
values on the faces, what dice do we get for 2-sided dice, 3-sided dice, etc.?

58. What if we want to make a die that when rolled twice and summed only yields primes? If
we want all the faces to be different, we cannot do that. But, what if we roll twice, sum and
add one?

59. Show that you cannot have a pair of dice with more than two sides that only gives sums that
are Fibonacci numbers.

2.4 Games with Dice

60. Two players each roll two dice, first player A, then player B. If player A rolls a sum of 6, they
win. If player B rolls a sum of 7, they win. They take turns, back and forth, until someone
wins. What is the probability that player A wins?

61. In the previous problem, we find out that the game is not fair. Are there sum targets for
player A and player B that would make the game fair? What about using a different number
of dice, or allowing targets to include more than one sum?

62. Two players each roll two dice. Player A is trying to roll a sum of 6, player B is trying to roll a
sum of 7. Player A starts, and rolls once. Then Player B rolls twice, then Player A rolls twice,
and they repeat, both players rolling twice in succession until someone rolls their target sum.
What is the probability of winning for each player?

63. Two players each roll a die. Player 1 rolls a fair m-sided die, while player 2 rolls a fair n sided
die, with m > n. The winner is the one with the higher roll. What is the probability that
Player 1 wins? What is the probability of a tie? If the players continue rolling in the case of a
tie until they do not tie, which player has the higher probability of winning? If the tie means
a win for Player 1 (or player 2), what is their probability of winning?

8
A Collection of Dice Problems Matthew M. Conroy

64. Two players each start with 12 tokens. They roll three dice until the sum is either 11 or 14. If
the sum is 14, player A gives a token to player B; if the sum is 11, player B gives a token to
player A. They repeat this process until one player, the winner, has all the tokens. What is
the probability that player A wins?

65. Two players each start a game with a score of zero, and they alternate rolling dice once to
add to their scores. Player A rolls three six-sided dice on each turn, while player B always
gets 11 points on their turn. If the starting player is chosen by the toss of a coin, what is the
probability that player A will be the first to 100 points?

66. Craps The game of craps is perhaps the most famous of all dice games. The player begin
by throwing two standard dice. If the sum of these dice is 7 or 11, the player wins. If the
sum is 2,3 or 12, the player loses. Otherwise, the sum becomes the player’s point. The player
continues to roll until either the point comes up again, in which case the player wins, or the
player throws 7, in which case they lose. The natural question is: what is a player’s probability
of winning?

67. Non-Standard Craps We can generalize the games of craps to allow dice with other than
six sides. Suppose we use two (fair) n-sided dice. Then we can define a game analogous
to craps in the following way. The player rolls two n-sided dice. If the sum of these dice is
n + 1 or 2n − 1, the player wins. If the sum of these dice is 2, 3 or 2n, then the player loses.
Otherwise the sum becomes the player’s point, and they win if they roll that sum again before
rolling n + 1. We may again ask: what is the player’s probability of winning?

68. Yahtzee There are many probability questions we may ask with regard to the game of
Yahtzee. For starters, what is the probability of rolling, in a single roll,

(a) Yahtzee
(b) Four of a kind (but not Yahtzee)
(c) Three of a kind (but not four of a kind or Yahtzee)
(d) A full house
(e) A long straight
(f) A small straight

69. More Yahtzee What is the probability of getting Yahtzee, assuming that we are trying just
to get Yahtzee, we make reasonable choices about which dice to re-roll, and we have three
rolls? That is, assume we’re in the situation where all we have left to get in a game of Yahtzee
is Yahtzee, so that all other outcomes are irrelevant.

70. Drop Dead In the game of Drop Dead, the player starts by rolling five standard dice. If
there are no 2’s or 5’s among the five dice, then the dice are summed and this is the player’s
score. If there are 2’s or 5’s, these dice become “dead" and the player gets no score. In either
case, the player continues by rolling all non-dead dice, adding points onto the score, until all
dice are dead.
For example, the player might roll {1, 3, 3, 4, 6} and score 17. Then they roll all the dice again
and get {1, 1, 2, 3, 5} which results in no points and two of the dice dying. Rolling the three

9
A Collection of Dice Problems Matthew M. Conroy

remaining dice, they might get {2, 3, 6} for again no score, and one more dead die. Rolling
the remaining two they might get {4, 6} which gives them 10 points, bringing the score to
27. They roll the two dice again, and get {2, 3} which gives no points and another dead die.
Rolling the remaining die, they might get {3} which brings the score to 30. Rolling again,
they get {5} which brings this player’s round to an end with 30 points.
Some natural questions to ask are:

(a) What is the expected value of a player’s score?

(b) What is the probability of getting a score of 0? 1? 20? etc.

71. Threes In the game of Threes, the player starts by rolling five standard dice. In the game,
the threes count as zero, while the other faces count normally. The goal is to get as low a sum
as possible. On each roll, at least one die must be kept, and any dice that are kept are added
to the player’s sum. The game lasts at most five rolls, and the score can be anywhere from 0
to 30.
For example a game might go like this. On the first roll the player rolls

2−3−3−4−6

The player decides to keep the 3s, and so has a score of zero. The other three dice are rolled,
and the result is
1−5−5
Here the player keeps the 1, so their score is 1, and re-rolls the other two dice. The result is

1−2

Here, the player decides to keep both dice, and their final score is 4.
If a player plays optimally (i.e., using a strategy which minimizes the expected value of their
score), what is the expected value of their score?

72. Pig In the game of Pig, two players take turns rolling a die. On a turn, a player may roll
the die as many times as they like, provided they have not thrown a one. If they end their
turn before rolling a one, their turn score is the sum of rolls for that turn. If they roll a one,
their turn score is zero. At the end of the turn, their turn score is added to the player’s total
score. The first player to reach 100 points wins.
Let’s consider the strategy for playing this game in which the player will roll until their turn
score is at least M . What value of M will maximize their expected turn score? What is the
expected value?

73. More Pig Suppose in a game of Pig, a player decides to just go for it and try to roll 100
points on their first turn. What is the probability that they will succeed?

74. Can’t Stop In the game of Can’t Stop, a player rolls four dice at once, groups the dice into
pairs and then sums each pair. The player gets to choose which grouping the want. For
example, if they roll 6 − 4 − 2 − 1, they can group them in one of the following ways:

• (6, 4) and (2, 1), for a sum pair of 10 and 3;

• (6, 2) and (4, 1), for a sum pair of 8 and 5;

10
A Collection of Dice Problems Matthew M. Conroy

• (6, 1) and (4, 2), for a sum pair of 7 and 6.

What are the probabilities of rolling each possible sum pair? What are the probabilities of
each possible sum?
75. Suppose we play a game with a die where we roll and sum our rolls. We can stop any time
and take the sum as our score, but if we roll a face we’ve rolled before then we lose everything.
What strategy will maximize our expected score?
76. (Same as previous game, but with two dice.) Suppose we play a game with two dice where
we roll and sum our rolls. We can stop any time and take the sum as our score, but if we roll a
sum we’ve rolled before then we lose everything. What strategy will maximize our expected
score?
77. Suppose we play a game with a die where we roll and sum our rolls. We can stop any time
and take the sum as our score, but if we roll the same face twice in a row we lose everything.
What strategy will maximize our expected score?
78. Suppose we play a game with a die. We roll once, and this first roll is the score.
We may continue to roll and add to the score, but if the roll ever divides the score we start
with (e.g., if our score is 15 and we roll a 1, 3, or 5), then we lose everything and end up with
nothing. If instead we choose to stop, we win an amount proportional to the score.
What strategy will yield the maximum expected value of our final score?
79. Suppose we play a game with a die where we roll and sum our rolls as long as we keep rolling
larger values. For instance, we might roll a sequence like 1-3-4 and then roll a 2, so our sum
would be 8. If we roll a 6 first, then we’re through and our sum is 6. Three questions about
this game:
(a) What is the expected value of the sum?
(b) What is the expected value of the number of rolls?
(c) If the game is played with an n-sided die, what happens to the expected number of rolls
as n approaches infinity?
80. Suppose we play a game with a die where we roll and add our rolls to our total when the
face that appears has not occurred before, and subtract it from our total if it has.
For example, if we rolled the sequence 1, 3, 4, 3, our corresponding totals would be 1, 4, 8, 5.
We can stop any time and take the total as our score. What strategy should we employ to
maximize our expected score?
81. Suppose we roll a single die, repeatedly if we like, and sum. We can stop at any point, and
the sum becomes our score; however, if we exceed 10, our score is zero.
What should our strategy be to maximize the expected value of our score? What is the ex-
pected score with this optimal strategy?
What about limits besides 10?
82. Suppose we play a game with a die where we roll and sum our rolls. We can stop any time,
and the sum is our score. However, if our sum is ever a multiple of 10, our score is zero, and
our game is over. What strategy will yield the greatest expected score? What about the same
game played with values other than 10?

11
A Collection of Dice Problems Matthew M. Conroy

83. Suppose we play a game with a die in which we use two rolls of the die to create a two-digit
number. The player rolls the die once and decides which of the two digits they want that roll
to represent. Then, the player rolls a second time and this determines the other digit. For
instance, the player might roll a 5, and decide this should be the “tens" digit, and then roll a
6, so their resulting number is 56.
What strategy should be used to create the largest number on average? What about the three
digit version of the game?

12
Chapter 3

Discussion, Hints, and Solutions

3.1 Single Die Problems

1. On average, how many times must a 6-sided die be rolled until a 6 turns up?
This problem is asking for the expected number of rolls until a 6 appears. Let X be the random
variable representing the number of rolls until a 6 appears. Then the probability that X = 1
is 1/6; the probability that X = 2 is (5/6)(1/6) = 5/36. In general, the probability that X = k
is  k−1
5 1
(3.1)
6 6
since, in order for X to be k, there must be k − 1 rolls which can be any of the numbers 1
through 5, and then a 6, which appears with probability 1/6.
We seek the expectation of X. This is defined to be
∞
X
E= nP (X = n) (3.2)
n=1

where P (X = n) is the probability that X takes on the value n. Thus,

∞  n−1 ∞  n
X 5 1 6 1X 5
E= n = · n (3.3)
6 6 5 6 6
n=1 n=1

Using Equation B.3 from Appendix B, we can conclude that

6 1 5/6
E= · = 6. (3.4)
5 6 (1 − (5/6))2

Thus, on average, it takes 6 throws of a die before a 6 appears.

Here’s another, quite different way to solve this problem. When rolling a die, there is a 1/6
chance that a 6 will appear. If a 6 doesn’t appear, then we’re in essence starting over. That is
to say, the number of times we expect to throw the die before a 6 shows up is the same as the
number of additional times we expect to throw the die after throwing a non-6. So we have a
1/6 chance of rolling a 6 (and stopping), and a 5/6 chance of not rolling a six, after which the

13
A Collection of Dice Problems Matthew M. Conroy

number of rolls we expect to throw is the same as when we started. We can formulate this as
1 5
E= + (E + 1) . (3.5)
6 6
Solving for E, we find E = 6. Note that Equation 3.5 implicitly assumes that E is a finite
number, which is something that, a priori, we do not necessarily know.
2. On average, how many times must a 6-sided die be rolled until a 6 turns up twice in a row?
We can solve this using a recurrence relation on, E, the expected number of rolls. When we
start rolling, we expect, on average 6 rolls until a 6 shows up. Once that happens, there is a
1/6 chance that we will roll once more, and a 5/6 chance that we will be, effectively, starting
all over again, and so have as many additional expected rolls as when we started. As a result,
we can say
1 5
E = 6 + · 1 + (E + 1).
6 6
Solving this, we find that E = 42.
3. On average, how many times must a 6-sided die be rolled until the sequence 65 appears (i.e., a 6
followed by a 5)?
This appears to be quite similar to problem 2, but there is a difference. In problem 2, once we
roll a 6, there are only two possibilities: either we roll a 6, or we start all over again.
In this problem, once we roll a 6, there are three possibilities: (a) we roll a 5, (b), we roll a 6,
or (c) we start all over again.
We can again solve it using recursion, but we’ll need two equations. Let E be the expected
number of rolls until 65 and let E6 be the expected number of rolls until 65 when we start
with a rolled 6. Then:
1 4 1
E6 = (E6 + 1) + (E + 1) + (1)
6 6 6
1 5
E = (E6 + 1) + (E + 1)
6 6
This gives us a system of two linear equations in two unknowns, which we can solve to find
E = 36, E6 = 30.

So it takes fewer rolls on average to see a 6 followed by a 5 than it does to see a 6 followed by
a 6.
4. On average, how many times must a 6-sided die be rolled until there are two rolls in a row that differ
by 1 (such as a 2 followed by a 1 or 3, or a 6 followed by a 5)? What if we roll until there are two rolls
in a row that differ by no more than 1 (so we stop at a repeated roll, too)?
Let E be the expected number of rolls. Let Ei be the expected number of rolls after rolling
an i (not following a roll of i − 1 or i + 1).
Then we have
1
E = 1 + (E1 + E2 + E3 + E4 + E5 + E6 ).
6
By symmetry, we know that E1 = E6 , E2 = E5 and E3 = E4 , so
2
E = 1 + (E1 + E2 + E3 ).
6

14
A Collection of Dice Problems Matthew M. Conroy

We can express E1 as
2 1 2
E1 = 1 + E1 + E2 + E3
6 6 6
since there will definitely be an additional roll, there is a 16 chance that this will be the last
roll (i.e., we roll a 2) and the five other possibilities are equally likely.
Similarly,
1 2 1
E2 = 1 + E1 + E2 + E3
6 6 6
and
2 1 1
E3 = 1 + E1 + E2 + E3 .
6 6 6
This gives us a system of three linear equations in three unknowns.
Solving, we find
70 58 60
E1 = , E2 = , and E3 =
17 17 17
and so
239
E= = 4.68627450980....
51
If we stop when we have a repeated roll, too, the situation is similar. Defining E, E1 , E2 , and
E3 as above, we have the system

2
E = 1 + (E1 + E2 + E3 )
6
1 1 2
E1 = 1 + E1 + E2 + E3
6 6 6
1 1 1
E2 = 1 + E1 + E2 + E3
6 6 6
2 1
E3 = 1 + E1 + E2 .
6 6

Solving this, we find

288 246 252
E1 = , E2 = , and E3 = .
115 115 115
and so
377
E= = 3.278260869565....
115
5. We roll a 6-sided die n times. What is the probability that all faces have appeared?
Let P (n) stand for the probability that all faces have appeared in n rolls.
To determine P (n), we can use the principle of inclusion-exclusion.
We wish to count the number of roll sequences that do not contain all faces.
There are 6n ways to roll a die n times.
Of these, 5n have no 1, 5n have no 2, etc.
Simply adding those will not yield what we seek, since there are roll sequences that contain
no 1 and no 2 (for example), so we would be counting those twice.

15
A Collection of Dice Problems Matthew M. Conroy

As a result, we take that sum and subtract all the roll sequences with both no 1 and no 2, or
both no 1 and no 3, etc.
Again, we will not have quite what we wish, since we will have removed sequences that
contain, say, both no 1 and no 2, and no 1 and no 3, twice.
Hence, we have to add back in the number of sequences that fail to have three faces.
We continue in this way, alternating subtracting and adding numbers of sequences, until we
reach the final count: no sequence can fail to have all 6 faces.
All together, then, we find that the number of sequences that fail to have all 6 faces is
         
6 n 6 n 6 n 6 n 6 n
5 − 4 + 3 − 2 + 1 .
1 2 3 4 5

Hence, the probability of having all 6 faces appear in n rolls of the die is
   n    n    n    n    n
6 5 6 4 6 3 6 2 6 1
1− + − + −
1 6 2 6 3 6 4 6 5 6
 n  n  n  n  n
5 2 1 1 1
=1−6 + 15 − 20 + 15 −6
6 3 2 3 6
n n n n n
6 − 6 · 5 + 15 · 4 − 20 · 3 + 15 · 2 − 6
= .
6n

Here is a short table of values of this probability.

n P (n) exactly P (n) approximately
1 0 0
2 0 0
3 0 0
4 0 0
5 0 0
6 5/324 0.01543210
7 35/648 0.05401235
8 665/5832 0.11402606
9 245/1296 0.18904321
10 38045/139968 0.27181213
11 99715/279936 0.35620642
12 1654565/3779136 0.43781568
13 485485/944784 0.51385819
14 317181865/544195584 0.58284535
15 233718485/362797056 0.64421274
16 2279105465/3265173504 0.69800440
17 4862708305/6530347008 0.74463245
18 553436255195/705277476864 0.78470712
19 1155136002965/1410554953728 0.81892308
20 2691299309615/3173748645888 0.84798754
36 0.99154188

6. We roll a 6-sided die n times. What is the probability that all faces have appeared in order, in some
six consecutive rolls (i.e., what is the probability that the subsequence 123456 appears among the n
rolls)?
This is a rather tedious calculation, but a nice way to handle it is as a Markov chain. We
define a zero state (the state we start in, and the state we are in if the current rolls value

16
A Collection of Dice Problems Matthew M. Conroy

was not preceded by the smaller values in order (e.g., if the current roll is a 2, but the pre-
vious roll was not a 1), and then six states corresponding to having a current “streak" of
1, 12, 123, 1234, 12345, 123456. Call these states one through six. The last state is an absorbing
state. We then have the following transition matrix:
 
5 1
0 0 0 0 0
6 6 
2 1 1
0 0 0 0

3 6 6 
 
2 1 1
 3 6 0 6 0 0 0

 
M =  23 16 0 0 16 0 0 
 
 
2 1
 3 6 0 0 0 16 0 

 
2 1 1

3 6 0 0 0 0 6


0 0 0 0 0 0 1

Then, the probability p we seek is the last entry in the first row of M n . Using a computer
algebra system, these probabilities can be calculated exactly. Here is a short table of values,
calculated exactly and then converted to decimal approximations.
n p, approx.
6 0.00002143347051
7 0.00004286694102
8 0.00006430041152
9 0.00008573388203
10 0.0001071673525
11 0.0001286008230
12 0.0001500338342
13 0.0001714663859
14 0.0001928984782
15 0.0002143301111
16 0.0002357612847
17 0.0002571919988
18 0.0002786222536
19 0.0003000520490
20 0.0003214813850
30 0.0005357494824
40 0.0007499716542
50 0.0009641479102
100 0.002034340799
200 0.004171288550
500 0.01055471585
1000 0.02110296021
2000 0.04186329068
5000 0.1015397384
10000 0.1928556782
20000 0.3485878704
30000 0.4742727525
40000 0.5757077184
50000 0.6575715999
60000 0.7236404850
70000 0.7769618947
80000 0.8199953550
90000 0.8547258452
100000 0.8827553586
200000 0.9862551674
300000 0.9983886648

It may be useful to note that, for n > 1000, say,

1 n
 
p≈1− 1− 6
6
is a quite good approximation.

7. We roll a 6-sided die n times. What is the probability that all faces have appeared in some order in some
six consecutive rolls? What is the expected number of rolls until such a sequence appears?
The use of a Markov chain is helpful here.

17
A Collection of Dice Problems Matthew M. Conroy

As we roll the die, let the state of the chain be the length of the current run of different faces
that have appeared. For example, if we’ve rolled 1232535 we would be in state 2 and if we’ve
rolled 621342 we would be in state 4. Then we can treat the game as starting in state 0 and
ending in state 6, the lone absorbing state, and our transition matrix,A, is:
 
0 1 0 0 0 0 0
 0 1 5 0 0 0 0 
 
 6 6 
1 1 2
 0 6 6 3 0 0 0 
 
 
A= 1 1 1 1
 0 6 6 6 2 0 0 

 0 16 16 16 16 13 0 
 
 
 0 1 1 1 1 1 1 
 6 6 6 6 6 6 
0 0 0 0 0 0 1

The last entry in the first row of Ak is the probability that we have had a run of six distinct
faces in six consecutive rolls after rolling n times.
Here’s a short table.
6 5/324 ≈ 0.0154320987654321
7 55/1944 ≈ 0.0282921810699588
8 475/11664 ≈ 0.0407235939643347
9 1235/23328 ≈ 0.0529406721536351
10 27295/419904 ≈ 0.0650029530559366
11 193805/2519424 ≈ 0.0769243287354570
12 1340735/15116544 ≈ 0.0886932224720148
13 3032735/30233088 ≈ 0.100311784227929
14 60831335/544195584 ≈ 0.111782118026154
15 401963125/3265173504 ≈ 0.123106206915980
16 2630801215/19591041024 ≈ 0.134285932624874
17 1898020885/13060694016 ≈ 0.145323126219390
18 110178168055/705277476864 ≈ 0.156219603871238
19 706591379045/4231664861184 ≈ 0.166977159634352
20 4509200245295/25389989167104 ≈ 0.177597564757422
30 ≈ 0.276632203155226
40 ≈ 0.363740977546063
50 ≈ 0.440360014062237
59 ≈ 0.501395674467765
100 ≈ 0.705366141972490
150 ≈ 0.844884010296883
185 ≈ 0.901003849080251
200 ≈ 0.918336030954966
239 ≈ 0.950488949860775
310 ≈ 0.980090832609887
364 ≈ 0.990042806960432
418 ≈ 0.995020098465974
544 ≈ 0.999011257908158
From the transition matrix, we can also calculate (see Appendix D for the method) that the
expect number of rolls until six distinct faces appear in six consecutive rolls is

416
= 83.2.
5

18
A Collection of Dice Problems Matthew M. Conroy

Alternatively, we can find the expected value by creating a set of linear rence equations. Let
Ei be the expected number of rolls from a point where the last i rolls were distinct. We seek
E0 . We have then

E0 = 1 + E1 (3.6)
1 5
E1 = 1 + E1 + E2 (3.7)
6 6
1 1 4
E2 = 1 + E1 + E2 + E3 (3.8)
6 6 6
1 1 1 3
E3 = 1 + E1 + E2 + E3 + E4 (3.9)
6 6 6 6
1 1 1 1 2
E4 = 1 + E1 + E2 + E3 + E4 + E5 (3.10)
6 6 6 6 6
1 1 1 1 1 1
E5 = 1 + E1 + E2 + E3 + E4 + E5 + E6 (3.11)
6 6 6 6 6 6
E6 = 0 (3.12)

The last zero rolls are distinct only before the rolls have started, so E0 = 1 + E1 since there
must be a roll, and that takes us to the state where the last 1 roll is distinct. Then another
roll occurs; at this point, with probability 1/6 the roll is the same as the last roll, and so we
remain in the same state, or, with probability 5/6, a different face appears, and then the last
two rolls are distinct. The pattern continues this way.
Thus we have a system of seven linear equations in seven unknowns, which is solvable via
many methods. The result is

416
E0 = = 83.2
5
411
E1 = = 82.2
5
E2 = 81
396
E3 = = 79.2
5
378
E4 = = 75.6
5
324
E5 = = 64.8
5

Thus, on average, it will take 83.2 rolls before getting a run of six distinct faces.

8. Person A rolls n dice and person B rolls m dice. What is the probability that they have a common face
showing (e.g., person A rolled a 2 and person B also rolled a 2) among all their dice?
We will assume 6-sided dice.
Let X be the multiset of faces that person A rolls, and Y be the multiset of faces that person
B rolls.
We want the probability

P ((1 ∈ X and 1 ∈ Y ) or (2 ∈ X and 2 ∈ Y ) or . . . ).

19
A Collection of Dice Problems Matthew M. Conroy

Let Ai be the event “ i ∈ X and i ∈ Y ".

Then, we want, by an application of the inclusion-exclusion principle,
6
! !
[ X \
|S|−1
P Ai = (−1) P Ai .
i=1 S⊆{1,...,6} i∈S
S6=∅

Now, suppose S ⊆ {1, . . . , 6}, with S = {j1 , . . . , j|S| }. Then

!
\
P Ai = P (j1 , . . . , j|S| ∈ X)P (j1 , . . . , j|S| ∈ Y ).
i∈S

Let αr = P (j1 , . . . , jr ∈ X). Then, applying inclusion-exclusion again,

αr = P (j1 , . . . , jr ∈ X)
= 1 − P (j1 6∈ X or j2 6∈ X or . . . )
r
!
[
=1−P ji 6∈ X
i=1
!
X \
=1− (−1)|S|−1 P ji 6∈ X
S⊆{1,...,r} i∈S
S6=∅
 n
X
|S|−1 |S|
=1− (−1) 1−
6
S⊆{1,...,r}
S6=∅
r  n  
X
i−1 i r
=1− (−1) 1− .
6 i
i=1

Similarly, letting βr = P (j1 , . . . , jr ∈ Y ), we have

r  m  
X
i−1 i r
βr = 1 − (−1) 1− .
6 i
i=1

and so
!
[ X
P Ai = (−1)|S|−1 α|S| β|S|
i∈S S⊆{1,...,6}
S6=∅
6  
X 6
= (−1)i−1 αi βi .
i
i=1

Here are a few calculated values of P , the probability of a common face, for various n and m.

20
A Collection of Dice Problems Matthew M. Conroy

n m P P , approx.
1 1 1/6 0.1666666
1 2 11/36 0.3055555
2 2 37/72 0.5138888
1 3 91/216 0.4212962
2 3 851/1296 0.6566358
3 3 6151/7776 0.7910236
1 4 671/1296 0.5177469
2 4 1957/2592 0.7550154
3 4 40571/46656 0.8695773
4 4 86557/93312 0.9276084
5 5 9856951/10077696 0.9780956
6 6 120194317/120932352 0.9938971

9. On average, how many times must a 6-sided die be rolled until all sides appear at least once? What
about for an n-sided die?
To roll until every side of the die appears, we begin by rolling once. We then roll until a
different side appears. Since there are 5 different sides we could roll, this takes, on average,
5/6 = 5 rolls. Then we roll until a side different from the two already rolled appears. This
1 6

requires, on average, 4/6

1
= 64 rolls. Continuing this process, and using the additive nature of
expectation, we see that, on average,

6 6 6 6 6 147
1+ + + + + = = 14.7
5 4 3 2 1 10
rolls are needed until all 6 sides appear at least once. For an n-sided die, the number of rolls
needed, on average, is
n n
n n n Xn X1
1+ + + ··· + = =n .
n−1 n−2 1 i i
i=1 i=1

For large n, this is approximately n log n.

(This problem is an example of what is often referred to as a Coupon Collector’s problem.
We can imagine that a person is trying to collect a set of n distinct coupons. Each day (say)
they get a new coupon, which has a fixed probability of being one of the n types. We may
then ask for the expected number of days until all n coupons have been collected. This prob-
lem is analogous to the situation in which all n coupon types are equally likely. For a more
complicated version, see problem 36.)

10. On average, how many times must a 6-sided die be rolled until all sides appear at least twice?
This is quite a bit more complicated than the previous problem (where we roll until each side
appears at least once).
Modeling the problem with a Markov chain is helpful here.
As we roll the die, we need to keep track of how many times each side has appeared. After
each roll, then, we can capture the state of our rolling with a vector, hx1 , x2 , x3 , x4 , x5 , x6 i,
where xi is the number of times side i has appeared so far. Since we are only interested in
rolling all sides twice, we can take xi ∈ {0, 1, 2} (that is, even if we roll a side more than twice,

21
A Collection of Dice Problems Matthew M. Conroy

we keep xi at 2 - it does not matter how many times we have rolled it as long as it is at least
2).
We could make a Markov chain using these vectors as our states. This would give us a chain
with 36 = 729 states, hence requiring a 729 × 729 transition matrix.
However, we can utilize the symmetry of our dice to reduce the number of states considerably.
Because all sides of the die are equally likely, we do not actually need the vector to represent
the state, but only the corresponding multiset of values.
For example, the vectors h0, 1, 1, 2, 0, 0i represents, in essence, the same state as h2, 0, 1, 0, 1, 0i.
Both correspond to the multiset {0, 0, 0, 1, 1, 2}.
Further, since each multiset has six elements, we can represent one of these multisets with
an ordered pair (a, b) where a is the number of 1’s and b is the number of 2’s in the set.
Thus, for example, the state vector h1, 0, 1, 0, 0, 0i can be denoted by (2, 0), and the vector
h2, 1, 0, 1, 0, 0i can be denoted by (2, 1).
The rolling begins, then, in the state (0, 0) and ends in the state (0, 6).
Thus, our set of states consists of all ordered pairs (a, b) where a, b ∈ {0, 1, . . . , 6} and a+b ≤ 6.
This gives us 28 states.
We then can calculate transition probabilities as follows.
The transition from (a, b) to (a + 1, b) occurs with probability p = 1 − a+b6 . This is because
6 − (a + b) is the current number of zeros, and so p gives the probability of rolling one of the
sides that have not appeared yet.
If b < 6, then the transition from (a, b) to (a − 1, b + 1) occurs with probability p = a6 . This
is because a is the number of sides which have appeared exactly once so far, and p gives the
probability of rolling one of these sides, converting the corresponding 1 into a 2, and hence
increasing the number of 2’s and reducing the number of 1’s by one each.
The transition from (a, b) to (a, b) occurs with probability p = 6b . This is because b is the
number of 2’s, and so p gives the probability of rolling one of the corresponding sides, which
does not change the counts at all.
The transition probabilities give a single absorbing state, (0, 6).
Ordering these states (0, 0), (1, 0), (2, 0), . . . , (0, 5), (1, 5), (0, 6), we have the following transi-
tion matrix:

22
A Collection of Dice Problems Matthew M. Conroy

 
0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

 0 0 5 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 


 0 0 0 4 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 


 0 0 0 0 3 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 


 0 0 0 0 0 2 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 


 0 0 0 0 0 0 1 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 
 
0 0 0 0 0 0 0 1 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 
 
0 0 0 0 0 0 0 0 1 4 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 
 
 
 0 0 0 0 0 0 0 0 0 1 3 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 
 

 0 0 0 0 0 0 0 0 0 0 1 2 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 


 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 


 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 

1 0 0 0 0 0 0 0 0 0 0 0 0 0 2 4 0 0 0 0 0 0 0 0 0 0 0 0 0 
P =  
6
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 3 0 0 1 0 0 0 0 0 0 0 0 0 


 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 0 0 2 0 0 0 0 0 0 0 0 


 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1 0 0 3 0 0 0 0 0 0 0 


 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 4 0 0 0 0 0 0 


 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 3 0 0 0 0 0 0 0 0 


 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 2 0 1 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 1 0 2 0 0 0 0
 
 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 3 0 0 0
 
 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 2 0 0 0 0
 
 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 1 1 0 0
 
 
 
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 2 0 
 

 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 1 0 

 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 1 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6

Applying the methods of Appendix D, we can determine from this matrix that the expected
number of rolls until all sides have appeared at least once is

390968681
= 24.1338692 . . . .
16200000
We can also use matrix P to calculate the probability q that after j rolls all sides have appeared
at least twice. Here are some values:

23
A Collection of Dice Problems Matthew M. Conroy

j q
11 0
12 0.003438285...
13 0.014899238...
14 0.037661964...
15 0.072748752...
16 0.119155589...
17 0.174576398...
18 0.236147670...
19 0.301007601...
20 0.366633348...
21 0.430995652...
22 0.492589321...
23 0.550391734...
30 0.828548154...
34 0.906280939...
39 0.957121359...
49 0.991461443...
62 0.999009173...
This problem is an example of what is often referred to as a Coupon Collector’s problem.
11. On average, how many times must a pair of 6-sided dice be rolled until all sides appear at least once?
We can solve this by treating the rolling of the dice as a Markov process. This means that we
view our game as being always in one of a number of states, with a fixed probability of moving
from one state to each other state in one roll of the dice.
We can define our states by the number of sides we have seen appear so far. Thus, we starts
in State 0, and we wish to end up in State 6, reaching some, or all, of States 1, 2, 3, 4 and 5
along the way.
On the very first roll, we will move from State 0 to either State 1 or State 2. We move to State
1 with probability 36
6
, since this happens exactly if we roll “doubles". Otherwise, we move to
State 2, so we move to State 2 from State 0 with probability 30 36 .
Thus, our question can be stated thus: starting in State 0, what is the expected number of
rolls until we reach State 6?
We determine the transition probabilities, the probability of transitioning from one state to
another in one roll. We can create a diagram like this that shows the probability of moving
from one state to each other state in one roll:
30 4 12 16 2
36 36 36 36 36 1

6 15 20 21 18 11
36 36 36 36 36 36
0 1 2 3 4 5 6
20 6
36 36
1 9 25
36 36 36

To solve the problem, we create a transition matrix for this process as follows. We let row
1 represent State 0, row 2 represent state 1, etc. Then the i,j-th entry in the matrix is the

24
A Collection of Dice Problems Matthew M. Conroy

probability of transition from the row i state to the row j state in one roll (that is, from state
i − 1 to state j − 1).
For this process, our transition matrix is
 
1 5
0 6 6 0 0 0 0
 
1 5 5
0 0 0 0
 
 36 12 9 
1 5 1
0 0 0 0
 
 9 9 3 
P = 0
 1 7 1 
0 0 4 12 6 0
 

0 4 1 1 
 0 0 0 9 2

18 
25 11 
 
0 0 0 0 0
 36 36 

0 0 0 0 0 0 1

The matrix Q as described in Appendix D is then

 
1 5
0 6 6 0 0 0
 
1 5 5
0 0 0
 
 36 12 9 
0 1 5 1
0 0
 
9 9 3
Q= 

0 1 7 1 
 0 0 4 12 6 

4 1 
 
0 0 0 0
 9 2 
25
0 0 0 0 0 36

The matrix N = (I − Q)−1 as described Appendix D is then

 
6 57 37 43 461
1 35 56 42 28 154 

36 27 47 41 463 
0

 35 56 42 28 154 

0 9 5 31 329 
0

8 6 20 110 



0 4 7 166 
 0 0 3 5 55 

9 162 
 
0 0 0 0
 5 55 
36
0 0 0 0 0 11

Summing the first row we find the expected number of rolls until all six sides have appeared
6 57 37 43 461 70219
=1+ + + + + = = 7.59945887445....
35 56 42 28 154 9240
By looking at the last entry of the first row of powers of the matrix P , we can find the proba-
bility of reaching state 6 in a given number of rolls:

25
A Collection of Dice Problems Matthew M. Conroy

rolls probability of reaching this state in ex- probability of reaching this state on or
actly this number of rolls before this number of rolls
1 0 0
2 0 0
3 5/324 ≈ 0.015432099 5/324 ≈ 0.015432099
4 575/5832 ≈ 0.098593964 665/5832 ≈ 0.11402606
5 22085/139968 ≈ 0.15778607 38045/139968 ≈ 0.27181213
6 313675/1889568 ≈ 0.16600355 1654565/3779136 ≈ 0.43781568
7 78924505/544195584 ≈ 0.14502967 317181865/544195584 ≈ 0.58284535
8 376014275/3265173504 ≈ 0.11515905 2279105465/3265173504 ≈ 0.69800440
9 61149474755/705277476864 ≈ 553436255195/705277476864 ≈
0.086702719 0.78470712
10 401672322475/6347497291776 ≈ 2691299309615/3173748645888 ≈
0.063280424 0.84798754
11 0.045328994 0.89331653
12 0.032098630 0.92541516
13 0.022567579 0.94798274
14 0.015795289 0.96377803
15 0.011023854 0.97480189
16 0.0076798753 0.98248176
17 0.0053441053 0.98782587
18 0.0037160115 0.99154188
19 0.0025827093 0.99412459
20 0.0017945018 0.99591909
21 0.0012466057 0.99716570
22 0.00086588683 0.99803158
23 0.00060139404 0.99863298
24 0.00041767196 0.99905065
So we see that there is a less than one in a thousand chance that more than 24 rolls would be
needed, for instance.
Alternative approach: Instead of using a transition matrix, we can create a system of linear
equations that we can solve to get the expected value of the number of throws.
Let En be the expected number of throws needed until all faces have appeared, if n faces have
already appeared. We seek E = 0.
We know that, starting with zero faces, we must roll the pair once; with 1
6 probability, exactly
one face appears, and with 56 probability, two faces appear. Hence,
1 5
E0 = 1 + E1 + E2 .
6 6
In a similar fashion, we can create the following system relating these E variables:
1 5
E0 = 1 + E1 + E2
6 6
1 15 20
E1 = 1 + E1 + E2 + E3
36 36 36
4 20 12
E2 = 1 + E2 + E3 + E4
36 36 36
9 21 6
E3 = 1 + E3 + E4 + E5
36 36 36
16 18
E4 = 1 + E4 + E5
36 36
25
E5 = 1 + E5
36

26
A Collection of Dice Problems Matthew M. Conroy

It is then straightforward to solve the system and find

70219
E0 =
9240
as found above.
Additional question: What if we roll three (or more) dice at a time? We can answer that
with another six-state Markov process; only the transition probabilities would change.
(Special thanks to Steve Hanes and Gabe for sending me this nice problem.)

12. Suppose we roll n dice. What is the expected number of distinct faces that appear?
Let E be the sought expectation.
I will give three distinct solutions.
Let X be the number of distinct faces appearing in n rolls of a die. Using the inclusion-
exclusion principle, we have the following probabilities:
   n
6 1
P (X = 1) =
1 6
   n    n 
6 2 2 1
P (X = 2) = −
2 6 1 6
   n    n    n 
6 3 3 2 3 1
P (X = 3) = − +
3 6 2 6 1 6
   n    n    n    n 
6 4 4 3 4 2 4 1
P (X = 4) = − + −
4 6 3 6 2 6 1 6
   n    n    n    n    n 
6 5 5 4 5 3 5 2 5 1
P (X = 5) = − + − +
5 6 4 6 3 6 2 6 1 6
   n    n    n    n    n    n 
6 6 6 5 6 4 6 3 6 2 6 1
P (X = 6) = − + − + −
6 6 5 6 4 6 3 6 2 6 1 6

These expressions determine the distribution of the number of distinct faces in n rolls.
To find the expectation, we want
6
X
E = iP (X = i)
i=1

and, after some chewing, this simplifies to

 n
5
E =6−6 .
6

Here’s a different approach.

The probability that the j-th roll will yield a face distinct from all previous faces rolled is
 j−1
6 · 5j−1 5
=
6j 6

27
A Collection of Dice Problems Matthew M. Conroy

since, thinking in reverse, there are 6 faces the j-th roll could be, and then 5j−1 ways to roll
j − 1 rolls not including that face, out of a total 6j ways to roll j dice.
As a result, the expected contribution from the j-th roll to the total number of distinct faces
is just the probability that the j-th roll is distinct: the roll contributes 1 with that probability,
and 0 otherwise.
Using the additivity of expectation, we thus have
 
n+1
n  j−1 n  
!
6 X 5 j
 n
X 5 6 1 − 56 5
E = = − 1 = 5 −1 =6−6 .
6 5 6 5 1− 6
6
j=1 j=0

For a third solution, let Xi be a random variable defined by

(
1 if the face i appears in n rolls of a die,
Xi =
0 otherwise.
Let X be the number of distinct faces appearing in n rolls of a die. Then
X = X1 + X2 + X3 + · · · + X6
and so the expected value of X is
E(X) = E(X1 ) + E(X2 ) + · · · + E(X6 ) = 6E(X1 )
by symmetry. Now, the probability that a 1 has appeared in n rolls is
 n
5
P (X1 = 1) = 1 −
6
and so  n
5
E(X1 ) = 1 · P (X1 = 1) = 1 −
6
and thus the expected number of distinct faces appearing in n rolls of a die is
  n 
5
E = 6E(X1 ) = 6 1 − .
6
Here’s a short table of values of E .
n E
1 1
2 1.83̄
3 2.527̄
4 3.106481
5 3.588734...
6 3.990612...
7 4.325510...
8 4.604591...
9 4.837159...
10 5.030966...
14 5.532680...
23 5.909430...
27 5.956322...
36 5.991535...
48 5.999050...

28
A Collection of Dice Problems Matthew M. Conroy

13. Suppose we roll n dice and keep the highest one. What is the distribution of values?
Let’s find the probability that the highest number rolled is k. Among the n dice rolled, they
must all show k or less. The probability of this occurring is

kn
.
6n
However, if k > 1, some of these rolls do not actually have any k’s. That is, they are made up
of only the numbers 1 through k − 1. The probability of this occurring, for any k ∈ {1, . . . , n},
is
(k − 1)n
6n
so the probability that the highest number rolled is k is

k n − (k − 1)n
.
6n

So, for instance, the probability that, if 7 dice are rolled, the highest number to turn up will
be 3 is
37 − 27 2059
= 7 ≈ 0.007355.
67 6
14. Suppose we can roll a 6-sided die up to n times. At any point we can stop, and that roll becomes our
“score". Our goal is to get the highest possible score, on average. How should we decide when to stop?

If n = 1, there is no decision to make; on average our score is 7/2.

If n = 2, we want to stick if the first roll is greater than 7/2; that is, if it is 4 or greater.
Otherwise, we roll again. Thus, with n = 2, our average score is
       
1 1 1 3 7 17
4+ 5+ 6+ = = 4.25.
6 6 6 6 2 4

If n = 3, we want to stick on the first roll if it is greater than 4.25; that is, if it is 5 or 6.
Otherwise, we are in the n = 2 case. Thus, with n = 3, our average score is
     
1 1 4 17
5+ 6+ = 4.666....
6 6 6 4

In general, if we let f (n) be the expected value of our score with n rolls left, using s-sided
dice, we have the recursion
s
bf (n − 1)c X j
f (n) = f (n − 1) +
s s
j=bf (n−1)c+1

with f (1) = (s + 1)/2.

We may then calculate, for s = 6, the following table:

29
A Collection of Dice Problems Matthew M. Conroy

n f (n)
1 7/2 = 3.5
2 17/4 = 4.25
3 14/3 = 4.666..
4 89/18 = 4.944...
5 277/54 = 5.1296...
10 5.6502...
21 5.95292...
30 5.9908762...
43 5.9991472...
Thus, for a 6-sided die, we can summarize the strategy as follows:

• If there are at least 5 rolls left, stick only on 6.

• If there are 4, 3, or 2 rolls left, stick on 5 or 6.
• If there is only 1 roll left, stick on 4, 5 or 6.

15. How many dice must be rolled to have at least a 95% chance of rolling a six? 99%? 99.9%?
Suppose we roll n dice. The probability that none of them turn up six is
 n
5
6

and so the probability that at least one is a six is

 n
5
1− .
6

To have a 95% chance of rolling a six, we need

 n
5
1− ≥ 0.95
6

which yields
log 0.05
n≥ = 16.43 . . . > 16.
log(5/6)
Hence, n ≥ 17 will give at least a 95% chance of rolling at least one six. Since log(0.01)/ log(5/6) =
25.2585 . . ., 26 dice are needed to have a 99% chance of rolling at least one six. Similarly, since
log(0.001)/ log(5/6) = 37.8877 . . ., 38 dice are needed for a 99.9% chance.

16. How many dice must be rolled to have at least a 95% chance of rolling a one and a two? What about
a one, a two, and a three? What about a one, a two, a three, a four, a five and a six?
Solving this problem requires the use of the inclusion-exclusion principle. Of the 6n possible
rolls of n dice, 5n have no one’s, and 5n have no two’s. The number that have neither one’s
nor two’s is not 5n + 5n since this would count some rolls more than once: of those 5n rolls
with no one’s, some have no two’s either. The number that have neither one’s nor two’s is 4n ,
so the number of rolls that don’t have at least one one, and at least one two is

5n + 5n − 4n = 2 · 5n − 4n

30
A Collection of Dice Problems Matthew M. Conroy

and so the probability of rolling a one and a two with n dice is

2 · 5n − 4n
1− .
6n
This is an increasing function of n, and by direct calculation we can show that it’s greater
than 0.95 for n ≥ 21. That is, if we roll at least 21 dice, there is at least a 95% chance that there
will be a one and a two among the faces that turn up.
To include three’s, we need to extend the method. Of the 6n possible rolls, there are 5n rolls
that have no one’s, 5n that have no two’s, and 5n that have no three’s. There are 4n that have
neither one’s nor two’s, 4n that have neither one’s nor three’s, and 4n that have neither two’s
nor three’s. In addition, there are 3n that have no one’s, two’s, or three’s. So, the number of
rolls that don’t have a one, a two, and a three is

5n + 5n + 5n − 4n − 4n − 4n + 3n = 3 · 5n − 3 · 4n + 3n .

Hence, the probability of rolling at least one one, one two, and one three is

3 · 5n − 3 · 4n + 3n
1− .
6n
This is again an increasing function of n, and it is greater than 0.95 when n ≥ 23.
Finally, to determine the probability of rolling at least one one, two, three, four, five and six,
we extend the method even further. The result is that the probability p(n) of rolling at least
one of every possible face is
5
6−j n
    n  n  n  n  n
(j+1) 6 1 1 1 2 5
X
p(n) = 1− (−1) = 1−6 +15 −20 +15 −6 .
j 6 6 3 2 3 6
j=1

This exceeds 0.95 when n ≥ 27. Below is a table showing some of the probabilities for various
n.

31
A Collection of Dice Problems Matthew M. Conroy

n p(n)
6 0.0154...
7 0.0540...
8 0.1140...
9 0.1890...
10 0.2718...
11 0.3562...
12 0.4378...
13 0.5138...
14 0.5828...
15 0.6442...
16 0.6980...
17 0.7446...
18 0.7847...
19 0.8189...
20 0.8479...
21 0.8725...
22 0.8933...
23 0.9107...
24 0.9254...
25 0.9376...
26 0.9479...
27 0.9565...
30 0.9748...
35 0.9898...
40 0.9959...

17. How many dice should be rolled to maximize the probability of rolling exactly one six? two sixes? n
sixes?
Suppose we roll n dice. The probability that exactly one is a six is
n n−1


1 5 n5n−1
= .
6n 6n
n n−1
The question is: for what value of n is this maximal? If n > 6 then (n+1)5
6n+1
< n56n , so the
maximum must occur for some n ≤ 6. Here’s a table that gives the probabilities:

n5n−1
n
6n
1 1/6 = 0.1666...
2 5/18 = 0.2777...
3 25/72 = 0.3472...
4 125/324 = 0.3858...
5 3125/7776 = 0.4018...
6 3125/7776 = 0.4018...
3125
This shows that the maximum probability is , and it occurs for both n = 5 and n = 6.
7776
For two sixes, the calculation is similar. The probability of exactly two sixes when rolling n
dice is n n−2


2 5 n(n − 1)5n−2
=
6n 2 · 6n

32
A Collection of Dice Problems Matthew M. Conroy

A quick calculation shows that this is maximal for n = 12 or n = 11.

It seems that for n sixes, the maximal probability occurs with 6n and 6n − 1 dice. I’ll let you
prove that.

18. Suppose we roll a fair die 100 times. What is the probability of a run of at least 10 sixes?
We will consider this problem generally.
Let pn be the probability of a run of at least r successes in n throws. Let α be the probability
of success on any one throw (so when throwing a single fair die, α = 1/6.)
Clearly pn = 0 if n < r.
We can determine pn+1 in terms of pn and pn−r . There are two ways that a run of r can happen
in n + 1 throws. Either (a) there is a run of r in the first n throws, or (b) there is not, and the
final r throws of the n + 1 are all successes.
The probability of (a) occurring is pn .
To calculate the probability of (b), first note that for (b) to occur, three things have to happen:

(a) There is no run of length r in the first n−r throws; this happens with probability 1−pn−r .
(b) On throw number n − r + 1, we do not get a success. If we did, then we would have a
run of r successes in the first n throws (since the final r throws are all successes). The
probability here is 1 − α.
(c) The final r throws are all successes. The probability of this is αr .

Since these three events are independent, we find that

pn+1 = pn + (1 − pn−r )(1 − α)αr .

Since r and α are fixed, this is a linear recurrence equation, and we have initial conditions

p0 = p1 = ... = pr−1 = 0, and pr = αr .

If we take n = r, we find

pr+1 = pr + (1 − p0 )(1 − α)αr = αr + (1 − α)αr = αr (2 − α).

and then
pr+2 = pr+1 + (1 − p1 )(1 − α)αr = αr (3 − 2α).

Similarly, if r > 2 then

pr+3 = pr+2 + (1 − p2 )(1 − α)αr = αr (3 − 2α) + (1 − α)αr = αr (4 − 3α).

So, for instance, the probability of a run of at least 3 sixes when a die is thrown 5 times is
(with r = 3 and α = 1/6)
 3  
1 2 1
p5 = 3− =
6 6 81
and if the die is thrown 6 times the probability is
 3  
1 3 7 1
p6 = 4− = = .
6 6 432 61.714...

33
A Collection of Dice Problems Matthew M. Conroy

With this recurrence equation, we can calculate an expression for pr+3 , pr+4 , etc.
To answer the question “what is the probability of a run of 10 sixes in 100 throws of a fair
die?" we wish to calculate p100 with α = 1/6 and r = 10. Using a free computer algebra
system (like PARI/GP), we can determine that, with r = 10 and α = 1/6,

p100 = −10α99 + 135α98 − 720α97 + 2100α96 − 3780α95 + 4410α94 − 3360α93 + 1620α92 − 450α91
+ 55α90 − 125970α88 + 1085280α87 − 4069800α86 + 8682240α85 − 11531100α84 + 9767520α83
− 5155080α82 + 1550400α81 − 203490α80 − 2035800α77 + 14844375α76 − 46314450α75
+ 80159625α74 − 83128500α73 + 51658425α72 − 17813250α71 + 2629575α70 − 3838380α66
+ 23688288α65 − 60865740α64 + 83347680α63 − 64155780α62 + 26320320α61 − 4496388α60
− 2118760α55 + 10824100α54 − 22108800α53 + 22569400α52 − 11515000α51 + 2349060α50
− 487635α44 + 1984760α43 − 3028470α42 + 2053200α41 − 521855α40 − 54740α33 + 166635α32
− 169050α31 + 57155α30 − 3160α22 + 6400α21 − 3240α20 − 90α11 + 91α10
2138428277869029245997109282919411017852189744280011307296262359092389
=
1701350582031434651293464237390775574315478412689986644643416579087232139264
1
= 0.00000125690042984... = .
795607.97...

19. Suppose we roll a fair die until some face has appeared twice. For instance, we might have a run of rolls
12545 or 636. How many rolls on average would we make? What if we roll until a face has appeared
three times?
For the first part of the question, we can enumerate easily the possibilities. Let X be the
number of rolls made until a face has appeared twice. We would like to know P (X = x) for
2 ≤ x ≤ 7.
In the X = 2 case, our run of rolls must have the form AA, where 1 ≤ A ≤ 6. So there are 6
such runs, out of 62 possible. Hence,
6 1
P (X = 2) = 2
= .
6 6
In the X = 3 case, our run of rolls must have the form ABA or BAA, and so
6·5 5
P (X = 3) = 2 3
= .
6 18
In the X = 4 case, our run of rolls must have the form ABCA, BACA, or BCAA, and so
6·5·4 5
P (X = 4) = 3 4
= .
6 18
Similarly, we have
6·5·4·3 5
P (X = 5) = 4 5
=
6 27
6·5·4·3·2 25
P (X = 6) = 5 6
=
6 324
6·5·4·3·2·1 5
P (X = 7) = 6 7
=
6 324

34
A Collection of Dice Problems Matthew M. Conroy

Thus we see that X = 3 and X = 4 are tied as the most likely, and the expected number of
rolls is
7
X 1223
iP (X = i) = = 3.7746913580246....
324
i=2

When rolling until a face appears three times, things are a little more complex. For fun, I
thought of treating this as a Markov chain. The number of states is quite large: as we roll,
we keep track of the number of 1’s, 2’s, etc. that have been rolled. Hence there will be 36 =
729 states to consider, plus the absorbing state, for a total of 730 states. We can map the
number of appearances of each face to a state by a function as follows. Suppose the number
of appearances of face i is ai . Then we can number the current state as

S = 1 + a1 + 3a2 + 32 a3 + 33 a4 + 34 a5 + 35 a6

Then, we create a transition matrix to express the probability of going from state S to state
T , for all possible states. Here is some GP/PARI code which does this:

\\ define a function to map the vector of face counts to a state number

state(a,b,c,d,e,f)=1+a+3*b+9*c+27*d+81*e+243*f;\
\\ initialize a matrix for the transition probabilities
A=matrix(730,730);\
\\ generate the probabilities and put them in the matrix
for(a1=0,2,for(a2=0,2,for(a3=0,2,for(a4=0,2,for(a5=0,2,for(a6=0,2,\
print(a1);\
\\ v is the vector of counts
v=vector(6);v[1]=a1;v[2]=a2;v[3]=a3;v[4]=a4;v[5]=a5;v[6]=a6;\
\\ s is the state
s=state(a1,a2,a3,a4,a5,a6);\
\\ look at how many face counts are equal to 2,
\\ since there is a 1/6 chance for each
\\ such face that we’ll go to the absorbing state from here
c=0;for(i=1,6,if(v[i]==2,c=c+1));\
print(c);\
\\ create a new vector w of the counts,
\\ then increase each face (with count<2) by one,
\\ and see where we go, give 1/6 probability of going to that state
w=vector(6);for(i=1,6,w[i]=v[i]);\
A[s+1,0+1]=c/6;\
for(i=1,6,for(j=1,6,w[j]=v[j]);\
if(w[i]<2,w[i]=w[i]+1;ss=state(w[1],w[2],w[3],w[4],w[5],w[6]);\
A[s+1,ss+1]=1/6;\
))\
))))))

Once we have the transition matrix A, we can calculate An for n = 1, ..., 13 and determine the
probabilities of ending in exactly n rolls:

35
A Collection of Dice Problems Matthew M. Conroy

n P (X = n) P (X ≤ n)
1 0 0
2 0 0
1 1
3 36 = 0.027̄ 36 = 0.027̄
5 7
4 72 = 0.0694̄ 72 = 0.972̄
5 25 ¯
= 0.1157407 23
= 0.212962...
216 108
25 119
6 162 = 0.154320... 324 = 0.367283...
25 701
7 144 = 0.17361̄ 1296 = 0.540895...
1295 5501
8 7776 = 0.166538... 7776 = 0.707433...
175 6551
9 1296 = 0.135030... 7776 = 0.842463...
175 2417
10 1944 = 0.0900205... 2592 = 0.932484...
4375 91387
11 93312 = 0.0468857... 93312 = 0.979370...
9625 557947
12 559872 = 0.0171914... 559872 = 0.996561...
1925
13 559872 = 0.00343828... 1
We find the expected number of rolls to be
13
X 4084571
iP (X = i) = = 7.2955443387059899....
559872
i=1

Additional questions: what if we roll until a face appears 4 times, or 5 times, etc?
20. Suppose we roll a fair die 10 times. What is the probability that the sequence of rolls is non-decreasing
(i.e., the next roll is never less than the current roll)?
For example, the sequence {1, 2, 2, 2, 3, 4, 5, 5, 5, 6} is a non-decreasing sequence.
The total number of possible roll sequences is 610 . How many of these are non-decreasing?
An excellent observation is that every non-decreasing sequence is equivalent to a “histogram"
or vector which gives the number of times each face appears.
For example, the sequence {1, 2, 2, 2, 3, 4, 5, 5, 5, 6} is equivalent to the vector h1, 3, 1, 1, 3, 1i.
By equivalent, I mean that there is a one-to-one correspondence between the sequences and
vectors. So, counting one is equivalent to counting the other.
Thus, we wish to count how many ways can 10 indistinguishable things be placed into 6 bins,
where we allow for zero items to be placed in some bins.
To count that, we observe that this is equivalent to the number of ways to place 16 indistin-
guishable things into 6 bins, where each bin must contain at least one item. Subtracting one
from each bin will give us a vector of the previous sort.
To count this, we can use the stars-and-bars method. Putting 16 things into 6 bins is equiv-
alent to putting 5 bars among 16 stars, such that there is at most one bar between any two
stars. For instance, this choice of bars:
∗ ∗ ∗| ∗ ∗ ∗ ∗ ∗ | ∗ ∗| ∗ | ∗ ∗ ∗ ∗|∗

36
A Collection of Dice Problems Matthew M. Conroy

represents the vector h3, 5, 2, 1, 4, 1i which, if we subtract one from each component yields
the vector h2, 4, 1, 0, 3, 0i which corresponds to the rolled sequence 1, 1, 2, 2, 2, 2, 3, 5, 5, 5.
Since there are 16 stars, there are 15 places for bars, and hence the number of such sequences
is  
15
= 3003
5

Thus, the probability of rolling such a sequence is a very low

3003 1001 1
= = 0.0000496641295788... =
610 20155392 20135.25674...

Generally, for a sequence of n rolls, the probability is

n+6−1


5
pn =
6n

Here is a table of some values

n pn
1 1
2 7
12 = 0.583̄
3 7
27 = 0.259
4 7
72 = 0.0972̄
5 7
216 = 0.032407
6 77
7776 = 0.00990226...
7 11
3888 = 0.00282921...
8 143
186624 = 0.000766246...
9 1001
5038848 = 0.000198656...
10 20155293
1001
= 0.0000496641...
The value of p12 is greater than one-in-a-million, but p13 is less.

21. Suppose a pair of dice are thrown, and then thrown again. What is the probability that the faces
appearing on the second throw are the same as the first?
What if three dice are used? Or six?

We may consider two cases. If two dice are thrown, the result will either be two different
faces, or the same face twice. We may notate these two cases as “AB" and “AA" (this will be
useful later). The probability that two different faces will appear is
6·5 5
2
=
6 6
and the probability that the second throw will be the same as the first in this case is
2
.
62
Thus, the probability that the second roll will repeat the first in this way is
6·5·2 5
4
= .
6 108

37
A Collection of Dice Problems Matthew M. Conroy

The other possibility of of rolling doubles. This case gives a probability of

  
6 1 6 1
2 2
= 4 =
6 6 6 216

of occurring. Adding together, we find the probability of the second throw being identical to
the first is
5 1 11
+ = = 0.0509259....
108 216 216
If we throw three dice, there are more cases to consider. These cases may be expressed as
AAA, AAB, and ABC. (For example, throwing {1, 3, 3} would be an example of the AAB
case, while {2, 4, 5} would be an example
 6
 of the ABC case.) The probability of repeating via
AAA 1
= 666
1


63 63
 6
5
3

each case is as follows: AAB 3

270
1 1 1
63 63
= 66
 6

·3!
ABC 3!

720
3
63 63
= 66

The first factor in each case is the probability of rolling that case, and the second is the prob-
ability of rolling the same set of faces a second time.
Adding these, we see that the probability of repeating with three dice is
996 83
6
= = 0.02134773662551....
6 3888

For six dice, the problem is similar, just with more cases. Here is the calculation:
AAAAAA 6

1

 6
6 66
= 6612
6·5· 61
AAAAAB 6
= 1080


66 66 612
 6

  6

6·5· 2
AAAABB 66 66
2
= 6750
612
 
 6

6·5·4·(6·5)
AAAABC 66 66
2
= 54000
612
 6
6
  6

AAABBB 2 3
66 66
3
= 6000
612
 
6·5·4· 62 · 41



AAABBC 6 4
= 432000




66 2 1 612
 6


6·5·4·3· 3
AAABCD 6·5·4
= 864000


66 66 612
6 4
   !
 6
4

6·5·4· 2 3! 2
AABBCC 66
2 2
66
= 162000
612
6 4 2
    !
2

2 1 6
4
2


6·5·4·3·
AABBCD 66
2·2 2 2 1
66
= 2916000
612
6 4 3 2
     ! 
6·5·4·3·2 2 1 4! 1 1 6
4
3
2

AABCDE 66
2 1 1 1
66
= 3888000
612

ABCDEF 6! 6! 518400



66 66
= 612
(For example, rolling {1, 2, 3, 3, 5, 5} would be an example of the AABBCD case.)

38
A Collection of Dice Problems Matthew M. Conroy

The first factor in each case is the probability of rolling that case, and the second is the prob-
ability of rolling the same set of faces a second time.
Adding the probabilities for all cases gives a total probability of
8848236 737353
12
= = 0.004064823502...
6 181398528
22. What is the most probable: rolling at least one six with six dice, at least two sixes with twelve dice,
or at least three sixes with eighteen dice? (This is an old problem, frequently connected with Isaac
Newton.)
One way to solve this is to simply calculate the probability of each. The probability of rolling
exactly m sixes when rolling r six-sided dice is
  r−m
r 5
m 6r
so the probability of rolling at least m sixes when rolling r six-sided dice is
r   r−i
X r 5
p(m, r) = .
i 6r
i=m

Grinding through the calculations yields

31031
p(1, 6) = ≈ 0.66510202331961591221
46656
1346704211
p(2, 12) = ≈ 0.61866737373230871348
2176782336
15166600495229
p(3, 18) = ≈ 0.59734568594772319497
25389989167104
so that we see that the six dice case is the clear winner.

23. Suppose we roll n dice, remove all the dice that come up 1, and roll the rest again. If we repeat this
process, eventually all the dice will be eliminated. How many rolls, on average, will we make? Show,
for instance, that on average fewer than O(log n) throws occur.
We expect that, on average, 5/6 of the dice will be left after each throw. So, after k throws,

k
we expect to have n 56 dice left. When this is less than 2, we have, on average less than 6
throws left, so the number of throws should be, on average, something less than a constant
time log n.
Let Mn be the expected number of throws until all dice are eliminated. Then, thinking in
terms of a Markov chain, we have the recurrence formula
 n n−1  5j
1 5 X 
n
Mn = n + (1 + Mn ) + (1 + Mj ) n − j
6 6 6n
j=1

which allows us to solve for Mn :

n−1
n
X  
n
1+5 + (1 + Mj ) n−j 5j
j=1
Mn =
6n − 5n
Here are a few values of Mn .

39
A Collection of Dice Problems Matthew M. Conroy

n Mn
1 6
2 8.72727272727273
3 10.5554445554446
4 11.9266962545651
5 13.0236615075553
6 13.9377966973204
7 14.7213415962620
8 15.4069434778816
9 16.0163673664838
10 16.5648488612594
15 18.6998719821123
20 20.2329362496041
30 22.4117651317294
40 23.9670168145374
50 25.1773086926527

We see that Mn increases quite slowly, another suggestion that Mn = O(log n). To show this,
suppose Mj < C log j for all 2 ≤ j < n. Then we have
n−1
X n

n
1 + 5 + max{1 + 6, 1 + C log(n − 1)} n−j 5j
j=1
Mn <
6n − 5n

1 + 5n + C log(n − 1)(6n − 5n − 1) 1 + 5n
 
1
= = C 1 − log(n − 1) + < C log n
6n − 5n 6n − 5n 6n − 5n
if and only if
1 + 5n
 
1 log(n − 1)
1− n + <1
6 − 5n log n C log n(6n − 5n )
Since M2 / log 2 < 13, we may suppose C = 13. It is not hard to show the above inequality
holds for all n, and hence Mn < 13 log n for all n ≥ 2.

24. Suppose we roll a die 6k times. What is the probability that each possible face comes up an equal
number of times (i.e., k times)? Find an asymptotic expression for this probability in terms of k.
In the 6k rolls, we want k of them to appear as the face “1". There are
 
6k
k
ways this can occur. There are then  
5k
k
ways for k 2s to occur among the 6k − k = 5k remaining spots.
Continuing, we can conclude that there are
      
6k 5k 4k 3k 2k k
k k k k k k
ways to rolls an equal number of each face when rolling 6k times.
Hence the probability of this happening is
6k 5k 4k 3k 2k





k

k k k k k k (6k)!
=
66k (k!)6 66k

40
A Collection of Dice Problems Matthew M. Conroy

after simplification.
By applying Stirling’s approximation for the factorial,

n!
lim √ n n

=1
n→∞ 2πn e

we can approximate the probability as

√
6k
(6k)! 2π · 6k 6ke
≈ √
k 6
(k!)6 66k
2πk ke 66k
2π · 6k
=
(2πk)3
√
6
= 5/2
k −5/2
(2π)

Let P (k) be the probability of rolling an equal number of all faces in 6k rolls of a die. Then
we have
P (k)
lim √ = 1.
k→∞ 6 −5/2
(2π)5/2 k

25. Call a “consecutive difference" the absolute value of the difference between two consecutive rolls of a
die. For example, the sequence of rolls 14351 has the corresponding sequence of consecutive differences
3, 1, 2, 4. What is the expected number of times we need to roll a die until all 6 consecutive differences
have appeared?
We can solve this with a Markov chain.
Here, we can define the state to be a pair (d, S), where d is the latest roll of the die, and S is
the set of differences already achieved.
For computation, we can define a vector ha1 , a2 , a3 , a4 , a5 , a6 i with ai = 1 if i ∈ S, and ai = 0
if i 6∈ S.
We can then convert the state pair (d, S) into a unique non-negative integer by
6
X
s = 64(d − 1) + 2i−1 ai .
i=1

Thus, each state corresponds to a row of a 384 × 384 matrix.

We may define a 385th row (and column) corresponding to the absorbing, “finished" state,
since once we have achieved all differences, it does not matter what additional rolls occur.
We then calculate, for each state, the new state attained by rolling 1, 2, . . . 6 on the next roll
and add this information to create the transition matrix.
Here is some GP code that does this:

{
A=vector(6);
M=matrix(64*6+1,64*6+1);

41
A Collection of Dice Problems Matthew M. Conroy

for(a0=0,1,for(a1=0,1,for(a2=0,1,for(a3=0,1,for(a4=0,1,for(a5=0,1,
for(d=1,6,
A=[a0,a1,a2,a3,a4,a5];
state1=64*(d-1)+sum(i=1,6,2^(i-1)*A[i]);
for(e=1,6,diff=abs(d-e);B=A;B[diff+1]=1;if(B==[1,1,1,1,1,1],
M[state1+1,64*6+1]=M[state1+1,64*6+1]+1/6,
state2=64*(e-1)+sum(i=1,6,2^(i-1)*B[i]);
M[state1+1,state2+1]=M[state1+1,state2+1]+1/6;
) )
)
))))));
M[385,385]=1;
}

We then let the matrix Q be M with the last row and column removed, and calculate N =
(I − Q)−1 ( as described in Appendix D).
If we sum rows 1, 1 + 64, 1 + 64 · 2, etc., we find that the expected number of rolls needed
after starting the sequence with a roll of d are (approximately)
1 23.77122103041073289277579517
2 25.27138286232360165381869693
3 25.50271996489307011817416107
4 25.50271996489307011817416107
5 25.27138286232360165381869693
6 23.77122103041073289277579517
and since each of these starting rolls is equally likely, the average of these, plus 1, yields the
overall expected number of rolls needed until all absolute differences have occurred:

672875275767847611958914137
≈ 25.84844128587580155492288439.
26031560987606728347794000

Note that in the table above, a 1 or 6 on the first roll markedly reduces the expected number of
rolls, since we must roll a 1 and a 6 consecutively at some point, whereas all other differences
can be achieved in more than one way.

26. Suppose we roll six dice repeatedly as long as there are repetitions among the rolled faces, rerolling all
non-distinct face dice. For example, our first roll might give 112245, in which case we would keep the
45 and roll the other four. Suppose those four turn up 1346 so the set of faces is 134456, and so we
re-roll the two 4 dice, and continue. What is the expected number of rolls until all faces are distinct?
(Problem suggested by Micha Stajszczak)
One way to investigate this process is by treating it as a Markov chain.
Define the states of the Markov chain to be the current number of unique die faces, 0, 1, 2, 3, 4, 5
or 6. We start in state 0 and we are interested in how long, on average, it takes to get to state
6.
Then, we need to create the transition matrix for this chain.
This is a little tedious, so I will just give two examples here of the calculation of entries in the
matrix.

42
A Collection of Dice Problems Matthew M. Conroy

The first entry, the probability of transitioning from state 0 to state 0, can be calculated like
this. In order to get no unique faces, we need to consider partitions of six without 1. There
are four such partitions: 6, 4 + 2, 3 + 3, and 2 + 2 + 2.
The 6 partition corresponds to rolling all identical dice: there are 6 ways to do this out of the
66 possible rolls.
The 4 + 2 partition corresponds to rolling four of one face, and two of a different face. There
are
6!
6·5 = 450
4!2!
ways of doing this out of the 66 possible rolls.
Similarly, for the 3 + 3 partition, there are
6 · 5 6!
= 300
2 3!3!
ways, and for the 2 + 2 + 2 partition, there are
 
6 6!
= 1800
3 2!2!2!
ways, for a total of 2556 ways (out of 66 ) to achieve no unique faces. Thus, the (0, 0) entry in
2556
the transition matrix is 6 .
6
One more example. Consider the transition from state 1 to state 3. If we are in state 1, with
unique face x, to get to state 3 there are two ways:
• a roll of the form abccc
• a roll of the form xxabc
where a, b and c are distinct and not equal to x.
Of the 65 possible rolls, the first way occurs
5·4 5!
· 3 · = 600
2 3!
times, and the second occurs  
5 5!
· = 600.
3 2!
1200
Thus, the (1, 3) transition probability is 5 .
6
In a similar manner, we can arrive at all the transition probabilities, and find the transition
matrix is
 2556 7380 18000 7200 10800  
720  71 205 125 25 25 5
66 6 6 66 6 6 6 6 0 66 1296 1296 324 162 108 0 324 
 426 1230 3000 1200 1800  
120  71 205 125 25 25 5 
 5
 6 65 65 65 65
0 65   1296 1296 324 162 108 0 324


 
 62 178 504 192 336 24 
 31 89 7 4 7 1
 4
 6 6 4 64 6 4 6 4 0 4
6 

 648 648 18 27 27 0 54


 6 18 84 30 72 6   1 1 7 5 1 1

A= 3 3 3 3 3 0 3
 =  36

12 18 36 3 0 36 
 6 6 6 6 6 6   
1 1 1 1 


 0 12 4 18 2  
0 0 0 18 
 0 62 6 2 6 2 0 62
 
  3 9 2
5 1 


 0 5 1  0 0 0 0 0
0 0 0 6 0 6
 
 6 6 
0 0 0 0 0 0 1 0 0 0 0 0 0 1

43
A Collection of Dice Problems Matthew M. Conroy

 0.0548 0.158 0.386 0.154 0.231 0.000 0.0154 

 0.0548 0.158 0.386 0.154 0.231 0.000 0.0154
 0.0478 0.137 0.389 0.148 0.259 0.000 0.0185


≈
 0.0278 0.0833 0.389 0.139 0.333 0.000 0.0278 
 0.000 0.000 0.333 0.111 0.500 0.000 0.0556 

0.000 0.000 0.000 0.000 0.833 0.000 0.167
0.000 0.000 0.000 0.000 0.000 0.000 1.00

Note that the first and second rows are identical. Also, the 5 state is unreachable, but it is
simpler to include it anyway.
Using the method of Appendix D, from A we can determine that the expected number of
rolls until all faces are distinct is
1692288
≈ 31.008483737975263.
54575

Here is a plot of the cumulative distribution of the number of throws:

0.8

0.6

0.4

0.2

20 40 60 80 100 120 140

About 49.35% of the time, state 6 has been reached on or before the throw 21, with about
51.02% reached on or before throw 22.
We can see from the plot above that the most likely number of turns occurs quite early. In
fact, the most likely number of throws is 3, as suggested by this table:

44
A Collection of Dice Problems Matthew M. Conroy

n probability of ending on throw n

1 0.01543209...
2 0.02757773...
3 0.03030101...
4 0.03026457...
5 0.02952035...
6 0.02861288...
7 0.02768562...
8 0.02677581...
9 0.02589256...
If we let E(n) be the expected number of turns that we will be in each state before ending,
we have the following values:
n E(n)
0 1.913064...
1 2.640448...
2 11.443151...
3 4.182134...
4 10.829683...
5 0
So we will spend the most of our time in states 2 and 4.
27. Suppose
Qs we roll n s-sided dice. Let ai be the number of times face i appears. What is the expected value
of i=1 ai ?
(Problem suggested by Isaac Lee.)
We can express the expected number as
X
E= a1 · · · as P (r1 = a1 , r2 = a2 , . . . , rs = as )
a1 ,...,as
a1 +···+as =n
0≤ai ≤n
 
X n! 1
= a1 · · · as
a1 ,...,as a1 !a2 ! · · · as ! sn
a1 +···+as =n
0≤ai ≤n

Now, we can leave out any terms in which a1 · · · as = 0, so we have

X n!
E = s−n
a1 ,...,as (a1 − 1)!(a2 − 1)! · · · (as − 1)!
a1 +···+as =n
1≤ai ≤n
X (n − s)!
= s−n n(n − 1)(n − 2) · · · (n − (s − 1))
a1 ,...,as (a1 − 1)!(a2 − 1)! · · · (as − 1)!
a1 +···+as =n
1≤ai ≤n
X (n − s)!
= s−n n(n − 1)(n − 2) · · · (n − (s − 1)) .
b1 !b2 ! · · · bs !
b1 ,...,bs
b1 +···+bs =n−s
0≤bi

45
A Collection of Dice Problems Matthew M. Conroy

We can then observe that this last sum is the number of ways to assign n − s items into s
distinguishable bins. So, this last sum is equal to sn−s , and finally we have
 
n(n − 1)(n − 2) · · · (n − (s − 1)) n! s! n
E= = = s .
ss (n − s)!ss s s

For example, with six-sided dice (s = 6), we have

n E
6 5/324 ≈ 0.015432
7 35/324 ≈ 0.108024
8 35/81 ≈ 0.432098
9 35/27 ≈ 1.296296
10 175/54 ≈ 3.240740
11 385/54 ≈ 7.129629
12 385/27 ≈ 14.259259
13 715/27 ≈ 26.481481
14 5005/108 ≈ 46.342592
15 25025/324 ≈ 77.237654
16 10010/81 ≈ 123.580246
17 15470/81 ≈ 190.987654
18 7735/27 ≈ 286.481481
19 11305/27 ≈ 418.703703
20 16150/27 ≈ 598.148148
28. What is the probability that, if we roll two dice, the product of the faces will start with the digit ‘1’?
What if we roll three dice, or, ten dice? What is going on?
When we roll two dice, the possible products that begin with the digit ‘1’ are 1, 10, 12, 15,
16 and 18, and these occur with probability 361
, 18 , 9 , 18 , 36
1 1 1 1
, and 18
1
, respectively. Hence, the
probability of the product of two dice starting with the digit ‘1’ is 13 = 0.3.
With three dice, the probability is 65
216 = 0.300925.
Here’s a table with the probabilities for various numbers of dice.

1 1
6 0.16
2 1
3 0.3
3 65
216 0.300925
4 379
1296 0.2924382716...
5 2317
7776 0.2979681069...
6 193
648 0.2978395061...
7 41977
139968 0.2999042638...
8 28123
93312 0.3013867455...
9 3043945
10077696 0.3020477101...
10 18271529
60466176 0.3021776836...
It seems that, if we roll more than one die, the probability is about 0.3. Why is this?
If a positive real number begins with a ‘1’ digit, then the base-10 logarithm of the number
will have a fractional part less than log10 2 = 0.301029995...

46
A Collection of Dice Problems Matthew M. Conroy

If, instead of considering the product of m rolled dice, we consider the base-10 logarithm of
the product, then this can be viewed as a sum of values chosen with equal likelihood from the
set {0, log10 2, log10 3, . . . , log10 m}. By the Central Limit Theorem, the distribution of these
sums will tend toward a Gaussian distribution as m goes to infinity.
We can make some histograms to see this process.
If we consider all rolls of three dice, and take the base-10 logarithm of the product on each
roll, we get the following histogram.
25
20
Frequency

15
10
5
0

0 2 4 6 8

Base−10 logarithm of product of three dice

The greyed portions of the histogram represent those rolls whose products begin with a digit
‘1’.
Here is the same thing, using five dice.
500
400
Frequency

300
200
100
0

0 2 4 6 8

Base−10 logarithm of product of five dice

And here it is using ten dice.

47
A Collection of Dice Problems Matthew M. Conroy

1000000 1500000 2000000 2500000 3000000

Frequency

500000
0

0 2 4 6 8

Base−10 logarithm of product of ten dice

In each histogram, the greyed bit corresponds to products with a base-10 logarithm with
fractional part less than log10 2, i.e., products that start with the digit ‘1’.
As the number of dice tends to infinity, the distribution becomes more and more similar to
a normal distribution. Meanwhile, the variance increases, so the “spread" of the distribution
covers more and more integers - the distribution of the products covers more orders of mag-
nitude. As a result, the number of grey intervals in the histograms will grow to infinity as
well. One can be convinced, then, that, as the number of dice tends to infinity, the greyed
portion of the histogram tends to log10 2 = 0.301029995....
(For a formal argument, it would be sufficient to show that a normal distribution is uniformly
distributed modulo 1 as the variance goes to infinity.)
This is an example of what is often call Benford’s Law, that certain distributions of numbers
tend to have a probability of a leading ‘1’ digit of around log10 2.

29. Suppose we roll an s-sided die repeatedly and multiply the results. What is the expected number of
rolls until the product is a perfect square?
As we multiply each roll to our growing product, what matters is the parity of the exponents
in the prime factorization of the product. That is, the only thing that matters is whether or
not the exponents in the prime factorization are even or odd: if they are all even, then the
product is a square; otherwise, it is not.
As a result of that observation, we see that we can model this problem as a Markov chain
with
2π(s)
states, where π(s) is the number of prime numbers less than or equal to s.
Each state can be represented as a binary vector of dimension 2π(n) .
For example, if we roll a six-sided die, there are three primes to consider, 2, 3, and 5.
Hence, each state can be represented as a vector ha, b, ci where a, b, c ∈ {0, 1} and

a ≡ α2 (mod 2), b ≡ α3 (mod 3), c ≡ α5 (mod 5)

48
A Collection of Dice Problems Matthew M. Conroy

where the current product is

p = 2α2 3α3 5α5 .

We begin with a state of h0, 0, 0i corresponding to an empty product of one.

If we roll a 6, for example, we transition to the state h1, 1, 0i. If we then roll a 3, we transition
to the state h1, 0, 0i. We will reach a squared product exactly when we transition (back) to
the state h0, 0, 0i.
Let A be the transition matrix of the chain.
This chain is aperiodic. We can transition from any state to itself by rolling a 1 (or any other
square). For any state, if we let S be the set of all positive integers n such that we can transition
from state i to state i in exactly n steps, then 1 ∈ S, and so the greatest common divisor of
the elements of S is one. As a result we say that the chain is aperiodic.
This chain is irreducible (aka connected) since we can transition from any state to any other
state with a series of steps with positive probabilities. We can see this by noting that we can
change any state vector to any other state vector by rolling the required sequence of prime
rolls. At most π(s) steps would be required.
In fact, we can get from any state to any other state with exactly π(s) rolls by rolling the
necessary primes and then, if needed, rolling the necessary number of squares needed to
total π(s) rolls. So all entries of Ak are positive for k = π(s).
Since all entries of Ak is positive for some k, the chain is regular, and hence, by Theorem 2 of
Appendix D, there is a stationary distribution z (a vector of dimension s of probabilities) such
that
zA = z
and
lim An = Z
n→∞

where every row of the matrix Z is z.

We note that the matrix A is symmetric: for every state i and j, every roll that would take
from j to i would take use from j to i. Hence, the columns of A sum to one.
D E
As a result, z = π(s)
1 1
, π(s) 1
, . . . , π(s) satisfies zA = z and so we can conclude that
 
1 1 1
z= , ,..., .
π(s) π(s) π(s)

Hence, by Theorem 4 of Appendix D, the expected return time for every state, (including the
initial square state, i.e., the empty product of one) is π(s).
Thus, the expected number of rolls until we reach a square product is π(s).
Example. Let s = 6.
Consider our states as (1, 2, 3, 6, 5, 10, 15, 30) or, equivalently, (000, 100, 010, 110, 001, 101, 011, 111).

49
A Collection of Dice Problems Matthew M. Conroy

Then the transition matrix is

 
1 1 1 1 1
3 6 6 6 6 0 0 0
1 1 1 1 1
 

 6 3 6 6 0 6 0 0 

1 1 1 1 1
0 0 0 
 

 6 6 3 6 6 
1 1 1 1 1 

6 6 6 3 0 0 0 6 
A=

1 1 1 1 1 


 6 0 0 0 3 6 6 6 
 0 1 1 1 1 1 
0 0

6 6 3 6 6 


 0 1 1 1 1 1 
 0 6 0 6 6 3 6 
1 1 1 1 1
0 0 0 6 6 6 6 3

and
 
19 17 17 17 11 1 1 1
108 108 108 108 108 12 12 12
17 19 17 17 1 11 1 1
 
 
 108 108 108 108 12 108 12 12 
 17 17 19 17 1 1 11 1 

 108 108 108 108 12 12 108 12 

 17 17 17 19 1 1 1 11 
3 108 108 108 108 12 12 12 108
A =
 
11 1 1 1 19 17 17 17

 
 108 12 12 12 108 108 108 108 
 1 11 1 1 17 19 17 17 
12 108 12 12 108 108 108 108
 
 
 1 1 11 1 17 17 19 17 
 12 12 108 12 108 108 108 108 
1 1 1 11 17 17 17 19
12 12 12 108 108 108 108 108

which we see has no zero entries. In fact, A2 has no zero entries, but this would not be the
case with, for example, s = 5, since three rolls would be needed to go from the 1 state to the
30 = 2 · 3 · 5 state.
Since A is regular, and A is symmetric, A has a uniform stationary distribution, with all terms
equal to
1 1 1
π(6)
= 3 =
2 2 8
and hence the expected number rolls to attain a square product is 8 when using a six-sided
die.
Interestingly, none of this depends on the fairness of the die used. As long as all faces have
a positive probability of being rolled, the transition matrix will be regular and so all of the
above remains true.

3.2 Dice Sums

30. Show that the probability of rolling 14 is the same whether we throw 3 dice or 5 dice.
This seems like a tedious calculation, and it is. To save some trouble, we can use a computer
algebra system to determine the coefficient of x14 in the polynomials (x+x2 +x3 +x4 +x5 +x6 )3

50
A Collection of Dice Problems Matthew M. Conroy

and (x + x2 + x3 + x4 + x5 + x6 )5 (see Appendix C for an explanation of this method). They

15 540 5
are 15 and 540, respectively, and so the probability in question is 3 = 5 = .
6 6 72
Are there other examples of this phenomenon?
Yes. Let pd (t, n) be the probability of rolling a sum of t with n d−sided dice. Then a few
examples are:
2
• p3 (5, 2) = p3 (5, 3) =
9
10
• p3 (10, 4) = p3 (10, 6) =
81
5
• p4 (9, 3) = p4 (9, 4) =
32
5
• p6 (14, 3) = p6 (14, 5) =
72
4
• p9 (15, 2) = p9 (15, 4) =
81
7
• p20 (27, 2) = p20 (27, 3) =
200
Questions: Are there others? Can we find all of them?

31. Show that the probability of rolling a sum of 9 with a pair of 5-sided dice is the same as rolling a sum
of 9 with a pair of 10-sided dice. Are there other examples of this phenomenon? Can we prove there
are infinitely many such?

Here, by an m-sided die, we mean a die with sides 1, 2, . . . , m all with equal probability of
being thrown.
Since

2
 
1 1 2 3 4 1 4 3 2 1
x + x2 + x3 + x4 + x5 = x10 + x9 + x8 + x7 + x6 + x5 + x4 + x3 + x2
5 25 25 25 25 5 25 25 25 25
and  2
1
x + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 + x10


10
1 20 1 9 10 2 7 8 1 2
x + x19 + · · · + x + x9 + x + ··· + + x
100 50 100 25 100 100
we may conclude that the probability of rolling 9 with a pair of 5-sided dice is the same as
with a pair of 10-sided dice.
There are lots of examples. Here is a short table of some:
sides 1 sides 2 sum
5 10 9
5 15 10
10 20 17
10 30 19
15 30 25
13 65 26
15 45 28
17 68 33
Are there infinitely many such examples? We have the following theorem.

51
A Collection of Dice Problems Matthew M. Conroy

Theorem 1 Let m be a positive integer. Then m − 1 is divisible by 8 or the square of an odd prime if
and only if there exist positive integers s1 and s2 , s1 < s2 , such that the probability of rolling a sum
of m with a pair of s1 -sided dice is the same as with a pair of s2 -sided dice.

Proof: Let m be a positive integer. Suppose there exist s1 and s2 as described in the theorem.
From the nature of the probability distributions of sums of a pair of dice, we can conclude
that
m−1 2s1 − m + 1
=
s 2 s21
or equivalently,
2s1 s22
m=1+ .
s21 + s22

Let r = gcd(s1 , s2 ), ŝ1 = r ,

s1
and ŝ2 = r .
s2
Then

2rŝ1 ŝ22
m=1+ .
ŝ21 + ŝ22

Let R = m − 1. Then we have

ŝ21 R + ŝ22 R = 2rŝ1 ŝ22 .
Note that, since s1 < s2 , we cannot have ŝ2 = 1 and so there exists a prime p that divides ŝ2 .
Hence, p2 divides R. If p = 2, we conclude that 8 divides R. Hence m − 1 is either divisible
by 8 or by the square of an odd prime.
Now, suppose m is a positive integer. Let R = m − 1. Suppose R is divisible by the square of
an odd prime or by 8. If R is divisible by an odd prime, let p be that prime; else, let p = 2.
Then let ŝ2 = p and ŝ1 = 1. Let
1 + p2 R
r= .
2 p2
Then
2rŝ1 ŝ22
R= .
ŝ21 + ŝ22
Let
(1 + p2 )R (1 + p2 )R
s1 = and s 2 = .
2p2 2p
Then
2s1 s22
m=1+
s21 + s22
and so the probability of rolling a sum of m with a pair of s1 -sided dice is the same as with
a pair of s2 -sided dice. 
Thus, the infinite sequence of such sums begins 9, 10, 17, 19, 25, 26, 28, 33, 37, 41, 46, 49, 50, ....
Questions: Is there a nice way to characterize the numbers of sides for which there exist
another number of sides for dice yielding equal sum probabilities? The sequence begins

5, 10, 13, 15, 17, 20, 25, 26, 30, 35, 37, 39, 40, 41, . . . .

52
A Collection of Dice Problems Matthew M. Conroy

32. Suppose we roll n dice and sum the highest 3. What is the probability that the sum is 18?
In order for the sum to be 18, there must be at least three 6’s among the n dice. So, we
could calculate probability that there are 3,4,5,. . . ,n 6’s among the n dice. The sum of these
probabilities would be the probability of rolling 18. Since n could be much greater than 3,
an easier way to solve this problem is to calculate the probability that the sum is not 18, and
then subtract this probability from 1. To get a sum that is not 18, there must be 0, 1 or 2 6’s
among the n dice. We calculate the probability of each occurrence:
5n
zero 6’s: the probability is
6n n−1
n5
one 6: the probability is
6
n
n n−2
5
two 6’s: the probability is 2 n
6
Hence, the probability of rolling a sum of 18 is
!
n n−2  n 


5n n5n−1

2 5 5 9 1 2
1− + + = 1 − 1 + n + n = p(n)
6n 6n 6n 6 50 50

say. Then, for example, p(1) = p(2) = 0, p(3) = 1/216, p(4) = 7/432, and p(5) = 23/648.
33. Four fair, 6-sided dice are rolled. The highest three are summed. What is the distribution of the sum?
This is a quick calculation with a tiny bit of coding. In PARI/GP, the computation looks like
this:
gp > A=vector(20);
gp > for(i=1,6,for(j=1,6,for(k=1,6,for(m=1,6,
s=i+j+k+m-min(min(i,j),min(k,m));A[s]=A[s]+1))))
gp > A
[0, 0, 1, 4, 10, 21, 38, 62, 91, 122, 148, 167, 172, 160, 131, 94, 54, 21, 0, 0]

(The funny min(min(i,j),min(k,m)) bit is there because the default min function only works
with two values, and we want the minimum of i, j, k and m.)
If we define A(n) to be the number of rolls out of 64 which yield a sum of n, we have the
following table:

n A(n) probability
3 1 1/1296 ≈ 0.00077
4 4 1/324 ≈ 0.00308
5 10 5/648 ≈ 0.00771
6 21 7/432 ≈ 0.01620
7 38 19/648 ≈ 0.02932
8 62 31/648 ≈ 0.04783
9 91 91/1296 ≈ 0.07021
10 122 61/648 ≈ 0.09413
11 148 37/324 ≈ 0.11419
12 167 167/1296 ≈ 0.12885
13 172 43/324 ≈ 0.13271
14 160 10/81 ≈ 0.12345
15 131 131/1296 ≈ 0.10108
16 94 47/648 ≈ 0.07253
17 54 1/24 ≈ 0.04166
18 21 7/432 ≈ 0.01620

53
A Collection of Dice Problems Matthew M. Conroy

How does this compare to the distribution of the sums of three dice?
We see the most likely roll is 13, compared to a tie for 10 and 11 with a simple roll of three
dice.
18
1 X 15869
The mean roll here is 4 iA(i) = ≈ 12.2445987654... compared to a mean of 10.5
6 1296
i=3
for a simple roll of three dice.
Here is a histogram comparing the distribution of sums for the “roll four, drop one" and the
simple roll three methods.

3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

34. Three fair, n-sided dice are rolled. What is the probability that the sum of two of the faces rolled equals
the value of the other rolled face?
There are two (classes of) ways this can happen.
One way is to get two distinct faces, a and b, with a appearing twice and b = 2a.
The other is to get three distinct faces, a, b and c, with c = a + b.
Let’s suppose we roll the dice and the faces that appear are a, b and c with a ≤ b ≤ c and the
sum of two of them equals the third.
We consider the two cases.
Case 1: If a = b, then c = 2a, and so we must have a ≤ b n2 c. Since there are three permutations
of the set {a, a, 2a}, we see there are jnk
3
2
ways for this to occur out of n3 throws.
Case 2: If a < b, then c = a + b ≤ n and the number of choices of {a, b, c} is
X X jnk  jnk 
|{b : a < b ≤ n − a}| = (n − 2a) = n− −1 .
n n 2 2
1≤a< 2 1≤a≤ 2

54
A Collection of Dice Problems Matthew M. Conroy

Since a, b, and c are distinct, there are six permutations of each possibility, and so there are
jnk  jnk 
6 n− −1
2 2
ways for this case to occur out of n3 total possible throws. Altogether, we have
jnk jnk  jnk  3
3 +6 n− − 1 = n(n − 1).
2 2 2 2
ways for this to occur out of n3 total possibile throws. One can verify the last equality by
treating even and odd n’s separately.
For n = 2, 3, 4, 5, 6, . . . the last expression is 3, 9, 18, 30, 45, . . . The values in this sequence are
the “triangular matchstick numbers" (see A045943 in the OEIS).
Thus the probability of this occurring is

3(n − 1)
,
2n2
with the probability tending to zero as n tends to infinity.
45 5
For n = 6, the probability is 3 = = 0.2083̄.
6 24
35. A fair, n-sided die is rolled until a roll of k or greater appears. All rolls are summed. What is the
expected value of the sum?
The probability that any roll is greater than or equal to k is

n+1−k
n
so the expected number of rolls until a roll of k or greater is
n
.
n+1−k
All but the last one of these rolls is less than k, so the expected value of the sum of these rolls
is  
n 1 + (k − 1)
−1 .
n+1−k 2
We add to this the expected value of the final roll

k+n
2
and so the expectation of the entire sum is

n2 + n
 
n 1 + (k − 1) k + n
−1 + =
n+1−k 2 2 2n − 2k + 2

We can also argue as follows. Let E be the expected value of the sum. On the first roll, the
sum is either less than k or it is k or greater. If it is less, then we can express E like this:

k−1 n+1−k
E = ( {expected value of roll < k} + E) + ( expected value of roll ≥ k)
n n

55
A Collection of Dice Problems Matthew M. Conroy

   
k−1 k n+1−k k+n
= +E +
n 2 n 2

From this we have

k−1
2n(1 − )E = k(k − 1) + (n + 1 − k)(k + n) = n2 + n
n
from which we find
n2 + n
E= .
2n − 2k + 2
More explicitly, and without the assumption of the uniform distribution of the dice values,
we may write
k−1   n
X 1 X 1
E = i+E + i
n n
i=1 i=k
   
k−1 k n+1−k k+n
= +E +
n 2 n 2

and the rest follows as above.

36. A pair of dice is rolled repeatedly. What is the expected number of rolls until all eleven possible sums
have appeared? What if three dice are rolled until all sixteen possible sums have appeared?
This is an example of a so-called coupon collector’s problem. We imagine a person is seeking
to complete a set of n distinct “coupons". Each day they get one coupon chosen at random
from a finite set of possible coupons (the set is replenished each day), and we wish to know
how many days are expected in order to get the complete set.
If the probability of each coupon appearing is the same as all others, the problem is fairly
simple (see problem 9). When the probabilities are not all the same, as is the case with the
sums of pairs of dice, it gets more complicated.
One way to solve this problem is to use Markov chains. This is conceptually straightforward,
but a bit computationally elaborate. As we roll the pair of dice, we consider ourselves in a
state represented by an 11-dimensional vector ha2 , a3 , · · · , a12 i, where ai = 0 or 1 for i =
2, · · · 12, and ai = 1 if and only if a sum of i has been achieved thus far. We start in the
state h0, 0, · · · , 0i and we want to know the expected number of rolls until we are in the state
h1, 1, · · · , 1i (this is our one absorbing state).
Thus there are 211 = 2048 states to this chain.
From each state except the absorbing state, the probability of moving to another state is de-
termined by the probability of rolling each of the so-far unrolled sums.
We can create the transition matrix M for this process, and use it to calculate the expected
value (see Appendix D for more details on this method). The basic idea is to create a tran-
sition matrix M , and from that take a sub-matrix Q, from which the matrix N = (I − Q)−1
is calculated. Then the expected number of rolls needed will be the sum of the values in the
first row of N .
Below is some GP code that creates the transition matrix and calculates the expected value.

56
A Collection of Dice Problems Matthew M. Conroy

A helpful idea here is to assign each state a positive integer via the map
12
X
s(ha2 , a2 , · · · , a1 2i) = 2i−2 ai
i=2

so we can represent each state as a positive integer, rather than as a vector.

A=vector(11);
s(A)=sum(i=1,11,2^(i-1)*A[i]);
p=sum(i=1,6,x^i)*1/6;
B=vector(12);
for(i=2,12,B[i]=polcoeff(p^2,i,x));
M=matrix(2048,2048); \\ allocatemem() as needed to get the required memory
for(a2=0,1,for(a3=0,1,for(a4=0,1,for(a5=0,1,for(a6=0,1,\
for(a7=0,1,for(a8=0,1,for(a9=0,1,for(a10=0,1,for(a11=0,1,for(a12=0,1,\
A=[a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12];\
s0=s(A);\
for(j=2,12,C=A;if(A[j-1]<1,C[j-1]=1;M[s0+1,s(C)+1]=B[j];));\
M[s0+1,s0+1] = sum(j=2,12,B[j]*A[j-1]);\
)))))))))))
print("Found M.");
Q=matrix(2047,2047);
print("Now we have Q.");
for(i=1,2047,for(j=1,2047,Q[i,j]=M[i,j]));
N=(matid(2047)-Q)^(-1)
print("Now we have N.");
print1("The expected value is ",sum(j=1,2047,N[1,j]));

The expected number of rolls is

769767316159
= 61.217384763957....
12574325400

In [?] (equation 14b) , the authors give the following formula for calculating such an expected
value:
m−1
X X 1
E= (−1)m−1−q
1 − PJ
q=0 |J|=q

where m is the number of “coupons", J is a subset of all possible coupons, and PJ =

P
j∈J pj
where pj is the probability of drawing the j-th coupon on any turn.
This requires, essentially, summing over the power set of the set of all coupons. Here is some
PARI/GP code that finds the expected value using this formula:

A=vector(11);
p=sum(i=1,6,x^i)*1/6;
B=vector(12);
for(i=2,12,B[i]=polcoeff(p^2,i,x));
E=0;
for(a2=0,1,for(a3=0,1,for(a4=0,1,for(a5=0,1,for(a6=0,1,\
for(a7=0,1,for(a8=0,1,for(a9=0,1,for(a10=0,1,for(a11=0,1,for(a12=0,1,\
A=[a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12];\
q=sum(i=1,11,A[i]);\

57
A Collection of Dice Problems Matthew M. Conroy

P=sum(i=1,11,A[i]*B[i+1]);\
if(P<1,E=E+(-1)^(11-1-q)*1/(1-P));\
)))))))))));
print(E);

This is definitely a more efficient way to compute this: on one machine, this code takes about
1/10000 as much time as the Markov chain method.
With a small modification to the above code, we can find the expected number of rolls until
all sixteen possible sums are attained when rolling three dice. The expected value is
32780408650180616717098566081494549422317059377168943326909666810782193227427941243843
96853626249252584111109636978626695927366864056199200661045945395107914269245971600
which is about 338.45308554395589, and here is the PARI/GP code:

A=vector(16);
p=sum(i=1,6,x^i)*1/6;
B=vector(18);
for(i=3,18,B[i]=polcoeff(p^3,i,x));
E=0;
for(a3=0,1,for(a4=0,1,for(a5=0,1,for(a6=0,1,\
for(a7=0,1,for(a8=0,1,for(a9=0,1,for(a10=0,1,for(a11=0,1,for(a12=0,1,\
for(a13=0,1,for(a14=0,1,for(a15=0,1,for(a16=0,1,for(a17=0,1,for(a18=0,1,\
A=[a3,a4,a5,a6,a7,a8,a9,a10,a11,a12,a13,a14,a15,a16,a17,a18];\
q=sum(i=1,16,A[i]);\
P=sum(i=1,16,A[i]*B[i+2]);\
if(P<1,E=E+(-1)^(16-1-q)*1/(1-P));\
))))))))))))))));
print(E);

37. A die is rolled repeatedly and summed. What can you say about the expected number of rolls until the
sum is greater than or equal to n?
When a six-sided die is rolled, the expected value of the roll is 72 .
2 n
So, to reach a sum of n, we expect to need about n = rolls.
7 3.5
That’s very rough. Let’s find a more precise expression of the expected value.
Define En to be the expected number of rolls until the sum is at least n.
Then E0 = 0 and E1 = 1.
Since on the first roll, there is a 5/6 probability of getting at least 2, and, if we don’t, the sum
will be at least 2 after the second roll, we have
1 7
E2 = 1 + = .
6 6
That is, E2 = 1 + 16 E1 .
Suppose n = 3. On the first roll, we will get 3 or greater with probability 4/6. If we get a 1,
then the expected number of additional rolls is E2 , and if get a 2, then the expected number
of additional rolls is E1 . Hence,
1 1 49
E3 = 1 + E1 + E2 = .
6 6 36

58
A Collection of Dice Problems Matthew M. Conroy

In the same way,

1 1 1 343
E4 = 1 + E1 + E2 + E3 =
6 6 6 216
1 1 1 1 2401
E5 = 1 + E1 + E2 + E3 + E4 =
6 6 6 6 1296
1 1 1 1 1 16807
E6 = 1 + E1 + E2 + E3 + E4 + E5 = .
6 6 6 6 6 7776

Suppose n > 6. In order to reach a sum of at least n, the final roll must be i after achieving a
sum of at least n − i. Hence,
6
1X
En = 1 + En−i . (3.13)
6
i=1

To help us study En , we will find a generating function for En . Define

∞
X
f (x) = En xn .
n=0

We wish to find a simple, closed-form expression for f .

Multiplying equation 3.13 by xi and summing from n = 6 to ∞ we have
∞ ∞ 6
!
X X 1X
n
En x = n
x + n
En−i x . (3.14)
6
n=6 n=6 i=1

k
X
Define fk (x) = Ei xi . Then equation 3.14 yields
i=0

f (x) − f5 (x) =
∞ 6 ∞
!
X
n 1X X
= x + En−i xn
6
n=6 i=1 n=6
∞ ∞ ∞ ∞
x6 1X n1X 1X 1X
= + En−1 x + En−2 xn + · · · + En−5 xn + En−6 xn
1−x 6 6 6 6
n=6 n=6 n=6 n=6
∞ ∞ ∞ ∞
x6 1 X 1 X 1 X 1 X
= + En xn+1 + En xn+2 + · · · + En xn+5 + En xn+6
1−x 6 6 6 6
n=5 n=4 n=1 n=0
∞ ∞ ∞ ∞
x6 1 X 1 X 1 X 1 X
= + x En xn + x 2
En xn + · · · + x 5
En xn + x 6
En xn
1−x 6 6 6 6
n=5 n=4 n=1 n=0
x6 1 1 1 1
= + x(f (x) − f4 (x)) + x2 (f (x) − f3 (x)) + · · · + x5 (f (x) − f0 (x)) + x6 f (x)
1−x 6 6 6 6

Using the fact that f0 (x) = 0 and simplifying, we have

x6 1 1
f (x) − f5 (x) = + (x + x2 + · · · + x6 )f (x) − (xf4 (x) + x2 f3 (x) + x3 f2 (x) + x4 f1 (x)).
1−x 6 6

59
A Collection of Dice Problems Matthew M. Conroy

Since the fi are just polynomials, we can solve this for f (x) and find that

6x 6x
f (x) = = .
x7 − 7x + 6 (x − 1)2 (x5 + 2x4 + 3x3 + 4x2 + 5x + 6)

Applying the method of partial fractions, we find

2 4 3
2/7 4/21 21 (2x + 3x − 10x − 30)
f (x) = − +
(x − 1)2 x − 1 x5 + 2x4 + 3x3 + 4x2 + 5x + 6
∞ ∞
2X 4 X n
= (n + 1)xn + x + Z(x)
7 21
n=0 n=0
∞  
X 2 10
= n+ xn + Z(x), say.
7 21
n=0

The poles of Z(x) are approximately

− 1.491797988139901,
− 0.805786469389031 ± 1.222904713374410i,
and 0.551685463458982 ± 1.253348860277206i.

The minimum modulus among these poles is R = 1.3693941054897684. As a result, the n-th
coefficient an of the power series of Z(x) satisfies
 n 
1
an = O = O(0.73024997n ).
R

(See, for example, [?], (June 26, 2009 edition), Theorem IV.7 (Exponential Growth Formula),
page 244)).
Thus, we may conclude that

2 10
En = n + + O(0.73024997n ).
7 21
So, En is very closely approximated by 27 n + 10
21 for all but the smallest values of n.
Here is a short table of values. Let g(n) = 2
7n + 21 .
10

60
A Collection of Dice Problems Matthew M. Conroy

n En g(n) En − g(n)

1 1 ≈ 1.000000000 0.7619047619 0.2380952381

2 7/6 ≈ 1.166666667 1.047619048 0.1190476190
3 49/36 ≈ 1.361111111 1.333333333 0.02777777778
4 343/216 ≈ 1.587962963 1.619047619 −0.03108465608
5 2401/1296 ≈ 1.852623457 1.904761905 −0.05213844797
6 16807/7776 ≈ 2.161394033 2.190476190 −0.02908215755
7 117649/46656 ≈ 2.521626372 2.476190476 0.04543589555
8 776887/279936 ≈ 2.775230767 2.761904762 0.01332600513
9 5111617/1679616 ≈ 3.043324784 3.047619048 −0.004294263859
10 33495175/10077696 ≈ 3.323693729 3.333333333 −0.009639604132
15 4.760008377 4.761904762 −0.001896385320
20 6.190195199 6.190476190 −0.0002809914888
25 7.619081612 7.619047619 0.00003399272215
30 9.047634594 9.047619048 0.00001554676498
35 10.47619480 10.47619048 0.000004327490791
40 11.90476290 11.90476190 0.0000009934675945
45 13.33333351 13.33333333 0.0000001795084385
50 14.76190478 14.76190476 0.00000001842084560
60 17.61904762 17.61904762 −0.000000000990023724
70 20.47619048 20.47619048 −8.20317511 × 10−11
80 23.33333333 23.33333333 −1.896370261 × 10−12
90 26.19047619 26.19047619 6.32378328 × 10−14
100 29.04761905 29.04761905 6.478729760 × 10−15
We see that En is extremely closely approximated by 27 n + 10
21 as n gets large.

38. A die is rolled repeatedly and summed. Show that the expected number of rolls until the sum is a
multiple of n is n.
We will treat small n first. We will use the fact that the expected number of additional rolls
until the sum is a multiple of n depends only on the residue class of the sum modulo n (e.g.,
the expected number of additional rolls until the sum is a multiple of 4 is the same whether
the sum is 3, 7, 11, or any other value congruent to 3 modulo 4).
Let n = 2. Then the expected number of rolls, E until the sum is a multiple of n is
1
E = 1 + E1
2
and
1
E1 = 1 + E1
2
where E1 is the expected number of additional rolls from an odd sum (i.e., a sum congruent
to 1 mod 2). These equations arise from the fact that half of the values {1, 2, 3, 4, 5, 6} are
even and half are odd, so there is a one-half chance of the first roll ending in an odd sum, and
from there, a one-half chance of staying with an odd sum. These two equations easily lead
to E = 2.
Let n = 3, and let E be the expected number of rolls until the sum is a multiple of three, and
E1 and E2 be the expected number of additional rolls from a sum congruent to 1 or 2 mod 3.
Then we have
1 1
E = 1 + E1 + E2
3 3
1 1
E1 = 1 + E1 + E2
3 3

61
A Collection of Dice Problems Matthew M. Conroy

1 1
E2 = 1 + E1 + E2
3 3
As in the n = 2 case, the fact that {1, 2, 3, 4, 5, 6} are uniformly distributed mod 3 results in
three identical expressions, and so we find E = E1 = E2 = 3.
The n = 4 case is a little different, since {1, 2, 3, 4, 5, 6} is not uniformly distributed modulo
4. As a result, our equations, following the scheme above, are
1 1 1
E = 1 + E1 + E2 + E3
3 3 6
1 1 1
E1 = 1 + E1 + E2 + E3
6 3 3
1 1 1
E2 = 1 + E1 + E2 + E3
6 6 3
1 1 1
E3 = 1 + E1 + E2 + E3
3 6 6
Solving this system, we find E1 = 98
25 , E2 = 84
25 , E3 = 25 ,
86
and E = 4.
The n = 5 case is similar. We have
1 1 1 1
E = 1 + E1 + E2 + E3 + E4
3 6 6 6
1 1 1 1
E1 = 1 + E1 + E2 + E3 + E4
6 3 6 6
1 1 1 1
E2 = 1 + E1 + E2 + E3 + E4
6 6 3 6
1 1 1 1
E3 = 1 + E1 + E2 + E3 + E4
6 6 6 3
1 1 1 1
E4 = 1 + E1 + E2 + E3 + E4
6 6 6 6
which yields E1 = 1554
311 , E2 = 1548
311 , E3 = 1512
311 , E4 = 1296
311 and E = 5.
For n = 6, we can conclude more easily. Since {1, 2, 3, 4, 5, 6} is uniformly distributed modulo
6, we have E = E1 = E2 = E3 = E4 = E5 and so
5
E =1+ E
6
and thus E = 6.
Suppose n > 6. Define E and Ei as above. Then we have the following system of equations.

1 1
E = 1 + E1 + · · · + E6
6 6
1 1
E1 = 1 + E2 + · · · + E7
6 6
.. .. .. .. .. .. ..
. . . . . . .
1 1
En−7 = 1 + En−6 + · · · + En−1
6 6
1 1
En−6 = 1 + En−5 + · · · + En−1
6 6

62
A Collection of Dice Problems Matthew M. Conroy

1 1 1
En−5 = 1 + En−4 + · · · + En−1 + E1
6 6 6
1 1 1 1
En−4 = 1 + En−3 + · · · + En−1 + E1 + E2
6 6 6 6
1 1 1 1
En−3 = 1 + En−2 + · · · + En−1 + E1 + · · · E3
6 6 6 6
1 1 1 1
En−2 = 1 + En−1 + · · · + En−1 + E1 + · · · E4
6 6 6 6
1 1
En−1 = 1 + E1 + · · · + E5
6 6

Summing, and counting, we have

n−1 n−1 n−1
X X 1 X
E+ Ei = n + 6 · Ei = n + Ei
6
i=1 i=1 i=1

and so E = n.
A curious feature of this is that a uniform distribution of dice values is actually not necessary
to have n rolls be the expected value. A variety of other kinds of die distributions (appear
to) yield n also. So a question is: what are necessary conditions on the values of a die so that
n is the expected number of rolls until the sum is a multiple of n?

39. A fair, n-sided die is rolled and summed until the sum is at least n. What is the expected number of
rolls?
To solve this, we will use some recursive expressions.
Let E(m) be the expected number of rolls until the sum is at least n, starting with a sum of
m.
Then we have:

E(n) = 0
E(n − 1) = 1
1 1
E(n − 2) = 1 + E(n − 1) = 1 +
n n
1 1
E(n − 3) = 1 + E(n − 2) + E(n − 1)
n n
1 1 1
=1+ (1 + E(n − 1)) +
n n n
2 1
=1+ +
n n2
1 1 1
E(n − 4) = 1 + E(n − 3) + E(n − 2) + E(n − 1)
n n n
3 3 1
=1+ + 2+ 3
n n n

Suppose
k−1
X k−1


i
E(n − k) =
ni
i=0

63
A Collection of Dice Problems Matthew M. Conroy

for 1 ≤ k < r.
Then
r−1 r−1 m−1 m−1

1 X 1 X X i
E(n − r) = 1 + E(n − m) = 1 +
n n ni
m=1 m=1 i=0
r−2 r−2   r−2  
1 X 1 X j 1 X 1 r−1
=1+ =1+
n ni i n ni i + 1
i=0 j=i i=0
r−2   r−1  
X 1 r−1 X 1 r−1
=1+ =1+
ni+1 i + 1 ni i
i=0 i=1
r−1  
X 1 r−1
=
ni i
i=0

m    
X k m+1
(Here we have used the lovely identity = .)
r r+1
k=r
k−1
X k−1


Thus by induction, we have E(n − k) = i
for 1 ≤ k ≤ n.
ni
i=0
The value we seek is E(0):
n−1 n−1

 n−1
X
i 1
E(0) = = 1+ .
ni n
i=0

We observe the curiosity that as n → ∞, E(0) → e.

We have the following values:
n E(0) exact E(0) approx.
1 1 1.0000
2 3/2 1.5000
3 16/9 1.7778
4 125/64 1.9531
5 1296/625 2.0736
6 16807/7776 2.1614
7 262144/117649 2.2282
8 4782969/2097152 2.2807
9 100000000/43046721 2.3231
10 2357947691/1000000000 2.3579
20 2.5270
100 2.6780
500 2.7101
1000 2.7142

40. A die is rolled and summed repeatedly. What is the probability that the sum will ever be a given value
x? What is the limit of this probability as x → ∞?
Let’s start by considering 2-sided dice, with sides numbered 1 and 2. Let p(x) be the proba-
bility that the sum will ever be x. Then p(1) = 1/2 since the only way to ever have a sum of
1 is to roll 1 on the first roll. We then have p(2) = 1/2 + 1/2p(1) = 3/4, since there are two
mutually exclusive ways to get a sum of 2: roll 2 on the first roll, or roll a 1 followed by a 1
on the second roll. Now, extending this idea, we have, for x > 2,
1 1
p(x) = p(x − 1) + p(x − 2). (3.15)
2 2

64
A Collection of Dice Problems Matthew M. Conroy

This equation could be used to calculate p(x) for any given value of x. However, this would
require calculating p for all lower values. Can we get an explicit expression for p(x)?
Equation 3.15 is an example of a linear recurrence relation. One way to get a solution, or explicit
formula, for such a relation is by examining the auxiliary equation for equation 3.15:
1 1
x2 = x +
2 2
or
1 1
x2 − x − = 0
2 2
The roots of this equation are
1
α = 1 and β = −
2
A powerful theorem (see Appendix E) says that
 n
n n 1
p(n) = Aα + Bβ = A + B −
2
for constants A and B. Since p(1) = 1/2 and p(2) = 3/4 we can solve for A and B to find that
 n
2 1 1
p(n) = + − .
3 3 2

For 3-sided dice, we have

1 4 16
p(1) = , p(2) = , and p(3) =
3 9 27
with, for n > 3,
3
1 1X
p(n) = (p(n − 1) + p(n − 2) + p(n − 3)) = p(n − i).
3 3
i=1

The characteristic equation for this recurrence equation can be written

3x3 − x2 − x − 1 = 0

which has roots √ √

1 2 1 2
α = 1, β = − − i, and γ = − + i.
3 3 3 3
Using these, and the fact that
1 4 16
p(1) = , p(2) = , and p(3) = ,
3 9 27
we find
1 1 n 1 n
p(n) =+ β + γ .
2 4 4
Since β and γ are complex conjugates, and, in any case, p(n) is always real, we might prefer
to write p(n) like this:

1 n
    
1 1 π −1 1
p(n) = + √ cos n + tan √
2 2 3 2 2

65
A Collection of Dice Problems Matthew M. Conroy

Using this formula to generate a table, we see that while p(n) is asymptotic to the value 1/2,
it wobbles quite a bit:
x p(x) p(x) − p(x − 1)
1 0.3333333333333333333333333333
2 0.4444444444444444444444444444 0.1111111111111111111111111111
3 0.5925925925925925925925925925 0.1481481481481481481481481481
4 0.4567901234567901234567901234 -0.1358024691358024691358024691
5 0.4979423868312757201646090534 0.04115226337448559670781893002
6 0.5157750342935528120713305898 0.01783264746227709190672153636
7 0.4901691815272062185642432556 -0.02560585276634659350708733424
8 0.5012955342173449169333942996 0.01112635269013869836915104404
9 0.5024132500127013158563227150 0.001117715795356398922928415384
10 0.4979593219190841504513200901 -0.004453928093617165405002624938
11 0.5005560353830434610803457015 0.002596713463959310629025611496
12 0.5003095357716096424626628355 -0.0002464996114338186176828660183
13 0.4996082976912457513314428757 -0.0007012380803638911312199598200
14 0.5001579562819662849581504709 0.0005496585907205336267075952194
15 0.5000252632482738929174187274 -0.0001326930336923920407317435396
16 0.4999305057404953097356706913 -0.00009475750777858318174803604667
17 0.5000379084235784958704132966 0.0001074026830831861347426052109
18 0.4999978924707825661745009051 -0.00004001595279592969591239145842
19 0.4999887688782854572601949643 -0.000009123592497108914305940764722
20 0.5000081899242155064350363887 0.00001942104593004917484142432929
Let’s skip over 4- and 5-sided dice to deal with 6-sided dice. Let p(x) be the probability that
the sum will ever be x. We know that:
1
p(1) =
6
1 1 7
p(2) =
+ p(1) =
6 6 36
1 1 1 49
p(3) = + p(2) + p(1) =
6 6 6 216
1 1 1 1 343
p(4) = + p(3) + p(2) + p(1) =
6 6 6 6 1296
1 1 1 1 1 2401
p(5) = + p(4) + p(3) + p(2) + p(1) =
6 6 6 6 6 7776
1 1 1 1 1 1 16807
p(6) = + p(5) + p(4) + p(3) + p(2) + p(1) =
6 6 6 6 6 6 46656
and for x > 6,
6
1X
p(x) = p(x − i).
6
i=1

The corresponding characteristic equation

6x6 − x5 − x4 − x3 − x2 − x − 1 = 0

has roots, approximately,

A1 = 1
A2 = −0.67033204760309682774
A3 = −0.37569519922525992469 − 0.57017516101141226375i
A4 = A3
A5 = 0.29419455636014167190 − 0.66836709744330106478i
A6 = A5

66
A Collection of Dice Problems Matthew M. Conroy

Solving the system of equations

6
ci Aji , j = 1, . . . , 6
X
p(j) =
i=1

we find c1 = 2
7 and ci = 1
7 for i = 2, . . . , 7.
Hence, we may express p(n) as
6
2 1X n
p(n) = + Ai .
7 7
i=2

Since all the Ai except A1 have absolute value less than one, we may conclude that
2
lim p(n) = .
n→∞ 7

Here’s a table of the values of p(x) and p(x) − p(x − 1) for x ≤ 20:
x p(x) p(x) − p(x − 1)
1 0.1666666666666666666666666666
2 0.1944444444444444444444444444 0.02777777777777777777777777777
3 0.2268518518518518518518518518 0.03240740740740740740740740740
4 0.2646604938271604938271604938 0.03780864197530864197530864197
5 0.3087705761316872427983539094 0.04411008230452674897119341563
6 0.3602323388203017832647462277 0.05146176268861454046639231824
7 0.2536043952903520804755372656 -0.1066279435299497027892089620
8 0.2680940167276329827770156988 0.01448962143728090230147843316
9 0.2803689454414977391657775745 0.01227492871386475638876187573
10 0.2892884610397720537180985283 0.008919515598274314552320953784
11 0.2933931222418739803665882007 0.004104661202101926648489672418
12 0.2908302132602384366279605826 -0.002562908981635543738627618117
13 0.2792631923335612121884963084 -0.01156702092667722443946427417
14 0.2835396585074294008073228155 0.004276466173868188618826507133
15 0.2861139321373954704790406683 0.002574273629966069671717852795
16 0.2870714299200450923645845173 0.0009574977826496218855438489728
17 0.2867019247334239321389988488 -0.0003695051866211602255856684957
18 0.2855867251486822574344006235 -0.001115199584741674704598225314
19 0.2847128104634228942354739637 -0.0008739146852593631989266598476
20 0.2856210801517331745766369062 0.0009082696883102803411629425406
Here’s another proof that p(n) approaches 2
7 (proof idea from Marc Holtz).
First, let’s define a sequence of vectors v(i):

v(i) = hp(i), p(i − 1), p(i − 2), p(i − 3), p(i − 4), p(i − 5)i.

If we then define the matrix M:

 1 1 1 1 1 1 
6 6 6 6 6 6
 1 0 0 0 0 0 
M = 0 1 0 0 0 0
 
 0 0 1 0 0 0


0 0 0 1 0 0
0 0 0 0 1 0

Then it’s not hard to show that

M v(i) = v(i + 1)

What we are interested in, then is M ∞ v(j) = lim v(i), where j is any finite value (but we
i→∞
may as well take it to be six, since we’ve calculated p(1),...,p(6) already

67
A Collection of Dice Problems Matthew M. Conroy

Note that each entry of M is between 0 and 1, each row of M sums to one, and M 6 has no
zero entries:  16807 9031 7735 6223 4459 2401 
46656 46656 46656 46656 46656 46656
 2401 2401 1105 889 637 343 
7776 7776 7776 7776 7776 7776 
 

 343 343 343 127 91 49 
 1296 1296 1296 1296 1296 1296 
M6 = 
 
49 49 49 49 13 7 

 216 216 216 216 216 216 
 7 7 7 7 7 1 
 36 36 36 36 36 36 
 
1 1 1 1 1 1
6 6 6 6 6 6

So, we can consider M to be a transition matrix of a regular Markov system. Hence M ∞ is a

matrix with all identical rows given by the vector w where the sum of the entries of w equals
1, and
wM = w.

A little simple algebra shows that

 
2 5 4 1 2 1
w= , , , , ,
7 21 21 7 21 21

Hence, v(∞) is a vector of six identical probabilities equal to

2
w · v(6) =
7

2
Thus, lim = .
i→∞ 7
More questions:

(a) Notice that while p(x) is settling down on 27 , it does so quite non-monotonically: p(x)
increases to its maximum at x = 6, and then wobbles around quite a bit. Is the sequence
p(i) eventually monotonic, or does it always wobble?

41. A die is rolled and summed repeatedly until the sum is 100 or more. What is the most likely last roll?
What if we roll two dice at time? Three, etc.? (Problem suggested by Dimitris Konomis.
When rolling a single die, the most likely final roll is six.
We can see this by expressing the probability of each possible final roll. Let p(x) be the prob-
ability that our sum is ever equal to x, as we roll and sum to 100. We know p(x) > 0 for all x,
since there is the possibility of simply rolling ”1" over and over.
Let r(x) be the probability that the final roll is x.
Then:
1
r(1) = p(99)
6
1
r(2) = (p(99) + p(98))
6
1
r(3) = (p(99) + p(98) + p(97))
6

68
A Collection of Dice Problems Matthew M. Conroy

1
r(4) = (p(99) + p(98) + p(97) + p(96))
6
1
r(5) = (p(99) + p(98) + p(97) + p(96) + p(95))
6
1
r(6) = (p(99) + p(98) + p(97) + p(96) + p(95) + p(94))
6
so we see that r(6) > r(5) > r(4) > · · · > r(1) regardless of the values of p(x). So, six is the
most likely final roll.
2
Now, as x goes to infinity (along with our “rolling until" bound), p(x) approaches , and in
7
fact, p(94), p(95), . . . , p(99) are all extremely close to 2/7, so in fact six is the final roll some-
thing very close to 6/21 = 2/7 of the time, while five is the final roll about 5/21 of the time,
etc.
To illustrate what I mean by very close, the actual probability that the final roll is six differs
from 2/7 by about 5.2 × 10−15 ; the actual probability is just this tiny amount less than 2/7.
What if we roll two dice at a time, and sum the pair sums until the sum is 100 or more? What
is the most likely final pair sum?
The probability that a pair sum is x is 1 − 16 |x − 7| = sx , say, and the probability that the final
pair sum is x can be calculated as
99
X
r(x) = sx p(j)
j=100−x

where p(j) now is the probability that the running sum is ever j.
Since we know sx is symmetric about 7, we can conclude that r(8) > r(6), r(9) > r(5), etc.
So, the maximum r(x) must occur among 7, 8, 9, 10, 11, 12. Then, for these values of x, the
probability of rolling x is 13−x
6 and, again, we can treat p as essentially constant here: for
88 ≤ j ≤ 100, p(j) differs from 17 by less than 2 × 10−9 . Hence, the probability of the final roll
being x can be expressed as essentially proportional to

(13 − x)x = 13x − x2

which is maximal when x = 6.5, so r(7) has the highest value among possible die rolls and
so 7 is the most likely final roll.
So, in the one-die case, the largest face is most likely the last roll, and in the two-dice case,
the most likely sum is the most likely last roll.
What if we use three or more dice?
Let’s do some calculations. When rolling n dice, let rn (x) be the probability of rolling a sum
of x. We are interested in the x which maximizes

xrn (x)

for each n; let γn be this x. Also, let’s assume we increase our bound of 100 as needed so that
p(x) (as defined above) is sufficiently constant. Calculating, we have the following results:

69
A Collection of Dice Problems Matthew M. Conroy

n γn
1 6 =n(7/2)+ 5/2
2 7 =n(7/2)+ 0
3 12 =n(7/2)+ 3/2
4 15 =n(7/2)+ 1
5 18 =n(7/2)+ 1/2
6 22 =n(7/2)+ 1
7 25 =n(7/2)+ 1/2
8 29 =n(7/2)+ 1
9 32 =n(7/2)+ 1/2
10 36 =n(7/2)+ 1
11 39 =n(7/2)+ 1/2
12 43 =n(7/2)+ 1
13 46 =n(7/2)+ 1/2
14 50 =n(7/2)+ 1
15 53 =n(7/2)+ 1/2
16 57 =n(7/2)+ 1
17 60 =n(7/2)+ 1/2
18 64 =n(7/2)+ 1
19 67 =n(7/2)+ 1/2
20 71 =n(7/2)+ 1
So, for n = 3, we see the most likely last roll is 12. For n > 3, we see a clear pattern: for odd
n, the most likely last roll is the most likely roll (greater than the median), while for even n,
it is one more than the most likely roll.
Here I will give some supporting evidence that this should be so, for all n ≥ 3.
We can approximate the distribution of p(x) for any fixed n using a Gaussian distribution
7 35
with mean µ = n and variance σ 2 = n. (Since these are the mean and variance of the
2 12
discrete distribution, it is not a terrible approximation).
We are interested in where the maximum of
1 1 x−µ 2
g(x) = x · √ e− 2 ( σ )
σ 2π
occurs. Using differentiation, we find the peak is at
r
µ µ2
x0 = + + σ2
2 4
We can tell that this is greater than µ, but how much greater?
Using Taylor series, we can show that
1 1 √ 1
1 + x − x2 < 1 + x < 1 + x
2 8 2
for all x ≥ 0, and from this conclude that
 2
5 5 1 5
µ+ − < x0 < µ + .
6 6 µ 6

70
A Collection of Dice Problems Matthew M. Conroy

5
So, for n > 3, x0 is very close to µ + . When n is even, the nearest integer to µ + 5
6 is µ + 1.
6
when n is odd, the nearest integer to µ + 56 is µ + 12 .

42. A die is rolled and summed repeatedly. Let x be a positive integer. What is the probability that the sum
will ever be x or x + 1? What is the probability that the sum will ever be x, x + 1, or x + 2? Etc.?
In an earlier problem, we worked out the probability that the sum will ever be x. Let p(x)
be this probability. Then, with inclusion-exclusion, we can work out the sought probabilities
for this problem.
The probability that the sum is ever x or x + 1 is

p(x) + p(x + 1) − q

where q is the probability that the sum will be both x and x + 1. Since the only way that can
happen is for the sum to reach x and then one appears as the next die roll, the probability is
 
1
q = p(x) .
6

Thus, the probability that the sum is ever x or x + 1 is

5
p(x) + p(x + 1).
6

Since p(x) approaches 27 as x goes to infinity, we can conclude that the probability that the
sum will ever be x or x + 1 is asymptotic to 11
21 ≈ 0.5238095.
Now, let’s consider the probability that the sum will ever be x, x + 1, or x + 2.
Let P (S) be the probability that the sum will ever be in the set S. Let An be the event that the
sum is ever equal to n.
By inclusion-exclusion,

P ({x} ∪ {x + 1} ∪ {x + 2}) = P ({x}) + P ({x + 1}) + P ({x + 2})

−P ({x} ∩ {x + 1}) − P ({x} ∩ {x + 2}) − P ({x + 1} ∩ {x + 2}) + P ({x} ∩ {x + 1} ∩ {x + 2})

       
1 7 1 1
= p(x) + p(x + 1) + p(x + 2) − p(x) − p(x) − p(x + 1) + p(x)
6 36 6 36
2 5
= p(x) + p(x + 1) + p(x + 2).
3 6
Thus, as x goes to infinity, the probability that the sum will ever be x, x+1 or x+2 approaches
5
7 ≈ 0.7142857.
Now, let’s consider the probability that the sum will ever be x, x + 1, x + 2 or x + 3.
If this happens, then the sum will either be x, or it will be at least one of x + 1, x + 2 and x + 3.
Using the calculation we just did, and a tiny bit of inclusion-exclusion, we can conclude that
the probability that the sum is ever x, x + 1, x + 2 or x + 3 is
   
2 5 1 1 2 5
p(x)+ p(x + 1) + p(x + 2) + p(x + 3) −p(x) = p(x)+ p(x+1)+ p(x+2)+p(x+3).
3 6 2 2 3 6

71
A Collection of Dice Problems Matthew M. Conroy

(This p(x) 12 bit is due to the probability that the sum is x and one of x + 1, x + 2 and x + 3 is
equal to p(x) times the probability that the roll after hitting x is less then 4 (i.e., 1/2).)
Thus, as x goes to infintiy, the probability approaches 27 12 + 23 + 56 + 1 = 67 .

Now, let’s consider the probability that the sum will ever be x, x + 1, x + 2, x + 3 or x + 4.
Just like the last case, we can utilize the previous calculation and find that the probability is
   
1 2 5 2
p(x) + p(x + 1) + p(x + 2) + p(x + 3) + p(x + 4) − p(x)
2 3 6 3
1 1 2 5
= p(x) + p(x + 1) + p(x + 2) + p(x + 3) + p(x + 4).
3 2 3 6
Thus, as x approaches infinity, the probability approaches 27 13 + 12 + 23 + 5 20


6 +1 = 21 ≈
0.952380...
This is, of course, as far as we can go, since the sum is guaranteed to hit at least one of x, x + 1,
x + 2, x + 3, x + 4 and x + 5 for every x.

43. A die is rolled once; call the result N . Then N dice are rolled once and summed. What is the distribution
of the sum? What is the expected value of the sum? What is the most likely value?
What the heck, take it one more step: roll a die; call the result N . Roll N dice once and sum them; call
the result M . Roll M dice once and sum. What’s the distribution of the sum, expected value, most
likely value?

Since each of the possible values {1, 2, 3, 4, 5, 6} of N are equally likely, we can calculate the
distribution by summing the individual distributions of the sum of 1, 2, 3, 4, 5, and 6 dice,
each weighted by 16 . We can do this using polynomial generating functions. Let
1
p = (x + x2 + x3 + x4 + x5 + x6 ).
6
Then the distribution of the sum is given by the coefficients of the polynomial
6
X 1
D= pi
6
i=1

1 1 7 7 7 7 31 77 30
= x36 + x35 + x34 + x33 + x32 + x + x +
279936 46656 93312 34992 15552 7776 46656
131 29 139 28 469 27 889 26 301 25 4697 24 245 23
x + x + x + x + x + x + x +
46656 31104 69984 93312 23328 279936 11664
263 22 691 21 1043 20 287 19 11207 18 497 17 4151 16
x + x + x + x + x + x + x +
10368 23328 31104 7776 279936 11664 93312
3193 15 1433 14 119 13 749 12 2275 11 749 10 3269 9
x + x + x + x + x + x + x +
69984 31104 2592 15552 46656 15552 69984
4169 8 493 7 16807 6 2401 5 343 4 49 3 7 2 1
x + x + x + x + x + x + x + x.
93312 11664 279936 46656 7776 1296 216 36
To get the expected value E, we must calculate
36
X
E= idi
i=1

72
A Collection of Dice Problems Matthew M. Conroy

36  2
X 49 7
where D = di xi . This works out to E = = = 12.25.
4 2
i=1
More simply, one can calculate the expected value of the sum as follows, using the fact that
the expected value of a single roll is 3.5:

1
E= (3.5 + 2 × 3.5 + 3 × 3.5 + · · · + 6 × 3.5) = 12.25.
6

11 12
1255 1 X X 8279 1
Since < , and di =
di = > , we can say that the median value is
2592 2 15552 2
i=1 i=1
between 11 and 12.
·10−2

5
coefficient of xi

0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36
i
You can see from the plot of the coefficients of D that 6 is the most likely value. It is perhaps
a bit surprising that there are three “local maxima" in the plot, at i = 6, 11, and 14.
Okay, now lets do one more step.
After rolling the dice, getting a sum of N , and then rolling N dice, the sum distribution is
6
X 1
D1 = pi
6
i=1

as above. The coefficient of xi in D1 then gives us the probability that the sum of i. Hence if
we call the sum M and then roll M dice once, the sum distribution is given by
36
X
D2 = D1 (i)pi
i=1

where D1 (i) is the coefficient on xi in D1 .

Now, D2 is a degree 216 polynomial with massive rational coefficients, so there is little point
in printing it here. Let D2 (i) be the coefficient on xi in D2 .

73
A Collection of Dice Problems Matthew M. Conroy

We can find the expected value of the sum as

216  3
X 343 7
iD2 (i) = = = 42.875.
8 2
i=1

40 41
X 1 X 1
Since D2 (i) < , and D2 (i) > , we can say that the median sum is between 40 and
2 2
i=1 i=1
41.
Here’s a plot of the distribution:
0
log10 of coefficient of xi in D2

−10

−20

−30

0 20 40 60 80 100 120 140 160 180 200

i
Here’s a plot showing just the coefficients of xi for small values of i. There are local maxima
at i = 6, i = 20 (the absolute max), and i = 38, and a local minimum at i = 7 and i = 30.
−1.8
log10 of coefficient of xi in D2

−1.9

−2

−2.1

−2.2

−2.3

0 5 10 15 20 25 30 35 40
i

44. A die is rolled once. Call the result N . Then, the die is rolled N times, and those rolls which are equal to
or greater than N are summed (other rolls are not summed). What is the distribution of the resulting
sum? What is the expected value of the sum?

74
A Collection of Dice Problems Matthew M. Conroy

This is a perfect problem for the application of the polynomial representation of the distri-
bution of sums.
The probability of a sum of k is the coefficient on xk in the polynomial

2
   
1 1 2 3 4 5 6

1 1 2 3 4 5 6
x+x +x +x +x +x + 1+x +x +x +x +x +
6 6 6 6

3 1 1
4
   
1 1
2 + x3 + x4 + x5 + x6 + 3 + x4 + x5 + x6 +
6 6 6 6

5 1 1
6
   
1 1 5 6 6
4+x +x + 5+x
6 6 6 6
1 1 30 5 5 5 5 1
= x36 + x + x29 + x28 + x27 + x26 + x25 +
279936 7776 46656 23328 23328 46656 46656
59 24 13 23 5 22 11 21 67 20 1 19
x + x + x + x + x + x +
31104 5832 1296 2916 23328 486
1117 18 23 17 7 16 16 15 1 1
x + x + x + x + x14 + x13 +
69984 1296 288 729 54 72
6781 12 47 11 377 10 67 9 19 8 1
x + x + x + x + x + x7 +
93312 729 5832 1296 432 36
8077 6 565 5 7 4 5 3 1 1 27709
x + x + x + x + x2 + x +
46656 5832 108 108 27 36 279936
So, that’s the distribution. Here’s a plot of the distribution:

0.15
coefficient of xi

0.1

5 · 10−2

0 5 10 15 20 25 30 35 40
i
The expected value is simply the sum of i times the coefficient on xi in the distribution poly-
nomial. The result is 133
18 = 7.38888....
104077
The probability that the sum is 5 or less is = 0.3717... while the probability that the
279936
152539
sum is 6 or less is = 0.5449..., so we would say the median sum is somewhere between
279936
5 and 6.

75
A Collection of Dice Problems Matthew M. Conroy

45. Suppose n six-sided dice are rolled and summed. For each six that appears, we sum the six, and reroll
that die and sum, and continue to reroll and sum until we roll something other than a six with that
die. What is the expected value of the sum? What is the distribution of the sum?
Each die is independent, so we can work out the distribution for a single die, and get every-
thing we need from that.
To start, we can note that the expected value E when rolling a single die satisfies
1 1 1 1 1 1
E = 1 + 2 + 3 + 4 + 5 + (6 + E)
6 6 6 6 6 6
and so E = 4.2, so with n dice, the expected sum is 4.2n.
The first thing we might notice is that the probability of getting a score of 6m + k, for any
non-negative m, and k ∈ {1, 2, 3, 4, 5} is
 m+1
1
P (6m + k) =
6

Note that it is not possible to score a multiple of 6.

We can create some generating functions (that is, power series where the coefficient on xm is
the probability of getting a final sum of m). For scores congruent to 1 mod 6, we have
1 1 1 x
x + 2 x7 + 3 x13 + · · · =
6 6 6 6 − x6
The generating function for congruence class k mod 6 is xk times this, so the overall generat-
ing function for a single die is

x + x2 + x3 + x4 + x5 x6 − x
=
6 − x6 (x − 1)(6 − x6 )
So, when rolling r dice, the generating function for the sum is
r
x6 − x

.
(x − 1)(6 − x6 )

Thus, the probability that the sum is k is the coefficient on xk in the power series representa-
tion of the above generating function.
Here’s an example of how to calculate with this. Suppose we roll 5 six-sided dice, and want
to know the probability that the sum will be greater than or equal to 20. We calculate the
probability that the sum will be less than 20 by truncating the generating function to the 19th
degree for a single die and raising it to the fifth power. Let
1 1 1 1 1 1 1 1 1
Q = x + x2 + x3 + x4 + x5 + x7 + x8 + x9 + x10
6 6 6 6 6 36 36 36 36
1 11 1 13 1 14 1 15 1 16 1 17 1 19
+ x + x + x + x + x + x + x
36 216 216 216 216 216 1296
Then, raising Q to the fifth power, we have
1 5 5 6 5 7 35 8 35 9 121 10 1115 11 1555 12
x + x + x + x + x + x + x + x
7776 7776 2592 7776 3888 7776 46656 46656

76
A Collection of Dice Problems Matthew M. Conroy

665 13 2365 14 659 15 2795 16 5695 17 5635 18 5495 19

+ x + x + x + x + x + x + x + ···
15552 46656 11664 46656 93312 93312 93312
Summing the coefficients of Q5 up to x19 gives us

44711
,
93312
the probability that we score less than 20 when rolling 5 dice. And so, the probability that
we score 20 or more is
44711 48601
1− = .
93312 93312
46. A die is rolled until all sums from 1 to x are attainable from some subset of rolled faces. For example,
if x = 3, then we might roll until a 1 and 2 are rolled, or until three 1s appear, or until two 1s and a
3. What is the expected number of rolls?
I don’t have a solution for a general x, but here are some thoughts.
If x = 1, then the expected number of rolls is 6.
Let x = 2. The expected number of rolls until a 1 or 2 is rolled is 3, and these two outcomes
are equally likely. If we rolled a 1, then we need to roll a 1 or a 2, which takes 3 rolls on
average. If we rolled a 2, then we must roll a 1, which takes 6 rolls on aveage. Hence, the
expected number of rolls is

1 1 15
E2 = 3 + (3) + (6) = = 7.5.
2 2 2

We can do the same thing with x = 3:

1 1 1
E3 = 2+ ( expected number of rolls after a 1 )+ ( e.n. of rolls after a 2 )+ ( e.n. of rolls after a 3 ).
3 3 3
After rolling a 1, we roll until a 1, 2 or 3 appears. If a 1 appears, then we need to roll a 1, 2
or 3. If a 2 appears, we are done. If a 3 appears, then we need to roll a 1 or a 2. Hence the
expected number of rolls after rolling a 1 is

1 1
2 + (2) + (3).
3 3
After rolling a 2, we roll until a 1 appesrs, which requires 6 rolls on average. After rolling a
3, we still need to achieve subsums 1 and 2, which takes E2 rolls on average.
Thus,  
1 1 1 1 1 139
E3 = 2 + 2 + (2) + (3) + 6 + E2 = .
3 3 3 3 3 18

We could continue in this way, but instead we can treat the problem via a Markov process.
Create the set of 2x vectors V = {ha1 , a2 , . . . , ax i : ai ∈ {0, 1}, i = 1, 2, . . . , x}. Each vector
corresponds to a state in a Markov chain: if in state ha1 , a2 , . . . , ax i, ai = 1 if and only if a sum
of i hss been achieved with the faces rolled so far. The goal is to reach the h1, 1, . . . , 1i state,
which we treat as the absorbing state. The process starts in state h0, 0, . . . , 0i.

77
A Collection of Dice Problems Matthew M. Conroy

For example, with x = 2, we have the states and transition matrix

h0, 0i h1, 0i h0, 1i h1, 1i

 
h0, 0i 2/3 1/6 1/6 0
h1, 0i  0
 2/3 0 1/3  
h0, 1i  0 0 5/6 1/6 
h1, 1i 0 0 0 1

For example, the probability of moving from state h1, 0i to state h1, 1i is 1/3 since, once a 1
has been rolled, we need to roll either a 1 or a 2, hence the probability is 2/6 = 1/3.
The following PARI/GP code implements this method and outputs the expected number of
rolls until all sums 1, 2, . . . , x have been attained. One useful idea is that of converting the
state vectors described above into integers by treating the vectors as strings of binary digits.
This code applies the method of Appendix D to find the expected value from the transition
matrix.

x=2; \\ we will roll until all sums 1,2,3,...,x can be achieved from rolled faces
M=matrix(2^x,2^x); \\
A=vector(x); \\
vectonum(V,x) = sum(i=1,x,2^(i-1)*V[i]); \\ gives the state number corresponding to vector V
numtovec(n,x) = B=vector(x);m=n;j=0;while(m>0,B[j+1]=m%2;j=j+1;m=floor(m/2));return(B) \\
{
for(kk=0,2^x-1,

for(d=1,6, \\ figure out what state we get to based on each possible face rolled
BB=numtovec(kk,x); \\ generate the vector for this state
forstep(r=x,1,-1, \\
if( (BB[r]>0) && (r+d<=x), BB[r+d]=1)
); \\
if(d<=x,BB[d]=1);
jj=vectonum(BB,x);\\
M[kk+1,jj+1] = M[kk+1,jj+1]+1/6;\\ adding one to make indices legal
) \\
);
Q=matrix(2^x-1,2^x-1);
for(a=1,2^x-1,for(b=1,2^x-1,Q[a,b]=M[a,b]));
N=(matid(2^x-1)-Q)^(-1);
print(sum(i=1,2^x-1,N[1,i]));
}

Using this code, I found the following expected values:

x expected value(exact) ev (approx.) first difference
2 15/2 7.5
3 138/18 7.72222 0.222222
4 9139/1152 7.93316 0.210937
5 28669967/3600000 7.96387 0.030072
6 777101609/97200000 7.99487 0.030992
7 2341848577/291600000 8.03103 0.036158
8 883143607/109350000 8.07630 0.045271
9 42538515011/5248800000 8.10442 0.028125
10 256722093191/31492800000 8.15177 0.047344
11 1550818181021/188956800000 8.20726 0.055492
The first differences are interestingly erratic. I suspect a simple expression for the expected
values here is unlikely.

78
A Collection of Dice Problems Matthew M. Conroy

Here’s another table. This shows the percentage of the time that all sums 1 through x will
have been achieved by a certain number of rolls.
x 1 2 3 4 5 6 7 8 9 10 11 12 13 14
2 0 8.33 19.9 32.0 43.4 53.3 61.8 68.9 74.8 79.5 83.4 86.5 89.0 91.0
3 0 5.56 15.7 27.9 39.9 50.7 60.0 67.7 74.0 79.0 83.1 86.3 88.9 91.0
4 0 0 9.72 23.5 37.3 49.4 59.3 67.4 73.8 79.0 83.0 86.3 88.9 90.9
5 0 0 8.33 22.5 36.9 49.2 59.3 67.4 73.8 79.0 83.0 86.3 88.9 90.9
6 0 0 5.56 22.2 36.8 49.2 59.3 67.4 73.8 79.0 83.0 86.3 88.9 90.9
7 0 0 2.78 21.5 36.8 49.2 59.3 67.4 73.8 79.0 83.0 86.3 88.9 90.9
8 0 0 0 19.9 36.6 49.2 59.3 67.4 73.8 79.0 83.0 86.3 88.9 90.9
9 0 0 0 17.6 36.1 49.1 59.3 67.4 73.8 79.0 83.0 86.3 88.9 90.9
10 0 0 0 13.9 35.2 49.0 59.3 67.4 73.8 79.0 83.0 86.3 88.9 90.9
This is fascinating. The percentages are nearly constant at many roll numbers, and the variety
is almost entirely where the number of rolls is small. Unfortunately, the method used above
is too computationally involved to be applied to large x.
It would be nice to get at least a heuristic for the growth of the expected value as a function
of x.
Comment: experimentally, if you roll a die 15 times, on average you can create sums from 1
to about 48, whereas if you roll 7 times, on average you can get sums from 1 to about 13.3,
and 20 rolls will get you to about 68. 30 rolls will get you to about 105, so it certainly appears
that this is approaching 3.5 times the number of rolls.

47. How long, on average, do we need to roll a die and sum the rolls until the sum is a perfect square
(1, 4, 9, 16, . . . )?
We can make a very precise estimate of this expected value.
We begin by calculating the expectation resulting from rolling the die up to 104 . That is, if
we let E be the value we want, and pi is the probability that the sum is a square for the first
time after i rolls, then
∞ 4
10 ∞
X X X
E= ipi = ipi + ipi = E1 + E2 , say .
i=1 i=1 i=104 +1

We can calculate E1 by running through all possible sequences of up to 10000 rolls of the die.
Here is some PARI/GP code that does that:
{
mm=62000;
A=vector(mm);
A[1]=1;
B=vector(mm);
p=0;
plast=0;
totProb=0;
lowerE=0;
for(roll=1,10000,
for(i=1,mm,
if(A[i]>0,for(d=1,6,
B[i+d]=B[i+d]+A[i]))
);
for(i=1,mm,
if(issquare(i-1) && B[i]>0,p=p+B[i];B[i]=0));A=B;
totProb=totProb+(p-plast)*1/6^roll;

79
A Collection of Dice Problems Matthew M. Conroy

lowerE=lowerE+roll*(p-plast)*1/6^roll;
plast=p;
print(roll," ",lowerE*1.," ",1-totProb*1.);
print();
B=vector(mm);)
}

The result, accurate to more than 50 digits, is

E1 = 7.079764237551105103895546667746425712389260689139678

At the same time, the calculation tells us that the probability that the sum has not reached a
square after 10000 rolls is less than 6.2 × 10−28 .
Hence, E2 ≤ (6.2−28 )E 0 where E 0 is the expected number of rolls needed to reach a square if
more than 10000 rolls are needed. Let’s get an upper bound on E 0 .
Let’s suppose we are rolling a die and the current sum is m2 +1 where m is large (say m > 10).
The next square the sum could hit is (m+1)2 . The probability of hitting this square is between
6 and 46656 , so the probability of missing this square is less than 6 , and the expected number
1 16807 5

of rolls needed to reach that square is certainly less than (m + 1)2 − (m2 + 1). If the sum
“misses" (m + 1)2 , then the next square the sum could hit is (m + 2)2 , requiring fewer than
(m + 2)2 − (m + 1)2 additional rolls.
Continuing in this way, we have the upper bound
∞
X
E 0 < 10000 + ((m + 1 + j − m2 )pq j
j=0
 
X∞ ∞
X ∞
X
= 10000 + p  j 2qj + (2m + 2)jq j + (2m + 1)q j 
j=0 j=0 j=0
 
q(1 + q) (2m + 2)q 2m + 1
= 10000 + p + +
(1 − q)3 (1 − q)2 1−q
16807 184877
= 10000 + m+
648 1296
< 10000 + 26m + 143

where p = 16807
46656 and q = 6 . After 10000 rolls, considering the worst case, we would have
5

m < 245 and so E 0 < 16513.

Thus, E2 < 10−22 , and so we can conclude that

E = 7.079764237551105103895

accurate to 21 digits to the right of the decimal.

48. How long, on average, do we need to roll a die and sum the rolls until the sum is prime? What if we
roll until the sum is composite?
We make a very precise estimate of this first expected value in the following way.
We start by calculating the expectation resulting from rolling the die up to 104 times.

80
A Collection of Dice Problems Matthew M. Conroy

That is, if E is the value we want, and pi is the probability that the sum is prime for the first
time after i rolls, then
∞ 4
10 ∞
X X X
E= ipi = ipi + ipi = E1 + E2 , say .
i=1 i=1 i=104 +1

We can calculate E1 by running through all possible sequences of up to 10000 rolls of the die.
Here is some PARI/GP code that does that:
{
mm=62000;
A=vector(mm);
A[1]=1;
B=vector(mm);
p=0;
plast=0;
totProb=0;
lowerE=0;
for(roll=1,10000,
for(i=1,mm,
if(A[i]>0,for(d=1,6,
B[i+d]=B[i+d]+A[i]))
);
for(i=1,mm,
if(isprime(i-1) && B[i]>0,p=p+B[i];B[i]=0));A=B;
totProb=totProb+(p-plast)*1/6^roll;
lowerE=lowerE+roll*(p-plast)*1/6^roll;
plast=p;
print(roll," ",lowerE*1.," ",1-totProb*1.);
print();
B=vector(mm);)
}

By setting the numerical precision in GP to display well over 500 decimal places, we can
conclude that, to 500 decimal places,
E1 = 2.42849791369350423036608190624229927163420183134471
18266468959211216521323257379860460932705658054285
24160047589165194841516565634336164772565943485751
20100473140535884140802682651337652276857652736803
43136681232417851326056596686947409855553312451011
32379770133661680260866153068051346260033855486155
52748670772033743828142893635968820059123417686546
04093838923758726201931868732128985848910810088718
92009240571795609351924253153205397373837440242279
09185701767244213100211303319283551672174728414550

Also output by the code above is the probability that, after 10000 rolls, the sum has never
been prime. This value is approximately 2.05 · 10−552 . Hence,
E = E1 + (2.06 · 10−552 )E10000

81
A Collection of Dice Problems Matthew M. Conroy

where E10000 is the expected number of rolls needed if more than 10000 are needed. Though
I do not have a proof, it seems true that E10000 is certainly less than 1050 (a little experimen-
tation shows that, starting from a sum in the range 10000 to 60000, the expected number of
rolls needed is not more than 20. Hence, I suspect the true value of E10000 is likely less than
10020, so I think I am making a very safe claim here.)
Thus, we may conclude that, to 500 digits of accuracy, E = E1 as listed above.
If I find a way to prove such an upper bound, I’ll be sure to add it.
Now, what if we roll until the sum is composite? This is a much easier question, because we
cannot roll indefinitely: there are no prime numbers between the primes 89 and 97, and since
97 − 89 > 6, if our sum passes 89, it must fall on one of the composites between these two
primes. Since 89 is the 24th prime, we must land on a composite on or before the 26th roll.
With a slight modification to the code above, we may run it for 26 rolls and find that the
expected value of the number of rolls until the sum is composite is exactly

60513498236803196347
≈ 2.12848699151757507022715820.
28430288029929701376

If we let pn be the probability that the sum will be composite for the first time on the nth roll,
then we have the following table.
Pn
1 − ni=1 pi
P
n pn i=1 pi

1 0.3333333333333333333 0.33333333333333333333 0.666666666666666666

2 0.3611111111111111111 0.69444444444444444444 0.305555555555555555
3 0.1990740740740740740 0.89351851851851851852 0.106481481481481481
4 0.0709876543209876543 0.96450617283950617284 0.035493827160493827
5 0.0245627572016460905 0.98906893004115226337 0.010931069958847736
6 0.0082304526748971193 0.99729938271604938272 0.002700617283950617
7 0.0021612082761774119 0.99946059099222679470 0.000539409007773205
8 0.0004441498507849 0.99990474013107757964 0.000095259868922420
9 0.0000773986434994665 0.99998213877457704618 0.000017861225422953
10 0.0000138093733594133 0.99999594814793645955 0.000004051852063540
11 0.0000031009071914850 0.99999904905512794459 0.000000950944872055
12 0.0000007538649927743 0.99999980292012071895 0.000000197079879281
13 0.0000001611706083475 0.99999996409072906651 0.000000035909270933
14 0.0000000297712612252 0.99999999386199029175 0.000000006138009708
15 0.0000000050341888355 0.99999999889617912731 0.000000001103820872
16 0.0000000008801500407 0.99999999977632916806 2.236708319418220031 E-10
17 1.7735336436591380173 E-10 0.99999999995368253242 4.631746757590820138 E-11
18 3.7485246399124685943 E-11 0.99999999999116777882 8.832221176783515438 E-12
19 7.3437736466195153487 E-12 0.99999999999851155247 1.488447530164000092 E-12
20 1.2781174767468527085 E-12 0.99999999999978966995 2.103300534171473825 E-13
21 1.8730953391657100290 E-13 0.99999999999997697948 2.302051950057638328 E-14
22 2.1219904608947140874 E-14 0.99999999999999819939 1.800614891629241323 E-15
23 1.7081782621714818617 E-15 0.99999999999999990756 9.243662945775692717 E-17
24 8.9693076528648355726 E-17 0.99999999999999999726 2.743552929109835594 E-18
25 2.7083791736101660356 E-18 0.99999999999999999996 3.517375551 E-20
26 3.5173755501430727735 E-20 1 0
We can see that, more than 99 percent of the time, 6 or fewer rolls are needed.

3.3 Non-Standard Dice

49. Show that the probability of rolling doubles with a non-fair (“fixed") die is greater than with a fair die.

82
A Collection of Dice Problems Matthew M. Conroy

1 1
For a fair, n-sided die, the probability of rolling doubles with it is n × 2 = . Suppose we
n n
have a “fixed" n-sided die, with probabilities p1 , ..., pn of rolling sides 1 through n respectively.
The probability of rolling doubles with this die is

p21 + · · · + p2n .
1
We want to show that this is greater than . A nice trick is to let
n
1
i = pi − for i = 1, ..., n.
n
Then
1 2 1 2 1
p21 + · · · + p2n = (1 + ) + · · · + (n + )2 = 21 + · · · + 2n + (1 + · · · + n ) + .
n n n n
Now, since p1 + · · · + pn = 1, we can conclude that 1 + · · · + n = 0. Hence,
1 1
p21 + · · · + p2n = 21 + · · · + 2n + >
n n
precisely when not all the i ’s are zero, i.e. when the die is “fixed".

50. Is it possible to have a non-fair six-sided die such that the probability of rolling 2, 3, 4, 5, and 6 is the
same whether we roll it once or twice (and sum)? What about for other numbers of sides?
Let’s start with a 2-sided die.
Suppose the probability of rolling a one is a1 and the probability of rolling a 2 is a2 . Then the
probability of rolling a 2 when rolling twice and summing is a21 .
So, to achieve equal probabilities whether rolling once or twice, we require non-negative a1
and a2 with
a1 + a2 = 1 and a21 = a2
so that a21 + a1 − 1 = 0, and hence
√ √
−1 + 5 1 3− 5 1
a1 = = ≈ 0.6180339887498, and a2 = = 2 ≈ 0.381966011250.
2 φ 2 φ
where φ is the golden ratio.
Let’s look at the six-sided case. Here, we seek a1 , . . . , a6 non-negative with a1 + · · · + a6 = 1
and

a21 = a2
2a1 a2 = a3
2a1 a3 + a22 = a4
2a1 a4 + 2a2 a3 = a5
2a1 a5 + 2a2 a4 + a23 = a6 .

This implies

a21 = a2

83
A Collection of Dice Problems Matthew M. Conroy

2a31 = a3
5a41 = a4
14a51 = a5
42a61 = a6

and so we seek a (real, bounded between zero and 1) solution to the polynomial

42a61 + 14a51 + 5a41 + 2a31 + a21 + a1 − 1.

This polynomial has one positive real root: a1 = 0.3833276422504671918282678397.... Thus,

weighting a die with probabilities

a1 = 0.3833276422504671918282678397 . . .
a2 = 0.1469400813133021601465169741 . . .
a3 = 0.1126523898438400996320617058 . . .
a4 = 0.1079569374817992533848329781 . . .
a5 = 0.1158720592665417507230810930 . . .
a6 = 0.1332508898440495442852394095 . . .

will give us a die such that the probability of rolling 2, 3, 4, 5 and 6 is the same whether we
roll once or roll twice and sum.
In general, for an n-sided die, we require a1 , . . . , an non-negative real numbers with
n
X
ai = 1
i=1

and
Ci−1 ai1 = ai , i = 1, . . . , n
2i


where Ci is the i-th Catalan number, Ci = i
. Thus we need to guarantee a positive real
i+1
root less the one for the polynomial
n
X
−1 + Ci−1 xi
i=1

Since this polynomial evaluates to −1 at x = 0, and is positive for x = 1, there must be at

least one real solution between 0 and 1, and so there exists one of these special dice for every
number of sides.
For an n-sided die, we have the following approximate a1 values:

84
A Collection of Dice Problems Matthew M. Conroy

n a1
2 0.6180339887498
3 0.5
4 0.4418115119484
5 0.4068294316935
6 0.3833276422504
7 0.3663733452433
8 0.3535209284167
9 0.3434158345289
10 0.3352452267388
20 0.2969330618649
50 0.2714018346938
100 0.2617716572724
200 0.2564370408369
500 0.2528692107822
1000 0.2515454964644
Some observations (proofs to be added later):

(a) It appears that a1 approaches 1

4 as n tends to infinity.
(b) For any given number of sides n, it appears that the values of ai decreases as i increases
until reaching a minimum with i = d n2 e, and increases thereafter.

51. Find a pair of 6-sided dice, labelled with positive integers differently from the standard dice, so that the
sum probabilities are the same as for a pair of standard dice.
Number one die with sides 1,2,2,3,3,4 and one with 1,3,4,5,6,8. Rolling these two dice gives
the same sum probabilities as two normal six-sided dice.
A natural question is: how can we find such dice? One way is to consider the polynomial

(x + x2 + x3 + x4 + x5 + x6 )2 .

This factors as
x2 (1 + x)2 (1 + x + x2 )2 (1 − x + x2 )2 .
We can group this factorization as

x(1 + x)(1 + x + x2 ) x(1 + x)(1 + x + x2 )(1 − x + x2 )2

= (x + 2x2 + 2x3 + x4 )(x + x3 + x4 + x5 + x6 + x8 ).

This yields the “weird" dice (1,2,2,3,3,4) and (1,3,4,5,6,8). These dice are known as Sicherman
dice, named for George Sicherman who communicated with Martin Gardner about them in
the 1970s.
See Appendix C for more about this method.

See [1] for more on renumbering dice.

85
A Collection of Dice Problems Matthew M. Conroy

52. Is it possible to have two non-fair n-sided dice, with sides numbered 1 through n, with the property
that their sum probabilities are the same as for two fair n-sided dice?
Another way of asking the question is: suppose you are given two n-sided dice that exhibit
the property that when rolled, the resulting sum, as a random variable, has the same prob-
ability distribution as for two fair n-sided dice; can you then conclude that the two given
dice are fair? This question was asked by Lewis Robertson, Rae Michael Shortt and Stephen
Landry in [2]. Their answer is surprising: you can sometimes, depending on the value of n.
Specifically, if n is 1,2,3,4,5,6,7,8,9,11 or 13, then two n-sided dice whose sum “acts fair" are,
in fact, fair. If n is any other value, then there exist pairs of n-sided dice which are not fair,
yet have “fair" sums.
The smallest example, with n = 10, gives dice with the approximate probabilities (see [Rob
2] for the exact values)

(0.07236, 0.14472, 0.1, 0.055279, 0.127639, 0.127639, 0.055279, 0.1, 0.14472, 0.07236)

and
(0.13847, 0, 0.2241, 0, 0.13847, 0.13847, 0, 0.2241, 0, 0.13847).
It’s clear that these dice are not fair, yet the sum probabilities for them are the same as for
two fair 10-sided dice.

53. Is it possible to have two non-fair 6-sided dice, with sides numbered 1 through 6, with a uniform sum
probability? What about n-sided dice?

No. Let p1 , p2 , p3 , p4 , p5 and p6 be the probabilities for one 6-sided die, and q1 , q2 , q3 , q4 , q5 and
q6 be the probabilities for another. Suppose that these dice together yield sums with uniform
probabilities. That is, suppose P (sum = k) = 11 1
for k = 2, ..., 12. Then

1 1
p 1 q1 = and p6 q6 = .
11 11
Also,
1
= P (sum = 7) ≥ p1 q6 + p6 q1
11
so
1 1 1
p1 + p6 ≤
11p6 11p1 11
i.e.,
p1 p6
+ ≤ 1.
p6 p1
p1
Now, if we let x = p6 , then we have
1
x+ ≤1
x
which is impossible, since for positive real x, x + 1
x ≥ 2. Thus, no such dice are possible.
An identical proof shows that this is an impossibility regardless of the number of sides of the
dice.

54. Suppose that we renumber three fair 6-sided dice (A, B, C) as follows: A = {2, 2, 4, 4, 9, 9}, B =
{1, 1, 6, 6, 8, 8}, and C = {3, 3, 5, 5, 7, 7}.

86
A Collection of Dice Problems Matthew M. Conroy

(a) Find the probability that die A beats die B; die B beats die C; die C beats die A.

(b) Discuss.

The probability that A beats B can be expressed as

       
2 2 2 2 2 5
+ + (1) = .
6 6 6 6 6 9

The thinking behind this goes like this: the probability of rolling a 2 with A is 2/6, and if a 2
is rolled, it will beat B with probability 2/6. The probability of rolling a 4 with A is 2/6, and
it will beat B with probability 2/6. The probability of rolling a 9 with A is 2/6, if it will beat
B with probability 1.
Similarly, the probability that B beats C is
    
2 4 2 5
+ (1) =
6 6 6 9

and the probability that C beats A is

        
2 2 2 4 2 4 5
+ + = .
6 6 6 6 6 6 9

Thus, each die beats another with probability greater than 50%. This is certainly a counter-
intuitive notion; this shows that “beats", as in “die 1 beats die 2" is not transitive.
Lots of questions arise. What other sets of “non-transitive" dice are possible? What is the
fewest number of sides necessary? For a given number of sides, what is the minimum pos-
sible maximum face value (e.g., in the set given above, the maximum face value is 9)? For a
given number of sides, and a bound on the face values, how many sets of transitive dice are
there? What about sets with more than three dice?

55. Find every six-sided die with sides numbered from the set {1,2,3,4,5,6} such that rolling the die twice
and summing the values yields all values between 2 and 12 (inclusive). For instance, the die numbered
1,2,4,5,6,6 is one such die. Consider the sum probabilities of these dice. Do any of them give sum prob-
abilities that are “more uniform" than the sum probabilities for a standard die? What if we renumber
two dice differently - can we get a uniform (or more uniform than standard) sum probability?

The numbers 1, 2, 5 and 6 must always be among the numbers on the die, else sums of 2, 3,
11 and 12 would not be possible. In order to get a sum of 5, either 3 or 4 must be on the die
also. The last place on the die can be any value in {1,2,3,4,5,6}. Hence there are 11 dice with
the required property. Listed with their corresponding error, they are:
1,2,4,5,6,6 0.0232884399551066
1,2,4,5,5,6 0.0325476992143659
1,2,4,4,5,6 0.0294612794612795
1,2,3,5,6,6 0.0232884399551066
1,2,3,5,5,6 0.026374859708193
1,2,3,4,5,6 0.0217452300785634
1,2,3,3,5,6 0.0294612794612795
1,2,2,4,5,6 0.026374859708193
1,2,2,3,5,6 0.0325476992143659
1,1,2,4,5,6 0.0232884399551066
1,1,2,3,5,6 0.0232884399551066

87
A Collection of Dice Problems Matthew M. Conroy

The error here is the sum of the square of the difference between 1/11 and the actual proba-
bility of rolling each of the sums 2 through 12 (the probability we would have for each sum
if we had a uniform distribution). That is, if pi is the probability of rolling a sum of i with
this die, then the error is
12 
1 2
X 
pi − .
11
i=2
Note that the standard die gives the smallest error (i.e., the closest to uniform sum).
If we renumber two dice differently, many more cases are possible. One pair of dice are
1,3,4,5,6,6 and 1,2,2,5,6,6. These two dice give all sum values between 2 and 12, with an error
(as above) of 0.018658810325477, more uniform than the standard dice. The best dice for
near-uniformity are 1,2,3,4,5,6 and 1,1,1,6,6,6 which yield all the sums from 2 to 12 with near
equal probability: the probability of rolling 7 is 1/6 and all other sums are 1/12. The error is
5/792, or about 0.00631.

56. If we roll a standard die twice and sum, the probability that the sum is prime is 15 5
36 = 12 . If we renumber
the faces of the die, with all faces being different, what is the largest probability of a prime sum that can
be achieved?
To get prime sums other than 2, we need to have both even and odd faces. If three faces are
even and three are odd, then there will be 18 odd sums out of the 36 possible combinations.
If two faces are odd and four are even, there will be 16 odd sums, and if one face is odd and
five are even, then there will be 10 odd sums. So, the maximum number of prime sums out
of 36 is 19 (if all odd sums are prime, and the sum 2 is achievable). This is achieved with
the die {1, 2, 3, 4, 9, 10} which yields the sum set {2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 18, 19, 20}
in which all odd numbers are prime. Thus, this die has a 19 36 = 0.527̄ probability of throwing
a prime sum when rolled twice, compared to 12 5
= 0.416̄ for a standard die.

57. Let’s make pairs of dice that only sum to prime values. If we minimize the sum of all the values on the
faces, what dice do we get for 2-sided dice, 3-sided dice, etc.?
We’ll assume that all faces of the dice are different, to keep this from being trivial.
We can use linear programming to find these dice. Suppose we want to make dice with
s sides. Let n be an upper bound on the face values. We can define the following linear
program to find the dice:
Xn n
X
minimize: i · ai + i · bi
i=1 i=1
subject to

ai + bj ≤ 1 for all i, j such that i + j is composite (i.e., not prime) (3.16)

X n
ai = s (3.17)
i=1
Xn
bi = s (3.18)
i=1

with ai , bj ∈ {0, 1} for all i, j ∈ {1, . . . , n}. There is the question of how to set n. We can
simply start small and increase it until we get some dice, and then keep increasing n until,
say, n is greater than the total face value sum of dice already found.

88
A Collection of Dice Problems Matthew M. Conroy

On the other hand, we could also ask for the dice with the minimum maximal face.
Here are the resulting dice:
sides minimal total face sum (sum) minimal maximal face
2 {2, 4}, {1, 3}(10) same
3 {2, 4, 10}, {1, 3, 9}(29) same
4 {2, 6, 12, 18}, {1, 5, 11, 35}(90) {6, 10, 16, 20}, {1, 7, 13, 31}
5 {2, 8, 14, 28, 44},{3, 9, 15, 39, 45}(207) same
6 {2, 8, 14, 38, 44, 98},{3, 9, 15, 29, 59, 65}(384) {4, 12, 16, 46, 72, 82}, {1, 7, 25, 55, 67, 85}
7 {6, 12, 16, 22, 72, 82, 106},{1, 7, 25, 31, 67, 91, 151}(689) same

With more sides, it takes progressively longer to solve these LPs.

By the Green-Tao theorem, proved in 2004, there exist arbitrarily long arithmetic progressions
of primes. That is, for any positive integer k, there exist positive integers a and b such that

a, a + b, a + 2b, . . . , a + kb
are all prime.
If we want to create a dice pair with m sides that sums to only primes, we can use the dice

{a, a + b, a + 2b, · · · , a + (m − 1)b}, {0, b, 2b, . . . , (m − 1)b}

where the arithmetic progression a, a + b, a + 2b, . . . , a + 2(m − 1)b contains only primes.
For example, the arithmetic progression 110437 + 13860n is prime for n = 0, . . . , 10, and so
the six-sided dice

{110437, 124297, 138157, 152017, 165877, 179737}, {0, 13860, 27720, 41580, 55440, 69300}

has only prime sums.

Thus this method gives us a way to prove that we can find pairs of dice with arbitrarily many
faces whose sums are all prime.
We could also try a greedy method of creating the dice. Start with 1 on die A, and 2 on
die B. Then add the next smallest integer to each die in turn that maintains the prime sum
requirement.
This results in the two sets

A = {1, 3, 9, 27, 57, 267, 1227, 1479, 3459, . . . }

and
B = {2, 4, 10, 70, 100, 1060, 27790, 146380, 2508040, . . . }
and, in particular, the six-sided dice with sides {1, 3, 9, 27, 57, 267} and {2, 4, 10, 70, 100, 1060}.
So you can see that this is pretty far from getting the minimal faces, but it is easy to code.
We can extend the question to sets of three dice.
For two-sided dice, assuming all faces are odd, the sets {{1, 3}, {3, 9}, {1, 7}} and {{3, 5}, {1, 7}, {1, 7}}
yield only prime sums, the latter one being the set with the minimal maximum face. If we
want to require that the dice faces are all distinct, the set {{9, 11}, {5, 17}, {3, 15}} is the one
with minimal maximum face. If we choose to have two dice with all even faces, and one with
all odd faces, then we get the dice {{2, 4}, {2, 8}, {1, 7}} with minimal maximum face. If we

89
A Collection of Dice Problems Matthew M. Conroy

further require all distinct faces, then {{2, 6}, {4, 10}, {1, 7} is the set with minimal maximum
face.
For three-sided dice, the set {{1, 7, 37}, {1, 7, 37}, {9, 15, 29}} yields only prime sums, and is
the set with minimal maximum face. If we require that the dice faces are all distinct, then the
set
{{1, 31, 37}, {3, 9, 39}, {13, 27, 33}}
works and has minimal maximum face.

58. What if we want to make a die that when rolled twice and summed only yields primes? If we want all
the faces to be different, we cannot do that. But, what if we roll twice, sum and add one?
We cannot just sum, since we’d get even sums when we roll the same face twice, so unless all
faces were 1, this fails.
We can take the same approach as in the previous answer and use linear programming to
find such dice.
Let s be the number of sides of our die.
An LP like this does the job:
n
X
minimize: i · ai
i=1

subject to

ai + aj ≤ 1 for all i, j such that i + j + 1 is composite (i.e., not prime) (3.19)

X n
ai = s (3.20)
i=1
(3.21)

with ai ∈ {0, 1} for all i ∈ {1, . . . , n}.

Here, we only look for dice with a maximum face of n. If is not clear what we should set n
to, but we can start small and increase it until we get a solution.
The objective function’s goal is to minimize the total sum of the faces of the die, i.e., we try
to keep the faces as small as possible (in this sense).
This LP yields the following solutions:
sides die
2 {1, 3}
3 {1, 3, 9}
4 {1, 5, 11, 35}
5 {2, 14, 26, 44, 56}
6 {1, 5, 41, 65, 125, 191}
Instead of using an LP, we could just start with 1, and add the smallest face such that all sums
plus one are prime. This yields the face sequence {1, 3, 9, 69, 429, 4089, 86529, 513099, . . . }. If
we start instead with {1, 5}, we get the face sequence {1, 5, 11, 35, 95, 221, 126221, . . . }. Start-
ing with {3, 9} we get the face sequence {3, 9, 33, 63, 273, 303, 3309, 63063, 172989, . . . }. We
could do this all day!

90
A Collection of Dice Problems Matthew M. Conroy

59. Show that you cannot have a pair of dice with more than two sides that only gives sums that are
Fibonacci numbers.
Here we consider each die to have distinct integer faces (i.e., no face is repeated), but we do
not need to assume that there is no face common to both dice.
Let’s start with the two-sided case, and we’ll see this leads easily to the greater-than-two sides
case.
Suppose we have two-sided dice with sides {r, s},{t, u} with sums that are all Fibonacci num-
bers. We can subtract r from the first die’s faces, and add r to the second to get the dice
{0, s − r}, {t + r, u + r} with the same sumset. Since the first die has a zero, and all sums are
Fibonacci, we can relabel the dice as {0, x}, {Fa , Fb }, where Fn is the n-th Fibonacci number
(e.g., F1 = 1, F2 = 1, F3 = 2, etc.) We may assume Fa < Fb .
Let’s write Fc = x + Fa and Fd = x + Fb .
Then Fb + Fc = Fa + Fd .
Suppose b < c. Then Fb + Fc ≤ Fc−1 + Fc = Fc+1 ≤ Fd < Fd + Fa , a contradiction.
Suppose b > c. Then Fb + Fc ≥ Fb + Fb−1 = Fb+1 ≤ Fd < Fd + Fa , a contradiction.
Hence, b = c, and so we have, simply, Fb = Fa + x and Fd = Fb + x.
Then x ≥ Fb−1 , since otherwise we’d have Fb + x < Fb + Fb−1 = Fb+1 ≤ Fd .
On the other hand, Fb = Fa + x implies x < Fb . Thus, x = Fb−1 . (Note we are using the fact
that Fa > 0 here).
Thus, if we have two-sided dice with sums that are Fibonacci, they must be “equivalent" to
the dice {0, Fb − 1}, {Fb−2 , Fb } for some integer b > 1. By “equivalent", I mean any dice
derived from these by adding an integer α to all faces of one die and subtracting α from all
the faces of the other.
So we can have dice like {0, 3}, {2, 5}, or {0, 8}, {5, 13}.
Now, if we have more than two sides, then all non-zero faces of the die with the zero on
it would have to be identical (in these cases, our x above standing for any non-zero face),
something we are not allowing here. Hence, dice with three or more sides whose sums are
all Fibonacci are impossible.

3.4 Games with Dice

60. Two players each roll two standard dice, first player A, then player B. If player A rolls a sum of 6, they
win. If player B rolls a sum of 7, they win. They take turns, back and forth, until someone wins. What
is the probability that player A wins?
The idea here might be that, even though rolling 7 is the most likely roll, player A gets to
go first, and perhaps this first-player advantage offsets player B’s more advantageous target.
Let’s see.
Let’s let p be the probability of rolling a sum of 6 with two dice (so p = 36 5
). Let r be the
probability of rolling a sum of 7 with two dice (so r = 6 ). Player A can win in a number of
1

ways: player A rolls 6 immediately; player A fails to roll a 6 and player B fails to roll a 7, then
player A rolls a 6; player A fails to roll a 6 two times and player B fails to roll a 7 two times,
then player A rolls a 6, etc.

91
A Collection of Dice Problems Matthew M. Conroy

Each of these are independent events, and each one has a probability equal to

(1 − p)k (1 − r)k p

where k = 0, 1, 2, 3, . . . . Hence we can add up the probabilities: the probability that player
A wins is
∞
X p p
(1 − p)k (1 − r)k p = = .
1 − (1 − p)(1 − r) p + r − pr
k=0
30
For p = 5
36 and r = 16 , this equals = 0.4918032... so the game just slightly favors player B.
61
61. In the previous problem, we find out that the game is not fair. Are there sum targets for player A and
player B that would make the game fair? What about using a different number of dice, or allowing
targets to include more than one sum?
Let p be the probability of player A rolling their target sum in one roll, and r be the probability
of player B rolling their target sum in one roll. In order for the game to be fair, we require
1 p
= .
2 p + r − pr
p
so r = .
1−p
Let’s say p = sk2 and r = sm2 where s is the number of sides of the dice. Note k and m are at
most s, and at most one of them may be equal to s, since r 6= p. Then
k m
= 2
s2 −k s
and so ks2 = ms2 − km. Hence, s2 divides km. But this is impossible, since km is not zero,
and km ≤ s(s − 1) < s2 .
Thus, there is no choice of target sums that would make this game fair.
So that doesn’t work.
p
But, we can note that if p = 369
, then 1−p 36 . Then we can note that the probability of
= 12
throwing a sum of 4 or 5 with two dice is 36 , while the probability of throwing a sum of 8, 9
9

or 10 with two dice is 12

36 . Thus, the game is fair if the first player’s target is a sum of 4 or 5,
and the second player’s target is a sum of 8, 9 or 10.
In the same way, the game is also fair if the first player’s target is a sum of 8, 9 or 10, while
the second player’s target is 5, 6 or 7.
If the players throw three dice, and player A’s target is a sum of 4 or 8 while player B’s target
is a sum of 11, then the game is fair. In this situation, we’d have p = 216
24
= 19 and r = 216
27
=
p
1
8 = 1−p .

62. Two players each roll two dice. Player A is trying to roll a sum of 6, player B is trying to roll a sum of
7. Player A starts, and rolls once. Then Player B rolls twice, then Player A rolls twice, and they repeat,
both players rolling twice in succession until someone rolls their target sum. What is the probability
of winning for each player?
This is a very old problem; one finds it as Problem I in perhaps the first book on probability,
the 1714 book Libellus De Ratiociniis In Ludo Aleae by Christian Huygens.

92
A Collection of Dice Problems Matthew M. Conroy

Let p be the probability of rolling a sum of 6 with two dice, so p = 36 5

. Let r be the probability
of rolling a sum of 7 with two dice, so r = 6 . Further, let p̄ = 1 − p and r̄ = (1 − r) = 30
1
36 .
Lastly, let pb = 1 − (1 − p)2 = 1296
335
, the probability of rolling a sum of 6 in either of two throws.
Player A can win in a number of ways:

• Throw a 6 immediately
• Fail to throw a 6, then have player B fail to throw a 7 in two throws, then throw a 6 in
one of the next two throws
• Fail to throw a 6 in three throws, have player B fail to throw a 7 in four throws, then
throw a 6 in two throws (not in this order of course)
• Fail to throw a 6 in five throws, have player B fail to throw a 7 in six throws, then throw
a 6 in two throws

etc.
The probability of the first possibility is simply p.
We can express the probability of each of the other possibilities as

p̄2j−1 r̄2 j pb

where j = 1, 2, 3, . . . . Summing, we find the probability of A winning is

∞  
X
2j−1 2j pb 1 10355
p+ p̄ r̄ pb = p + −1 = .
p̄ 1 − p̄2 r̄2 22631
j=1

12276
As a result, the probability of player B winning is and so the ratio of player A’s chance
22631
of winning to player B’s chance of winning is

10355 : 12276.

This is the way Christian Huygens reported the answer.

63. Two players each roll a die. Player 1 rolls a fair m-sided die, while player 2 rolls a fair n sided die, with
m > n. The winner is the one with the higher roll. What is the probability that Player 1 wins? What
is the probability that Player 2 wins? What is the probability of a tie? If the players continue rolling
in the case of a tie until they do not tie, which player has the higher probability of winning? If the tie
means a win for Player 1 (or player 2), what is their probability of winning?
When the two players roll their dice, there are mn possible outcomes. These can be thought
of as lattice points, i.e., points (x, y) in the xy-plane where x and y are positive integers, and
1 ≤ x ≤ m and 1 ≤ y ≤ n.
Of these mn lattice points, Player 1 is a winner whenever x > y. The number of lattice points
with x > y is equal to
1
(m − 1) + (m − 2) + (m − 3) + · + (m − n) = nm − n(n + 1).
2
Hence, the probability of Player 1 winning is
n+1
1− .
2m

93
A Collection of Dice Problems Matthew M. Conroy

Of the nm possibly outcomes, n are ties. So the probability of a tie is

n 1
= .
mn m

Hence, the probability of Player 2 winning is

n−1
.
2m

Now, suppose the players continue rolling until there is no tie, and then the winner is declared
based on the final roll. What are the winning probabilities then? Let p be the probability of
Player 1 rolling a larger roll on a single roll, and q be the probability of a tie. Then, for Player 1
to win, there must be a sequence of ties, followed by a single winning roll by Player 1. Hence,
the probability of Player 1 winning is
∞ ∞
X
i
X p
qp=p qi = .
1−q
i=0 i=0

Using the values for p and q calculated above, we find that the probability of Player 1 winning
if the players reroll until they are not tied is

1 − n+1
2m n−1
1 = 1 − 2(m − 1)
1− m

and so the probability of Player 2 winning is

n−1
.
2(m − 1)

If, instead of rerolling, ties mean a win for Player 1, then Player 1’s probability of winning
becomes
n+1 1 n−1
1− + =1− .
2m m 2m
while Player 2’s is
n−1
.
2m
If, instead of rerolling, ties mean win for Player 2, then Player 1’s probability of winning is

n+1
1− .
2m
while Player 2’s is
n−1 1 n+1
+ = .
2m m 2m
Since n+1
2m < 2 as long as n < m − 1, Player 2 is at a disadvantage even if ties go them, except
1

when n = m − 1, in which case the players are evenly matched (each with a 12 probability
of winning). If Player 1’s die has at least two more faces than Player 2’s die, Player 1 has the
advantage, regardless of how ties are treated.

94
A Collection of Dice Problems Matthew M. Conroy

64. Two players each start with 12 tokens. They roll three dice until the sum is either 14 or 11. If the sum
is 14, player A gives a token to player B; if the sum is 11, player B gives a token to player A. They
repeat this process until one player, the winner, has all the tokens. What is the probability that player
A wins?
This is a very old problem; one finds it as Problem V in an early book on probability, the 1714
book Libellus De Ratiociniis In Ludo Aleae by Christian Huygens.
Let’s generalize slightly and suppose that each player starts with a tokens and the probability
of player A gaining a token on one turn is p.
Let x be the number of A’s tokens minus a. So the game begins with x = 0, and player A
needs to reach x = a before reaching x = −a in order to win.
We can view the game as a biased, absorbing random walk: x begins at zero, and at each step,
x increases by one (with probability p) or decreases by 1 (with probability 1 − p) until x = a
or x = −a.
Let Rx be A’s probability of winning when the number of A’s tokens minus a is x.
Then we know
Ra = 1 and R−a = 0
and
Rn = pRn+1 + (1 − p)Rn − 1 (3.22)
for −a < n < a. Equation (3.22) is an example of a linear recurrence relation, and we can
solve for Rn using the method in Appendix E as follows.
Rewriting, equation (3.22) becomes

pRn+1 = Rn − (1 − p)Rn−1

and this has characteristic equation

px2 − x + 1 − p = 0.
1−p
Let’s assume p > 12 . Then the two roots of this equation are α1 = 1 and α2 = p .
Then, there exist constants c1 and c2 such that

Rn = c1 α1n + c2α2n .

with 0 = R−a and 1 = Ra .

αa −αa
Solving, we find c1 = 2a 2 2a and c2 = 2a 1 2a .
α2 − α1 α2 − α1
We are interested in R0 and we find
1
R0 = c1 + c2 = .
α1a + α2a

For our particular problem, a = 12 and p = 14 9

(since the probabilities of throwing a sum
of 11 and 14 with three dice are 8 and 72 , respectively), so α2 = 59 and so the probability of
1 5

player A winning is

1 912 282429536481
R0 =
= =
5 12 512 + 912 282673677106
1+ 9

95
A Collection of Dice Problems Matthew M. Conroy

which is approximately 0.999136316.... Thus, player B has a probability of winning of

244140625 1 1
= + + · · · ≈ 0.00086368362098 . . .
282673677106 1158 7951489

In keeping with the style that Huygens used, we can say that the ratio of the two players’
probabilities of winning is 244140625 to 282429536481.

65. Two players each start a game with a score of zero, and they alternate rolling dice once to add to their
scores. Player A rolls three six-sided dice on each turn, while player B always gets 11 points on their
turn. If the starting player is chosen by the toss of a coin, what is the probability that player A will be
the first to 100 points?
Since player B always gets 11 points and player A gets 10.5 points on average, we might expect
player B to have the advantage.
Since player B always gets 11 points, they will reach 100 points on exactly their tenth roll.
If player A goes first, player A needs to reach 100 points on or before their 10th roll in order
to win. Letting
1
x + x2 + x3 + x4 + x5 + x6


p=
6
we can express the probability that their score is 100 or greater as
10·3·6
X 1967530550176293236225
P1 = ((p3 )10 )i = ≈ 0.72088998
2729307650873251332096
i=100

where the subscript i indicates the coefficient of xi in the polynomial (see Appendix C for
more about this method).
If player B goes first, then player A needs to reach 100 points on or before their 9th roll in
order to win. Calculating as above, this probability is
9·3·6
X 510825255320984633
P2 = ((p3 )9 )i = ≈ 0.28748228.
1776893001870606336
i=100

We see that P1 + P 2 is very close to one, so it’s a close game. But,

1 1 2752158142349325632513
P1 + P2 = ≈ 0.50418613
2 2 5458615301746502664192
so player A has a very slim advantage.
What if the game is played to limits other than 100? Considering all possible game limits, it
seems player A has the advantage when the game is played to

12, 13, 14, 15, 23, 24, 25, 26, 34, 35, 36, 45, 46, 47, 56, 57, 58, 67, 68, 78, 79, 89 and 100

and for no larger limits. Player A has the largest advantage with a limit of 12, winning about
68.25% of the time, and the smallest advantage with a limit of 58, winning about 50.06% of
the time.

96
A Collection of Dice Problems Matthew M. Conroy

66. Craps What is the probability of winning a round of the game Craps?
The probability of winning a round of craps can be expressed as
X
P (rolling 7 or 11) + P (rolling b)P (rolling b again before rolling 7).
b∈{4,5,6,8,9,10}

We now evaluate each probability. The probability of rolling 7 is 6

36 = 16 , and the probability
of rolling 11 is 36
2 1
= 18 . Hence,
6 2 2
P (rolling 7 or 11) = + = .
36 36 9
The following table gives the probability of rolling b, for b ∈ {4, 5, 6, 8, 9, 10}. (This is the
probability of b becoming the “point".)

4 3/36 = 1/12
5 4/36 = 1/9
6 5/36
8 5/36
9 4/36 =1/9
10 3/36 =1/12

Finally, we need to determine the probability of rolling b before rolling 7. Let p be the prob-
ability of rolling b on any single roll. Rolling b before rolling 7 involves rolling some number
of rolls, perhaps zero, which are not b or 7, followed by a roll of b. The probability of rolling
k rolls which are not b or 7, followed by a roll of b is

1 k
   k
5
1−p− p= − p p.
6 6
Since k may be any non-negative integer value, we have
∞  k
X 5 p
P (rolling b before rolling 7) = −p p= 1 .
6 6 +p
k=0

See Appendix B for some formulas for simplifying series such as the one above. Another
way of looking at this is that the probability of rolling b before rolling a 7 is the conditional
probability of rolling b, given that either b or 7 was rolled.
We can calculate the following table:

b P (rolling b) P (rolling b again before rolling 7) P (rolling b)P (rolling b again before rolling 7)
4 1/12 1/3 1/36
5 1/9 2/5 2/45
6 5/36 5/11 25/396
8 5/36 5/11 25/396
9 1/9 2/5 2/45
10 1/12 1/3 1/36

Thus, the probability of winning a round of craps is

2 1 2 25 25 2 1 244
+ + + + + + = = 0.4929.
9 36 45 396 396 45 36 495
244 1 7
Since = − , the odds are just slightly against the player.
495 2 990

97
A Collection of Dice Problems Matthew M. Conroy

67. Non-Standard Craps We can generalize the games of craps to allow dice with other than six sides.
Suppose we use two (fair) n-sided dice. Then we can define a game analogous to craps in the following
way. The player rolls two n-sided dice. If the sum of these dice is n + 1 or 2n − 1, the player wins.
If the sum of these dice is 2, 3 or 2n the player loses. Otherwise the sum becomes the player’s point,
and they win if they roll that sum again before rolling n + 1. We may again ask: what is the player’s
probability of winning?

For two n-sided dice, the probability of rolling a sum of n + 1 is

n 1
P (n + 1) = 2
=
n n
and the probability of rolling a sum of 2n − 1 is

2
P (2n − 1) = .
n2
In general, the probability of a sum of k is

n − |k − n − 1|
P (k) = .
n2

Hence, the probability of winning a round of Craps with n-sided dice is

1 2 X P (k)2 1 2 X (n − |k − n − 1|)2
pn = + 2+ = + 2+
n n P (k) + P (n + 1) n n n2 (2n − |k − n − 1|)
4≤k≤2n−2 4≤k≤2n−2
k6=n+1 k6=n+1

We have the following table:

n pn
3 5/9 = 0.55555...
4 15/28 = 0.535714...
5 461/900 =0.512222...
6 244/495 = 0.492929...
7 100447/210210 = 0.477841...
8 37319/80080 = 0.4660214...
9 2288779/5012280 = 0.456634...
10 23758489/52907400 = 0.449057...
20 0.415459...
30 0.404973...
50 0.397067...
100 0.391497...
1000 0.386796...
10000 0.386344...
100000 0.386299...
1000000 0.38629486...
It certainly appears that pn approaches a limit as n approaches infinity.

68. Yahtzee There are many probability questions we may ask with regard to the game of Yahtzee. For
starters, what is the probability of rolling, in a single roll,
a) Yahtzee
b) Four of a kind (but not Yahtzee)

98
A Collection of Dice Problems Matthew M. Conroy

c) A full house
d) Three of a kind (but not Yahtzee, four of a kind or full house)
e) A long straight
f) A small straight
These questions aren’t too tricky, so I’ll just give the probabilities here:
6 1
(a) Yahtzee: 5
= ≈ 0.07716%
6 1296
5


·6·5 25
(b) Four of a kind (but not Yahtzee): 5
4
= ≈ 1.929%
6 1296
5


3 ·6·5 25
(c) A full house: 5
= ≈ 3.858%
6 648
(d) Three of a kind (but not Yahtzee, four of a kind or full house) :
5


3 ·6·5·4 25
5
= ≈ 15.432%
6 162
2 · 5! 5
(e) A long straight: 5
= ≈ 3.086%
6 162
(f) A small straight (but not a long straight):
5! 5!


2! ·4+2 2! · 4 + 5! 10
= ≈ 12.346%
65 81
69. More Yahtzee What is the probability of getting Yahtzee, assuming that we are trying just to get
Yahtzee, we make reasonable choices about which dice to re-roll, and we have three rolls? That is, if
we’re in the situation where all we have left to get in a game of Yahtzee is Yahtzee, so all other outcomes
are irrelevant.
This is quite a bit trickier than the previous questions on Yahtzee. The difficulty here lies in
the large number of ways that one can reach Yahtzee: roll it on the first roll; roll four of a kind
on the first roll and then roll the correct face on the remaining die, etc. One way to calculate
the probability is to treat the game as a Markov chain (see Appendix D for general information
on Markov chains).
We consider ourselves in one of five states after each of the three rolls. We will say that we
are in state b if we have b common dice among the five. For example, if a roll yields 12456,
we’ll be in state 1; if a roll yields 11125, we’ll be in state 3. Now, the goal in Yahtzee is to try
to get to state 5 in three rolls (or fewer). Each roll gives us a chance to change from our initial
state to a better, or equal, state. We can determine the probabilities of changing from state i
to state j. Denote this probability by Pi,j . Let the 0 state refer to the initial state before rolling.
Then we have the following probability matrix:
120 900 250 25 1
 
0 1296 1296 1296 1296 1296
 0 120 900 250 25 1 
 1296 1296 1296 1296 1296 
 0 120 80 15 1
0
 
P = (Pi,j ) =  216 216 216 216  (3.23)

 0 25 10 1
 0 0 36 36 36 

 0 5 1
0 0 0 6 6

0 0 0 0 0 1

99
A Collection of Dice Problems Matthew M. Conroy

The one representing P5,5 indicates that if we reach yahtzee, state 5, before the third roll, we
simply stay in that state. Now, the probability of being in state 5 after 3 rolls is given by
X
P0,i1 Pi1 ,i2 Pi2 ,5 = (M 3 )1,5

where the sum is over all triples (i1 , i2 , i3 ) with 0 ≤ ij ≤ 5. Calculating M 3 gives us the
probability
2783176 347897
10
= ≈ 0.04603.
6 7558272
347897 1
Since = , a player will get Yahtzee about once out of every twenty two
7558272 21.7256026...
attempts.

70. Drop Dead

(a) What is the expected value of a player’s score?

(b) What is the probability of getting a score of 0? 1? 10? 20? etc.

(a) The player begins with five dice, and throws them repeatedly, until no dice are left. The
key factor in calculating the expected score is the fact that the number of dice being thrown
changes. When throwing n dice, a certain number may “die" (i.e. come up 2 or 5), and leave
j non-dead dice. The probability of this occurring is
  n−j j
n 2 4
Pn,j = .
n−j 6n

The following table gives Pn,j for n and j between 0 and 5.

n\j 0 1 2 3 4 5
1 1/3 2/3 0 0 0 0
2 1/9 4/9 4/9 0 0 0
3 1/27 6/27 12/27 8/27 0 0
4 1/81 8/81 24/81 32/81 16/81 0
5 1/243 10/243 40/243 80/243 80/243 32/243

When throwing n dice, the expected sum is 3.5n, if none of the dice come up 2 or 5. Let E(n)
represent the expected score starting with n dice (so we’re ultimately concerned with E(5)).
Consider E(1). Rolling a single die, the expected score is

E(1) = 3.5P1,1 + E(1)P1,1 .

That is, in one roll, we pick up 3.5 points, on average, if we don’t “drop dead" (so we get
3.5P1,1 expected points), and then we’re in the same position as when we started (so we pick
up E(1)P1,1 expected points). We can solve this equation to get
  
2 7
E(1) = 3 · = 7.
3 2

Now, suppose we start with 2 dice. The expected score is

E(2) = (2 · 3.5 + E(2)) P2,2 + E(1)P2,1 .

100
A Collection of Dice Problems Matthew M. Conroy

That is, on a single roll, we pick up 2 · 3.5 points on average if none of the dice “die", in which
case we’re back where we started from (and then expect to pick up E(2) points), or exactly
one of the dice “die", and so we expect to pick up E(1) points with the remaining die. This
equation yields
1 56
E(2) = (7P2,2 + E(1)P2,1 ) = .
1 − P2,2 5
Continuing in this way, we have the general equation
n
X
E(n) = 3.5 · n · Pn,n + E(j)Pn,j
j=1

which we can rewrite as

 
n−1
1 3.5 · n · Pn,n +
X
E(n) = E(j)Pn,j 
1 − Pn,n
j=1

With this formula, we can calculate E(n) for whatever value of n we want. Here is a table of
E(n):

n E(n)
1 7
2 56
5 = 11.2
3 1302
95 ≈ 13.70526
4 3752
247 ≈ 15.19028
5 837242
52117 ≈ 16.06466
6 4319412
260585 ≈ 16.57583
10 9932935945754444
577645434482545 ≈ 17.19556
20 ≈ 17.26399
30 ≈ 17.26412371400800701809841213
100 ≈ 17.26412423601867057324993502
250 ≈ 17.26412422187783220247082379

18
                      
 
16 

14 

12

10

8

6
0 5 10 15 20 25 30

101
A Collection of Dice Problems Matthew M. Conroy

So we see that a game of Drop Dead, using 5 dice, will have, on average, a score of about
16.06.
Further questions: Notice that if we play the game with more than 5 dice, the expected score
does not increase very much. In fact, it appears as if there is an upper bound on the expected
score; that is, it seems that there is some B so that E(n) < B for all n. What is the smallest
possible value for B? Also, we expect E(n) to always increase as n increases. Can we prove
this is so?
(b) Calculating the exact probabilities of scores seems to be a bit of a pain. The easiest score
to work out is zero. To get zero, the player must roll at least one 2 or 5 on every roll. If we
define a Markov process, with states 0, F, 5, 4, 3, 2, 1 (in that order), where 0 means a score
of zero has been achieved, F means a score greater than 0 has been achieved, and 5 through
1 are the current number of dice being rolled, we have the following transition matrix:

1 0 0 0 0 0 0
 
 01 1 0 0
32 80
0
80
0
40
0 
10 

 243 243 0 243 243 243 243 
 1 16
0 0 32 8 8 
P0 =  81 81 81 27 81 
1 8 4 2 

 27 27 0 0 0 9 9 
 1 4
0 0 0 0 4 
9 9 9
1 2
3 3 0 0 0 0 0

Since the games takes at most five rolls, the fifth power of this matrix tells us what we want
to know:
1 0 0 0 0 0 0
 
0
 978853 1 0 0 0 0 0
3804116
4782969 0 0 0 0 0
 
 4782969
4163 15520
P05 =  19683

19683 0 0 0 0 0
55 188


 243 243 0 0 0 0 0
 7 20

27 27 0 0 0 0 0
1 2
3 3 0 0 0 0 0
978853 978853
Thus we see that the probability of achieving a score of zero is = , which is
4782969 314
about 0.2046538457598....
The probability of achieving a score of 1 is calculable in a similar way. Our transition matrix
is
1 0 0 0 0 0 0
 
 0 11 1 0 0
80
0
80
0
40
0 
10 
0 0
81 243 243 243 243 
17 32 8 8 

P1 =  0 81 0 0

81 27 81 
0 1 4 2 
3 0 0 0 9 9 
0 5 0 0 4 

9 0 0 9
1 17
18 18 0 0 0 0 0
A note on this lower-left most entry: once the player has only one die left, they have a 1/6
chance of rolling a one; but then, the die must die, which occurs with probability 1/3. Hence
the 1/18 probability of getting a score of 1 after the state of one die is attained.

102
A Collection of Dice Problems Matthew M. Conroy

Raising this matrix to the fifth power yields

1 0 0 0 0 0 0
 
0
 305285 1 0 0 0 0 0
4477684

 14348907 4782969 0 0 0 0 0
 1300 18383

P15 =  59049 19683 0 0 0 0 0
 17 226

 729 243 0 0 0 0 0
2 25


81 27 0 0 0 0 0
1 17
18 18 0 0 0 0 0

and thus the probability of a score of 1 in this game is 305285/14348907 = 0.0212758365497804118....

Scores higher than 1 are more difficult, since it will not be necessary to reach a single die.
On the other hand, to achieve a score of n, there can be at most n + 4 rolls, so the problem is
finite.

71. Threes In the game of Threes, the player starts by rolling five standard dice. In the game, the threes
count as zero, while the other faces count normally. The goal is to get as low a sum as possible. On
each roll, at least one die must be kept, and any dice that are kept are added to the player’s sum. The
game lasts at most five rolls, and the score can be anywhere from 0 to 30.
For example a game might go like this. On the first roll the player rolls

2−3−3−4−6

The player decides to keep the 3s, and so has a score of zero. The other three dice are rolled, and the
result is
1−5−5
Here the player keeps the 1, so their score is 1, and re-rolls the other two dice. The result is

1−2

Here, the player decides to keep both dice, and their final score is 4.
If a player plays optimally (i.e., using a strategy which minimizes the expected value of their score),
what is the expected value of their score?
This is certainly best analysed in reverse.
Suppose we are rolling one die. Then the expected value of the result is

1+2+0+4+5+6
= 3.
6

Suppose we roll two dice. The rules require that we keep at least one, so clearly we must keep
the lower of the two. The question is whether to keep the other one. If we don’t keep it, our
expected value from it will be 3 when we reroll. Hence, we should keep it if it is a 3, a 1, or a
2.
Following this method, the expected value with two dice is expressible as
6 6
1 XX 158 79
E2 = (min{i, j} + min{max{i, j}, 3}) = = = 4.388... .
36 36 18
i=1 j=1

103
A Collection of Dice Problems Matthew M. Conroy

Suppose we roll three dice. We must keep the lowest die, so we need to decide whether to
keep either of the other two dice. Obviously, if we keep only one of them, we would keep the
lower one. Call the three dice
d1 ≤ d2 ≤ d3 .
Then if we keep both d2 and d3 , our sum is d2 + d3 . If we re-roll only d3 , then our expected
sum is d2 + 3. If we re-roll both d2 and d3 , then our expected sum is E2 = 4.3888... . Thus
we want to choose the option so that our expected sum is

min{d2 + d3 , d2 + 3, E2 }.

Analyzing this, we find that if d2 ≥ 4, we should re-roll both. If d2 = 3, we should keep both
if d3 < 3. If d2 = 2, then we should keep d3 if d3 = 2; otherwise we should re-roll both. (This
is the surprising part of the optimal strategy: a two is not necessarily keepable by itself: it
depends on the value of the other die.) If d2 = 1 and d3 = 1 or 2, keep both; otherwise, keep
d2 and re-roll d3 .
The calculation of the expected value with three dice can be expressed as

6 0
1X 2261
E3 = 3 (d1 + min{d2 + d3 , d2 + 3, E2 }) = = 5.233796...
6 2 · 63
i,j,k
=0

where the sum skips 3, and d1 ≤ d2 ≤ d3 is {i, j, k} sorted in increasing order.

Continuing in this way, the expected value with four dice can be expressed as

6 0
1 X 1663107
E4 = 4 (d1 + min{d2 + d3 + d4 , d2 + d3 + 3, d2 + E2 , E3 }) = = 5.833858...
6 67
i,j,k,l
=0

where the sum skips 3, and d1 ≤ d2 ≤ d3 ≤ d4 is {i, j, k, l} sorted in increasing order.

Finally, the expected value with five dice can be expressed as

6 0 ( 5
)!
1 X X
E5 = 5 d1 + min dn , d2 + d3 + d4 + 3, d2 + d3 + E2 , d2 + E3 , E4
6
i,j,k,l,m n=2
=0
13613549985
= = 6.253978525....
612
where the sum skips 3, and d1 ≤ d2 ≤ d3 ≤ d4 ≤ d5 is {i, j, k, l, m} sorted in increasing order.
Thus, the expected score in this game, played with an optimal strategy, is about 6.25398.
But, what is the optimal strategy? It is essentially encoded above, but is there a more simple
statement? A small simplification is made by noting that a sum of integers is less than, say,
4.38888... only if the sum is less than or equal to 4. So the Ei values that appear in the sums
above can be replaced by their integer parts.
It is a tricky strategy to paraphrase. Consider that if you roll 3-3-3-2-2, you should keep all
the dice, but if you roll 3-3-2-2-2, you should re-roll the 2s, since 6 > E3 = 5.233796... . The
strategy is not summarizable to a “this die or less should always be kept on roll i" simplicity.

104
A Collection of Dice Problems Matthew M. Conroy

A further question: what is the probability of getting a score of zero? This question has more
than one interpretation: (a) what is the probability of getting a score of zero if played using
the “optimal" strategy above, and (b) what is the probability of getting a score of zero if the
player does everything possible to get a score of zero (i.e., keeps only 3s as long as possible).
(Special thanks to David Korsnack for inspiring me to look into this problem, and for providing some
numerics with which I could compare my calculations.)

72. Pig In the game of Pig, two players take turns rolling a die. On a turn, a player may roll the die as
many times as they like, provided they have not thrown a one. If they end their turn before rolling a
one, their turn score is the sum of rolls for that turn. If they roll a one, their turn score is zero. At the
end of the turn, their turn score is added to the player’s total score. The first player to reach 100 points
wins.
Let’s consider the strategy for playing this game in which the player will roll until their turn score is
at least M . What value of M will maximize their expected turn score? What is the expected value?
We can determine the M which will maximize the expected score by arguing that we should
keep rolling as long as the expected score after rolling is at least as large as our current score.
So we should stop if our score S satisfies
5
S ≥ (S + 4),
6
which yields S ≥ 20. Since we could equally argue that we should stop only if our score
satisfies
5
S > (S + 4),
6
we conclude that M = 20 and M = 21 are equally good as far as maximizing the expected
turn score.
To work out the expected score, we begin with the generating function for a die, with the one
excluded:
1 1 1 1 1
p0 = x2 + x3 + x4 + x5 + x6
6 6 6 6 6
Considering M = 20 for now, we note that to reach 20 will require at least four rolls. Raising
p0 to the fourth power, we have
1 24 1 23 5 22 5 21 35 20 13 19 17 18 5
p40 = x + x + x + x + x + x + x + x17
1296 324 648 324 1296 324 324 81
85 16 5 17 14 13 13 35 12 5 11 5 10 1 9 1 8
+ x + x15 + x + x + x + x + x + x + x
1296 81 324 324 1296 324 648 324 1296
This polynomial gives the distribution of scores after four rolls, except for the score of zero,
the probability of which we can find as the complement of the sum of all of these probabilities.
Note that, if the score has reached 20 or more, the player stops rolling. So when considering
the situation after five rolls, we must remove the terms with power 20 or higher.
Thus, the distribution after five rolls, given that 20 was not achieved earlier, is given by

13 19 17 18 5 85 16 5 17 14 13 13 35 12
p0 x + x + x17 + x + x15 + x + x + x
324 324 81 1296 81 324 324 1296

5 11 5 10 1 9 1 8
+ x + x + x + x
324 648 324 1296

105
A Collection of Dice Problems Matthew M. Conroy

13 25 5 24 25 23 95 22 365 21 127 20 365 19 10 18

x + = x + x + x + x + x + x + x
1944 324 972 2592 7776 2592 7776 243
85 17 185 16 121 15 35 14 35 13 5 12 5 11 1 10
+ x + x + x + x + x + x + x + x
2592 7776 7776 3888 7776 2592 7776 7776
We thus see more ways the player can reach scores of 20 or above, and we can remove the
corresponding terms from the polynomial, and continue in this way until there are no terms
left. Since we must roll at least 2 if we do not roll a one, at most 10 rolls can occur with a
threshold of M = 20.
So, in this way, we can work out the distribution of scores (and hence the expected score) for
any threshold M .
Here is PARI/GP code that calculates the expected turn score for any threshold, M , using
this method.

p0=1/6*x^6 + 1/6*x^5 + 1/6*x^4 + 1/6*x^3 + 1/6*x^2

f(M)=s=0;p=p0;
while(poldegree(p)>1,
for(j=M,poldegree(p),
s=s+j*polcoeff(p,j);
p=p-polcoeff(p,j)*x^j);
p=p*p0);
return(s)

For M = 20 or M = 21, the expected turn score is

492303203
= 8.1417948937... .
60466176
Though the expected values are the same, the distributions are not. For one thing, with
M = 20, the probability of getting zero on a turn is about 0.6245 while with M = 21, the
probability is about 0.6412.
What about other values of M ?
Here is a plot of the expected turn score for M ranging from 2 to 100:
expected turn score using threshold M

0 10 20 30 40 50 60 70 80 90 100
M

106
A Collection of Dice Problems Matthew M. Conroy

The expected score is above 8 for 17 ≤ M ≤ 24 (and equal to about 7.99718 when M = 25).
The expected score when M = 2 is 10/3 = 3.333.... This is matched closely at M = 65, for
which the expected score is 3.29346..., and M = 64, with an expected score of 3.39364.... An
interesting question: if one player uses M = 2 and the other uses M = 64 or 65, which player
will win more often?
At M = 100, the expected turn score is just above 1, at 1.03693....
Although M = 20 and M = 21 yield the highest expected turn score, this does not mean
that these maximize the probability of winning in an actual game. (More on this in a future
problem!)
73. More Pig Suppose in a game of Pig, a player decides to just go for it and try to roll 100 points on
their first turn. What is the probability that they will succeed?
We can find this probability using a Markov chain with the states 0, 1, ..., 100, 101 where the
states < 100 are the total rolled so far, 100 is the state that a total of 100 or more has been
achieved, and state 101 is the state we transition to if we roll a 1 before reaching state 100. We
make both states 100 and 101 absorbing states: once we enter these states, we cannot leave
them.
Then, we calculate the transition matrix, A, for this chain.
Here is some Sage code that does it:

M=100
A=zero_matrix(QQ,M+2);
for i in range(0,M):
for j in range(2,7):
test = j+i
if (test>=M):
test = M
A[i,test]+= 1/6
A[i,M+1]=1/6
A[M,M]=1
A[M+1,M+1]=1

For each state i < 100, there is a 1/6 chance that we will roll a 1 and transition to state 101,
the "lost" state. For states < 94, there will be six non-zero entries: 1/6 in the 101 column, and
five 1/6 in a row, indicating the increase in the score due to the roll of the die. When the state
is 94 or higher, we have a chance to reach 100, so the probabilities start piling up in the 100
column for these rows.
We can notice that, since the smallest non-one face we can safely roll is 2, it will take at most
100/2 = 50 rolls to reach 100. Hence, we can determine the probability of reaching 100 before
rolling a 1 by raising A to the power of 50 and looking at the 100 entry of the first row.
We do this and find the probability, p, to be
2060507550845146798433160823128452341
p= = 0.0101969827004188....
202070319366191015160784900114134073344
So we see that the player has a just over 1 percent chance of succeeding:
1 1
p= + .
100 5076.5789 . . .

107
A Collection of Dice Problems Matthew M. Conroy

74. Can’t Stop In the game of Can’t Stop, a player rolls four dice at once, groups the dice into pairs
and then sums each pair. The player gets to choose which grouping the want. For example, if they roll
6 − 4 − 2 − 1, they can group them in one of the following ways:

• (6, 4) and (2, 1), for a sum pair of 10 and 3;

• (6, 2) and (4, 1), for a sum pair of 8 and 5;
• (6, 1) and (4, 2), for a sum pair of 7 and 6.

What are the probabilities of rolling each possible sum pair? What are the probabilities of each possible
sum?
Probabilities for each possible pair are shown in the following table. In the table, n is the num-
ber of ways to throw the pair out of the 1296 = 64 possible throws, and p is an approximate
decimal value of the probability n/1296.
pairs n p
( 2 , 2 ), ( 12 , 12 ) 1 0.00077
( 2 , 3 ), ( 11 , 12 ) 4 0.00308
( 2 , 12 ), ( 3, 3 ), ( 11, 11 ) 6 0.00462
( 2 , 4 ), ( 10 , 12 ) 10 0.00771
( 2 , 11 ), ( 3 , 12 ) 12 0.00925
( 2 , 5 ), ( 3 , 4 ), ( 9 , 12 ), ( 10, 11 ) 16 0.01234
( 2 , 10 ), ( 4 , 12 ) 18 0.01388
( 4 , 4 ), ( 10, 10 ) 19 0.01466
( 2 , 6 ), ( 8 , 12 ) 22 0.01697
( 2 , 9 ), ( 3 , 5 ), ( 3 , 11 ), ( 5 , 12 ), ( 9 , 11) 24 0.01851
( 2 , 7 ), ( 7 , 12 ) 28 0.0216
( 2 , 8 ), ( 6 , 12 ) 30 0.02314
( 3 , 6 ), ( 3, 10 ), ( 4 , 11 ), ( 5 , 5 ), ( 8 , 11 ), ( 9 , 9) 36 0.02777
( 4 , 5 ), ( 9 , 10 ) 40 0.03086
( 3 , 7 ), ( 3 , 8 ), ( 3 , 9 ), ( 5 , 11 ), ( 6 , 11 ), ( 7 , 11) 48 0.03703
( 4 , 10 ) 54 0.04166
( 4 , 9 ), ( 5 , 10 ) 60 0.04629
( 6 , 6 ), ( 8 , 8 ) 61 0.04706
( 4 , 6 ), ( 8 , 10) 62 0.04783
( 4 , 8 ), ( 6 , 10 ) 70 0.05401
(5,9) 72 0.05555
( 4 , 7 ), ( 5 , 6 ), ( 7 , 10 ), ( 8 , 9 ) 76 0.05864
( 5 , 8 ), ( 6 , 9 ) 88 0.0679
(7,7) 90 0.06944
( 5 , 7 ), ( 7 , 9 ) 96 0.07407
(6,8) 110 0.08487
( 6 , 7 ), ( 7 , 8 ) 124 0.09567
It is worth nothing that (7, 7) is not the mostly likely pair.
The probability of being able to get any single sum on a single roll is as follows (with n the
number of ways out of 64 = 1296 rolls, and p ≈ n/1296):

108
A Collection of Dice Problems Matthew M. Conroy

sum n p
2 171 0.13194
3 302 0.23302
4 461 0.3557
5 580 0.44753
6 727 0.56095
7 834 0.64351
8 727 0.56095
9 580 0.44753
10 461 0.3557
11 302 0.23302
12 171 0.13194
These probabilities can all be worked out with some code with a few nested for-loops.
The game is very complex (see, for example, this paper by James Glenn and Christian Aloi)
so I don’t know what problems related to it I will eventually talk about here, but I wanted to
at least get these tables introduced for those interested.

75. Suppose we play a game with a die where we roll and sum our rolls. We can stop any time and take
the sum as our score, but if we roll a face we’ve rolled before then we lose everything. What strategy
will maximize our expected score?
We want to roll until the expected sum after rolling is less than our current sum. Let C be
our current sum and S be the set of faces that have been rolled already. Then we should stop
if
|S| X1
·0+ (C + i) < C.
6 6
i6∈S
X
Using the fact that i = C, this inequality simplifies to
i∈S

C(|S| + 1) > 21.

After our first roll, |S| = 1 and C < 6 so C(|S| + 1) ≤ 12. Hence we should roll again. After
our second roll, |S| = 2, so we should stop if C > 7. After our third roll, |S| = 3, so we should
stop if C > 214 , that is, if C ≥ 6. However, if we have made it to our third roll, C must be at
least 6, and so we should stop at this point.
Thus: Roll twice. If the second roll is not the same as the first, and the sum is less than 7, roll
again and stop; otherwise, stop.
223
With this strategy, the expected score is = 6.194̄ and the game ends with a zero score
36
5
with probability = 0.27̄.
18
76. (Same as previous game, but with two dice.) Suppose we play a game with two dice where we roll and
sum our rolls. We can stop any time and take the sum as our score, but if we roll a sum we’ve rolled
before then we lose everything. What strategy will maximize our expected score?
Let C be our current score, and S be the set of sums rolled so far, so
X
C= i.
i∈S

Let p(i) be the probability of rolling a sum of i with a single roll of two dice.

109
A Collection of Dice Problems Matthew M. Conroy

Then, to maximize our expected score, we should stop rolling if the expected score after
rolling again is less than our current score. That is,
!
X X
p(i) · 0 + p(i)(C + i) < C.
i∈S i6∈S

This simplifies to X
p(i)(C + i) > 7. (3.24)
i∈S

When does this occur?

After a single roll r, the stopping condition is

2rp(r) > 7.

Since the left-hand side maxes out at r = 7, with 2rp(r) = 73 , we should always roll at least
twice.
One can check as well that, after two rolls, the left-hand side of (3.24) is at most 247
36 ≈ 6.861 <
7, so we should always roll at least three times (if we can).
After rolling three times, there are many S for which we should stop. We should stop after
three rolls if any of the following are true:

• {6, 7}, {7, 8}, {7, 9}, {7, 10}, or {8, 9} ⊂ S

• 2 6∈ S and {6, 8}, {6, 9}, {6, 10}, {7, 11}, {7, 12}, {8, 10}, {8, 11} ⊂ S
• current score is 28 or greater and S 6= {5, 11, 12}
• S ∈ {{3, 9, 10}, {4, 5, 7}, {4, 5, 8}, {4, 5, 9}, {4, 6, 11}, {4, 8, 12}, {4, 9, 10}, {4, 9, 11},
{4, 9, 12}, {4, 10, 11}, {5, 6, 11}, {5, 6, 12}, {5, 8, 12}, {5, 9, 10}, {5, 9, 11}, {5, 9, 12}, {5, 10, 11},
{5, 10, 12}}

After rolling four times, we should stop unless one of the following is true:

(a) {2, 3, 4} ⊂ S and 7 6∈ S

(b) S equals one of {2, 3, 5, 6}, {2, 3, 5, 11}, {2, 3, 5, 12}, {2, 3, 10, 12}, {2, 3, 11, 12}, {2, 4, 11, 12}.
X
If we are lucky enough to roll five times, we should stop. With |S| = 5, p(i)(C + i) is
i∈S
minimal when S = {2, 3, 4, 5, 12}, with the sum being 169
18 ≈ 9.389 > 7.
If we apply this optimal strategy, the expected score will be 513389
34992 ≈ 14.671611.
With this strategy, the smallest non-zero score that can be attained is 15, and the largest pos-
217495
sible score is 39. The probability of zero is ≈ 0.345309, and the most likely non-zero
629856
score is 21, occuring with probability 139968 ≈ 0.0722237.
10109

In the optimum strategy described above, the stopping condition was

X
p(i)(C + i) > 7.
i∈S

110
A Collection of Dice Problems Matthew M. Conroy

The greater than symbol can be replaced with greater-than-or-equals and the resulting strat-
egy will yield the same expected value, but a very slightly different score distribution.
Interestingly, instead of using this complex strategy, a very good and simple strategy is to al-
6265
ways stop after three rolls. With this simple strategy, the expected score is ≈ 14.502315,
432
not that much less than the optimal strategy. The range of possible non-zero scores is 9 to 33.
401
The probability of scoring zero is ≈ 0.309414 and the most likely non-zero score is 21,
1296
277
as it is with the complex strategy, and this occurs with probability ≈ 0.0712449.
3888
The plots below show the score distribution for the “> 7" strategy in black and the “stop after
three rolls" strategy in blue; the second plot has the values on a logarithmic scale.
probability of scoring i with optimal strategy

0.3

0.2

0.1

0 5 10 15 20 25 30 35
i
0

−1
log10 of prob. of scoring i

−2

−3

−4

−5

0 5 10 15 20 25 30 35
i
The simple strategy can be made quite a bit better while keeping it simple by adding a score
condition. If the strategy is to stop rolling if we have rolled at least three times and our score

111
A Collection of Dice Problems Matthew M. Conroy

is 16 or greater, experiments show the expected value is close to 14.6! If we want a strategy
based purely on the score, the best strategy appears to be stopping when the score is at least
18, which yields an expected value just over 14.3.

77. Suppose we play a game with a die where we roll and sum our rolls. We can stop any time and take
the sum as our score, but if we roll the same face twice in a row we lose everything. What strategy will
maximize our expected score?
If the last face rolled is r and our current sum is S, then the expected value of our score if we
roll again is  
6
1 5 1 X
·0+ S+  i .
6 6 6
i=1,i6=r

If this is less than S, we should not roll. When is it less than S? It depends on S and r.
Specifically, if S is greater than the sum of all faces other than r, we should not roll. In other
words, if
r + S > 21
then rolling will not, on average, increase our score, and so we should stop. With this strategy,
the expected score is about 8.7, with zero scores occurring about 56% of the time. General-
izing to m-sided dice, we should stop if the current sum plus the last roll exceeds the sum of
all faces of the die.

78. Suppose we play a game with a die. We roll once, and this first roll is the score.
We may continue to roll and add to the score, but if the roll ever divides the score we start with (e.g.,
if our score is 15 and we roll a 1, 3, or 5), then we lose everything and end up with nothing. If instead
we choose to stop, we win an amount proportional to the score.
What strategy will yield the maximum expected value of our final score?
This is an optimal stopping problem. We are trying to decide the strategy, which consists of a
rule for when to stop rolling, and we want it to be optimal in the sense that it maximizes our
expected final score.
A strategy in this game is a set of positive integers A = {a1 , a2 , . . . }: we will continue rolling
as long as our score x in A; that is, we will stop rolling only when x 6∈ A.
A given set A entirely determines how the game is played, and so there is an expected value
of the score at the end of the game for each A. Call it E(A). We wish to choose A from all
possible subsets of positive integers so that E(A) is maximized.
Since there are infinitely many such subsets A, this seems a daunting task.
To cut things down to size, we begin by arguing that there exists a bound B such that if our
score x is greater than or equal to B, we should stop rolling. That is, we should stop rolling
when our score is B or greater.
How to find such a B?
Consider a score of x.
If we roll once more, the maximum our expect value then could be is certainly (being very
wasteful here)
5
≤ (x + 6)
6

112
A Collection of Dice Problems Matthew M. Conroy

and
5
(x + 6) < x
6
when x > 30. Thus, if our score is greater than 30, our expected value will not increase with
any number of additional rolls, since each roll reduces the expected value.
So we should stop rolling if our score is ever greater than 30.
We can do better than this.
The general situation is actually that the expected score after rolling once from a score of x is

1 1 1 1 1
= · (x + 2) · r2 + · (x + 3)r3 + · (x + 4)r4 + · (x + 5)r5 + · (x + 6)r6
6 6 6 6 6
where ri ∈ {0, 1} with ri = 1 only if i does not divide x. From this we see that the expected
score after rolling once from any score x is
6
X 1 5 20 5
≤ (x + i) = x + = (x + 4)
6 6 6 6
i=2

which is ≤ x when x ≥ 20. Hence, we should stop rolling if our score is ever greater than or
equal to 20.
(Note that additional rolls will not be helpful. If we roll once from a score of x, our expected
score is less. If we roll m times from a score of x, our expected score is
 m
5
≤ (x + 4m)
6

which is less than or equal to x when

4m(5/6)m
x≥ .
1 − (5/6)m

This right-hand expression is maximal when m = 1, yielding x ≥ 20. Hence, we should stop
rolling when our score is greater than or equal to 20.)
With this, we just have to consider scores less than 20 and decide whether we should stop or
continue rolling at each of them.
If x = 19, then the expected score with one additional roll is

5 115
(19 + 4) = = 19.16̄ > 19
6 6
so rolling when our score is 19 is advantageous. Now, since we will not roll on any score of
20 or greater (i.e., we will roll exactly once), the expected score starting from a score of 19 is
19.16̄.
With x = 18, if we roll again, we will roll exactly once; our expected score would be

1 1
(22) + (23) = 7.5 < 18
6 6
so we should not roll on x = 18

113
A Collection of Dice Problems Matthew M. Conroy

With x = 17, if we roll once, our expected score is

5
(17 + 4) = 17.5 > 17
6
so we should roll on 17. However, our expected score starting from a score of 17 is not 17.5,
since if we roll 2, and reach a score of 19, we will roll again. Hence, the expected score starting
from a score of x = 17 is
1 1 1 1 1 631
(19.16̄) + (20) + (21) + (22) + (23) = = 17.527̄.
6 6 6 6 6 36

Rolling from x = 16, our expected score will be

1 1 1
= (19.16̄) + (21) + (22) = 10.38̄ < 16
6 6 6
so we should not roll when our score is 16.
Continuing in this way, downward, we have the following table of expected scores E starting
from a score of x:
x E E, approx.
19 115/6 19.167
18 15/2 7.5000
17 631/36 17.528
16 373/36 10.361
15 2077/216 9.6157
14 2689/216 12.449
13 3085/216 14.282
12 631/216 2.9213
11 16591/1296 12.802
10 9565/1296 7.3804
9 72685/7776 9.3474
8 53245/7776 6.8474
7 454363/46656 9.7386
6 29551/7776 3.8003
5 1860997/279936 6.6479
4 1357033/279936 4.8477
3 9443323/1679616 5.6223
2 8506279/1679616 5.0644
1 55186267/10077696 5.4761
In bold are those x at which it is beneficial to continue rolling (i.e., E > x).
The most interesting, perhaps is x = 9. If we calculate the expected score with one additional
roll from x = 9, not considering additional rolls at all, we get
1
(11 + 13 + 14 + 15) = 8.83̄ < 9.
6
It may appear that we should not roll on 9. However, since when landing on 11 or 13 it is
to our advantage to roll more, the true story is that it is advantageous to roll further from a
score of 9, with an expected score, ultimately, of about 9.34.
So, the optimal strategy will be to roll again when our score is one of

A = {1, 2, 3, 4, 5, 7, 9, 11, 13, 17, 19}

and otherwise stop.

114
A Collection of Dice Problems Matthew M. Conroy

What is the expected final score, E(A), with this strategy?

We can view the game as a Markov chain with the following transition matrix, M :
 
0 16 16 16 16 16 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 16 16 16 16 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
 
 0 0 6


 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 
 6 6 6 6 3 
 0 0 0 0 0 16 0 16 16 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
 
0 0 3

 
 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 
 6 6 6 2 
 0 0 0 0 0 0 0 16 16 16 0 16 0 0 0 0 0 0 0 0 0 0 0 0 1
 
0 0 3

 
 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
 
 0 0 0 0 0 0 0 0 0 16 16 16 16 16 0 0 0 0 0 0 0 0 0 0 1
 
0 0 6

 
 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
 
 0 0 0 0 0 0 0 0 0 0 0 16 0 16 16 16 0 0 0 0 0 0 0 0 0 0 1
 
3

 
 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
 
 0 0 0 0 0 0 0 0 0 0 0 0 0 16 16 16 16 16 0 0 0 0 0 0 0 0 1
 
 6 

 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
 
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 16 16 16 16 16 0 0 0 0 0 0 1
 
 6 

 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 
 
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
 

 
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 
 
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 16 16 16 16 16 0 0 1
 
 6 

 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 
 
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 16 16 16 1 1 1
 
 6 6 6 

 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 
 
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
 

 
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 
 
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
 

 
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 
 
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 
 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

With indices from 0 to 26, we have 0 as the initial state and 26 as the absorbing "lost every-
thing, game over" state. In between, state i corresponds to a score of i. If our strategy says to
stop rolling when in state i, then Mi,i = 1. For each state i, we set Mi+j = 1/6 exactly when
2 ≤ j ≤ 6 and j does not divide i. All other entries of M are zero.
Then, since the game is over in at most ten turns (hitting every odd score from 1 to 19 and
then taking one last roll), the first row of M 10 tells us the probability of ending in each of the
states:

115
A Collection of Dice Problems Matthew M. Conroy

6 2/9 0.222222222222222
8 133/1296 0.102623456790123
10 463/7776 0.0595421810699589
12 211/7776 0.0271347736625514
14 10561/279936 0.0377264803383631
15 81523/1679616 0.0485366893385155
16 43903/1679616 0.0261387126581314
18 18157/1679616 0.0108102090001524
20 43903/10077696 0.00435645210968856
21 416263/60466176 0.00688422896132873
22 416263/60466176 0.00688422896132873
23 416263/60466176 0.00688422896132873
24 152845/60466176 0.00252777685164016
25 152845/60466176 0.00252777685164016
26 26314915/60466176 0.435200582223027

The last entry in the table is the probability of ending with a score of zero, so we finish with
a non-zero score with probability

34151261
= 0.564799417....
60466176

By summing these non-zero score absorbing state probabilities scaled by the score, we find
the expected value of the final score with this optimal strategy to be

339199135
E(A) = = 5.60973353102402....
60466176

What if we change the strategy to include stopping on 9, too? The new expected value of the
score with this suboptimal strategy would be just a little less: approximately 5.563053.

79. Suppose we play a game with a die where we roll and sum our rolls as long as we keep rolling larger
values. For instance, we might roll a sequence like 1-3-4 and then roll a 2, so our sum would be 8. If
we roll a 6 first, then we’re through and our sum is 6. Three questions about this game:

(a) What is the expected value of the sum?

(b) What is the expected value of the number of rolls?
(c) If the game is played with an n-sided die, what happens to the expected number of rolls as n
approaches infinity?

We can consider this game as a Markov chain with an absorbing state. If we consider the
state to be the value of the latest roll, or 7 if the latest roll is not larger than the previous one,
then we have the following transition matrix:

0 1/6 1/6 1/6 1/6 1/6 1/6

 
 0 0 1/6 1/6 1/6 1/6 2/6 
 0 0 0 1/6 1/6 1/6 3/6 
P = (3.25)
 
0 0 0 0 1/6 1/6 4/6 

 0 0 0 0 0 1/6 5/6 

0 0 0 0 0 0 1
0 0 0 0 0 0 1

116
A Collection of Dice Problems Matthew M. Conroy

Using the notation of Appendix D, we have

 
0 1/6 1/6 1/6 1/6 1/6
 0 0 1/6 1/6 1/6 1/6 
 0 0 0 1/6 1/6 1/6 
Q=  0 0

0 0 1/6 1/6 
0 0 0 0 0 1/6
 
0 0 0 0 0 0

so that N = (I − Q)−1 is
 
1 1/6 7/36 49/216 343/1296 2401/7776
 0 1 1/6 7/36 49/216 343/1296 

N = 0 0 1 1/6 7/36 49/216 
 0 0 0 1 1/6 7/36 
0 0 0 0 1 1/6
 
0 0 0 0 0 1

The row sum of N is  

16807/7776
 2401/1296 

 343/216 

 49/36 
7/6
 
1
and so the expected number of rolls before absorption (i.e., the number of rolls that count in
the sum) is

(1/6) (16807/7776 + 2401/1296 + 343/216 + 49/36 + 7/6 + 1) = 70993/7776 ≈ 1.521626.

We use N to calculate the expected sum as well. If the first roll is a 1, the expected sum will
be
1 7 49 343 2401
1+2· +3· +4· +5· +6· = 6.
6 36 216 1296 7776
In fact, for any first roll, the expected sum is 6. Hence, the expected sum is 6.
Now, suppose the game is played with an n-sided die. Let E be the expected number of rolls.
Let E(j) be the expected number of rolls if the first roll is j. Then,

1 1 1
E(j) = 1 + E(j + 1) + E(j + 2) + · · · + E(n)
n n n
and so
1 1 1
E(j + 1) = 1 + E(j + 2) + E(j + 3) + · · · + E(n)
n n n
from which we can conclude
 
1
E(j) = 1 + E(j + 1).
n

Since E(n) = 1, we have

 n−j
1
E(j) = 1+ .
n

117
A Collection of Dice Problems Matthew M. Conroy

Thus,
n n   n 
1 n−j 1 n+1 nX
  j
1X 1X n
E= E(j) = 1+ =
n n n n n n+1
j=1 j=1 j=1

n+1 n
n  
n+1 n
    
n
= 1− = − 1.
n n+1 n
And so we see that
lim E = e − 1 = 1.718281828459....
n→∞

80. Suppose we play a game with a die where we roll and add our rolls to our total when the face that
appears has not occurred before, and subtract it from our total if it has.
For example, if we rolled the sequence 1, 3, 4, 3, our corresponding totals would be 1, 4, 8, 5.
We can stop any time and take the total as our score. What strategy should we employ to maximize
our expected score?
The optimal strategy need only consider what faces have already appeared.
If A is the set of distinct faces which have already appeared, then the expected change C in
the total on the next roll of the die is
1 X 1 X
C=− i+ i.
6 6
1≤i≤6 1≤i≤6
i∈A i6∈A

If this is negative, we should stop rolling, since on the next roll we expect to decrease our
total, and any further rolling only makes the situation worse.
Now, C is negative if the sum of the distinct faces thrown is 11 or more, and positive other-
wise. Hence, to maximize the expected value of our score, we should keep rolling until the
sum of distinct faces thrown is 11 or more.
For example, if we roll 1, 3, 5, 1, 6, then we should stop, with a score of 16.
Experimentally, we can find that this strategy yields an expected score of about 8.7.

81. Suppose we roll a single die, repeatedly if we like, and sum. We can stop at any point, and the sum
becomes our score; however, if we exceed 10, our score is zero.
What should our strategy be to maximize the expected value of our score? What is the expected score
with this optimal strategy?
What about limits besides 10?
We consider the game first with a limit of 10.
We need to decide, if our current score is n, whether or not we should continue rolling.
Suppose our current score is 10. Then rolling will not help, since our score would become
zero. So we must “stick" (i.e., not roll) if our score is 10.
Suppose our current score is 9. Then rolling will give us an expected score of
   
1 5 10
10 + 0= < 9.
6 6 6

Since the expected value is less than 9, it is better to stick on 9 than to roll.

118
A Collection of Dice Problems Matthew M. Conroy

Suppose our current score is 8. Then rolling will give us an expected score of
     
1 1 4 19
9+ 10 + 0= <8
6 6 6 6

so we should stick on 8.
Suppose our current score is 7. Then rolling will give us an expected score of
       
1 1 1 3 9
8+ 9+ 10 + 0= <7
6 6 6 6 2

so we should stick on 7.
Suppose our current score is 6. Then rolling will give us an expected score of
         
1 1 1 1 2 17
7+ 8+ 9+ 10 + 0= <6
6 6 6 6 6 3

so we should stick on 6.
Suppose our current score is 5. Then rolling will give us an expected score of
           
1 1 1 1 1 1 20
6+ 7+ 8+ 9+ 10 + 0= > 5.
6 6 6 6 6 6 3

Since the expected value is greater than 5, we should roll, even though there is a chance that
we will end up with a score of zero.
If our current score is 4 or less, then there is no chance that one more roll will result in a score
of zero (i.e., a lower score than the current score), so it is always better to roll.
Hence, the optimal strategy is: roll again if the score is 5 or less, and stick otherwise.
To calculate the expected final score with this strategy, let E(m) be the expected final score
starting with a current score of m. Then we seek E(0).
If m > 5, E(m) = m.
P10
If m = 5, we have E(5) = 1
6 i=6 E(i) = 3 .
20

Then
6
1X 70
E(4) = E(4 + i) =
6 9
i=1
6
1 X 200
E(3) = E(3 + i) =
6 27
i=1
6
1X 1157
E(2) = E(2 + i) =
6 162
i=1
6
1 X 6803
E(1) = E(1 + i) =
6 972
i=1
6
1X 40817
E(0) = E(i) =
6 5832
i=1

119
A Collection of Dice Problems Matthew M. Conroy

Thus, the expected value of the score is 40817

5832 = 6.99879972565157..., just the tiniest bit less
than 7.
What about other limits?
Suppose the limit is k (so we lose all points if the score ever exceeeds k).
Then if our current score is n = k − 1, our expected score if we roll is 16 (n + 1) which is greater
than n if and only if n < 15 , i.e., n = 0. Thus, should always stop on if our current score is
k − 1 or greater.
Suppose our current score is n = k − 2. If we roll, our expected score is 16 (n + 1 + n + 2) =
6 (2n + 3) which is greater than n if and only if n < 4 , i.e., n = 0. So we should always stop
1 3

if our current score is k − 2 or greater.

Suppose our current score is n = k − 3. Then the expected score if we roll is 16 (n + 1 + n + 2 +
n + 3) = 16 (3n + 6) which is greater than n if and only if n < 2, i.e., k < 5. Hence, we should
stick on k − 3 or greater, unless k = 4, in which case we should roll on k − 3.
Suppose our current score is n = k − 4. Then the expected score if we roll is 16 (n + 1 + n + 2 +
n + 3 + n + 4) = 16 (4n + 10) which is greater than n if and only if n < 5, i.e., k < 9. Hence we
should stick on k − 4 or greater, unless k = 5, 6, 7, or 8, in which case we should roll on k − 4.
Suppose our current score is n = k − 5. Then the expected score if we roll is 16 (n + 1 + n +
2 + n + 3 + n + 4 + n + 5) = 16 (5n + 15) which is greater than n if and only if n < 15, i.e.,
k < 20. Hence, we should stick on k − 5 or greater if k ≥ 20, and otherwise roll on k − 5.
Let k be the limit in our game, and let s be the sticking value, i.e., we should stop rolling if out
score is at or above s. Then, for all k ≥ 20, the sticking value is k − 5. For smaller values of k,
the s values are summarized in the table below.
What are the expected scores using this optimal strategy?
For any k, let E(x) be the expected value of our final score if our score is x.
If k = 1, then the expected score is 16 (1) = 16 .
If k = 2, then the expected score is 16 (1) + 16 (2) = 12 .
If k = 3, then the expected score is 16 (1 + 2 + 3) = 1.
If k = 4, then the expected score is 16 (2 + 3 + 4) + 16 ( 16 (2 + 3 + 4)) = 7
4 = 1.75.
If k = 5, then the expected score is 16 (2 + 3 + 4 + 5) + 16 ( 16 (2 + 3 + 4 + 5)) = 49
18 = 2.72̄.
Suppose k = 6. We stick on 3 or greater. Then E(3) = 3, E(4) = 4, E(5) = 5, and E(6) = 6.
Then E(2) = 16 (E(3) + E(4) + E(5) + E(6)) and E(1) = 16 (E(2) + E(3) + E(4) + E(5) + E(6)).
Finally, the expected score is
6
1X 49
E(i) = = 4.083̄.
6 12
i=1

Suppose k = 7. We stick on 4 or greater. Then E(4) =

P4, E(5) = 5, E(6) = 6, and E(7) = 7,
and we may set E(x) = 0 if x > 7. Then E(j) = 16 6i=1 E(j + i) for j = 0, 1 and 2. The
expected score is then E(0) = 3017
648 ≈ 4.6558642.
Using the same technique, we have the following table of results.

120
A Collection of Dice Problems Matthew M. Conroy

k s E(0) E(0) approx.

1 1 1/6 0.166666
2 1 1/2 0.5
3 1 1 1
4 2 7/4 1.75
5 2 49/18 2.722222
6 3 49/12 4.083333
7 4 3017/648 4.655864
8 5 20629/3888 5.305813
9 5 46991/7776 6.043081
10 6 40817/5832 6.998800
11 7 84035/10368 8.105228
12 8 7695859/839808 9.163831
13 9 101039827/10077696 10.026084
14 10 55084715/5038848 10.932006
15 11 4307852885/362797056 11.874002
16 12 13976066993/1088391168 12.841033
17 13 60156375517/4353564672 13.817729
18 14 1131329591/76527504 14.783307
19 15 7388908661401/470184984576 15.714897
20 15 2611098542647/156728328192 16.660029
50 45 46.666667
100 95 96.666667
The calculations suggest that the expected score approaches k − 10
3 as k goes to infinity. We
can prove this with the following argument.
For any k ≥ 20, while using the optimal strategy, if our final score is not zero, then the final
score must be one of k, k − 1, k − 2, k − 3, k − 4 or k − 5.
Using the optimal strategy, to end with a score of k, we must first achieve a sum of k − 6
and then roll a 6. The probably of achieving a sum of k − 6 approaches 2/7 as k approaches
infinity (see Problem 40), so the probably of a final score of k approaches
  
2 1
7 6
as k approaches infinity.
Similarly, in order to end with a score of k − 1, we must first achieve a sum of k − 7 and then
roll a 6 or achieve a sum of k − 6 and roll a 5. So, the probability of ending with a score of
k − 1 approaches   
2 1
2
7 6
as k approaches infinity.
Applying this to all possible non-zero final scores, we find the expected value of the final
score to be, as k approaches infinity,
5   
X 2 1 10
(i + 1) (k − i) = k − .
7 6 3
i=0

121
A Collection of Dice Problems Matthew M. Conroy

For some numerical investigation, let f (k, m) be the expected score of the game with a limit
of k where we use the strategy of stopping on m or greater. We can calculate f (k, m) exactly
in PARI/GP with the following code:

f(k, m) = A=vector(k+6);for(i=m,k,A[i]=i);
for(j=1,m-1,A[m-j]=1/6*sum(n=1,6,A[m-j+n])); return(1/6*sum(i=1,6,A[i]))

By the way, for n = 5, 9 or 20, it turns out that the expected value of the score when stopping
at the optimal s is the same as when stopping at s + 1 (i.e., there are two optimal strategies).
For example, for n = 5, the strategy of stopping on 2 and the strategy of stopping on 3 yield
the same expected value. Similarly, for n = 9, stopping on 5 and stopping on 6 yield the same
expected value, and for n = 20, stopping on 15 and stopping on 16 yield the same expected
value. To see why, we can note that rolling on 15 yields the same expected value as sticking,
and this is the only case of this for n ≥ 20, so there are no more examples of this.

82. Suppose we play a game with a die where we roll and sum our rolls. We can stop any time, and the
sum is our score. However, if our sum is ever a multiple of 10, our score is zero, and our game is over.
What strategy will yield the greatest expected score? What about the same game played with values
other than 10?
Let’s generalize things right away.
Suppose we want to avoid multiples of m. For now, let’s suppose m ≥ 6.
Suppose we have been playing, and our sum is n, and

km < n < (k + 1)m

for some integer k > 0.

If our score is less than (k+1)m−6, then we should certainly roll until it is at least (k+1)m−6,
since there is no risk.
Suppose (k + 1)m − 6 ≤ n < (k + 1)m. Should we roll to get past (k + 1)m? There is at least
a 1/6 chance that this will result in a score of zero, and the best our score could be (without
risking another multiple of m) is (k + 2)m − 1. Hence the expected value E of our score with
risking one multiple of m is
5
E < ((k + 2)m − 1)
6
and this is less than (k + 1)m − 6 if
31
k >4+ .
m
Hence, if k > 4 + m,
31
then we should stop rolling if our score, n, is in the interval

km < n < (k + 1)m

and possibly earlier.

Suppose m = 10. Then 4 + 31 10 = 7.1, so (with k = 8 > 7.1) we should definitely stop rolling
if our score is between 84 and 89.
We can then work out an optimal strategy recursively as follows.
Let E(x) be the expected value of our ultimate score if our sum is ever x.

122
A Collection of Dice Problems Matthew M. Conroy

Then E(84) = 84, E(85) = 85, E(86) = 86, E(87) = 87, E(88) = 88, and E(89) = 89 (since
we will stop at any of those scores). We also know E(x) = 0 if x is a positive multiple of m.
6
1X
We can then define f (n) = E(n + i). Then, if f (n) > n, we should roll when our sum
6
i=1
is n and E(n) = f (n). On the other hand, if f (n) ≤ n, we should stop rolling when our sum
is n and E(n) = n.
In this way, we can calculate E(n) downward from n = 83 to n = 0, noting whether we stop
rolling or not to create our optimal strategy and the expected value of our strategy.
Writing a little code, we can thus find that we should roll unless the sum is 24 or 25 or greater
than 33. With this strategy, the expected score is

162331123011053862884431
= 13.21711859042473....
12281884428929630994432

Applying this same method to other values of m, we have the following table.
m stop if approximate expected value
6 n ≥ 19 7.221451623108286812
7 n ≥ 15 8.585032818442838864
8 n = 18 or n ≥ 26 10.12982919499704393
9 n = 21, 22 or n ≥ 30 11.67916132417996147
10 n = 24, 25, or n ≥ 34 13.21711859042473150
11 n = 27, 28 or n ≥ 38 14.72823564563309959
12 n = 30, 31 or n ≥ 42 16.27534383168068736
13 n = 33, 35, 35 or n ≥ 46 17.90549414976900364
14 n = 36, 37, 38 or n ≥ 50 19.43362157318550401
15 n = 39, 40, 41 or n ≥ 54 20.97094434047380285
16 n = 42, 43, 44, 58, 59, 60, 61, 62 or n ≥ 74 22.51571524339529867
17 n = 45, 46, 47, 62, 63, 64, 65, 66 or n ≥ 79 24.07230800164414883
18 n = 48, 49, 50, 66, 67, 68, 69, 70 or n ≥ 84 25.64211352850069779
19 n = 51, 52, 53, 70, 71, 72, 73, 74 or n ≥ 89 27.21360753502956739
20 n = 54, 55, 56, 74, 75, 76, 77, 78 or n ≥ 94 28.75912955252540060
For 2 ≤ m ≤ 5, it is probably best to attack each one separately, which perhaps I will do some
other time.

83. Suppose we play a game with a die in which we use two rolls of the die to create a two digit number.
The player rolls the die once and decides which of the two digits they want that roll to represent. Then,
the player rolls a second time and this determines the other digit. For instance, the player might roll a
5, and decide this should be the “tens" digit, and then roll a 6, so their resulting number is 56.
What strategy should be used to create the largest number on average? What about the three digit
version of the game?
A strategy in this game is merely a rule for deciding whether the first roll should be the “tens"
digit or the “ones" digit. If the first roll is a 6, then it must go in the “tens" digit, and if it’s a 1,
then it must go in the “ones" digit. This leaves us with what to do with 2,3,4 and 5. If the first
roll is b, then using it as the “ones" digit results in an expected number of 72 · 10 + b. Using it
as the “tens" digit results in an expected number of 10b + 72 . So, when is 10b + 72 > 72 · 10 + b?

123
A Collection of Dice Problems Matthew M. Conroy

When b ≥ 4. Thus, if the first roll is 4, 5 or 6, the player should use it for the “tens" digit. With
this strategy, the expected value of the number is

1
(63.5 + 53.5 + 43.5 + 38 + 37 + 36) = 45.25.
6

In the three-digit version of the game, once we have decided what to do with the first roll,
we’ll be done, since we will then be in the two-digit case which we solved above. Note this is
obviously true if we place the first roll in the “hundreds" digit. If we place the first roll in the
“ones" digit, then the strategy to maximize the resulting number is the same as the two-digit
case, simply multiplied by a factor of ten. If we place the first roll in the “tens" digit, then our
strategy is to put the next roll b in the “hundreds" digit if

100b + 3.5 > 350 + b

i.e., if b ≥ 4. Thus we have the same strategy in all three cases: put the second roll in the
largest digit if it is at least 4.
Now, if the first roll, b, is placed in the “hundreds" digit, then the expected value will be
100b + 45.25. If the first roll is placed in the “ones" digit, then the expected value will be
452.5 + b. If the first roll is placed in the “tens" digit, then the expected value will be

10b + (351 + 352 + 353 + 403.5 + 503.5 + 603.5)/6 = 427.75 + 10b.

Our strategy thus comes down to maximizing the quantities 100b + 45.25, 427.75 + 10b, and
452.5+b. From the graph below, we see that 100b+45.25 is the largest when b ≥ 5; 427.75+10b
is largest when 3 ≤ b ≤ 4, and 452.5 + b is largest when b < 3. Thus our strategy for the first
roll is this: if it is at least 5, put it in the “hundreds" digit; if it is 3 or 4, put it in the “tens"
digit; otherwise, put it in the ones digit. If the second roll is 4, 5, or 6, place it in the largest
available digit.

124
A Collection of Dice Problems Matthew M. Conroy

600

550

500

450

400

350

300

250

200

2 3 4 5
The expected value using this strategy is thus

(645.25 + 545.25 + (40 + 427.75) + (30 + 427.75) + (452.5 + 2) + (452.5 + 1))/6 = 504.

125
Chapter 4

Problems for the future

Here are some problems that I intend to add to this collection some time in the future, as soon
as I get around to writing decent solutions.

1. You roll a single die. You can roll it as many times as you like (or maybe we put an upper
bound, like 10 or 100). When you stop, you will recieve a prize proportional to your average
roll. When should you stop? (Experiments indicate it is when your average is greater than
about 3.8.)

2. Suppose you have a fair die, but you do not know how many faces it has. You roll the die five
(say) times. What is the best estimate for the number of sides based on the rolls?

3. More Drop Dead: probability of getting zero? probability of any particular value?

4. More Threes: probability of getting any particular score?

5. Law of Large Numbers related: What is the expected number of rolls of a single die needed
until there is a 99% chance that the proportion of 2s (say) thrown is within some specified
interval around 1/6 (e.g., 1/6 − 0.01 ≤ r ≤ 1/6 + 0.01 ?

6. For every composite n, there appear to be pairs of “weird" dice with n sides (i.e. a pair of
dice not numbered in the usual way with sum probabilities equal to the standard dice). Prove
this. For many n, there are many such pairs. Give useful bounds on the number of such pairs
in terms of n.
For n = 4k + 2, it appears that the dice

{1, 2, 2, 3, 3, ..., 2k+3, 2k+3, 2k+4}, {1, 3, 5, ..., 2k+1, 2k+2, 2k+3, ..., n−1, n, n+2, n+4, ..., 6k+2}

do the trick.

126
Bibliography

[1] Duane M. Broline. Renumbering of the faces of dice. Mathematics Magazine, 52(5):312–314,
1979.

[2] Lewis C. Robertson, Rae Michael Shortt, and Stephen G. Landry. Dice with fair sums. Amer.
Math. Monthly, 95(4):316–328, 1988.

127
A Collection of Dice Problems Matthew M. Conroy

Additional reading
[Ang 1] Angrisani, Massimo, A necessary and sufficient minimax condition for the loaded dice
problem (Italian), Riv. Mat. Sci. Econom. Social. 8 (1985), no. 1, 3-11
[Ble 1] Blest, David; Hallam Colin, The design of dice, Math. Today (Southend-on-Sea) 32 (1996),
no. 1-2, 8-13
[Bro 1] Broline, Duane M., Renumbering of the faces of dice, Math. Mag. 52 (1979), no. 5, 312-314
[Dia 1] Diaconis, Persi; Keller, Joseph B., Fair dice, Amer. Math. Monthly, 96 (1989), no. 4, 337-339
[Faj 1] Fajtlowitz, S., n-dimensional dice, Rend. Math. (6) 4 (1971), 855-865
[Fel 1] Feldman, David; Impagliazzo, Russell; Naor, Moni; Nisan, Noam; Rudich, Steven; Shamir,
Adi, On dice and coins: models of computation for random generation, Inform. and Comput. 104
(1993), 159-174
[Fer 1] Ferguson, Thomas S., On a class of infinite games related to liar dice, Ann. Math. Statist. 41
(1970) 353-362
[Fre 1] Freeman, G.H., The tactics of liar dice, J. Roy. Statist. Soc. Ser. C 38 (1989), no. 3, 507-516
[Gan 1] Gani, J., Newton on “a question touching ye different odds upon certain given chances
upon dice", Math. Sci. 7 (1982), no. 1, 61-66
[Gri 1] Grinstead, Charles M., On medians of lattice distributions and a game with two dice, Com-
bin. Probab. Comput. 6 (1997), no. 3, 273-294
[Gup 1] Gupta, Shanti S.; Leu, Lii Yuh, Selecting the fairest of k ≥ 2, m-sided dice, Comm. Statist.
Theory Methods, 19 (1990), no. 6, 2159-2177
[Ito ] Itoh, Toshiya, Simulating fair dice with biased coins, Inform. and Compu. 126 (1996), no.1,
78-82
[Koo ] Koole, Ger, An optimal dice rolling policy for risk, Nieuw Arch. Wisk. (4) 12 (1994), no. 1-2,
49-52
[Mae 1] Maehara, Hiroshi; Yamada, Yasuyuki, How Many icosahedral dice?, Ryukyu Math. J. 7
(1994), 35-43
[McM 1] McMullen, P., A dice probability problem, Mathematika 21 (1974), 193-198
[Pom 1] Pomeranz, Janet Bellcourt, The dice problem - then and now, College Math. J. 15 (1984),
no. 3, 229-237
[Rob 1] Roberts, J. D., A theory of biased dice, Eureka 1955 (1955), no. 18, 8-11
[Rob 2]* Robertson, Lewis C., Shortt, Rae Michael; Landry, Stephen G., Dice with fair sums, Amer.
Math. Monthly 95 (1988), no. 4, 316-328
[Sav 1] Savage, Richard P., Jr., The paradox of non-transitive dice, Amer. Math. Monthly 101 (1994),
no. 5, 429-436
[She 1] Shen, Zhizhang; Marston, Christian M., A Study of a dice problem, Appl. Math. Comput.
73 (1993), no. 2-3, 231-247
[Sol 1] Sol de Mora-Charles, Leibniz et le probleme des partis. Quelches papiers inedits [Leibniz
and the problem of dice. Some unpublished papers], Historia Math. 13 (1986), no. 4,352-369
[Wys 1] Wyss, Roland, Identitaten bei den Stirling-Zahlen 2. Art aus kombinatorischen Uber-
legungen bein Wurfelspiel [Identities for Stirling numbers of the second kind from combinatorial
considerations in a game of dice], Elem. Math. 51 (1996), no. 3,102-106

128
Appendix A

Dice sum probabilities

Sums of 3, 6-Sided Dice

Sums of 2, 6-Sided Dice Sum Probability
Sum Probability 3 1/216
2 1/36 4 3/216 = 1/72
3 2/36 = 1/18 5 6/216 = 1/36
4 3/36 = 1/12 6 10/216 = 5/108
5 4/36 = 1/9 7 15/216 = 5/72
6 5/36 8 21/216 = 7/72
7 6/36 = 1/6 9 25/216
8 5/36 10 27/216 = 1/8
9 4/36 =1/9 11 27/216 = 1/8
10 3/36 =1/12 12 25/216
11 2/36 =1/18 13 21/216 = 7/72
12 1/36 14 15/216 = 5/72
15 10/216 = 5/108
16 6/216 = 1/36
17 3/216 = 1/72
18 1/216 = 1/216

129
Appendix B

Handy Series Formulas

For |r| < 1,

∞
X a
arn = (B.1)
1−r
n=0

For r 6= 1,
N
X a(1 − rN +1 )
arn = (B.2)
1−r
n=0

For |r| < 1,

∞
X r
nrn = (B.3)
(1 − r)2
n=1

For r 6= 1,
N
X r − rN +1 (1 + (1 − r)N )
nrn = (B.4)
(1 − r)2
n=1

For |r| < 1,

∞
X r(1 + k − kr)
(n + k)rn = (B.5)
(1 − r)2
n=1

For |r| < 1,

∞
X r(1 + r)
n2 r n = (B.6)
(1 − r)3
n=1

130
Appendix C

Dice Sums and Generating Functions

Very often in mathematics a good choice of notation can take you a long way. An example of
this is the following method for representing sums of dice. Suppose we have an n-sided die, with
sides 1, 2, ..., n that appear with probability p1 , p2 , ..., pn , respectively. Then, if we roll the die twice
and add the two rolls, the probability that the sum is k is given by
n
X n−k
X
pj pk−j = pj pk−j (C.1)
j=1 j=k−1

if we say pi = 0 if i < 1 or i > n.

Now consider the following polynomial:

P = p1 x + p2 x2 + · · · + pn xn (C.2)

If we square P , we get
P 2 = a2 x2 + a3 x3 + · · · + a2n x2n (C.3)
where ak , for k=2, 3,. . . , 2n, is given by
n−k
X
ak = pj pk−j . (C.4)
j=k−1

In other words, the probability of rolling the sum of k is the same as the coefficient of xk in the
polynomial given by squaring the polynomial P .
Here’s an example. Suppose we consider a standard 6-sided die. Then

1 1 1 1 1 1
P = x + x2 + x3 + x4 + x5 + x6 (C.5)
6 6 6 6 6 6
and so
x2 2x3 3x4 4x5 5 x6 6x7 5 x8 4x9 3x10 2x11 x12
P2 = + + + + + + + + + + (C.6)
36 36 36 36 36 36 36 36 36 36 36
x 2 x 3 x 4 x 5 5x 6 x 7 5x 8 x 9 x 10 x11 x 12
= + + + + + + + + + + (C.7)
36 18 12 9 36 6 36 9 12 18 36
And so, we see that the probability of rolling a sum of 9, for instance, is 1/9.

131
A Collection of Dice Problems Matthew M. Conroy

For two different dice the method is the same. For instance, if we roll a 4-sided die, and a 6-
sided die, and sum them, the probability that the sum is equal to k is give by the coefficient on xk
in the polynomial

x x2 x3 x4 x x2 x3 x4 x5 x6
  
+ + + + + + + + (C.8)
4 4 4 4 6 6 6 6 6 6

which, when expanded, is

x2 x3 x4 x5 x6 x7 x8 x9 x10
+ + + + + + + + . (C.9)
24 12 8 6 6 6 8 12 24
Notice that this can be written as
1
x2 + 2 x3 + 3 x4 + 4 x5 + 4 x6 + 4 x7 + 3 x8 + 2 x9 + x10 (C.10)


24
In general, a fair n-sided die can be represented by the polynomial

1
x + x2 + x3 + · · · + xn (C.11)


n
With this notation, many questions about dice sums can be transformed into equivalent ques-
tions about polynomials. For instance, asking whether or not there exist other pairs of dice that
give the same sum probabilities as a pair of standard dice is the same as asking: in what ways can
the polynomial
(x + x2 + x3 + x4 + ... + xn )2
be factored into two polynomials (with certain conditions on the degrees and coefficients of those
polynomials)?
Using more general terminology, such polynomials are called generating functions. They can be
applied in lots of situations involving discrete random variables, including sitations in which the
variables take on infinitely many values: in such cases, the generating function will be a power
series.

132
Appendix D

Markov Chain Facts

[Note: The following useful Markov facts are presented without proofs. Many textbooks on
Markov chains (and stochastic processes more generally) contain some or all proofs of these results.
I really should add a bibliography for this appendix...]

A Markov chain is a mathematical model for describing a process that moves in a sequence of
steps through a set of states. A finite Markov chain has a finite number of states, {s1 , s2 , . . . , sn }.
When the process is in state si , there is a probability pij that the process will next be in state sj .
The matrix P = (pij ) is called the transition matrix for the Markov chain. Note that the rows of the
matrix sum to 1.
The ij-th entry of P k (i.e. the k-th power of the matrix P ) gives the probability of the process
moving from state i to state j in exactly k steps.
An absorbing state is one which the process can never leave once it is entered. An absorbing chain
is a chain which has at least one absorbing state, and starting in any state of the chain, it is possible
to move to an absorbing state. In an absorbing chain, the process will eventually end up in an
absorbing state.
Let P be the transition matrix of an absorbing chain. By renumbering the states, we can always
rearrange P into canonical form:  
Q R
P = 
O J
where J is an identity matrix (with 1’s on the diagonal and 0’s elsewhere) and O is a matrix of
all zeros. Q and R are non-negative matrices that arise from the transition probabilities between
non-absorbing states.
The series N = I + Q + Q2 + Q3 + . . . converges, and N = (I − Q)−1 . The matrix N gives us
important information about the chain, as the following theorem shows.

Theorem 1 Let P be the transition matrix for an absorbing chain in canonical form. Let N = (I − Q)−1 .
Then:

• The ij-th entry of N is the expected number of times that the chain will be in state j after starting in
state i.

• The sum of the i-th row of N gives the mean number of steps until absorbtion when the chain is started
in state i.

133
A Collection of Dice Problems Matthew M. Conroy

• The ij-th entry of the matrix B = N R is the probability that, after starting in non-absorbing state i,
the process will end up in absorbing state j.

An ergodic chain is one in which it is possible to move from any state to any other state (though
not necessarily in a single step).
A regular chain is one for which some power of its transition matrix has no zero entries. A
regular chain is therefore ergodic, though not all ergodic chains are regular.

Theorem 2 Suppose P is the transition matrix of an ergodic chain. Then there exists a matrix A such that

P + P2 + P3 + ··· + Pk
lim =A
k→∞ k
For regular chains,
lim P k = A.
k→∞

The matrix A has each row the same vector a = (a1 , a2 , . . . , an ). One way to interpret this is to
say that the long-term probability of finding the process in state i does not depend on the initial
state of the process.
The components a1 , a2 , . . . , an are all positive. The vector a is the unique vector such that

a1 + a2 + · · · + an = 1

and
aP = a
For this reason, a is sometimes called the fixed point probability vector.
The following theorem is sometimes called the Mean First Passage Theorem.

Theorem 3 Suppose we have a regular Markov chain, with transition matrix P . Let E = (eij ) be a matrix
where, for i 6= j, eij is the expected number of steps before the process enters state j for the first time after
starting in state i, and eii is the expected number of steps before the chain re-enters state i. Then

E = (I − Z + JZ 0 )D

where Z = (I − P − A)−1 ,A = lim P k , Z 0 is the diagonal matrix whose diagonal entries are the same as
k→∞
Z, J is the matrix of all 1’s, and D is a diagonal matrix with Dii = 1/Aii .

Theorem 4 Suppose we have an ergodic Markov chain with transition matrix P . Then the mean recurrence
time for state i is 1/ai where ai is the i-th term of the stationary distribution vector.

134
Appendix E

Linear Recurrence Relations

Here’s a useful theorem:

Theorem 2 Consider the linear recurrence relation

xn = a1 xn−1 + a2 xn−2 + · · · + ak . (E.1)

If the polynomial equation (known as the characteristic equation of the recurrence relation)

xn − a1 xn−1 − a2 xn−2 − · · · − ak = 0 (E.2)

has k distinct roots r1 , ...rk , then the recurrence relation E.1 has as a general solution

xn = c1 r1n + c2 r2n + · · · + ck rkn . (E.3)

for some constants c1 , . . . , ck .

Proof: We can prove this with a bit of linear algebra, but we’ll do that some other time.

Example: May as well do the old classic. The Fibonacci numbers are defined by

f0 = 1, f1 = 1, and fn = fn−1 + fn−2 for n > 1.

The characteristic equation is

x2 − x − 1 = 0
which has roots √ √
1+ 5 1− 5
r1 = and r2 = .
2 2
So √ !n √ !n
1+ 5 1− 5
fn = A +B
2 2
for constants A and B. Since
f0 = 1 = A + B
and √
5
f1 = 1 = A + B + (A − B)
2

135
A Collection of Dice Problems Matthew M. Conroy

we conclude that √ √
1+ 5 −1 + 5
A = √ and B = √
2 5 2 5
so that √ √
(1 + 5)n+1 − (1 − 5)n+1
fn = √ .
2n+1 5

136
Index

Benford’s Law, 46

Central Limit Theorem, 45

coupon collector’s problem, 20, 22, 52
Craps, 8, 91, 92

expectation, 4, 6, 9–13, 17, 20, 22, 24, 25, 28, 33,

34, 37, 51, 56, 67, 70, 94, 98, 111, 118

Gaussian distribution, 65
generating functions, 55, 67, 71, 126

inclusion-exclusion, 14, 18, 25, 29

linear programming, 83
linear recurrence, 13, 17, 31, 60, 90

Markov chain, 15, 16, 20, 33, 37, 52, 63, 94, 96,
111, 128
multiset, 20

optimal stopping, 107

PARI/GP, 32, 33, 49, 53, 117

random walk, 90
recursion, 13, 28, 31, 32, 37, 58, 60

stars-and-bars method, 34

Taylor series, 66

Yahtzee, 9, 93, 94

137