test if a markov chain is equal to a theoretical one

Question

I have got an empirical transitions count matrix Q. I have a theoretical first order Markov chain P. Say N is the number of transitions. I would like to test if Q is compatible with P. Is it correct to find the theoretical count transition matrix (N*P) calculating the chi-square statistics, $\sum_{i,j}^{K} \frac{(Q_{ij}-(N*P_{ij}))^2}{N*P_{ij}}$, and then calculating the p-value of a $\chi^2$ distribution with $K*(K-1)$ degrees of freedom?

Answer 1

Assuming your matrices are something like $$P_{ij}=\Pr[j\mid\!i] \,,\, Q_{ij}=\sum_{t=1}^N\big[x_t=i\,\&\,x_{t+1}=j\,\big]$$ then you could interpret each row $i$ as a multinomial distribution with parameters $$p_i=P_{i,:} \,,\, n_i=\sum_{j=1}^{K}Q_{ij}$$

I am not sure that you can lump all of the rows together, because the "number of trials" will vary between rows.

For example say $K=3$ and your data is $x=[1,1,2,1,2,3,1,2]$. So there are $N=7$ transitions, with $n_1=4$ coming from $x=1$, but $n_2=2$ from $x=2$ and only and $n_3=1$ from $x=3$. So I would think your confidence in $\hat{p}_1$ should generally be higher than your confidence in $\hat{p}_3$.

(In the extreme case, maybe for this example $K$ was actually $4$, but you have no data at all on those transitions, as $n_4=0$. Treating "absence of evidence as evidence of absence" would seem problematic to me here.)

I am not very familiar with chi-squared tests, but this suggests you might want to treat the rows independently (i.e. sum only over $j$, and use $n_i$ rather than $N$). This reasoning does not seem specific to the chi-squared test, so should also apply to any other significance test you might use (e.g. exact multinomial).

The key issue is that the transition probabilities are conditional, so for each matrix-entry only the transitions which satisfy its pre-condition are relevant. Indeed, presumably the transition matrix will satisfy $\sum_jP_{ij}=1$, hence the "empirical transition matrix" should be $\hat{P}_{ij}=Q_{ij}/n_i$.

---

Update: In response to query by OP, a clarification on the "test parameters".

If there are $K$ states in the Markov chain, i.e. $P\in\mathbb{R}^{K\times{K}}$, then for row $i$, the corresponding multinomial distribution will have probability vector $p_i\in\mathbb{R}^K$ and number of trials $n_i\in\mathbb{N}$, given above.

So there will be $K$ categories, and the probability vector $p_i$ will have $K-1$ degrees of freedom, as $\sum_{j=1}^K(p_i)_j=1$. So for row $i$ the corresponding $\chi^2$ statistic would be $$\chi^2_i=\sum_j\frac{\left(Q_{ij}-n_iP_{ij}\right)^2}{n_iP_{ij}}$$ which will asymptotically follow a chi-squared distributed with $K-1$ degrees of freedom (as stated here and here). See also here for a discussion of when the $\chi^2$ test is appropriate, and alternative tests which may be more appropriate.

It may be possible to do a "lumped test", assuming $\chi^2_P=\sum_i\chi^2_i$ follows a chi-squared distribution with $K(K-1)$ dof's (i.e. summing dofs over rows). However I am not certain if the $\chi^2_i$ can be treated as independent. In any case, the row-wise tests would seem to be more informative, so may be preferable to a lumped test.