Probability of sum of N dice being above certain value X

Question

In Dnd, sometimes you have to roll n, m-sided dice (say 5, d20s) and have the sum be greater than or equal to a certain value, x (say 90).

This is easy for me to calculate by brute force, for most typical examples. I simply take the total number of possibilities that meet the criteria, and divide by the total number of possibilities, by running through each combination of dice rolls. My result for the above example is 3003 dice combinations that sum to > 90, out of 3200000 combinations in total p = 0.009384375 chance of getting 90 or over.

Is there a way (e.g. an equation) to reach this value directly?

Answer 1

Concerning a "closed" ( = finite summation) formula, start from $$ \eqalign{ & N_b (s - n,m - 1,n) = {\rm No}{\rm .}\,{\rm of}\,{\rm solutions}\,{\rm to}\;\left\{ \matrix{ {\rm 1} \le {\rm integer}\;x_{\,j} \le m \hfill \cr x_{\,1} + x_{\,2} + \; \cdots \; + x_{\,n} = s \hfill \cr} \right. = \cr & = {\rm No}{\rm .}\,{\rm of}\,{\rm solutions}\,{\rm to}\;\left\{ \matrix{ 0 \le {\rm integer}\;y_{\,j} \le m - 1 \hfill \cr y_{\,1} + y_{\,2} + \; \cdots \; + y_{\,n} = s - n \hfill \cr} \right. \cr} $$ where $N_b$ is given by $$ N_b (s,r,m)\quad \left| {\;0 \leqslant \text{integers }s,m,r} \right.\quad = \sum\limits_{\left( {0\, \leqslant } \right)\,\,k\,\,\left( { \leqslant \,\frac{s}{r+1}\, \leqslant \,m} \right)} {\left( { - 1} \right)^k \binom{m}{k} \binom { s + m - 1 - k\left( {r + 1} \right) } { s - k\left( {r + 1} \right)}\ } $$ as explained in this related post.

Then the number of ways to obtain a sum $x \le s$ is given by $$ \eqalign{ & M(x,m,n) = \sum\limits_{x\, \le \,s\,\left( { \le \,m\,n} \right)\,} {N_b (s - n,m - 1,n)} = \cr & = m^{\,n} - \sum\limits_{0\, \le \,s\, \le \,x - 1\,} {N_b (s - n,m - 1,n)} = \cr & = m^{\,n} - \sum\limits_{0\, \le \,s\, \le \,x - n - 1\,} {N_b (s,m - 1,n)} = \cr & = m^{\,n} - \sum\limits_{0\, \le \,s\, \le \,x - n - 1\,} {\sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( { \le \,{s \over m}\, \le \,n} \right)} {\left( { - 1} \right)^k \left( \matrix{ n \hfill \cr k \hfill \cr} \right)\left( \matrix{ s + n - 1 - k\,m \cr s - k\,m \cr} \right)} } = \cr & = m^{\,n} - \sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( { \le \,{s \over m}\, \le \,n} \right)} {\left( { - 1} \right)^k \left( \matrix{ n \hfill \cr k \hfill \cr} \right)\left( \matrix{ x - 1 - k\,m \cr x - n - 1 - k\,m \cr} \right)} \cr} $$

and in fact $M(90,20,5)=3003$.

Note that, as explained in the cited related post, the problem has the geometric equivalent of finding:
the number of integral points on the diagonal plane $y_1, \cdots, y_n=s-n$, intercepted by a $n$-D cube with side $[0,m-1]$.
The formula for $N_b$ corresponds to calculating the points on the whole plane ($k=0$) and subtracting those pertaining to the surrounding cubes.
The geometric analogy clearly shows that $N_b(nm-s,m,n)=N_b(s,m,n)$.

Answer 2

You could try to solve this using the Chebychev inequality. This should at least give you an estimate.

Answer 3

G Cab gave a good closed-form answer, and it may well be what you're looking for.

Another approach that works decently well -- particularly if the number of dice is large at all, or if you're looking for events that are closer to the mean results -- is to use a Central Limit Theorem approximation. Here's how that would play out for your example in the problem text:

First: we're going to use something continuous to approximate something discrete, so let's do it carefully. If $S$ is the sum, we want to know about $\mathbb P(S > 90) = \mathbb P (S \geq 91)$, so we'll split the difference and consider $S = 90.5$. (This is the so-called "continuity correction.")

Asking whether the sum of five dice will be at least $90.5$ is equivalent to asking whether the average of five dice will exceed $90.5/5 = 18.1$. For one single die, the expected die roll is $10.5$ and the standard deviation of the die roll is $\sqrt{133}/2$. If you average $n$ of these (independent) rolls together, the average will be an approximately normal random variable with mean $10.5$ and standard deviation $\sqrt{133}/(2 \sqrt n)$; in the case of $n = 5$, this is roughly $2.579$. The question then becomes: "How often does a normal random variable with those properties exceed $18.1$?" Use your favorite calculator, or a $Z$-score technique and a table of known values about the standard normal distribution, to get an answer of about $0.0016$.

Then, stop and appreciate the fact that our answer wasn't that great! It was off by a factor of almost 10. So, what happened? Well, two things: (1) the approximation would have worked better if we were using more dice, and (2) the approximation would have worked better if we were considering numbers closer to the expected average of $10.5$. For instance, let's redo the problem with asking about the sum of five dice being larger than $60$ (again, we'll use $60.5$): it can be shown (click the "at least" button on the link) that the true probability is about $0.2730$, and repeating the above procedure gives an answer of $0.2804$ as our approximation.

So, why is this worth doing? For five dice, maybe it's not. But for more dice, this gives a really efficient way of getting a good approximation (that, again, gets better and better the more dice you use) that can save you from some truly obnoxious combinatorics and enormous numbers. As another example of the value of this tactic: the true probability that the sum of $10$ dice exceeds $100$ is $0.5961$, and the aforementioned tactic gives an estimate of $0.5975$. This approach scales really well with the number of dice in a way that doing actual counting does not.

Answer 4

I found a simple answer based on a similar but different question:

Where $n$ = number of dice, $m$ = sides of dice, $x$ = target score,

$$ p = \frac{nm - x + n\choose n} {m^n} $$

But this answer only works when $(nm - x) < m$