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:
h(x) = h0 + h1x + ... + hn xn.
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
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) = cn/(n+1), where cn is
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 c10, and the generating polynomial for the second die must have roots at the remaining roots of c10. 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.