12
$\begingroup$

The following problem arose for my collaborators and me when studying the computational complexity of the Maximum-Cut problem.

Let $f : \mathbb{R} \to \mathbb{R}$ be an odd function. Let $\rho \in [0,1]$. Let $X$ and $Y$ be standard Gaussians with covariance $\rho$. Prove that $\mathbf{E}[f(X)f(Y)]$ ≤ $\mathbf{E}[f(X)^2 \mathrm{sgn}(X) \mathrm{sgn}(Y)]$.

The quantity on the left-hand side arises naturally in many contexts; e.g., it is the integral of $f(x)f(y)$ against the Mehler kernel (with parameter $\rho$).

I have some reason to believe this inequality is true. For one piece of evidence, suppose $f$'s range is $\pm 1$. Then the inequality reduces to

$\mathbf{E}[f(X)f(Y)]$ ≤ $\mathbf{E}[\mathrm{sgn}(X) \mathrm{sgn}(Y)]$;

i.e., it's saying that $\mathrm{sgn}$ is the $\pm 1$-valued odd function maximizing the LHS. This is indeed true; it follows from a result of Christer Borell ("Geometric bounds on the Ornstein-Uhlenbeck velocity process"), proved by Ehrhard symmetrization. It was also given a different proof by Beckner, deducing it from a rearrangment inequality on the sphere.

The second inequality generalizes to the case of functions $f : \mathbb{R}^n \to$ {$-1,1$}, but I believe the first inequality, which I would like to prove, is inherently $1$-dimensional.

Any ideas, or pointers to literature that might help? Thanks!

$\endgroup$

2 Answers 2

5
$\begingroup$

Using the antisymmetry of $f$ and $\mathrm{sgn}$ to bring the expectations to integral expressions over $[0, \infty) \times [0, \infty)$, the first expectation takes the form:

$const\times \int f(x) f(y) \exp\left(-\frac{x^2+y^2}{2(1-\rho^2)}\right)\sinh\left(\frac{2\rho xy}{2(1-\rho^2)}\right) dx dy$

while for the second case $f(y)$ is replaced by $f(x)$.

The proof becomes an application of the Cauchy–Schwarz inequality.

$\endgroup$
10
$\begingroup$

That is just Cuchy-Schwartz (though pretty well hidden). Writing everything down in terms of the joint density, dropping irrelevant factors, and taking into account that $f(-t)=-f(t)$, we see that the inequality in question is equivalent to $$ \iint_{(0,+\infty)^2}e^{-\frac 12(x^2+y^2)}(e^{\rho xy}-e^{-\rho xy})f(x)f(y)dxdy\le \iint_{(0,+\infty)^2}e^{-\frac 12(x^2+y^2)}(e^{\rho xy}-e^{-\rho xy})f(x)^2 dxdy $$ Now, $$ e^{\rho xy}-e^{-\rho xy}=\sum_n c_n(\rho) x^ny^n $$ with $c_n(\rho)\ge 0$. Thus, it suffices to show that $$ \iint_{(0,+\infty)^2}e^{-\frac 12(x^2+y^2)}x^ny^nf(x)f(y)dxdy\le \iint_{(0,+\infty)^2}e^{-\frac 12(x^2+y^2)}x^ny^n f(x)^2 dxdy $$ But, since the integrands are pure products now, this rewrites as $$ \left[\int_{(0,+\infty)}e^{-\frac 12 x^2}x^n f(x)dx\right]^2\le \left[\int_{(0,+\infty)}e^{-\frac 12 x^2}x^n f(x)^2dx\right]\cdot \left[\int_{(0,+\infty)}e^{-\frac 12 x^2}x^n dx\right], $$ which is pure Cauchy-Schwartz.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.