Expected number of tries to get all N balls

Jennifer Murphy

New Member
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

hlsmith

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

Jennifer Murphy

New Member
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.

rogojel

TS Contributor
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.

Jennifer Murphy

New Member
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

Dason

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

Dason

Ambassador to the humans
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.

katxt

Member
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.