2
$\begingroup$

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?

  • 0
    Mildly related: http://math.stackexchange.com/q/117022/64602012-03-07

6 Answers 6

2

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$.

  • 0
    @Brian Again, the comments are too short.2012-03-08
1

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).

1

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!

1

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} $

Ref: Max Alekseyev answer to a math-overflow question

0

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.

--to be added--

0

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