Combinatoric Probability problem

[Academic Actuary]

Originally Posted by Divide by Zero

Let's simplify the example. What is the probability of getting all 4 unique toys from buying only 4 boxes of cereal? For your 1st box of cereal, you can get any of the 4 toys. For your 2nd box of cereal, you can't receive the same toy you got from the 1st box of cereal but can get any of the other 3 toys remaining. For your 3rd box, you have 2 toys which have not yet been selected. Finally, for your 4th box, you have only 1 toy left which has not yet been selected. Thus, the numerator is 4*3*2*1 or 4!. You can think of this as a sequence of events that leads to getting all 4 toys in 4 trials. How many different patterns of toys can you observe from 4 boxes of cereal? That's 4*4*4*4 or 4^4 which is the denominator. Thus, the answer is 24/256 or 9.375%.

What happens if we increase the number of trials and purchase 5 boxes of cereal instead? The easy part is that the denominator becomes 4^5. What happens to the numerator? You can still receive all 4 unique toys in 4 trials, which is the numerator in the above example. If that happens, then we don't care what we receive in the 5th box so that box can contain any of the 4 toys. Thus, the number of different patterns in which you can receive all the unique toys in the first 4 boxes in 5 trials is 4*3*2*1*4. In addition to that, you might only receive just 3 unique toys in the first 4 trials and get the 4th and last unique toy in the 5th trial. This will happen when there's a repeat toy on either trials (1 & 2), (1 & 3), (1 & 4), (2 & 3), (2 & 4), or (3 & 4). In other words, there are 6 ways we can receive the last unique toy from the 5th box. There are still 4*3*2*1 orders in which we could observe the 4 unique toys with 6 different combinations of repeated toys. So, there are 4*3*2*1*6 permutations which result in getting all 4 unique toys from the 5th box of cereal. The numerator is then calculated as 4*3*2*1*4 + 4*3*2*1*6. Thus, the answer is 240/1024 or 23.438%.

If you apply the same method when you increase the trials to 6, you'll end up getting 4*3*2*1*4*4 + 4*3*2*1*6*4 + 4*3*2*1*10 + 4*3*2*1*15 for the numerator and 4^6 for the denominator. Thus, the answer is 1560/4096 or 38.086%.

Someone correct me if I'm wrong or there's some flaw in my logic. If anyone can run some simulations on this to confirm the answer, that would be good enough too. In any case, you have to buy a lot of cereal if you want a decent shot at getting all the toys.

Your answer is consistent with mine.

1560 = 4^6 - 4(3^6) + 6(2^6) - 4

[AAABBBCCC]

Did you figure this out on your own? Or did you get it from a combinatorics book? I guess it is not that hard, but it is still pretty slick. My answer is the same, but yours is much better for obvious reasons.

[AAABBBCCC]

In general, if you fix r toy choices and you have n trials, then you want to count the number of ways of placing n objects into r bins with each bin containing at least one element. This is just a sum of multinomials:

with I the index set {(n_1,...,n_r):n_1+...+n_r=n, n_i>=1 for all i}.

You then multiply by r_2 choose r for the total number of ways of getting r unique toys in n trials given an initial set of r_2 unique toys.

acadeactuary, how did you get that closed form solution? did you use induction?

[AAABBBCCC]

haha!

YOu see, if the bins are not labeled then you just get the stirling numbers:

http://en.wikipedia.org/wiki/Stirlin...he_second_kind

If they are labeled, then you just multiply the stirling numbers by r! (r bins) and you obtain the formula:

[Academic Actuary]

Originally Posted by AAABBBCCC

In general, if you fix r toy choices and you have n trials, then you want to count the number of ways of placing n objects into r bins with each bin containing at least one element. This is just a sum of multinomials:

with I the index set {(n_1,...,n_r):n_1+...+n_r=n, n_i>=1 for all i}.

You then multiply by r_2 choose r for the total number of ways of getting r unique toys in n trials given an initial set of r_2 unique toys.

acadeactuary, how did you get that closed form solution? did you use induction?

I just looked at a simple specific case and generalized.

[Academic Actuary]

I did find the formula in a text entitled Elementary Probability by Stiraker. The general problem is an urn with n distinct balls and r selected with replacement. What is the probability each ball is selected at least once?

[jas66Kent]

This question is actually stochastic in nature and not combinatronic.

You can think of each box as a renewable set of probabilities.

If you open one box you get four probabilities with one choice. Then the next box offers you the same probabilities and one choice. Etc.. i.e. Each time you get a box the stochastic system renews itself. i.e. It's a renewal process