2005/06/30 by Travis Gagie
Computer Science · Mathematics · #Algorithms and Data Compression #Combinatorics #Computability, Logic, AI Algorithms #Computer science #De Bruijn sequence #Discrete mathematics #Entropy (arrow of time) #Kolmogorov complexity #Markov chain #Mathematics #Metric (unit) #Physics #Statistics #cs.IT #math.IT #semigroups and automata theory
paper · pdf · doi:10.1016/j.ipl.2006.04.008
arxiv created 2006/03/09 · openalex publication_date 2006/05/27 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We briefly survey some concepts related to empirical entropy -- normal numbers, de Bruijn sequences and Markov processes -- and investigate how well it approximates Kolmogorov complexity. Our results suggest ℓth-order empirical entropy stops being a reasonable complexity metric for almost all strings of length m over alphabets of size n about when n^ℓ surpasses m.