guido111
guido111
  • Threads: 10
  • Posts: 707
Joined: Sep 16, 2010
February 16th, 2012 at 10:30:41 AM permalink
The coupon collector's problem is well known in math circles.
The Wizard did the math on "What is the expected number of rolls of two dice for every total from 2 to 12 to occur at least once?"
That column can be found here:
Ask the Wizard #278

I hope I worded my question to be understandable.
added: (Yes, Rolling two six-sided dice)
The set we are looking for is {1,2,3,4,5,6} at least 1 of each.

So the first roll of 2 dice is 5,2
Now we wait for the 1,3,4,6 to show.

Second roll is a 4,4

Now we are waiting for the 1,3 and 6 to show.

It is the 2 dice that has my head in a spin.
I do not know where to begin.

(Get this: This question was asked by my 7 y/o grandson!
I think he gambles with his school teachers at recess.)
added: he knows the Penney Ante game rules for coin tossing!
He always makes me choose my pattern first. Kids are too smart these days.
7craps
7craps
  • Threads: 18
  • Posts: 1977
Joined: Jan 23, 2010
February 16th, 2012 at 11:58:56 AM permalink
For one die to see all 6 faces can be done easily.
1 roll +
1/(5/6) = 1.2 +
1/(4/6) = 1.5 +
1/(3/6) = 2 +
1/(2/6) = 3 +
1/(1/6) = 6
=14.7
Dare we just divide by 2?
7.35
Cant be that easy.

The first roll can produce 2 numbers with p = 30/36
and 1 number with 6/36
Back to the drawing board
winsome johnny (not Win some johnny)
Jufo81
Jufo81
  • Threads: 6
  • Posts: 344
Joined: May 23, 2010
February 17th, 2012 at 7:33:10 AM permalink
Quote: 7craps

For one die to see all 6 faces can be done easily.
1 roll +
1/(5/6) = 1.2 +
1/(4/6) = 1.5 +
1/(3/6) = 2 +
1/(2/6) = 3 +
1/(1/6) = 6
=14.7
Dare we just divide by 2?
7.35
Cant be that easy.



I think your result 7.35 is close. The only thing needed is to account for possible odd number of rolls of single die to get all numbers (rolling two dice just means that total number of single die rolls is always even).

N = Number of single die rolls to get all numbers 1-6.

There is no mathematical difference with rolling one die N times compared to rolling two dice N/2 times, since all the outcomes are independent from each other. So as long N is even, outcomes from N rolls of single die are indistinguishable from N/2 rolls of two dice.

The only difference between the two would come from when N is odd. Let's say that you roll all numbers 1-6 in 13 rolls of single die. With two dice this would mean 7 rolls (and not 13/2 = 6.5) and the outcome of the last die would be actually irrelevant (the first of the two dice would give you the last missing number).

If we assume that there is an equal chance of N to be even or odd, then it means that there is 50% chance that one extra roll is needed (in the odd case) to account for rolling two dice at a time, and the answer would be:

7.35 + 0.5 = 7.85 expected rolls.

However, I am not sure whether the odds for N to be even/odd is in fact 50/50 so a further calculation is needed: Rolling single die, what is the probability that collecting all numbers 1-6 ends up with even/odd number of rolls?
7craps
7craps
  • Threads: 18
  • Posts: 1977
Joined: Jan 23, 2010
February 17th, 2012 at 7:55:52 AM permalink
I have not had the time to look back at this. Maybe I will now, but I kind of understand the extra 0.5 roll being added.
If you add that to the 14.7 = 15.2 then divide by 2.
=7.6
That number is very close to my sim results of 7.599786667
part of my data
rollrelativecumulative
1  
2  
30.0158733330.015873333
40.0983033330.114176667
50.1581766670.272353333
60.1658733330.438226667
70.1439733330.5822
80.1148366670.697036667
90.0871233330.78416
100.0643033330.848463333
110.0450866670.89355
120.032040.92559
130.0224433330.948033333
140.015450.963483333
150.011140.974623333
160.0078066670.98243
170.0053733330.987803333
180.0036633330.991466667
190.0026133330.99408
200.001810.99589
winsome johnny (not Win some johnny)
Jufo81
Jufo81
  • Threads: 6
  • Posts: 344
Joined: May 23, 2010
February 17th, 2012 at 8:11:00 AM permalink
Quote: 7craps

I have not had the time to look back at this. Maybe I will now, but I kind of understand the extra 0.5 roll being added.
If you add that to the 14.7 = 15.2 then divide by 2.
=7.6
That number is very close to my sim results of 7.599786667
part of my data



Ah yes, I think I made a mistake in my post. You need to add that 0.5 correction term to single die rolls and then divide by two for two dice, so your 7.6 would be correct. The fact that you got 7.599786667 from the sim suggests that this is correct. Could you also run another sim for the odds of total number of single die rolls to be odd / even?
7craps
7craps
  • Threads: 18
  • Posts: 1977
Joined: Jan 23, 2010
February 20th, 2012 at 12:07:20 AM permalink
Quote: Jufo81

Ah yes, I think I made a mistake in my post. You need to add that 0.5 correction term to single die rolls and then divide by two for two dice, so your 7.6 would be correct.
The fact that you got 7.599786667 from the sim suggests that this is correct. Could you also run another sim for the odds of total number of single die rolls to be odd / even?

I had a chance to get back to this problem tonight.
(I have been fighting off a real nasty cold this week and hope it is out of here.)

I started to set this up as a Markov Chain solution, thinking that "each face" one is waiting for would be a separate state with transition probabilities.
Before I finished my matrix, Matthew M. Conroy over at www.matthewconroy.com emailed me his solution.
He has an excellent paper called "A Collection of Dice Problems" that I have learned a lot from and Matt wanted to add it to his collection.
Well, I had to look at his solution, since my matrix is not yet completed.

Of course, he did an excellent job.
Link to the pdf and his solution. It is Question #3. Solution starts on page 9.
A Collection of Dice Problems

Just in case someone else is solving this.

Jufo81, I was really thinking that our solution was too easy and my simulations that I ran, sorry I have not ran any that you have asked, kept me right at that
7.599786667 value.

His exact answer is 70219/9240
about 7.59945887445....

With the matrix, one can also raise it to any power for each roll to get the probability distribution and Matt also included that up to 24 rolls.

Is there another solution?
Yes, I am sure there is. Maybe that will come later.

here is a part of Matt's solution
winsome johnny (not Win some johnny)
Jufo81
Jufo81
  • Threads: 6
  • Posts: 344
Joined: May 23, 2010
February 20th, 2012 at 6:04:16 AM permalink
Quote: 7craps


Jufo81, I was really thinking that our solution was too easy and my simulations that I ran, sorry I have not ran any that you have asked, kept me right at that
7.599786667 value.

His exact answer is 70219/9240
about 7.59945887445....

With the matrix, one can also raise it to any power for each roll to get the probability distribution and Matt also included that up to 24 rolls.

Is there another solution?
Yes, I am sure there is. Maybe that will come later.



Hi, yes Matt's Markov Chain solution is the accurate and proper one, no question about that.

Anyway, I still think that the "easier" solution I proposed is correct one as well. But it requires solving the probability that the number of single die rolls to yield all numbers 1...6 is odd. If we use following notation:

N = Number of single die rolls to get all numbers 1...6
E[...] = Expected value of [...]

I propose that the following equation:

E[Number of two dice rolls to get all numbers 1...6] = ( E[N] + Prob(N is odd) ) / 2

will give the exact same solution.

You already calculated above that E[N] = 14.7, so it's only a matter of calculating: Prob(N is odd). However, calculating this might lead to the same kind of Markov Chain as in Matt's solution.
  • Jump to: