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 $\ell$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^\ell$ surpasses $m$.