October 17, 2007
Suppose you
repeatedly toss a
fair coin until you get two heads in a row. What is the probability
that
you stop on the 10th toss?
Solution. There
are $2^{10}$ possible outcomes when one flips a coin 10 times. Let
$T_i$ be the result of the $i$th flip. We want to compute the number of
possible outcomes which have $T_9 = T_{10}=H$ and no adjacent $H$'s in
$T_1$, $T_2$, $\cdots$, $T_8$.
Certainly, $T_8=T$ and we wish to know how many sequences of length 7
have no adjacent $H$'s. Let $S_n$ be the number of sequences of length
$n$ without 2 consecutive occurences of $H$. Each such sequence must
start with $HT$ followed by a sequence of length $n-2$ with no
consecutive $H$'s or start with $T$ followed by a sequence of length
$n-1$ with no consecutive $H$'s.
Therefore $S_n=S_{n-1}+S_{n-2}$. Since $S_2=1$ and $S_2=3$, we have
that $S_n=F_{n+2}$ where $F_k$ denotes the $k$th Fibonacci number.
Hence $S_7=F_9=34$. That is, there are 34 possible outcomes which
satisfy our condition.
The probability that such an outcome occurs is thus $34/1024$. (If 10
is replaced by an arbitrary $n\in\mathbf{N}$, then the probability that
we stop after the $n$th flip is $F_{n-1}/2^n$.)