Drawing Blanks

Premature Optimization is a Prerequisite for Success

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

leave a comment »

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

Advertisements

Written by bbzippo

06/25/2011 at 7:42 pm

Posted in Uncategorized

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: