Markov Memoryless Property confusion with counterexample

Question

Consider the following transitions:

$$P(X_2=d|X_1=b)=P(X_1=d|X_0=b)=3/4$$

By Markov property, all what happened before $X_1=b$ doesn't matter:

So when I see $P(X_2=d|X_1=b)$ I know that I can choose $X_0$ in all possible ways.

$$P(X_2=d|X_1=b)=P(X_2=d|X_1=b,X_0=a) + P(X_2=d|X_1=b,X_0=b)=$$ $$P(X_2=d|X_1=b)=1*2/3*3/4+1*1/4*3/4=11/16$$ $$\ne P(X_1=d|X_0=b)$$

Did I actually give a counterexample or what am I confusing here ?

Answer 1

Given that $X_1=b$, it's true that $X_0$ must have been either $a$ or $b$. However, there's no rule that allows you to write $$ P(X_2=d\mid X_1=b)=P(X_2=d\mid X_1=b,X_0=a) + P(X_2=d\mid X_1=b,X_0=b).\tag1 $$ Indeed, by the Markov property, the RHS of (1) is two copies of the LHS, which is impossible.

The second mistake that you made was in the evaluation $P(X_2=d\mid X_1=b,X_0=a)$. You evaluated $P(X_2=d, X_1=b\mid X_0=a)$ instead.

Answer 2

$P(X_2=d|X_1=b)=P(X_1=d|X_0=b)=3/4$ is not a statement for the Markov Property.

Suppose I tell you that at the current time-step, you're in a given state. This information is sufficient for you to calculate the probabilities of being in different states at the next time-step. Hence, the process is Markov.

In your case, the statement for Markovness would be: $P(X_2=d|X_1=b)=P(X_2=d|X_1=b,X_0=a)=P(X_2=d|X_1=b,X_0=b)$

Let me know if something is still unclear. I'll be happy to clarify :)