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}}$?


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.