High-Dimensional Statistics | Solution to Exercise 2.3

Exercise 2.3 (Polynomial Markov versus Chernoff)

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

$$inf⁡k=1,2,…E[∣X∣k]δk≤inf⁡λ>0E[eλX]eλδ \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⁡kE[∣X∣k]δkc = \inf_{k} \frac{\mathrm{E}[|X|^k]}{\delta^k}$. Then $c≤E[∣X∣k]δkc \leq \frac{\mathrm{E}[|X|^k]}{\delta^k}$ for all $kk$.

Since $λ>0\lambda >0$, we have

$$cλkδkk!≤λkE[∣X∣k]k!. c\frac{\lambda^k \delta^k}{k!} \leq \frac{\lambda^k \mathrm{E}[|X|^k]}{k!}.$$

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

$$c∑k=1∞λkδkk!≤∑k=1∞λkE[∣X∣k]k!.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≤E[eλX]eλδ.c \leq \frac{\mathrm{E}[e^{\lambda X}]}{e^{\lambda \delta}}.$$

Taking the infimum of $kk$ and $λ>0\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.