Dice

If I roll two dice and I take the sum, I'm more likely to roll seven than to roll two. But is it possible that I could weight a pair of dice so that all possible sums are equally probable?

If you like mathematical puzzles, I strongly encourage you to stop here and play with this problem for a while. It's a fun one, and there are all sorts of generalizations. What if I use more than two dice? What if I use dice with four sides, or with twenty sides? This isn't an original problem, by the way. I learned about from Bill Gasarch and Clyde Kruskal when I was an undergraduate (in 1998, I think); they have a paper on it.

I was reminded of this problem yesterday afternoon when one of my office mates asked me about a problem with the eigensystem for a nearly-Toeplitz matrix. It doesn't sound closely related, but it is. Both problems can be reduced to problems with polynomials, and to multiplying polynomials.

How would I compute the probability distribution associated with a sum of two dice rolls, anyhow? The answer is not hard:

P(die1+die2 = i) = sum_{j+k = i} P(die1 = j) P(die2 = k).

Now, here's a remarkable thing. Suppose that I have two polynomials

g(x) = g₀ + g₁x + ... + g_n xⁿ
h(x) = h₀ + h₁x + ... + h_n xⁿ.

What are the coefficients of f(x) = g(x) h(x)? The answer looks suspiciously familiar:

f_i = sum_{j+k = i} g_j h_k.

The formulae for computing the distribution of a sum of random variables or for computing the coefficients of the product of polynomials are the same! This formula defines a convolution product of two sequences. Convolutions show up in the theory of polynomials, in statistics, in Fourier analysis, in image processing... all over the place.

Back to dice. Because distributions of sums of random variables and coefficients of products of polynomials can be computed in the same way, it makes sense to identify discrete distributions with polynomials. If X is a random variable which can take on values 0, ..., n, the generating polynomial for the corresponding distribution is a polynomial g(x) of degree n such that

g_i = P(X=i).

As we have seen, if X and Y are random variables with associated generating polynomials g(x) and h(x), then X+Y has a generating polynomial g(x) h(x). It's worth noting here that not every polynomial is a generating polynomial: the coefficients of a generating polynomial have to be positive and sum, or else they don't correspond to a probability distribution.

With the connection to generating polynomials in hand, we can rephrase the original problem. The generating polynomial for a uniform distribution over 0, ..., n is f(x) = c_n/(n+1), where c_n is

c_n(x) = 1 + x + x² + ... + xⁿ.

The polynomial c_n(x) is called a cyclotomic polynomial. It can also be written as:

c_n(x) = (xⁿ⁺¹-1)/(x-1).

This latter form shows that cyclotomic polynomials are easy to factor: the roots of c_n are the (n+1)st roots of unity, except for the root at +1.

A uniform distribution for the roll of two six-sided dice is a cyclotomic polynomial of degree 10 (in my world, by the way, dice are labeled 0-5 rather than 1-6). This polynomial has five pairs of complex-conjugate roots. If I have two weighted dice whose sum is uniformly distributed, I need those dice to have corresponding generating polynomials with products proportional to the cyclotomic polynomial; that means that the generating polynomial for the first die must have roots at some subset of the roots of c₁₀, and the generating polynomial for the second die must have roots at the remaining roots of c₁₀. Furthermore, since I need my generating polynomials to be real, I can't split up a complex conjugate pair of roots: if the generating polynomial for a die has a root at z, it must also have a root at conj(z).

I have ten roots; I have to split them into two groups of five; and the roots come into pairs that I can't split up. This is clearly an impossible task, and so we have the answer to the question: there is no way to weight two ordinary dice so that the sum is uniformly distributed.