> [!NOTE] Lemma > Let $\left(X_n\right)_{n \geq 0}$ be a time-homogeneous discrete time Markov chain with the state space > $S$. Then$\mathbb{P}\left(X_{n+k}=a \mid X_k=b\right)=\mathbb{P}\left(X_n=a \mid X_0=b\right), \quad a, b \in S, \quad n, k \in \mathbb{N} \cup\{0\}$ ###### Proof Suppose that $k \in \mathbb{N}$ is fixed. We proceed by induction on $\mathbb{N}$. Let $n=1$. Then the statement is true by Definition. Suppose that the statement is true for fixed $n \in \mathbb{N}$, that is $ \mathbb{P}\left(X_{n+k}=a \mid X_k=b\right)=\mathbb{P}\left(X_n=a \mid X_0=b\right), \quad a, b \in S $ We want to show that the statement is true for $n+1$, that is $ \mathbb{P}\left(X_{n+1+k}=a \mid X_k=b\right)=\mathbb{P}\left(X_{n+1}=a \mid X_0=b\right), \quad a, b \in S $ Observe that, by Definition 2.3.1, for any $k, n \in \mathbb{N}$ and any $a, b \in S$, $ \mathbb{P}\left(X_{n+1+k}=a \mid X_{n+k}=b\right)=\mathbb{P}\left(X_1=a \mid X_0=b\right)=\mathbb{P}\left(X_{n+1}=a \mid X_n=b\right) $ We have that $ \begin{aligned} \mathbb{P}\left(X_{n+1+k}=a \mid X_k=b\right) & =\sum_{x \in S} \mathbb{P}\left(X_{n+1+k}=a, X_{n+k}=x \mid X_k=b\right) \\ & =\sum_{x \in S} \mathbb{P}\left(X_{n+1+k}=a \mid X_{n+k}=x, X_k=b\right) \mathbb{P}\left(X_{n+k}=x \mid X_k=b\right) \\ & =\sum_{x \in S} \mathbb{P}\left(X_{n+1+k}=a \mid X_{n+k}=x\right) \mathbb{P}\left(X_{n+k}=x \mid X_k=b\right) \\ & =\sum_{x \in S} \mathbb{P}\left(X_{n+1}=a \mid X_n=x\right) \mathbb{P}\left(X_n=x \mid X_0=b\right) \\ & =\sum_{x \in S} \mathbb{P}\left(X_{n+1}=a, X_n=x \mid X_0=b\right) \\ & =\mathbb{P}\left(X_{n+1}=a \mid X_0=b\right) \end{aligned} $ Hence, the statement is true for $n=1$, and if it is true for $n \in \mathbb{N}$ then it is true for $n+1 \in \mathbb{N}$. By induction it follows that the statement is true for all $n \in \mathbb{N}$.