Suppose a box of cereal costs 5$, and each box has a toy in it. There are 5 different toys for you to collect; by collecting all of them you can assemble them together and create a giant robot. If the toys have equal probabilities of turning up - that is, each toy is 1/5 likely to appear in a randomly chosen cereal box - how much will you have to spend, on average, before you can assemble the giant robot of your dreams?

5/5 + 5/4 + 5/3 + 5/2 + 5/1 = 137/12. Moby Dick.

ReplyDeleteThe above should, of course, be multiplied by 5 (for $5 per box). Moby Dick.

ReplyDeleteLet E(i) = State where there is exactly a collection of i toys. P(i) = Prob of reaching E(i) from E(i-1).Then P(1) = 1 , P(2) = 4/5. P(3) = 3/5. P(4) = 2/5. P(5) = 1/5. Probability of staying on E(i) is 1-P(i+1).

ReplyDeleteLet A(i) = Expected number of boxes to reach E(i). T(i) = Number of boxes required to reach E(i+1) from E(i)

Then . T(i) = P(i+1)(1) + (1-P(i+1))(1+T(i))

=> T(i) = 1/{P(i+1)}

And thus A(i+1) = A(i) + T(i)

=> A(5) = T(0)+T(1)+T(2)+T(3)+T(4)

=> A(5) = 1+ 5/4 + 5/3 + 5/2 + 5/1

=> A(5) = 137/12

Therefore expected expenditure C = 5xA(5) = $57.083