basic inequalities

Some basic probabilistic inequalities. Used mostly under the hood to build more sophisticated concentration inequalities, but also useful in other scenarios.

Markov’s inequality

For a nonnegative random variable $X$ and parameter $a>0$, Markov’s inequality states that

$$\mathbb{P}(X\ge a)\le \frac{\mathbb{E}[X]}{a}.$$

Clearly the condition that $X\ge 0$ is necessary: consider any random variable which has negative mean but some positive mass.

The proof of Markov’s is easy:

$$\mathbb{E}X={\int }_0^{\infty }xdP\ge {\int }_a^{\infty }xdP\ge a{\int }_a^{\infty }dP=a\mathbb{P}(X\ge a).$$

Markov’s inequality is tight in the sense that there are distributions for which the inequality holds with equality. But it is not very interesting in the sense that it doesn’t provide interesting concentration behavior. However, it’s a cornerstone in more sophisticated concentration techniques, which often rely on applying Markov’s inequality to the random variable

$$\exp \left(\lambda \sum _{i\le n}{X}_i\right).$$

(See the Chernoff method below, which is precisely this strategy.)

You can strengthen Markov by writing

$$\mathbb{P}(X\ge a)\le \frac{\mathbb{E}[X1\{X\ge t\}]}{a},$$

for any (not necessarily nonnegative) random variable $X$. To prove this just apply expectations to the inequality $1\{x\ge t\}\le \frac{x}{t}1\{x\ge t\}$ which holds for all $x$ and all $t\ge 0$.

Some notes and pointers:

• For achievability and optimality see optimality of Markov and Chebyshev.
• Markov’s inequality can also be derived using convex optimization arguments (concentration via convex optimization).
• Ville’s inequality is a time-uniform extension of Markov’s inequality for nonnegative supermartingales (or reverse submartingales, as the case may be). Just as Markov’s inequality is used as a foundation for concentration inequalities, Ville’s inequality is used as a foundation for time-uniform concentration inequalities.
• There is also a randomized Markov’s inequality (randomized inequalities:Markov) which uses external randomization.
• An intuitive explanation of Markov’s inequality is the optimization perspective on Markov’s inequality.

Chebyshev’s inequality

Chebyshev’s inequality is simply Markov’s inequality applied to $(X-\mu {)}^2$. For $a>0$,

$$\mathbb{P}(X-\mu \ge a)\le \mathbb{P}(|X-\mu |\ge a)=\mathbb{P}(|X-\mu {|}^2\ge a^2)\le \frac{\mathbb{V}(X)}{a^2}.$$

Chebyshev’s inequality gives the first flavor of concentration. If $X_1,X_2,\dots ,X_n$ are iid with mean $\mu$, then Chebyshev gives

$$\mathbb{P}(|{\overline{X}}_n-\mu |\ge a)\le \frac{\mathbb{V}(\overline{X_n})}{a^2}=\frac{\mathbb{V}(X)}{n{a}^2},$$

where ${\overline{X}}_n=n^{-1}{\sum }_i{X}_i$. Making the RHS equal to $\delta$ gives with probability $1-\delta$,

$$|{\overline{X}}_n-\mu |\le \sqrt{\mathbb{V}(X)/(\delta n)}.$$

The rate of concentration here is actually not too bad, it scales with $\sqrt{n}$ which is what we expect in many scenarios. However, the dependence on $1/\sqrt{\delta }$ is not great. We’d rather have $\log (1/\delta )$, which is an exponential improvement over $1/\sqrt{\delta }$. The Chernoff method gives us this sort of dependence.

Note that the strict iid assumption is not necessary for the above bounds. If we have $\mathbb{V}(X_i)\le v^2$ for all $i$ and $\text{Cov}(X_i,X_j)\le 0$ (uncorrelated or reverse-correlated) for all $i\ne j$, then $\mathbb{V}({\overline{X}}_n)\le {\sigma }^2/n$ so the same discussion applies after swapping $\mathbb{V}({\overline{X}}_n)$ with $v^2$. See negative correlation can improve concentration for more.

Notes:

• Chebyshev’s inequality is a specific instance of the method of moments for concentration.
• The time-uniform extension of Chebyshev’s inequality is the Dubins-Savage inequality.
• For achievability and optimality see optimality of Markov and Chebyshev.

Cantelli’s inequality

Cantelli’s inequality is a one-sided improvement to Chebyshev’s inequality. For any random variable $X$ with mean $\mu$ and variance ${\sigma }^2$, for any $t\ge 0$, write

$$\mathbb{P}(X-\mu \ge a)\le \mathbb{P}((X-\mu +t{)}^2\ge (t+a{)}^2),$$

so by Chebyshev,

$$\mathbb{P}(X-\mu \ge a)\le \underset{t\ge 0}{\inf }\frac{{\sigma }^2+t^2}{(t+a{)}^2}=\frac{{\sigma }^2}{{\sigma }^2+a^2}.$$

which is Cantelli’s inequality. This was proved using concentration via convex optimization.

Chernoff method

The Chernoff method applies Markov’s inequality to the nonnegative random variable $e^{\lambda X}$, and then chooses $\lambda$ to optimize the bound. More detail is given in Chernoff method (also called the Cramer-Chernoff method).