NOTES 131

100.10 Dice problems with generating function solutions

Introduction
Probability theory prescribes rules for computing likelihoods of
complicated events. Unfortunately, these rules often result in exact formulas
that are complicated beyond usefulness, like missing the forest for the trees.
One handy tool to deal with complicated probabilities is the so-called
generating function. Generating functions provide a bridge between the
discrete world of combinatorics and the continuous world of calculus. The
main idea is to convert a sequence of probabilities into a function (the
generating function) and then, using techniques from algebra or calculus, to
analyse the function. It turns out that the derivatives, singularities, etc., of
the generating function often give telling information about the
probabilities. The beauty of the method is that frequently only basic algebra
and calculus skills are needed to reveal fundamental characteristics,
including accurate estimates, of the underlying probabilities.
As an example of this method, we consider questions related to rolling
dice in the game of Monopoly. In this game players roll a pair of dice to
move a token around a game board. The most expensive property on the
board is Mayfair (in the UK, or Boardwalk in the USA, or countless others
in other countries), located thirty-nine sites from the start. Moving a token
around the board with random rolls of a pair of dice, what is the probability
of landing on Mayfair during the first circuit? In other words, what is the
probability of exactly obtaining a sum of thirty-nine with rolls of dice? A
closely related question deals with obtaining or exceeding a particular sum.
In Monopoly, players collect a salary of £200 each time they pass Go, which
is located forty spaces from the start. On average, how many rolls does it
take to pass Go? In other words, what is the expected number of rolls of dice
to obtain or exceed a sum of forty? Exact answers to these questions are
complicated. However, using generating functions, we shall see that it is
easy to obtain accurate estimates of these probabilities and expectations
using only basic methods from elementary algebra and calculus.

Preliminaries
Generating functions for dice games are usually rational functions
(ratios of polynomials). To deal with rational functions, only a handful of
skills are necessary. The first is polynomial arithmetic. The addition of
polynomials goes term by term so, for instance,
(4 + z2) + (8 − 8z + 2z2 − 2z3) + (2z − 4z2 + 2z3) = 12 − 6z − z2.
The multiplication of polynomials coincides with the so-called discrete
convolution of sequences: the coefficient of each term in the product is the
sum of the products of coefficients whose powers add up to the power of the
given term. For instance,
(1 − z)2 × (4 + z2) = 4 − 8z + 5z2 − 2z3 + z4.
132 THE MATHEMATICAL GAZETTE

Quotients of polynomials can be decomposed with partial fractions, one

term for each prime power factor of the denominator. For instance,
12 − 6z − z2 1 2 2z
= + + .
4 − 8z + 5z − 2z + z
2 3 4 (1 − z) 2 1 − z 4 + z2
Another tool for dealing with rational functions is the geometric series.
A geometric series with an initial term of 1 and ratio z with |z| < 1 has a
1
sum of 1 + z + z2 + z3 + … = . Likewise, a geometric series with
1 − z
an initial term of 1 and a ratio of 2 z with |z| < 2 has a sum of
1

z z2 z3 1
1 + + + + …= .
2 4 8 1 − 2z
1 z z2 z3
More generally, = 1 + + + + …. One easy-but-useful
1 − rz r r2 r3
observation about this geometric series is that if |r| > 1, then the
coefficients of the terms in this series go to zero exponentially fast. For
example, the rational function
4 − z 3 1
= −
2 − 3z + z2 1 − z 1 − 12 z
has the series expansion

∑ (3 − 2−n) zn,
n≥0
but the coefficients of this series approach 3 since 2−n goes to 0
exponentially fast. The main observation that we use in first-order
approximations here is the following. If a root of the denominator of a term
of the decomposition of a rational function in partial fractions is greater than
1 in absolute value, then we can ignore this term completely since, like 2−n
in the previous example, the coefficients go to 0 (see, for instance, Theorem
IV.9 of [1] for an exact expansion of rational functions).
1
A series related to the geometric series is . This series can be
(1 − z)2
thought of as either the square of the geometric series (with the product
following the discrete convolution) or as the derivative of the geometric
series. In any case, the coefficient of the zn term is n + 1, so that
1
(1 − z)2
= ∑ (n + 1) zn, for |z| < 1.
n≥0

Landing on Mayfair
Getting an exact expression for the probability of rolling dice and
obtaining a particular sum is a thorny problem. Exact expressions for this
probability exist, but they are so complicated that they cloud the big picture.
NOTES 133

However, with the aid of generating functions, it is easy to get accurate

approximations that clearly show the general nature of the solutions. We
consider two cases—rolling a single fair die or rolling a pair of fair dice. In
each case we compute the probability of obtaining a particular sum. For
instance, Mayfair is located on the thirty-ninth site from the start of the
board in Monopoly.
Let us start by computing probabilities of several events related to
repeated rolls of a single fair die. The probability of rolling value n is 16 if
1 ≤ n ≤ 6 and 0 otherwise. The generating function of this sequence is the
polynomial
Roll (z) = 1
6z + 16 z2 + 16 z3 + 16 z4 + 16 z5 + 16 z6.
The sum of the probabilities of all the individual values is one, so
1 − Roll (z)
Roll (1) = 1. Then, the quotient is a quintic polynomial
1 − z
6 5 4 3 2 1
+ z + z2 + z3 + z4 + z5,
6 6 6 6 6 6
which we denote by Q (z). Now the probability of getting a sum of n with
two rolls of a single die is a sum over the probabilities of obtaining a
particular value m on the first roll times the probability of obtaining the
difference n − m on the second. This sum exactly corresponds to
polynomial multiplication. So, the generating function of the sequence of
probabilities of getting particular sums with two rolls is (Roll (z))2.
Likewise, the generating function of the sequence of probabilities of getting
particular sums with r rolls is (Roll (z))r. Finally, the probability of obtaining
a particular value, regardless of the number of rolls, is just the sum of the
probabilities of obtaining that value over all numbers of rolls. So, the
generating function for the sequence of probabilities of obtaining a
particular sum of rolls with a single die is

(Sum of Rolls) (z) = ∑ (Roll (z))r .

r≥0
This is a geometric series of polynomials, which is
1
(Sum of Rolls) (z) = .
1 − Roll (z)
In order to find the probability of landing on Mayfair, all that is left to
do is to extract the coefficient of z39 in this generating function. It has a
partial fractions decomposition of the form
1
(Sum of Rolls) (z) =
(1 − z) Q (z)
?2
= + 7
,
1 − z Q (z)
where ? denotes a yet-to-be determined quartic polynomial. Granted, the
134 THE MATHEMATICAL GAZETTE

roots of the quintic Q (z) are difficult to obtain exactly, but they are easy to
approximate with the following proposition, which is a corollary of the so-
called Eneström-Kakeya theorem (see exercises 1 and 2 following theorem
(30,2) in [2]).

Proposition: All the roots of a polynomial a0 + a1z + … + anzn, whose

ak
coefficients are real and positive, lie in the annulus with radii min and
ak + 1
ak
max .
ak + 1

Proof: Consider a path in the complex plane consisting of the line segments
joining successively a0, a1z, … , anzn and suppose |
ak + 1zk + 1
ak zk |> 1 for each
k . Then the exterior angles at all vertices are congruent (to arg z) and the
path must spiral out. So, z cannot be a root. Therefore, if z is a root, this
ak ak
inequality must fail for some k , in which case |z| ≤ ≤ max .
ak + 1 ak + 1
ak
Similarly, min ≤ |z| for any root z.
ak + 1

In other words, to obtain a bound for the roots of a polynomial with

positive coefficients, just compute the ratios of consecutive coefficients and
take their maximum and minimum. Computing the ratios of consecutive
coefficients in Q (z) shows that its roots must be between 65 and 2 in absolute
value. This is excellent news since, according to the example in the
preliminaries, the coefficients of all the terms in the series expansion of the
quintic part go to zero exponentially fast, and hence the unknown numerator
in the partial fractions decomposition is irrelevant for a first-order
approximation. So, the probability of rolling a single die and landing on
Mayfair can be nicely approximated by the coefficient of z39 in the
7 / (1 − z) term of (Sum of Rolls) (z), which is just 7 . This result makes
2 2

intuitive sense since the probability coincides with the reciprocal of the
average value of a roll (which also coincides with Roll ′ (1)). The exact
636548506161891666510055438417
probability of landing on Mayfair is ,
2227915756473955677973140996096
which is less than 10−6 off the approximation.
Of course, most people play Monopoly with a pair of dice, rather than a
single die. This has a minimal effect on our calculations. Instead of the
generating function Roll (z) = 16 z + 16 z2 + 16 z3 + 16 z4 + 16 z5 + 16 z6 for a
single die, the generating function for a pair of dice is the same as the
generating function for the sum of two dice (Roll (z))2, as calculated above.
Therefore, the probability of landing on Mayfair when rolling a pair of dice
1
is the coefficient of z39 in . A partial fractions decomposition
1 − (Roll (z))2
NOTES 135

of this generating function has the form

1
? ?
7
+ + .
1 − z Q (z) 1 + Roll (z)
As before, the coefficients of the Q (z) term go to zero exponentially fast.
Likewise, by the proposition, the roots of 1 + Roll(z) must be greater than 1
in absolute value, so the coefficients of the last term go to zero
exponentially fast, as well. Therefore, an approximation of the probability of
rolling a pair of dice and landing on Mayfair is 17 , a difference that turns out
to be less than 10−4 off the exact value of
26513269387508292854930466283
.
185659646372829639831095083008

Passing Go
In the game of Monopoly, players collect a salary of £200 as they pass
Go, which is forty sites from the start. A similar problem is calculating the
expected number of rolls to pass Go and collect the salary. Let en denote the
expected number of rolls needed to land on or first pass the n th site on the
game board. This is equivalent to the expected number of rolls to obtain or
first exceed sum n. As a first guess, one would suspect en would be close to
n divided by the average value of a roll. The initial values are en = 0 for
n ≤ 0, and by taking conditions on the first roll

en = 1 + ∑ em P (rolling n − m) , for each n ≥ 1.

m<n

Let E1 (z) denote the generating function of this sequence ∑ enzn when
rolling a single die. The generating function equivalent of this recurrence
relation involves a geometric series with unit ratio and unit initial term, as
z
well as the discrete convolution. So, E1 (z) = + E1 (z) Roll (z) and it
1 − z
z
follows that E1 (z) = . Again, the generating
(1 − z) (1 − Roll (z))
function is rational, and it has a partial fractions decomposition of the form
2 4
?
E1 (z) = 7
+ 21
+ .
(1 − z)2 1 − z Q (z)
The expected number of rolls to pass Go is the coefficient of z40 in E1 (z). As
1
noted in the preliminaries, the coefficient of the n th term of is
(1 − z)2
1
n + 1, the coefficient of the n th term of is 1, and the coefficients of
1 − z
?
go to zero. Therefore, en ≈ 27 (n + 1) + 21 4
. In other words, the
Q (z)
expected number of rolls to reach sum n with a single die exceeds n divided
by the average roll by about 10 21 . For passing Go with n = 40, the
136 THE MATHEMATICAL GAZETTE
−6
approximation of 250 21 turns out to be within 10 of the exact expected
number of rolls.
If a player rolls a pair of dice, the generating function for the sequence
of expected number of rolls to pass a sum would be
z
E2 (z) = .
(1 − z) (1 − (Roll (z))2)
This has a partial fractions decomposition of the form
1 29
? ?
E2 (z) = 7
+ 84
+ + .
(1 − z)2 1 − z Q (z) 1 + Roll (z)
As before, we can ignore the terms with Q (z) and 1 + Roll (z) which go to
zero, and so the expected number of rolls to reach sum n with a pair of dice
is en ≈ 17 (n + 1) + 29 521
84 . This time, the approximation of 84 turns out to be
−4
within 10 of the exact expected number of rolls to pass Go with a pair of
dice.

Further problems
There are many variations of these dice problems. For an example of a
generalisation, you can show that if Roll (z) is the generating function for a
weighted die (as opposed to a fair die), then the probability of obtaining the
1
sum n is approximately . Actually, this approximation is a finite
Roll ′ (1)
version of a theorem of Erdös, Feller and Pollard; see [3]. Likewise, the
expected number of rolls needed to obtain or exceed sum n is approximately
n Roll ″ (1)
+ .
Roll ′ (1) 2 (Roll ′ (1))2
In truth, the collection of dice problems is seemingly endless. (For an
example of a large compilation with solutions, see [4].) Almost all of these
problems can be solved, almost mechanically, with generating functions. If
you find these generating functions intriguing, please read [5] and [6] for
wonderful accounts.

References
1. P. Flajolet and R. Sedgewick, Analytic combinatorics, Cambridge
University Press (2009).
2. M. Marden, Geometry of polynomials, Amer. Math. Soc. (1949).
3. P. Erdös, W. Feller and H. Pollard, A property of power series with
positive coefficients, Bull. of the Amer. Math. Soc., 55(2) (1949)
pp. 201-204.
4. Matthew M. Conroy, A collection of dice problems, available at:
[Link]