Re:The Unreasonable Effectiveness of Conditional Probabilities
by tzs on Thursday February 23, 2023 @12:58AM
(#34907290)
Let E(n) be the expected number of meals to collect at least one each of n toys if there are n possible toys available. We want to find E(4).
Note that
E(4) = 1 + 4/3 E(3)
That's because after the first meal, there are now 3 toys we need to collect. If there were only 3 toys available we would expect to take E(3) meals to get them all. But since there are 4 available, 1/4 of the time we get another one of the toys we got on the first meal, so only 3/4 of the meals are productive toward our goal of collecting the remaining 3 toys, so it takes 4/3 as long.
Similarly,
E(3) = 1 + 3/2 E(2)
E(2) = 1 + 2/1 E(1)
If there were only 1 toy available it would take exactly 1 meal to collect it, so
Note that
That's because after the first meal, there are now 3 toys we need to collect. If there were only 3 toys available we would expect to take E(3) meals to get them all. But since there are 4 available, 1/4 of the time we get another one of the toys we got on the first meal, so only 3/4 of the meals are productive toward our goal of collecting the remaining 3 toys, so it takes 4/3 as long.Similarly,
If there were only 1 toy available it would take exactly 1 meal to collect it, so