Abstract We prove the following type of discrete entropy monotonicity for sums of isotropic, log-concave, independent and identically distributed random vectors $$X_1,\dots ,X_{n+1}$$ X 1 , ⋯ , X n + 1 on $$\mathbb {Z}^d$$ Z d : $$ H(X_1+\cdots +X_{n+1}) \ge H(X_1+\cdots +X_{n}) + \frac{d}{2}\log {\Bigl (\frac{n+1}{n}\Bigr )} +o(1), $$ H ( X 1 + ⋯ + X n + 1 ) ≥ H ( X 1 + ⋯ + X n ) + d 2 log ( n + 1 n ) + o ( 1 ) , where o (1) vanishes as $$H(X_1) \rightarrow \infty $$ H ( X 1 ) → ∞ . Moreover, for the o (1)-term, we obtain a rate of convergence $$ O\Bigl ({H(X_1)}{e^{-\frac{1}{d}H(X_1)}}\Bigr )$$ O ( H ( X 1 ) e - 1 d H ( X 1 ) ) , where the implied constants depend on d and n . This generalizes to $$\mathbb {Z}^d$$ Z d the one-dimensional result of the second named author (2023). As in dimension one, our strategy is to establish that the discrete entropy $$H(X_1+\cdots +X_{n})$$

Following a growing number of studies that, over the past 15 years, have established entropy inequalities via ideas and tools from additive combinatorics, in this work we obtain a number of new bounds for the differential entropy of sums, products, and sum-product combinations of continuous random variables. Partly motivated by recent work by Goh on the discrete entropic version of the notion of “additive energy”, we introduce the additive energy of pairs of continuous random variables and prove various versions of the statement that “the additive energy is large if and only if the entropy of the sum is small”, along with a version of the Balog–Szemerédi–Gowers theorem for differential entropy. Then, motivated in part by recent work by M´athé and O’Regan, we establish a series of new differential entropy inequalities for products and sum-product combinations of continuous random variables. In particular, we prove a new, general, ring Plüunnecke–Ruzsa entropy inequality. We briefly return to the case of discrete entropy and provide a characterization of discrete random variables with “large doubling”, analogous to Tao’s Freiman-type inverse sumset theory for the case of small doubling. Finally, we consider the natural entropic analog of the Erdős–Szemerédi sum-product phenomenon for integer-valued random variables. We show that, if it does hold, then the range of parameters for which it does would necessarily be significantly more restricted than its anticipated combinatorial counterpart.

The problem of variable-rate lossless data compression is considered, for codes with and without prefix constraints. Sharp bounds are derived for the best achievable compression rate of memoryless sources, when the excess-rate probability is required to be exponentially small in the blocklength. Accurate nonasymptotic expansions with explicit constants are obtained for the optimal rate, using tools from large deviations and Gaussian approximation. When the source distribution is unknown, a universal achievability result is obtained with an explicit “price for universality” term. This is based on a fine combinatorial estimate on the number of sequences with small empirical entropy, which might be of independent interest. Examples are shown indicating that, in the small excess-rate-probability regime, the approximation to the fundamental limit of the compression rate suggested by these bounds is significantly more accurate than the approximations provided by either normal approximation or error exponents. The new bounds reinforce the crucial operational conclusion that, in applications where the blocklength is relatively short and where stringent guarantees are required on the excess-rate probability, the best achievable rate is no longer close to the entropy. Rather, it is an appropriate, morepragmaticrate, determined via the inverse error exponent function and the blocklength.

A new finite form of de Finetti's representation theorem is established using elementary information-theoretic tools. The distribution of the first$k$random variables in an exchangeable vector of$n\geq k$random variables is close to a mixture of product distributions. Closeness is measured in terms of the relative entropy and an explicit bound is provided. This bound is tighter than those obtained via earlier information-theoretic proofs, and its utility extends to random variables taking values in general spaces. The core argument employed has its origins in the quantum information-theoretic literature.

We study the entropy and Fisher information of mixtures of centered Gaussian random variables (with respect to the variance). First, we prove that if$X_{1}, X_{2}$are independent scalar Gaussian mixtures, then the entropy of$\sqrt{t}X_{1}+\sqrt{1-t}X_{2}$is concave in$t\in[0,1]$, thus confirming a conjecture of Ball, Nayar and Tkocz (2016) for this class of random variables. In fact, we prove a generalisation of this statement, which also strengthens a result of Eskenazis, Nayar and Tkocz (2018). Secondly, we establish rates of convergence for the Fisher information matrix of the sum of weighted i.i.d. Gaussian mixtures in the operator norm along the central limit theorem under mild moment assumptions. These are obtained by showing that the Fisher information matrix is operator convex as a matrix-valued function acting on densities of mixtures in$\mathbb{R}^{d}$, extending a result of Bobkov (2022). A full version of this paper is available at: arXiv:2308.15997.

We prove the following discrete generalised Entropy Power Inequality (EPI) for isotropic log-concave sums of independent identically distributed random vectors$X_{1}, \ldots X_{n+1}$on$\mathbb{Z}^{d}$: \begin{equation*}H\left( \sum\limits_{i=1}^{n+1}X_{i}\right)\geq H\left(\sum\limits_{i=1}^{n}X_{i}\right)+\frac{d}{2}\log\left(\frac{n+1}{n}\right)+o(1),\end{equation*} where$o(1)$vanishes as$H(X_{1})\rightarrow\infty$. Moreover, for the$o(1) \mathbf{term}$we obtain a rate of convergence$O\left(H(X_{1})e^{-\frac{1}{d}H(X_{1})}\right)$, where the implied constants depend on$d$and$n$. This generalises to$\mathbb{Z}^{d}$the one-dimensional result of the second named author (2023). As in dimension one, our strategy is to establish that the discrete entropy is close to the differential entropy of the sum after adding$n$independent and identically distributed uniform random vectors on$[0,1]^{d}$and to apply the continuous EPI. However, in dimension$d\geq 2$, more involved tools from convex geometry are needed. One of our technical tools is a dimensional analogue to a result of Bobkov, Marsiglietti and Melbourne (2022), which bounds the maximum probability of a log-concave p.m.f. in terms of the inverse of the determinant of the covariance matrix and may be of independent interest.

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 discrete analogue of the generalised entropy power inequality for log-concave random variables on the integers. As a special case, we show that a conjecture of Tao (2010) holds true for log-concave random variables on the integers:\begin{equation*}H\left( {{X_1} + \cdot s + {X_{n + 1}}} \right) \geq H\left( {{X_1} + \cdot s + {X_n}} \right) + \frac{1}{2}\log \left( {\frac{{n + 1}}{n}} \right) - o(1),\end{equation*}where the o(1)-term vanishes as H(X1) → ∞. Explicit, finite bounds for the error term are provided, which are exponential in H(X1).

An information-theoretic proof of a strengthened version of the classical discrete central limit theorem is presented. Using only information-theoretic and elementary arguments, convergence to zero of the relative entropy between the standardised sum of n independent and identically distributed lattice random variables and an appropriately discretised Gaussian is established.

We review information-theoretic approaches to obtaining simple probabilistic representations for sequences of exchangeable random variables. Specifically, we examine information-theoretic proofs of finite versions of de Finetti’s celebrated representation theorem. Such results state, in a quantitative manner, that the joint distribution of the first k of n > k exchangeable random variables is close to a mixture of product distributions. Closeness is measured in terms of the relative entropy and explicit bounds are typically provided. First we review a recent information-theoretic proof a finite de Finetti theorem for binary random variables, and then we give a different, new proof for the case of arbitrary finite alphabets. This second proof is nicely motivated by the Gibbs conditioning principle in connection with statistical mechanics, and it follows along an appealing sequence of steps. The technical estimates required for these steps are obtained via the method of types.A full version of this paper is available online as [23].

The problem of lossless data compression with side information available to both the encoder and the decoder is considered. The finite-blocklength fundamental limits of the best achievable performance are defined, in two different versions of the problem: Reference-based compression, when a single side information string is used repeatedly in compressing different source messages, and pair-based compression, where a different side information string is used for each source message. General achievability and converse theorems are established for arbitrary source-side information pairs. Nonasymptotic normal approximation expansions are proved for the optimal rate in both the reference-based and pair-based settings, for memoryless sources. These are stated in terms of explicit, finite-blocklength bounds, that are tight up to third-order terms. Extensions that go significantly beyond the class of memoryless sources are obtained. The relevant source dispersion is identified and its relationship with the conditional varentropy rate is established. Interestingly, the dispersion is different in reference-based and pair-based compression, and it is proved that the reference-based dispersion is in general smaller.

The problem of lossless data compression with side information available to both the encoder and the decoder is considered. The finite-blocklength fundamental limits of the best achievable performance are defined, in two different versions of the problem: Reference-based compression, when a single side information string is used repeatedly in compressing different source messages, and pair-based compression, where a different side information string is used for each source message. General achievability and converse theorems are established. Nonasymptotic normal approximation expansions are proved for the optimal rate with memoryless sources, in both the reference-based and pair-based settings. These are stated in terms of explicit, finite-blocklength bounds, that are tight up to third-order terms. Extensions that go significantly beyond the class of memoryless sources are obtained. The relevant source dispersion is identified and its relationship with the conditional varentropy rate is established. Interestingly, the dispersion is different in reference-based and pair-based compression, and it is proved that the reference-based dispersion is in general smaller.