> [!NOTE] Lemma > Let $\left(X_n\right)_{n \geq 0}$ be a discrete time [[Stochastic Process|stochastic process]] with the discrete state space $S$. Then $\left(X_n\right)_{n \geq 0}$ is [[Discrete-time Markov Chains|Markov]] if and only if > > $ > \mathbb{P}\left(X_{n+m}=x_{n+m} \mid X_m=x_m, \ldots, X_1=x_1, X_0=x_0\right)=\mathbb{P}\left(X_{n+m}=x_{n+m} \mid X_m=x_m\right) > $ > > for any $n, m \in N$, any $x_0, x_1, \ldots x_m \in S$ and any $x_{n+m} \in S$. ###### Proof ( $\impliedby$ ) This direction is proved by taking $n=1$. $(\implies$ ) We proceed by induction on $n$. For $n=1$ the statement is true by the definition of a Markov chain. Suppose that the statement is true for a fixed $n \in N$. We will show that it is then true for $n+1$ as well. Recall that for any three events $A, B, C$, $\mathbb{P}(A \cap B \mid C)=\mathbb{P}(A \mid B \cap C) \mathbb{P}(B \mid C). \tag {1}$ Also $ \mathbb{P}\left(X_{n+1}=x_{n+1} \mid X_n=x_n, X_k=x_k\right)=\mathbb{P}\left(X_{n+1}=x_{n+1} \mid X_n=x_n\right) \tag{2} $for any $k, n \in \mathbb{N}, n \geq 1,0 \leq k<n$, and any $x_i \in S, i \in \mathbb{N} \cup\{0\}$ - which we can prove as follows: applying the [[Law of Total Probability|law of total probability]] yields $\begin{aligned} & \mathbb{P}\left(X_{n+1}=x_{n+1} \mid X_n=x_n, X_k=x_k\right) \\ & =\sum_{x_j \in S, 0 \leq j \leq n-1, j \neq k} \mathbb{P}\left(X_{n+1}=x_{n+1}, X_{n-1}=x_{n-1}, \ldots, X_0=x_0 \mid X_n=x_n, X_k=x_k\right) \\ & =\sum_{x_j \in S, 0 \leq j \leq n-1, j \neq k}\left(P\left(X_{n+1}=x_{n+1} \mid X_n=x_n, X_{n-1}=x_{n-1}, \ldots X_j=x_j, \ldots, X_0=x_0\right)\right. \\ & \left.\times P\left(X_{n-1}=x_{n-1}, \ldots, X_j=x_j, \ldots, X_0=x_0 \mid X_n=x_n, X_k=x_k\right)\right) \\ & =P\left(X_{n+1}=x_{n+1} \mid X_n=x_n\right) \\ & \times \sum_{x_j \in S, 0 \leq j \leq n-1, j \neq k} P\left(X_{n-1}=x_{n-1}, \ldots, X_j=x_j, \ldots, X_0=x_0 \mid X_n=x_n, X_k=x_k\right) \\ & =\mathbb{P}\left(X_{n+1}=x_{n+1} \mid X_n=x_n\right). \end{aligned}$ Applying the law of total probability again gives $\begin{aligned} & \mathbb{P}\left(X_{n+m+1}=x_{n+m+1} \mid X_m=x_m, \ldots, X_1=x_1, X_0=x_0\right) \\ & =\sum_{x_{n+m} \in S} \mathbb{P}\left(X_{n+m+1}=x_{n+m+1}, X_{n+m}=x_{n+m} \mid X_m=x_m, \ldots, X_1=x_1, X_0=x_0\right) \\ & =\sum_{x_{n+m} \in S} \mathbb{P}\left(X_{n+m+1}=x_{n+m+1} \mid X_{n+m}=x_{n+m}, X_m=x_m, \ldots, X_1=x_1, X_0=x_0\right) \\ & \quad \times \mathbb{P}\left(X_{n+m}=x_{n+m} \mid X_m=x_{m+\ldots}, X_1=x_1, X_0=x_0\right) \\ & =\sum_{x_{n+m} \in S} \mathbb{P}\left(X_{n+m+1}=x_{n+m+1} \mid X_{n+m}=x_{n+m}\right) \quad \text { (by Markov property) } \\ & \quad \times \mathbb{P}\left(X_{n+m}=x_{n+m} \mid X_m=x_m\right) \quad \text { (by induction hypothesis) } \\ & =\sum_{x_{n+m} \in S} \mathbb{P}\left(X_{n+m+1}=x_{n+m+1} \mid X_{n+m}=x_{n+m}, X_m=x_m\right) \quad \text { (using (2)) } \\ & \quad \times \mathbb{P}\left(X_{n+m}=x_{n+m} \mid X_m=x_m\right) \\ & =\sum_{x_{n+m} \in S} \mathbb{P}\left(X_{n+m+1}=x_{n+m+1}, X_{n+m}=x_{m+m} \mid X_m=x_m\right) \quad \text { (using (1)) } \\ & =\mathbb{P}\left(X_{n+m+1}=x_{n+m+1} \mid X_m=x_m\right) \end{aligned}$