Solution: 2014 Fall Final - 23

Author: Michiel Smid

Question

Consider the following recursive algorithm $\ThreeHeadsOrThreeTails$, which takes as input a positive integer $k$:

$\mathbf{Algorithm}$ $\ThreeHeadsOrThreeTails(k)$:
$\quad \text{flip a fair coin three times};$
$\quad \mathbf{if}\ \text{the result is $HHH$ or $TTT$}$
$\quad \quad \mathbf{then}\ \mathrm{return}\ k$
$\quad \mathbf{else}$
$\quad \quad \ThreeHeadsOrThreeTails(k + 1)$
$\quad \mathbf{endif}$

You run algorithm $\ThreeHeadsOrThreeTails(1)$, i.e., with $k = 1$. Define the random variable $X$ to be the value of the output of this algorithm. What is the expected value of $X$?

(a)

(b)

(c)

(d)

Solution

So um, this algorithm pretty much counts the number of attempts we make until we get $HHH$ or $TTT$

We have a $ \frac{1}{8} $ chance of flipping an $HHH$

We have a $ \frac{1}{8} $ chance of flipping an $TTT$

This gives us a $ \frac{1}{4} $ chance of flipping either $HHH$ or $TTT$

By the geometric distribution, the expected value of the number of attempts until we get a success is $ \frac{1}{p} $

Therefore, the expected value of $X$ is $ \frac{1}{ \frac{1}{4}} = 4 $