Entropy Bounds for Discrete Random Variables via Maximal Coupling

I Introduction

The question of quantifying the continuity (or lack of it) of entropy, with respect to natural topologies on discrete probability distributions is fundamental. This question has been studied in the literature for the topology induced by the total variation distance, and there it is well known that the entropy is continuous when the alphabet is finite, but it is not necessarily continuous when the alphabet is countably infinite. The interplay between the difference of the entropies of two discrete random variables and their total variation distance has been extensively studied (see, e.g., [8, Theorem 17.3.3], , [10, Lemma 1], –, , –, , , ).

New bounds on the difference of the entropies of two discrete random variables are derived in this work. The bounds apply to random variables with finite or countably infinite alphabet, and they improve some previously reported bounds. The derivation of the new bounds relies on the notion of maximal coupling, which is also known to be useful for the derivation of error bounds via Stein’s method (see, e.g., [31, Chapter 2] and ). Stein’s method also serves to exemplify the use of the new bounds in the context of the Poisson approximation. The link between Stein’s method and information theory was pioneered in in the context of the compound Poisson approximation, and a recent work (that was done independently and in parallel to this work) further links between information theory and Stein’s method for discrete probability distributions.

To set definitions and notation, we introduce essential terms that serve to derive the new bounds in this paper.

A coupling of a pair of two random variables $(X,Y)$ is a pair of two random variables $(\hat{X},\hat{Y})$ with the same marginal probability distributions as of $(X,Y)$.

Let $X$ and $Y$ be discrete random variables that take values in a set $\mathcal{A}$, and let $P_{X}$ and $P_{Y}$ be their respective probability mass functions. The local distance and total variation distance between $X$ and $Y$ are, respectively,

The local distance is the $l^{\infty}$ distance between the probability mass functions, and the total variation distance is half the $l^{1}$ distance. The factor of one-half on the right-hand side of (2) normalizes the total variation distance to get values between zero and one. It is noted that the notation in the literature is not consistent, with a factor 2 on the right-hand side of (2) often being present or not. It is easy to show (see, e.g., [13, Lemma 5.4 on pp. 133–134]) that with this definition

From the last equality and the definition of the local distance in (1), it follows that $d_{\text{loc}}(X,Y)\leq d_{\text{TV}}(X,Y).$

The following theorem is a basic result on maximal coupling that also suggests, as part of its proof, a construction for maximal coupling (see, e.g., [31, Chapter 2]). We later rely on this particular construction to derive in Section III some new bounds on the entropy of discrete random variables.

Let $X$ and $Y$ be discrete random variables that take values in a set $\mathcal{A}$, and let their respective probability mass functions be

Then, the maximal coupling of $(X,Y)$ satisfies

Let $\mathcal{B}\triangleq\{u\in\mathcal{A}:\,P_{X}(u)<P_{Y}(u)\}$, and let $\mathcal{B}^{\text{c}}\triangleq\mathcal{A}\setminus\mathcal{B}$. Then, for every coupling $(\hat{X},\hat{Y})$ of $(X,Y)$,

The following provides a construction of a coupling $(\hat{X},\hat{Y})$ that achieves the bound in (4) with equality, so it forms a maximal coupling of $(X,Y)$. Let $U$, $V$, $W$ and $J$ be independent discrete random variables, where

so $J\sim\text{Bernoulli}(p)$, and let $U$, $V$, $W$ have the following probability mass functions:

If $J=1$, let $\hat{X}=\hat{Y}=U$, and if $J=0$ let $\hat{X}=V$ and $\hat{Y}=W$. For every $x,y\in\mathcal{A}$

and similarly $P_{\hat{Y}}(y)=P_{Y}(y)$, so $(\hat{X},\hat{Y})$ is indeed a coupling of $(X,Y)$. Furthermore,

The following result is a simple consequence of Theorem 3 (see, e.g., [31, Chapter 2]), and it is also used for the derivation of the new bounds on the entropy in Section III.

Let $X$ and $Y$ be two discrete random variables that take values in a set $\mathcal{A}$. If $(\hat{X},\hat{Y})$ is a maximal coupling of $(X,Y)$ then

This work refines bounds on the difference of the entropies of two discrete random variables via the use of maximal couplings, leading to sharpened bounds that depend on both the local and total variation distances. The reader is also referred to a recent work in that derived bounds for information measures by relying on the notion of the minimum entropy coupling.

The main observation of this work is that if the local distance between two probability distributions on a finite alphabet is smaller than the total variation distance, then the bounds on the entropy difference can be significantly strengthened. The second observation made in this work is that there is an extension of the new bound to countably infinite alphabets, where just knowing the total variation distance between two distributions does not imply anything about the difference of the respective entropies. The new bound that follows from the second observation is applied in this work to obtain refined bounds on the entropy of sums of independent (possibly non-identically distributed) Bernoulli random variables that arise in numerous applications. The application of the new bounds to the Poisson approximation is facilitated by using bounds on the total variation and local distances which follow from Stein’s method, and the improvement that is obtained by these bounds is exemplified in this work. For comparison, a looser version of the new bounds was earlier applied in to get bounds on the entropy of sums of dependent and non-identically distributed Bernoulli random variables.

The continuation of this paper is structured as follows: Section II introduces a known bound, due to Zhang , on the difference of the entropies of two discrete random variables in terms of the total variation distance. A shortened proof that is based on maximal coupling serves to motivate the derivation of some refined bounds. These new bounds, proved in Section III via maximal coupling, depend on both the local and total variation distances. Section IV exemplifies the use of the new bounds with a link to Stein’s method, and it also compares them with some previously known bounds. Finally, the paper is concluded in Section V. Throughout this paper, the logarithms and the entropies are to the base $e$.

II A Proof of a Known Bound on the Entropy of Discrete Random Variables via Coupling

The following theorem relies on a bound that first appeared in [38, Eq. (4)] and proved by coupling. It was later introduced in [17, Theorem 6] by re-proving the inequality in a different way (without coupling), and it was also strengthened there by showing an explicit case where the following bound is tight. As is proved in [38, Section 3], the bound on the entropy difference that is introduced in the following theorem improves the bound in [8, Theorem 17.3.3] or [9, Lemma 2.7].

Let $X$ and $Y$ be two discrete random variables that take values in a finite set $\mathcal{A}$, and let $|\mathcal{A}|=M$. Then,

where $h$ denotes the binary entropy function. Furthermore, there is a case where the bound is tight.

The following proof of Theorem 3 exemplifies the use of maximal coupling in proving an information-theoretic result.

Let $(\hat{X},\hat{Y})$ be a maximal coupling of $(X,Y)$. Since $H(X)=H(\hat{X})$ and $H(Y)=H(\hat{Y})$ (note that the marginal probability mass functions of $(X,Y)$ and $(\hat{X},\hat{Y})$ are the same), it follows from Fano’s inequality and Theorem 10 (see (10)) that

This proves the bound in (11) (see [38, Eq. (4)]). If $d_{\text{TV}}(X,Y)\leq\varepsilon$ for some \varepsilon\in\bigl{[}0,1-\frac{1}{M}\bigr{]}, the replacement of $d_{\text{TV}}(X,Y)$ in the last bound by $\varepsilon$ is valid; this holds since the function $f(x)\triangleq x\log(M-1)+h(x)$ is monotonic increasing over the interval $[0,1-\frac{1}{M}]$ (since $f^{\prime}(x)=\log(M-1)+\log\left(\frac{1-x}{x}\right)>0$ for $0<x<1-\frac{1}{M}$). Otherwise, if $\varepsilon>1-\frac{1}{M}$,

Cases where the bound is tight : If $\varepsilon\in[0,1-\frac{1}{M}]$, the bound is tight when

If $\varepsilon\in(1-\frac{1}{M},1]$ then the bound is tight when

so, $d_{\text{TV}}(X,Y)=1-\frac{1}{M}<\varepsilon$ and $|H(X)-H(Y)|=\log(M)$. ∎

III New Bounds on the Entropy of Discrete Random Variables via Coupling

In the cases where the known bound in Theorem 3 was shown to be tight in (see the last part of the proof in Section II), it is easy to verify that the local distance is equal to the total variation distance. However, as is shown in the following, if it is not the case (i.e., the local distance is smaller than the total variation distance), then the bound in Theorem 3 is necessarily not tight. Furthermore, this section provides new bounds that depend on both the total variation and local distances. If these two distances are equal then the new bound is particularized to the bound in Theorem 3 but otherwise, the new bound improves the bound in Theorem 3. The general approach for proving the following new inequalities relies on the construction of the maximal coupling that is introduced in the proof of Theorem 3. The new results are stated and proved in the following.

Let $X$ and $Y$ be two discrete random variables that take values in a finite set $\mathcal{A}$, and let $|\mathcal{A}|=M$. Then,

denotes the ratio of the local and total variation distances (so, $\alpha\in[\frac{2}{M},1]$), and $h$ denotes the binary entropy function. Furthermore, if the probability mass functions of $X$ and $Y$ satisfy the condition that $\frac{1}{2}\leq\frac{P_{X}}{P_{Y}}\leq 2$ whenever $P_{X},P_{Y}>0$, then the bound in (12) is tightened to

Since, in general, $\alpha\leq 1$ then the case where $\alpha=1$ is the worst case for the bound in (12). In the latter case, it is particularized to the bound in Theorem 3 (see [17, Theorem 6] or [38, Eq. (4)]).

If $\alpha\leq\frac{1}{N}$ for some integer $N$ (since \alpha\in\bigl{[}\frac{2}{M},1\bigr{]} then $N\in\{1,\ldots,\lfloor\frac{M}{2}\rfloor\}$), the bound in (12) implies that

The bounds in (15) and [17, Theorem 7] are similar but they hold under different conditions. The bound in [17, Theorem 7] requires that $P_{X},P_{Y}\leq\frac{1}{N}$ everywhere, whereas the bound in (15) holds under the requirement that the ratio $\alpha$ of the local and total variation distances satisfies $\alpha\leq\frac{1}{N}$. None of these conditions implies the other.

Assume without loss of generality (w.l.o.g.) that $H(X)-H(Y)\geq 0$ (note that the terms $|H(X)-H(Y)|$, $d_{\text{loc}}(X,Y)$ and $d_{\text{TV}}(X,Y)$ are invariant under a switch of $X$ and $Y$). Let $(\hat{X},\hat{Y})$ be the maximal coupling of $(X,Y)$ according to the construction in the proof of Theorem 3. Then,

The conditional entropy $H(\hat{X}|J)$ satisfies

where equality (a) holds since $J\sim\text{Bernoulli}(p)$ with

(see the proof of Theorem 3 and the result in Theorem 10), and because $\hat{X}$ is equal to $V$ or $U$ when $J$ gets that values zero or one, respectively. Furthermore, equality (b) holds since $U,V,W,J$ are independent random variables (due to the construction shown in the proof of Theorem 3). Similarly,

In the following, we derive upper bounds on $H(V)-H(W)$ and $I(\hat{X};J)-I(\hat{Y};J)$, and rely on (19) to get an upper bound on $|H(X)-H(Y)|$. Let $\mathcal{A}\triangleq\{a_{1},\ldots,a_{M}\}$, and

and $H(V)-H(W)=-\sum_{i=1}^{M}s_{i}\log(s_{i})+\sum_{i=1}^{M}t_{i}\log(t_{i}).$ Hence, for fixed $\alpha$ and $M$ (since $|\mathcal{A}|=M$, then $\alpha\in[\frac{2}{M},1]$),

where $g(\alpha)$ is the solution of the optimization problem

with the $2M$ variables $s_{1},t_{1},\ldots s_{M},t_{M}$. Fortunately, this non-convex optimization problem admits a closed-form solution.

The solution of the non-convex optimization problem in (26), denoted by $g(\alpha)$, is the following:

with the convention that $0\log 0$ means 0.

Let’s first show that the solution on the right-hand side of (27) forms an upper bound on $g(\alpha)$, and then show that this upper bound is tight.

For the derivation of the upper bound, note that due to the above constraints,

where inequality (a) holds since $s_{i}+t_{i}\leq\alpha$ and $s_{i},t_{i}\geq 0$ for every $i\in\{1,\ldots,M\}$, (b) follows from the constraint that $s_{i}\,t_{i}=0$ for every $i$, and (c) holds since the cardinality of the support of $\{s_{i}\}$ is an integer, and $\left\lfloor M-\frac{1}{\alpha}\right\rfloor=M-\left\lceil\frac{1}{\alpha}\right\rceil$. Hence,

and the solution of the optimization problem in (26) satisfies

where $f(\alpha)$ solves the optimization problem

with the $M$ optimization variables $t_{1},\ldots,t_{M}$. Note that the objective function in (32) is convex, and the feasible set is a bounded polyhedron. Furthermore, the maximum of a convex function over a bounded polyhedron is attained at one of its vertices (see, e.g., [30, Corollary 32.3.3]; this property follows from the convex-hull description of a bounded polyhedron and Jensen’s inequality). Since the objective function and the feasible set in (32) are invariant to a permutation of the variables $t_{1},\ldots,t_{M}$, then an optimal point is given by

where $l\leq\frac{M}{2}$ (since $\alpha\in[\frac{2}{M},1]$); as requested, $t_{i}\in[0,\alpha]$ for $i\in\{1,\ldots,M\}$. This implies that the solution of the optimization problem in (32) is given by

From (29) and (33), it follows that the right-hand side of (27) forms an upper bound on $g(\alpha)$. It remains to show that this bound is tight. To this end, we separate into the following two cases:

Case 1: Suppose that $N\triangleq\frac{1}{\alpha}$ is an integer. In this case, the upper bound on $g(\alpha)$ (see (29) and (33)) gets the simplified form

This upper bound on $g(\alpha)$ is achieved by the point $(s_{1},t_{1},\ldots,s_{M},t_{M})$ where

Note that this point is included in the feasible set of the optimization problem in (26) since $\frac{1}{M-N}=\frac{\alpha}{M\alpha-1}\leq\alpha$ where the last inequality holds because $\alpha\in[\frac{2}{M},1]$. The value of the objective function in (26) at this point is equal to

so this upper bound on $g(\alpha)$ is tight if $\frac{1}{\alpha}$ is an integer.

Case 2: Suppose that $\frac{1}{\alpha}$ is not an integer. In this case, let $l\triangleq\left\lfloor\frac{1}{\alpha}\right\rfloor$ so l+1=\Bigl{\lceil}\frac{1}{\alpha}\Bigr{\rceil}, and consider the $(2M)$-dimensional vector $(s_{1},t_{1},\ldots,s_{M},t_{M})$ where

To verify that it is included in the feasible set of (26), note that due to the constraints of this optimization problem

and, by combining it with (28), it follows that

so $\left\lceil\frac{1}{\alpha}\right\rceil\leq\frac{M}{2}$. This implies that for $j\in\{l+2,\ldots,M\}$ (note also that $\alpha\in[\frac{2}{M},1]$)

and $t_{l+1}=1-\alpha\left\lfloor\frac{1}{\alpha}\right\rfloor\leq\alpha$, so the vector is indeed included in the feasible set of (26). The value of the objective function in (26) at the selected point in (34) is equal to

so the upper bound on $g(\alpha)$ from (29) and (33) is tight, and this completes the proof of Lemma 1. ∎

The solution of the non-convex optimization problem in (26) satisfies the inequality

and this bound is tight if and only if $\frac{1}{\alpha}$ is an integer.

From Lemma 1 (see Eq. (27)), it follows that

and the above inequality turns to be an equality if and only if $\frac{1}{\alpha}$ is an integer. ∎

By combining (22) and Corollary 1, it follows that

Finally, the bound in (12) follows from the inequality

We move to derive a refinement of the bound in (12) when $\frac{1}{2}\leq\frac{P_{X}}{P_{Y}}\leq 2$. In this case, the starting point is the inequality in (35) where it is aimed to improve the upper bound in (36). To this end,

where $J_{\text{MAP}}(\hat{X})$ is the maximum a-posteriori (MAP) estimator of $J$ based on $\hat{X}$ (note that the minimum on the left-hand side of [18, Eq. (110)] is achieved by the MAP estimator). In the following, the estimator $J_{\text{MAP}}(\hat{X})$ on the right-hand side of (38) is calculated.

If $\hat{X}\notin\text{supp}(P_{V})$ then a.s. $J=1$ (otherwise, $J=0$ and $\hat{X}=V$, so $\hat{X}\in\text{supp}(P_{V})$ a.s.). Hence,

From (7), it follows that $\hat{X}\notin\text{supp}(P_{V})$ if and only if $P_{X}(\hat{X})\leq P_{Y}(\hat{X})$.

If $\hat{X}\in\text{supp}(P_{V})$ then, from (7), $P_{X}(\hat{X})>P_{Y}(\hat{X})$. Hence, from (6) and (7) with $p=1-d_{\text{TV}}(X,Y)$,

Since $U,V,J$ are independent, then from (5)

so, if $\hat{X}\in\text{supp}(P_{V})$, then

To conclude, the MAP estimator of $J$ that is based on the observation $\hat{X}$ is given by

It therefore implies that if $\frac{P_{Y}}{P_{X}}\geq\frac{1}{2}$ whenever $P_{X}>0$, then $J_{\text{MAP}}(\hat{X})=1$ independently of $\hat{X}$, so in this case

Hence, from (37), (38) and the last equality, if $\frac{P_{Y}}{P_{X}}\geq\frac{1}{2}$ whenever $P_{X}>0$ then

A combination of the last inequality with (35) finally gives the refined bound in (14). Since it was assumed at the beginning of the proof that $H(X)\geq H(Y)$ while it is not necessarily known in advance which entropy is larger, the requirement on $\frac{P_{Y}}{P_{X}}$ can be symmetrized by requiring that $\frac{1}{2}\leq\frac{P_{X}}{P_{Y}}\leq 2$ whenever $P_{X},P_{Y}>0$. This completes the proof of Theorem 4. ∎

Let $X$ and $Y$ be two discrete random variables that take values in a finite set $\mathcal{A}$, and let $|\mathcal{A}|=M$. Assume that for some positive constants $\varepsilon_{1},\varepsilon_{2}$

From (12), (13), (42), and since $\alpha\leq\varepsilon_{2}$

The function $q(\varepsilon)\triangleq\varepsilon c+h(\varepsilon)$ is monotonic increasing over the interval \Bigl{[}0,\frac{e^{c}}{1+e^{c}}\Bigr{]} ($q^{\prime}(\varepsilon)=c+\log\left(\frac{1-\varepsilon}{\varepsilon}\right)>0$ if and only if $0<\varepsilon<\frac{e^{c}}{1+e^{c}}$). Referring to the right-hand side of the above inequality, let $c\triangleq\log(M\varepsilon_{2}-1)$, so $\frac{e^{c}}{1+e^{c}}=1-\frac{1}{M\varepsilon_{2}}$. Hence, if the conditions in (41) and (42) are satisfied then the inequality in (43) holds. ∎

By considering the pair of probability mass functions $P_{X,Y}$ and $P_{X}\times P_{Y}$ (without abuse of notation, let $H(P_{X})\triangleq H(X)$), then

Hence, Theorem 4 and Corollary 43 provide bounds on the mutual information between two discrete random variables of finite support, where these bounds are expressed in terms of the local and total variation distances between the joint distribution of $(X,Y)$ and the product of its marginal distributions. The specialization of Theorem 4 to this setting tightens the bound in [38, Theorem 1], and the former bound is particularized to the latter known bound in the case where the local and total variation distances are equal (which is the extreme case).

The bound in [38, Theorem 1] was improved in [27, Proposition 1] without any further assumptions. It is noted that by introducing the additional requirement where there exists some constant $\varepsilon_{2}\in$ such that for every $y\in\mathcal{Y}$

then it enables to refine the bound in [27, Proposition 1]. This follows by combining the proof of [27, Proposition 1] with (43) (see Corollary 43) where Eq. (43) replaces the use of [38, Eq. (4)] in [27, Eq. (35)]. The same thing also applies to [28, Proposition 2], referring to its proof in [28, p. 305].

For countably infinite alphabets, just knowing the total variation distance between two distributions does not imply anything about the difference of entropies (i.e., one has discontinuity of the entropy). The following theorem shows that is one of the distributions is finitely supported, and some knowledge of the tail behavior of the other distribution is available, then having bounds on the local and total variation distances allows one to bound the difference of the entropies even in this case.

where $\eta_{3}\leq\eta_{2}\leq\eta_{1}<1$. Let $M$ be an integer such that

The inequality $\eta_{3}\leq\eta_{2}\leq\eta_{1}<1$ (after (44)) is easily satisfied since $d_{\text{loc}}(X,Y)\leq d_{\text{TV}}(X,Y)\leq 1$; so, if $d_{\text{TV}}(X,Y)<1$ then it is possible to choose $\eta_{1}$, $\eta_{2}$ and $\eta_{3}$ that satisfy this inequality.

Let $\widetilde{Y}$ be a random variable that is defined to be equal to $Y$ if $Y\in\{a_{1},\ldots,a_{M-1}\}$, and it is set to be equal to $a_{M}$ if $Y=a_{i}$ for some $i\geq M$. Hence, the probability mass function of $\widetilde{Y}$ is related to that of $Y$ as follows:

Since $P_{X}(a_{i})=0$ for every $i>m$ and also $M\geq m+1$ (see the second inequality in (45)), then it follows from (48) that

Hence, $X$ and $\widetilde{Y}$ are discrete random variables that take values in the set $\{a_{1},\ldots,a_{M}\}$ (note that it includes the set $\mathcal{X}$), and from (44) and (49)

Furthermore, the local distance between $X$ and $\widetilde{Y}$ satisfies

where (a), (b) and (c) above follow from the equality in (48) (note also that $m\leq M-1$), the first inequality in (45) and the second inequality in (44), respectively. From (50) and (51)

where $0<\varepsilon_{1}<1$ and $0<\varepsilon_{2}\leq 1$ (since, by assumption, $0<\eta_{3}\leq\eta_{2}\leq\eta_{1}<1$). The integer $M$ is set to satisfy the inequality $M\geq\frac{\eta_{2}}{\eta_{3}(1-\eta_{1})}$ (see (45)), so from (52) and (53)

Since $\widetilde{Y}$ is a deterministic function of $Y$ then $H(Y)\geq H(\widetilde{Y})$, and from (48)

Finally, the bound in (47) follows from (54), (55) and the triangle inequality. ∎

In the setting of $X$ and $Y$ in Theorem 47, assume that $d_{\text{TV}}(X,Y)\leq\eta$ for some $\eta\in(0,1)$. Let M\triangleq\max\Bigl{\{}m+1,\frac{1}{1-\eta}\Bigr{\}}, and assume that for some $\mu>0$

then $|H(X)-H(Y)|\leq\eta\log(M-1)+h(\eta)+\mu.$

This follows from Theorem 47 by setting $\eta_{2}=\eta_{3}=d_{\text{loc}}(X,Y)$ (note that $d_{\text{loc}}(X,Y)\leq d_{\text{TV}}(X,Y)$), and then $\eta_{1}$ and $\eta_{4}$ are replaced by $\eta$ and $\mu$, respectively. ∎

The result in Corollary 3 can be obtained by a simplification of the proof of Theorem 47 where (54) is replaced by the bound in [38, Eq. (4)] (see (11)), without the refinement which takes the local distance into consideration.

IV Examples

In the following, we exemplify the use of the new bounds in Section III, and also compare them with some previously known bounds.

Let $X$ be a discrete random variable that gets values in the set $\mathcal{A}=\{a_{1},\ldots,a_{M}\}$. Let’s express its arbitrary probability mass function in the form

where the latter equality is equivalent to $\sum_{i=1}^{M}P_{X}(a_{i})=1$.

In the following, we derive a lower bound on the entropy $H(X)$. Let $Y$ be a random variable that takes the values from $\mathcal{A}$ with equal probability, so $H(Y)=\log M$. The local and total variation distances between $X$ and $Y$ are equal to

where $\xi_{\text{avg}}^{(M)}$ and $\xi_{\max}^{(M)}$ denote the average and maximal values of $\{\xi_{i}\}_{i=1}^{M}$, respectively. From (13)

From (12) (where also $H(Y)=\log M\geq H(X)$), it follows that

and, since the binary entropy function is bounded between 0 and $\log 2$, the above inequality can be loosened to

For comparison, the bound in Theorem 3 gives that

The latter condition in (61) is stronger than (59). To see this, note that $1\leq K_{M}\leq\frac{M}{2}$ (since $\frac{2}{M}\leq\frac{d_{\text{loc}}(X,Y)}{d_{\text{TV}}(X,Y)}\leq 1$). On the other hand, as a concrete example for the case where the condition in (59) holds whereas the condition in (61) does not hold, let $M$ be an arbitrary even number, and

where, indeed, $\sum_{i=1}^{M}u_{i}\xi_{i}=\beta\sum_{i=1}^{M}(-1)^{i}=0$. In this case, $P_{X}(a_{i})=\frac{1-\beta}{M}$ for odd numbers $i\in\{1,\ldots,M\}$, and $P_{X}(a_{i})=\frac{1+\beta}{M}$ for even numbers $i$. Furthermore, in this case $K_{M}=1$ for every even $M$, so the condition in (59) holds by letting the even number $M$ tend to infinity. On the other hand, the condition in (61) is not satisfied since $\lim_{M\rightarrow\infty}\xi_{\text{avg}}^{(M)}=\beta>0.$ The upper and lower bounds in (60) tend to $1$ and $1-\frac{\beta}{2}$, respectively, so the gap between these asymptotic bounds is increased linearly with $\beta$. Therefore, Theorem 4 gives a simple lower bound on the entropy $H(X)$ in terms of the average and maximal values of $\{\xi_{i}\}_{i=1}^{M}$, which improves the lower bound on the entropy that follows from the known bound in Theorem 3 (see (60)).

For comparison, the bound in [17, Theorem 7] is also applied to this example. In this case, since $P_{X},P_{Y}\leq\frac{1+\xi_{\max}}{M}$ then $P_{X}$ and $P_{Y}$ are less than or equal to $\frac{1}{N_{M}}$ with N_{M}\triangleq\Bigl{\lfloor}\frac{M}{1+\xi_{\max}^{(M)}}\Bigr{\rfloor}. Similarly to the above analysis, it is easy to verify from [17, Theorem 7] that

where the right-hand side of this inequality holds since the function $f(x)=x\log x$ for $x>0$ achieves its minimal value at $x=\frac{1}{e}$, it follows that if the limit on the left-hand side of (62) is zero then also

Therefore, the definition of $K_{M}$ in (57) gives that

This shows that the conclusion in (59) implies the one in (62).

Let $Y$ be a random variable that gets all the values in the set $\{a_{1},\ldots,a_{M}\}$ with equal probability (i.e., $2^{-m}$). Then, the local and total variation distances between $X$ and $Y$ are

so, from (13), $\alpha=\frac{2}{M}$. The entropies of $X$ and $Y$ are

so, H(Y)-H(X)=\log 2-h\bigl{(}\frac{1-\beta}{2}\bigr{)} independently of $m$.

For comparison, the known bound in Theorem 3 that only depends on the total variation distance between $X$ and $Y$ (with no further knowledge about their probability mass functions) gives

so this upper bound increases almost linearly with $m$, in contrast to the exact value that is independent of $m$. The new bound in (12), which depends on both the local and total variation distances between $X$ and $Y$ (but again, without any further information on their probability mass functions) gives

Similarly to the exact value, but in contrast to the former bound, the latter bound is independent of $m$. Furthermore, if $\beta\rightarrow 0$ and $m\beta\rightarrow\infty$, then the exact value of $H(Y)-H(X)$ as well as the latter bound (that follows from Theorem 4) tend to zero, whereas the former bound that follows from Theorem 3 tends to infinity. This shows the difference in the two bounds, exemplifying the possible advantage of taking into account the local distance in addition to the total variation distance.

For $\beta\in[0,\frac{1}{2}]$, the condition $\frac{1}{2}\leq\frac{P_{X}}{P_{Y}}\leq 2$ is fulfilled, so the tightened bound in (14) gives that

If $\beta=\frac{1}{2}$, H(Y)-H(X)=\log 2-h\bigl{(}\frac{1}{2}\bigr{)}=0.131 nats, the upper bound in (64) is equal to 0.562 nats, and the tightened version of this bound in (65) is equal to 0.216 nats.

It is noted that since $P_{X}$ is majorized by $P_{Y}$ (see [18, Definition 1 on p. 5934]), then according to [18, Theorem 3]

and since $P_{Y}$ refers to a uniform distribution over a set of cardinality $M=2^{m}$ then $H(Y)=m\log 2$, and

so, the above lower bound is achieved here with equality.

In Example 1, the probability mass function of the discrete random variable $X$ was known explicitly. However, in many interesting applications, this is not necessarily the case. If the exact distribution of $X$ is not available or is numerically hard to compute, a derivation of some good bounds on the local and total variation distances between $X$ and another random variable $Y$ with a known probability mass function can be valuable to get a rigorous bound on the difference $|H(X)-H(Y)|$ via Theorems 4 or 47. As a result of the calculation of such a bound on the entropy difference, it provides bounds on the entropy of $X$ in terms of another entropy (the entropy of $Y$) which is assumed to be easily calculable. For example, assume that $X=\sum_{i=1}^{n}X_{i}$ is expressed as a sum of Bernoulli random variables that are either independent or weakly dependent, and may be also non-identically distributed. Let $X_{i}\sim\text{Bernoulli}(p_{i})$, and assume that $\sum_{i=1}^{n}p_{i}=\lambda$ where all of the $p_{i}$’s are much smaller than 1. In this case, the approximation of $X$ by a Poisson distribution with mean $\lambda$ (according to the law of small numbers ) raises the question: How close is $H(X)$ to the entropy of the Poisson distribution with mean $\lambda$ ? (note that the latter entropy of the Poisson distribution is calculated efficiently in ). This question is especially interesting because the support of the Poisson distribution is the infinite countable set of non-negative integers, and the entropy is known not to be continuous when the support is not finite; hence, a small total variation distance does not yield in general a small difference of the two entropies. This question was addressed in via the use of Corollary 3, combined with an upper bound on the total variation distance between $X$ and $Y$; the latter bound is calculated via the use of the Chen-Stein method (see, e.g., [31, Chapter 2]).

In the following, we wish to tighten the bounds on the entropy of a sum of independent Bernoulli random variables that are not necessarily identically distributed. The bound provided in [33, Corollary 1] relies on an upper bound on the total variation distance between this sum and a Poisson random variable with the same mean (see [4, Theorem 1] or [5, Theorem 2.M]). In order to tighten the bound on the entropy in the considered setting, we further rely on a new lower bound on the total variation distance (see [34, Theorem 1 and Corollary 1]) and an upper bound on the local distance (see [5, Theorem 2.Q and Corollary 9.A.2]). The latter two bounds provide an upper bound on the ratio of the local and total variation distances, which enables to apply the bound in Theorem 47; it improves the bound in Corollary 3 which solely relies on an upper bound on the total variation distance. It is noted that the latter looser bound, which relies on Corollary 3 was used in for estimating the entropy of a sum of Bernoulli random variables in the more general setting where the summands are possibly dependent.

Furthermore, from [34, Corollary 1], the following lower bound on the total variation distance holds:

An upper bound on the local distance between a sum of independent Bernoulli random variables and a Poisson distribution with the same mean $\lambda$ follows as a special case of [5, Corollary 9.A.2] by setting $l=1$ (so that the distribution $Q_{l}$ in this corollary is specialized for $l=1$ to the Poisson distribution $\text{Po}(\lambda)$, according to [5, Eq. (1.12) on p. 177]). Since the upper bound on the right-hand side of the inequality in [5, Corollary 9.A.2] does not depend on the (time) index $j$, it follows that the same bound also holds while referring to

Based on the notation used in this corollary, it implies that if $\left(\frac{1-e^{-\lambda}}{\lambda}\right)\,\sum_{i=1}^{n}p_{i}^{2}\leq\frac{1}{8}$ then the local distance between a sum of independent Bernoulli random variables $X_{i}\sim\text{Bernoulli}(p_{i})$ and a Poisson random variable with mean $\lambda=\sum_{i=1}^{n}p_{i}$ is upper bounded by

where inequality (a) holds due to [5, Proposition A.2.7 on pp. 262–263], and $I_{0}$ denotes the modified Bessel function of order zero. Since an upper bound on the total variation distance also forms an upper bound on the local distance, then a combination of (66) and (70) gives that

We now apply Theorem 47 to get rigorous bounds on the entropy $H(X)$ by estimating how close it is to H\bigl{(}\text{Po}(\lambda)\bigr{)}. Note that the improvement in the tightness of the bound in Theorem 47, in comparison to the looser bound in Corollary 3, is more significant when the ratio $\alpha$ of the local and total variation distances is close to zero. This happens to be the case if $\lambda\gg 1$ where due to the asymptotic expansion of $I_{0}$ (see [1, Eq. (9.7.1) on p. 377] or [12, Eq. (8.451.5) on p. 973])

one gets from Eqs. (67)–(69) and (71), combined with the limit in [34, Eq. (47)], that

so, for large values of $\lambda$, the upper bound on the parameter $\alpha$ in (13) decays to zero like the square-root of $\frac{1}{\lambda}$.

As a possible application, consider a noiseless binary-adder multiple-access channel (MAC) with $n$ independent users where each user transmits binary symbols, and the channel output is the algebraic sum of the input symbols. The capacity region of this MAC channel is an $n$-dimensional polyhedron. One feature of this capacity region is the sum of the rates that is given by $R_{\text{SUM}}\triangleq\sum_{i=1}^{n}R_{i}$, and it is upper bounded by the joint mutual information between the input symbols $X_{1},\ldots,X_{n}$ and the corresponding channel output $Y=\sum_{i=1}^{n}X_{i}$, i.e.,

In the following, we make use of Theorem 47 to get an upper bound on the entropy difference

where, due to the maximal entropy result for the Poisson distribution (see, e.g., , or ), this difference is positive. Let X\sim\text{Binom}\bigl{(}n,\frac{\lambda}{n}\bigr{)} be a sum of $n$ i.i.d. Bernoulli random variables with probability of success $p=\frac{\lambda}{n}$, and let $Y\sim\text{Po}(\lambda)$. From (66), the total variation distance in this case is upper bounded by

From (67) and (68), the following inequality holds:

where $\theta$ is given in (69). Furthermore, for using Theorem 47, one needs an upper bound on the local distance between the Poisson and Binomial distributions. Eq. (71) gives that

Following the notation in Theorem 47, it follows that $m=n+1$. From (45), one needs to choose an integer $M$ such that

Let $M\geq\lambda e^{2}$, then it follows from (78) and (79) that it is sufficient for $M$ to satisfy the condition

Combining it with (77) leads to the following possible choice of $M$:

where $\eta_{1}$, $\eta_{2}$ and $\eta_{3}$ are introduced in (74), (75), and (76) respectively. Finally, for the use of Theorem 47, one needs to choose $\eta_{4}>0$ such that \sum_{j=M}^{\infty}\bigl{\{}-\Pi_{\lambda}(j)\;\log\bigl{(}\Pi_{\lambda}(j)\bigr{)}\bigr{\}}\leq\eta_{4}. Straightforward calculation gives that

where equality (a) follows from the identity

By combining (81) and (82), it follows that

At this stage, we are ready to apply Theorem 47 to derive a bound on the non-negative difference of the entropies in (73). From Theorem 47, it follows that

For comparison, it follows from Corollary 3 that the upper bound on the right-hand side of (84) is replaced by

Note that the bound in (84) improves the bound in (85) if $\eta_{3}<\eta_{2}$ (i.e., if the upper bound on the local distance is smaller than the lower bound on the total variation distance). Furthermore, the latter bound does not take into account the parameters $\eta_{2}$ and $\eta_{3}$. As a numerical example, for $n=10^{6}$ and $p=0.1$, lets check the bound on the entropy difference in (73) for $\lambda=np$ (i.e., $\lambda=10^{5}$). Eqs. (74)–(76), (80), (83) and (86) yield that

and the two bounds in (84) and (85) are, respectively, equal to 1.483 and 1.707 nats, respectively. The value of H\bigl{(}\text{Po}(\lambda)\bigr{)} is 7.175 nats, so the entropy H\bigl{(}\text{Binom}(n,\frac{\lambda}{n})\bigr{)} ranges between 5.693 to 7.175 nats. Note that for $n=10^{6}$ and $\lambda=10^{4}$, where $p=\frac{\lambda}{n}$ is decreased from $10^{-1}$ to $10^{-2}$, the upper bounds on (73) are decreased, respectively, to 0.183 and 0.194 nats, and H\bigl{(}\text{Po}(\lambda)\bigr{)}=6.024 nats. The Poisson approximation is more accurate in the latter case, consistently with the law of small numbers (see, e.g., ).

Example 2 considers the use of Theorem 47 for the estimation of the entropy of a sum of independent Bernoulli random variables. The more general case of the estimation of the entropy (via rigorous bounds) for a sum of possibly dependent Bernoulli random variables was considered in by using the looser bound in Corollary 3 with an upper bound on the total variation distance that follows from the Chen-Stein method (see [3, Theorem 1]). It is noted that, in principle, also the sharper bound in Theorem 47 can be applied to obtain bounds on the entropy for a sum of possibly dependent Bernoulli random variables. To this end, in addition to the upper bound on the total variation distance in [3, Theorem 1], one needs to rely on a lower bound on the total variation distance (see [5, Chapter 3]) and an upper bound on the local distance (see [5, Theorem 2.Q on p. 42]). It is noted, however, that these distance bounds are much simplified in the setting of independent summands (see Example 2).

The Chen-Stein method for the Poisson approximation was adapted in to the setting of the geometric distribution, and it yields a convenient method for assessing the accuracy of the geometric approximation to the distribution of the number of failures preceding the first success in dependent trials. A recent study of upper bounds on the total variation and local distances for the geometric approximation (respectively, denoted by $d_{1}$ and $d_{2}$ in ) enables to apply the entropy bounds in Theorem 47 and Corollary 3 in a conceptually similar way to Example 2. Furthermore, the entropy bound in Corollary 3 can be applied to compound geometric and negative binomial approximations, based on upper bounds on the total variation distance that were derived via Stein’s method in and , respectively.

V Summary and Outlook

This paper is motivated by the fundamental question of quantifying the continuity (or lack of it) of entropy, with respect to natural topologies on discrete probability distributions. This question has been studied in the literature for the topology induced by the total variation distance, and there it is well known that the entropy is continuous when the alphabet is finite, but not when the alphabet is countably infinite (see, e.g., and references therein). To set terminology, the local and total variation distances are introduced in Definition 3 (see Section I): the local distance between two discrete random variables is defined to be the $l^{\infty}$ distance between their probability mass functions, and the total variation distance is half the $l^{1}$ distance; it is easy to show that the local distance is less than or equal to the total variation distance.

This paper starts by introducing preliminary material in Sections I and II; Theorems 3–3 are known results on maximal coupling, and a bound from on the difference of the entropies of two discrete random variables in terms of the total variation distance. Note that the proofs of these known results are important for the analysis in this paper.

The new results in this paper are the following:

For two given distributions on a finite alphabet, if the local distance is strictly smaller than the total variation distance, then Theorem 4 provides a new bound which can be significantly better than the previously best known bound (Theorem 3) due to Zhang .

For countably infinite alphabets, a knowledge of the total variation distance between two distributions is not sufficient for establishing an informative bound on the difference of entropies (i.e., one has discontinuity of entropy). Theorem 47 demonstrates that if one of the distributions is finitely supported and some knowledge of the other distribution is available, then the knowledge of the local and total variation distances (or bounds on these distances) allows one to bound the difference of the entropies even in this case.

Refined bounds on the entropy of near-uniform random variables on large alphabets, as well as of sums of independent Bernoulli random variables (which arise in numerous applications, see and references therein) are obtained in Section IV (see Examples 1 and 2). These refined bounds are compared with previously known bounds. One special case where the entropy can be explicitly evaluated and compared to various bounds is worked out, and it is shown that Theorem 4 improves significantly the known bound in Theorem 3.

A natural question that arises in the context of this paper is what if one only has bounds on the local distance ? A treatment of this problem (which does not exist in the literature) possibly gives further insight into why the local distance is useful in combination of the total variation distance. In the finite alphabet case, the two metrics are equivalent since

and, hence, generate the same topology; so the bare continuity of entropy is guaranteed for finite alphabets, and so is the discontinuity of the entropy for infinite alphabets. But are there tight bounds on the difference of entropies just based on the local distance for finite alphabets ?

The following proposition suggests a simple bound on the difference of entropies of two discrete random variables that are finitely supported, based only on their local distance:

Let $X$ and $Y$ be discrete random variables that take values in a finite set $\mathcal{A}$, and let $|\mathcal{A}|=M$. If $d_{\text{loc}}(X,Y)\leq\frac{1}{e}$, then

with the convention that $0\log 0$ means 0.

The derivation of this bound forms a small modification of the proof of [8, Theorem 17.3.3]. Let $P_{X}$ and $P_{Y}$ denote the probability mass functions of $X$ and $Y$, respectively, and let $r(u)\triangleq|P_{X}(u)-P_{Y}(u)|$ for every $u\in\mathcal{A}$. From [8, Eqs. (17.27)–(17.30)], if $r(u)\leq\frac{1}{2}$ for every $u\in\mathcal{A}$, then

The bound in (87) now follows from the simple inequality $r(u)\leq d_{\text{loc}}(X,Y)$ for every $u\in\mathcal{A}$ (by definition), and due to the fact that the function $f(x)=-x\log(x)$ is monotonic increasing over the interval $[0,\frac{1}{e}]$. ∎

The bound in (87) does not necessarily hold if $d_{\text{loc}}(X,Y)>\frac{1}{e}$. As a counter example, let $\mathcal{A}$ be a set of 3 elements, and let

Then $d_{\text{loc}}(X,Y)=1$ and $H(X)-H(Y)=\log 2$, so (87) is not satisfied due to the violation of the condition on the local distance in Proposition 1.

A slight loosening of the bound in (87) gives that if $d_{\text{loc}}(X,Y)\leq\frac{1}{e}$, then

where $h$ is the binary entropy function. In the simple case where the probability mass functions of $X$ and $Y$ are equal to $P_{X}=(1-\varepsilon,\varepsilon)$ and $P_{Y}=(1,0)$, respectively, we have $d_{\text{loc}}(X,Y)=\varepsilon$; if $0<\varepsilon\leq\frac{1}{e}$, the bound on $|H(X)-H(Y)|$ is twice larger than its exact value that is equal to $h(\varepsilon).$ Even in this simple case, the bound on the difference of the entropies that only depends on the local distance is not tight. On one hand, it will be of interest to derive tighter bounds on the difference of entropies for finite alphabets that are just based on the local distance; on the other hand, even the simple bound in Proposition 1 provides some insight into why the local distance is useful in combination of the total variation distance for upper bounding the difference of entropies for finite alphabets (see Theorem 4).

An anonymous reviewer of this journal paper and the conference version at ISIT 2013 is gratefully acknowledged for suggestions that led to an improvement of the presentation, and for raising the question in Section V that led to the bound in Proposition 1. The Associate Editor, Ioannis Kontoyiannis, is acknowledged for handling the manuscript. This research work was supported by the Israeli Science Foundation (ISF), grant number 12/12.

References