All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 On Average (Posted on 2004-01-26)
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).

 See The Solution Submitted by SilverKnight Rating: 3.7500 (4 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 The other answers | Comment 5 of 11 |
(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

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

 Search: Search body:
Forums (0)
Random Problem
Site Statistics
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox: