# Significance testing for Markov chain transition probabilities

The question

How can I calculate p values for individual transitions in a Markov chain? I want to test the null hypothesis that the probability of entering state $B$ from previous state $A$ is less than or equal to the overall probability of being in state $B$.

Details

I have an observed sequence of discrete states and am fitting a first order, stationary Markov chain. I'd like to calculate a matrix of p values (one for each possible transition). Say the state at time $t$ is $S_t$. Given states $A$ and $B$, I want to test the null hypothesis that $P(S_t=B \mid S_{t-1}=A) \le P(S_t=B)$ against the alternative hypothesis that $P(S_t=B \mid S_{t-1}=A) > P(S_t=B)$.

There are a couple hundred states. The 'true' transition matrix of the data-generating process is very sparse, meaning that each state can transition to only a few other states. All states transition to themselves with high probability, but there are no absorbing states. The data contain ~10,000 time points, but some transitions may only be observed several times. So, I'm probably not in the asymptotic regime.

The literature

The closest method I've found is described in:

Vautard et al. (1990). Statistical significance test for transition matrices of atmospheric Markov chains.

They randomly permute the sequence of observed states and estimate transition probabilities from the shuffled data. For each pair of states $(A, B)$, they calculate a p value as the fraction of shuffles for which the estimated $A \rightarrow B$ transition probability exceeds that of the original data. My hesitation about this method is that 1) They don't clearly state a null hypothesis. 2) The permutation destroys temporal dependence between all states. But, I can imagine many more models where some states exhibit temporal dependence and others don't. The method doesn't seem to be counting these cases, but I don't know whether it matters.

Another paper:

Anderson and Goodman (1957). Statistical inference about Markov chains.

They give a $\chi^2$ test for the hypothesis that particular transition probabilities have particular values. Maybe I could use this to compare $P(S_t=B \mid S_{t-1}=A)$ to the estimated marginal probability of state $B$, but this doesn't seem to take into account the uncertainty of estimating $P(S_t=B)$ from the data.

• I am experiencing the same problem and don't seem to find an appropriate solution, I found something here lexjansen.com/sugi/sugi13/sd/204-13.pdf but looks a bit dodgy, if anyone has developed a good easy system please share the knowledge :) Dec 19, 2020 at 22:34

I had the same problem, you can take into account the uncertainty of estimating $P(S_t=B)$ from the data by doing a two sample $\chi^2$ test for the hypothesis test. Thus instead of $P(S_t=B)$, you use it as a sample (number times being in B and the total number of events in you chain)
• Thanks for your answer. This sounds like an interesting approach, and I'd like to understand it better. AFAIK, $\chi^2$ tests are a broad category. What specific variety should be used? If I separately test the transition counts between each pair of states, is there no need to account for the constraint that they must sum to the total number of times being in each state? Is there a reference in the literature for this approach? Mar 19, 2017 at 22:46