Why are the $n$-step transition probabilities well defined?

Question

I was reading a proof for the Chapman-Kolmogorov equations and now I understand why it is the case that for a discrete-time homogeneous Markov Chain $X=(X_n) _{n\geq 0}$ (with state space $S$) the following result holds: $$\mathbb{P} (X_{m+n} | X_0 = i) = \sum _{k\in S} \mathbb{P} (X_{m+n} = j | X_m = k) \cdot \mathbb{P} (X_m = k | X_0 = i) \ \text{ for }\ m,n\geq 0, i,j\in S \text{.}$$ But I find it difficult to understand that $\mathbb{P} (X_{m+n} = j | X_m =k)$ is the same as the $n$-step transition probability $\mathbb{P} (X_{n} = j | X_0 =k)$. I have the feeling that it must be very easy to prove this and I have tried to prove this with induction to $n$, but I just do not see it. So my question is: how can I prove that $\mathbb{P} (X_{m+n} = j| X_m=k) = \mathbb{P} (X_n = j | X_0 = i)$?

Answer 1

You can prove that the $n$-step transition probabilities are time-independent, i.e., $$ \text{For each $n$:}\ P(X_{m+n}=x_n \mid X_m=x_0) = P(X_n=x_n\mid X_0=x_0)\ \text{for all $m\ge0$} $$ by induction on $n$. For $n=1$ this follows from the definition of the (one-step) transition probabilities. If the claim holds for $n$, then for any $m\ge0$:

$$\begin{align} &P(X_{m+n+1}=x_{n+1}\mid X_m=x_0)\\ &\stackrel{(1)}=\sum_{x_n}P(X_{m+n+1}=x_{n+1},X_{m+n}=x_n\mid X_m=x_0)\\ &\stackrel{(2)}=\sum_{x_n}P(X_{m+n+1}=x_{n+1}\mid X_{m+n}=x_n,X_m=x_0) P(X_{m+n}=x_n\mid X_m=x_0)\\ &\stackrel{(3)}=\sum_{x_n}P(X_{m+n+1}=x_{n+1}\mid X_{m+n}=x_n) P(X_{m+n}=x_n\mid X_m=x_0)\\ &\stackrel{(4)}=\sum_{x_n}P(X_{1}=x_{n+1}\mid X_{0}=x_n) P(X_{n}=x_n\mid X_0=x_0).\tag{*}\\ \end{align} $$ In step (1) we are summing over the possible values for $X_{m+n}$. In (2) we are conditioning on $X_{m+n}=x_n$. In (3) we apply the Markov property, and step (4) uses the induction hypothesis and the base case $n=1$. Finally we note that (*) is free of $m$, which means we get the same result for $m=0$ as for any other $m$. That is, $$P(X_{m+n+1}=x_{n+1}\mid X_m=x_0) =P(X_{n+1}=x_{n+1}\mid X_0=x_0),$$ as desired.