# Markov property for discrete Markov chains. A question about "adjacent random variables"

Consider a discrete Markov chain (with values in $\mathbb R$) $\{X_n:\, n\in\mathbb N\}$: namely the state space $S$ is a countable subset of $\mathbb R$ and the random variables are $X_0, X_1, X_2\ldots$

Now, one definition of Markov property for $\{X_n\}$, assuming the above hypothesis, is the following:

1) For every $n_0,\ldots,n_{k+1}\in\mathbb N$ and every $i_0,i_2,\ldots,i_{k+1}\in S$ $$P(X_{n_{k+1}}=i_{k+1}\,|\, X_{n_0}=i_0,\ldots,X_{n_k}=i_k)=P(X_{n_{k+1}}=i_{k+1}\,|\,X_{n_k}=i_k)$$

I have to show that this property is equivalent to the following different condition involving only "adjacent random variables":

2) For every $k\in\mathbb N$ and every $i_0,i_2,\ldots,i_{k+1}\in S$ $$P(X_{k+1}=i_{k+1}\,|\, X_0=i_0,\ldots, X_k=i_k)=P(X_{k+1}=i_{k+1}\,|\, X_k=i_k)$$

Clearly $1)\Rightarrow 2)$ but I have problems to show the opposite implication. Intuitively the equivalence sounds plausible to me, but I can't write a formal proof.

Let $n_0, n_1, n_2\in\mathbb N$ and $i_0, i_1, i_2 \in S$ be given. We'll expand the expression in the following way.

$$P(X_{n_{2}}=i_{2}\,|\, X_{n_1}=i_1, X_{n_0}=i_0)=$$ $$\frac{P(X_{n_{2}}=i_{2}, X_{n_1}=i_1, X_{n_0}=i_0)}{P(X_{n_1} = i_1, X_{n_0} = i_0)} =$$ $$\frac{\sum_{(k_q)}\sum_{(j_q)} P(X_{n_{2}}=i_{2}, X_{n_{2}-1}=k_{n_2-n_1-1},\dots,X_{n_{1}+1}=k_{1} \mid X_{n_1}=i_1, X_{n_{1}-1}=j_{n_1-n_0-1},\dots,X_{n_{0}+1}=j_{1}, X_{n_0}=i_0) \cdot P(X_{n_1}=i_1, X_{n_{1}-1}=j_{n_1-n_0-1},\dots,X_{n_{0}+1}=j_{1}, X_{n_0}=i_0)} {P(X_{n_1} = i_1, X_{n_0} = i_0)} =$$ $$\frac{\sum_{(k_q)} P(X_{n_{2}}=i_{2}, X_{n_{2}-1}=k_{n_2-n_1-1},\dots,X_{n_{1}+1}=k_{1} \mid X_{n_1}=i_1) \cdot \sum_{(j_q)} P(X_{n_1}=i_1, X_{n_{1}-1}=j_{n_1-n_0-1},\dots,X_{n_{0}+1}=j_{1}, X_{n_0}=i_0)} {P(X_{n_1} = i_1, X_{n_0} = i_0)} =$$ $$\sum_{(k_q)} P(X_{n_{2}}=i_{2}, X_{n_{2}-1}=k_{n_2-n_1-1},\dots,X_{n_{1}+1}=k_{1} \mid X_{n_1}=i_1) =$$ $$P(X_{n_{2}}=i_{2} \mid X_{n_1}=i_1)$$

Equality:

1. Def. of conditional probability.
2. Law of total probability.
3. Hypothesis of "neighbor" Markov Property.
4. Law of total probability, and simplify fraction.

The notation $\sum_{(k_q)}$ and $\sum_{(j_q)}$ means to sum over all paths in the sample space from $i_1$ to $i_2$ and $i_0$ to $i_1$, respectively.

You would then need to repeat this argument via an induction proof. The algebra is more or less the same, although the notation is more verbose. I will fill in the induction portion if you think it would be helpful.