# Drawing Blanks

Premature Optimization is a Prerequisite for Success

## Expected number of kid’s meals to catch ‘em all

You get one free pokemon of a random kind with each kid’s meal. When you collect all kinds of pokemon you get a prize. How many kid’s meals on average you need to buy to get a prize, if there are n different kinds of pokemon?

Hint: use the results of the previous problem

Solution:

We need to buy 1 meal to get the 1st pokemon. Then we use additivity of expectation: E = 1 + {the rest}

The probability of getting a new pokemon after we got the 1st one is 1-1/n, and the expectation of this event (based on the result of the previous problem) is n/(n-1). So E = 1 + n/(n-1) + {the rest}.

The 3rd new pokemon would require n/(n-2) purchases. So E = 1 + n/(n-1) + n/(n-2) + {the rest}.

Finally, the last pokemon would be obtained on average after n additional purchases.

$E = n\sum_{i=1}^n \frac{1}{i}$

http://www.wolframalpha.com/input/?i=Plot%5Bn+HarmonicNumber%5Bn%5D%2C+%7Bn%2C+1%2C+100%7D%5D