How much is it expected to cost to get all 12?

Question

A decal vending machine randomly dispenses 12 different decals, one at a time for a dime each time. The ad on the machine says, "Get all 12!" How much is it expected to cost to finally get at least 1 of each of the 12?

John P, as with many of these cheap vending machines targeting children, they dispense them randomly, and so of course it can cost a lot of money to get all 12. That's the whole idea here. But about how much?

AJ, no, there's no "certainity", ever. However, the "expected cost" doesn't depend on certainity. For example, what's the "expected cost" to get at least one heads from flipping a coin, if it costs me a dime for each flip? It's 10(1/2) + 20(1/4) + 30(1/8) + ..., which converges to 20 cents as the expected cost.

This is a tough problem, called "The Collector's Problem". Here's a link to a pdf paper by Persi Diaconis, a card sharp who is also a mathematician on probability theory, that covers this subject, and from this a numerical approximation of the answer to this problem can be found.

http://sankhya.isical.ac.in/search/64a3/64a3047.pdf

Answer 1

I think I have a way to calculate this. To start with a general result:

Given the odds of an independent event is (b - a)/b. Then, the number of times the event must be executed before it can be expected to occur is b/(b - a).

For example, if the odds of the event is 1/12, then take the reciprocal to get the expected number of turns: 12/1 = 12.

To calculate this:

Odds of the result in one turn = (b - a)/b
Odds of the result in exactly two turns = (a/b) * (b - a)/b
Odds of the result in exactly three turns = (a/b)² * (b - a)/b

etc. More generally, odds of the result in exactly n turns = (a/b)^(n-1) * (b - a)/b

So, the expected number of turns is

(b - a)/b + 2(a/b) * (b - a)/b + 3(a/b)² * (b - a)/b + ... =
(b - a)/b * (1 + 2a/b + 3(a/b)² + ...) =
(b - a)/b * (1/(1 - a/b) + a/b + 2(a/b)² + ...) =
(b - a)/b * (1/(1 - a/b)(1 + a/b + (a/b)² + ...) =
(b - a)/b * (1/(1 - a/b)) * (1/(1 - a/b)) =
(b(b - a)/(b - a)(b - a)) =
b/(b - a).

We can apply the above result to the vending machine question as follows: When you have possession of n decals, then the expected number of purchases to get a new decal is 12/(12 - n), i.e.:

• The expected number of purchases to get the first decal is 12/(12 - 0) = 1.

• Given you have one decal, the expected number of purchases to get a second (new) decal is 12/(12 - 1) = 12/11.

• Given you have two decals, the expected number of purchases to get a third (new) decal is 12/(12 - 2) = 12/10.

• etc. up to the last decal. Given you have all but one decal, the expected number of purchases to get the last decal is 12/(12 - 11) = 12/1.

So, getting all 12 decals entails twelve expectations that can be calculated by the summation 1 + 12/11 + 12/10 + ... + 12/1 = ∑ 12/n for n = 1 → 12. When I do the summation, I get about 37.2. That means if you buy 37 decals, there is just under a 50% chance you will get at least one of all 12 decals.

Answer 2

It all depends on how the the decals were placed in the machine. If the design repeats after the first 12, 24. 36 etc the answer would be $1.20 BUT the supplier does not do it that way, they are not placed in any special order so you will spend more to get all 12.

Answer 3

Looks like some kind of test. So clues only.

If the probability of having N distinct coins after buying P coins is given by F(N, P) then

F(N, P)=(F(N, P-1) * N + F(N-1, P-1) * (13 - N)) / 12
with
F(1,1) = 1
F(N>1,1)=0

Note there is no certainty of getting all 12, EVER.