4
$\begingroup$

To clear up potential misunderstandings and make it easier to understand, I'll use this notation:
Instead of writing "Rolling $n$ $m$-sided dice", I'll shorten it to "Rolling ndm". (n is the amount of dice and m is the amount of sides on the dice) (This is the notation used in D&D if you know what that is)

Im asking how to calculate the probability of getting at least a sum of s when rolling ndm. Finding the amount of possible outcomes is fairly easy, its just $m^n$. So f.ex for 3d6, the amount of possible outcomes would be $6^3 = 216$. I've looked at similar asked questions before and found a very useful, related formula for finding the amount of ways to get the sum s when rolling ndm:

Let $k = \lfloor \frac {s-n}m \rfloor$
$$\sum_\limits{i=0}^{k} (-1)^i{n\choose i}{s-1 - im\choose n-1}$$ However, this only gives us the probability of getting exactly s, not at least s.

$\endgroup$
  • 1
    $\begingroup$ sum over $s$ to get what you want $\endgroup$ – Masacroso Jan 25 at 22:15
  • $\begingroup$ @Masacroso Then you can use the Hockey stick identity to eliminate the summation. Much nicer solution. $\endgroup$ – Mike Earnest Jan 25 at 22:55
  • $\begingroup$ @Masacroso: do you remember, we already discussed about the writing of this formula: if you don't get rid of the sum bounds it is complicated to sum over $s$ $\endgroup$ – G Cab Jan 25 at 23:02
3
$\begingroup$

Consider that $$ \eqalign{ & {\rm No}{\rm .}\,{\rm of}\,{\rm solutions}\,{\rm to}\;\left\{ \matrix{ {\rm 1} \le {\rm integer}\;y_{\,j} \le m \hfill \cr y_{\,1} + y_{\,2} + \; \cdots \; + y_{\,n} = s \hfill \cr} \right.\quad \Rightarrow \cr & \Rightarrow \quad {\rm No}{\rm .}\,{\rm of}\,{\rm solutions}\,{\rm to}\;\left\{ \matrix{ {\rm 0} \le {\rm integer}\;x_{\,j} \le m - 1 \hfill \cr x_{\,1} + x_{\,2} + \; \cdots \; + x_{\,n} = s - n \hfill \cr} \right. = \cr & = N_{\,b} (s - n,m - 1,n) \cr} $$ where $N_b$ is given by $$ \eqalign{ & N(sum = s,m,n) = N_b (s - n,m - 1,n)\quad = \cr & = \sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( { \le \,{{s - n} \over m}\, \le \,n} \right)} { \left( { - 1} \right)^k \binom{n}{k}\binom{s-1-k\,m}{s-n-k\,m} } \cr} $$ as widely explained in this related post.

Note that the second binomial looks equivalent to that in the formula you cited.
But written in this way it has the advantage to implicitly contain the bounds of the sum, which then can be omitted (indicated in brackets).
This has the advantage of simplifying the the algebraic manipulations, and in fact for the cumulative Number we easily get $$ \eqalign{ & N(sum \le S,m,n) = \cr & = \sum\limits_{0\, \le \,s\, \le \,S} {\sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( { \le \,{{s - n} \over m}\, \le \,n} \right)} { \left( { - 1} \right)^k \binom{n}{k}\binom{s-1-k\,m}{s-n-k\,m} } } = \cr & = \sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( {\, \le \,n} \right)} {\sum\limits_{\left({0\, \le}\right) \,s\, \left({\,\le \,S}\right)} { \left( { - 1} \right)^k \binom{n}{k} \binom{S-s}{S-s} \binom{s-1-k\,m}{s-n-k\,m} } } = \cr & = \sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( {\, \le \,n} \right)} { \left( { - 1} \right)^k \binom{n}{k} \binom{S-k\,m}{S-n-k\,m}} \cr} $$

by using the "double convolution" formula for binomials.

$\endgroup$
2
$\begingroup$

It is a little easier to answer the probability of rolling less than $s$. This is $m^{-n}$ times the number of solutions to $$ d_1+d_2+\dots+d_n+e=s,\\ 1\le d_i\le m,\\ 1\le e $$ which is the coefficient of $x^s$ in $$ m^{-n}(x+x^2+\dots+x^m)^n\cdot (x+x^2+x^3+\dots)=m^{-n}x^{n+1}(1-x^m)^n(1-x)^{-n-1}. $$ Therefore, $$ \boxed{P(\text{roll less than s})=m^{-n}\sum_{i=0}^{\left\lfloor\frac{s-1-n}{m}\right\rfloor}(-1)^i\binom{n}{i}\binom{s-1-im}{n}} $$ For example, with two six sided dice, you get $$ \frac1{36}\Bigg[\binom{s-1}{2}-2\binom{s-7}{2}+\binom{s-13}{2}\Bigg] $$ which checks out.

$\endgroup$
  • $\begingroup$ So this would be equivalent to finding the probability for getting at most s then? $\endgroup$ – Nils Phillip Talgö Jan 25 at 22:47
  • $\begingroup$ @NilsPhillipTalgö Unless I misunderstand you, no, the probability of rolling less than $s$ (my answer) is not equal to that of rolling at most $s$. $\endgroup$ – Mike Earnest Jan 25 at 22:52
0
$\begingroup$

While thinking about this problem I finally saw the simplicity to it. Firstly, what means "getting at least s", well, it simply means getting any sum bigger than or equal to s. So to get the desired result, we need to "sum over s" as mentioned by @Masacroso. Actually finding this formula wasn't that obvious, but I think I worked it out: $$\frac{\sum_\limits{j=s}^{n*m} \sum_\limits{i=0}^{\lfloor \frac {j-n}m \rfloor} (-1)^i{n\choose i}{s-1 - im\choose n-1}}{m^n}$$ To explain why this should work: The formula I cited in the question gave us the amount of ways to get s as a sum when rolling ndm, but since the amount of ways to get at least $s$ is just all the cases where the sum is ≥ $s$, we can just add the amount of ways of getting $s$, then $s+1$, then $s+2$ and so on up to the maximum possible roll, namely $n*m$. (Then dividing by the amount of possible outcomes, namely $m^n$) This should give us the desired probability from $0$ to $1$.

Similarly, the probability of rolling at most $s$ is the exact same formula, but going from $n$ to $s$ instead of $s$ to $n*m$. (This is because the lowest possible roll is always going to be equal to the amount of dice rolled. (Assuming you roll a 1 on every individual roll)) $$\frac{\sum_\limits{j=n}^{s} \sum_\limits{i=0}^{\lfloor \frac {j-n}m \rfloor} (-1)^i{n\choose i}{s-1 - im\choose n-1}}{m^n}$$

$\endgroup$

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.