The Interplay Between Entropy and Variational Distance
Authors:
- 18 November 2010
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 56 (12) , 5906-5929
Abstract
The relation between the Shannon entropy and variational distance, two fundamental and frequently-used quantities in information theory, is studied in this paper by means of certain bounds on the entropy difference between two probability distributions in terms of the variational distance between them and their alphabet sizes. We also show how to find the distribution achieving the minimum (or maximum) entropy among those distributions within a given variational distance from any given distribution. These results are applied to solve a number of problems that are of fundamental interest. For entropy estimation, we obtain an analytic formula for the confidence interval, solving a problem that has been opened for more than 30 years. For approximation of probability distributions, we find the minimum entropy difference between two distributions in terms of their alphabet sizes and the variational distance between them. In particular, we show that the entropy difference between two distributions that are close in variational distance can be arbitrarily large if the alphabet sizes of the two distributions are unconstrained. For random number generation, we characterize the tradeoff between the amount of randomness required and the distortion in terms of variation distance. New tools for non-convex optimization have been developed to establish the results in this paper.Keywords
This publication has 17 references indexed in Scilit:
- Estimating Entropy Rates with Bayesian Confidence IntervalsNeural Computation, 2005
- CONTINUITY OF A CLASS OF ENTROPIES AND RELATIVE ENTROPIESReviews in Mathematical Physics, 2004
- Universal Entropy Estimation Via Block SortingIEEE Transactions on Information Theory, 2004
- Estimation of Entropy and Mutual InformationNeural Computation, 2003
- Convergence properties of functional estimates for discrete distributionsRandom Structures & Algorithms, 2001
- Basic Concepts, Identities and Inequalities - the Toolkit of Information TheoryEntropy, 2001
- Simulation of random processes and rate-distortion theoryIEEE Transactions on Information Theory, 1996
- Approximation theory of output statisticsIEEE Transactions on Information Theory, 1993
- Estimation of entropy of a binary variable: Satisfying a reliability criterionBiological Cybernetics, 1973
- On a Statistical Estimate for the Entropy of a Sequence of Independent Random VariablesTheory of Probability & Its Applications, 1959