Results 1 to 3 of 3

Math Help - Basic Probability Question

  1. #1
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1

    Basic Probability Question

    Hi, I'm analyzing how valid a solution is to a problem, and I've realized that it's correctness can't be guaranteed. I've translated it into a math problem to try and figure out how correct of a solution it is. But it's been a while since I've done any math, I was hoping someone could help me out.

    MATH VERSION:
    If there are a pool of 24 unique numbers
    and I pull one at random and write it down if I haven't seen it before
    then place it back in
    and I do this 1000 times in total
    how likely is it that I will have written down 24 numbers?

    REAL VERSION:
    A one line permutation generator receives an array with 4 functions, sorts them into a random order 1000 times, then keeps the unique sortings. I've ran it probably 10_000 times and always gotten the same results, and am debating whether I should keep trying to get it to fail.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    Thanks, galactus, I don't think I was very clear, though. There are 24 numbers, they are drawn from 1000 times. How likely is it that all 24 will have been selected at some point during the 1000 drawings.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by angel.white View Post
    Hi, I'm analyzing how valid a solution is to a problem, and I've realized that it's correctness can't be guaranteed. I've translated it into a math problem to try and figure out how correct of a solution it is. But it's been a while since I've done any math, I was hoping someone could help me out.

    MATH VERSION:
    If there are a pool of 24 unique numbers
    and I pull one at random and write it down if I haven't seen it before
    then place it back in
    and I do this 1000 times in total
    how likely is it that I will have written down 24 numbers?

    REAL VERSION:
    A one line permutation generator receives an array with 4 functions, sorts them into a random order 1000 times, then keeps the unique sortings. I've ran it probably 10_000 times and always gotten the same results, and am debating whether I should keep trying to get it to fail.
    This is equivalent to the "Coupon Collector's Problem". The general statement of the problem is that there are N distinct types of coupons and each time we obtain a coupon it is equally likely to be any one of the N, independent of prior selections. We would like to know the probability that we will have to collect more than n coupons to get a complete set.

    The answer, taken from Ross, "A First Course in Probability, 7th edition", is

    \Pr(\text{more than n trials are needed}) = \sum_{i=1}^{N-1} \binom{N}{i} \left( \frac{N-i}{N} \right) ^n (-1)^{i+1}

    With your values (N=24, n=1000), this works out to be about 8 \times 10^{-18}, or to put it another way, you will need about 10^{17} trials, on average, before you see an incomplete set.

    You can find more information about the Coupon Collector's Problem here:

    http://en.wikipedia.org/wiki/Coupon_...or%27s_problem

    but for some mysterious reason the Wikipedia article does not include the formula I quoted.
    Last edited by awkward; November 13th 2009 at 03:16 PM. Reason: added more information
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Basic Probability Question
    Posted in the Statistics Forum
    Replies: 1
    Last Post: July 3rd 2011, 03:22 PM
  2. Basic Probability Question Help
    Posted in the Statistics Forum
    Replies: 3
    Last Post: October 4th 2010, 10:56 AM
  3. very basic probability question
    Posted in the Statistics Forum
    Replies: 10
    Last Post: March 4th 2010, 12:21 AM
  4. basic probability question
    Posted in the Statistics Forum
    Replies: 1
    Last Post: February 22nd 2010, 07:58 PM
  5. A few basic probability question
    Posted in the Statistics Forum
    Replies: 1
    Last Post: December 9th 2009, 01:28 PM

Search Tags


/mathhelpforum @mathhelpforum