stochastic processes - Time until a consecutive sequence of ones in a random bit sequence

This a reformulation of a practical problem I encountered.

Say we have an infinite sequence of random, i.i.d bits. For each bit $X_i$, $P(X_i=1)=p$.

What is the expected time until we get a sequence of $n$ 1 bits?

Thanks!

Answer

There is a lot of literature on such questions concerning the mean time for patterns. For your particular problem a solution can be found on page 156 of Introduction to Probability Models (10th edition) by Sheldon Ross. The formula is
$$E[T]=1/p+1/p^2+\cdots+1/p^n={(p^{-n}-1)/(1-p)}.$$

As expected, this is a decreasing function of $p$ for fixed $n$: it takes longer to see rarer events. As $p$ goes from 0 to 1, $E[T]$ decreases from infinity to $n$.

---

Added: Here is a derivation of the formula in my answer.

Let $T$ be the random variable that records the first time
we see $n$ ones in a row. Let's also
define the random variable $L$ to be the position of the first zero bit in
the sequence.

Looking at the first $n$ bits there are, roughly speaking,
two possibilities: either I get the desired pattern of $n$ ones

or I got a zero bit at time $k$ and the whole problem starts over.

More formally, conditioning on the value of $L$ we get
\begin{eqnarray*}
E[T] &=& \sum_{k=1}^{n} E[T \ |\ L=k]\ P(L=k) + E[T\ |\ L> n]\ P(L>n)\cr
&=& \sum_{k=1}^{n} (k+E[T])\ P(L=k) + n P(L > n)\cr
&=& \sum_{k=1}^{n} (k+E[T])\ p^{k-1}(1-p) + n p^n.
\end{eqnarray*}

Solving this equation for $E[T]$ gives the formula.

There are many generalizations of this problem and
variations on the above proof that use, for instance, Markov chains,
or martingales, or generating functions, etc. In addition to Ross's book
mentioned above, you may like to look at

1. Section 8.4 of Concrete Mathematics by Graham, Knuth, and Patashnik


2. Chapter 14 of Problems and Snapshots from the World of Probability by Blom, Holst, and Sandell


3. Section XIII 7 of An Introduction to Probability Theory and Its Applications by Feller