Large alphabets and incompressibility

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.