[lamford]

In Atlanta for Xmas. In a packet of cereal which my nephew and niece eat, one gets a small plastic model. For simplicity we shall say that it is one of the seven dwarfs. The chance of each dwarf being in a random packet is 1/7. I mused (yes I know there are nine of them) how many packets I would need to buy to be favourite to get a set of all seven dwarfs. I am sure that you can work it out after you make excuses for not playing board games with relatives over Xmas. Excel helps.

[Fluffy]

you should state clearly that the number of packets is suposed to be infinite so the 1/7 remains constant, I guess you actually know but are ignoring on purpose the fact that all of this collections never has the same probability for all figures and one or 2 of them are always extremelly hard to find

[lamford]

Fluffy, on 2012-December-21, 12:17, said:

you should state clearly that the number of packets is suposed to be infinite so the 1/7 remains constant, I guess you actually know but are ignoring on purpose the fact that all of this collections never has the same probability for all figures and one or 2 of them are always extremelly hard to find

Yes that approximation is necessary. In practice I agree that the cereal manufacturers make one dwarf scarcer than the others, so that the dopey customers are not happy too soon.

[Antrax]

The time until you get the ith dwarf for the first time is distributed geometrically with parameter (8-i)/7. So, the expected to get all seven is the sum of i from 1 to 7 on 7/(8-i), which is 363/20, or 18 and a bit. According to Markov's theorem (I think), the odds it'll take more than twice that are < 0.5, i.e. you're a favourite to get all seven once you purchase the 37th packet.
I think.

[lamford]

Antrax, on 2012-December-21, 12:44, said:

The time until you get the ith dwarf for the first time is distributed geometrically with parameter (8-i)/7. So, the expected to get all seven is the sum of i from 1 to 7 on 7/(8-i), which is 363/20, or 18 and a bit. According to Markov's theorem (I think), the odds it'll take more than twice that are < 0.5, i.e. you're a favourite to get all seven once you purchase the 37th packet.
I think.

I think it is a lot less than that. I get
7 0.006119899
8 0.024479596
9 0.057701905
10 0.104912555
11 0.163096201
12 0.22845244
13 0.297306545
14 0.366574924
15 0.433918826
16 0.497719823
17 0.556972711
as the probability of getting all 7 dwarfs in n packets. The first two agree when checked using brute force, so I hope they are all right.

[Cascade]

lamford, on 2012-December-21, 13:08, said:

I think it is a lot less than that. I get
7 0.006119899
8 0.024479596
9 0.057701905
10 0.104912555
11 0.163096201
12 0.22845244
13 0.297306545
14 0.366574924
15 0.433918826
16 0.497719823
17 0.556972711
as the probability of getting all 7 dwarfs in n packets. The first two agree when checked using brute force, so I hope they are all right.

I concur with these.

7 0.006119899
8 0.024479596
9 0.057701905
10 0.104912555
11 0.163096201
12 0.22845244
13 0.297306545
14 0.366574924
15 0.433918826
16 0.497719823
17 0.556972711

[Cyberyeti]

lamford, on 2012-December-21, 13:08, said:

I think it is a lot less than that. I get
7 0.006119899
8 0.024479596
9 0.057701905
10 0.104912555
11 0.163096201
12 0.22845244
13 0.297306545
14 0.366574924
15 0.433918826
16 0.497719823
17 0.556972711
as the probability of getting all 7 dwarfs in n packets. The first two agree when checked using brute force, so I hope they are all right.

I agree with your numbers.

Basically the working is:

After 2 packets you have 1/7 chance of only one dwarf and 6/7 chance of 2 different.

When you add a third packet you have 1/7 x 1/7 chance of only one dwarf, 1/7 x 6/7 (chance you had 1 and got a different one) + 6/7 x 2/7 (chance you had 2 different and matched one) chance of 2, 6/7 x 5/7 chance of 3

You continue this process onwards and you have an iterative formula which basically says that the chance of n dwarves from m+1 packets is (the chance of n dwarves from m packets) x n/7 + (the chance of n-1 dwarves from m packets) x (8-n)/7

Iterating this on a spreadsheet gives the numbers above.

[gwnn]

http://en.wikipedia.org/wiki/Coupon_collector's_problem

[Antrax]

Yeah, I woke up this morning with my heart racing: "Markov's inequality is not a tight bound!". Alas, the post had already been made