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?
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this communityConsider 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?
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.
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. $$
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.
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.