1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ nice idea (+1), but same comment as to the answer above. $\endgroup$ – G Cab Nov 30 '18 at 15:40
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Your "asymptotics" analysis is appreciable (+1). But in fact, the difficulty to apply it is to estimate in advance the error we are going to have. The matter is that actually we have the sum of variables uniformly distributed over a given range, which is limited, while the gaussian is unlimited and not enough "flat" in the central part to approximate the "box" function of the uniform. $\endgroup$ – G Cab Nov 30 '18 at 15:38
  • 1
    $\begingroup$ @GCab Right. As I mentioned, this approach works very well for the "bulk" of the distribution, but will consistently have a high relative error near the tails of the distribution. Notably, the absolute error of these kinds of estimates will still tend to $0$ as the number of dice increases, but that's mostly because both the true values and estimates will both tend to $0$. And estimating the error remains a challenge, yes. $\endgroup$ – Aaron Montgomery Nov 30 '18 at 16:07
0
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ apart from the denominator, which is the total n. of throws, for the numerator consider that $N_b(s,m,r)=N_b(mr-s,m,r)$ ($N_b$ being the number given in my answer). So your answer, missing a $-1$, corresponds to the term with $k=0$ of $N_b$. In the other post I give as reference it is explained the geometric analogy with determining the number of points on the diagonal plane of a hyper-cube ... Pls. read that and you will understand that your answer is in general wrong. $\endgroup$ – G Cab Nov 30 '18 at 14:37
  • $\begingroup$ Sorry your answer is too far above my ability level, I don't know where to start :( - other than that my formula produces the same as my brute force calculations. e.g. for n = 5, m = 20, x = 90, nominator produces 3003. If you care to explain it would be much appreciated! $\endgroup$ – james_alvarez Nov 30 '18 at 15:09
  • $\begingroup$ I forgot to mention that the reference you provided didn't seem to work... $\endgroup$ – james_alvarez Nov 30 '18 at 15:16
  • $\begingroup$ yes, sorry, I did not properly link to it: corrected. $\endgroup$ – G Cab Nov 30 '18 at 15:26
  • $\begingroup$ More testing reveals that indeed this simple formula above is indeed wrong, so I will have to trust yours as I can't figure out how to actually calculate it given the three parameters. I do think the above is correct for when (nm-x) < m. But you mention a missing -1? Where should that go? It seems ok when I'm comparing the result with my counting method in python. $\endgroup$ – james_alvarez Nov 30 '18 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.