wu :: forums (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
riddles >> medium >> All 6 Numbers On a Die.
(Message started by: luke's new shoes on Nov 13th, 2002, 4:47pm)

Title: All 6 Numbers On a Die.
Post by luke's new shoes on Nov 13th, 2002, 4:47pm
Question: on average, how many times do u need to roll a dice before getting all six numbers at least once?

Title: Re: NEW PUZZLE: dice average
Post by towr on Nov 14th, 2002, 4:00am
I've run a simulation that suggests it's about 14.65 times..

Of course it would be much more worthwile if I could calculate it exactly.. Which is what I'll ponder about now..

Title: Re: NEW PUZZLE: dice average
Post by S. Owen on Nov 14th, 2002, 11:07am
Here's how I think about it, and I believe it's right, though I welcome a more insightful answer.

How many times do you expect you'll have to roll the die until you have seen 1 distinct number? (Clearly, 1). From there, how many times do you expect you'll have to roll the die until you have seen 2 distinct numbers in all? Keep going and you'll arrive at an answer which is more or less confirmed by your simulation.

Title: Re: NEW PUZZLE: dice average
Post by towr on Nov 14th, 2002, 11:31am
I tried to do that in several ways, and failed miserable everytime..
I do now know the answer is exactly 14.7 (Instead of a chance model I used a finite-state model, giving a nice converging number in short time)

Title: Re: NEW PUZZLE: dice average
Post by James Fingas on Nov 14th, 2002, 11:55am
My simulation indicates that it's exactly 14.7.

I found out a solution, but it's not particularly simple:

ways to get all 6 faces in x rolls= 6x-6*5x+15*4x-20*3x+15*2x-6

This was essentially brute-forced from a spreadsheet, but it corresponds to considering all possibilities, then subtracting ways to get five faces or fewer, but adding back ways to get 4 faces or fewer that were subtracted twice, then subtracting off ways to get 3 faces or fewer that were added back, etc...

I find the CDF (total probability up to roll x) using this formula, and then find the PDF (probability that you got the sixth face on roll x), multiply by x and sum from 1 to infinity, getting this formula:

sumx=1..inf x*[6/5*(5/6)x - 15/2*(4/6)x + 20*(3/6)x - 30*(2/6)x + 30*(1/6)x]
:P
The sum is equal to 14.7, but there is probably a way to simplify it, or maybe a way to think about the problem in a simpler way.

Title: Re: NEW PUZZLE: dice average
Post by Garzahd on Nov 14th, 2002, 12:10pm
Simple expectation analysis will get it for you.

What's the expected number of rolls until you get the nth number (En)? With probability (7-n)/6, you get the roll you need, so it's one. Otherwise, with probability (n-1)/6, it's one plus En because you have to reroll.

En = 1*(7-n)/6 + (1 + En) * (n-1)/6
En = 6/(7-n)

So your total is 6/6 + 6/5 + 6/4 + 6/3 + 6/2 + 6/1 = 14.7.

Title: Re: NEW PUZZLE: dice average
Post by towr on Nov 14th, 2002, 12:37pm
So in general for an n-sided die A(n) := sum(n/(n + 1 - i), i, 1, n)

Title: Re: NEW PUZZLE: dice average
Post by THUDandBLUNDER on May 5th, 2003, 9:19am

Quote:
So in general for an n-sided die A(n) := sum(n/(n + 1 - i), i, 1, n)
                                                                                                                                                                                                                                             n
Simpler, albeit identical, is n*SIGMA (1/r)
                                                                                                                                                                                                                                           r=1

Title: Re: NEW PUZZLE: dice average
Post by NickH on May 8th, 2003, 12:41pm
See the solution on my site, which is that of Garzahd...

http://www.qbyte.org/puzzles/p025s.html

Title: Re: NEW PUZZLE: dice average
Post by THUDandBLUNDER on May 8th, 2003, 9:03pm

Quote:
"For large n, this is asymptotically equal to n (ln n + Y), where Y  0.5772 is the Euler-Mascheroni Constant."

Nick, on Mathworld they say the nth harmonic number is given asymptotically by Hn ~ ln n + Y + 1/2n

I don't understand why they have the 1/2n term. Do you?
I guess it must be more accurate when n is not so large.

See Equation 11 at http://mathworld.wolfram.com/HarmonicNumber.html

Title: Re: NEW PUZZLE: dice average
Post by NickH on May 8th, 2003, 10:27pm
I've seen both forms, and I think they're both asymptotic.  However, I've added the 1/2n into the equation on my site, as the harmonic term is being multiplied by n.

So now 6(ln 6 + Y + 1/12) iis accurate to one decimal place.

Title: Re: All 6 Numbers On a Die.
Post by Margit Schubert-While on Dec 18th, 2003, 10:22am
Follow-up :
On average, how many times do you need to roll 2 dice  before getting all possible totals from 2 to 12 at least once ?

Title: Re: All 6 Numbers On a Die.
Post by rmsgrey on Dec 20th, 2003, 5:04am
I first met the original problem as the "cereal freebie" problem - the number of packets of cereal (or Happy Meals if you prefer MacDonalds) you expect to need to buy in order to get all the toys at least once. If you play trading card games, there's the equivalent problem of how many packs you expect to need to get a full set, the answer to which explains why they're called trading card games... It's also relevant to the 100 prisoners problem (see Hard forum) as a lower bound on the expected release time.

The variation is a little nastier because you no longer have the uniform distribution - I'll have to think about it.



Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board