n-step Transition Matrix

Definition

The n-step Transition Matrix ${\mathbf{P}}^{(n)}$ contains probabilities that a state $i$ transitions to $j$ in $n$ steps:

$P_{ij}^{(n)}=P(X_n=j\mid X_0=i)$

By the Chapman-Kolmogorov equation:

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

Theorem

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

The n-step transition matrix equals the $n$-th power of the transition matrix.

Proof

See n-step Transition Matrix Identity.

Example

For $\mathbf{P}=\Vert \begin{array}{cc}0.7& 0.3\\ 0.4& 0.6\end{array}\Vert$:

${\mathbf{P}}^{(4)}={\mathbf{P}}^4=\Vert \begin{array}{cc}0.5749& 0.4251\\ 0.5668& 0.4332\end{array}\Vert$

• $P_{00}^{(4)}=0.5749$: If it rains today, probability it rains 4 days later is 57.49%
• $P_{01}^{(4)}=0.4251$: If it rains today, probability it’s sunny 4 days later is 42.51%

Related

• Transition Probability Matrix
• Chapman-Kolmogorov Equation