Drawing Blanks

Premature Optimization is a Prerequisite for Success

Archive for June 2011

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:

Read the rest of this entry »

Written by bbzippo

06/25/2011 at 7:42 pm

Posted in Uncategorized

Expected number of coin tosses once again

leave a comment »

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.

Written by bbzippo

06/25/2011 at 7:20 pm

Posted in math