# Proof (at least name or source) of this probability inequality?

I stumbled upon this beautiful piece of inequality : I'd appreciate very much if anyone can provide me a source where I can find the proof of this inequality. Does it have a name? (It must! But I don't know where to look.)

• Let's start with: where did you find the theorem? – Raskolnikov Jan 25 '18 at 8:29
• There are a number of comments I would like to make on the statement. The wording makes $c_1$,$c_2$ possibly depend on $\epsilon$ but nu such inequality can be proved in this case. Let us assume that $c_1$,$c_2$ are constants. We have EX_n= \int_0 {\infty} P\{X_n >\epsilon d \epsilon$and we can get a bound for$EX_n$using this. This is the best inequality you can get and there won't be a$log (c_1)$on the right side. So the exact inequality seems doubtful. – Kavi Rama Murthy Jan 25 '18 at 8:42 • Hmmm... So when$c_1=e^{-1}$,$E(X_n)=0$? Obviously wrong. For a more detailed reduction, please see my answer. – Did Jan 25 '18 at 8:43 • @Raskolnikov Here's the source : npslagle.info/articles/onehundredprobabilityinequalities.pdf page 3, number 4. – nami_op Jan 25 '18 at 8:53 • There's a reference to a lecture for your inequality, so that answers already part of your question. – Raskolnikov Jan 25 '18 at 8:55 ## 1 Answer Probably no name. For a proof, first note that the hypothesis that $$c_1>0\qquad c_2>e^{-1}$$ should read $$c_1>e^{-1}\qquad c_2>0$$ for the conclusion to make sense and let us choose values of the parameters such that $$c_1=c\qquad c_2n=1$$ Replacing$X_n$by$\sqrt{c_2n}X$, this is not a loss of generality, thus it suffices to consider the case when, for every$x>0$, $$P(X>x)\leqslant ce^{-x^2}$$ Then $$E(X)=\int_0^\infty P(X>x)dx$$ Thus, if$c<1$, $$E(X)\leqslant\int_0^\infty ce^{-x^2}dx=c\frac{\sqrt{\pi}}2$$ so the task in this case is to prove that, for every$c$in$(e^{-1},1)$, $$c\frac{\sqrt{\pi}}2\leqslant\sqrt{1+\log c}$$ or, equivalently, that for every$a$in$(0,1)$, $$e^{-a}\frac{\sqrt{\pi}}2\leqslant\sqrt{1-a}\tag{1}$$ On the other hand, if$c>1$, $$E(X)\leqslant\int_0^{\sqrt{\log c}}dx+\int_{\sqrt{\log c}}^\infty ce^{-x^2}dx$$ so the task in this case is to prove that, for every$c>1$, $$\sqrt{\log c}+\int_{\sqrt{\log c}}^\infty ce^{-x^2}dx\leqslant\sqrt{1+\log c}$$ or, equivalently, that, for every$a>0$, $$a+\int_a^\infty e^{a^2-x^2}dx\leqslant\sqrt{1+a^2}\tag{2}$$ The trouble with all this is that your problem is really equivalent to proving$(1)$and$(2)$and that$(1)$is obviously wrong. Edit: It appears that, while$(1)$is wrong, the desired inequality holds when$c>1$. Since the technique used in the notes mentioned in a comment below works in this case, avoids completely the clumsy inequality$(2)$above, and is, independently of the specific question at hand, worthy of being remembered, we outline it here. Again, one starts from the hypothesis that$X\geqslant0$almost surely and that, for some$c\geqslant1$, for every$x\geqslant0$, $$P(X>x)\leqslant ce^{-x^2}$$ Then one makes the apparent détour of considering$Y=X^2$instead of$X$... Thus, for every$y\geqslant0$, $$P(Y> y)=P(X>\sqrt y)\leqslant ce^{-y}$$ hence $$E(X^2)=E(Y)=\int_0^\infty P(Y> y)dy\leqslant\int_0^{\log c}dy+\int_{\log c}^\infty ce^{-y}dy=(\log c)+1$$ hence, using Cauchy-Schwarz inequality, $$E(X)\leqslant\sqrt{E(X^2)}\leqslant\sqrt{1+\log c}$$ To sum up the above, passing by$X^2$, one loses a bit due to Cauchy-Schwarz but one gains a lot because the primitives of$e^{-y}$are handier than those of$e^{-x^2}$. Cute... • I understood your argument. On the other hand, Larry Wasserman apparently gave a proof here : stat.cmu.edu/~larry/=stat705/Lecture2.pdf (page 7). I'm confused. – nami_op Jan 25 '18 at 9:03 • The mistake in the notes you linked to is that, in the notations there, they first assume that $$a>0$$ then they choose $$a=\frac{\log c_1}{nc_2}$$ under the only conditions that $$nc_2>0\qquad c_1>1/e$$ If$c_1<1$, this can only lead to chaos since then, $$\frac{\log c_1}{nc_2}<0$$ If$c_1>1$, their approach is sound. (But anyway, please correct the irritating condition$c_2>1/e$in your question...) – Did Jan 25 '18 at 9:53 • Thanks! I'm kinda shocked to see this in Wasserman's notes. I mean not because of the technical mistake, that's probably been done by a TA. But the wrong statement of the theorem is really shocking. – nami_op Jan 25 '18 at 10:02 • Hmmm, these are only humans, you know? Even LW... Time better spent trying to understand and remember the cute détour by$X^2\$ in the proof. – Did Jan 25 '18 at 10:12
• Thanks a lot for the detailed edit, explaining the nice trick! – nami_op Jan 25 '18 at 10:48