Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Probability of obtaining all members of a group, combination with repitition

  1. Aug 23, 2011 #1

    Hi all,

    I'm posing this question because I'm interested in the answer from a
    purely theoretical point of view - I'm not going to go out and test
    the answer afterwards, and it's not for my homework (I last did
    homework more than 10 years ago).


    A certain breakfast cereal manufacturer is giving away a free toy
    inside each pack. There are ten toys in the series, and I'd like to
    collect them all. However, I can't tell which toy I'm going to get
    when I buy the pack. Assuming that each toy is distributed equally,
    how many packs would I have to buy to be 50%, 70% or 90% sure of
    having all ten toys?

    Work I've done already:

    I can see that in order to calculate the number of possible
    combinations of toys I would have after buying n packs of cereal, I
    would need the 'combination with repitition' formula. However, I
    can't find an expression for the 'successful' combinations, which is
    where I'm struggling. I suspect that the number of successful
    combinations after buying 10 packs is equal to the number of
    permutations, as this will list all the possible combinations with one
    of each toy. I'm at a complete loss for buying 11 packs, or 12 or any
    n(packs) > n(toys).

    I've done some tests with just two toys (start small!):

    After buying two packs, the probability of success is 0.5. The two
    successful combinations are AB and BA, and the two unsuccessful are AA
    and BB (i.e. I get the same toy twice).

    After buying three packs, the probability of success rises to 0.75.
    There are eight total combinations, but only two are unsuccessful (AAA
    and BBB), leaving six successful.

    After buying four packs, the probability of success rises to 7/8, as
    the number of unsuccessful combinations remains at two, but the number
    of successes rises to 14.

    Generally, for the two-toy problem, the probability of getting a
    successful combination after n turns is equal to (2^n - 2) / 2^n or,
    in words, the total number of combinations minus unsuccessful, divided
    by the total number of combinations.

    But I'm not sure how to proceed, and I can't see how I'd expand to
    significantly larger numbers (such as the 10 I posed at the start).
  2. jcsd
  3. Aug 23, 2011 #2

    Stephen Tashi

    User Avatar
    Science Advisor

    If may help to recast your analysis for two toys in a more mechanical form.

    [itex] ( (1/2) A + (1/2) B)^2 = (1/2)^2 A^2 + 2 (1/2)^2 AB + (1/2)^2 B^2 [/itex]

    The coefficient of the term AB gives the probability of getting at least one toy of each type.

    For 4 purchases, we can look at:

    [itex] ((1/2)A + (1/2)B)^4 [/itex] and ask for the sum of the coefficients of the terms [itex] A^3B,A^2B^2,A B^3 [/itex].

    As another example, for 3 toys and 5 purchases, we can look at:
    [itex] ( (1/3)A + (1/3)B + (1/3)C)^5 [/itex] and sum the coefficients of terms that have at least one power of [itex] A,B[/itex] and [itex] C [/itex] in them.

    At least this approach shows that solving your problem amounts to adding up coefficients that appear in a "multinomial expansion".

    Perhaps you can find an inductive formula so that if you know the answer for M types of toys and N purchases, you can write the answer for N+1 purchases in terms of it. As you can probably tell, I haven't solved this problem myself. I'm just making an untested suggestion.

    The above assumes we are going to buy a certain number of boxes and then open them all rather than open each box before buying another.
    Last edited: Aug 23, 2011
  4. Aug 23, 2011 #3
    This is a classic problem called the "Coupon Collector's Problem". The following result is from Ross, "A First Course in Probability", 7th edition.

    Let's say there are N different toys (or types of coupons) and T is the number of toys/coupons which must be collected to form a complete set. It is awkward to compute the probability that T=n directly, so we start instead with the probability that T>n, i.e. more than n items are required to get a complete set.

    [tex]P(T > n) = \sum_{i=1}^{N-1} \binom{N}{i} \left( \frac{N-i}{N} \right) ^n (-1)^{i+1}[/tex]
    To find the probability that exactly n toys/coupons must be collected, use

    [tex]P(T=n) = P(T > n-1) - P(T>n)[/tex]

    The Wikipedia article
    has more information on expected values etc. but, oddly enough, does not give the formula above.
  5. Jan 27, 2012 #4
    Thanks to everyone for their responses - especially the "Coupon Collector's Problem" which really does get to grips with the algebra involved. I'm going to look out that book and start reading!

    I've taken a slightly different route in the six months since I last posted here, and modelled the problem with a spreadsheet. Unsurprisingly, the results I have obtained for different values of number of toys and number of tries show the same shape as the formula shown above.

    My work, starting with toys = tries is found here
    http://davechessgames.blogspot.com/2012/01/probabilities-and-free-toys-part-1.html [Broken]
    http://davechessgames.blogspot.com/2012/01/probabilities-and-free-toys-part-2.html [Broken]

    And the modelling I've done is here:

    Finally, I recently discovered an elegant solution which works out the average number of tries (boxes of cereal) you'd have to employ to get the complete set of toys. I'm just writing up my findings and will be back shortly.
    Last edited by a moderator: May 5, 2017
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook