Overview
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 n → 0, +∞) be non-negative real-valued measurable functions defined on n-dimensional Euclidean space R n . Suppose that these functions satisfy for all x and y in R n . 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 n → 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 (R n ; 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. 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 n 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 to prove the Brunn–Minkowski inequality in its more familiar form: if 0 < λ n 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 .
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 n , so that by definition we have 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 1 , y 2 ∈ R n and 0 1 + λy 2 ), f(x) = H(x,y 1 ) and g(x) = H(x,y 2 ), 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 A \subseteq \mathbb R ^n , and set A_ \epsilon = \ x : d(x,A) . Let \gamma(x) denote the standard Gaussian pdf, and \mu its associated measure. Then \mu(A_ \epsilon ) \geq 1 - \frac e^ - \epsilon^2/4 \mu(A) . The proof of this theorem goes by way of the following lemma: Lemma In the notation of the theorem, \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 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 ) \geq \sqrt f(x) g(y) , note that we only need to consider y \in A , in which case 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 \int h(x) dx = 1 , the PL-inequality immediately gives the lemma. To conclude the concentration inequality from the lemma, note that on \mathbb R ^n \setminus A_ \epsilon , d(x,A) > \epsilon , so we have \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.