Question 7.35: Compute E[T], the expected time until the pattern h, h, h, t......
Compute E[T], the expected time until the pattern h, h, h, t , h, h, h appears, when a coin that comes up heads with probability p and tails with probability q = 1− p is continually flipped.
Define a renewal process by letting the first renewal occur when the pattern first appears, and then start over. Also, say that a reward of 1 is earned whenever the pattern appears. If R is the reward earned between renewal epochs, we have
\begin{aligned}E[R] & =1+\sum\limits_{i=1}^6 E[\text { reward earned } i \text { units after a renewal }] \\& =1+0+0+0+p^3 q+p^3 q p+p^3 q p^2\end{aligned}
Hence, since the expected reward earned at time i is E\left[R_i\right]=p^6 q, we obtain the following from the renewal reward theorem:
\frac{1+q p^3+q p^4+q p^5}{E[T]}=q p^6
or
E[T]=q^{-1} p^{-6}+p^{-3}+p^{-2}+p^{-1}