News for hackers. Stuff that matters.
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

  E(1) = 1
  E(2) = 1 + 2/1 1 = 3
  E(3) = 1 + 3/2 3 = 11/2 = 5 1/2
  E(4) = 1 + 4/3 11/2 = 50/6 = 25/3 = 8 1/3

There are no comments on this comment yet.