Exercise 2.8: Bernstein and Expectations
(a)
Since \(Z \geq 0\) by assumption and we are given a bound on the tail probability of \(Z\), a natural first step is to invoke the layer cake identity \(\E [Z] = \int_0^\infty \P (Z \geq t) \, \sd t\). However, the Bernstein-type bound is not easy to integrate when substituted in the form of equation (2.63). We thus first convert into the sub-exponential style bound by separately considering (i) small \(t \leq \nu^2 / b\) where \(\exp \{- \frac{t^2}{2(\nu^2 + bt)}\} \leq \exp \{- \frac{t^2}{4 \nu^2}\}\), and (ii) large \(t > \nu^2 / b\) where \(\exp \{ - \frac{t^2}{2(\nu^2 + bt)} \} \leq \exp \{- \frac{t}{4 b} \}\). Applying the layer cake identity with the implied upper bound \begin{align} \E [Z] = \int_{0}^\infty \P (Z \geq t ) \, \sd t \leq \underbrace{ \int_{0}^\infty 1 \wedge \bigl( C e^{-\frac{t^2}{4 \nu^2}} \bigr) \, \sd t }_{\text{(i)}} + \underbrace{ \int_{0}^\infty 1 \wedge \bigl( C e^{-\frac{t}{4 b}} \bigr) \, \sd t }_{\text{(ii)}} \, . \end{align}
(i)
Introducing an auxiliary parameter \(\alpha \geq 0\) which we will optimise later \begin{align} \int_{0}^\infty 1 \wedge \bigl( C e^{-\frac{t^2}{4 \nu^2}} \bigr) \, \sd t \leq \alpha + C \int_{\alpha}^\infty e^{-\frac{t^2}{4 \nu^2}} \, \sd t \overset{u = \frac{t}{2 \nu}}{=} \alpha + 2 \nu C \int_{0}^\infty e^{-(u + \frac{\alpha}{2 \nu})^2} \, \sd u \, . \end{align} Substituting \(\alpha = 2 \nu \sqrt{\log C}\) and noticing \begin{align} (u + \sqrt{\log C})^2 = u^2 + \log C + 2 u \sqrt{\log C} \geq u^2 + \log C \, , \end{align} for all \(u \geq 0\), implies \begin{align} \int_{0}^\infty 1 \wedge \bigl( C e^{-\frac{t^2}{4 \nu^2}} \bigr) \, \sd t \leq 2 \nu \left( \sqrt{\log C} + \int_{0}^\infty e^{- u^2} \, \sd u \right) = 2 \nu \left( \sqrt{\log C} + \frac{\sqrt{\pi}}{2} \right) \, . \end{align}
(ii)
Again introducing an auxiliary parameter \(\beta \geq 0\) which we will optimise later \begin{align} \int_{0}^\infty 1 \wedge \bigl( C e^{-\frac{t}{4 b}} \bigr) \, \sd t \leq \beta + C \int_{\beta}^\infty e^{-\frac{t}{4 b}} \, \sd t \overset{\beta = 4b \log C}{=} 4b \left( \log C + 1 \right) \, . \end{align}
Putting (i) and (ii) together we obtain \begin{align} \E [ Z ] \leq 2 \nu \left( \frac{\sqrt{\pi}}{2} + \sqrt{\log C} \right) + 4b \left(1 + \log C \right) \, , \end{align} which is slightly tighter than the required bound.
(b)
Since the MGF of the mean of independent zero-mean Bernstein random variables satisfies \begin{align} \E \left[ e^{\frac{\lambda}{n} \sum_{i=1}^n X_i} \right] \leq \exp \left\lbrace - n \, \frac{\frac{\lambda^2}{n^2}\sigma^2 / 2}{1 - b\frac{|\lambda|}{n}} \right\rbrace \leq \exp \left\lbrace - \frac{\lambda^2 \frac{\sigma^2}{n} / 2}{1 - \frac{b}{n}|\lambda|} \right\rbrace \, , \end{align} the result follows by the two-sided bound from Proposition 2.10 and (a).
Notes
- In (a) part (i), we could use an alternative Mills ratio type bound (see Exercise 2.2) for the integral \(\int_{\alpha}^\infty e^{- \frac{t^2}{4 \nu^2}} \, \sd t\) \begin{align} \P \left(\e \geq \frac{\alpha}{\sqrt{2 \nu^2}}\right) \leq \frac{\sqrt{2 \nu^2}}{\alpha} e^{-\frac{\alpha^2}{4 \nu^2}} \, , \end{align} \(\e \sim \gauss (0, 1)\), which with the same choice for \(\alpha = 2 \nu \sqrt{\log C}\) and rearrangement yields \begin{align} \int_{0}^\infty 1 \wedge \bigl( C e^{-\frac{t^2}{4 \nu^2}} \bigr) \, \sd t \leq \frac{2 \nu}{\sqrt{\log C}} \left( \frac{1}{2} + \log C \right) \, . \end{align} This is tighter than the bound in part (i) when \(\log C \geq 1\) and looser otherwise.