# Bounding integral arising from expectation of a random variable satisfying Bernstein's inequality

Let $$X$$ be a random variable s.t. for $$v, b > 0$$ and $$C \geq 1$$:

$$P(X \geq t) \leq C\exp\left(-\frac{t^2}{2(v^2 + bt)} \right)$$

I am trying to show that $$\mathbb{E}X \leq 2v(\sqrt{\pi} + \sqrt{\log C}) + 4b(1 + \log C)$$.

In terms of progress I have made so far, I set $$X = \int_0^\infty P(X \geq t)dt$$, and have also made cases for when $$v^2 > bt$$ and otherwise (i.e. simplifying the exponentiated value to be $$-t^2/4v^2$$ in one case and $$-t^2/4bt$$ in the other).

This obtainis all the non $$C$$ values in the final inequality; However, I can't figure out how to squash the $$C$$ into the $$\log C$$ and $$\sqrt{\log C}$$ terms.

• You have a closing bracket missing in the second equation. Commented Mar 17, 2019 at 1:19

For $$t>0$$, we have $$v^2+bt\le\max(2bt,2v^2)$$, whence $$$$P(X\ge t)\le1\wedge\max[Q_1(t),Q_2(t)]\le[1\wedge Q_1(t)]+[1\wedge Q_2(t)],$$$$ where $$x\wedge y:=\min(x,y)$$, $$$$Q_1(t):=C\exp\Big(-\frac{t^2}{4bt}\Big),\quad Q_2(t):=C\exp\Big(-\frac{t^2}{4v^2}\Big).$$$$ So, $$$$EX=\int_0^\infty P(X\ge t)\,dt\le I_1+I_2,$$$$ where $$\begin{multline} I_1:=\int_0^\infty[1\wedge Q_1(t)]\,dt =4b\ln C+C\int_{4b\ln C}^\infty \exp\Big(-\frac{t}{4b}\Big)\,dt=4b(1+\ln C) \end{multline}$$ and $$\begin{multline} I_2:=\int_0^\infty[1\wedge Q_2(t)]\,dt =v\sqrt 2\int_0^\infty\min(1,Ce^{-s^2/2})\,ds \\ =v\sqrt 2\Big(\sqrt{2\ln C}+C\int_{\sqrt{2\ln C}}^\infty e^{-s^2/2}\,ds\Big) \le 2v\big(\sqrt{\ln C}+\sqrt\pi/2\big); \end{multline}$$ the latter inequality follows because $$\int_t^\infty e^{-s^2/2}\,ds\le\sqrt{\pi/2}\,e^{-t^2/2}$$ for $$t\ge0$$.
Thus, $$$$EX\le 4b(1+\ln C)+2v\big(\sqrt{\ln C}+\sqrt\pi/2\big),$$$$ which is a bit better than the bound requested in the OP, where we see $$\sqrt\pi$$ in place of $$\sqrt\pi/2$$.
• Thank you! On a more conceptual note, how is it that there is no linear dependence on $C$? I almost convinced myself this is impossible, since the LHS can be written as C*[some constant integral], whereas the right hand side only grows as $log(C)$. Commented Mar 17, 2019 at 13:46
• Since any probability is $\le1$, the tail bound actually available to us is of the form $1\wedge(Cq(t))$, which is nonlinear in $C$, and, in contrast with $Cq(t)$, does not grow with $C$ at all as soon as $C$ becomes large enough. After integration, the resulting bound does grow with $C$, but only logarithmically in $C$, much slower than $C$ itself. Commented Mar 17, 2019 at 14:02