## Sunday, October 15, 2006

### Great Expectations. Topic: Probability. Level: AMC/AIME.

Definition: The expected value of a random variable $X$ is $\displaystyle \sum_x x \cdot p(x)$, where the summation is taken over all possible values $x$ of $X$ and $p(x)$ is the probability that $X = x$. For example, the expected value of a die roll is

$1 \cdot \frac{1}{6}+ 2\cdot \frac{1}{6}+ \cdots + 6 \cdot \frac{1}{6} = \frac{7}{2}$.

--------------------

Problem: What is the expected number of rolls on a standard die that you need to make before every number shows up at least once?

Solution: Let $E_n$ be the expected number of rolls before $n$ of the numbers shows up at least once. Clearly, $E_1 = 1$. Then

$E_2 = \frac{5}{6}(E_1+1)+\frac{1}{6}(E_2+1)$

because there is a $\frac{5}{6}$ probability that it will take exactly one more than $E_1$ (if we roll a new number) and a $\frac{1}{6}$ probability that it will result in the same number as before and we start from the same situation again. Using this same argument, we deduce that

$E_{n+1} = \frac{6-n}{6}(E_n+1)+\frac{n}{6}(E_{n+1}+1)$,

which is equivalent to

$E_{n+1} = E_n+\frac{6}{6-n}$.

Since we want to find $E_6$, we just apply this recursion $6$ times to get

$E_6 = 6\left(1+\frac{1}{2}+\cdots+\frac{1}{6}\right) = 14.7$.

QED.

--------------------

Comment: Expected value is an interesting topic and can result in a bunch of strange recursions, but it's quite cool in that respect. It's "possible" to solve this problem using only probability, but that would get very ugly very quickly.

--------------------

Practice Problem: Generalize this to a die with $8$, $12$, or $20$ sides (the three bigger regular die which exist).