High-Dimensional Statistics | Solution to Exercise 2.3

Exercise 2.3 (Polynomial Markov versus Chernoff)

Suppose that $X \geq 0$, and that the moment generating function of $X$ exists in an interval around zero. Given some $\delta > 0$ and integer $k = 1, 2 \dots$, show that

$$\inf_{k=1, 2, \dots} \frac{\mathrm{E}[|X|^k]}{\delta^k} \leq \inf_{\lambda > 0}\frac{\mathrm{E}[e^{\lambda X}]}{e^{\lambda \delta}}$$

Consequently, an optimized bound based on polynomial moments is always at least as good as Chernoff upper bound.

Solution

Let $c = \inf_{k} \frac{\mathrm{E}[|X|^k]}{\delta^k}$. Then $c \leq \frac{\mathrm{E}[|X|^k]}{\delta^k}$ for all $k$.

Since $\lambda >0$, we have

$$c\frac{\lambda^k \delta^k}{k!} \leq \frac{\lambda^k \mathrm{E}[|X|^k]}{k!}.$$

By the assumption, the moment generating function of $X$ exists, therefore,

$$c\sum_{k=1}^\infty \frac{\lambda^k \delta^k}{k!} \leq \sum_{k=1}^\infty \frac{\lambda^k \mathrm{E}[|X|^k]}{k!}.$$

Using the Taylor expansion of an exponential function, we have

$$c \leq \frac{\mathrm{E}[e^{\lambda X}]}{e^{\lambda \delta}}.$$

Taking the infimum of $k$ and $\lambda > 0$ finishes the proof.

Reference

Wainwright, Martin. High-dimensional statistics : a non-asymptotic viewpoint. Cambridge, United Kingdom New York, NY, USA: Cambridge University Press, 2019.

Philips, Thomas & Nelson, Randolph. (1995). The Moment Bound Is Tighter Than Chernoff's Bound for Positive Tail Probabilities. The American Statistician. 49. 175. 10.2307/2684633.