> [!NOTE] Lemma > Let $\left(X_n\right)_{n \geq 0}$ be a [[Discrete-time Markov Chains]] with the state space $S$ and the **one-step transition matrix** $P$. Then the $n$-step transition probabilities of the Markov chain $\left(X_n\right)_{n \geq 0}$ are given by > $ > \mathbb{P}\left(X_n=j \mid X_0=i\right)=P_{i j}^n, \quad i, j \in S, \quad n \in \mathbb{N} > $ > where $P^n$ is the $n$-th power of the matrix $P$ and $P_{i j}^n$ denotes the $(i, j)$ component of the matrix $P^n$. ###### Proof Applying the law of total probability, conditional independence, and the Markov property, $ \begin{aligned} & \mathbb{P}\left(X_n=j \mid X_0=i\right) \\ & =\sum_{i_1, \ldots i_{n-1} \in S} \mathbb{P}\left(X_n=j, X_{n-1}=i_{n-1}, X_{n-2}=i_{n-2}, \ldots, X_1=i_1 \mid X_0=i\right) \\ & =\sum_{i_1, \ldots i_{n-1} \in S} \mathbb{P}\left(X_n=j \mid X_{n-1}=i_{n-1}, X_{n-2}=i_{n-2}, \ldots, X_1=i_1, X_0=i\right) \\ & \times \mathbb{P}\left(X_{n-1}=i_{n-1}, X_{n-2}=i_{n-2}, \ldots, X_1=i_1 \mid X_0=i\right) \\ & =\sum_{i_1, \ldots i_{n-1} \in S} \mathbb{P}\left(X_n=j \mid X_{n-1}=i_{n-1}, X_{n-2}=i_{n-2}, \ldots, X_1=i_1, X_0=i\right) \\ & \times \mathbb{P}\left(X_{n-1}=i_{n-1} \mid X_{n-2}=i_{n-2}, \ldots, X_1=i_1, X_0=i\right) \\ & \times \mathbb{P}\left(X_{n-2}=i_{n-2} \mid X_{n-3}=i_{n-3} \ldots, X_1=i_1, X_0=i\right) \\ & \vdots \\ & \times \mathbb{P}\left(X_3=i_3 \mid X_2=i_2, X_1=i_1, X_0=j\right) \\ & \times \mathbb{P}\left(X_2=i_2 \mid X_1=i_1, X_0=i\right) P\left(X_1=i_1 \mid X_0=i\right) \\ & =\sum_{i_1, \ldots i_{n-1} \in S} \mathbb{P}\left(X_n=j \mid X_{n-1}=i_{n-1}\right) \mathbb{P}\left(X_{n-1}=i_{n-1} \mid X_{n-2}=i_{n-2}\right) \\ & \times \mathbb{P}\left(X_{n-2}=i_{n-2} \mid X_{n-3}=i_{n-3}\right) \cdots \times \mathbb{P}\left(X_1=i_1 \mid X_0=i\right) \\ & =\sum_{i_1, \ldots i_{n-1} \in S} P_{i i_1} P_{i_1 i_2} P_{i_2 i_3} \ldots P_{i_{n-2} i_{n-1}} P_{i_{n-1} j} \\ & =P_{i j}^n \end{aligned} $ # Applications Kolmogorov-Chapman equation is given by $\begin{aligned} \mathbb{P}\left(X_{n+m}=j \mid X_0=i\right)= & \sum_{k \in S} \mathbb{P}\left(X_{n+m}=j \mid X_n=k\right) \mathbb{P}\left(X_n=k \mid X_0=i\right) \end{aligned}$or equivalently, $P_{i j}^{n+m}=\sum_{k \in S} P_{i k}^n P_{k j}^m$ for any $i, j \in S$ and any $n, m \in \mathbb{N}$ (when we have time-homogeneity).