What is the expected number of rolls of a
fair, normal 6-sided die, one is required to make, so that each of the 6 numbers comes up at least once?
Hint: this is not necessarily an integer answer
_____________________
As an aside, it would be interesting to see the computer program simulation of this, but this would not be proof of the solution (merely evidence supporting the proof).
(In reply to
re(2): solution plus simulation-- and another question or two by Charlie)
The solution for getting all possible totals for throws of a pair of dice depends on the inclusion/exclusion principle:
At any given number of throws having taken place in the trial, the probability of having thrown all the eleven possible totals up until then is the sum of all the individual probabilities of having thrown a 2 through having thrown a 12, minus all 55 (i.e., C(11,2)) pairwise probabilities of having thrown a 2 OR a 3 ... through an 11 OR a 12, plus all 165 triplets of ORed possibilities, etc., alternating adding and subtracting. Taking each ORed set individually that adds up to 2^11 = 2048 terms.
Each ORed probability is one minus the probability that none of the given set had appeared through that numbered toss of the dice. That is 1 - ((36 - w) / 36) ^ n, where w is the number of ways of rolling the given set and n is the number of throws thus far. For example, if going after the probability of having thrown a 3 or a 5 or a 9, w would be 2+4+4=10.
A UBASIC program that evaluates this for n = 1 to 2000 is
100 point 5
200 data 1,2,3,4,5,6,5,4,3,2,1
300 dim W(11)
400 for I=1 to 11
500 read W(I)
600 TotWays=TotWays+W(I)
700 next
800
900
1000 for Turn=1 to 2000
1100 T=0
1200 Sg=-1:Ways=0
1300 for W1=0 to 1
1400 Ways=Ways+W(1)*W1
1500 for W2=0 to 1
1600 Ways=Ways+W(2)*W2
1700 for W3=0 to 1
1800 Ways=Ways+W(3)*W3
1900 for W4=0 to 1
2000 Ways=Ways+W(4)*W4
2100 for W5=0 to 1
2200 Ways=Ways+W(5)*W5
2300 for W6=0 to 1
2400 Ways=Ways+W(6)*W6
2500 for W7=0 to 1
2600 Ways=Ways+W(7)*W7
2700 for W8=0 to 1
2800 Ways=Ways+W(8)*W8
2900 for W9=0 to 1
3000 Ways=Ways+W(9)*W9
3100 for W10=0 to 1
3200 Ways=Ways+W(10)*W10
3300 for W11=0 to 1
3400 Ways=Ways+W(11)*W11
3500 T=T+Sg*(1-((TotWays-Ways)/TotWays)^Turn)
3600 Ways=Ways-W(11)*W11
3700 Sg=-Sg
3800 next W11
3900 Ways=Ways-W(10)*W10
4000 Sg=-Sg
4100 next W10
4200 Ways=Ways-W(9)*W9
4300 Sg=-Sg
4400 next W9
4500 Ways=Ways-W(8)*W8
4600 Sg=-Sg
4700 next W8
4800 Ways=Ways-W(7)*W7
4900 Sg=-Sg
5000 next W7
5100 Ways=Ways-W(6)*W6
5200 Sg=-Sg
5300 next W6
5400 Ways=Ways-W(5)*W5
5500 Sg=-Sg
5600 next W5
5700 Ways=Ways-W(4)*W4
5800 Sg=-Sg
5900 next W4
6000 Ways=Ways-W(3)*W3
6100 Sg=-Sg
6200 next W3
6300 Ways=Ways-W(2)*W2
6400 Sg=-Sg
6500 next W2
6600 Ways=Ways-W(1)*W1
6700 Sg=-Sg
6800 next W1
6910 P=T-PrevT
6950 ExpVal=ExpVal+Turn*P
7000 print Turn,P,T
7100 PrevT=T:Ppp=PrevP:PrevP=P
7200 next Turn
7300 print ExpVal
------
By flipping sg from positive 1 to negative 1 and back each time a throw total comes in or out of the ORed set, the proper sign is applied when that ORed probability is added in (or, consequently, subtracted out).
The program calculates each probability (which is in fact a cumulative probability) and finds the individual probability that that throw would be the one to complete the set by subtracting the cumulative probability from the previous cumulative probability. Each individual probability multiplied by the number of throws is added into the expected value.
By the time 2000 throws have been made the total probability is close enough to 1 for 24 significant digits, and the expected value comes out to 61.2173847639571980537370.
An artifact of doing it this way is that we can also get the mode and the median:
34 0.017375360700789131212236 0.220565986006324770340293
35 0.017473676386676434347342 0.238039662393001204687635
36 0.017510455835875378339185 0.255550118228876583026821
37 0.017492202669494406266952 0.273042320898370989293774
38 0.017425077816538910306595 0.29046739871490989960037
39 0.01731485097448574303068 0.30778224968939564263105
40 0.01716687506726530698634 0.324949124756660949617391
41 0.016986077815400902055923 0.341935202572061851673315
42 0.016776965733031975914904 0.35871216830509382758822
43 0.016543636875769735968425 0.375255805180863563556645
44 0.016289799495065753579066 0.391545604675929317135712
45 0.016018794429128916085576 0.407564399105058233221288
46 0.015733619599724859039908 0.423298018704783092261197
47 0.015436955410310670563372 0.438734974115093762824569
48 0.015131190173936084062307 0.453866164289029846886877
49 0.014818444956775478994304 0.468684609245805325881182
50 0.014500597420046446390173 0.483185206665851772271355
51 0.014179304391944190500357 0.497364511057795962771713
52 0.013856023012360844243681 0.511220534070156807015394
53 0.013532030374900937773496 0.524752564445057744788891
-----
The mode is 36, having the highest individual probability (about 1.751%) of being the throw that completes the set. The median is just above 51 throws.
A similar program, run for
the original problem of one die being tossed, and getting all 6 possible results, gives, in part:
9 0.075017146776406035665287 0.189043209876543209876529
10 0.082768918609967992684039 0.271812128486511202560568
11 0.084394290123456790123451 0.356206418609967992684019
12 0.081609262011211028129202 0.437815680621179020813222
13 0.076042513421057088181005 0.513858194042236108994228
14 0.068987154809400290907168 0.582845348851636399901396
15 0.061367389743463996944156 0.644212738595100396845553
16 0.053791659090958983844544 0.698004397686059380690098
----
This shows that the mode for the number of tosses needed is 11 and the median is just below 13 and the run verifies that the mean is 14.7.
Edited on January 26, 2004, 5:29 pm
|
|
Posted by Charlie
on 2004-01-26 17:28:13 |
The other answers
