World's Worst Boardgame

On YouTube, there is a description of a game called the World's Worst Boardgame. I will modify it slightly for this problem.

You have two six-sided dice; one red, and one blue.

What is the expected number of rolls needed in order to get a sequence of rolls where you have 102 rolls (not necessarily consecutive) where the red die is 6 since the last roll where neither die was a 6? (In other words, start with a count of zero; after each roll, add 1 to the count if the red die is 6, keep the count where it is if the red die is not 6 but the blue die is, and reset the count to zero if neither die is a 6 - what is the expected number of rolls needed to get the count to 102?)

For those interested, I think this is the YouTube link Don is referring to: http://www.youtube.com/watch?v=ySikH7EcVAQ

And I think this is the Board Game Geek page for this game: http://boardgamegeek.com/boardgame/99918/w-w-b

I'm guessing the expected number of rolls is a number that 100 digits long... or more!

for a target of N red sixes, I get that the expected number of rolls should be:
186/25 * (31/6)^(N-1) - 36/25

So for N = 102, expected number of rolls ~ 8.05*10^72

Quote: smileyfish

for a target of N red sixes, I get that the expected number of rolls should be:
186/25 * (31/6)^(N-1) - 36/25

So for N = 102, expected number of rolls ~ 8.05*10^72

Would you care enlightening me as to how you got this number?

Also, this board's editor has a superscript function, [ sup ]...[ /sup ] (but without the spaces), so 10^72 shows up as 10⁷².

Quote: EdCollins

For those interested, I think this is the YouTube link Don is referring to: http://www.youtube.com/watch?v=ySikH7EcVAQ

Yes, that's the game, and my request does not include how many additional rolls would be needed when both players end up on the same square and both have to start over.

Quote: ThatDonGuy

Would you care enlightening me as to how you got this number?

First, thanks for the tip about the super and subscripts.

Let S be a state variable representing how many red 6's we currently have in the streak, and E_S be the expected number of additional rolls needed to reach the final target. E_N = 0, since you've already reached the target. The answer you want is E₀.

What can happen if we are currently at S (S>0) and roll:
1/6 that we roll a red 6 and go to S+1
5/6*1/6 = 5/36 that we roll a red 1-5 and a blue 6 and stay at S
5/6*5/6 = 25/36 that we don't roll any 6 and go back to state 0

So: E_S = 1/6 * E_S+1 + 5/36 * E_S + 25/36 * E₀ + 1, where the +1 is the roll we just made
E_S = 6/31 * E_S+1 + 25/31 * E₀ + 36/31

Start from S = N-1 and work backwards until you get to S = 1
i.e. E_N-1 = 25/31 * E₀ + 36/31, since E_N = 0

E_N-2 = 25/31 * E₀ + 1/6 * E_N-1 + 36/31, and substitute in the equation we just got for E_N-1
E_N-2 = 25/31 * (6+31)/31 * E₀ + 36/31 * (6+31)/31

As you work backwards, you'll notice two things are happening. One, you'll get equations for E_S in only a single variable E₀. Two, each equation follows a pattern, namely for m >= 2:

E_N-m = 25/31 * (6^m-1+6^m-2*31+6^m-3*31²+...+31^m-1)/31^m-1 * E₀ + 36/31 * (6^m-1+6^m-2*31+6^m-3*31²+...+31^m)/31^m-1

This can be simplified by using the summation of series formula, i.e.
(6^m-1+6^m-2*31+6^m-3*31²+...+31^m-1)/31^m-1 = [1 - (6/31)^m] / [1 - 6/31]

Thus, E_N-m = 25/31 * [1 - (6/31)^m] / [1 - 6/31] * E₀ + 36/31 * [1 - (6/31)^m] / [1 - 6/31]

Setting m = N - 1 gives us E₁, i.e.
E₁ = 25/31 * [1 - (6/31)^N-1] / [1 - 6/31] * E₀ + 36/31 * [1 - (6/31)^N-1] / [1 - 6/31]

Things are a little different if we are at S = 0 and roll, since staying where we are and going back to 0 amount to the same outcome. The probabilities are:
1/6 that we roll a red 6 and go to S = 1
5/6 that we roll a red 1-5 and stay at S = 0

E₀ = 1/6 * E₁ + 5/6 * E₀ + 1
E₀ = E₁ + 6

Substituting in the equation for E₁ and some algebra gives you the answer I provided, namely
E₀ = 186/25 * (31/6)^N-1 - 36/25

Quote: smileyfish

10^72

Just for comparison: This is almost the number of atoms (i.e. a significant amount) in the whole universe.

Here's a generic solution:
Let P be the probability of moving ahead one space, and Q be the probability of staying in place (which, of course, means (1-Q-P) is the probability of going back to space 0)
E_k-1 = 1 + Q E_k-1 + (1-Q-P) E₀ + P E_k
(1-Q) E_k-1 = 1 + (1-Q-P) E₀ + P E_k
E_k-1 = 1 / (1-Q) + ((1-Q) / (1-Q) - P / (1-Q)) E₀ + P / (1-Q) * E_k
Let X = P / (1-Q):
E_k-1 = X / P + (1 - X) E₀ + X E_k

Let N be the number of the last space (i.e. the number of spaces minus 1)
E[N] = 0
E_N-k = (X + X² + X³ + ... + X^k) / P + (1 - X^k) E₀
Proof by induction:
If k = 1: E_N-1 = X / P + (1 - X) E₀ + X E_N = X / P + (1 - X) E₀, so it is true
Assume it is true for k:
E_N-(k+1) = E_(N-k)-1 = X / P + (1 - X) E₀ + X E_N-k
= X / P + (1 - X) E₀ + X * ((X + X² + X³ + ... + X^k) / P + (1 - X^k) E₀)
= X / P + (1 - X) E₀ + (X² + X³ + ... + X^k+1) / P + (X - X^k+1) E₀)
= X / P + (X² + X³ + ... + X^k+1) / P + (1 - X + X - X^k+1) E₀
= (X + X² + X³ + ... + X^k+1) / P + (1 - X^k+1) E₀
Therefore, if it is true for k, then it is true for k+1

E₀ = E_N-N
= (X + X² + X³ + ... + X^N) / P + (1 - X^N) E₀
= X (1 + X + X² + X³ + ... + X^N-1) / P + (1 - X^N) E₀
= X (1 - X^N) / (P (1 - X)) + (1 - X^N) E₀
(1 - (1 - X^N)) E₀ = X (1 - X^N) / (P (1 - X))
E₀ = X (1 - X^N) / (P (1 - X) X^N)
E₀ = ((1 - Q)^N - P^N) / (P^N (1 - Q - P))

In the initial problem, P = 1/6, Q = 5/36, and N = 101:
E₀ = ((31/36)¹⁰¹ - (1/6)¹⁰¹) / ((1/6)¹⁰¹ x 25/36) = 1.558 x 10⁷²