Entropy and the Law of Small Numbers

Abstract

Two new information-theoretic methods are introduced for establishing Poisson approximation inequalities. First, using only elementary information-theoretic techniques it is shown that, when $S_n={\sum }_{i=1}^n{X}_i$ is the sum of the (possibly dependent) binary random variables $X_1,X_2,...,X_n$, with $E(X_i)=p_i$ and $E(S_n)=\la$, then \ben D(P_{S_n}\|\Pol)\leq \sum_{i=1}^n p_i^2 + \Big[\sum_{i=1}^nH(X_i) - H(X_1,X_2,..., X_n)\Big], \een where $D(P_{S_n}\|{Po}(\la))$ is the relative entropy between the distribution of $S_n$ and the Poisson($\la$) distribution. The first term in this bound measures the individual smallness of the $X_i$ and the second term measures their dependence. A general method is outlined for obtaining corresponding bounds when approximating the distribution of a sum of general discrete random variables by an infinitely divisible distribution. Second, in the particular case when the $X_i$ are independent, the following sharper bound is established, \ben D(P_{S_n}\|\Pol)\leq \frac{1}λ \sum_{i=1}^n \frac{p_i^3}{1-p_i}, % \label{eq:abs2} \een and it is also generalized to the case when the $X_i$ are general integer-valued random variables. Its proof is based on the derivation of a subadditivity property for a new discrete version of the Fisher information, and uses a recent logarithmic Sobolev inequality for the Poisson distribution.

15 pages. To appear, IEEE Trans Inform Theory

Cited by in corpus (17)

• Information Theoretic Proofs of Entropy Power Inequalities
• Log-concavity and the maximum entropy property of the Poisson distribution
• Log-concavity, ultra-log-concavity, and a maximum entropy property of discrete compound Poisson measures
• Sharp Bounds on the Entropy of the Poisson Law and Related Quantities
• Thinning, Entropy and the Law of Thin Numbers
• Entropy Bounds for Discrete Random Variables via Maximal Coupling
• A discrete log-Sobolev inequality under a Bakry-Emery type condition
• Monotonic Convergence in an Information-Theoretic Law of Small Numbers
• Entropy Inequalities for Sums in Prime Cyclic Groups
• Majorization and Rényi Entropy Inequalities via Sperner Theory
• Concavity of entropy under thinning
• Discrete versions of the transport equation and the Shepp-Olkin conjecture
• On the Entropy of Sums of Bernoulli Random Variables via the Chen-Stein Method
• A de Bruijn identity for discrete random variables
• Information-theoretic convergence of extreme values to the Gumbel distribution
• Entropy and thinning of discrete random variables
• Relative entropy bounds for sampling with and without replacement