Optimal lossless compression: Source varentropy and dispersion

This work¹ deals with the fundamental limits of strictly-lossless variable-length compression of known sources without prefix constraints. The source dispersion characterizes the time-horizon over which it is necessary to code in order to approach the entropy rate within a pre-specified tolerance. We show that for a large class of sources, the dispersion of the source is equal to the varentropy rate, defined as the asymptotic per-symbol variance of the information random variables. We focus on ergodic Markov chains, whose optimal encodings are shown to be asymptotically normal and to satisfy an appropriate laws of the iterated logarithm.