Power of Markov transition matrix

Question

Given a Markov transition matrix $P$, what is the meaning of $P^n$? And what is the meaning of the $(i,j)$ entry of matrix $A=\sum_{k=0}^{k=n}{P^k}$? A possible answer is the expected number of times to visit state $j$ from state $i$ in n steps, but I don't know how to deduce it.

Answer 1

If $\ \big\{X_k\big\}_{k=1}^\infty\ $ is the sequence of states of the Markov chain, then $$ \big(P^n\big)_{ij}=\mathbb{P}\big(\,X_{s+n}=j\,\big|\,X_s=i\big) $$ for any $\ s,i,j\ $ and $\ n\ $. Putting $\ s=nk+d\ $ in this equation shows that $\ P^n\ $ is the transition matrix of the Markov chains $\ \big\{X_{nk+d}\big\}_{k=0}^\infty\ $ for any natural number $\ d\ $.

Your surmise about the value of the entry in row $\ i\ $ and column $\ j\ $ is correct. To prove it, let $\ N_j\ $ be the number of times the chain visits state $\ j\ $ in $\ n\ $ steps from state $\ i\ $. Then $$ N_j=\sum_{k=0}^n\delta_{jX_{s+k}}\ , $$ where $\ s\ $ is the time, immediately before the first step, when the state is $\ i\ $. Therefore, \begin{align} \mathbb{E}\big(\,N_j=\,\big|\,X_s=i\,\big)&=\sum_{k=0}^n\mathbb{E}\big(\delta_{jX_{s+k}}|\,X_s=i\,\big)\\ &=\sum_{k=0}^n\sum_{x=1}^\sigma\delta_{jx}\mathbb{P}\big(\,X_{s+k}=x\,\big|\,X_s=i\big)\\ &=\sum_{k=0}^n\sum_{x=1}^\sigma\delta_{jx}\big(P^k\big)_{ix}\\ &=\sum_{k=0}^n\big(P^k\big)_{ij}\ , \end{align} where $\ \sigma\ $ is the number of states of the chain.