Flip a fair coin until three consecutive heads or tails appear

Question

What is the expected number of flips until three consecutive heads or tails appear?

Answer 1

This can be seen as an MC with 4 states. Denote for convenience $S=\{HHH, TTT\}$

One thing to notice first, is that only before you have tossed any coins at all you need 3 matching tosses till $S$. After that, regardless of the outcome, you have no more than two matching tosses from $S$. Hence we have the following MC:

$S_0$: 3 matching tosses till $S$

$S_1$: 2 matching tosses till $S$

$S_2$: 1 matching tosses till $S$

$S_3$: 0 matching tosses till $S$

Denoting $m_{i,j}$ the mean hitting time of state $j$ starting in state $i$, we obtain the following set of recurrent equations: $$ m_{0,3}=1+m_{1,3}\\ m_{1,3}=1+0.5 m_{1,3} +0.5m_{2,3}\\ m_{2,3}=1+0.5 m_{1,3} +0.5m_{3,3} $$ And the boundary condition is of course $m_{3,3}=0$. Solving this set of equations we get $$ m_{0,3}=1+6=7 $$

Answer 2

Let $P$ be the expected number when the last two flips match, $Q$ the expected number when the last two flips don't match (or there has only been one flip). Our answer is $Q+1$ as the first flip will take us to state $Q$.
Then $P=\frac 12 \text{(that we match the last 2)}+\frac 12 (Q+1)\text{ (as we are now in state } Q)$ $Q=\frac 12 (1+P)\text{(that we match the last flip)} + \frac 12 (1+Q)\text{(that we don't match the last flip)}$

This gives $P=4, Q=6$ and our final answer is $7$

Answer 3

Here is probably another way and hope this can be easier to understand. Let us assume to get HHH for X number of times, then for {HHH, TTT} is just X/2.

1)first time get T, then just waste one time, everything turns to be same as before, plus this event chance is 1/2. Then to get HHH is 1/2*(X+1)

2)first time get H 2.1)second time get T, then waste two times plus 1/4 probability of this event. Then total number is 1/4*(X+2) 2.2)second time get H 2.2.1) third time get T, then waste 3 times plus 1/8 prob of this event. Then total number is 1/8*(X+3) 2.2.2) third time get H, this is perfect and prob is 1/8. So total number is 1/8*3.

Now, everything sum together should converge to X. we have: 1/2*(X+1) + 1/4*(X+2) + 1/8*(X+3) + 1/8*3 = X => X = 14.

So to get {HHH, TTT} is X/2 = 7.

Answer 4

I think it should be 14.

$X_k$=number of flips needed to obtain first k consecutive heads.

$$E[X_k]=\frac{1}{p}+\frac{1}{p*2}+\cdots+\frac{1}{p*k}$$ where $$p(\text{Heads})=p \\ p(\text{Tails})=1-p$$

and p is not equal to zero.

Answer 5

Let us keep it general and assume that $\mathrm{P(heads})=p$ and $\mathrm{P(tails})=1-p=q$, and start by analyzing only the event of three consecutive heads, which composes the larger event asked.

All sequences can be obtained by appending to the initial sequences {T,HT,HHT,HHH}, the last one already having our target event. So, these sequences induce a partition of the sample space. Furthermore, every time a T appears, the subsequent sequences will also be generated by these initial sequences, thus they induce also a partition of the sub-events, being recurrent. So, it is possible to express the probability $f(k)$ of three consecutive tails occurring after $k$ flippings, conditionally on those sequences: \begin{equation} \begin{array}{ll} f(k)=0, & k<3\\ f(3)=p^3 \\ f(k)=qf(k-1)+pqf(k-2)+p^2qf(k-3), & k >3; \end{array} \end{equation} where the interpretation of the recurrence equation is that each of its terms corresponds to each of the sequences {T,HT,HHT} occurring before the sub-events become a copy of the same recurrence relation.

If one prefers to interpret the flipping sequences being generated by transitions in a Markov Chain (MC), all transitions associated to the occurrence of a T point to the same state, which will need at least three more flippings to obtain the desired event. The states can be expressed as {{},H,HH,HHH}, each of these labels expressing uninterrupted sequences of heads in the last three flippings. Every time a T occurs, the system returns to the state {}. The state HHH is terminal. Then, the recurrence relation $f(k)$ above expressed can be obtained by analyzing the probabilities of trajectories in the MC.

Given that the expected number of flips (the expectation of the random variable $K_{3\mathrm{T}}$) until three consecutive heads appear can be expressed as $\mu=E(K_{3\mathrm{T}})=\sum_{k=1}^{\infty}kf(k)$, we apply this summation to the definition of $f(k)$ above and manipulate as following: \begin{equation} \mu=\sum_{k=1}^{\infty}kf(k)=3f(3)+\sum_{k=4}^{\infty}k\left[qf(k-1)+pqf(k-2)+p^2qf(k-3)\right]\\ =3p^3+q\sum_{k=4}^{\infty}kf(k-1)+pq\sum_{k=4}^{\infty}kf(k-2)+p^2q\sum_{k=4}^{\infty}kf(k-3), \end{equation} from which we can deduce that \begin{equation} \begin{array}{lll} \sum_{k=4}^{\infty}kf(k-1)=&4f(3)&[=f(3)+3f(3)]\\ & +5f(4)&[=f(4)+4f(4)]\\ & ...\\ & +(1+n)f(n)&[=f(n)+nf(n)]\\ &=\\ &1+\mu&[=\sum_{k=3}^{\infty}f(k)+\sum_{k=3}^{\infty}kf(k)]. \end{array} \end{equation} Applying the same reasoning for the other summations, we conclude that \begin{equation} \mu=q(1+\mu)+pq(2+\mu)+p^2q(3+\mu)+3p^3, \end{equation} from which we can use that $q=1-p$ and isolate $\mu$ such that \begin{equation} \mu=p^{-3}(1+p+p^2). \end{equation} The event of three consecutive tails is symmetric to three consecutive heads, so $\lambda=E(K_{3\mathrm{H}})=q^{-3}(1+q+q^2)$. If $p=q=1/2$, we have $\lambda=\mu=14$ and, with certain assumptions (e.g. independence, type of distribution), we could argue that the average time for either event occur is half of this time. However I am not sure about what assumptions would be needed and how they could be checked, so I will restart the demonstration from scratch using arguments similar to the ones used above.

A MC which generates the sequences until three consecutive heads or tails occur, for $p\in[0,1]$, has the following states: {{},H,HH,HHH,T,TT,TTT}, where {} occurs only at the beginning, and HHH and TTT are terminal or absorbing. The problem of establishing a recurrence relation from this MC is that it does not have a single state to which all of the non-absorbing states may return, as it happened for the example given above. However, we can consider the following two mutually exclusive events: the initial transition goes to H and the initial transition goes to T. This allows us to express the probability mass function $g(k)$ as: \begin{equation} g(k)=p.g(k|\mathrm{H})+q.g(k|\mathrm{T}), \end{equation} which is conditioned on either H or T occurring first. The MC associated to $g(k|\mathrm{H})$ has all the states of that associated to $g(k)$ except {}, and starts at the state H; similarly to that associated to $g(k|\mathrm{T})$, which starts at T. With each of these MCs, it is possible to find a recurrence relation.

Let us start by analyzing $g(k|\mathrm{T})$. In order to express its recurrence relation, we have to identify all possible trajectories which either terminate or return to the initial state T. These are {TTT,TTHT,TTHHT,TTHHH,THT,THHT,THHH}. They are used to identify the event partitions below: \begin{equation} \begin{array}{rlll} g(k|T)=& &=0, & k<3\\ g(3|T)=&\mathrm{P}(\mathrm{TTT}) &=q^2, \\ g(4|T)=&\mathrm{P}(\mathrm{THHH}) &=p^3,\\ g(5|T)=&\mathrm{P}(\mathrm{TTHHH})+\mathrm{P}(\mathrm{THT})g(3|\mathrm{T})&=p^3q+pq^3, \\ g(k|T)=&\mathrm{P}(\mathrm{TTHT})g(k-3|\mathrm{T})+\mathrm{P}(\mathrm{TTHHT})g(k-4|\mathrm{T})\\ &+\mathrm{P}(\mathrm{THT})g(k-2|\mathrm{T})+\mathrm{P}(\mathrm{THHT})g(k-3|\mathrm{T}) \\ =&pq.g(k-2|\mathrm{T})+(p^2q+pq^2)g(k-3|\mathrm{T})\\ &+p^2q^2.g(k-4|\mathrm{T}),& & k\geq 6. \end{array} \end{equation} Similarly to what I did for $f(k)$ above, I use the expectation formula $\mu_T=E(K_3|T)=\sum_{k=1}^{\infty}k.g(k|\mathrm{T})$ to obtain \begin{equation} \mu_t=3q^2+4p^3+5p^3q+pq(\mu_\mathrm{T}+2)+(p^2q+pq^2)(\mu_\mathrm{T}+3)+p^2q^2(\mu_\mathrm{T}+4) \end{equation} and, making $\mu_T$ explicit: \begin{equation} \mu_T=\frac{p^4-p^3-2p^2+p-3}{p^4-2p^3-p^2+2p-1}. \end{equation} In which the denominator never vanishes for $p\in[0,1]$. Because the problem structure is symmetric for $g(k|\mathrm{H})$, we can obtain $\mu_H=E(K_3|\mathrm{H})$ by substituting $q$ for $p$ in the formula above. And, from the fact that $g(k)=p.g(k|\mathrm{H})+q.g(k|\mathrm{T})$, we can deduce that \begin{equation} E(K_3)=p.E(K_3|\mathrm{H})+q.E(K_3|\mathrm{T})=p\mu_\mathrm{H}+q\mu_\mathrm{T}. \end{equation}

We can easily verify that a fair coin gives $E(K_3)=7$.