2020/03/10 by Łukasz Dębowski, Dębowski, Łukasz · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #60G10 #62M05 #94A17 #94A29 #Algorithms and Data Compression #Bayesian Methods and Mixture Models #Cellular Automata and Applications #FOS: Computer and information sciences #Fractal and DNA sequence analysis #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.2003.04754
openalex publication_date 2020/03/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We investigate a class of estimators of the Markov order for stationary\nergodic processes which form a slight modification of the constructions by\nMerhav, Gutman, and Ziv in 1989 as well as by Ryabko, Astola, and Malyutov in\n2006 and 2016. All the considered estimators compare the estimate of the\nentropy rate given by a universal code with the empirical conditional entropy\nof a string and return the order for which the two quantities are approximately\nequal. However, our modification, which we call universal Markov orders,\nsatisfies a few attractive properties, not shown by the mentioned authors for\ntheir original constructions. Firstly, the universal Markov orders are almost\nsurely consistent, without any restrictions. Secondly, they are upper bounded\nasymptotically by the logarithm of the string length divided by the entropy\nrate. Thirdly, if we choose the Prediction by Partial Matching (PPM) as the\nuniversal code then the number of distinct substrings of the length equal to\nthe universal Markov order constitutes an upper bound for the block mutual\ninformation. Thus universal Markov orders can be also used indirectly for\nquantification of long memory for an ergodic process.\n