Expected number of tosses for two coins to achieve the same outcome for five consecutive flips

Question

Consider two unbiased coins. Toss both until last 5 sequence outcome are same. That means we stop when output of the sequence of both are as follows: HTTHTHHTH , HHTTTHHTH.

What is the expected number of trials?

Answer 1

Here's a different approach that simultaneously generalizes the solution.

As Didier and David have pointed out, the problem is equivalent to finding the expected number of flips required for a fair coin to achieve five consecutive heads for the first time. Let $X_n$ denote the toss on which a fair coin achieves $n$ consecutive heads for the first time. The analysis is just as easy if the coin isn't fair, though, so let's suppose that the coin has probability $p$ of being heads.

Suppose the coin has just achieved $n-1$ consecutive heads for the first time. Then, with probability $p$, the coin achieves $n$ consecutive heads for the first time on the next flip, and with probability $1-p$, the process restarts after the next flip. Mathematically, this is saying that $$\begin{align}E[X_n|X_{n-1}] &= p (X_{n-1}+1) + (1-p)(X_{n-1} + 1+ E[X_n])\\ &= X_{n-1} +1+ (1-p)E[X_n].\end{align}$$ Applying the law of total expectation, we have $$\begin{align} E[X_n] &= E[X_{n-1}] +1 + (1-p)E[X_n] \\ \Rightarrow E[X_n] &= \frac{E[X_{n-1}] +1}{p}.\end{align}$$ Now we have a nice recurrence for $E[X_n]$. Since $E[X_0] = 0$, unrolling this recurrence shows that $$\begin{align}E[X_1] &= \frac{1}{p}, \\ E[X_2] &= \frac{1 + p}{p^2}, \\ E[X_3] &= \frac{1 + p+p^2}{p^3},\end{align}$$ and in general $$E[X_n] = \frac{1+p+p^2+\cdots + p^{n-1}}{p^n}.$$ Using the formula for the partial sum of a geometric series, this expression simplifies to $$\begin{align}E[X_n] &= \frac{1-p^n}{(1-p)p^n} \\ &= \frac{p^{-n}-1}{1-p}.\end{align}$$ In the case of a fair coin we have $p = 1/2$, and so $$E[X_n] = 2^{n+1}-2.$$ Thus the answer to the OP's question is $E[X_5] = 2^6-2 = 62,$ as David Mitra has already shown.

---

This approach also handles the generalization of the OP's question in which the two coins being tossed do not necessarily have the same probability of being heads. Suppose one has probability $p_1$ of being heads, the other has probability $p_2$ of being heads, and we toss them until the last $n$ flips are the same. For a single flip, they are the same if they both come up heads, with probability $p_1 p_2$, or both tails, with probability $(1-p_1)(1-p_2)$. Thus the probability that they are the same on a single flip is $1 - p_1 - p_2 + 2p_1p_2$. Tossing these two coins until the last $n$ flips are the same is the same problem as tossing a single coin with heads probability $1 - p_1 - p_2 + 2p_1p_2$ until we see $n$ consecutive heads, and so the formula above for $E[X_n]$ tells us that the expected number of tosses of the two coins until the last $n$ flips are the same is $$E[X_n] = \frac{(1-p_1 - p_2+ 2p_1p_2)^{-n}-1}{p_1 + p_2 - 2p_1p_2}.$$

Answer 2

As Didier points out in his comment, the problem is equivalent to the problem of finding the expected number of flips, $X$, of a fair coin that are made until 5 heads appear in a row.

We condition on whether or not a tail appears in the first five flips.

For $1\le i\le5$, let $T_i$ be the event that the first tail occurs on flip $i$ and let $T_6$ be the event that the first five flips are all heads.

We have $$\Bbb E(X\mid T_i)=i+\Bbb E(X),\quad 1\le i\le 5$$ (if the first tail occurs on flip 3, for example, then it's as if we are "restarting": the expected number of flips to obtain 5 heads in a row would be 3 plus the original expected number of flips).

Also, cleary, $$\Bbb E(X\mid T_6)=5.$$

We have: $$\eqalign{ \Bbb E(X)&= \sum_{i=1}^6 P(T_i)\,\Bbb E(X\mid T_i) \cr &=\sum_{i=1}^5 \bigl({\textstyle{1\over 2}}\bigr)^{i }\bigl(\,i+\Bbb E(X)\,\bigr)+ P(T_6)\Bbb E(X\mid T_6)\cr &= \sum_{i=1}^5{i\over 2^i}+ \sum_{i=1}^5{1\over 2^i}\Bbb E(X)+{1\over32}\cdot 5\cr &={31\over 32}\Bbb E(X)+ {62\over32} . } $$

Solving the above for $\Bbb E(X)$ gives $$ \Bbb E(X)={62/32\over1/32}=62. $$

---

Inspired by Mike Spivey's excellent answer, I'll add that the above can be generalized to the case where $X$ is the number of flips to be made until $n$ heads in a row are obtained, where the probability that the coin lands heads on one flip is $p$.

Here, for $1\le i\le n$, let $T_i$ be the event that the first tail occurs on flip $i$ and let $T_{n+1}$ be the event that the first $n$ flips are all heads.

Then $$\Bbb E(X\mid T_i)=i+\Bbb E(X),\quad 1\le i\le n$$
and $$\Bbb E(X\mid T_{n+1})=n.$$

Also, $$ P(T_i)= (1-p) p^{i-1},\quad 1\le i\le n $$ and $$ P(T_n)=p^n. $$

We have: $$\eqalign{ \Bbb E(X)&= \sum_{i=1}^{n+1} P(T_i)\,\Bbb E(X\mid T_i) \cr &=\sum_{i=1}^n (1-p) p^{i-1}\bigl(\,i+\Bbb E(X)\,\bigr)+ P(T_{n+1})\Bbb E(X\mid T_{n+1})\cr &= (1-p) \sum_{i=1}^n{i} p^{i-1} + (1-p)\sum_{i=1}^n{p^{i-1}} \Bbb E(X)+ p^n\cdot n\cr &=(1-p){ np^{n+1}-np^n-p^n+1\over( 1-p)^2} +(1-p) {1-p^n\over 1-p }\Bbb E(X) +np^n.\cr } $$

Solving the above for $\Bbb E(X)$ gives $$\eqalign{ \Bbb E(X)&={ {np^{n+1}-np^n-p^n+1\over1-p} +np^n \over 1-(1-p^n)}\cr &={ {np^{n+1}-np^n-p^n+1\over1-p} +{np^n (1-p)\over 1-p} \over 1-(1-p^n)}\cr &={1-p^n\over(1-p)p^n }.\cr } $$

In retrospect, it appears that Mike Spivey's method is much neater.

---

In the above we used the formula $$ \sum_{i=1}^n i p^{i-1} ={ np^{n+1}-np^n-p^n+1\over( 1-p)^2}. $$ Here is a proof of that:

Let $$ \def\ts{\textstyle} S_n=\ts{p^0}+2 {p}^1 +3 {p}^2+\cdots+n {p}^{n-1}.$$

Then $$\eqalign{ \ts pS_n &=\ts \bigl[\,{p}^1+2 p^2+3 p^3 +\cdots+(n-1) p^{n-1 }\,\bigr]+n p^{n }\cr &=\ts S_n- [p^0+ p^1 +p^2 + \cdots + p^{n-1 } ] + np^{n } \cr &=\ts S_n-{p^0 -p^{n }\over 1-p}+ np^{n }. }$$

Whence

$$ \eqalign{ S_n&={ -{1-p^n\over1-p}+np^n\over p-1}\cr &= {1-p^n\over (p-1)^2}+{np^n(p-1)\over (p-1)^2}\cr &={ np^{n+1}-np^n-p^n+1\over( 1-p)^2}, } $$ as claimed.