Prékopa–Leindler inequality

In mathematics, the Prékopa–Leindler inequality is an integral inequality closely related to the reverse Young's inequality, the Brunn–Minkowski inequality and a number of other important and classical inequalities in analysis. The result is named after the Hungarian mathematicians András Prékopa and László Leindler.[1][2]

Statement of the inequality

Let 0 < λ < 1 and let f, g, h : Rⁿ → [0, +∞) be non-negative real-valued measurable functions defined on n-dimensional Euclidean space Rⁿ. Suppose that these functions satisfy

h\left((1-\lambda )x+\lambda y\right)\geq f(x)^{1-\lambda }g(y)^{\lambda }

(1)

for all x and y in Rⁿ. Then

\|h\|_{1}:=\int _{\mathbb {R} ^{n}}h(x)\,\mathrm {d} x\geq \left(\int _{\mathbb {R} ^{n}}f(x)\,\mathrm {d} x\right)^{1-\lambda }\left(\int _{\mathbb {R} ^{n}}g(x)\,\mathrm {d} x\right)^{\lambda }=:\|f\|_{1}^{1-\lambda }\|g\|_{1}^{\lambda }.

Essential form of the inequality

Recall that the essential supremum of a measurable function f : Rⁿ → R is defined by

\mathop {\mathrm {ess\,sup} } _{x\in \mathbb {R} ^{n}}f(x)=\inf \left\{t\in [-\infty ,+\infty ]\mid f(x)\leq t{\text{ for almost all }}x\in \mathbb {R} ^{n}\right\}.

This notation allows the following essential form of the Prékopa–Leindler inequality: let 0 < λ < 1 and let f, g ∈ L¹(Rⁿ; [0, +∞)) be non-negative absolutely integrable functions. Let

s(x)=\mathop {\mathrm {ess\,sup} } _{y\in \mathbb {R} ^{n}}f\left({\frac {x-y}{1-\lambda }}\right)^{1-\lambda }g\left({\frac {y}{\lambda }}\right)^{\lambda }.

Then s is measurable and

\|s\|_{1}\geq \|f\|_{1}^{1-\lambda }\|g\|_{1}^{\lambda }.

The essential supremum form was given by Herm Brascamp and Elliott Lieb.[3] Its use can change the left side of the inequality. For example, a function g that takes the value 1 at exactly one point will not usually yield a zero left side in the "non-essential sup" form but it will always yield a zero left side in the "essential sup" form.

Relationship to the Brunn–Minkowski inequality

It can be shown that the usual Prékopa–Leindler inequality implies the Brunn–Minkowski inequality in the following form: if 0 < λ < 1 and A and B are bounded, measurable subsets of Rⁿ such that the Minkowski sum (1 − λ)A + λB is also measurable, then

\mu \left((1-\lambda )A+\lambda B\right)\geq \mu (A)^{1-\lambda }\mu (B)^{\lambda },

where μ denotes n-dimensional Lebesgue measure. Hence, the Prékopa–Leindler inequality can also be used[4] to prove the Brunn–Minkowski inequality in its more familiar form: if 0 < λ < 1 and A and B are non-empty, bounded, measurable subsets of Rⁿ such that (1 − λ)A + λB is also measurable, then

\mu \left((1-\lambda )A+\lambda B\right)^{1/n}\geq (1-\lambda )\mu (A)^{1/n}+\lambda \mu (B)^{1/n}.

Applications in probability and statistics

Log-concave distributions

The Prékopa–Leindler inequality is useful in the theory of log-concave distributions, as it can be used to show that log-concavity is preserved by marginalization and independent summation of log-concave distributed random variables. Since, if $X,Y$ have pdf $f,g$ , and $X,Y$ are independent, then $f\star g$ is the pdf of $X+Y$ , we also have that the convolution of two log-concave functions is log-concave.

Suppose that H(x,y) is a log-concave distribution for (x,y) ∈ R^m × Rⁿ, so that by definition we have

H\left((1-\lambda )(x_{1},y_{1})+\lambda (x_{2},y_{2})\right)\geq H(x_{1},y_{1})^{1-\lambda }H(x_{2},y_{2})^{\lambda },

(2)

and let M(y) denote the marginal distribution obtained by integrating over x:

M(y)=\int _{\mathbb {R} ^{m}}H(x,y)\,dx.

Let y₁, y₂ ∈ Rⁿ and 0 < λ < 1 be given. Then equation (2) satisfies condition (1) with h(x) = H(x,(1 − λ)y₁ + λy₂), f(x) = H(x,y₁) and g(x) = H(x,y₂), so the Prékopa–Leindler inequality applies. It can be written in terms of M as

M((1-\lambda )y_{1}+\lambda y_{2})\geq M(y_{1})^{1-\lambda }M(y_{2})^{\lambda },

which is the definition of log-concavity for M.

To see how this implies the preservation of log-convexity by independent sums, suppose that X and Y are independent random variables with log-concave distribution. Since the product of two log-concave functions is log-concave, the joint distribution of (X,Y) is also log-concave. Log-concavity is preserved by affine changes of coordinates, so the distribution of (X + Y, X − Y) is log-concave as well. Since the distribution of X+Y is a marginal over the joint distribution of (X + Y, X − Y), we conclude that X + Y has a log-concave distribution.

Applications to concentration of measure

The Prékopa–Leindler inequality can be used to prove results about concentration of measure.

Theorem Let ${\textstyle A\subseteq \mathbb {R} ^{n}}$ , and set ${\textstyle A_{\epsilon }=\{x:d(x,A)<\epsilon \}}$ . Let ${\textstyle \gamma (x)}$ denote the standard Gaussian pdf, and ${\textstyle \mu }$ its associated measure. Then ${\textstyle \mu (A_{\epsilon })\geq 1-{\frac {e^{-\epsilon ^{2}/4}}{\mu (A)}}}$ .

Proof of concentration of measure

The proof of this theorem goes by way of the following lemma:

Lemma In the notation of the theorem, ${\textstyle \int _{\mathbb {R} ^{n}}\exp(d(x,A)^{2}/4)d\mu \leq 1/\mu (A)}$ .

This lemma can be proven from Prékopa–Leindler by taking ${\textstyle h(x)=\gamma (x),f(x)=e^{\frac {d(x,A)^{2}}{4}}\gamma (x),g(x)=1_{A}(x)\gamma (x)}$ and ${\textstyle \lambda =1/2}$ . To verify the hypothesis of the inequality, ${\textstyle h({\frac {x+y}{2}})\geq {\sqrt {f(x)g(y)}}}$ , note that we only need to consider ${\textstyle y\in A}$ , in which case ${\textstyle d(x,A)\leq ||x-y||}$ . This allows us to calculate:

(2\pi )^{n}f(x)g(x)=\exp({\frac {d(x,A)}{4}}-||x||^{2}/2-||y||^{2}/2)\leq \exp({\frac {||x-y||^{2}}{4}}-||x||^{2}/2-||y||^{2}/2)=\exp(-||{\frac {x+y}{2}}||^{2})=(2\pi )^{n}h({\frac {x+y}{2}})^{2}.

Since ${\textstyle \int h(x)dx=1}$ , the PL-inequality immediately gives the lemma.

To conclude the concentration inequality from the lemma, note that on ${\textstyle \mathbb {R} ^{n}\setminus A_{\epsilon }}$ , ${\textstyle d(x,A)>\epsilon }$ , so we have ${\textstyle \int _{\mathbb {R} ^{n}}\exp(d(x,A)^{2}/4)d\mu \geq (1-\mu (A_{\epsilon }))\exp(\epsilon ^{2}/4)}$ . Applying the lemma and rearranging proves the result.

References

Prékopa, András (1971). "Logarithmic concave measures with application to stochastic programming" (PDF). Acta Sci. Math. 32: 301–316.
Prékopa, András (1973). "On logarithmic concave measures and functions" (PDF). Acta Sci. Math. 34: 335–343.
Herm Jan Brascamp; Elliott H. Lieb (1976). "On extensions of the Brunn–Minkowski and Prekopa–Leindler theorems, including inequalities for log concave functions and with an application to the diffusion equation". Journal of Functional Analysis. 22 (4): 366–389. doi:10.1016/0022-1236(76)90004-5.
Gardner, Richard J. (2002). "The Brunn–Minkowski inequality" (PDF). Bull. Amer. Math. Soc. (N.S.). 39 (3): 355–405 (electronic). doi:10.1090/S0273-0979-02-00941-2. ISSN 0273-0979.