# Thread: Expected number of tries to get all N balls

1. ## Expected number of tries to get all N balls

We took my grandson to the Santa Cruz Boardwalk. He fell in love with the gondola ride. He wants to go back until he has ridden on all of the 32 "cars".

My probability is too foggy to work out the expected number of rides he would have to take to have a 50% (or 90%) chance of riding on each of the 32 cars.

I am assuming that it is a very large number (thousands?).

Can anyone supply the formula f(N,P) where N is the number of cars and P is the target probability (50%, 90%)?

Thanks

2. ## Re: Expected number of tries to get all N balls

So which car he gets is random with a 1\32 probability for any unique car?

3. ## Re: Expected number of tries to get all N balls

Originally Posted by hlsmith
So which car he gets is random with a 1\32 probability for any unique car?
Yep. It's essentially the problem of the expected number of draws to get all 32 numbered balls from a bag with replacement.

4. ## Re: Expected number of tries to get all N balls

hi,
looking at this as a practical problem, by running some simulations it looks like you have a 22% chance to finish in less then 100 rides, 75% chance to finish in less then 150 and 95% chance to finish in less then 200 rides. Now it becomes a question of budget and time I think this is a better indicator then the expected number of rides would be.

5. ## Re: Expected number of tries to get all N balls

Originally Posted by rogojel
hi,
looking at this as a practical problem, by running some simulations it looks like you have a 22% chance to finish in less then 100 rides, 75% chance to finish in less then 150 and 95% chance to finish in less then 200 rides. Now it becomes a question of budget and time I think this is a better indicator then the expected number of rides would be.
Failing to come up with a closed form equation, I also ran a simulation. My results match yours. Mine are below.

But I really want the closed form equation. I'm hoping someone can point me in the right direction.

Code:
Number of trials = 1,000,000
Number of balls  = 32

Trial Summary
Draws   Tally   Cum Prob
43       1       0.00
44       1       0.00
45       3       0.00
46       2       0.00
47       7       0.00
48       7       0.00
49       6       0.00
50      15       0.00
51      30       0.01
52      26       0.01
53      42       0.01
54      82       0.02
55     112       0.03
. . .
68    1538       0.92
69    1786       1.10
70    2042       1.30
71    2279       1.53
72    2698       1.80
73    2781       2.08
. . .
86    7493       9.04
87    7903       9.83
88    8385      10.67
89    8553      11.53
. . .
122   11671      49.66
123   11596      50.82
124   11361      51.96
. . .
149    7269      74.93
150    6915      75.62
151    6627      76.29
. . .
180    3053      89.93
181    2952      90.22
182    2934      90.51
183    2858      90.80
184    2837      91.08
. . .
202    1663      94.89
203    1556      95.04
204    1562      95.20
. . .
253     349      98.99
254     338      99.02

6. ## Re: Expected number of tries to get all N balls

I think the best "closed form" solution you would get would be in the form of a horrible cascading summation beast.

7. ## Re: Expected number of tries to get all N balls

Although to answer the question in your title we can get the expected value of the number of tries it will take.

(math tags seem broken at the moment but...)

Sum from i = 1 to 32 of (32)/(32 - i + 1) = 129.87184625396864

The simulation I ran also gives a median of 123 which seems reasonable.

8. ## Re: Expected number of tries to get all N balls

N =32 possible rides. Let's say you want the probability of having collected 3 rides after 12 tries. The time before you had either had 3 rides already and you got another old one or you had 2 rides and got a new one. So P(3 after 12) = P(3 after 11)x3/32 + P(2 after 11)x30/32
In general P(r after t) = P(r after t-1)xr/N + P(r-1 after t-1)x(N+1-r)/N. Also P(1 after 1) = 1 All other P(0 after t) and P(r after 0) = 0.

The spreadsheet attached gives the exact probabilities calculated by filling in the t = 0 and r = 0 probabilities, using the general formula for using the general formula for P(1,1) and copying the formula all over the place. The simulation figures agree with the table.

9. ## Re: Expected number of tries to get all N balls

Just wanted to point out that this is known as the Coupon Collector's Problem.

 Tweet

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts