# Upper bound on the expectation from Bernstein-type inequality

Let $$Z$$ be a nonnegative random variable satisfying the following concentration inequality for all $$t\ge 0$$:

$$\mathbb{P}[Z\ge t]\le C e^{-\frac{t^2}{2(1+t)}}$$

(for some $$C\ge 1$$)

Then:

$$\mathbb{E}[Z]\le 2(\sqrt{\pi}+\sqrt{\log C})+4(1+\log C)$$

This is basically exercise 2.8 from High-Dimensional Statistics: A Non-Asymptotic Viewpoint. I tried to use:

$$\mathbb{E}[Z]=\int_0^\infty \mathbb{P}[Z\ge t]\, dt\le C\int_0^\infty e^{-\frac{t^2}{2(1+t)}}\, dt$$

But I don't know how to upper bound the term in the integral (also, I don't see how I would get $$\log C$$ or $$\sqrt{\log C}$$ terms from this expression). Is there another way to get $$\mathbb{E}[Z]$$ from $$\mathbb{P}[Z\ge t]$$?

• The $\ln C$ term appears if you use$$P(Z\geqslant t)\leqslant\min\left(C\exp\left(-\frac{t^2}{2(1+t)}\right),1\right)$$instead. Commented Jul 8, 2020 at 13:35
• @Saad: Thank you. That was indeed the idea I was missing. I just answered my own question following your hint. Commented Jul 8, 2020 at 21:25

Thanks to the hint of @Saad in comments, I am now able to finish the proof.

First I separate the summand in the integral into two parts (the first one will be relevant when $$t$$ is small, the second one when $$t$$ is large):

$$\exp\left(-\frac{t^2}{2(1+t)}\right)\le \exp\left(-\frac{t^2}{4\max(1,t)}\right)\le e^{-t^2/4}+e^{-t/4}$$

Now I can use the hint in the following way:

$$\mathbb{E} Z=\int_0^\infty\mathbb{P}[Z\ge t]\le \int_0^\infty \min\left(C \exp\left(-\frac{t^2}{2(1+t)}\right),1\right)\,dt\le A+B$$

with:

$$A=\int_0^\infty \min(C e^{-t^2/4},1)\,dt$$ $$B=\int_0^\infty \min(C e^{-t/4},1)\,dt$$

For $$B$$ the crossing point of the two regimes is for $$t=4 \log C$$, hence:

$$B\le 4\log C+\int_{4\log C}^\infty C e^{-t/4}\,dt=4(\log C+1)$$

For $$A$$ it happens at $$t=2\sqrt{\log C}$$, so that:

$$A\le 2\sqrt{\log C}+\int_{2\sqrt{\log C}}^\infty Ce^{-t^2/4}\,dt$$

And the integral can be upper bounded as follows:

$$\int_{2\sqrt{\log C}}^\infty Ce^{-t^2/4}\,dt=\sqrt{2} C\int_{\sqrt{2\log C}}^\infty e^{-t^2/2}\,dt\le 2\sqrt{\pi}$$

where I used the standard inequality:

$$\int_x^\infty e^{-t^2/2}\, dt\le \sqrt{2\pi} e^{-x^2/2}$$