However, my memory of probability is very fuzzy and I wasn't sure if my above intuition was mathematically rigorous. Ie, can the expected values of these 4 events be simply summed in order to get the combined expected value?
For anyone else curious about this, here's the mathematical proof that you can indeed do so. Ie, proof that E(X+Y) = E(X) + E(Y). Where X can be defined as the number of tries to get the 1st toy, Y is the number of tries to get the 2nd toy, and so on: https://www.milefoot.com/math/stat/rv-sums.htm
In this specific example, X and Y are independent random variables. But if my reading of the above proof is correct, you can still sum the expected values even if X and Y happen to be correlated.
(A_0) -> (A_1) -> (A_2) -> (A_3) -> (A_4)
State A_i = you have i unique toys. Each state from 1-4 also has a transition to itself.
The probability of going from A_i -> A_{i+1} = P(A_{i,i+1}) = (1 - i/4). This is pretty obviously: 1, 3/4, 2/4, and 1/4. The transition probability of staying in the same state is 1 - that = i/4, although we don't use those values in our calculations.
The expected time to reach A_4 is E[A_0 -> A_1] + E[A_1 -> A_2] + E[A_2 -> A_3] + E[A_3 -> A_4] = 1/P(A_{0,1}) + 1/P(A_{1,2}) + 1/P(A_{2,3}) + 1/P(A_{3,4}) = 1 + 4/3 + 2 + 4 = 8 1/3. This is true due both to linearity of expectation and the fact that each state only either stays the same or advances. If any state could transition to another state besides itself or the subsequent one, you'd have to do a more complex calculation.
> From a fundamentals perspective, the expected number of meals is a function of the probability of finding the fourth toy in any specific meal.
I can barely parse it. The probability of finding the nth toy before the nth meal is 0, so is the answer a function of 0? Or maybe the probability of finding the toy with index 4 in a specific meal is 1/4, and the answer is a function of 1/4?
Anyway, if you drink another coffee and stop reducing your fractions, you get a nicer way to say the answer :) . After getting n different toys, the probability of a duplicate on the next try is n/4, so the probability of a new toy is 1-n/4 = (4-n)/4, and it takes 4/(4-n) draws on expectation to go from n to n+1 toys. So to do from 0 toys to 4 toys takes 4 * (1/4 + 1/3 + 1/2 + 1/1) tries on expectation, because you can just add the expected number of tries for each new toy.
> I can barely parse it. The probability of finding the nth toy before the nth meal is 0, so is the answer a function of 0?
The probability of finding the fourth toy in the first meal is 0%.
The probability of finding the fourth toy in the second meal is 0%.
The probability of finding the fourth toy in the third meal is 0%.
The probability of finding the fourth toy in the fourth meal is 9.4% or whatever.
The probability of finding the fourth toy in the fifth meal is p5.
Etc.
The expected number of meals is 1 x 0% + 2 x 0% + 3 x 0% + 4 x 9.4% + 5 x p5 + 6 x p6 + ...
The probability of finding the fourth toy in the first meal is 0%.
The probability of finding the fourth toy in the second meal is 0%.
The probability of finding the fourth toy in the third meal is 0%.
The probability of finding the fourth toy in the fourth meal is 3/32 = 9.4%.
The probability of finding the fourth toy in the fifth meal is 9/64 = 14.1%.
The probability of finding the fourth toy in the sixth meal is 123/512 = 24.0%.
The probability of finding the fourth toy in the seventh meal is 135/1024 = 12.0%.
The probability of finding the fourth toy in the eight meal is 903/8192 = 11.0%.
The probability of finding the fourth toy in the ninth meal is 1449/16384 = 8.8%.
Etc.
The expected number of meals is 1 x 0% + 2 x 0% + 3 x 0% + 4 x 9.4% + 5 x 14.1% + 6 x 24.0% + 7 x 12.0% + 8 x 11% + 9 x 8.8% + ...
Suppose there are on average N items left to be seen at time t. Then using a continuous time approximation:
dN/dt = -N / N_tot
This gives
-dN / N = dt / N_tot
Integrate from N_tot to a small value at left and from 0 to t at right,
Log(N_tot /a) = t / N_tot,
Solving for t gives the scaling quoted.
Or, to put it slightly more formally, we're choosing each time from 4 equally likely possibilities, with replacement. Imagine you're drawing from a bag with 4 toys inside. How long until you've drawn each of the 4 toys, if you replace the toy in the bag after each choice?
Most of the McDonald's toys are made in equal quantities, and the quantity available dwarfs the quantity any one customer buys.
> clearly it must make some - if only 1000 of each toy were produced and 1000 customers took part, surely very few would have been lucky enough to get all 4 toy types at all
I don't think the odds change much in this case. 4 provides you with a very small chance from a bottomless pit -- 3/4 * 1/2 * 1/4 = .09375 chance of getting all 4 with with purchased.
It's slightly better if there's a small number, say, 4 of each, because you remove the ones you don't want from contention.
You have a 12/15 chance of the second not matching (3 toys remain that you don't want; and 4 toys each remain of each of the 3 kinds you want); then a 8/14 chance of the third not matching, and then a 4/13 chance of the fourth one not matching-- or a ~14% chance. So even when we say there's only 4 of each toy, the odds don't change -that- much.
Once we get to 1000 of each, the odds basically are the same as the infinite case. 3000/3999, 2000/3998, 1000/3997 are practically 3/4, 1/2, 1/4 -- ~.09389.
> as on average they could have only received 4
Well, we already know from the infinite case you need to buy more than 4 to have a good shot.
After 9: 71.13%
p99.9: 29
You can think of it like "expected value", where you're doing a comparison. Those meals are $8 each. If someone says they'll give you $80 for a set, this would be a profitable endeavor. On average, you'd expect to spend $66.67 (8.33*8) to get a collection.
If you think of it like "setting expectations", it's not so good. If a mafia boss told you he was expecting you to get all four toys for his daughter, you're not going to place an order for nine meals and walk in there with 71% confidence. I might show up with 59 of them, which is the p99.9999 value.
I’m really surprised by this. I knew things converged slowly, but I didn’t appreciate how much and for how long it would move here. I’d be very appreciative if anyone calculated the number.
- We can then subtract 6 * P(two balls), so 6 * (2/4)^9. Now this counts singles a few times too, in fact it cancels all of them out.
- We then need to add back four singles, so 4 * (1/4)^9
Putting this together gives:
1 - (4 * (3/4)^9 - 6 * (2/4)^9 + 4 (1/4)^9) = 0.7113647
But I get it now. If the four prizes are ABCD, then if you calculate your chance of only getting two balls in five purchases, you can do it by calculating your chances to get "A or B" five times in a row. But those include the AAAAA and BBBBB scenarios, which aren't two balls.
Repeat that for AC, AD, BC, BD, and CD.
If I plug in 7, I still get a probability of above 50%, which seems to conflict with the 8.333 answer calculated upstream.
Wouldn't a positive EV imply that a 50% probability is the break-even?
First, for the computer scientists out there, this is the Coupon Collector's problem - so you probably know already it's Θ(N log N). That doesn't give us a precise answer but it should guide our intuition - it should take somewhere like 4 * log(4) ~= 8 draws to get what we want. [1]
Being exact:
When you have already have 3 of the 4 toys, what's the chance you get the 4th? It's 1 in 4. The expected number of draws to get an item with P=1/4 is 4.
Generalizing, the expected number of tries to get an item with probability p is 1/p. When you have 2 toys, you have a 1/2 probability of getting one of the two you haven't seen already, etc. When you have no toys, you always get something you don't have.
So the only slightly tricky case is when you have 1 toy, where you have a 3 in 4 chance of getting something new. 1/(3/4) = 1 1/3.
So the answer is very simply 4 + 2 + 1 1/3 + 1 = 8.3333.
More on the Coupon Collector's Problem: https://en.wikipedia.org/wiki/Coupon_collector%27s_problem
[1] The actual bounds use ln, not log2, but from a "getting intuition" perspective log2 gets us into the right range.