Two new Markov order estimators

Abstract

We present two new methods for estimating the order (memory depth) of a finite alphabet Markov chain from observation of a sample path. One method is based on entropy estimation via recurrence times of patterns, and the other relies on a comparison of empirical conditional probabilities. The key to both methods is a qualitative change that occurs when a parameter (a candidate for the order) passes the true order. We also present extensions to order estimation for Markov random fields.

arXiv comment15 pages

References in corpus (1)

• Consistent estimation of the basic neighborhood of Markov random fields

Cited by in corpus (4)

• Context tree selection and linguistic rhythm retrieval from written texts
• Alignment-Free Sequence Analysis and Applications
• Learning the Markov order of paths in a network
• Bounds for Algorithmic Mutual Information and a Unifilar Order Estimator