Two new Markov order estimators

2005/06/04 by Yuval Peres, Peres, Yuval, Paul C. Shields +2 · 1 citation
Computer Science · Mathematics · #62F12 #62M05 #Algorithms and Data Compression #Bayesian Methods and Mixture Models #FOS: Mathematics #Machine Learning and Algorithms #Probability (math.PR) #Statistics Theory (math.ST) #math.PR #math.ST #msc:62F12 #msc:62M05 #stat.TH

paper · pdf · doi:10.48550/arxiv.math/0506080

15 pages

arxiv created 2005/06/04 · openalex publication_date 2005/06/04 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Cited by

• Learning the Markov order of paths in a network

Related

• Markov Chain Order Estimation and Relative Entropy
• On a Class of Markov Order Estimators Based on PPM and Other Universal\n Codes
• Learning the Markov order of paths in a network
• Markov chain order estimation with parametric significance tests of conditional mutual information
• Learning Markov Chain in Unordered Dataset