2017/04/28 by Maciej Skórski, Skorski, Maciej
Physics and Astronomy · #Advanced Thermodynamics and Statistical Mechanics #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.1704.09007
openalex publication_date 2017/04/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The weak law of large numbers implies that, under mild assumptions on the source, the Renyi entropy per produced symbol converges (in probability) towards the Shannon entropy rate. This paper quantifies the speed of this convergence for sources with independent (but not iid) outputs, generalizing and improving the result of Holenstein and Renner (IEEE Trans. Inform. Theory, 2011). (a) we characterize sources with slowest convergence (for given entropy): their outputs are mixtures of a uniform distribution and a unit mass. (b) based on the above characterization, we establish faster convergences in high-entropy regimes. We discuss how these improved bounds may be used to better quantify security of outputs of random number generators. In turn, the characterization of "worst" distributions can be used to derive sharp "extremal" inequalities between Renyi and Shannon entropy. The main technique is non-convex programming, used to characterize distributions of possibly large exponential moments under certain entropy.