Large-scale typicality of Markov sample paths and consistency of MDL order estimators

For Markov chains of arbitrary order, with finite alphabet A, almost sure sense limit theorems are proved on relative frequencies of k-blocks, and of symbols preceded by a given k-block, when k is permitted to grow as the sample size n grows. As an application, the consistency of two kinds of minimum description length (MDL) Markov order estimators is proved, with upper bound o(log n), respectively, alpha log n with alpha < 1/log \A\, on the permissible value of the estimated order. It was shown by Csiszar and Shields that in the absence of any bound, or with bound alpha log n with large alpha, consistency falls.