25. [14] A particular coin can land on heads $(\mathrm{H})$, on tails $(\mathrm{T})$, or in the middle $(\mathrm{M})$, each with probability $\frac{1}{3}$. Find the expected number of flips necessary to observe the contiguous sequence HMMTHMMT...HMMT, where the sequence HMMT is repeated 2016 times.
Answer:
$$
\frac{3^{8068}-81}{80}
$$

Let $E_{0}$ be the expected number of flips needed. Let $E_{1}$ be the expected number more of flips needed if the first flip landed on $\mathrm{H}$. Let $E_{2}$ be the expected number more if the first two landed on HM. In general, let $E_{k}$ be the expected number more of flips needed if the first $k$ flips landed on the first $k$ values of the sequence HMMTHMMT...HMMT.
We have
$$
E_{i}=\left\{\begin{array}{lll}
1+\frac{1}{3} E_{i+1}+\frac{1}{3} E_{1}+\frac{1}{3} E_{0} & i \not \equiv 0 & (\bmod 4) \\
1+\frac{1}{3} E_{i+1}+\frac{2}{3} E_{0} & i \equiv 0 & (\bmod 4)
\end{array}\right.
$$

Using this relation for $i=0$ gives us $E_{1}=E_{0}-3$. Let $F_{i}=\frac{1}{3^{i}} E_{i}$. By simple algebraic manipulations we have
$$
F_{i+1}-F_{i}=\left\{\begin{array}{lll}
-\frac{2}{3^{i+1}} \cdot E_{0} & i \not \equiv 0 & (\bmod 4) \\
-\frac{1}{3^{i}}-\frac{2}{3^{i+1}} \cdot E_{0} & i \equiv 0 & (\bmod 4)
\end{array}\right.
$$

We clearly have $F_{2016 \cdot 4}=0$ and $F_{0}=E_{0}$. So adding up the above relations for $i=0$ to $i=2016 \cdot 4-1$ gives
$$
\begin{aligned}
-E_{0} & =-2 E_{0} \sum_{i=1}^{2016 \cdot 4} \frac{1}{3^{i}}-\sum_{k=0}^{2015} \frac{1}{3^{4 k}} \\
& =E_{0}\left(\frac{1}{3^{2016 \cdot 4}}-1\right)-\frac{1-\frac{1}{3^{2016 \cdot 4}}}{\frac{80}{81}}
\end{aligned}
$$
so $E_{0}=\frac{3^{8068}-81}{80}$.