# Probability of rolling $n$ successes on an open-ended/exploding dice roll

I'm trying to compute the probability of achieving a certain number of successes when rolling a die pool for both open-ended/exploding and closed tests. Success is defined as a roll above a certain (variable) threshold. If a roll is open-ended, any die which rolls the maximum value triggers an additional die to be rolled. This is for a role-playing game (Burning Wheel Gold).

Assume the use of a $n$-sided die. Additionally, we assume $d$ to be the number of dice, $r$ to be the required number of successes, and $c$ to be the minimum value accepted as a success. I'm breaking the question down into two blocks: one for open-ended rolls, and one for closed rolls.

Closed roll: For closed rolls, we can define a probability recurrence as follows:

$$Pr\left[r,d\right] = \begin{cases} \\1-\frac{c}{n}:Pr\left[d-1,r\right]\\\frac{c}{n}:Pr\left[d-1,r-1\right] \end{cases}$$

With probability $\frac{c}{n}$, a success will be met. However, I'm not sure how to solve this recurrence relation for any number of dice/required successes. There's probably an easier way to do this, but I haven't done much discrete probability.

Edit: It looks like a binomial probability distribution works for this part of the problem. This comes in the form of:

$${{d}\choose{r}}\left(\frac{c}{n}\right)^{r}\left(1-\frac{c}{n}\right)^{d-r}$$

Open ended roll: For open-ended rolls, we can find the equivalent number of rolled dice. This is going to be equal to:

$$d+\sum_{j=1}^{\infty}\left(\frac{d}{6^{j}} \right)=\frac{6d}{5}$$

This implies that, given a number of dice $n$, rolling open-ended results in approximately $\frac{6}{5}n$ dice rolled. If we had an easy way to solve the above for any number of dice $n$, it would be easy: we could just input the non-integer value $n$ and get our result. However, since the above is defined with a recurrence relation is a binomial distribution, and thus uses combinations, it won't work for a non-integer number. Thus, we can define a probability recurrence relation as follows:

$$Pr\left[ r,d\right] = \begin{cases} \\1-\frac{c}{n}:Pr\left[d-1,r\right]\\\frac{c-1}{n}:Pr\left[d-1,r-1\right]\\\frac{1}{n}:Pr\left[d,r-1\right] \end{cases}$$

The probability of no significant result is $1-\frac{c}{n}$, the probability of a regular success is $\frac{c-1}{n}$, and the probability of an 'exploding' or open-ended result is $\frac{1}{n}$. However, I don't know how to solve this recurrence relation, either.

So these are my questions:

• For closed rolls, how do I find the probability of $n$ successes? I've looked at existing probability tables (PDF), but they don't actually contain the math for their generation, and it's non-intuitive to discern from the table. Edit: See above; the binomial formula applies.
• For open rolls, can the closed roll formula be applied to a non-integer number $\frac{6n}{5}$? Edit: No. See above; the binomial formula uses combinations, thus requires integer numbers.
• So, how do I solve the closed roll recurrence relation and/or find the open probability?
-
It looks to me like closed roll is binomial: The probability of at least $r$ successes among $n$ independent trials, each having probability $p$? – Hagen von Eitzen May 14 '13 at 20:28
Note that you can get displayed equations by using double dollar signs instead of single dollar signs. They get centred and look less squashed, especially when containing fractions and sums with limits. – joriki May 14 '13 at 20:57
Possible duplicate of Exploding dice in a dice pool – con-f-use Feb 12 at 14:37

These can be solved at the same time, the closed roll is just a special case of the open ended.

Let

$$d = \text{Number of sides on each die}$$ $$n = \text{Number of dice rolled}$$ $$s = \text{Score required for success}$$ $$m = \text{number of successes required}$$

Also, let

$$s = n^k+r$$

where $$k\in 0,1,2,\dots$$ $$r\in 1,2,\dots,d$$

And, let

\begin{align} p_o &= \text{chance of getting open ended}\\ &= \begin{cases} \frac{1}{d}&,\text{if roll is open}\\ 0&,\text{otherwise}\\ \end{cases} \end{align}

So, for 1 die, we have a geometric distribution to get $k$ open ended results followed by a single roll to get $r$ (note that this is not exactly a geometric distribution since we need $k$ failures with $q=1-p_0$ followed by 1 success with a different probability). Also we will require $x^0=1$.

$$p_1=\left(p_0\right)^{k}\left(\frac{d-r+1}{d}\right)$$

To get $m$ success from $n$ dice, we have a binomial distribution as you noticed so

\begin{align} p_{m,n}&=\sum_{i=m}^n\binom{n}{i}p_1^i\left(1-p_1\right)^{n-i}\\ \end{align}

Some examples:

• $d=6$, $n=1$, $s=4$, $m=1$ & open ended; so $k=0$, $r=4$

\begin{align} p_0=\frac{1}{6}\\ \end{align}

\begin{align} p_1&=\left(\frac{1}{6}\right)^{0}\left(\frac{6-4+1}{6}\right)\\ &=1\left(\frac{3}{6}\right)\\ &=1\times\frac{1}{2}\\ &=\frac{1}{2}\\ \end{align}

\begin{align} p_{1,1}&=\sum_{i=1}^1\binom{1}{i}p_1^i\left(1-p_1\right)^{1-i}\\ &=\binom{1}{1}\left(\frac{1}{2}\right)^{1}\left(1-\frac{1}{2}\right)^{1-1}\\ &=1\times\frac{1}{2}\times{1}\\ &=\frac{1}{2}\\ \end{align}

• $d=6$, $n=1$, $s=10$, $m=1$ & open ended; so $k=1$, $r=4$

\begin{align} p_0=\frac{1}{6}\\ \end{align}

\begin{align} p_1&=\left(\frac{1}{6}\right)^{1}\left(\frac{6-4+1}{6}\right)\\ &=\frac{1}{6}\times\frac{3}{6}\\ &=\frac{1}{12}\\ \end{align}

\begin{align} p_{1,1}&=\sum_{i=1}^1\binom{1}{i}p_1^i\left(1-p_1\right)^{1-i}\\ &=\binom{1}{1}\left(\frac{1}{12}\right)^{1}\left(1-\frac{1}{12}\right)^{1-1}\\ &=1\times\frac{1}{12}\times{1}\\ &=\frac{1}{12}\\ \end{align}

• $d=6$, $n=3$, $s=4$, $m=2$ & closed; so $k=0$, $r=4$

\begin{align} p_0=0\\ \end{align}

\begin{align} p_1&=\left(0\right)^{0}\left(\frac{6-4+1}{6}\right)\\ &=1\left(\frac{3}{6}\right)\\ &=\frac{1}{2}\\ \end{align}

\begin{align} p_{3,2}&=\sum_{i=2}^3\binom{1}{i}p_1^i\left(1-p_1\right)^{1-i}\\ &=\binom{3}{2}\left(\frac{1}{2}\right)^{2}\left(1-\frac{1}{2}\right)^{3-2}+\binom{3}{3}\left(\frac{1}{2}\right)^{3}\left(1-\frac{1}{2}\right)^{3-3}\\ &=3\times\frac{1}{4}\times\frac{1}{2}+1\times\frac{1}{8}\times1\\ &=\frac{4}{8}\\ &=\frac{1}{2}\\ \end{align}

• $d=6$, $n=3$, $s=10$, $m=2$ & open ended; so $k=1$, $r=4$

\begin{align} p_0=\frac{1}{6}\\ \end{align}

\begin{align} p_1&=\left(\frac{1}{6}\right)^{1}\left(\frac{6-4+1}{6}\right)\\ &=\left(\frac{1}{6}\right)\left(\frac{3}{6}\right)\\ &=\frac{1}{12}\\ \end{align}

\begin{align} p_{3,2}&=\sum_{i=2}^3\binom{1}{i}p_1^i\left(1-p_1\right)^{1-i}\\ &=\binom{3}{2}\left(\frac{1}{12}\right)^{2}\left(1-\frac{1}{12}\right)^{3-2}+\binom{3}{3}\left(\frac{1}{12}\right)^{3}\left(1-\frac{1}{12}\right)^{3-3}\\ &=3\times\frac{1}{144}\times\frac{11}{12}+1\times\frac{1}{1,728}\times1\\ &=\frac{34}{1,728}\\ &=\frac{17}{864}\\ &\approx0.02\\ \end{align}

-
I'm not sure what you're setting $r$ and $k$ to; could you please clarify? (I'm generally confused by this; it really looks like a bunch of formulas) – Emrakul May 15 '13 at 3:56
The formula is given above - essentially k is how many open ended rolls you need and r is the result you need once you get those open ended rolls. – Dale M May 15 '13 at 3:58
But what if no open-ended rolls are actually needed? This is probabalistic - if I roll 6 dice and need 5 successes, I don't actually need any open ended rolls. – Emrakul May 15 '13 at 3:59
Then $k=0$, $r=\text{whatever result} \le d \text{ you need}$. – Dale M May 15 '13 at 4:04
Remember, $k$ & $r$ are only used to work out the chance of succeeding with 1 die. The next part of the calculation deals with how many successes you require. – Dale M May 15 '13 at 4:05