Large-scale typicality of Markov sample paths and consistency of MDL order estimators
- 7 August 2002
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 48 (6) , 1616-1628
- https://doi.org/10.1109/tit.2002.1003842
Abstract
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, /spl alpha/ log n with /spl alpha/ < 1/log |A|, on the permissible value of the estimated order. It was shown by Csiszar and Shields (see Ann. Statist., vol.28, p.1601-1619, 2000) that in the absence of any bound, or with bound /spl alpha/ log n with large /spl alpha/ consistency fails.Keywords
This publication has 8 references indexed in Scilit:
- Fuzzy estimation of unknown source model for universal codingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- The consistency of the BIC Markov order estimatorThe Annals of Statistics, 2000
- Variable length Markov chainsThe Annals of Statistics, 1999
- The minimum description length principle in coding and modelingIEEE Transactions on Information Theory, 1998
- The context-tree weighting method: basic propertiesIEEE Transactions on Information Theory, 1995
- A universal finite memory sourceIEEE Transactions on Information Theory, 1995
- Deviations from uniformity in random stringsProbability Theory and Related Fields, 1988
- The performance of universal encodingIEEE Transactions on Information Theory, 1981