On the Rate of Convergence in the Entropic Central Limit Theorem

Shiri Artstein ^{∗}, Keith Ball^{†}, Franck Barthe^{‡}and Assaf Naor^{§}

September 25, 2003

Abstract We study the rate at which entropy is produced by linear combinations of

independent random variables which satisfy a spectral gap condition.

1 Introduction

The Shannon entropy of a random variable X with density f is defined as Ent(X) = − ∫_{ℝ} f log f, provided the positive part of the integral is finite. So Ent(X) ∈ [−∞, +∞). If X has variance 1, it is a classical fact that its entropy is well defined and bounded above by that of a standard Gaussian random variable G. By the Pinsker-Csiszar-Kullback inequality ([12], [9], [10]), G is a stable maximizer of entropy in the following strong sense:

d_{T V} (X − 𝔼X, G)^{2} ≤ 2[Ent(G) − Ent(X)],  (1)

where d_{T V} is the total variation distance. It is therefore natural to track the convergence in the central limit theorem (CLT) in terms of entropy. Let (X_{n})_{n∈ℕ} be a sequence of independent copies of a random variable X. For notational convenience we assume that 𝔼X = 0 and 𝔼X^{2} = 1. Set

S_{n} = \frac{X_{1} + ⋯ + X_{n}}{\sqrt{n}} .

and the Israel Science Foundation

∗Supported in part by the EU Grant HPMT-CT-2000-00037, The Minkowski center for Geometry

†Supported in part by NSF Grant DMS-9796221

‡Supported in part by EPSRC Grant GR/R37210

§Supported in part by the BSF, Clore Foundation and EU Grant HPMT-CT-2000-00037

Linnik [11] used entropy to reprove convergence in distribution of S_{n} to G. He actually showed that Ent(S_{n}) converges to Ent(G) under some smoothness assumptions on the law of X. This is discussed in [4] where Barron established entropic convergence in the CLT in full generality: if the entropy of S_{n} ever becomes different from −∞, then Ent(S_{n}) converges to Ent(G). This convergence is very strong, as (1) shows.

The fact that the sequence of entropies Ent(S_{n}) has a limit follows from the Shannon-Stam inequality ([13], [15]): for independent variables Y, Z and λ ∈ (0, 1) one has

Ent(\sqrt{1 − λ} Y + \sqrt{λ}Z) ≥ (1 − λ)Ent(Y) + λEnt(Z),  (2)

therefore (nEnt(S_{n})) is super-additive and converges to its supremum. In particular Ent(S_{2^{k}}) is non-decreasing. In [1] we confirmed an old conjecture: that the entire sequence (Ent(S_{n})) is non-decreasing.

Until recently, quantitative improvements on the Shannon-Stam inequality (2), have been somewhat elusive. A qualitative result in this direction, under pretty general hypotheses was obtained by Carlen and Soffer [8] (see also the works of Brown and Shimuzu [7] [14]). In [3] we obtained quantitative estimates for random variables X satisfying a Poincaré (or spectral gap) inequality with constant c > 0: i.e. so that for every smooth function s, one has

c Var(s(X)) ≤ 𝔼[(s′(X))^{2}].

The main result in [3] asserts that independent copies X_{1}, X_{2} of such a random variable X satisfy

Ent (\frac{X_{1} + X_{2}}{\sqrt{2}} ) − Ent(X) ≥ \frac{c}{2 + 2c}(Ent(G) − Ent(X)).

In this article we apply an extension of the variational method of [3] to estimate the entropy of sums (or linear combinations) of more than two copies of a random varaiable. Independently of [3] and almost simultaneously, Barron and Johnson proved an analogous but slightly weaker fact for the Fisher information. We have just learned that, by modifying their argument they are able to recover our results for entropy: the new argument appears in [5].

The principal result of this article is the following.

Theorem 1 Let X_{1}, …, X_{n} be independent copies of a random variable X with density f. Assume that Var(X) = 1 and that X satisfies the Poincaré inequality with constant c. Then for every a ∈ ℝ^{n} with ∑_{i=1}^{n} a_{i}^{2} = 1,

Ent(G) − Ent (∑_{i=1}^{n} a_{i}X_{i}) ≤ \frac{α(a)}{c/2 + (1 − c/2)α(a)} (Ent(G) − Ent(X)) ,

where α(a) = ∑_{i=1}^{n} a_{i}^{4}.

Remark. In fact, we obtain a slightly stronger, more complicated inequality- see inequality (16).

Before passing to the proof, let us make a few comments. Note that when one of the a_{i}’s tends to ±1, there can be no increase of entropy. This is consistent with the fact that α(a) tends to 1 in this case. On the other hand, for equal coefficients 1/\sqrt{n} we obtain that the entropy distance from the Gaussian decays at rate 1/n

Ent(G) − Ent (\frac{1}{\sqrt{n}} ∑_{i=1}^{n} X_{i}) ≤ \frac{1}{1 + \frac{c}{2}(n − 1)} (Ent(G) − Ent(X)) .  (3)

In conjunction with the Csiszar-Kulback-Pinsker inequality, the above theorem leads to a quantitative information-theoretic proof of the central limit theorem (under a spectral gap assumption). The rate of convergence obtained (in total variation distance) is O(1/\sqrt{n}), which is well known to be optimal. Moreover, we also obtain Berry-Esseen type estimates, but in total variation, for the rate of convergence to a Gaussian.

2 Proof of the main theorem

Assume as we may that the variables are centered, that is 𝔼X = ∫ xf(x) dx = 0. The proof is divided into several steps:

2.1 Reduction to an inequality for Fisher information

Recall that the Fisher information of a random variable X with density f is

I(X) = I(f) = ∫ \frac{(f′)^{2}}{f} .

According to Bruijn’s identity (see e.g. [15]), Fisher information is the time derivative of entropy along the heat semi-group. A similar relation holds along the adjoint Ornstein-Uhlenbeck semigroup (see [2, 4]), where the evolute at time t of a variable X, denoted X^{(t)}, has the same law as e^{−t}X + \sqrt{1 − e^{−2t}} G where G is a normal Gaussian variable independent of X. More precisely if Ent(X) is finite then for every t > 0 , X^{(t)} has finite Fisher information and

Ent(G) − Ent(X) = ∫_{0}^{∞} (I(X^{(t)}) − 1) dt.

A very clear explanation of this appears in [8]. Also note that I(G) = 1. Since the evolute (∑ a_{i}X_{i})^{(t)} has the same distribution as ∑ a_{i}X_{i}^{(t)} it suffices to prove:

Theorem 2 Let Y be a random variable with Var(Y) = 1, finite entropy, and spectral gap at least c > 0. Let t > 0, X = Y^{(t)} and X_{1}, …, X_{n} be independent copies of X. Then for every a ∈ ℝ^{n} with ∑_{i=1}^{n} a_{i}^{2} = 1,

I (∑_{i=1}^{n} a_{i}X_{i}) − 1 ≤ \frac{α(a)}{c/2 + (1 − c/2)α(a)} (I(X) − 1) .

Let us also point out that the hypotheses in the latter theorem are far from optimal; we could certainly get away with less smoothness for X than is guaranteed by its being an Ornstein-Uhlenbeck evolute. However the hypothesis is sufficient for our goal and ensures that the density f of X has an integrable second derivative (see e.g. the Appendix of [3]). The rest of the paper is devoted to the proof of Theorem 2 and keeps the same notation.

2.2 Variational representations of the Fisher information

Our approach relies on the following result, which we proved in [1]

Theorem 3 Let w : ℝ^{n} → (0, ∞) be a continuously twice differentiable density on ℝ^{n} with

∫ \frac{∥∇w∥^{2}}{w} , ∫ ∥Hess(w)∥ < ∞.

Let a be a unit vector in ℝ^{n} and h the marginal density in direction a defined by

h(t) = ∫_{ta+a^{⊥}} w.

Then the Fisher information of the density h satisfies

J(h) ≤ ∫ \frac{(div(pw))^{2}}{w} ,

for any continuously differentiable vector field p : ℝ^{n} → ℝ^{n} with the property that for every x, ⟨p(x), a⟩ = 1 (and, say, ∫ ∥p∥w < ∞). If w satisfies ∫ ∥x∥^{2}w(x) < ∞, then there is equality for some suitable vector field p.

The previous formula is very short but it leads to tedious calculations when applied to specific p. For this reason we provide another formulation of it, which is easier to use in the present situation.

Lemma 4 Let w be as in Theorem 3 and let p : ℝ^{n} → ℝ^{n} be twice continuously differentiable, such that each coordinate function p_{i} is bounded and has bounded derivatives of first and second order. Then

∫ \frac{(div(pw))^{2}}{w} = ∫ w [Tr((Dp)^{2}) + ⟨Hess(− log w)p, p⟩] .

Proof of the Lemma: Distributing the divergence and the square gives

∫ \frac{(div(pw))^{2}}{w} = ∫ (w(div(p))^{2} + \frac{⟨∇w, p⟩^{2}}{w} + 2div(p)⟨∇w, p⟩) .

On the other hand

∫ w [Tr((Dp)^{2}) + ⟨Hess(− log w)p, p⟩] = ∫ (wTr((Dp)^{2}) + \frac{⟨∇w, p⟩^{2}}{w} − ⟨Hess(w)p, p⟩) .

So the identity we want amounts to

∫ (w(div(p))^{2} + 2div(p)⟨∇w, p⟩ − wTr((Dp)^{2}) + ⟨Hess(w)p, p⟩) = 0.

This can be checked by integration by parts, once for the second term and twice for the fourth term, in order to get rid of derivatives of w.

Let X with density f be as in Theorem 2 and set w(x_{1}, …, x_{n}) = f(x_{1}) ⋯ f(x_{n}). Then the function h(t) = ∫_{ta+a^{⊥}} w is the density of ∑_{i=1}^{n} a_{i}X_{i}. The latter results yield

I (∑_{i=1}^{n} a_{i}X_{i}) ≤ ∫ w [T r(Dp)^{2} + ⟨Hess(− log w)p, p⟩] ,  (4)

for any sufficiently integrable vector field p : ℝ^{n} → ℝ^{n} with the property that for every x, ⟨p(x), a⟩ = 1. Note that the best choice of p would give equality in (4), whereas the simplest choice (p(x) = a for all x) recovers I (∑_{i=1}^{n} a_{i}X_{i}) ≤ I(X), a consequence of the Blachman-Stam inequality [6, 15]. As in our previous works, our strategy is to optimize over a workable sub-family of test functions p.

2.3 Choice of particular test functions

In order to exploit the product structure of w, in expression (4), we restrict ourselves to functions p_{i} which are linear combinations of the constant function and functions depending only on one variable. It seems to be sufficient to choose a single one-variable function: so our test function has the form p_{i}(x_{1}, …, x_{n}) = c_{i0} +∑_{j=1}^{n} c_{ij}r(x_{j}) and the only restriction on p is that ∑_{i=1}^{n} a_{i}p_{i} ≡ 1. We would like to choose p = (a_{1}r(x_{1}), a_{2}r(x_{2}), …, a_{n}r(x_{n})) but since this does not satisfy the condition we project it orthogonally onto the hyperplane {x : ⟨a, x⟩ = 1}. So we choose

p_{i}(x_{1}, …, x_{n}) = a_{i} + a_{i}(1 − a_{i}^{2})r(x_{i}) − a_{i} ∑_{j≠i} a_{j}^{2}r(x_{j}),

where r is a real-valued function on ℝ.

Now for smooth r with compact support inequality (4) is valid. Denoting ϕ = − log f, the two integrands on the right hand side of (4) are

Tr((Dp)^{2}) = ∑_{1≤i,j≤n} \frac{∂p_{i}}{∂x_{j}} \frac{∂p_{j}}{∂x_{i}} = ∑_{i=1}^{n} a_{i}^{2}(1 − a_{i}^{2})^{2}r′(x_{i})^{2} + ∑_{i≠j} a_{i}^{3}a_{j}^{3}r′(x_{i})r′(x_{j}),

and

⟨Hess(− log w)p, p⟩ = ∑_{i=1}^{n} ϕ′′(x_{i})a_{i}^{2} (1 + (1 − a_{i}^{2})r(x_{i}) − ∑_{j≠i} a_{j}^{2}r(x_{j}))^{2}
= ∑_{i=1}^{n} ϕ′′(x_{i})a_{i}^{2} [1 + (1 − a_{i}^{2})^{2}r(x_{i})^{2} + ∑_{j≠i} a_{j}^{4}r(x_{j})^{2} − 2 ∑_{j≠i} a_{j}^{2}r(x_{j})

+2(1 − a_{i}^{2})r(x_{i}) − 2 ∑_{j≠i}(1 − a_{i}^{2})a_{j}^{2}r(x_{j})r(x_{i})+

∑_{i≠j≠k≠i} a_{j}^{2}a_{k}^{2}r(x_{j})r(x_{k})] .

Integrating against the product density w(x) and using the fact that ∑ a_{i}^{2} = 1, this identity reduces to

∫ w [T r(Dp)^{2} + ⟨Hess(− log w)p, p⟩]
= J + W (∫ f(r′)^{2} + ∫ fϕ′′r^{2}) + JV ∫ fr^{2} + J(W − V) (∫ fr)^{2}
+2U (∫ fϕ′′r − J ∫ fr) − 2W (∫ fr) (∫ fϕ′′r) + M (∫ fr′)^{2} ,

where:

J = I(X), U = 1 − ∑_{i=1}^{n} a_{i}^{4}, V = ∑_{i=1}^{n} a_{i}^{4} − ∑_{i=1}^{n} a_{i}^{6}, W = U − V

and M = (∑_{i=1}^{n} a_{i}^{3})^{2} − ∑_{i=1}^{n} a_{i}^{6}.

Our aim is to choose r to make the estimate small. This is a standard variational problem except for the term M (∫ fr′)^{2}. If the random variable X is symmetric, so that f is an even function, then we will choose an even function r and so the term in question will vanish. This gives a slightly better result for symmetric random variables. In the the general case we can control the term because

(∫ fr′)^{2} = (∫ f′r)^{2} ≤ (∫ \frac{(f′)^{2}}{f} ) (∫ fr^{2}) = J (∫ fr^{2}) .  (5)

However, our choice of vector field p is invariant under the addition of a constant to r and this property simplifies considerably the calculations. In order to maintain this invariance we improve the estimate (5) slightly as follows. Setting m = ∫ fr we have

(∫ fr′)^{2} = (∫ f′(r − m))^{2} ≤ (∫ \frac{(f′)^{2}}{f} ) (∫ f(r − m)^{2}) = J (∫ fr^{2} − m^{2}) . (6)

Lastly, the coefficient M is at most V by Hölder’s inequality.

Hence we obtain the estimate

I (∑_{i=1}^{n} a_{i}X_{i}) − J ≤ T (r)

where

T (r) = W (∫ f(r′)^{2} + ∫ fϕ′′r^{2}) + 2JV ∫ fr^{2} + J(W − 2V) (∫ fr)^{2}
+2U (∫ fϕ′′r − J ∫ fr) − 2W (∫ fr) (∫ fϕ′′r) .

Our goal is to find r that makes this quantity as negative as possible.

2.4 Optimization in the test function r

In this subsection we apply variational methods to find the optimum value of T (r). Their statement in the appropriate Sobolev spaces, as well as the questions of existence and regularity are discussed in detail in the appendix of [3]. So, in the following we shall ignore technical issues.

In order to deal with the quadratic terms J(W −2V) (∫ fr)^{2} and −2W (∫ fr) (∫ fϕ′′r) we introduce a Lagrange multiplier λ and choose r to be λr_{0} where r_{0} is the minimiser of

∫ f(r′)^{2} + ∫ fϕ′′r^{2} + Jβ ∫ fr^{2} + 2 (∫ fϕ′′r − J ∫ fr)

and β = 2V/W. The Euler-Lagrange equation for this minimization problem is

−(fr′_{0})′ + fr_{0}ϕ′′ + Jβfr_{0} = Jf − fϕ′′.  (7)

By integrating this equation against r_{0} and 1 respectively, we obtain that any solution r_{0} of (7) automatically satisfies the following relations

∫ f(r′_{0})^{2} + ∫ fϕ′′r_{0}^{2} + Jβ ∫ fr_{0}^{2} = J ∫ fr_{0} − ∫ fϕ′′r_{0},  (8)
∫ fϕ′′r_{0} + Jβ ∫ fr_{0} = 0.  (9)

Set A = ∫ fr_{0} and B = ∫ fϕ′′r_{0}. Using equations (8) and (9) we obtain

T (λr) = AJλ(1 + β) (λ(1 + A)W − 2U) .

The optimal choice of λ is U/W (1 + A) and the estimate is then

T (λr_{0}) = −\frac{JU^{2}(1 + β)}{W} \frac{A}{A + 1}.  (10)

To finish the proof we need to estimate A = ∫ fr_{0} from below: we want to know that if U and W are close to 1 and β is small then A is large so that the quantity above captures almost all of J. From now on, we suppress the subscript and use r instead of r_{0}. The equation satisfied by r reads

−(fr′)′ + fϕ′′r + Jβfr = f(J − ϕ′′).  (11)

Writing f′ = −fϕ′ and dividing by f we can rewrite it as

−r′′ + ϕ′r′ + ϕ′′r + Jβr = J − ϕ′′.

If we set r = s′ then we can integrate the equation to get

−s′′ + ϕ′s′ + Jβs = Jx − ϕ′  (12)

where the constant of integration is chosen so that ∫ fs = 0 (assuming that our random variable is centred so that ∫ fx = 0). Multiplying (12) by f we get

− (fs′)′ + Jβfs = Jfx − fϕ′  (13)

Now equation (13) is the Euler-Lagrange equation for a different minimisation problem in which the objective function is

Q(s) = \frac{1}{2} ∫ f(s′)^{2} + \frac{Jβ}{2} ∫ f (s − \frac{x}{β} + \frac{ϕ′}{Jβ} )^{2} .  (14)

Observe that in our new notation A = ∫ fs′. Integrating equation (13) against s and x respectively we get

∫ f(s′)^{2} + Jβ ∫ fs^{2} = J ∫ fsx − ∫ fs′

and

∫ fs′ + Jβ ∫ fsx = J ∫ fx^{2} − ∫ f = J − 1

since f is the density of a random variable with variance 1.

As before these equations yield an expression of Q(s) in terms of A = ∫ fs′ only. One obtains that

Q(s) = \frac{1 + β}{2β} A.  (15)

So in order to bound A from below it suffices to bound the functional Q. Note that the value of Q on the zero function is

Q(0) = \frac{J}{2β} ∫ f (x − \frac{ϕ′}{J} )^{2} = \frac{J − 1}{2β}.

Now we use the fact that f satisfies a Poincaré inequality with constant c. This will force the minimum of Q to be of the order of Q(0). Since ∫ fs = 0 the Poincaré inequality gives

c ∫ fs^{2} ≤ ∫ fs^{′2}.

Thus we get

Q(s) = \frac{1}{2} ∫ fs^{′2} + \frac{Jβ}{2} ∫ f (s − \frac{x}{β} + \frac{ϕ′}{Jβ} )^{2}
≥ \frac{1}{2} ∫ f (cs^{2} + Jβ (s − \frac{x}{β} + \frac{ϕ′}{Jβ} )^{2})
≥ \frac{1}{2} · \frac{cJβ}{c + Jβ} ∫ f (−\frac{x}{β} + \frac{ϕ′}{Jβ} )^{2}
= \frac{c}{2(c + Jβ)}Q(0) = \frac{c(J − 1)}{2β(c + βJ)}.

Substituting into the expression (15) for Q(s) in terms of A, we obtain the lower bound

A ≥ \frac{c(J − 1)}{(1 + β)(c + Jβ)}.

Substituting this into (10) rearranging and using the facts that W = U − V and β = 2V/W gives an estimate slightly better than

I (∑_{i=1}^{n} a_{i}X_{i}) − J ≤ −\frac{c(J − 1)U^{2}}{cU + 2V − cV} ,  (16)

where we have used the fact that J ≥ 1, which is a consequence of the Cramer-Rao inequality. It is easy to check that V ≤ U − U^{2} and this implies the desired estimate

I (∑ a_{i}X_{i}) − 1 ≤ (J − 1) \frac{1 − U}{cU/2 + 1 − U} = (J − 1) \frac{α(a)}{c(1 − α(a))/2 + α(a)}.

References

[1] S. Artstein, K. Ball, F. Barthe, and A. Naor. Solution of Shannon’s Problem on the Monotonicity of Entropy. Submitted, 2002.

[2] D. Bakry and M. Emery. Diffusions hypercontractives. In Séminaire de Probabilités XIX, number 1123 in Lect. Notes in Math., pages 179–206. Springer, 1985.

[3] K. Ball, F. Barthe, and A. Naor. Entropy jumps in the presence of a spectral gap. Duke Math. J. 119, No. 1, 41-63, 2003.

[4] A. R. Barron. Entropy and the central limit theorem. Ann. Probab., 14:336–342, 1986.

[5] A. R. Barron and O. Johnson. Fisher information inequalities and the central limit theorem. Preprint, ArXiv:math.PR/0111020

[6] N. M. Blachman. The convolution inequality for entropy powers. IEEE Trans. Info. Theory, 2:267–271, 1965.

[7] L. D. Brown. A proof of the central limit theorem motivated by the Cramer-Rao inequality. In Kalliampur et al., editor, Statistics and Probability: Essays in Honor of C. R. Rao, pages 314–328, Amsterdam, 1982. North-Holland.

[8] E. A. Carlen and A. Soffer. Entropy production by block variable summation and central limit theorem. Commun. Math. Phys., 140(2):339–371, 1991.

[9] I. Csiszar. Informationstheoretische Konvergenzbegriffe im Raum der Wahrscheinlichkeitsverteilungen. Publications of the Mathematical Institute, Hungarian Academy of Sciences, VII, Series A:137–157, 1962.

[10] S. Kullback. A lower bound for discrimination information in terms of variation. IEEE Trans. Info. Theory, 4:126–127, 1967.

[11] Ju. V. Linnik. An information theoretic proof of the central limit theorem with lindeberg conditions. Theory Probab. Appl., 4:288–299, 1959.

[12] M.S̃. Pinsker. Information and information stability of random variables and processes. Holden-Day, San Francisco, 1964.

[13] C. E. Shannon and W. Weaver. The mathematical theory of communication. University of Illinois Press, Urbana, IL, 1949.

[14] R. Shimizu. On Fisher’s amount of information for location family. In Patil et al., editor, A modern course on statistical distributions in scientific work, Boston, MA, 1974. D. Reidel.

[15] A. J. Stam. Some inequalities satisfied by the quantities of information of Fisher and Shannon. Info. Control, 2:101–112, 1959.

2000 Mathematics Subjects Classification: 94A17, 60F05.

Shiri Artstein School of Mathematical Sciences, Tel Aviv University, Ramat Aviv, Tel Aviv 69978, Israel; E-mail artst@post.tau.ac.il Keith M. Ball, Department of Mathematics, University College London, Gower Street, London WC1 6BT, United Kingdom; E-mail: kmb@math.ucl.ac.uk Franck Barthe, Laboratoire d’Analyse et de Mathématiques Appliquées, CNRS UMR8050, Université de Marnela-Vallée, Cité Descartes, Champs-sur-Marne, 77454 Marne-la-Vallée, Cedex 2, France; E-mail: barthe@math.univ.mlv.fr Assaf Naor, Theory Group, Microsoft Research, One Microsoft Way, Redmond WA 98052-6399, USA; Email: anaor@microsoft.com