Entropy power inequality

In information theory, the entropy power inequality (EPI) is a result that relates to so-called "entropy power" of random variables. It shows that the entropy power of suitably well-behaved random variables is a superadditive function. The entropy power inequality was proved in 1948 by Claude Shannon in his seminal paper "A Mathematical Theory of Communication". Shannon also provided a sufficient condition for equality to hold; Stam (1959) showed that the condition is in fact necessary.

Statement of the inequality

For a random vector $X:\mathrm{\Omega }\to {\mathbb{ℝ}}^n$ with probability density function $f:{\mathbb{ℝ}}^n\to \mathbb{ℝ}$, the differential entropy of $X$, denoted $h(X)$, is defined to be

$h(X)=-\underset{{\mathbb{ℝ}}^n}{\int }f(x)\log f(x)dx$

and the entropy power of $X$, denoted $N(X)$, is defined to be

$N(X)=\frac{1}{2\pi e}{e}^{\frac{2}{n}h(X)}.$

In particular, $N(X)=|K{|}^{1/n}$ when $X$ is normally distributed with covariance matrix $K$.

Let $X$ and $Y$ be independent random variables with probability density functions in the $L^p$ space $L^p({\mathbb{ℝ}}^n)$ for some $p>1$. Then

$N(X+Y)\ge N(X)+N(Y).$

Moreover, equality holds if and only if $X$ and $Y$ are multivariate normal random variables with proportional covariance matrices.

Alternative form of the inequality

The entropy power inequality can be rewritten in an equivalent form that does not explicitly depend on the definition of entropy power (see Costa and Cover reference below).

Let $X$ and $Y$ be independent random variables, as above. Then, let $X^{\prime }$ and $Y^{\prime }$ be independent random variables with Gaussian distributions and proportional covariance matrices such that

$h(X^{\prime })=h(X)$ and $h(Y^{\prime })=h(Y)$

Then,

$h(X+Y)\ge h(X^{\prime }+Y^{\prime })$

Strengthened form with an auxiliary variable

When one of the summands is Gaussian, the entropy power inequality can be strengthened to account for an auxiliary random variable that depends on the summands only through their sum. Let X be a real-valued random variable, let Y be a Gaussian random variable independent of X, and let W be a random variable such that (X, Y) → X + Y → W forms a Markov chain. Then

$N(X+Y)e^{-2I(X;W)}\ge N(X)e^{-2I(X+Y;W)}+N(Y),$

where $I(\cdot ;\cdot )$ denotes mutual information. If W is constant, both mutual informations vanish and the inequality reduces to the entropy power inequality.

When X is also Gaussian, the inequality was established earlier by Oohama in the course of determining the rate–distortion function of the quadratic Gaussian CEO problem. In this case it follows from a short argument. Let X and Y be independent zero-mean Gaussian random variables and let

$\alpha =\frac{\mathrm{Var}(X)}{\mathrm{Var}(X+Y)}=\frac{N(X)}{N(X+Y)}.$

Then $\mathrm{E}[X\mid X+Y]=\alpha (X+Y)$, and the estimation error $X-\alpha (X+Y)=(1-\alpha )X-\alpha Y$ is Gaussian and uncorrelated with, hence independent of, X + Y. By the Markov condition it is therefore independent of the pair (X + Y, W), and its entropy power is $\alpha N(Y)$. Applying the entropy power inequality conditionally on W (which follows from the unconditional inequality by Jensen's inequality) to the decomposition $X=\alpha (X+Y)+(X-\alpha (X+Y))$ gives

$N(X\mid W)\ge {\alpha }^{2}N(X+Y\mid W)+\alpha N(Y),$

where $N(\cdot \mid W)=\frac{1}{2\pi e}{e}^{2h(\cdot \mid W)}$ is the conditional entropy power. Since $N(X\mid W)=N(X)e^{-2I(X;W)}$ and $N(X+Y\mid W)=N(X+Y)e^{-2I(X+Y;W)}$, dividing by α yields the inequality above.

Connections and partial extensions to non-Gaussian X were explored by Eswaran, and the general case was proved by Courtade. Eswaran and Gastpar used it to extend Oohama's results on remote source coding to non-Gaussian sources.

See also

• Information entropy
• Information theory
• Limiting density of discrete points
• Self-information
• Kullback–Leibler divergence
• Entropy estimation

References

• Dembo, Amir; Cover, Thomas M.; Thomas, Joy A. (1991). "Information-theoretic inequalities". IEEE Trans. Inf. Theory 37 (6): 1501–1518. doi:10.1109/18.104312. 
• Costa, Max H. M.; Cover, Thomas M. (1984). "On the similarity of the entropy-power inequality and the Brunn-Minkowski inequality". IEEE Trans. Inf. Theory 30 (6): 837–839. doi:10.1109/TIT.1984.1056983. 
• Gardner, Richard J. (2002). "The Brunn–Minkowski inequality". Bull. Amer. Math. Soc. (N.S.) 39 (3): 355–405 (electronic). doi:10.1090/S0273-0979-02-00941-2. 
• Shannon, Claude E. (1948). "A mathematical theory of communication". Bell System Tech. J. 27 (3): 379–423, 623–656. doi:10.1002/j.1538-7305.1948.tb01338.x. 
• Stam, A. J. (1959). "Some inequalities satisfied by the quantities of information of Fisher and Shannon". Information and Control 2 (2): 101–112. doi:10.1016/S0019-9958(59)90348-1.