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

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})}$$

• The notation is very confusing. – Michael R. Chernick Dec 29 '16 at 13:07
• @MichaelChernick what can I do to improve it? – user143646 Dec 29 '16 at 16:29
• What is C_n? What do you mean by P(H=1)? Seems like you are considering an event when you get 5 heads in a row and not just one head ? The two recursions don't make sense. Why do you get "if the first flip is a tail the conditional expectation is 1+E(C_n|H=1) and if the first flip is a head the conditional expectation is 2+E(C_n|H=1). Since I don't understand what this notation means and I don't follow these two results given the result of the first flip, I can't follow the next step. Your question is getting a lot of upvotes but no answers. – Michael R. Chernick Dec 30 '16 at 3:31
• I think people are impressed by the chain of equations even though they probably don't really understand what you are doing. It does seem that there should be a way to write a recursion by conditioning on the first flip but I can't get past the problems I am having with the notation. – Michael R. Chernick Dec 30 '16 at 3:35
• @MichaelChernick I explained both $C_n$ and $H$, please tell me if there are other things that are left unclear. – user143646 Dec 30 '16 at 4:32

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.

• If you write out the recursion in matrix form, it will be easy to derive a formula in closed form. – whuber Dec 30 '16 at 18:51
• @whuber I was able to derive a closed form solution for this particular problem (with n = 5), but how would I do it for the case of arbitrary n? It seems like the size of the matrix would change, since for larger n there are more states. – vbox Dec 30 '16 at 19:02
• Since the recurrence relations govern $x_i$ and $y_i$, consider the vector $v_i=(x_i,y_i)^\prime$ and write the recurrence relations in the form $$v_{i+1}=\mathbb{A}v_i + \mathbb{B}v_1 + c$$ for fixed matrices $\mathbb{A},\mathbb{B}$ and fixed constant vector $c=(1,1)^\prime$. This recurrence is no more difficult to solve than its counterpart in one dimension, where $\mathbb{A},\mathbb{B},$ and $c$ are all just numbers. It helps to know how to sum geometric series; for instance, $1+p+\cdots+p^4=(1-p^5)/(1-p)$ allows the formula to be given in a closed form. – whuber Dec 30 '16 at 21:11
• Where did you encounter difficulties understanding my derivation. I appreciate the effort you put into the answer, but my question was with regards to why is my solution scaled by $2$? – user143646 Dec 31 '16 at 7:48
• To be honest, I'm not quite sure your solution is wrong. I looked through your derivation again, and I think I understand it ok now. I'm suspicious of the first line, actually. For instance, suppose the coin is fair. Then, the equation reduces to $E[C_n] = E[C_n|H = 1]$, which is not true, at least with how you've defined $E[C_n|H=1]$. I think there's some sort of abuse of conditional expectation notation, although I can't quite figure it out. My feeling is that what you've calculated as $E[C_n|H=1]$ is actually the joint expectation, not the conditional. – vbox Dec 31 '16 at 14:50