Friday, October 11, 2013

Brainteaser: Expected Number of Trials

The first part is the classic coin flipping question: For a fair coin, what is the expected number of trials in order to get the first Head? And the answer is 2 (see here for discussion and related problems).

Now, put the coin aside and consider instead a deck of 52 cards. What is the expected number of trials in order to get the first red card? Would it be less than, equal to, or larger than 2? In the coin case, one way to get the answer is to do the infinite sum

$$ E[H] = \sum_{i=1}^{\infty} \frac{1}{2^i} i $$


Now, along the same line we can have a finite series

$$ E[Red] = \sum_{i=1}^{52} P_i i$$

The only problem is that for this case the $P_i$'s are uglier. Just write down the first few terms and we will see

$$ E[Red] = \frac {26}{52}1 + \frac {26}{52} \frac {26}{51}2 + \frac {26}{52} \frac {25}{51} \frac {26}{50}3 + \sum_{i=4}^{52} P_i i$$

As you can see, some of the fractions are greater than 1/2 and some are less. Can we easily conclude if the finite sum is less than or greater than 2?

See here for more interview questions/brainteasers

No comments:

Post a Comment