When can I expect to get 5 heads in a row when tossing a coin?

Question

A coin that lands on heads with probability $p$ is flipped until either $n$ consecutive heads appear or $n$ consecutive tails appear. What is the expected number of coin tosses? I get $$\mathbb{E}[C_n]=\mathbb{E}[\mathbb{E}[C_n|H]]=\mathbb{E}[C_n|H=1]\mathbb{P}(H=1)+\mathbb{E}[C_n|H=0](1-\mathbb{P}(H=1))$$ Where
$C_n$ is the number of flips until we get either $n$ consecutive heads or $n$ consecutive tails. $H=1$ iff we get $n$ consecutive heads before $n$ consecutive tails and is zero otherwise. $$\mathbb{E}[C_n|H=1]=\frac {p^{-n}-1}{1-p}$$ $$\mathbb{E}[C_n|H=0]=\frac {(1-p)^{-n}-1}{p}$$ $$\mathbb{P}(H=1)=\frac{p^{n}}{1-(1-p^{n-1})(1-(1-p)^{n-1})}+(1-p)p^{n-1}\frac{1-(1-p)^{n-1}}{1-(1-p^{n-1})(1-(1-p)^{n-1})}$$ As an answer, but, when trying to compute this value when $p=1$, which better be $n$, it is $2n$. what is wrong with the formula?
PS:
The way I got the terms is as follows:
If the first flip is tails, then the conditional expected value is $1+\mathbb{E}[C_n|H=1]$, if the first flip is heads and the second tails, the conditional expected value is $2+\mathbb{E}[C_n|H=1]$, if ..., thus $$\mathbb{E}[C_n|H=1]=\sum_{k=0}^{n-1}p^k(1-p)(1+k+\mathbb{E}[C_n|H=1])$$ Solving for $\mathbb{E}[C_n|H=1]$ gives $$\mathbb{E}[C_n|H=1]=\frac{p^{-n}-1}{1-p}$$ Likewise for $\mathbb{E}[C_n|H=0]$ except that the probabilities are now inverted, thus: $$\mathbb{E}[C_n|H=0]=\frac{(1-p)^{-n}-1}{p}$$ To compute $\mathbb{P}(H=1)$ we condition on whether the first flip is a head. Here, we have two possibilities, either the following $n-1$ flips are heads, or one of these $n-1$ flips results in tails, at which point we forget about all previous heads and imagine that our first flip is a tail, thus $$P=\mathbb{P}(H=1|\text{first flip is heads})=p^{n-1}+(1-p^{n-1})\mathbb{P}(H=1|\text{first flip is tails})$$ To compute $\mathbb{P}(H=1|\text{first flip is tails})$, we have two possibilities again: either the following $n-1$ flips are all tails, in which case the probability of obtaining $n$ consecutive heads before $n$ consecutive tails is zero, or somewhere along the line we get a head, in which case we start all over again as if though our first flip had been a head. Thus $$Q=\mathbb{P}(H=1|\text{first flip is tails})=(1-(1-p)^{n-1})\mathbb{P}(H=1|\text{first flip is heads})$$ We now have the simultaneous equations $$\begin{align} P&=p^{n-1}+(1-p^{n-1})Q \\ Q &=(1-(1-p)^{n-1})P\end{align}$$ Which implies that $$P=\frac{p^{n-1}}{1-(1-p^{n-1})(1-(1-p)^{n-1})}$$ $$Q=\frac{p^{n-1}(1-(1-p)^{n-1})}{1-(1-p^{n-1})(1-(1-p)^{n-1})}$$ Remembering we had conditioned on the first flip, we now get $$\mathbb{P}(H=1)=\frac{p^{n}}{1-(1-p^{n-1})(1-(1-p)^{n-1})}+(1-p)p^{n-1}\frac{1-(1-p)^{n-1}}{1-(1-p^{n-1})(1-(1-p)^{n-1})}$$

Answer 1

I couldn't follow your derivation, but I believe the correct way to solve the problem is as follows.

First, some notation: take $x_i$ to be the expected number of flips to reach the end state ($n$ consecutive heads or $n$ consecutive tails), given that we're on a "run" of exactly $i$ consecutive flips of heads. Similarly, take $y_i$ to be the expected number of flips to reach the end state, given that we're on a run of exactly $i$ consecutive flips of tails. Clearly, $x_n = y_n = 0$, since if we've already had $n$ consecutive heads or tails, we're done.

Then, we're interested in finding $x_0$ ($= y_0$). The relevant equations are (for $i < n$):

\begin{equation} \begin{split} x_i & = (1-p)(1 + y_1) + p(1 + x_{i+1}) \\ y_i & = p(1 + x_1) + (1-p)(1 + y_{i+1}) \end{split} \end{equation}

Let's derive the first equation (the second one is analogous). Suppose we're on a run of $i$ heads. We want to find the expected number of flips to end the game, which is $x_i$. Let's take our next flip. There's a probability $p$ that it comes up heads, which means we now have a run of $i+1$ heads. That's the second term on the right-hand-side of the equation: there's a probability of $p$ of moving from the state with $i$ consecutive heads to the state with $i+1$ consecutive heads, and it costs 1 flip in order to do so. There's also a probability $1-p$ that it comes up tails, in which case we have a run of only 1 tail. That's the first term on the right-hand-side of the equation: there's a probability of $1-p$ of moving from the state with $i$ consecutive heads to the state with 1 consecutive tail, and it costs us 1 flip in order to do so.

With these equations you can solve the problem for any $n$. I tried implementing this in Mathematica, and if $p = 0$ or $p = 1$, I indeed get that $x_0 = y_0 = n$, as expected. I'm not sure if there's any closed form solution to the equations for arbitrary $n$; that's probably a question for the Math StackExchange. (Edit: see derivation below for the solution for arbitrary $n$).

What I've sketched out here is a general approach for solving many types of coin flipping problems (and other problems). It essentially constructs a Markov chain that has states (e.g., 3 consecutive heads), and transition probabilities for moving between states (e.g., a probability of $1-p$ of moving from 3 consecutive heads to 1 tail). The absorbing states are the end states of the game. See, for instance, the answer to this question.

EDIT: For the particular case of $n=5$, I get (using Mathematica):

\begin{equation} x_0 = \frac{(5 - 10p + 10p^2 - 5p^3 + p^4)(1 + p + p^2 + p^3 + p^4)}{1 - 4p + 6p^2 - 4p^3 + p^4 + 4p^5 - 6p^6 + 4p^7 - p^8} \end{equation}

which seems to have the right limits (although it's possible I have a typo somewhere).

Edit #2: Following @whuber's advice, I solved the recurrence relation for general $n$. The solution is:

\begin{equation} \begin{bmatrix} x_0 \\ y_0 \end{bmatrix} = (A + B)[(I-A^{n-1})^{-1}(I-A)-B]^{-1}c + c \end{equation}

where \begin{equation} A = \begin{bmatrix} p & 0 \\ 0 & 1-p \end{bmatrix} \end{equation}

and

\begin{equation} B = \begin{bmatrix} 0 & 1-p \\ p & 0 \end{bmatrix} \end{equation}

and

\begin{equation} c = \begin{bmatrix} 1 \\ 1 \end{bmatrix} \end{equation}

and $I$ is the identity matrix. For $n=5$, this gives the same result as above.