Large Sample Properties of Higher Order Markov Models

Abstract

We study large-sample properties of higher-order Markov chains on a finite alphabet $\Sigma$ when the order $m_n$ is allowed to grow with the sequence length $n$. By embedding the process into a first-order chain on ${\Sigma }^{m_n}$ and exploiting return-time decompositions, we establish a central limit theorem for additive functionals ${\sum }_t{g}_n(Y_t^{(n)})$ under natural ergodicity and sparsity conditions. The normalization involves the stationary return time to a suitably chosen state and accommodates triangular arrays with $m_n\to \infty$ and $m_n/n\to 0$. We further illustrate the assumptions in a binary variable length Markov chain (VLMC), deriving explicit lower bounds on stationary masses that yield a concrete growth regime (e.g., $m_n\log m_n/n\to 0$) ensuring the CLT. These results provide asymptotic foundations for inference in sparse/partitioned higher-order models; including VLMCs and sparse Markov models (SMMs) where the effective dimensionality grows with the sample size.