Entropy Power Inequalities for Discrete Random Variables

45 concepts20 papers2 proposals

When you mix two independent sources of random noise, the resulting combination is inherently more uncertain than either source alone. In continuous information theory, this intuition is beautifully formalized by Shannon’s Entropy Power Inequality (EPI). The EPI states that the "entropy power" (the variance of a Gaussian variable with the same entropy) of the sum of two independent continuous variables is at least the sum of their individual entropy powers:

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

In the continuous domain, this inequality works cleanly because the Gaussian distribution acts as a universal, smooth baseline. Any convolution of continuous variables tends to smooth out and spread the probability density, a phenomenon bounded by the geometry of vector spaces.

However, when we try to port this fundamental law to discrete random variables—such as integer-valued variables or variables defined on finite groups—the mathematical machinery grinds to a halt. Developing discrete counterparts to the EPI has historically been a major challenge in information theory. Understanding why the continuous EPI breaks down in discrete spaces reveals the deep structural friction between Shannon entropy and differential entropy, and illuminates how modern research resolves it.

The Scale Mismatch and Topological Friction

To understand why a discrete EPI is difficult to construct, we must look at two fundamental mismatches between discrete and continuous spaces: scale invariance and topological structure.

1. The Scale-Invariance Mismatch

Discrete Shannon entropy $H(X)$ is entirely scale-invariant. If you take an integer-valued random variable $X$ and multiply it by 2, you are merely relabeling the support of the distribution (e.g., the value 1 becomes 2, 2 becomes 4). The individual probabilities do not change, meaning the uncertainty remains identical: $H(2X) = H(X)$.

Continuous differential entropy $h(X)$, however, is highly scale-sensitive. Stretching a continuous distribution changes its volume, which directly alters its differential entropy: $h(2X) = h(X) + \log(2)$.

As Makkuva et al. and Wu demonstrate in their work on entropy inequalities, this asymmetry means that linear inequalities involving continuous variables can easily lead to mathematical contradictions if the coefficients are not perfectly balanced. Because discrete entropy ignores scaling while continuous entropy demands it, translating theorems between the two domains requires strict constraints.

2. The Lack of a Smooth Geometry

Continuous proofs of the EPI often rely on smooth geometric and physical analogies, such as heat flow, optimal transport, or Fisher information paths. These methods depend on a continuous topology that allows probability mass to diffuse smoothly.

As Madiman et al. point out in their analysis of cyclic groups, discrete spaces lack these topological properties. When you add two discrete variables, the "spreading effect" of the sum depends heavily on the exact shape of the probability mass function—whether it is highly spiky or flat. Furthermore, as noted by Wang et al., discrete entropy measures do not always converge cleanly to their continuous counterparts, creating a mathematical gap when analyzing data distributions.

Quantifying the Discrete Entropy Gap

If discrete variables do not expand smoothly like continuous ones, how can we guarantee a predictable lower bound on the entropy of their sum?

The breakthrough comes from shifting the focus from a smooth geometric expansion to a universal entropy gap function. In two foundational papers, Telatar et al. and Haghighatshoar established a new EPI specifically for integer-valued random variables (Telatar et al.).

Instead of trying to force the continuous exponential formulation onto integers, the authors proved that for independent integer-valued variables, the entropy of their sum exceeds their individual entropies by a predictable, strictly positive margin:

$$H(X+Y) \ge \max\{H(X), H(Y)\} + g(H(X), H(Y))$$

Here, $g$ is a universal, strictly positive "doubly-increasing" function.

Why the Gap Function Works

The intuition behind this function $g$ relies on analyzing the asymptotic behavior of discrete distributions. When the individual entropies are very low (spiky distributions), the act of addition forces a significant relative increase in the number of possible outcomes, creating a sharp jump in entropy. When the individual entropies are very large (flat, spread-out distributions), the discrete distribution begins to mimic a continuous one.

Remarkably, the authors showed that as the entropy increases, this discrete correction function $g$ asymptotically approaches $\log_2(e)$. This provides a rigorous discrete counterpart to the classic EPI, proving that discrete convolution forces a predictable minimum expansion of uncertainty regardless of the distribution's specific shape. Furthermore, this framework extends to conditional entropy scenarios, ensuring that this guaranteed increase in uncertainty holds even when systems contain side information.

The Boundary of Equivalence: Balanced vs. Affine

Given these structural differences, under what exact conditions do discrete and continuous entropy inequalities share the same mathematical validity?

Makkuva et al. established a definitive boundary by proving a fundamental equivalence: a linear inequality holds for discrete Shannon entropy if and only if it holds for continuous differential entropy, provided the inequality is balanced. An inequality is balanced when the sum of the coefficients on both sides equals zero (e.g., $H(X+Y) - H(X) - H(Y) \le 0$ is unbalanced, but expressions comparing matched differences are balanced).

The intuition here is elegant: when an inequality is balanced, any scaling factor applied to the variables cancels out perfectly. This eliminates the scale-sensitivity of differential entropy, allowing it to behave with the same scale-invariance as Shannon entropy.

However, Makkuva et al. showed that this equivalence completely breaks down for affine inequalities (inequalities that include a constant offset). The friction lies in how the two domains treat deterministic variables:

  • In the discrete world, a deterministic variable has exactly $H(X) = 0$. It contributes nothing to the uncertainty and can be eliminated from affine inequalities.
  • In the continuous world, a deterministic variable collapses to a Dirac delta function, which has a differential entropy of $-\infty$.

This divergence prevents a bidirectional mapping for affine expressions, meaning the continuous information environment is fundamentally more constrained than the discrete one.

Frontiers: Lattices, Groups, and Local Distances

The modern landscape of discrete entropy inequalities extends well beyond one-dimensional integers, adapting to various algebraic and structural contexts:

  • Prime Cyclic Groups: When adding variables within a finite cyclic group, the boundary effects of the group structure alter how entropy grows. Madiman et al. proved that the entropy power of a sum in these groups includes an explicit discrete correction term that is entirely absent in continuous settings, providing universal bounds for arbitrary probability mass functions.
  • The Integer Lattice ($\mathbb{Z}^d$): Moving to higher dimensions, Madiman et al. leveraged Sperner theory to establish Rényi entropy inequalities for uniform distributions on multi-dimensional integer lattices. However, finding sharp, dimension-dependent inequalities for arbitrary discrete distributions remains an open challenge.
  • Rényi Entropy Regimes: While standard EPIs focus on Shannon entropy, Melbourne extended continuous EPIs to Rényi entropy of orders between 0 and 1 for log-concave vectors. Translating these fractional entropy bounds to discrete settings is a critical next step for optimizing digital communication systems.
  • Local Discrepancies via Stein's Method: Rather than looking at global entropy growth from addition, Ley et al. focused on measuring the distance between discrete distributions. By introducing a "discrete Stein operator," they developed a local version of Pinsker's inequality. This provides tight, generalizable bounds between relative entropy and total variation distance relative to a fixed discrete target distribution, bypassing the need for distribution-specific assumptions.

Ultimately, while discrete random variables cannot be perfectly decomposed or scaled like their continuous counterparts (Li), the development of discrete correction functions, balanced linear equivalences, and discrete density operators allows information theorists to bound uncertainty in the digital world with the same mathematical rigor that Shannon brought to the analog one.

Key Foundational Work

A new entropy power inequality for integer-valued random variables (2013) — contributed 8 concept elements to this direction.
Local Pinsker Inequalities via Stein's Discrete Density Approach (2013) — contributed 3 concept elements to this direction.
Cumulative Residual Entropy, A New Measure of Information & its Application to Image Alignment (2003) — contributed 1 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_discrete_entropy_power_inequality_a5ed6e17,
  title = {discrete entropy power inequality},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/discrete-entropy-power-inequality/rdr_a5ed6e1762bf454e95fa274c2ab6178b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_discrete_entropy_power_inequality_a5ed6e17_v1,
  title = {discrete entropy power inequality},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/discrete-entropy-power-inequality/rdr_a5ed6e1762bf454e95fa274c2ab6178b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake