Large Alphabets and Incompressibility
<|reference_start|>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$.<|reference_end|>
@article{gagie2005large,
    title={Large Alphabets and Incompressibility},
    author={Travis Gagie},
    journal={arXiv preprint arXiv:cs/0506056},
    year={2005},
    doi={10.1016/j.ipl.2006.04.008},
    archivePrefix={arXiv},
    eprint={cs/0506056},
    primaryClass={cs.IT math.IT}
}