News for hackers. Stuff that matters.
Re:The Unreasonable Effectiveness of Conditional Probabilities by dgacmu on Wednesday February 22, 2023 @01:59PM (#34900823)
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

[1] The actual bounds use ln, not log2, but from a "getting intuition" perspective log2 gets us into the right range.

Re:The Unreasonable Effectiveness of Conditional Probabilities by whack on Wednesday February 22, 2023 @02:41PM (#34901491)
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

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.

Re:The Unreasonable Effectiveness of Conditional Probabilities by vecter on Wednesday February 22, 2023 @02:55PM (#34901683)
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.
Re:The Unreasonable Effectiveness of Conditional Probabilities by vecter on Wednesday February 22, 2023 @02:31PM (#34901320)
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.

Re:The Unreasonable Effectiveness of Conditional Probabilities by LudwigNagasena on Wednesday February 22, 2023 @10:07PM (#34906217)
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.
Re:The Unreasonable Effectiveness of Conditional Probabilities by amluto on Wednesday February 22, 2023 @02:27PM (#34901248)
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.

Re:The Unreasonable Effectiveness of Conditional Probabilities by kgwgk on Wednesday February 22, 2023 @03:24PM (#34902092)
>> 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 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 + ...

Re:The Unreasonable Effectiveness of Conditional Probabilities by kgwgk on Wednesday February 22, 2023 @05:41PM (#34904053)
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 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% + ...

Re:The Unreasonable Effectiveness of Conditional Probabilities by onos on Wednesday February 22, 2023 @03:05PM (#34901819)
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.

Re:The Unreasonable Effectiveness of Conditional Probabilities by wizofaus on Wednesday February 22, 2023 @03:11PM (#34901912)
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.
Re:The Unreasonable Effectiveness of Conditional Probabilities by mlyle on Wednesday February 22, 2023 @03:15PM (#34901954)
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?

Re:The Unreasonable Effectiveness of Conditional Probabilities by wizofaus on Wednesday February 22, 2023 @06:46PM (#34904804)
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).
Re:The Unreasonable Effectiveness of Conditional Probabilities by mlyle on Wednesday February 22, 2023 @07:24PM (#34905101)
> 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.

Re:The Unreasonable Effectiveness of Conditional Probabilities by tunesmith on Wednesday February 22, 2023 @03:57PM (#34902601)
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?
Re:The Unreasonable Effectiveness of Conditional Probabilities by travisjungroth on Wednesday February 22, 2023 @05:14PM (#34903715)
Estimates from 67 million simulations

After 9: 71.13%

p99.9: 29

Re:The Unreasonable Effectiveness of Conditional Probabilities by tunesmith on Wednesday February 22, 2023 @05:47PM (#34904140)
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.
Re:The Unreasonable Effectiveness of Conditional Probabilities by travisjungroth on Wednesday February 22, 2023 @06:45PM (#34904786)
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.

Re:The Unreasonable Effectiveness of Conditional Probabilities by travisjungroth on Wednesday February 22, 2023 @10:25PM (#34906347)
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.

Re:The Unreasonable Effectiveness of Conditional Probabilities by colmanhumphrey on Wednesday February 22, 2023 @11:01PM (#34906602)
I got 71.13647% on a first pass. So we want P(all 4 in 9) = 1 - P(not all 4), and we can split that out a few ways. To not get all four, we can restrict ourselves to three, so that's (3/4)^9, but there are four ways of doing that, so that's 4 * (3/4)^9. But that counts using singles and pairs too many times. Specifically each version of "three" can be exactly three balls, three ways of one ball, or three ways of exactly two balls ("1 or 2 or 3" = "1&2&3" or "just 1" or "just 2" or "just 3" or "1&2" or "1&3" or "2&3").

- 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

Re:The Unreasonable Effectiveness of Conditional Probabilities by tunesmith on Thursday February 23, 2023 @07:28PM (#34918926)
This took me way too long to understand. :)

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.

Re:The Unreasonable Effectiveness of Conditional Probabilities by colmanhumphrey on Thursday February 23, 2023 @11:55PM (#34920954)
Re:The Unreasonable Effectiveness of Conditional Probabilities by tunesmith on Monday February 27, 2023 @05:14PM (#34962703)
Don't know if you're still reading this thread, but one thing I'm stumped on is that if I plug in 8.333 instead of 9, I get a probability of around 65%.

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?

Re:The Unreasonable Effectiveness of Conditional Probabilities by travisjungroth on Saturday February 25, 2023 @02:02AM (#34934562)
The reply button is back so I can thank you publicly!