\problemdata
{distribution}
{s96 ps9}
{random variable}

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

\begin{problemparts}
\problempart
Prove that $T$ has distribution 
\[\Pr(T=k) = {\Fib(k-2)\over 2^k} \ \ \ \ (1<k\leq n) \]
where $\Fib(k)$ are the Fibonacci numbers.

\bigskip
\noindent
\solution{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)$.
(Note: we assume $\Fib(0)=\Fib(1)=1$.)

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(T=k) = {\Fib(k-2)2^{n-k}\over 2^n} = {\Fib(k-2)\over 2^k}{,}
\]
as desired.
}

\problempart
Compute $\Pr(T=n+1)$.

\bigskip
\noindent
\solution{To answer this question we need to count the sequences
of length $n$ that do not contain any pairs {\em HH}. From part (a),
we can conclude that the number of sequences of length $n+3$ which end
in {\em THH} and do not contain pair {\em HH} in first $n$ positions,
is $\Fib(n+1)$. The total number of sequences of length $n+3$ that end
in {\em THH} is $2^n$, so the probability thet there is no pair {\em
HH} in $n$ coin tosses is
\[
P(T=n+1) = {\Fib(n+1)\over 2^n}{.}
\]
}
\end{problemparts}
\end{problem}

