Entropy Bounds for Sums of Random Variables

15 concepts5 papers1 proposal

When we combine independent sources of data, their information mixes. Mathematically, adding two independent random variables $X$ and $Y$ corresponds to the convolution of their probability distributions. A fundamental challenge across information theory, statistics, and wireless communications is determining exactly how much entropy—or uncertainty—this combined sum contains.

The classical tool for this is Shannon’s Entropy Power Inequality (EPI), which provides a lower bound on the entropy of a sum. However, classical bounds can be loose because they treat all distributions with a given variance equally. Modern research shows that if we exploit the underlying structure of the variables—whether that structure is geometric, combinatorial, or physical—we can derive much tighter, more robust sum-set and entropy power inequalities.

Shape Constraints: The Power of Log-Concavity

Why do standard entropy bounds fall short? They often fail to account for the "shape" of a probability density function. Many natural distributions are log-concave, meaning the logarithm of their probability density function is concave. This family includes Gaussian, exponential, and uniform distributions. Log-concavity acts as a powerful structural regularizer: it dictates that the distribution is unimodal and lacks heavy tails or erratic spikes.

When independent log-concave variables are added together, their smooth geometry prevents their combined entropy from expanding uncontrollably. In A Family of Bayesian Cramér-Rao Bounds, and Consequences for Log-Concave Priors, Aras et al. demonstrate that independent log-concave random variables satisfy a reverse entropy power inequality. While the standard EPI bounds how small the entropy of a sum can be, this reverse inequality provides a tight upper-bound style characterization, offering a clearer picture of how information aggregates in probabilistic models.

This geometric predictability also extends beyond standard Shannon entropy. In On the Entropy Power Inequality for the Rényi Entropy of Order [0, 1], James Melbourne explores Rényi entropy, a generalized information measure that quantifies the diversity or "spread" of a distribution. Melbourne proves that for log-concave random vectors, the Rényi entropy power of a sum is super-additive for parameters between 0 and 1. This means the combined entropy power is strictly greater than or equal to the sum of their individual components, bridging a long-standing theoretical gap between functional geometry (the Brunn-Minkowski inequality) and information theory.

Discrete Spaces and Combinatorial Majorization

The calculus-based tools used to analyze continuous log-concave densities break down when we move to discrete, integer-valued random variables. In discrete spaces, we cannot rely on smooth derivatives to guarantee that a distribution is well-behaved.

To solve this, Mokshay Madiman, Liyao Wang, and Jae Oh Woo utilize a discrete analogue known as $\sharp$-log-concavity. In Majorization and Rényi entropy inequalities via Sperner theory, the authors connect the entropy of discrete sums to majorization theory and Sperner theory (a branch of combinatorics dealing with ordered sets).

Majorization provides a formal way to say that one probability distribution is more "spread out" or less concentrated than another. The authors establish a foundational majorization inequality for the convolution of independent $\sharp$-log-concave variables by mapping the problem to the combinatorial structure of partially ordered sets. They show that the convolution of these variables majorizes a specific "squeezed rearrangement" of the underlying probabilities. Because Rényi entropy preserves majorization ordering, this combinatorial link yields sharp, fundamental lower bounds on the entropy of discrete sums, giving researchers a mathematical tool to quantify the distributional spread of integer-valued data.

Aligned Image Sets in Wireless Networks

While statisticians use log-concavity to bound entropy in abstract spaces, wireless communication engineers face a highly practical version of the same problem: bounding the entropy of linear combinations of signals to determine network capacity.

In a multi-antenna (MIMO) broadcast channel, a transmitter sends mixed signals to multiple users simultaneously. If the transmitter has perfect knowledge of the channel, it can pre-code signals so they cancel out unwanted interference at each receiver. However, in reality, transmitters usually operate with partial Channel State Information at the Transmitter (CSIT). Under finite-precision channel knowledge, signals from different transmitters arrive at a receiver mixed together as a noisy linear combination: $A X + B Y$. To find the fundamental capacity limits—known as the Generalized Degrees of Freedom (GDoF)—engineers must find robust lower bounds on the entropy of these sums.

To tackle this, Arash Gholami Davoodi and Syed Ali Jafar developed the Aligned Image Sets (AIS) framework. The core intuition of AIS is geometric: it analyzes how many distinct combinations of transmitted signals can "align" or collapse into the same received signal from the perspective of an un-intended receiver.

Transmitted Signals (X, Y)  --->  Channel (Partial CSIT)  --->  Received Sum (AX + BY)
   [Distinct Points]               [Uncertain Alignment]          [Expanded Image Set]

If the channel coefficients $A$ and $B$ are uncertain, the signals cannot perfectly align to cancel each other out. In Sum-Set Inequalities From Aligned Image Sets: Instruments for Robust GDoF Bounds, the authors use this lack of alignment to prove that the "image set" (the range of possible outcomes) of the sum must be large. This geometric expansion translates directly into robust lower bounds on the entropy of bounded-density linear combinations.

By generalizing these sum-set inequalities to multi-antenna and multi-letter settings, the authors successfully mapped out the exact performance limits of complex networks. In a companion paper, Degrees of Freedom Region of the (M, N₁, N₂) MIMO Broadcast Channel With Partial CSIT: An Application of Sum-Set Inequalities Based on Aligned Image Sets, Davoodi et al. applied these sum-set inequalities to establish the definitive outer bounds for the 2-user MIMO broadcast channel, resolving a long-standing open problem in wireless information theory.

A Unified Perspective

Whether analyzing continuous densities, discrete integer distributions, or overlapping signals in a wireless channel, the underlying principle remains identical. Classical information-theoretic bounds often assume the worst-case scenario. By identifying and exploiting structural constraints—be it the geometric smoothness of log-concavity, the combinatorial order of $\sharp$-log-concavity, or the alignment limits imposed by partial CSIT—researchers can derive precise sum-set inequalities that accurately govern how information behaves when it mixes.

Key Foundational Work

Majorization and Rényi entropy inequalities via Sperner theory (2019) — contributed 8 concept elements to this direction.
Sum-Set Inequalities From Aligned Image Sets: Instruments for Robust GDoF Bounds (2020) — contributed 4 concept elements to this direction.
Degrees of Freedom Region of the (M, N₁, N₂) MIMO Broadcast Channel With Partial CSIT: An Application of Sum-Set Inequalities Based on Aligned Image Sets (2020) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_sum_set_inequalities_d04a099d,
  title = {sum-set inequalities},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sum-set-inequalities/rdr_d04a099d1950499189a2a9ca15f3a178},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_sum_set_inequalities_d04a099d_v1,
  title = {sum-set inequalities},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sum-set-inequalities/rdr_d04a099d1950499189a2a9ca15f3a178/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake