Introduction to High-Dimensional Statistics, 2nd Edition

Appendix B

Probabilistic Inequalities

B.1 Basic Inequalities

Markov inequality plays a central role in the control of the fluctuations of random variables.

Lemma B.1 Markov inequality

For any non-decreasing positive function φ : ℝ → ℝ⁺ and any real-valued random variable X, we have

$\mathbb{P}\left(X\ge t\right)\le \frac{1}{\phi \left(t\right)}\mathbb{E}\left[\phi \left(X\right)\right]forallt\in ℝ.$

In particular, for any λ > 0, we have

$\mathbb{P}\left(X\ge t\right)\le e^{-\lambda t}\mathbb{E}\left[e^{\lambda X}\right]forallt\in ℝ.$

Proof. Since φ is positive and non-decreasing, we have

$\mathbb{P}\left(X\ge t\right)\le \mathbb{E}\left[\frac{\phi \left(X\right)}{\phi \left(t\right)}{1}_{X\ge t}\right]\le \frac{1}{\phi \left(t\right)}\mathbb{E}\left[\phi \left(X\right)\right].$

A consequence of Markov inequality is the Chernoff bound on the deviation of X from its expectation.

Lemma B.2 Chernoff bound

Let X be a real random variable, with finite expectation. ...