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

The main purpose of the following question is to get some intuition and deeper understanding why the presented method works which would hopefully help me in trying to adapt it to the setting I am dealing with in my research.

Let $X,Y\sim N(0,1)$, not necessarily independent. Suppose we want to find an upper bound for $\mathbb{E}\max(X,Y)$.

The most obvious approach would be something like the following $$\mathbb{E}\max(X,Y)\leq \mathbb{E}|X|+\mathbb{E}|Y|=2\sqrt{2/\pi}\approx 1.59$$

However, I've found the trick in the literature that uses Laplace transform to get something better. Although the idea is much less obvious, details are still easy. For any $\lambda >0$, Jensen's inequality gives us the following

$$\mathbb{E}\max(X,Y) \leq \frac1{\lambda}\log\left(\mathbb{E}e^{\lambda\max(X,Y)}\right)\leq \frac1{\lambda}\log\left(\mathbb{E}e^{\lambda X}+\mathbb{E}e^{\lambda Y}\right) = \frac{\log(2e^{\lambda^2/2})}{\lambda}.$$ Minimizing this gives us the upper bound $\approx 1.17$, which is better than the previous approach.

Now, my question is, heuristically/intuitively, why is second method better? Or to put in a different way, is there some easy way to see that the second method should give a better bound even before doing the actual calculations that confirm this?

At this stage, I don't have any intuition for why this works, and I am certainly not fine with that's the standard trick researchers in the field use.

share|improve this question
1  
    
I am not sure this is satisfactory enough. It's still not clear to me why the second method should be better on a conceptual level. In other words, I would hope for something that wouldn't rely on the fact that we know the exact distribution of $\max(X,Y)$. For example, let's consider the general situation when X and Y are not necessarily independent. –  user0810 Jun 20 at 18:33
4  
The fact that you know $\mathbb{E}(e^{\lambda X})$ is a reflection of the fact that you have control over all of the moments of $X$; the first argument uses weaker assumptions, and in particular doesn't assume that even the second moments exist (but on the other hand applies in much greater generality). It shouldn't be surprising that assuming more about moments gets you a stronger bound. (I picked up this idea from Terence Tao: see, for example, terrytao.wordpress.com/2010/01/03/… ). –  Qiaochu Yuan Jun 20 at 19:46
5  
The ultimate reason in the case presented is that doing something even minimally smart is always better than doing something stupid in every possible respect. It is not the Laplace trick that is better here, but the estimate $\max(X,Y)\le|X|+|Y|$ that is worse. Even if you improve it to something as obvious as $\max(X,Y)\le \max(X,0)+\max(Y,0)$, you get a two-fold gain immediately resulting in $1.59/2\approx 0.8$, which beats the Laplace estimate hands down. –  fedja Jun 20 at 20:03
2  
Unfortunately, the whole point I'm trying to make (perhaps too aggressively, I apologize again for that) is that the second method is pretty much as illogical as the first and it works better just because to get a bound worse than that of the first method without immediately seeing a way to improve it is next to impossible. So, any comparison of these two will illuminate next to nothing. What should be done instead is to think for a few minutes of what the worst possible case is (I posted it in my answer) and then you'll see everything there is to see here yourself :-) –  fedja Jun 20 at 21:13

3 Answers 3

First, an upper bound that beats your second bound is the following: use the equality $$\max(a,b)=(a+b+|a-b|)/2.$$ Then $$E\max(X,Y)=E|X-Y|/2\leq \frac{1}{2} (E|X|+E|Y|)=E|X|=\sqrt{2/\pi}\sim 0.798$$ This bound cannot be improved as the case $Y=-X$ shows.

So you see that your second bound is better not because you used the exponential moments, but rather because your first bound controls the max function way too brutally - you lost a factor of $2$. The advantage of the second method over the little trick I showed above is that it generalizes better when you deal with the max of more than two variables.

share|improve this answer

What should be really done is as follows. Suppose that $X_1,\dots,X_n$ are any real random variables for which individual distribution laws are known but no information is given on the joint distribution law. Choose $t$ such that $\sum_jP(X_j>t)\le 1\le \sum_jP(X_j\ge t)$. Then $E\max(X_j)\le t+\sum_jE(X_j-t)_+$ and the bound is the best possible.

I wonder when we will finally realize that if somebody has trouble finding the antiderivative of $\frac{x+1}{x^2\sqrt{x^2+4}}$, this will, most likely, never affect his work in mathematics, but if somebody doesn't see things like this one, his education has been thoroughly screwed up. When shall we stop teaching calculus and start teaching analysis at least at the most basic level?

I apologize for the rant, but there is a limit to everything. I do not blame the students, but I'd like everyone who comes to the class with a book by Stewart in hand think of this thread a bit before coming to the blackboard.

share|improve this answer
1  
@Proba Good point. However, the answer stays: there is no intuition, just whoever did it recalled (consciously or unconsciously) the Bernstein estimate for the sum of independent Gaussians (where it makes sense because the exponential function is pretty much the only non-trivial one that allows an easy computation of the expectation) and decided to do the same and see what comes out of it. There is absolutely no reason to prefer $e^{\lambda x}$ to $x^p$ or $e^{\lambda x^2}$ and "Laplace transform" is nothing more than a buzzword in this particular case. –  fedja Jun 20 at 21:37
    
Thanks, this last comment is exactly something I was hoping to hear, i.e. whether there is something clever about $e^{\lambda x}$ or this is just something that's computable and at the same time gives something nontrivial. –  user0810 Jun 20 at 21:44
    
@Proba Anyway, putting all other things aside, if you had asked about the actual setup you have instead of all this, there would be much less room for misinterpretation and the responses would be much more beneficial to you. So, I suggest we scrap this discussion and start the one that is more interesting for everybody involved :-) –  fedja Jun 20 at 21:47

Given: $X \sim N(0,1)$ and $Y \sim N(0,1)$ where $X$ and $Y$ may be correlated.

If we assume that the underlying Normals are jointly Normal, then (a) the exact answer is quite simple, and (b) we can do much better, conditioning the maximum bound on the correlation coefficient. In particular, if $(X,Y)$ are bivariate Normal with correlation $\rho$, then the joint pdf $f(x,y)$ is:

Then, $E\big[Max[X,Y]\big]$ is:

where I am using the Expect function from the mathStatica package for Mathematica to automate the nitty gritties. Plainly, the expected maximum is contingent on $\rho$, as a quick plot illustrates:

As @oferzeitouni noted, the maximum possible value is $\sqrt{\frac{2}{\pi}}$, which is attained when $\rho = -1$.

share|improve this answer
3  
You assumed implicitly that (X,Y) is jointly Gaussian, which is not given. –  ofer zeitouni Jun 21 at 20:37
    
Actually, explicitly ... it nests all the requirements that the marginal distributions of $X$ and $Y$ are standard Normal as well as any desired correlation $\rho$ between $X$ and $Y$, ... though there would be, of course, alternative models. The real point is to illustrate that the maximum bound will be a function of $\rho$, ... whereas to merely describe it as $\sqrt{\frac{2}{\pi}}$ is a bit of a broad sword that lacks proper aim. –  wolfies Jun 22 at 6:48

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.