On the Entropy of Sums of Bernoulli Random Variables via the Chen-Stein Method

I Introduction

Convergence to the Poisson distribution, for the number of occurrences of possibly dependent events, naturally arises in various applications. Following the work of Poisson, there has been considerable interest in how well the Poisson distribution approximates the binomial distribution. This approximation was treated by a limit theorem in [13, Chapter 8], and later some non-asymptotic theoretical results have studied the accuracy of this approximation. The Poisson approximation and later the compound Poisson approximation have been treated extensively in the probability and statistics literature (see, e.g., –, –, – and references therein).

$\{X_{i}\}_{i=1}^{n}$ are weakly dependent.

This paper provides an information-theoretic study of Poisson approximation, and it combines elements of information theory with the Chen-Stein method. The novelty in this paper, in comparison to previous related works, is related to the derivation of upper bounds on the error that follows from an approximation of the entropy of a sum of possibly dependent and non-identically distributed Bernoulli random variables by the entropy of a Poisson random variable with the same mean (see Theorem 17 and some of its consequences in Section II). The use of these new bounds is exemplified, partially relying on interesting applications of the Chen-Stein method from .

II Error Bounds on the Entropy of the Sum of Bernoulli Random Variables

This section considers the entropy of a sum of (possibly dependent and non-identically distributed) Bernoulli random variables. Section II-A provides a review of some known results on the Poisson approximation, via the Chen-Stein method, that are relevant to the derivation of the new bounds (see [31, Section 2]). Section II-B introduces explicit upper bounds on the error that follows from the approximation of the entropy of a sum of Bernoulli random variables by the entropy of a Poisson random variable with the same mean. Some applications of the new bounds are exemplified in Section II-C.

In the following, the term ‘distribution’ refers to the probability mass function of an integer-valued random variable.

Let $P$ and $Q$ be two probability measures defined on a set $\mathcal{X}$. Then, the total variation distance between $P$ and $Q$ is defined by

where the supermum is taken w.r.t. all the Borel subsets $A$ of $\mathcal{X}$. If $\mathcal{X}$ is a countable set then (1) is simplified to

so the total variation distance is equal to one-half of the $L_{1}$-distance between the two probability distributions.

The following theorem combines [6, Theorems 1 and 2], and its proof relies on the Chen-Stein method:

The ratio between the upper and lower bounds in Theorem 1 is not larger than 32, irrespectively of the values of $\{p_{i}\}$. This shows that these bounds are essentially tight. The upper bound in (3) improves Le Cam’s inequality (see , )) which states that $d_{\text{TV}}(P_{W},\text{Po}(\lambda))\leq\sum_{i=1}^{n}p_{i}^{2}$ so the improvement, for $\lambda\gg 1$, is by the factor $\frac{1}{\lambda}$.

Theorem 1 provides a non-asymptotic result for the Poisson approximation of sums of independent binary random variables via the use of the Chen-Stein method. In general, this method enables to analyze the Poisson approximation for sums of dependent random variables. To this end, the following notation was used in and :

Let $I$ be a countable index set, and for $\alpha\in I$, let $X_{\alpha}$ be a Bernoulli random variable with

where it is assumed that $\lambda\in(0,\infty)$. For every $\alpha\in I$, let $B_{\alpha}$ be a subset of $I$ that is chosen such that $\alpha\in B_{\alpha}$. This subset is interpreted in as the neighborhood of dependence for $\alpha$ in the sense that $X_{\alpha}$ is independent or weakly dependent of all of the $X_{\beta}$ for $\beta\notin B_{\alpha}$. Furthermore, the following coefficients were defined in [2, Section 2]:

where $\sigma(\cdot)$ in the conditioning of (8) denotes the $\sigma$-algebra that is generated by the random variables inside the parenthesis. In the following, we cite [2, Theorem 1] which essentially implies that when $b_{1},b_{2}$ and $b_{3}$ are all small, then the total number $W$ of events is approximately Poisson distributed.

Let $W=\sum_{\alpha\in I}X_{\alpha}$ be a sum of (possibly dependent and non-identically distributed) Bernoulli random variables $\{X_{\alpha}\}_{\alpha\in I}$. Then, with the notation in (4)–(8), the following upper bound on the total variation distance holds:

A comparison of the right-hand side of (9) with the bound in [2, Theorem 1] shows a difference in a factor of 2 between the two upper bounds. This follows from a difference in a factor of 2 between the two definitions of the total variation distance in [2, Section 2] and Definition 1 here. Note however that Definition 1 is consistent with, e.g., .

Theorem 9 forms a generalization of the upper bound in Theorem 1 by choosing $B_{\alpha}=\alpha$ for $\alpha\in I\triangleq\{1,\ldots,n\}$ (note that, due to the independence assumption of the Bernoulli random variables in Theorem 1, the neighborhood of dependence of $\alpha$ is $\alpha$ itself). In this setting, under the independence assumption, $b_{1}=\sum_{i=1}^{n}p_{i}^{2},\quad b_{2}=b_{3}=0$ which therefore gives, from (9), the upper bound in (3).

The following inequality holds (see [11, Theorem 17.3.3]):

Let $P$ and $Q$ be two probability mass functions on a finite set $\mathcal{X}$ such that the $L_{1}$ norm of their difference is not larger than one-half, i.e.,

Then the difference between their entropies satisfies

The bounds on the total variation distance for the Poisson approximation (see Theorems 1 and 9) and the $L_{1}$ bound on the entropy (see Theorem 11) motivate to derive a bound on $|H(W)-H(Z)|$ where $W\triangleq\sum_{\alpha\in I}X_{\alpha}$ is a finite sum of (possibly dependent and non-identically distributed) Bernoulli random variables, and $Z\sim\text{Po}(\lambda)$ is Poisson distributed with mean $\lambda=\sum_{\alpha\in I}p_{\alpha}$. The problem is that the Poisson distribution is defined on a countable set that is infinite, so the bound in Theorem 11 is not applicable for the considered problem of Poisson approximation. This motivates the theorem in the next sub-section. Before proceeding to this analysis, the following maximum entropy result of the Poisson distribution is introduced for the special case where the Bernoulli random variables are independent. This maximum entropy result follows directly from [14, Theorems 7 and 8].

The Poisson distribution $\text{Po}(\lambda)$ has the maximal entropy among all probability distributions with mean $\lambda$ that can be obtained as sums of independent Bernoulli RVs:

where in the above sum, $\{X_{i}\}_{i=1}^{n}$ are independent Bernoulli random variables. Furthermore, since the supremum of the entropy over the set $B_{n}(\lambda)$ is monotonic increasing in $n$, then

Calculation of the entropy of a Poisson random variable: In the next sub-section we consider the approximation of the entropy of a sum of Bernoulli random variables by the entropy of a Poisson random variable with the same mean. To this end, it is required to evaluate the entropy of $Z\sim\text{Po}(\lambda)$. It is straightforward to verify that

so the entropy of the Poisson distribution (in nats) is expressed in terms of an infinite series that has no closed form. Sequences of simple upper and lower bounds on this entropy, which are asymptotically tight, were derived in . In particular, for large values of $\lambda$,

II-B New Error Bounds on the Entropy

We introduce here new error bounds on the entropy of Bernoulli sums. Due to space limitations, the proofs are omitted. The proofs are available in the full paper version (see [31, Section II.D]).

Let $I$ be an arbitrary finite index set with $m\triangleq|I|$. Under the assumptions of Theorem 9 and the notation used in Eqs. (4)–(8), let

The following corollary follows from Theorems 4 and 17, and Remark 3:

Consider the setting in Theorem 17, and assume that the Bernoulli random variables $\{X_{\alpha}\}_{\alpha\in I}$ are also independent. If $\left(\frac{1-e^{-\lambda}}{\lambda}\right)\;\sum_{\alpha\in I}p_{\alpha}^{2}\leq\frac{1}{4}$ and $\lambda\leq m-1$ then, for $Z\sim\text{Po}(\lambda)$,

The following bound forms a possible improvement of the result in Corollary 1. It combines the upper bound on the total variation distance in [6, Theorem 1] (see Theorem 1 here) with the upper bound on the total variation distance in [8, Eq. (30)]. It is noted that the bound in [8, Eq. (30)] improves the bound in [27, Eq. (10)] (see also [28, Eq. (4)]).

Assume that the conditions in Corollary 1 are satisfied. Then, the following inequality holds:

if $g(\underline{p})\leq\frac{1}{2}$ and $\lambda\leq m-1$, where

Furthermore, the condition $\lambda\leq m-1$ is mild since $|I|=m$ and the probabilities $\{p_{\alpha}\}_{\alpha\in I}$ should be typically small for the Poisson approximation to hold.

Proposition 1 improves the bound in Corollary 1 only if $\theta$ is below a certain value that depends on $\lambda$. The maximal improvement that is obtained by Proposition 1, as compared to Corollary 1, is in the case where $\theta\rightarrow 0$ and $\lambda\rightarrow\infty$, and the corresponding improvement in the value of $g(\underline{p})$ is by a factor of $\frac{3}{4e}\approx 0.276$.

II-C Some Applications of the New Error Bounds on the Entropy

In the following, the use of Theorem 17 is first exemplified when the Bernoulli random variables are independent. It is also exemplified in a case from [2, Section 3] where dependence among the Bernoulli random variables exists. The use of Theorem 17 is exemplified for the calculation of error bounds on the entropy via the Chen-Stein method.

Let $W=\sum_{i=1}^{n}X_{i}$ be a sum of $n$ independent Bernoulli random variables where $X_{i}\sim\text{Bern}(p_{i})$ for $i=1,\ldots,n$. The calculation of the entropy of $W$ involves the numerical computation of the probabilities

whose computational complexity is high for very large values of $n$, especially if the probabilities $p_{1},\ldots,p_{n}$ are not the same. The bounds in Corollary 1 and Proposition 1 enable to get rigorous upper bounds on the accuracy of the Poisson approximation for $H(W)$. As was explained earlier in this section, the bound in Proposition 1 may only improve the bound in Corollary 1. Lets exemplify this in the following case: Suppose that

The entropy of $Z\sim\text{Po}(\lambda)$ is $H(Z)=8.327\,\text{nats}$. Corollary 1 gives that $0\leq H(Z)-H(W)\leq 0.588\,\text{nats}$ and Proposition 1 improves it to $0\leq H(Z)-H(W)\leq 0.205\,\text{nats}.$ Hence, $H(W)\approx 8.224\,\text{nats}$ with a relative error of at most $1.2\%.$ We note that by changing the values of $a$ and $n$ to $10^{-14}$ and $10^{12}$, respectively, it follows that $H(W)\approx 12.932\,\text{nats}$ with a relative error of at most $0.04\%$. The enhancement of the accuracy of the Poisson approximation in the latter case is consistent with the law of small numbers (see, e.g., and references therein).

This problem, which appears in [2, Example 1], is described as follows: On the cube $\{0,1\}^{n}$, assume that each of the $n2^{n-1}$ edges is assigned a random direction by tossing a fair coin. Let $k\in\{0,1,\ldots,n\}$ be fixed, and denote by $W\triangleq W(k,n)$ the random variable that is equal to the number of vertices at which exactly $k$ edges point outward (so $k=0$ corresponds to the event where all $n$ edges, from a certain vertex, point inward). Let $I$ be the set of all $2^{n}$ vertices, and $X_{\alpha}$ be the indicator that vertex $\alpha\in I$ has exactly $k$ of its edges directed outward. Then $W=\sum_{\alpha\in I}X_{\alpha}$ with

This implies that $\lambda={{n}\choose{k}}$ (since $|I|=2^{n}$). Clearly, the neighborhood of dependence of a vertex $\alpha\in I$, denoted by $B_{\alpha}$, is the set of vertices that are directly connected to $\alpha$ (including $\alpha$ itself since Theorem 9 requires that $\alpha\in B_{\alpha}$). It is noted, however, that $B_{\alpha}$ in [2, Example 1] was given by $B_{\alpha}=\{\beta:\,|\beta-\alpha|=1\}$ so it excluded the vertex $\alpha$. From (6), this difference implies that $b_{1}$ in their example should be modified to

so $b_{1}$ is larger than its value in [2, p. 14] by a factor of $1+\frac{1}{n}$ which has a negligible effect if $n\gg 1$. As is noted in [2, p. 14], if $\alpha$ and $\beta$ are two vertices that are connected by an edge, then a conditioning on the direction of this edge gives that

for every $\alpha\in I$ and $\beta\in B_{\alpha}\setminus\{\alpha\}$, and therefore, from (7),

Finally, as is noted in [2, Example 1], $b_{3}=0$ (this is because the conditional expectation of $X_{\alpha}$ given $(X_{\beta})_{\beta\in I\setminus B_{\alpha}}$ is, similarly to the un-conditional expectation, equal to $p_{\alpha}$; i.e., the directions of the edges outside the neighborhood of dependence of $\alpha$ are irrelevant to the directions of the edges connecting the vertex $\alpha$).

In the following, Theorem 17 is applied to get a rigorous error bound on the Poisson approximation of the entropy $H(W)$. Table I presents numerical results for the approximated value of $H(W)$, and an upper bound on the maximal relative error that is associated with this approximation. Note that, by symmetry, the cases with $W(k,n)$ and $W(n-k,n)$ are equivalent, so $H\bigl(W(k,n)\bigr)=H\bigl(W(n-k,n)\bigr).$

II-D Generalization: Bounds on the Entropy for a Sum of Non-Negative, Integer-Valued and Bounded Random Variables

We introduce in [31, Section II-E] a generalization of the bounds in Section II-B that considers the accuracy of the Poisson approximation for the entropy of a sum of non-negative, integer-valued and bounded random variables.

This generalization is enabled via the combination of the proof of Theorem 17 for sums of Bernoulli random variables with the approach of Serfling in [32, Section 7].

References