# Finding average number of rolls for recursive rolls on success

If there is more appropriate terminology to better phrase my question, please edit.

Imagine I have a 3 sided die: two faces marked 0, one face marked 2

Whenever a two is rolled, two more rolls are to occur. How do I determine the average number of rolls that will occur?

I tried figuring this out based on an explanation of exploding dice (http://axiscity.hexamon.net/users/isomage/rpgmath/explode/) but I'm not sure I'm even headed in the right direction.

p(number of rolls)

p(1) = 1/3
p(3) = 1/3 * 2/3 * 2/3
p(5) = 1/3 * 1/3 * 2/3 * 2/3 * 2/3
p(7) = 1/3 * 1/3 * 1/3 * 2/3 * 2/3 * 2/3 * 2/3
p(n) = n+1/3^n


Solve for the sum of p(n) ???

Are those probabilities correct or do i have to include the alternate ordering (ex: p(5) = 1/3 * 2/3 * 1/3 * 2/3 * 2/3)

what about a 3 sided die: 0,1,2 where 1 = +1 roll and 2 = +2 rolls? what about a 20 sided die: 15 zero faces, 3 two faces, 1 three face, and 1 five face?

Curious why in the heck I care? In an effort to learn python i thought it'd be fun to generate a random dungeon. Now i'm curious about the probabilities of the random (or should I say psuedo-random) generation.

I tried digesting the question/answers linked below ... snow crash! If you do help me, please, please, feed me via spoon. I am a statistics baby.

How to easily determine the results distribution for multiple dice?

Help with probabilities on a game I am making

Now i'm going to read http://www.diku.dk/hjemmesider/ansatte/torbenm/Troll/RPGdice.pdf while I wait for enlightenment

Thanks in advance for said enlightenment.

• You could take a look at the first example of the wikipedia article: en.wikipedia.org/wiki/Geometric_series and see if it helps? The expected number of rolls is your $\sum_i i p(i)$ – Neil G Jun 19 '13 at 6:55
• This is not a simple problem because if you start with a 2, your next 2 rolls can be 2, 2, and then you're looking at the next 4 rolls, and so on. That, I think makes it not just a simple geometric series problem, but a variant of a branching process, and I think it's probably best solved with generating functions. See, for example, sec 3.7 here, but you can find a lot more on this approach. – Glen_b Jun 19 '13 at 11:48

The solution method is mentioned in the title: recursion.

The expected number of rolls $e$ is the sum of:

• $1$ for the first roll and

• The expected number of subsequent rolls if the first roll is a 2.

In the latter case, the expected number of subsequent rolls is $2e$ because the whole process is started over twice (independently). Because the latter case occurs with probability $1/3$, we obtain the recursive relationship

$$e = 1 + (1/3)\times (2e)$$

whose solution is $e=3$.

For the generalizations of this question, similar recursive equations will be obtained (although they might be a little more complicated) and are almost as easy to solve.

For the sceptical--and everybody should be when it comes to probability questions :-)--here's R code to simulate the experiment.

roll <- function() 1 + if (runif(1) < 1/3) roll() + roll() else 0

system.time(x <- replicate(10^6, roll())) # Do a million experiments
average <- sum(x) / length(x)
variance <- sum(x^2) / length(x) - average^2
se <- sqrt(variance / length(x))
c(average-3*se, average, average+3*se)


Sample output:

   user  system elapsed
14.82    0.04   14.86

[1] 2.994785 3.009526 3.024267


The simulation average is $3.01$, which is reasonably close to $3$. (I use three standard errors to assess the precision because the distribution is highly skewed: draw a histogram as hist(x) to see.)

• I tried to apply this method on my second scenario (1d3, sides 0,1,2) but I must be setting it up incorrectly. e = 1 + 1/3 * 1e + 1/3 * 2e which reduces to e = 1 + e which is putting me in jeopardy of breaking some mathematical laws. Anyone fix my blunder? – new Thrall Jun 20 '13 at 4:01
• You're actually getting the right answer! In your second scenario the expectation is infinite. Think about it: on average, each throw of the die is going to lead to (0 + 1 + 2)/3 = 1 more throws. You shouldn't expect this always to end. (It's a better model for population growth than it is for game play.) – whuber Jun 20 '13 at 13:49
• Thanks I see it now. It's actually more of a population I'm trying to model. Population of rooms and passages of dungeons. :) On a side note are you really only 13? – new Thrall Jun 20 '13 at 19:44

With @whuber's help, here is a slight variation on the conditioning argument. Take the die with 3 sides of 0, 0, and 2 and let $R$ be the number of rolls. With probability $2 \over 3$ the process ends in 1 step with a roll of 0. With probability $1 \over 3$, the process will have $1 + 2E[R]$ steps. So $$E[R]=1 \left({2 \over 3} \right)+ \left[1+2E[R] \right]\left({1 \over 3} \right).$$ Solving for $E[R]$ we get $$E[R] = 3.$$

• +1. But you sound a little uncertain :-). – whuber Jun 19 '13 at 13:52
• I am, as confirmed by your answer! – soakley Jun 19 '13 at 13:57