## Archive for **June 2011**

## 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:

## Expected number of coin tosses once again

What is the average number of coin tosses needed to throw a head?

When I wrote about this before here https://bbzippo.wordpress.com/2009/11/25/expected-number-of-tosses-general/ and here https://bbzippo.wordpress.com/2009/11/05/expected-number-of-coin-tosses/ , I didn’t really do a good job.

Let’s try once again.

The expectation is by definition is the infinite sum E = 1 * 1/2 + 2 * 1/4 + 3 * 1/8 + …

How do you compute it?

**Solution 1**. You don’t need to compute it. You can just use the obvious additivity of the expectation. You either throw a head on the first try or not.

E = 1/2 * 1 + {the rest}

What is “the rest”? “The rest” occurs with probability 1/2 (when you fail to through a head on the first try) and it takes on average E tosses. So “the rest” = 1/2 * (E + 1). “+1” is for the first failed toss.

E = 1/2 * 1 + 1/2 * (E + 1) => E = 2

**Solution 2.** E = 1 * 1/2 + 2 * 1/4 + 3 * 1/8 + … Multiply both side by 1/2:

E/2 = 1 * 1/4 + 2 * 1/8 + 3 * 1/16 + … Subtract this from the initial expression:

E/2 = 1/2 + (2-1)*1/4 + (3-2) * 1/8 + (4-3) * 1/16 + … => E/2 = 1.

In general, if we have a constant probability of success p, **what is the average number of trials until first success?** Probability of success on n-th trial (and no earlier) is p*(1-p)^{n-1}. The expectation

E = 1*p + 2*p(1-p) + 3*p(1-p)^{2} + 4*p(1-p)^{3} +…

Using the above trick, we easily derive E = 1/p.