Exact test for Markov order

Shawn D. Pethel, Daniel W. Hahs

We describe an exact test of the null hypothesis that a Markov chain is nth order versus the alternate hypothesis that it is $(n+1)$-th order. The procedure does not rely on asympt…