ThatDonGuy
ThatDonGuy
  • Threads: 118
  • Posts: 6405
Joined: Jun 22, 2011
November 9th, 2013 at 1:20:36 PM permalink
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?)
EdCollins
EdCollins
  • Threads: 20
  • Posts: 1739
Joined: Oct 21, 2011
November 9th, 2013 at 2:16:01 PM permalink
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!
smileyfish
smileyfish
  • Threads: 0
  • Posts: 10
Joined: Oct 31, 2013
November 9th, 2013 at 2:23:27 PM permalink
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
ThatDonGuy
ThatDonGuy
  • Threads: 118
  • Posts: 6405
Joined: Jun 22, 2011
November 9th, 2013 at 3:50:47 PM permalink
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 1072.


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.
smileyfish
smileyfish
  • Threads: 0
  • Posts: 10
Joined: Oct 31, 2013
November 9th, 2013 at 6:25:32 PM permalink
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 ES be the expected number of additional rolls needed to reach the final target. EN = 0, since you've already reached the target. The answer you want is E0.

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: ES = 1/6 * ES+1 + 5/36 * ES + 25/36 * E0 + 1, where the +1 is the roll we just made
ES = 6/31 * ES+1 + 25/31 * E0 + 36/31

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

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

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

EN-m = 25/31 * (6m-1+6m-2*31+6m-3*312+...+31m-1)/31m-1 * E0 + 36/31 * (6m-1+6m-2*31+6m-3*312+...+31m)/31m-1

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

Thus, EN-m = 25/31 * [1 - (6/31)m] / [1 - 6/31] * E0 + 36/31 * [1 - (6/31)m] / [1 - 6/31]

Setting m = N - 1 gives us E1, i.e.
E1 = 25/31 * [1 - (6/31)N-1] / [1 - 6/31] * E0 + 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

E0 = 1/6 * E1 + 5/6 * E0 + 1
E0 = E1 + 6

Substituting in the equation for E1 and some algebra gives you the answer I provided, namely
E0 = 186/25 * (31/6)N-1 - 36/25
MangoJ
MangoJ
  • Threads: 10
  • Posts: 905
Joined: Mar 12, 2011
November 10th, 2013 at 2:41:41 PM permalink
Quote: smileyfish

10^72



Just for comparison: This is almost the number of atoms (i.e. a significant amount) in the whole universe.
ThatDonGuy
ThatDonGuy
  • Threads: 118
  • Posts: 6405
Joined: Jun 22, 2011
November 14th, 2013 at 4:58:18 PM permalink
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)
Ek-1 = 1 + Q Ek-1 + (1-Q-P) E0 + P Ek
(1-Q) Ek-1 = 1 + (1-Q-P) E0 + P Ek
Ek-1 = 1 / (1-Q) + ((1-Q) / (1-Q) - P / (1-Q)) E0 + P / (1-Q) * Ek
Let X = P / (1-Q):
Ek-1 = X / P + (1 - X) E0 + X Ek

Let N be the number of the last space (i.e. the number of spaces minus 1)
E[N] = 0
EN-k = (X + X2 + X3 + ... + Xk) / P + (1 - Xk) E0
Proof by induction:
If k = 1: EN-1 = X / P + (1 - X) E0 + X EN = X / P + (1 - X) E0, so it is true
Assume it is true for k:
EN-(k+1) = E(N-k)-1 = X / P + (1 - X) E0 + X EN-k
= X / P + (1 - X) E0 + X * ((X + X2 + X3 + ... + Xk) / P + (1 - Xk) E0)
= X / P + (1 - X) E0 + (X2 + X3 + ... + Xk+1) / P + (X - Xk+1) E0)
= X / P + (X2 + X3 + ... + Xk+1) / P + (1 - X + X - Xk+1) E0
= (X + X2 + X3 + ... + Xk+1) / P + (1 - Xk+1) E0
Therefore, if it is true for k, then it is true for k+1

E0 = EN-N
= (X + X2 + X3 + ... + XN) / P + (1 - XN) E0
= X (1 + X + X2 + X3 + ... + XN-1) / P + (1 - XN) E0
= X (1 - XN) / (P (1 - X)) + (1 - XN) E0
(1 - (1 - XN)) E0 = X (1 - XN) / (P (1 - X))
E0 = X (1 - XN) / (P (1 - X) XN)
E0 = ((1 - Q)N - PN) / (PN (1 - Q - P))

In the initial problem, P = 1/6, Q = 5/36, and N = 101:
E0 = ((31/36)101 - (1/6)101) / ((1/6)101 x 25/36) = 1.558 x 1072
  • Jump to: