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

[Tregowan]

HOW MANY PACKETS DO I HAVE TO BUY?

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

Anyway:

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

 

[Stephen Tashi]

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

( (1/2) A + (1/2) B)^2 = (1/2)^2 A^2 + 2 (1/2)^2 AB + (1/2)^2 B^2

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:

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

As another example, for 3 toys and 5 purchases, we can look at:
( (1/3)A + (1/3)B + (1/3)C)^5 and sum the coefficients of terms that have at least one power of A,B and C 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.

 

[awkward]

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.

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

P(T=n) = P(T > n-1) - P(T>n)

The Wikipedia article
http://en.wikipedia.org/wiki/Coupon_collector's_problem
has more information on expected values etc. but, oddly enough, does not give the formula above.

 

[Tregowan]

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 modeled 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
and
http://davechessgames.blogspot.com/2012/01/probabilities-and-free-toys-part-2.html

And the modelling I've done is here:
http://davechessgames.blogspot.com/2012/01/probabilities-and-free-toys-part-three.html

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.