Why do Fisher & $\chi^2$ tests show dependence for simulated Markov chain in nonadjacent observations?

Question

I'm trying to understand Fisher's exact test and the $\chi^2$ test of independence.

Suppose I've got a Markov Chain of first order with the following TPM:

$M = \begin{pmatrix} 0.3 & 0.7 \\ 0.99 & 0.01 \end{pmatrix}$.

I create a path with $N$ observations using the inverse CDF method. I can reproduce almost the same TPM with MLE from the path:

$N=1000: \hat{M} = \begin{pmatrix} 0.27& 0.73\\0.98 & 0.02\end{pmatrix}$

By the way, is there a rule of thumb about what the minimum sample size $N$ is?

Anyway, I know, for a first order Markov process the $X_t \in X$ and $X_{t+1} \in X$ are dependent, but $X_t$ and $X_{t+2}\in X$ are not (how do I write that formally?). If I create the contingency table via:

    [tab,~,p]=crosstab(X(1:end-1),X(2:end)) 
    tab = 
       158   417
       417     8

    p =  1.5748e-110 

    tab2 = full(sparse(X(1:end-1),X(2:end),1))
    tab2 =

       158   417
       417     8

Which should give me the one step contingency table, correct? p is the p-value of the $\chi^2$ test. That is ok so far. But if I use

    [tab,~,p]=crosstab(X(1:end-2),X(3:end)) 
    tab = 
       455   119
       119   106

    p =  4.968e-59 

Shouldn't be that independent?

And if I reduce the sample size to $N=100$ the $p=2.2e-11$ for the two step table. The same occurs with Fisher's test from http://www.mathworks.com/matlabcentral/fileexchange/26883-myfisher

Would anybody please be so kind and explain to me what I'm doing wrong here? Especially why my assumption don't work, or whether my code is wrong?

The background of the whole story is: I have a quite long time series with 4 states, and I need to estimate the minimal Markov chain order.

Thank you very much!

Answer 1

You're simply mistaken.

Unconditionally, $X_t$ and $X_{t-2}$ from a Markov chain aren't independent.

As a result, you'd expect, with sufficiently large samples, to reject a test of independence.

(Conditionally on $X_{t-1}$, $X_t$ doesn't depend on $X_{t-2}$, because all the dependence comes through $X_{t-1}$.)