Large Alphabets and Incompressibility

Travis Gagie

doi:10.1016/j.ipl.2006.04.008

paper

Large Alphabets and Incompressibility

arXiv:cs/0506056 · doi:10.1016/j.ipl.2006.04.008

Abstract

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$ .