n-step Transition Matrix Identity

Theorem

For any $n\ge 1$, the n-step Transition Matrix ${\mathbf{P}}^{(n)}$ is the $n$-th power of the transition matrix $\mathbf{P}$:

${\mathbf{P}}^{(n)}={\mathbf{P}}^n$

Proof by Induction

Base Case ($n=1$)

By definition of transition probability, $P_{ij}^{(1)}$ is the probability of transitioning from state $i$ to $j$ in one step, which is $P_{ij}$. Thus:

${\mathbf{P}}^{(1)}={\mathbf{P}}^1$

Inductive Hypothesis

Assume ${\mathbf{P}}^{(n)}={\mathbf{P}}^n$ holds for some $n\ge 1$.

Inductive Step

Consider ${\mathbf{P}}^{(n+1)}$. By the Chapman-Kolmogorov equation with $m=1$:

$P_{ij}^{(n+1)}={\sum }_k{P}_{ik}^{(n)}{P}_{kj}^{(1)}$

Substituting $P_{kj}^{(1)}=P_{kj}$ and using the inductive hypothesis $P_{ik}^{(n)}=({\mathbf{P}}^n{)}_{ik}$:

$P_{ij}^{(n+1)}={\sum }_k({\mathbf{P}}^n{)}_{ik}{P}_{kj}$

The right-hand side corresponds to the entry in row $i$ and column $j$ of the matrix product ${\mathbf{P}}^n\cdot \mathbf{P}$.

Therefore:

${\mathbf{P}}^{(n+1)}={\mathbf{P}}^n\cdot \mathbf{P}={\mathbf{P}}^{n+1}$

By induction, the identity holds for all $n\ge 1$.

Related

• n-step Transition Matrix
• Chapman-Kolmogorov Equation