The entropy power inequality for independent random vectors is a foundational result of information theory, with deep connections to probability and geometric functional analysis. Several extensions of the entropy power inequality have been developed for settings with dependence, including by Takano, Johnson, and Rioul. We extend these works by developing a quantitative version of the entropy power inequality for dependent random vectors. A notable consequence is that an entropy power inequality stated using conditional entropies holds for random vectors whose joint density is log-supermodular.

We begin a systematic study of the region of possible values of the volumes of Minkowski subset sums of a collection of $M$ compact sets in $\mathbb{R}^d$, which we call the Lyusternik region, and make some first steps towards describing it. Our main result is that a fractional generalization of the Brunn-Minkowski-Lyusternik inequality conjectured by Bobkov et al. (2011) holds in dimension 1. Even though Fradelizi et al. (2016) showed that it fails in general dimension, we show that a variant does hold in any dimension.

Entropy comparison inequalities are obtained for the differential entropy$h(X+Y)$of the sum of two independent random vectors$X,Y$, when one is replaced by a Gaussian. For identically distributed random vectors$X,Y$, these are closely related to bounds on the entropic doubling constant, which quantifies the entropy increase when adding an independent copy of a random vector to itself. Consequences of both large and small doubling are explored. For the former, lower bounds are deduced on the entropy increase when adding an independent Gaussian, while for the latter, a qualitative stability result for the entropy power inequality is obtained. In the more general case of non-identically distributed random vectors$X,Y$, a Gaussian comparison inequality with interesting implications for channel coding is established: For additive-noise channels with a power constraint, Gaussian codebooks come within a$\frac {\mathsf { snr}}{3{\mathsf { snr}}+2}$factor of capacity. In the low-SNR regime this improves the half-a-bit additive bound of Zamir and Erez. Analogous results are obtained for additive-noise multiple access channels, and for linear, additive-noise

We prove a new class of inequalities for submodular set functions, indexed by chordal graphs. Since entropy is a particularly useful example of a submodular function, we deduce some entropy inequalities. As a further corollary, we construct a novel family of determinant inequalities for sums of positive definite Hermitian matrices, and also recover an inequality of Barrett, Johnson, and Lundquist (1989).

Mixture distributions are extensively used as a modeling tool in diverse areas from machine learning to communications engineering to physics, and obtaining bounds on the entropy of mixture distributions is of fundamental importance in many of these applications. This article provides sharp bounds on the entropy concavity deficit, which is the difference between the differential entropy of the mixture and the weighted sum of differential entropies of constituent components. Toward establishing lower and upper bounds on the concavity deficit, results that are of importance in their own right are obtained. In order to obtain nontrivial upper bounds, properties of the skew-divergence are developed and notions of “skew”$f$-divergences are introduced; a reverse Pinsker inequality and a bound on Jensen-Shannon divergence are obtained along the way. Complementary lower bounds are derived with special attention paid to the case that corresponds to independent summation of a continuous and a discrete random variable. Several applications of the bounds are delineated, including to mutual information of additive noise channels, thermodynamics of computation, and functional inequalities.

Lower bounds for the Rényi entropies of sums of independent random variables taking values in cyclic groups of prime order under permutations are established. The main ingredients of our approach are extended rearrangement inequalities in prime cyclic groups building on Lev [ Duke Math. J., 107 (2001), pp. 239--263] and notions of stochastic ordering. Several applications are developed, including to discrete entropy power inequalities, the Littlewood--Offord problem, and counting solutions of certain linear systems.

We show that the uniform distribution minimizes entropy among all one-dimensional symmetric log-concave distributions with fixed variance, as well as various generalizations of this fact to Rényi entropies of orders less than 1 and with moment constraints involving p-th absolute moments with p ≤ 2. As consequences, we give new capacity bounds for additive noise channels with symmetric log-concave noises, as well as for timing channels involving positive signal and noise where the noise has a decreasing log-concave density. In particular, we show that the capacity of an additive noise channel with symmetric, log-concave noise under an average power constraint is at most 0.254 bits per channel use greater than the capacity of an additive Gaussian noise channel with the same noise power. Consequences for reverse entropy power inequalities and connections to the slicing problem in convex geometry are also discussed.

Usable upper and lower deviation bounds are given for the information content of random vectors from a s-concave probability density function. Some information-theoretic interpretation, related to non-asymptotic equipartition properties, is also developed.

We examine the analogue of Arimoto's definition of conditional Rényi entropy and Rényi mutual information for abstract alphabets. Despite being dependent on the reference measure, these notions have useful properties similar to those known in the discrete setting. Moreover, we explore relationships between the families of mutual informations defined by Sibson, Csiszár, and Lapidoth-Pfister. In particular, we show that various notions of Rényi capacity and center coincide, extending results of Csiszár and Nakiboğlu.

In 1948, Shannon showed that the worst additive noise channel for a given noise power is the additive white Gaussian noise channel. We pose the question of the best additive noise within a natural class of noise distributions- namely, symmetric and log-concave distributions on the real line. While we are unable to answer the question, we do completely solve two related optimization problems. In particular, we identify the distribution in this class that minimizes differential entropy when the variance is fixed, and thereby give refined capacity bounds for channels with symmetric log-concave noises. A full version of this paper which also contains more general results and some additional theorems and corollaries is accessible at: https://arxiv.org/abs/1811.00345.

We initiate the study of the Stam region, defined as the subset of the positive orthant in ℝ(2n-1) that arises from considering the entropy powers of subset sums of n independent random vectors in a Euclidean space of finite dimension. We show that the class of fractionally superadditive set functions provides an outer bound to the Stam region, resolving a conjecture of Barron and Madiman. On the other hand, the entropy power of a sum of independent random vectors is not supermodular in any dimension. We also develop some qualitative properties of the Stam region, showing for instance that its closure is a logarithmically convex cone.

The capacity-achieving input distribution of the complex Gaussian channel with both average- and peak-power constraint is known to have a discrete amplitude and a continuous, uniformly-distributed, phase. Practical considerations, however, render the continuous phase inapplicable. This work studies the backoff from capacity induced by discretizing the phase of the input signal. A sufficient condition on the total number of quantization points that guarantees an arbitrarily small backoff is derived, and constellations that attain this guaranteed performance are proposed.

Over the past few years, a family of interesting new inequalities for the entropies of sums and differences of random variables has been developed by Ruzsa, Tao, and others, motivated by analogous results in additive combinatorics. This paper extends these earlier results to the case of random variables taking values in Rn or, more generally, in arbitrary locally compact and Polish abelian groups. We isolate and study a key quantity, the Ruzsa divergence between two probability distributions, and we show that its properties can be used to extend the earlier inequalities to the present general setting. The new results established include several variations on the theme that the entropies of the sum and the difference of two independent random variables severely constrain each other. Although the setting is quite general, the results are already of interest (and new) for random vectors in Rn. In that special case, we discuss quantitative bounds for the stability of the equality conditions in the entropy power inequality, a reverse entropy power inequality for log-concave random vectors, an information-theoretic analog of the Rogers-Shephard inequality for convex bodies, and consequences of some of our results to determinant inequalities for sums of positive-definite matrices. Moreover, by considering various multiplicative subgroups of the complex plane, one obtains new inequalities for the differential entropies of products and ratios of nonzero, complex-valued random variables.

We develop a general notion of rearrangement for certain metric groups, and prove a Hardy-Littlewood type inequality. Combining this with a characterization of the extreme points of the set of probability measures with bounded densities with respect to a reference measure, we establish a general min-entropy inequality for convolutions. Special attention is paid to the integers where a min-entropy power inequality is conjectured and a partial result proved.

An optimal ∞-Rényi entropy power inequality is derived for d-dimensional random vectors. In fact, the authors establish a matrix ∞-EPI analogous to the generalization of the classical EPI established by Zamir and Feder. The result is achieved by demonstrating uniform distributions as extremizers of a certain class of ∞-Rényi entropy inequalities, and then putting forth a new rearrangement inequality for the ∞-Rényi entropy. Quantitative results are then derived as consequences of a new geometric inequality for uniform distributions on Euclidean balls.

Sharp exponential deviation estimates for the information content as well as a sharp bound on the varentropy are obtained for convex probability measures on Euclidean spaces. These provide, in a sense, a nonasymptotic equipartition property for convex measures even in the absence of stationarity-type assumptions.

We explore conditions under which a reverse Rényi entropy power inequality holds for random vectors with s-concave densities, and also discuss connections with Convex Geometry.

We explore various tempting conjectures for discrete entropy power inequalities on the integers, proving both positive results for interesting subclasses of distributions and negative results that falsify some of the conjectures in general. In particular, we show that an inequality very similar to the usual entropy power inequality holds for uniform distributions over finite subsets of the integers.

We describe the norm of Fourier operator from Lp(T) to lq(ℤ), and from lp(ℤ) to Lq(T) for all p, q ≥ 1, motivated by the problem of finding sharp uncertainty principles expressed in terms of Rényi entropies.

A simple new lower bound is provided for the Rényi entropy of the convolution of probability distributions on the integers in terms of certain (discrete) rearrangements of these distributions. This inequality may be thought of as an entropy power inequality for integer-valued random variables.

The sumset and inverse sumset theories of Freiman, Plünnecke, and Ruzsa, give bounds connecting the cardinality of the sumset A + B = {a + b; a ∈ A, b ∈ B} of two discrete sets A, B, to the cardinalities (or the finer structure) of the original sets A, B. For example, the sum-difference bound of Ruzsa states that, |A + B| |A| |B| |A - B|3, where the difference set A - B = {a - b; a ∈ A, b ∈ B}. Interpreting the differential entropy h(X) of a continuous random variable X as (the logarithm of) the size of the effective support of X, the main contribution of this paper is a series of natural information-theoretic analogs for these results. For example, the Ruzsa sum-difference bound becomes the new inequality, h(X+Y)+h(X)+h(Y) ≤ 3h(X-Y), for any pair of independent continuous random variables X and Y. Our results include differential-entropy versions of Ruzsa's triangle inequality, the Plünnecke-Ruzsa inequality, and the Balog-Szemerédi-Gowers lemma. In addition, we give a differential entropy version of a Freiman-type inverse-sumset theorem, which can be seen as a quantitative converse to the entropy power inequality. Versions of most of these results for the discrete entropy H(X) were recently proved by Tao, relying heavily on a strong, functional form of the submodularity property of H(X). Since differential entropy is not functionally submodular, in the continuous case many of the corresponding discrete proofs fail, in many cases requiring substantially new proof strategies. We find that the basic property that naturally replaces the discrete functional submodularity, is the data processing property of mutual information.

A lower bound on the Rényi differential entropy of a sum of independent random vectors is demonstrated in terms of rearrangements. For the special case of Boltzmann-Shannon entropy, this lower bound is better than that given by the entropy power inequality. Several applications are discussed, including a new proof of the classical entropy power inequality and an entropy inequality involving symmetrization of Lévy processes.

A new lower bound on the entropy of the sum of independent random vectors is demonstrated in terms of rearrangements. This lower bound is better than that given by the entropy power inequality. In fact, we use it to give a new, independent, and simple proof of the entropy power inequality in the case when the summands are identically distributed. We also give a more involved but new way to recover the full entropy power inequality, without invoking Fisher information, MMSE or any differentiation of information functionals.

Motivated by a series of recently discovered inequalities for the sum and difference of discrete or continuous random variables [3], [5], [9], [10], we argue that the most natural, general form of these results is in terms of a special case of a mutual information, which we call the Ruzsa divergence between two probability distributions. This can be defined for arbitrary pairs of random variables taking values in any discrete (countable) set, on Rn, or in fact on any locally compact Hausdorff abelian group. We study the basic properties of the Rusza divergence and derive numerous consequences. In particular, we show that many of the inequalities in [3], [5], [9], [10] can be stated and proved in a unified way, extending their validity to the present general setting. For example, consequences of the basic properties of the Ruzsa divergence developed here include the fact that the entropies of the sum and the difference of two independent random vectors severely constrain each other, as well as entropy analogues of a number of results in additive combinatorics. Although the setting is quite general, the results are already of interest (and new) in the case of random vectors in Rn. For instance, another consequence in Rnis an entropic analogue (in the setting of log-concave distributions) of the Rogers-Shephard inequality for convex bodies.

The Plünnecke-Ruzsa sumset theory gives bounds connecting the cardinality of the sumset A + B defined as {a + b; a ϵ A, b ϵ B} with the cardinalities of the original sets A, B. For example, the sum-difference bound states that, |A+B| |A| |B| ≤ |A-B|3, where A-B = {a-b; a ϵ A, b ϵ B}. Interpreting the differential entropy h(X) as (the logarithm of) the size of the effective support of X, the main results here are a series of natural information-theoretic analogs for these bounds. For example, the sum-difference bound becomes the new inequality, h(X + Y) + h(X) + h(Y) ≤ 3h(X - Y), for independent X, Y. Our results include differential-entropy versions of Ruzsa's triangle inequality, the Plünnecke-Ruzsa inequality, and the Balog-Szemerédi-Gowers lemma. Versions of most of these results for the discrete entropy H(X) were recently proved by Tao, relying heavily on a strong, functional form of the submodularity property of H(X). Since differential entropy is not functionally submodular, in the continuous case many of the corresponding discrete proofs fail, in several cases requiring substantially new proof strategies. The basic property that naturally replaces functional submodularity is the data processing property of mutual information.

The entropy per coordinate in a log-concave random vector of any dimension with given density at the mode is shown to have a range of just 1. Uniform distributions on convex bodies are at the lower end of this range, the distribution with i.i.d. exponentially distributed coordinates is at the upper end, and the normal is exactly in the middle. Thus, in terms of the amount of randomness as measured by entropy per coordinate, any log-concave random vector of any dimension contains randomness that differs from that in the normal random variable with the same maximal density value by at most 1/2. As applications, we obtain an information-theoretic formulation of the famous hyperplane conjecture in convex geometry, entropy bounds for certain infinitely divisible distributions, and quantitative estimates for the behavior of the density at the mode on convolution. More generally, one may consider so-called convex or hyperbolic probability measures on Euclidean spaces; we give new constraints on entropy per coordinate for this class of measures, which generalize our results under the log-concavity assumption, expose the extremal role of multivariate Pareto-type distributions, and give some applications.

The hyperplane conjecture is a major unsolved problem in high-dimensional convex geometry that has attracted much attention in the geometric and functional analysis literature. It asserts that there exists a universal constant c such that for any convex set K of unit volume in any dimension, there exists a hyperplane H passing through its centroid such that the volume of the section K ∩ H is bounded below by c. A new formulation of this conjecture is given in purely information-theoretic terms. Specifically, the hyperplane conjecture is shown to be equivalent to the assertion that all log-concave probability measures are at most a bounded distance away from Gaussianity, where distance is measured by relative entropy per coordinate. It is also shown that the entropy per coordinate in a log-concave random vector of any dimension with given density at the mode has a range of just 1. Applications, such as a novel reverse entropy power inequality, are mentioned.

Consider the entropy increase h(Y + Y') - h(Y) of the sum of two continuous i.i.d. random variables Y, Y', and the corresponding entropy increase h(Y - Y') - h(Y) of their difference. We show that the ratio between these two quantities always lies between 1/2 and 2. This complements a recent result of Lapidoth and Pete, showing that the difference h(Y + Y') - h(Y - Y') may be arbitrarily large. Corresponding results are discussed for the discrete entropy, and connections are drawn with exciting recent mathematical work in the area of additive combinatorics.

In statistics and theoretical computer science, the notion of exchangeability provides a framework for the study of large alphabet scenarios. This idea has been developed in an important line of work starting with Kingman's study of population genetics, and leading on to the paintbox processes of Kingman, the Chinese restaurant processes and their generalizations. In information theory, the notion of the pattern of a sequence provides a framework for the study of large alphabet scenarios, as developed in work of Orlitsky and collaborators. The pattern is a statistic that captures all the information present in the data, and yet is universally compressible regardless of the alphabet size. In this note, connections are made between these two lines of work- specifically, patterns are examined in the context of exchangeability. After observing the relationship between patterns and Kingman's paintbox processes, and discussing the redundancy of a class of mixture codes for patterns, alternate representations of patterns in terms of graph limits are discussed.

Upper and lower bounds are obtained for the joint entropy of a collection of random variables in terms of an arbitrary collection of subset joint entropies. These inequalities generalize Shannon's chain rule for entropy as well as inequalities of Han, Fujishige, and Shearer. A duality between the upper and lower bounds for joint entropy is developed. All of these results are shown to be special cases of general, new results for submodular functions-thus, the inequalities presented constitute a richly structured class of Shannon-type inequalities. The new inequalities are applied to obtain new results in combinatorics, such as bounds on the number of independent sets in an arbitrary graph and the number of zero-error source-channel codes, as well as determinantal inequalities in matrix theory. A general inequality for relative entropies is also developed. Finally, revealing connections of the results to literature in economics, computer science, and physics are explored.

The Poisson distribution is known to have maximal entropy among all distributions (on the nonnegative integers) within a natural class. Interestingly, straightforward attempts to generalize this result to general compound Poisson distributions fail because the analogous result is not true in general. However, we show that the compound Poisson does indeed have a natural maximum entropy characterization when the distributions under consideration are log-concave. This complements the recent development by the same authors of an information-theoretic foundation for compound Poisson approximation inequalities and limit theorems.

It is shown that the entropy power of a sum of independent random vectors, seen as a set function, is fractionally superadditive. This resolves a conjecture of the first author and A. R. Barron, and implies in particular all previously known entropy power inequalities for independent random variables. It is also shown that, for general dimension, the entropy power of a sum of independent random vectors is not supermodular.

Consider a situation involving many sources of finite-length data, with buyers potentially interested in purchasing data from any bundle (subset) of the sources. A principled way is presented to assign a price to each source, when the value of the data is measured in terms of how much information about an underlying location parameter can be extracted from it. Apart from the operational relevance to data pricing, these results also have relevance to sensor network theory.

Notions from cooperative game theory arise in a very natural way in connection with the study of rate and capacity regions for many important problems. Furthermore, (i) game theory clarifies the fundamental structural connection between rate regions and information inequalities, and (ii) the interpretation of these regions in terms of users that are thought of as players in a cooperative game is of intrinsic value. Both these aspects are illustrated in a variety of settings, including Slepian-Wolf compression and Gaussian multiple access channels.

It is shown that the entropy of a sum of independent random vectors is a submodular set function, and upper bounds on the entropy of sums are obtained as a result in both discrete and continuous settings. These inequalities complement the lower bounds provided by the entropy power inequalities of Madiman and Barron (2007). As applications, new inequalities for the determinants of sums of positive-definite matrices are presented.

Fisher information plays a fundamental role in the analysis of Gaussian noise channels and in the study of Gaussian approximations in probability and statistics. For discrete random variables, the scaled Fisher information plays an analogous role in the context of Poisson approximation. Our first results show that it also admits a minimum mean squared error characterization with respect to the Poisson channel, and that it satisfies a monotonicity property that parallels the monotonicity recently established for the central limit theorem in terms of Fisher information. We next turn to the more general case of compound Poisson distributions on the nonnegative integers, and we introduce two new "local information quantities" to play the role of Fisher information in this context. We show that they satisfy subadditivity properties similar to those of classical Fisher information, we derive a minimum mean squared error characterization, and we explore their utility for obtaining compound Poisson approximation bounds.

New upper and lower bounds are given for joint entropy of a collection of random variables, in both discrete and continuous settings. These bounds generalize well-known information theoretic inequalities due to Han. A number of applications are suggested, including a new bound on the number of independent sets of a graph that is of interest in discrete mathematics, and a bound on the number of zero-error codes.

New families of Fisher information and entropy power inequalities for sums of independent random variables are presented. These inequalities relate the information in the sum of n independent random variables to the information contained in sums over subsets of the random variables, for an arbitrary collection of subsets. As a consequence, a simple proof of the monotonicity of information in central limit theorems is obtained, both in the setting of independent and identically distributed (i.i.d.) summands as well as in the more general setting of independent summands with variance-standardized sums.

We provide a simple proof of the monotonicity of information in the central limit theorem for i.i.d. summands. Extensions to the more general case of independent, not identically distributed summands are also presented. New families of Fisher information and entropy power inequalities are discussed

Using a simple inequality about the relative entropy, its so-called "tensorization property," we give a simple proof of a functional inequality which is satisfied by any compound Poisson distribution. This functional inequality belongs to the class of modified logarithmic Sobolev inequalities. We use it to obtain measure concentration bounds for compound Poisson distributions under a variety of assumptions on their tail behavior. In particular, we show how the celebrated "Herbst argument" can be modified to yield sub-exponential concentration bounds. For example, suppose Z is a compound Poisson random variable with values on the nonnegative integers, and let f be a function such that |f(k+1) - f(k)| les 1 for all k. Then, if the base distribution of Z does not have a finite moment-generating function but has finite moments up to some order L > 1, we show that the probability that f(Z) exceeds its mean by a positive amount t or more decays approximately like (const)middott-L, where the constant is explicitly identified. This appears to be one of the very first examples of concentration bounds with power-law decay

This paper describes the minimum description length principle in maximum likelihood estimate(MLE) in lossy data compression. In the lossless case the problem of optimal compression is theoretically equivalent to finding a probability distributions and minimizes the code-lengths.

The problem of approximating the distribution of a sum S/sub n/ = /spl Sigma//sub i=1//sup n/ Y/sub i/ of n discrete random variables Y/sub i/ by a Poisson or a compound Poisson distribution arises naturally in many classical and current applications, such as statistical genetics, dynamical systems, the recurrence properties of Markov processes and reliability theory. Using information-theoretic ideas and techniques, we derive a family of new bounds for compound Poisson approximation. We take an approach similar to that of Kontoyiannis, Harremoes and Johnson (2003), and we generalize some of their Poisson approximation bounds to the compound Poisson case. Partly motivated by these results, we derive a new logarithmic Sobolev inequality for the compound Poisson measure and use it to prove measure-concentration bounds for a large class of discrete distributions.