15
$\begingroup$

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 $\log(4) \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.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ en.wikipedia.org/wiki/… $\endgroup$
    – Steve Huntsman
    Commented Jun 20, 2014 at 16:55
  • $\begingroup$ 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. $\endgroup$
    – user0820
    Commented Jun 20, 2014 at 18:33
  • 6
    $\begingroup$ 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/… ). $\endgroup$
    – Qiaochu Yuan
    Commented Jun 20, 2014 at 19:46
  • 8
    $\begingroup$ 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. $\endgroup$
    – fedja
    Commented Jun 20, 2014 at 20:03
  • 5
    $\begingroup$ 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 :-) $\endgroup$
    – fedja
    Commented Jun 20, 2014 at 21:13

3 Answers 3

Reset to default
17
$\begingroup$

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.

Improve this answer
$\endgroup$
6
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ @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. $\endgroup$
    – fedja
    Commented Jun 20, 2014 at 21:37
  • $\begingroup$ 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. $\endgroup$
    – user0820
    Commented Jun 20, 2014 at 21:44
  • $\begingroup$ @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 :-) $\endgroup$
    – fedja
    Commented Jun 20, 2014 at 21:47
  • $\begingroup$ My intuition for your solution is this: Pick $t$ such that (in expectation) exactly one of the random variables is above it. Then, in the sum $\sum_j \mathbb{E}(X_j-t)_+$, we have (in expectation) that all the terms are $0$, apart from one which is $\mathbb{E} X_j - t$, and it must be the maximum. But, the proof is not obvious to me. Also, the intuition explains only why $\mathbb{E}\max_j X_j$ is roughly $t+\sum_j\mathbb{E}(X_j-t)_+$, but not why the latter is an upper bound. I could, perhaps, figure it out with some work. $\endgroup$
    – rgrig
    Commented Apr 22, 2017 at 12:39
  • 3
    $\begingroup$ Since this post has been bumped and I don't think the idea here is that obvious, I believe it helpful to explain: for any $t$ at all, $E \max(X_j) = t + E\max(X_j - t) \leq t + E\max((X_j-t)_+) \leq t + \sum_j E(X_j-t)_+$. The first inequality is an equality if the largest $X_j$ always exceeds $t$, and the second is an equality if only the largest ever exceeds $t$ (so other terms are always zero). This is only possible for fedja's choice of $t$ and a worst-case correlation where with probability $1$, exactly one $X_j$ exceeds $t$. $\endgroup$
    – usul
    Commented Sep 8, 2017 at 5:31
4
$\begingroup$

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$.

Improve this answer
$\endgroup$
2
  • 6
    $\begingroup$ You assumed implicitly that (X,Y) is jointly Gaussian, which is not given. $\endgroup$
    – ofer zeitouni
    Commented Jun 21, 2014 at 20:37
  • $\begingroup$ 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. $\endgroup$
    – wolfies
    Commented Jun 22, 2014 at 6:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .