Consider something like a McDonald’s kids meal where the meal comes with a toy and there are X different toys in the total collection. The toys are added to the meals randomly and each toy has a 1-in-X chance of being added to the meal. How many meals would you expect to purchase if you want to get the full set of X toys? If you’re really lucky you’ll get the full set in X meals, but that’s not likely to happen. You’ll likely get duplicate toys along the way to getting all X toys. And speaking of dups, what kind of dup pattern would you expect to have once you got all X toys? What’s the maximum number of dups of any single toy that you would expect to have at the end?
What got me wondering about this is when I was playing a computer game. Killing a boss monster will sometimes have a special piece of armor, but it’s just one piece out of X total pieces. Since I need all X different pieces to make a whole set, I’m wondering how many kills of the boss monster I should plan for. (In games it’s common for different loot to have different probabilities of showing up, but for simplicity I’m ignoring that.)
In a truly random drawing, there is no certainty that you will ever get all of them.
Let’s say there are 10 different toys. With your first happy meal, you are guaranteed to get a toy you need. On the next one, you’ll get a toy you need 9 times out of 10.Then 8 out of ten, etc.
Let’s say you get 9 out of ten. You now have a 1 in 10 chance of getting the last toy each time you eat. After 10 attempts, you have 65% chance of getting the toy. In 20 trials, about 88%. This converges to a limit of 100% as the number of trials goes up, but never quite gets there. By 100 trials (once you are down to1 toy needed) you have a 99.998% chance of getting it.
That’s assuming an even number of toys of each type in circulation. In these kinds of contests it is common to restrict the number of winners by artifically limiting one of the options. So there might be 10 million each of 9 of the toys, but only a thousand of the tenth.
Details like that make it difficult to assign probabilities. But it will always be a probability, and never a certainty.
Now that I’ve got a minute, the average amount of kills to get all X pieces is X times the sum of 1/1+1/2+1/3…+1/X. So if X is 2, the average number of kills is 2*(1+1/2)=3 so you’ll have on average 1 duplicate piece of armor, but the number of duplicates increases rapidly. If X is 10 for example, the average number of kills will be about 74 - so you’ll have 60-some duplicates lying around on average. And for McDonalds, it gets more complicated, because some prizes are more rare than others - but fortunately, McMath can handle it
Thanks for the math. That’ll be helpful to estimate how long things should take. No wonder toy promotions always say “Collect them all!” That’s a lot of extra purchases to make in order to get a full set.
An intuitive way to understand the problem is that on the first attempt you automatically get a prize you didn’t have before. To get the second prize, you have a 9/10 chance of getting a new prize every pick - so on average it takes 10/9 attempts to get that second prize. For the third prize it takes 10/8 attempts, for the fourth it takes 10/7, etc., etc., so in total it takes 10(1/1+1/2+1/3+1/4… +1/10) attempts to get the full set.
Nope. Only the first one is guaranteed. The odds of getting one you need on the next visit is 9/10. IF you get one, the next one is 8/10, then 7/10, etc. But on each one of those you may have to visit mu;tiple times to get it, and as the number you need to still get shrinks, even more visits are required.
I did the math for the last one up above. You can do simiilar math for each one, add them up, and figure out how long it will likely take.
So for example, let’s say we’re down to 2 left. Now we have a 1/5 chance of getting one we need on the next visit. In that case, after 5 visits there’s still a 33% chance that we don’t get one of those two, about a 10% chance of not getting one after 10 visits.
I don’t quite follow what you mean. If you need A, B, C, D, E, F, G, H, I, and J, then on your first pick you are guaranteed to get one you need - G, for example. From then on, you have a 90% chance of getting one you need on every pick (and a 10% chance of getting G again) until you actually get a non-G (B for example). From the point on you have a 80% chance of getting a new one, and so on. If we’re down to two left (C and J) then every pick you have a 1/5 chance of picking one of those two. If will almost certainly take you multiple attempts to get C or J, but until you get one of them you’re still missing two. After you’re doen to one left then it will take (one average ) 10 more picks to finally have them all - hence my calculation of 10(1/10+1/9+1/8+1/7+1/6+1/5+1/4+1/3+1/2+1/1) for the average total
The Joe Shlabotnik problem isn’t the same. Charlie Brown only wants Joe Shlabotnik, and doesn’t care if he gets any of the others, and he chose Shlabotnik as the one he wanted even before he started buying any cards. If there are N baseball players, and all are equally likely, Charlie Brown will, on average, only need to buy N cards to get the one he wants.
Someone trying for a complete set will eventually have one and only one specific one that they’re trying for, but that one will be selected based purely on it being the one that they haven’t gotten yet. At that point, they need on average N more cards to finish, but that’s only after already having bought some other number of cards, most likely significantly greater than N.
Assuming that the only way to get them is from the original source. If multiple people are collecting, they’ll all be able to finish their sets much more quickly if they can trade. Promotions never count on the coupon-collector problem making wins rare for actual valuable prizes: If there’s a valuable prize, then they’ll always just make one of the coupons itself that rare.
Have to fix an error - for X=10, the average number of kills required is almost 30, not 74. Silly math error - my fault.
For fun I ran a simulation today of about a million attempts to get all 10 prizes.
To get the first 1, took 1 attempt (every time)
To get the second took 2.11 attempts (in total) with a min of 2, and a max of 7 with a standard deviation of 0.3505
To get the third through 10th took these totals:
with minimums of 3,4,5,6,7,8,9,10
maximums of 12 17 22 33 39 55 80 171
and standard deviations of
0.6585 1.0228 1.4672 2.0375 2.8115 3.9537 5.9724 11.1829
Because what got me wondering about it was the loot from killing monsters in a computer game. After you kill a monster you can search its body for loot. If the monster’s loot has 1 piece of armor (head, chest, legs, etc) and I need 10 pieces in total for a full set, I was wondering about how many kills it would likely take to get the 10 unique armor pieces.
It’s an assumption that the OP made, for the sake of setting up the problem, while acknowledging that things are sometimes more complicated than that. You’re correct that, in real-world situations, you can’t necessarily assume that the probabilities are equal.
