2

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.

Community
  • 1
new Thrall
  • 123
  • 2
  • You could take a look at the first example of the wikipedia article: http://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 06: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](https://en.wikipedia.org/wiki/Branching_process), and I think it's probably best solved with [generating functions](https://en.wikipedia.org/wiki/Probability-generating_function). See, for example, sec 3.7 [here](http://www.am.qub.ac.uk/users/g.gribakin/sor/Chap3.pdf), but you can find a lot more on this approach. – Glen_b Jun 19 '13 at 11:48

2 Answers2

2

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

whuber
  • 281,159
  • 54
  • 637
  • 1,101
  • 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 04: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
1

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

soakley
  • 4,341
  • 3
  • 16
  • 27