Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

Using the antisymmetry of f and sgn to bring the expectations to integral expressions over [0, inf) x [0, inf), the first expectation takes the form:

const* int f(x) f(y) exp(-(x^2+y^2)/(2*(1-rho^2))) sinh(2*rho*x*y/(2*(1-rho^2))) dx dy

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

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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