Dice Probability Problem

Here is a problem I recently found in a book on Probability:

When 'x' fair dice (which have six faces each) are rolled, derive the formula for the probability that the sum of the scores on the dice is a certain number 'n'.

Would anyone have an elegant approach to deriving this formula?

There is no simple closed formula, though there are generating functions and recursive functions.

For example it is the coefficient of $y^n$ in the expansion of $$\left(\frac{y+y^2+y^3+y^4+y^5+y^6}{6}\right)^x = \left(\frac{y(1-y^6)}{6(1-y)}\right)^x.$$

It is also $p(x,n)$ where $$p(a,b)=\frac{1}{6}\sum_{c=1}^6 p(a-1,b-c)$$ starting from $p(0,b)=0$ except that $p(0,0)=1$.

• Henry, how do you prove that it is the coefficient of y^n in that expansion? – Brian Mar 7 '12 at 23:03
• @Brian: By induction These are the average of the coefficients of $y^{n-1}$, $y^{n-2}$, $y^{n-3}$, $y^{n-4}$, $y^{n-5}$ and $y^{n-6}$ when you raise to the $x-1$th power. Eventually you get back to the $0$th power, which is just $1$, as the probability of rolling $0$ with $0$ dice is $1$. – Henry Mar 7 '12 at 23:11
• Just look at the exponents -- they behave just as the sums of the dice. If you multiply two results you get all the pairs like $y^3y^5$, $y^4y^4$ and so on, and pairs with exponents that sum to the same number are grouped, exactly as the sums of dice. In fact generating functions do the very same calculations (there's no magic there), they just tend to be easier to deal with in cases of much more complex formulas. – dtldarek Mar 7 '12 at 23:12
• @dtldarek: dtldarek, surely there must be a formal mathematical way to show that? – Brian Mar 7 '12 at 23:47
• @Brian What I said can be reformulated into a rigorous proof. Just take two such polynomials with the assumption that the coefficient for $y^n$ is the probability of getting sum $n$, then multiply those two and show that resulting polynomial have exactly same property. Using this and induction you will get Henry's result. – dtldarek Mar 8 '12 at 9:04

Let $X$ be a representation sum of some dice and $Y$ sum of some other dice. Let $W_X(z) = \sum_k P(X = k) z^k$, i.e. $P(X = k) = k!\frac{d^kW}{dz^k}\!(0)$. Simiralry for $Y$ and $W_Y$. I will show that $W_{X+Y} = W_X \cdot W_Y$. \begin{align*} W_X\cdot W_Y &= \left(\sum_k P(X = k)z^k\right)\left(\sum_m P(Y = m)z^m\right) \\ &= \sum_k \left(P(X = k)z^k\sum_m P(Y = m)z^m\right) \\ &= \sum_k \sum_m P(X = k)z^k P(Y = m)z^m \\ &= \sum_k \sum_m P(X = k)P(Y = m)z^{k+m} \\ &= \sum_n \sum_m P(X = n-m)P(Y = m)z^{n} \hspace{50pt} & (1)\\ &= \sum_n \left(\sum_m P(X = n-m)P(Y = m)\right)z^n \\ &= \sum_n \left(\sum_m P(X = n-m\ \ \text{and}\ \ Y = m)\right)z^n & (2)\\ &= \sum_n \left(\sum_m P(X + Y = n\ \ \text{and}\ \ Y = m)\right)z^n & (3)\\ &= \sum_n P(X + Y = n)z^n &(4)\\ &= W_{X+Y}\\ \end{align*} Here in (1) we have $n = k+m$, in (2) I am using that $X$ and $Y$ use different dice, therefore $X$ and $Y$ are independent, in (3) we have $Y = m$ therefore I can add this to both sides of $X = n-m$, and finally in (4) I need that events $Y = m$ are non-overlapping for different $m$s and in total they give all the possible results (i.e. $Y \neq \frac{1}{2}$, etc.). Reordering of the sums is allowed because they are finite (for infinite series it would be possible to, but only because they are all non-negative and converge for all $|z| < 1$).

Please ask, if you have further questions (also there maybe some typos despite the fact I checked twice).

Let $X_i$ be the result of $i$-th die. Thesis: $$P\left(\sum_{i=1}^{N} X_i = k\right) \text{ is equal to coefficient in z^k of } \left(\frac{z^1+\ldots +z^6}{6}\right)^N. \quad\quad\quad(1)$$

Proof by induction:

Base of induction: $P(X_1 = k) = \frac{1}{6}$ for $1 \leq k \leq 6$ and $0$ otherwise.

Indeed this is the case for $\left(\frac{z^1+\ldots+z^6}{6}\right)^1$.

Assumption of induction: thesis (1) holds for $1, 2, \ldots, N$.

Hypothesis of induction: thesis (1) holds for $N+1$.

Step of induction:

We know that $$\left(\frac{z^1+\ldots+z^6}{6}\right)^{N+1} = \left(\frac{z^1+\ldots+z^6}{6}\right)^N\left(\frac{z^1+\ldots+z^6}{6}\right) \quad\quad\quad(2)$$ By the assumption we know that first part of right-hand side represents the probability distribution of sum of $N$ dice and the second part represents single die. Using the notation I've used in another answer we can observe that right-hand side can be written as $W_{X_1 + \ldots + X_N} \cdot W_{X_{N+1}}$ and that equals $W_{X_1 + \ldots + X_N + X_{N+1}}$ by the formulas I have derived there. But definition of this polynomial is $$W_{X_1 + \ldots + X_N + X_{N+1}}(z) = \sum_k P(X_1 + \ldots + X_N + X_{N+1} = k) z^k$$

so the coefficient at $z^k$ is $P(X_1 + \ldots + X_N + X_{N+1} = k)$ which is precisely the induction hypothesis and that completes the induction step.

By the method of induction that completes the proof of (1) for all $N \geq 1$.

Afterword: It is important that different dice get different $X$-es, because this way you say that those results are independent. Having just one $X$ would make possible to derive that you have only 6 possible answers: $N, 2N, 3N, \ldots, 6N$, as it would mean just taking the very same result of the single $die$ $N$ times. (Notation $W_{X+X}$ in one of the previous comments is just wrong and shouldn't have happened. That ought to be $W_{X_1 + X_2}$ naturally.)

In conclusion, I think I overdid it a little, but I guess more explicit is in this case better than less explicit, please bear it. Also there may be some typos there, so watch out!

We can solve this using generating functions, the answer is coefficient of $x^n$ $$\left(\frac 1 6 \right)^x \times (z+z^2+\dots+z^6)^x = \left(\frac 1 6 \right)^x \times \left(z\frac{1-z^6}{1-z}\right)^x$$ $$= \left(\frac 1 6 \right)^x \times z^x (1-z^6)^x(1-z)^{-x}$$

We can derive the explicit formula for this expansion as $$\left(\frac 1 6 \right )^x \times \sum \limits_{i=0}^{\min(x,\lfloor (n-x)/6\rfloor)} (-1)^{n+i} \binom{x}{i} \binom{-x}{n-x-6i}$$ $$= \left(\frac 1 6 \right)^x \times \sum_{i=0}^{\min(x,\lfloor (n-x)/6\rfloor)} (-1)^i \binom{x}{i} \binom{n-6i-1}{x-1}$$

Define the random variable $X_i$ to be uniformly distributed on $\{1,2,3,4,5,6\}$. This random variable models the outcome on the $i^{th}$ die. So, you are looking for,

$$\Bbb P(X_1+\cdots+X_x=n)$$

You know the number of solutions for the diophantine $\cdot$ in $\Bbb P(\cdot)$ and the probability for each of the solution.

Let's start with the simple case of a single two sided dice, and let $p(x)$ be our desired probability.

Clearly $p(1)=1/2$. How can we get a 2? We roll a 2 the first time (with probability 1/2) or we can roll or roll a 1 and then a 1, that is $$p(2)=\frac{1}{2}+p(1)\cdot \frac{1}{2}$$

In general a little thought gives that for $x>2$ $$p(x)=\frac{1}{2}p(x-1)+\frac{1}{2}p(x-2)$$

Let's try solve this recurrence relation. The characteristic polynomial is $$x^2-\frac{1}{2}x-\frac{1}{2}$$

with roots $r_1=1,r_2=-1/2$.

Then

\begin{align} p(x)&=k_1 r_1^x + k_2 r_2^x \\ & = k_1+k_2\left(-\frac{1}{2}\right)^x \end{align} where we can determine the constants $k_1,k_2$ from our knowledge of $p(1)$ and $p(2)$.

For a single six-sided dice a similar argument gives that for $x>6$

$$p(x) = \frac{1}{6}\sum_{i=1}^6 p(x-i)$$

Adding in another dice gets you to the recurrence given by Henry