How to compute the distribution of sums when rolling 'N' dice with 'M' faces?

Question

I stumbled upon the following problem:

Given 'n' dice with 'm' faces with values 1 to m and a number 'x' what is the probability that the sum of the numbers on the 'm' dice is greater than or equal to 'x'? That is $m \le x \le n.m$ find $P(sum \ge x)$

Now, this 'almost approximates' a normal distribution. I'm sure it won't be a straight triangle but would have some sort of 'bell'-ish shape. Now the point is, "how" can I compute this without necessarily enumerating everything? Is there a generating function like thing I can use. Probably a recursive definition? Not sure if that's the way to go but I'm just at my wit's end. I was thinking of visualizing this distribution but that would still require to know the individual probabilities $P(sum = 6),...,P(sum = m.n)$

I've mostly encountered problems with 2-3 dice and it is somewhat easy to do or compute the sums. But how can one generalize this like in this problem?

Answer 1

For many purposes, you can use a normal approximation with continuity correction.

You can also use recursion for the probability that the total equals $y$, and add these from $y=x+1$ through $y=mn$.

There is also an exact formula for the probability that the sum equals $y$ involving a single summation, which gives you a double sum for the probability the sum is greater than $x$. Be careful that in the linked answer, the "dice" had values from $0$ through $m$ instead of from $1$ through $m$. You can convert these by subtracting $1$ from each die and $n$ from the total, and using $m-1$ in place of $m$. Also, as whuber pointed out, there can be numerical instability if you are not careful in the order in which you add the terms of an alternating sum.

Answer 2

Why don't you compute $P(sum > x)$ using a recursive formula with respect to the number of dices? Something like $P(sum_n > x) = P(sum_{n - 1} + outcome_n > x) = \sum_{1}^{m}p_i1_{1 \le i \le m}P(sum_{n-1}>x-i)$.

Answer 3

Outside general formulas or recursions (already looking like they're being covered) --

If you just want probabilities for some specific cases (I frequently do calculations for a dozen or so dice, not always with the same number of sides), it's trivial to do such calculations in things like Excel or R - they can generally be set up in a matter of moments in Excel.

For moderately large numbers of dice ($n$) where the above approach starts to become impractical, I sometimes have used numeric convolution (taking the $n^\rm{th}$ power of the Fourier transform).

For even fairly moderate $n$, the normal approximation works quite well unless you go some way into the tail. In very large samples, the normal approximation does really well, except in the most extreme part of the tail. (I generally use a continuity correction with the normal approximation.)