Let $X$ be a non-negative random variable and $p \geq e$, $q > 0$ be two constant values such that
$$
P [X \geq x] \leq p e^{-x^2/q^2} \quad \forall x \geq 0.
$$
Prove that
$$
\mathbb{E}[X] \leq q(1+\sqrt{\log p}).
$$
There's my first attempt. Using the identity
$$
\mathbb{E}[X] = \int_0^\infty (1-F(x)) d x – \int_{-\infty}^0 F(x) d x
$$
and the fact that $X \geq 0$ I obtain:
$$
\mathbb{E}[X] = \int_0^\infty (1-F(x)) d x
$$
and using the hypothesis I get
$$
\mathbb{E}[X] \leq \int_0^{+\infty} p e^{-x^2/q^2} d x = pq \int_0^{+\infty} e^{-z^2} dz = \frac{pq \sqrt{\pi}}{2}
$$
where the last equality is given by the gaussian integral.
But then I'm stuck.
The second attempt I tried was to partition the events set in some smart way, that is using $( X \geq q )$ or $(X \geq \sqrt{\log p} )$ but I couldn't go anywhere.
Best Answer
By replacing $X$ with $X/q$, we can w.l.o.g. assume $q = 1$.
Note that the inequality $\mathbb{P}(X \ge x) \le p e^{-x^2}$ is a strong inequality for large $x$, but rather poor for small $x$. Indeed, for $x = 0$ this only yields $\mathbb{P}(X \ge x) \le p$, which by assumption is greater than $e$. Since Probabilities are bounded by $1$, this inequality is poor when $pe^{-x^2} > 1$, or equivalently $x < \sqrt{\log(p)}$. We should therefore split up the integral:
$$\mathbb{E}[X] = \int_0^\infty \mathbb{P}(X \ge x) \,dx = \int_0^\sqrt{\log(p)} \mathbb{P}(X \ge x) \, dx + \int_{\sqrt{\log(p)}}^\infty \mathbb{P}(X \ge x) \, dx.$$
Now the first term is bounded by $\sqrt{\log(p)}$. For the second term, use the inequality in the assumption, as well as $e^{-x^2} \le x e^{-x^2}$ for $x \ge 1$.