Die rolling probability question?

Question

Every day a man must roll a die again and again until he has rolled at least one of each of the numbers 1-6. This means it may take him just 6 rolls to accomplish this...or it may take him 20, 200, or an infinite number of rolls! For example if he rolls 2, then 6, 4, 2, 1, 6, 5, 4, 3 it would have taken him 9 rolls to get all six numbers.

If this man performs this task each day, what is the median number of rolls you expect this man to have to make before getting all six numbers. "Median" is probably not the right term (I'm curious to know what is.). What I'm looking for is a number of rolls where 50% of the days the man will require fewer rolls than this number, and 50% of the days he'll roll more than this number. My guess is it's somewhere around 11 rolls. Could be higher though.

I'd love to know exactly how this is solved because I have a number of questions where a task is performed numerous times and i need to know the "median" number of times expected.

Answer 1

this is a version of the coupon collector's problem.

http://en.wikipedia.org/wiki/Coupon_collector's_problem



the *expected* value is easy to compute: 6/6 + 6/5 + 6/4 +.... +6/1 = 14.7,

but you are asking for the median, which will be lower because the distribution will be skewed to the right.



using inclusion-exclusion, C(6,1)*5^n standing for ways of missing at least 1# & so on,



Pr = (6^n - C(6,1)*5^n + C(6,2)*4^n - C(6,3)*3^n + .... +6 )/6^n



= sum ( C(6,k)*(-1)^k*(6-k)^n /6^n) for k = 0 to 5



the table below gives the probabilities of getting all 6 #s for n = 10 to 15

n . . P(n)

10 27.18%

11 35.62%

12 43.78%

13 51.39% <<<<<<< ans

14 58.28%

15 64.42%



ps:

----

an interesting simulation package, which among other similar problems, simulates "collecting" all 6 #s on a dice can be seen at

http://www-stat.stanford.edu/~susan/surprise/Collector.html

Answer 2

P[ no 6 is rolled i n n throws ] = (5/6)^n



P[ no 1 is rolled OR no 2 is rolled OR ... OR no 6 is rolled in n throws ]



= 6 P[ no 6 is rolled ] - 15 P[ no 5 and no 6 is rolled ] + C(6,3) P[ no 4 and no 5 and no 6 is rolled]

- C(6,4) P[no 3 ... ] + 6 P[no 2 nor 3 nor ... nor 6 is rolled] - P[no number is rolled]



= 6 (5/6)^n - 15 (4/6)^n + 20 (3/6)^n - 15 (2/6)^n + 6 (1/6)^n - 0 (if n > 0) = f(n)



Now we search for n so that f(n) = 0.5



f(n) = 1, for n<6 like should (logical)

f(10) = 0.7..... too big

f(15) = too small

so n has to be between 10 and 15

we try n=12

f(12) = 0.5..... too big

f(13) = 0.486 very close to 0.5, 50%



So this number of days is 13 (actually a bit smaller than 13).

Answer 3

What we have here is a negative binomial distribution (number of trials (tosses) required) to get 6 successes. success 1 = roll number 1

success 2 = roll number 2

success 3 = roll number 3

success 4 = roll number 4

success 5 = roll number 5

success 6 = roll number 6



The expected value (number of trials) for a negative binomial distribution is r (1-p)/p

p= 1/6 (probability of each success) -- if the die is fair

r = 6 ( we want numbers 1 through 6 rolled)

r(1-p)/p = (6) (1-1/6) / (1/6) = 30



If this man performs this task each day, what is the mean number of rolls you expect this man to have to make before getting all six numbers.



Theoretically, it could take infinite number of trials before he could roll all of the 6 numbers but the expected (mean) number of rolls is 30.

Answer 4

I don't know the right distribution for n, but it a multinomial distribution for the numbers on the dice.



So I wrote a small program to add up all the possible probabilities, and generated the expected value of n. It turned out to be very close to 26.



For more information on the multinomial distribution, check this wikipedia page



http://en.wikipedia.org/wiki/Multinomial_distribution

Answer 5

median is the correct term, yet I do not know how to solve the problem