2 ms·
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)
by tzs 4y ago
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