# Markov chains - how to translate mathematically the fact that the state at $n+1$ only depends on the state at $n$? [closed]

In a Markov chain of, say, three states $$1,2,3$$, when proving that the probabilistic state at $$n+1$$ ($$\pi_n$$) is equal to the probabilistic state at $$n$$ times the transition matrix, one has to use the total probability law as such: $$p(X_{n+1}=1) = p(X_{n+1} = 1 | X_{n} = 1) p(X_n =1) + p(X_{n+1} = 1 | X_{n} = 2) p(X_n =2) +p(X_{n+1} = 1 | X_{n} = 3) p(X_n =3)$$

Note that I stopped at $$p(X_n=1)$$, and I didn't write things like $$p(X_n=1)= p(X_n=1 |X_{n-1}=1)+p(X_n=1 |X_{n-1}=2)+p(X_n=1 |X_{n-1}=3)$$.

One could justify this by saying that in a Markov chain, the state $$n+1$$ only depends on the state $$n$$. But I feel like this will be not enough for the potentially very curious student, who would like to see it through a proof.

What would be such a proof ?

Here is my try:

Noting:

• $$A=p(X_n=1 | X_{n-1}=1)$$
• $$B=p(X_n=1 | X_{n-1}=2)$$
• $$C=p(X_n=1 | X_{n-1}=3)$$
• $$A'=p(X_n=2 | X_{n-1}=1)$$
• $$B'=p(X_n=2 | X_{n-1}=2)$$
• $$C'=p(X_n=2 | X_{n-1}=3)$$
• $$A''=p(X_n=3 | X_{n-1}=1)$$
• $$B''=p(X_n=3 | X_{n-1}=2)$$
• $$C''=p(X_n=3 | X_{n-1}=3)$$

I arrived at the conclusion, assessing $$p(X_2=1)$$, that:

$$p(X_2=1)=A(Ap(X_0=1) +Bp(X_0=2) + Cp(X_0=3))+B(A'p(X_0=1) +B'p(X_0=2) + C'p(X_0=3)) + C(A''p(X_0=1) +B''p(X_0=2) + C''p(X_0=3))$$

From there I wanted to use the fact that $$A+B+C=1$$ and $$A'+B'+C'= 1$$ and $$A''+B''+C''=1$$, but I don't know where to apply it.

My goal is to show that $$p(X_2=1)$$ only depends on $$X_1$$ (and not on $$X_0$$).

PS: Markov chains (and the proof that the probabilistic state at $$n+1$$ relates to the probabilistic state at $$n$$ via the transition matrix) is in the program of (certain classes of) high-school seniors, in my country.

• Why did you post in MathEducators? This looks to me like it belongs in Math.StackExchange instead. I don't see anything relating to pedagogy, different teaching approaches, etc. You can ask a moderator to move it, or if noone else has comments or answers, you might be able to simply delete it and repost it there. Commented Apr 14 at 15:29
• What country do you live in? Markov chains are to be solved, using eigenvalue decomposition and Taylor expansion for calculating powers of matrices. This looks too high for secondary education, in my opinion. Commented Apr 30 at 9:10

I'll answer this question because the given scenario is really about a curious student having a misconception about Markov chains.

You can't "prove" that in a Markov chain, the state $$n+1$$ only depends on the state $$n.$$ That's literally baked into the definition of a Markov chain:

$$p(X_{n+1} | X_n, X_{n-1}, ...) = p(X_{n+1} | X_n)$$

The particular attempted proof is doomed to failure because $$p(X_2)$$ does depend on $$X_0.$$ Not explicitly, but implicitly.

Here's an example.

• Consider the following Markov process: start at $$0$$ and repeatedly either add $$1$$ or subtract $$1$$ with equal probability. Then $$X_0 = 1,$$ and $$p(X_1 = 1) = 0.5,$$ and $$p(X_2 = 2) = 0.25.$$

• In this example, if we started at $$-1$$ instead of $$0,$$ then we'd have $$X_0 = -1,$$ and $$p(X_1 = 1) = 0,$$ and $$p(X_2 = 2) = 0.$$

• So, the value of $$X_0$$ does affect the distribution of $$X_2.$$

Another way to think about it: $$p(X_2)$$ depends on $$X_0$$ because $$p(X_2)$$ depends on $$X_1,$$ and $$p(X_1)$$ depends on $$X_0.$$ It's just that the transition probability $$p(X_2 | X_1)$$ does not depend on $$X_0.$$