+ Reply to Thread
Results 1 to 9 of 9

Thread: Expected number of tries to get all N balls

Hybrid View

  1. #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. #2
    Omega Contributor
    Points: 38,374, Level: 100
    Level completed: 0%, Points required for next Level: 0
    hlsmith's Avatar
    Location
    Not Ames, IA
    Posts
    6,998
    Thanks
    398
    Thanked 1,186 Times in 1,147 Posts

    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?
    Stop cowardice, ban guns!

  3. #3
    Points: 3,571, Level: 37
    Level completed: 48%, Points required for next Level: 79
    Jennifer Murphy's Avatar
    Posts
    37
    Thanks
    3
    Thanked 0 Times in 0 Posts

    Re: Expected number of tries to get all N balls

    Quote Originally Posted by hlsmith View Post
    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. #4
    TS Contributor
    Points: 12,227, Level: 72
    Level completed: 45%, Points required for next Level: 223
    rogojel's Avatar
    Location
    I work in Europe, live in Hungary
    Posts
    1,470
    Thanks
    160
    Thanked 332 Times in 312 Posts

    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. #5
    Points: 3,571, Level: 37
    Level completed: 48%, Points required for next Level: 79
    Jennifer Murphy's Avatar
    Posts
    37
    Thanks
    3
    Thanked 0 Times in 0 Posts

    Re: Expected number of tries to get all N balls

    Quote Originally Posted by rogojel View Post
    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. #6
    Devorador de queso
    Points: 95,819, Level: 100
    Level completed: 0%, Points required for next Level: 0
    Awards:
    Posting AwardCommunity AwardDiscussion EnderFrequent Poster
    Dason's Avatar
    Location
    Tampa, FL
    Posts
    12,935
    Thanks
    307
    Thanked 2,629 Times in 2,245 Posts

    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.
    I don't have emotions and sometimes that makes me very sad.

  7. #7
    Points: 1,974, Level: 26
    Level completed: 74%, Points required for next Level: 26

    Location
    New Zealand
    Posts
    227
    Thanks
    3
    Thanked 48 Times in 47 Posts

    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.
    Attached Files

  8. #8
    Devorador de queso
    Points: 95,819, Level: 100
    Level completed: 0%, Points required for next Level: 0
    Awards:
    Posting AwardCommunity AwardDiscussion EnderFrequent Poster
    Dason's Avatar
    Location
    Tampa, FL
    Posts
    12,935
    Thanks
    307
    Thanked 2,629 Times in 2,245 Posts

    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.
    I don't have emotions and sometimes that makes me very sad.

  9. #9
    Points: 5,470, Level: 47
    Level completed: 60%, Points required for next Level: 80

    Posts
    176
    Thanks
    5
    Thanked 93 Times in 82 Posts

    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.

+ Reply to Thread

           




Posting Permissions

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






Advertise on Talk Stats