on concentration of information and log-concave distributions

Overview

This post analyzes the landmark result by Sergey Bobkov and Mokshay Madiman (Bobkov & Madiman, 2011) regarding the concentration of information in log-concave distributions. The central finding is that for any log-concave random vector $X\in {\mathbb{R}}^n$, the information functional $i(X)=-\log f(X)$ concentrates around its mean (the entropy) with sub-exponential tails. This property serves as a geometric substitute for independence, enabling the extension of the Shannon-McMillan-Breiman theorem to non-i.i.d. stochastic processes.

🏷️ Foundational Concepts

To understand the concentration results, we define the “surprise” of a distribution and the geometric constraints that stabilize it.

The Information Functional

For a random vector $X\in {\mathbb{R}}^n$ with density $f$, the Information Content $\tilde{h}(X)$ (also called “random entropy”) is:

$$\tilde{h}(X)=-\log f(X)$$

The outcome density $f(X)$ determines the “surprise” of a realization. Its average value is the Shannon Entropy, $h(X)=\mathbb{E}[\tilde{h}(X)]$.

Log-Concave Measures

A distribution is log-concave if its density $f$ can be written as $f(x)=e^{-V(x)}$ where $V$ is a convex function. This geometric regularity prevents the mass from spreading too thin or having multiple peaks, forcing the distribution into a “well-behaved” shape.

Prefix Notation

For a stochastic process $\mathbb{X}=(X_1,X_2,\dots )$, we define the prefix (or $n$-dimensional projection) as:

$$X^{(n)}=(X_1,X_2,\dots ,X_n)$$

This represents the first $n$ observations of the process, with $f_n$ denoting their joint density.

🏷️ Main Results: Concentration of Information

The primary contribution of the paper is proving that the random variable $\tilde{h}(X)$ stays extremely close to its mean $h(X)$ in high dimensions.

Theorem 1.1: Exponential Tail Concentration

If $X$ has a log-concave density $f$ on ${\mathbb{R}}^n$, then for all $t>0$:

$$\mathbb{P}\left\{|\tilde{h}(X)-h(X)|\ge t\sqrt{n}\right\}\le 2e^{-ct}$$

where $c=1/16$. The fluctuations of information grow only as $O(\sqrt{n})$, matching the Law of Large Numbers.

Corollary: Universal Variance Bound

For any log-concave random vector $X\in {\mathbb{R}}^n$, the variance of the information content satisfies:

$$\text{Var}(\log f(X))\le Cn$$

for some universal constant $C$. This confirms that the “random entropy” per coordinate stabilizes at the rate $1/\sqrt{n}$.

Proof: From Tail Concentration to Variance

The sub-exponential tail directly implies an $O(n)$ variance bound. Let $Z=|\tilde{h}(X)-h(X)|$. Using the tail integration formula:

$$\text{Var}(\log f(X))=\mathbb{E}[Z^2]={\int }_0^{\infty }\mathbb{P}(Z^2\ge u)du$$

Setting $u=t^{2}n$ and applying Theorem 1.1 ($\mathbb{P}\le 2e^{-ct}$):

$$\text{Var}(\log f(X))\le {\int }_0^{\infty }2e^{-ct}\cdot 2ntdt=4n{\int }_0^{\infty }t{e}^{-ct}dt=\frac{4}{c^2}n$$

Thus, the “average spread” of information grows linearly with dimension.

Theorem 1.2: Gaussian Regime

For smaller deviations ($0\le t\le 2\sqrt{n}$), the decay is even sharper (Gaussian):

$$\mathbb{P}\left\{\frac{1}{\sqrt{n}}|\log f(X)-\mathbb{E}\log f(X)|\ge t\right\}\le 3e^{-c{t}^2}$$

🏷️ Main Proof Strategy

The proof is an elegant multi-stage reduction from high dimensions down to 1D geometry, leveraging the multiscale preservation of log-concavity.

The 1D Baseline: Geometric Profile Stability

In 1D, the information is stable because of the concavity of the profile function $I(t)=f(F^{-1}(t))$, where $F$ is the CDF and $F^{-1}$ its inverse. For log-concave $f$, $I$ is concave on $(0,1)$. Using the identity for any function $\Psi$:

$$\iint \Psi (f(x),f(y))f(x)f(y)dxdy={\int }_0^1{\int }_0^1\Psi (I(t),I(s))dtds$$

Choosing $\Psi (u,v)=e^{\alpha |\log u-\log v|}$ and normalizing $I(1/2)=1/2$, concavity forces $I(t)\ge \min \{t,1-t\}$. This allows bounding the 1D MGF:

$$\mathbb{E}{e}^{\alpha |\log f(X)-\mathbb{E}\log f(X)|}\le {\int }_0^1{\int }_0^1{e}^{-\alpha \log \min \{t,s,1-t,1-s\}}dtds=\frac{2^{1+\alpha }}{(1-\alpha )(2-\alpha )}$$

For $\alpha =1/2$, the bound is 4, ensuring $\text{Var}(\log f(X))\le O(1)$ for all 1D log-concave distributions.

Reverse Lyapunov Inequalities: The Moment Engine

Standard Lyapunov inequalities state that $p\mapsto \log \mathbb{E}[{\eta }^p]$ is convex for any $\eta >0$. Bobkov and Madiman use a deep result by Borell (Borell, 1973) to show that for log-concave $\eta$, the normalized moment function ${\bar{\lambda }}_p=\mathbb{E}[{\eta }^p]/\Gamma (p+1)$ is log-concave. This is derived by considering the volume of convex bodies in ${\mathbb{R}}^n\times \mathbb{R}$ and taking the limit $n\to \infty$. This “reversed” stability ensures that moments of log-concave variables are tightly constrained, which is the key to bounding the fluctuations of $\log \eta$.

Log-Concavity of Order $p$ and the Trigamma Bound

A density $f(x)=x^{p-1}g(x)$ for log-concave $g$ has log-concavity of order $p$. The authors prove (Prop 4.1) that the concavity of $u(q)=\log \mathbb{E}[{\eta }^{q-1}]-\log \Gamma (q)$ implies:

$$u^{\prime \prime }(p)=\text{Var}(\log \xi )-{\psi }_1(p)\le 0⟹\text{Var}(\log \xi )\le {\psi }_1(p)$$

where ${\psi }_1(p)={\sum }_{k=0}^{\infty }(k+p{)}^{-2}$ is the trigamma function. Since ${\psi }_1(p)\sim 1/p$ for large $p$, higher-order log-concavity forces the random information to become extremely stable.

The Localization Engine: Reduction to Weighted Needles

Using the KLS Localization Lemma (Kannan, Lovász & Simonovits, 1995), any integral inequality in ${\mathbb{R}}^n$ is reduced to 1D “weighted needles” $\Delta$ with density $f_{\ell }(x)=\frac{1}{Z}f(x)\ell (x{)}^{n-1}$. The global fluctuation is decomposed as:

$$|\log f-{\mathbb{E}}_{\ell }\log f|\le |\log f_{\ell }-{\mathbb{E}}_{\ell }\log f_{\ell }|+(n-1)|\log \ell -{\mathbb{E}}_{\ell }\log \ell |$$

1. The first term is the 1D log-concave baseline (Step 1), contributing $O(1)$.
2. The second term involves the affine function $\ell$ weighted by ${\ell }^{n-1}$, which is log-concave of order $n$ (Step 3). Its fluctuations are $O((n-1)/\sqrt{n})=O(\sqrt{n})$. Combining these via the convexity of the MGF lifts the $O(1/n)$ needle-variance to the global $O(\sqrt{n})$ tail concentration.

🏷️ Application: The Strong Ergodic Theorem (SMB)

The most profound impact of this concentration is the extension of the Shannon-McMillan-Breiman (SMB) theorem.

Corollary 1.3: Extension of SMB

Let $\mathbb{X}=(X_1,X_2,\dots )$ be a discrete-time stochastic process with log-concave joint marginals. If the entropy rate $h(\mathbb{X})$ exists, then:

$$-\frac{1}{n}\log f_n(X^{(n)})\to h(\mathbb{X})\text{almost surely.}$$

Why this extension is transformative

• Geometry as a Substitute for Statistics: It replaces the traditional requirement of stationarity and mixing with joint convexity.
• Non-Asymptotic Utility: The $O(\sqrt{n})$ concentration provides a universal rate of convergence that mixing-based theorems often lack.
• High-Dimensional Stability: It proves that any system governed by a convex potential forms a “thin shell” of information in high dimensions, making its long-term average surprise perfectly predictable.

🏷️ Related Insights

• Thin Shell Hypothesis: Information concentration is the functional dual to mass concentration. In isotropic convex bodies, mass concentrates near a sphere of radius $\sqrt{n}$; here, surprise concentrates near the entropy $h(f)$.
• Isotropic Position: When $\text{Cov}(X)=I$, the theorem implies the density $f(x)$ is roughly constant on the $\sqrt{n}$-sphere.

🏷️ See Also

• on sum-product in finite fields via entropy --- Entropy as a measure of structural complexity in discrete settings.
• on eigenvalue estimate of kernel --- The spectral perspective of concentration of measure in log-concave spaces.

📚 References

🐻  Bobkov, S. & Madiman, M. 2011. Concentration of the information in data with log-concave distributions. The Annals of Probability 39(4).

🐻  Borell, C. 1973. Complements of lyapunov’s inequality. Mathematische Annalen 205(4), 323–331.

🐻  Kannan, R., Lovász, L. & Simonovits, M. 1995. Isoperimetric problems for convex bodies and a localization lemma. Discrete & Computational Geometry 13(3), 541–559.