4
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ The notation is very confusing. $\endgroup$ Dec 29, 2016 at 13:07
  • $\begingroup$ @MichaelChernick what can I do to improve it? $\endgroup$
    – user143646
    Dec 29, 2016 at 16:29
  • $\begingroup$ 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. $\endgroup$ Dec 30, 2016 at 3:31
  • $\begingroup$ 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. $\endgroup$ Dec 30, 2016 at 3:35
  • $\begingroup$ @MichaelChernick I explained both $C_n$ and $H$, please tell me if there are other things that are left unclear. $\endgroup$
    – user143646
    Dec 30, 2016 at 4:32

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ If you write out the recursion in matrix form, it will be easy to derive a formula in closed form. $\endgroup$
    – whuber
    Dec 30, 2016 at 18:51
  • $\begingroup$ @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. $\endgroup$
    – vbox
    Dec 30, 2016 at 19:02
  • 2
    $\begingroup$ 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. $\endgroup$
    – whuber
    Dec 30, 2016 at 21:11
  • $\begingroup$ 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$? $\endgroup$
    – user143646
    Dec 31, 2016 at 7:48
  • $\begingroup$ 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. $\endgroup$
    – vbox
    Dec 31, 2016 at 14:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.