Let XX be a non-negative random variable such that ∀t≥0\forall t \ge 0,

Pr⁡[X≥t]≤exp⁡(−2nt2). \begin{aligned} \Pr[ X \ge t] \le \exp \left( - 2 n t^2 \right). \end{aligned}

Then

E[X]=∫0∞Pr⁡[X≥t] dt≤∫0∞exp⁡(−2nt2) dt=σ2π⋅1σ2π∫0∞exp⁡(−t22σ2) dtσ≐14n=σ2π2⋅1σ2π∫−∞∞exp⁡(−t22σ2) dt=12⋅π2n. \begin{aligned} \mathbb{E}[ X ] &= \int_{0}^\infty \Pr[ X \ge t] \, dt \\ &\le \int_{0}^\infty \exp \left( - 2 n t^2 \right) \, dt \\ &= \sigma \sqrt{2 \pi} \cdot \frac{1}{ \sigma \sqrt{2 \pi} }\int_{0}^\infty \exp \left( - \frac{t^2 }{ 2 \sigma^2 } \right) \, dt & \sigma \doteq \sqrt{ \frac{1}{4n} } \\ &= \frac{\sigma \sqrt{2 \pi} }{ 2 }\cdot \frac{1}{ \sigma \sqrt{2 \pi} }\int_{ - \infty }^\infty \exp \left( - \frac{t^2 }{ 2 \sigma^2 } \right) \, dt \\ &= \frac{1}{2} \cdot \sqrt{ \frac{ \pi }{ 2n } }. \end{aligned}