Lossless Data Compression Rate: Asymptotics and Non-Asymptotics
This paper considers the distribution of the optimum rate of lossless compression. It shows that in the non-asymptotic regime the fundamental limits of lossless compression with and without prefix constraints are tightly coupled. The authors give an exact analysis of the fundamental limit for arbitrary sources. Gaussian approximations to the distribution of the optimum rate, and the concept of source dispersion are also characterized. Together with the entropy rate, the varentropy rate serves to tightly approximate the fundamental non-asymptotic limits for all but very small block-lengths.