\problem{(\bf 15 points)}

Consider the process of tossing a sequence of $n$ independent fair
coins $X_1,X_2,\ldots,X_n$.  Let $V$ be the first time two consecutive
heads occur in the sequence, i.e. $(X_{V-1},X_V)=(H,H)$ and
$(X_{i-1},X_i)\neq (H,H)$ for all $2\leq i<V$.  If the sequence of $n$
coin tosses does not contain two consecutive heads, then we assign
$V=n+1$.

Prove that $V$ has distribution
\[\Pr(V=k) = \frac{\Fib(k-2)}{ 2^k} \ \ \ \ (2\leq k\leq n) \]
where $\Fib(k)$ is the $k$-th Fibonacci number (assume 
$\Fib(0)=\Fib(1)=1$.)

\solution{
% This problem is taken from spring 96, problem 10
%
Let's count the sequences of coin tosses of length $k$ such that the
only pair {\em HH} that occurs in the sequence is at the end. Let
$H(k)$ be the number of such sequences that start with $H$, and let
$T(k)$ be the number of such sequences that start with $T$.  Observe
that $H(2) = 1$ and $T(2) = 0$. Similarly, $H(3) = 0$ and $T(3) =
1$. Given a valid sequence {\em HS} of length $k$ that starts with
$H$, the sequence {\em THS} is also valid and starts with $T$.  Given
a valid sequence {\em TS} of length $k$ that starts with $T$, the
sequences {\em HTS} and {\em TTS} are also valid and start with $H$
and $T$ respectively. From this we deduce the recurrence relations
\begin{eqnarray*}
H(k+1) &=& T(k)\\
T(k+1) &=& H(k) + T(k){.}
\end{eqnarray*}
The total number of valid sequences of length $k$ is $T(k)+H(k)$,
hence it satisfies the following recurrence
\begin{eqnarray*}
T(k+1)+ H(k+1) &=& (T(k) + H(k)) + T(k)\\
&=& (T(k) + H(k)) + (T(k-1) + H(k-1)){.}
\end{eqnarray*}
This is the same recurrence relation that defines the Fibonacci
numbers, and with the given initial conditions we can conclude that
the total number of valid sequences of length $k$ is $\Fib(k-2)$.

Now the total number of sequences of length $n$ such that the first
pair of heads occurs after $k$-th toss is $\Fib(k-2)2^{n-k}$, since we
don't care what the coin tosses are in the last $n-k$ places.

The sample space in this problem is the set of all sequences of coin
tosses of length $n$, so its size is $2^n$. Therefore the probability
\[
P(V=k) = \frac{\Fib(k-2)2^{n-k}}{ 2^n} = \frac{\Fib(k-2)}{ 2^k}{,}
\]
as desired.
}

\noindent {\bf Question for the curious (not graded):} What is the
cumulative distribution function for $V$?  It is a similar expression
involving $\Fib(k+c_1)$ and ${2^{k+c_2}}$ for some small $c_1,c_2$.

\solution{ The equation is $\prob{V \leq k}=1-\frac{\Fib(k+1)}{2^k}$, and
you can show it by induction: The base case: $\prob{V\leq{2}}=1/4=1-3/4=
1-\frac{\Fib(3)}{2^2}$.  And the inductive case holds too.}