Using $\chi^2$ to compare two Markov transition matrices

Question

I have a set of observed Markov sequences for which I have calculated first and second order transition matrices:

$$M={P}(X_i=x_i|X_{i-1}=x_j)$$ and $$M^2=P(X_i=x_i|X_{i-1}=x_j,\,X_{i-2}=x_i )$$.

I then produced a series of Markov chains based on the transition matrix $M$ and hence recalculated the empirical transition matrix $M^2$ based on this new data calling it $\tilde M^2$ and would like to compare it against the expected $M^2$.

Is the $\chi^2$ test appropriate here? ie. $\displaystyle \sum \dfrac{M^2_{ij}-\tilde M^2_{ij}}{\tilde M^2_{ij}}$?

Answer 1

It looks as though you would like to use the Pearson $\chi^2$ test to assess whether a sample $x_1,...,x_n$ that is taken from a first-order chain with transition probabilities given by $M$ is well fit by the second order chain with transition probabilities given by $M^2$.

The notation you are using is a little confusing only because it seems to imply matrix multiplication. What I understand you to mean is that if I collapse transition probabilities in $M^2$ then I'll get the transition probabilities given in $M$.

Is the $\chi^2$ test appropriate here?

It depends on what you are testing. But, I think in your case that the idea is good.

The form of the $\chi^2$ test should be a bit different. For example, see the Wikipedia entry on Pearson's chi-squared test. If the expected values are denoted $E_\alpha$ and the observed values $O_\alpha$, the form of the test should be $$X^2 =\sum_\alpha \frac{\left(O_\alpha - E_\alpha\right)^2}{E_\alpha}.$$

Now, we need to think of the second-order chain in its flattened first-order form. That is, the matrix of transition probabilities consists of the bigram transition probabilities.

If we let $f_{ij}$ be the frequencies of observed bigram transitions taken from the sample $x_1,...,x_n$, $f_{i}$ the observed frequencies of bigrams, and $p_{ij}$ the second-order transition probabilities given in $M^2$, then we can calculate the Pearson $\chi^2$ statistic $$X^2 = \sum_{ij} \frac{\left(f_{ij} - f_{i}p_{ij}\right)^2}{ f_{i}p_{ij}},$$ and per Billingsley (1960) $$X^2 \sim \chi^2_{d-s},$$ where $d$ is the number of positive entries in the transition matrix $M^2$ and $s$ is the number of unique bigrams.

This gives an evaluation of how well the distribution $M^2$ fits the data $x_1,...,x_n$.

Billingsley credits Bartlett (1951) with this result, so as usual these days we are looking at material that has been developed some time ago! Billingsley also notes that the usual $\chi^2$ test on values from a Markov chain may be interpreted as a test for independent sampling given that the sampling is derived from a first-order Markov chain.

MS Bartlett (1951) The frequency goodness of fit test for probability chains. Proc. Camb. Phil. Soc. 47: 86--95.

P Billingsley (1960) Statistical methods in Markov chains. Technical Report P-2092. The RAND Corporation.