# Exact test for Markov order

arXiv: https://arxiv.org/abs/1302.1500 · HTML: https://mlsanity.com/paper/1302.1500/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Feb 2013.

## Built on by (most cited first, 1 of 1)

- [Exact Distinguishability in Non-Markovian Decision Processes](https://mlsanity.com/paper/2610.01527/) (2026)

## Abstract (arXiv)

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 asymptotic properties, but instead builds up the test statistic distribution via surrogate data and is valid for any sample size. Surrogate data are generated using a novel algorithm that guarantees, per shot, a uniform sampling from the set of sequences that exactly match the nth order properties of the observed data.