A man is tossing infinite number of coins one by one. What is the average number of coins he must toss before he gets 4 consecutive head-tail pairs starting with heads?
Attempt- We need to find the expectation that of the number of coins we must toss before we get the sequence HTHTHTHT.
There is a lot of 'notation' going on here but I hope it's self explanatory. Let $s$ be the sequence $HTHTHTHT$ and $X_s$ be the random variable that counts the number of tosses it takes to get $s$. Consider the following numbers:
\begin{align} x&=\mathbb{E}(X_s)&&y=\mathbb{E}(X_s|\text{First tosses are T})\\ a&=\mathbb{E}(X_s|\text{First tosses are H})&&b=\mathbb{E}(X_s|\text{First tosses are HT})\\ c&=\mathbb{E}(X_s|\text{First tosses are HTH})&&d=\mathbb{E}(X_s|\text{First tosses are HTHT})\\ e&=\mathbb{E}(X_s|\text{First tosses are HTHTH})&&f=\mathbb{E}(X_s|\text{First tosses are HTHTHT})\\ g&=\mathbb{E}(X_s|\text{First tosses are HTHTHTH})&&h=\mathbb{E}(X_s|\text{First tosses are HTHTHTHT}) \end{align}
We wish to calculate $x$. To do so, we notice the following relations:
\begin{align} x&=\frac12a+\frac12y&&&&y=1+x\\ a&=\frac12b+\frac12(1+a)&&&&b=\frac12c+\frac12(3+x)\\ c&=\frac12d+\frac12(3+a)&&&&d=\frac12e+\frac12(5+x)\\ e&=\frac12f+\frac12(5+a)&&&&f=\frac12g+\frac12(7+x)\\ g&=\frac12h+\frac12(7+a)&&&&h=8 \end{align}
Solving this system of linear equations we obtain that $x=340$.