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.


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.


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.