Author |
Topic: All 6 Numbers On a Die. (Read 670 times) |
|
luke's new shoes
Guest
|
Question: on average, how many times do u need to roll a dice before getting all six numbers at least once?
|
| « Last Edit: Oct 23rd, 2003, 8:04pm by Icarus » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
 |
Re: NEW PUZZLE: dice average
« Reply #1 on: Nov 14th, 2002, 4:00am » |
 Quote  Modify
|
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..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: NEW PUZZLE: dice average
« Reply #2 on: Nov 14th, 2002, 11:07am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: NEW PUZZLE: dice average
« Reply #3 on: Nov 14th, 2002, 11:31am » |
Quote Modify
|
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)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: NEW PUZZLE: dice average
« Reply #4 on: Nov 14th, 2002, 11:55am » |
Quote Modify
|
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]
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.
|
| « Last Edit: Nov 14th, 2002, 11:57am by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Garzahd
Junior Member
Gender:
Posts: 130
|
|
Re: NEW PUZZLE: dice average
« Reply #5 on: Nov 14th, 2002, 12:10pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: NEW PUZZLE: dice average
« Reply #6 on: Nov 14th, 2002, 12:37pm » |
Quote Modify
|
So in general for an n-sided die A(n) := sum(n/(n + 1 - i), i, 1, n)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: NEW PUZZLE: dice average
« Reply #7 on: May 5th, 2003, 9:19am » |
Quote Modify
|
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
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: NEW PUZZLE: dice average
« Reply #9 on: May 8th, 2003, 9:03pm » |
Quote Modify
|
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
|
| « Last Edit: May 8th, 2003, 11:04pm by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
|
Re: NEW PUZZLE: dice average
« Reply #10 on: May 8th, 2003, 10:27pm » |
Quote Modify
|
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.
|
|
IP Logged |
Nick's Mathematical Puzzles
|
|
|
Margit Schubert-While
Guest
|
|
Re: All 6 Numbers On a Die.
« Reply #11 on: Dec 18th, 2003, 10:22am » |
Quote Modify
 Remove
|
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 ?
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
   
Gender:
Posts: 2873
|
|
Re: All 6 Numbers On a Die.
« Reply #12 on: Dec 20th, 2003, 5:04am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print