7 ms·

I find this a quite terrible explanation of a fairly simple concept, but perhaps I haven't had enough coffee. Here's an alternative try: First, for the compute

by dgacmu 4y ago

I find this a quite terrible explanation of a fairly simple concept, but perhaps I haven't had enough coffee. Here's an alternative try: 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 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.

amluto 4y ago
I agree - the OP’s explanation is terrible. What does this even mean: > 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.
- kgwgk 4y ago
  >> 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? 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 37.5% or whatever. Etc. The expected number of meals is 1 x 0% + 2 x 0% + 3 x 0% + 4 x 9.4% + 5 x 37.5% + 6 x ... + ...
  - deleted 4y ago
    [deleted]
  - kgwgk 4y ago
    More precisely: 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 eighth 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.0% + 9 x 8.8% + ...
vecter 4y ago
To put it in a different way, construct a Markov chain with these states and transitions: (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.
- LudwigNagasena 4y ago
  When I started reading the article, I thought it was going to be an introduction to Markov Chains. But now that I’ve finished reading it, I guess we should expect an article named “The Unreasonable Effectiveness of Matrices” before that.
whack 4y ago
My initial hunch was also to calculate the answer as 1 + 4/3 + 2 + 4. Ie, "average tries to get 1st toy, plus average tries to get 2nd toy, plus ...." 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 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.
- vecter 4y ago
  Linearity of expectation is of course true in general, but in this case summing the expectations of the individual transition probabilities is only valid because the only valid state transitions are going from state i -> i+1 (owning i unique toys to i+1 unique toys) or just staying in state i. If you could magically go from state i to any other state (you lose unique toys or gain more than one unique toy), then this simple calculation would not be correct.
onos 4y ago
A way to see the scaling this commenter quoted: 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.
wizofaus 4y ago
Doesn't it depend on the #/ distribution of coupons printed/toys manufactured though? To take an extreme example if there are 4 different toys and only 10 of each are manufactured, then the probability of getting 4 all the same is surely somewhat lower than it would be if you assume essentially an infinite toy supply where the chance of getting a particular toy is always 1/4.
- mlyle 4y ago
  We're effectively assuming that the number of toys are infinite and equally likely. 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?
  - wizofaus 4y ago
    Yes I gathered, but in reality there's not an infinite number all produced in equal quantities. I'm curious how much it might change how many meals you'd need to buy if it was a limited production run, and even whether the total number of participants would make much difference (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, as on average they could have only received 4).
    - mlyle 4y ago
      > Yes I gathered, but in reality there's not an infinite number all produced in equal quantities. 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.
tunesmith 4y ago
After 9 purchases, what's the percentage certainty you'd have all four toys? If you had to pre-purchase all n at once from the outset, what's the value of n to be 99.9% certain you'd get all four?
- travisjungroth 4y ago
  Estimates from 67 million simulations After 9: 71.13% p99.9: 29 Ran it up to 2 billion. Still holds, but no additional precision! It's somewhere around 71.134%, so it was threatening to round up for a bit.
  - tunesmith 4y ago
    Thanks for doing that. I suspected those answers were very different than the 8.3, which I'm guessing must have been around the 50th percentile. The way the initial question was asked, it seemed to suggest you had a pretty high probability of all four after 8.3, which isn't true.
    - travisjungroth 4y ago
      It hinges on the "expect" in how "much do you expect to pay?". 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.
  - travisjungroth 4y ago
    Got it up to 17 billion and it flipped to 71.135%! I’m away from my computer and can’t remember more digits. 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.

by dgacmu 4y ago

amluto 4y ago

I agree - the OP’s explanation is terrible. What does this even mean: > 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.

kgwgk 4y ago
>> 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? 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 37.5% or whatever. Etc. The expected number of meals is 1 x 0% + 2 x 0% + 3 x 0% + 4 x 9.4% + 5 x 37.5% + 6 x ... + ...
- deleted 4y ago
  [deleted]
- kgwgk 4y ago
  More precisely: 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 eighth 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.0% + 9 x 8.8% + ...

vecter 4y ago

To put it in a different way, construct a Markov chain with these states and transitions: (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.

LudwigNagasena 4y ago
When I started reading the article, I thought it was going to be an introduction to Markov Chains. But now that I’ve finished reading it, I guess we should expect an article named “The Unreasonable Effectiveness of Matrices” before that.

whack 4y ago

My initial hunch was also to calculate the answer as 1 + 4/3 + 2 + 4. Ie, "average tries to get 1st toy, plus average tries to get 2nd toy, plus ...." 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 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.

vecter 4y ago
Linearity of expectation is of course true in general, but in this case summing the expectations of the individual transition probabilities is only valid because the only valid state transitions are going from state i -> i+1 (owning i unique toys to i+1 unique toys) or just staying in state i. If you could magically go from state i to any other state (you lose unique toys or gain more than one unique toy), then this simple calculation would not be correct.

onos 4y ago

A way to see the scaling this commenter quoted: 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.

wizofaus 4y ago

Doesn't it depend on the #/ distribution of coupons printed/toys manufactured though? To take an extreme example if there are 4 different toys and only 10 of each are manufactured, then the probability of getting 4 all the same is surely somewhat lower than it would be if you assume essentially an infinite toy supply where the chance of getting a particular toy is always 1/4.

mlyle 4y ago
We're effectively assuming that the number of toys are infinite and equally likely. 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?
- wizofaus 4y ago
  Yes I gathered, but in reality there's not an infinite number all produced in equal quantities. I'm curious how much it might change how many meals you'd need to buy if it was a limited production run, and even whether the total number of participants would make much difference (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, as on average they could have only received 4).
  - mlyle 4y ago
    > Yes I gathered, but in reality there's not an infinite number all produced in equal quantities. 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.

tunesmith 4y ago

After 9 purchases, what's the percentage certainty you'd have all four toys? If you had to pre-purchase all n at once from the outset, what's the value of n to be 99.9% certain you'd get all four?

travisjungroth 4y ago
Estimates from 67 million simulations After 9: 71.13% p99.9: 29 Ran it up to 2 billion. Still holds, but no additional precision! It's somewhere around 71.134%, so it was threatening to round up for a bit.
- tunesmith 4y ago
  Thanks for doing that. I suspected those answers were very different than the 8.3, which I'm guessing must have been around the 50th percentile. The way the initial question was asked, it seemed to suggest you had a pretty high probability of all four after 8.3, which isn't true.
  - travisjungroth 4y ago
    It hinges on the "expect" in how "much do you expect to pay?". 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.
- travisjungroth 4y ago
  Got it up to 17 billion and it flipped to 71.135%! I’m away from my computer and can’t remember more digits. 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.