Proof that a stochastic process isn't a Markov Process

[gesteves]

I've been trying to solve this problem for a week now, but haven't been able to. Basically I need to prove that a certain process satisfies Chapman-Kolmogorov equations, yet it isn't a Markov Process (it doesn't satisfy the Markovian Property).

I attached the problem as a .doc below.

Please, I really need a little help here.

[Wong]

hi gesteves!

I read your question, and I think it is readily seen to be not markov (because it is easily seen that P(X_{3(m-1)+3}=1|X_{3(m-1)+2}=1 \mbox{ and }X_{3(m-1)+1}=1) does not equal P(X_{3(m-1)+3}=1|X_{3(m-1)+2}=1)). In other words, since X_{3(m-1)+3}, X_{3(m-1)+2}, X_{3(m-1)+1} are giving information about the *same draw* from the mth box, most probably these variables are not independent and the proof should take into account of this.

Also note that X_{3(n-1)+i}, X_{3(m-1)+j}, 1\leq i, j\leq 3 are independent when m and n are different, as they correspond to different draws.

Since X_{3(n-1)+i}, X_{3(m-1)+j}, 1\leq i, j\leq 3 are independent when m and n are different, then P(X_{3(n-1)+i}=l|X_{3(m-1)+j}=k) = P(X_{3(n-1)+i}=l) = \frac{1}{2}, 0\leq l,k\leq 1 for different m and n.

As to the case when m and n are the same, it is necessary to calculate the probability explicity. But amazingly you will find that P(X_{3(m-1)+i}=l|X_{3(m-1)+j}=k)=\frac{1}{2}, 1\leq i,j\leq 3, 0\leq l,k \leq 1. For example, P(X_{3(1-1)+2}=1|X_{3(m-1)+1}=1)=P(\mbox{1 or 2 in the first draw}|\mbox{1 or 4 in the first draw}) = \frac{1}{2}.

Since all conditional probabilities are essentially 1/2, I think the assertion thus holds.

[gesteves]

Hi Wong,

Thanks for your quick reply! If I understood correctly, all I need to prove that it isn't a Markov Process is a counterexample that shows that P(X_{3(m-1)+3}=1|X_{3(m-1)+2}=1 \mbox{ and }X_{3(m-1)+1}=1) doesn't equal P(X_{3(m-1)+3}=1|X_{3(m-1)+2}=1). For m = 1, P(X_{3}=1|X_{2}=1 \mbox{ and }X_{1}=1) = 0 and P(X_{3}=1|X_{2}=1)=1/2. Therefore it isn't a Markov Process.

But how can I prove that it satisfies Chapman-Kolmogorov? I'll try to prove it on my own, but I could use some pointers.

Thanks in advance.

[Wong]

Yes, gesteves, you got the non-markov part.

As for the Chapman-Kolmogorov part, you may first think of the form of the equation. If I am not mistaken, the Chapman-Kolmogorov equation says that P(X_{m+n+l}=i|X_{l}=j) = \sum_{k}P(X_{m+n+l}=i|X_{m+l}=k)P(X_{m+l}=k|X_{l}= j). In my first post, I already gave you the various conditional probabilities for the equation. You may just "plug in" and see whether the LHS agrees with the RHS.

[gesteves]

I finally finished it. Thanks for all your help.