Prékopa–Leindler inequality

Template:Short description 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.

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

for all x and y in Rⁿ. Then

$\Vert h{\Vert }_1:={\int }_{{ℝ}^n}h(x)\mathrm{d}x\ge {({\int }_{{ℝ}^n}f(x)\mathrm{d}x)}^{1-\lambda }{({\int }_{{ℝ}^n}g(x)\mathrm{d}x)}^{\lambda }=:\Vert f{\Vert }_1^{1-\lambda }\Vert g{\Vert }_1^{\lambda }.$

Essential form of the inequality

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

${\mathrm{e}\mathrm{s}\mathrm{s}\mathrm{s}\mathrm{u}\mathrm{p}}_{x\in {ℝ}^n}f(x)=inf\{t\in [-\mathrm{\infty },+\mathrm{\infty }]\mid f(x)\le t\text{ for almost all }x\in {ℝ}^n\}.$

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)={\mathrm{e}\mathrm{s}\mathrm{s}\mathrm{s}\mathrm{u}\mathrm{p}}_{y\in {ℝ}^n}f{\left(\frac{x-y}{1-\lambda }\right)}^{1-\lambda }g{\left(\frac{y}{\lambda }\right)}^{\lambda }.$

Then s is measurable and

$\Vert s{\Vert }_1\ge \Vert f{\Vert }_1^{1-\lambda }\Vert g{\Vert }_1^{\lambda }.$

The essential supremum form was given by Herm Brascamp and Elliott Lieb. 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 ((1-\lambda )A+\lambda B)\ge \mu (A{)}^{1-\lambda }\mu (B{)}^{\lambda },$

where μ denotes n-dimensional Lebesgue measure. Hence, the Prékopa–Leindler inequality can also be used 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 {((1-\lambda )A+\lambda B)}^{1/n}\ge (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

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

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

Let y₁, y₂ ∈ Rⁿ and 0 < λ < 1 be given. Then equation (Template:EquationNote) satisfies condition (Template:EquationNote) 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)\ge 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.

TheoremTemplate:Citation needed Let $A\subseteq {ℝ}^n$, and set $A_{ϵ}=\{x:d(x,A)<ϵ\}$. Let $\gamma (x)$ denote the standard Gaussian pdf, and $\mu$ its associated measure. Then $\mu (A_{ϵ})\ge 1-\frac{e^{-{ϵ}^2/4}}{\mu (A)}$.

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

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

This lemma can be proven from Prékopa–Leindler by taking $h(x)=\gamma (x),f(x)=e^{\frac{d(x,A{)}^2}{4}}\gamma (x),g(x)=1_A(x)\gamma (x)$ and $\lambda =1/2$. To verify the hypothesis of the inequality, $h(\frac{x+y}{2})\ge \sqrt{f(x)g(y)}$, note that we only need to consider $y\in A$, in which case $d(x,A)\le ||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)\le \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 $\int h(x)dx=1$, the PL-inequality immediately gives the lemma.

To conclude the concentration inequality from the lemma, note that on ${ℝ}^n\setminus A_{ϵ}$, $d(x,A)>ϵ$, so we have ${\int }_{{ℝ}^n}\exp (d(x,A{)}^2/4)d\mu \ge (1-\mu (A_{ϵ}))\exp ({ϵ}^2/4)$. Applying the lemma and rearranging proves the result. Template:Collapse bottom

Further reading

• Template:Cite book
• Template:Cite book