Ross's Probablity Models(11th)
Example 4.26 (Mean Pattern Times in Markov Chain Generated Data) Consider an irreducible Markov chain $\{X_n, n\geqslant0\}$ with transition probabilities $P(i,j)$ and stationary probabilities$\{π_j, j\geqslant 0\}$. Starting in state r, we are interested in determining the expected number of transitions until the pattern $i_1,i_2,...,i_k$ appears. That is, with $$ N(i_1,i_2,...,i_k ) = \min\{n\geqslant k: X_{n−k+1} = i_1,..., X_n = i_k \} $$ we are interested in $$ E[N(i_1,i_2,...,i_k )|X_0 = r] $$ Note that even if $i_1 = r$, the initial state $X_0$ is not considered part of the pattern sequence.
...... $$ E[\text{number of transitions between visits to }i_1,i_2,...,i_k ] = \frac{1} {π(i_1,...,i_k)}\qquad (4.13) $$ Let $A(i_1,...,i_m)$ be the additional number of transitions needed until the pattern appears, given that the first m transitions have taken the chain into states $X_1 = i_1,..., X_m = i_m.$
We will now consider whether the pattern has overlaps, where we say that the pattern $i_1,i_2,...,i_k$ has an overlap of size $j,j < k,$ if the sequence of its final $j$ elements is the same as that of its first $j$ elements. That is, it has an overlap of size $j$ if $$ (i_{k− j+1},...,i_k) = (i_1,...,i_j), j < k $$ ......
Case 2 Now suppose that the pattern has overlaps and let its largest overlap be of size s. In this case the number of transitions between successive visits of the k-chain to the state $i_1,i_2,...,i_k$ is equal to the additional number of transitions of the original chain until the pattern appears given that it has already made $s$ transitions with the results $X_1 = i_1,..., X_s = i_s.$ Therefore, from Equation (4.13) $$ E[A(i_1,...,i_s)] = \frac{1} {π(i_1,...,i_ k )}. $$
How to understand this formula？ I cannot see how to derive it from Equation (4.13).
After $i_1,\ldots,i_k$ has appeared, we expect $\frac1{\pi(i_1,\ldots,i_k)}$ transitions until $i_1,\ldots,i_k$ appears the next time. But because of the overlap of size $s$, the last $s$ states at this point where $i_1,\ldots,i_s$; so this is also $E[A(i_1,\ldots,i_s)]$.