Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is there a way to determine the chance of rolling at least $k$ on $n$ dice with $s_1,\ldots,s_n$ sides?

Example: What is the chance of rolling a sum of at least 13 on 3 dice with 6, 8, and 10 sides?

I know that the chance of rolling exactly $k$ on $n$ dice with $s$ sides is

$$F_{s,n}(k)=\sum_{i=1}^{k-n+1} F_{s,1}(i)F_{s,n-1}(k-1)$$

where $F_{s,1}(k)=\frac{1}{s}$ for all $1\leq k\leq s$ and $0$ otherwise (see this Wikipedia page), but I am not sure how to either generalize it for differently sided dice or combine it for different values of $s$.

Note: This will be done programmatically so efficiency is very important to me.

share|improve this question

2 Answers 2

up vote 2 down vote accepted

Recursively, $\displaystyle F_{s_1,\cdots,s_n}(k)=\sum_iF_{s_1}(i)F_{s_2,\cdots,s_n}(k-i)$ with $\displaystyle F_{s}(k)=1/s$ if $1\le k\le s$ and $0$ otherwise. The sum can be over every $i$ in $\mathbb{Z}$.


Another approach One can also compute the generating function of the coefficients $F_{s_1,\cdots,s_n}(k)$, defined as $$ G_{s_1,\cdots,s_n}(x)=\sum_kF_{s_1,\cdots,s_n}(k)x^k. $$ The generating function for a dice with $s$ sides being $(x+x^2+\cdots+x^s)/s$, $$ (s_1\cdots s_n)G_{s_1,\cdots,s_n}(x)=\prod_{i=1}^n(x+x^2+\cdots+x^{s_i}). $$ Thus $(s_1\cdots s_n)F_{s_1,\cdots,s_n}(k)$ is the coefficient of $x^k$ in $$ \prod_{i=1}^n(x+x^2+\cdots+x^{s_i})=\frac{x^n}{(1-x)^n}\prod_{i=1}^n(1-x^{s_i}). $$ Likewise, the sum over every $k\le K$ of $(s_1\cdots s_n)F_{s_1,\cdots,s_n}(k)$ is the coefficient of $x^K$ in $$ \frac1{1-x}\frac{x^n}{(1-x)^n}\prod_{i=1}^n(1-x^{s_i}), $$ which is also the coefficient of $x^{K-n}$ in $$ \frac1{(1-x)^{n+1}}\prod_{i=1}^n(1-x^{s_i}). $$

Numerical application For $K=12$, $s_1=6$, $s_2=8$ and $s_3=10$, $n=3$ hence one is interested in linear integer combinations of $6$, $8$ and $10$ at most equal to $K-n=9$, that is, in the coefficient $c_{9}$ of $x^{9}$ in $$ \frac1{(1-x)^4}(1-x^6-x^8). $$ The coefficient of $x^k$ in $1/(1-x)^4$ is $a_k=(k+3)(k+2)(k+1)/6$ hence $$ c_9=a_9-a_3-a_1, $$ and the chance of a sum at least $13$ is $$ 1-\frac{c_9}{6\cdot8\cdot10}=\frac{71}{120}. $$ Verification The chances that a dice with $s$ faces produces $s+1-k$ or $k$ are equal hence the probabilities of the sums $s_1+\cdots+s_n+n-k$ and $k$ are equal. In our case, $27-k$ and $k$ are equiprobable for each $k$ between $1$ and $26$ hence a result $\le13$ and a result $\ge14$ are equiprobable. A result $\ge13$ has probability $1/2$ plus the probability of a result exactly equal to $13$ hence one should check that a result equal to $13$ has probability $11/120$, or equivalently, that there exists $44$ ways to choose three positive integers less than $6$, $8$ and $10$ respectively such that their sum is $13$ (and this is true!).

share|improve this answer
    
Just to clarify - this algorithm is for the probability of getting exactly k on s1,...,sn dice. At least k is trivial from here though. Thanks! –  dpatchery May 3 '11 at 17:43

You can generalise your probability of rolling exactly $k$ from the first $n$ dice as

$$F_n(k) = \frac{1}{s_n} \sum_{i=k-s_n}^{k-1} F_{n-1}(i),$$

starting at $F_0(k)=0$ for all non-zero $k$, and $F_0(0)=1$. There are efficient ways of calculating this through addition and subtraction of running totals.

Your probability is

$$ \sum_{j \ge k} F_{n}(j)$$

or

$$ 1- \sum_{j < k} F_{n}(j)$$

and you can use whichever is quicker to calculate.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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