Advanced28 min

Probability Inequalities

Markov, Chebyshev, Jensen, Cauchy–Schwarz and Hoeffding bounds, and where each is used in ML theory.

Assumes you know

Variance, Moments and Generating Functions

Probability Inequalities

Intuition first

Often you cannot compute a probability exactly — the distribution is unknown, or the integral is intractable — but you can bound it. Inequalities give guarantees using only partial information such as the mean, or the mean and variance.

The trade-off is universality against tightness. Markov's inequality needs only the mean and holds for every non-negative variable, so it must accommodate the worst case and is usually loose. Chebyshev adds the variance and does better. Hoeffding assumes bounded variables and gives exponentially tight bounds — which is why it, not the others, underpins generalisation theory in machine learning.

These are the tools behind every statement of the form "with probability at least $1 - \delta$ , the error is at most $\epsilon$ ".

Markov's inequality

For a non-negative random variable $X$ and any $a > 0$ :

\Prob(X \geq a) \leq \frac{\E[X]}{a}

Proof by indicatorAdvanced

Define the indicator $\mathbb{1}[X \geq a]$ . The key observation is the pointwise inequality

X \;\geq\; a\,\mathbb{1}[X \geq a]

Check both cases. If $X \geq a$ the right side is $a$ and indeed $X \geq a$ . If $X < a$ the right side is 0 and $X \geq 0$ by assumption — which is exactly where non-negativity is needed.

Take expectations of both sides, using monotonicity of expectation:

\E[X] \;\geq\; a\,\E\big[\mathbb{1}[X \geq a]\big] = a\,\Prob(X \geq a)

Divide by $a > 0$ . Note how little was assumed: only $X \geq 0$ and a finite mean. That generality is why the bound is weak.

Chebyshev's inequality

For any random variable with finite mean $\mu$ and variance $\sigma^2$ , and any $k > 0$ :

\Prob\big(\lvert X - \mu \rvert \geq k\sigma\big) \leq \frac{1}{k^2}

Chebyshev from MarkovAdvanced

Apply Markov to the non-negative variable $Y = (X - \mu)^2$ with threshold $a = k^2\sigma^2$ :

\Prob\big((X-\mu)^2 \geq k^2\sigma^2\big) \leq \frac{\E[(X-\mu)^2]}{k^2\sigma^2} = \frac{\sigma^2}{k^2\sigma^2} = \frac{1}{k^2}

The event $(X-\mu)^2 \geq k^2\sigma^2$ is identical to $\lvert X - \mu \rvert \geq k\sigma$ , since squaring is monotone on non-negative values. Done.

The gain over Markov comes from squaring: it converts a one-sided statement about a non-negative variable into a two-sided statement about deviations, and the $1/k^2$ decay is faster than Markov's $1/k$ .

$k$	Chebyshev bound	Actual, if normal
1	$\leq 100\%$ (vacuous)	31.7%
2	$\leq 25\%$	4.6%
3	$\leq 11.1\%$	0.27%
4	$\leq 6.25\%$	0.006%

Solved problem 1 · Comparing the three bounds

Exam scores have mean 70 and standard deviation 10. Bound $\Prob(X \geq 100)$ using Markov, then Chebyshev, then compare with the normal answer.

Step 1 — Markov, using only the mean

Scores are non-negative, so Markov applies with $a = 100$ :

\Prob(X \geq 100) \leq \frac{70}{100} = 0.70

Step 2 — Chebyshev, using mean and variance

$100$ is $k$ standard deviations above the mean where

k = \frac{100 - 70}{10} = 3

Chebyshev bounds the two-sided event:

\Prob\big(\lvert X - 70\rvert \geq 30\big) \leq \frac{1}{9} \approx 0.1111

We want only the upper tail. Without a symmetry assumption we cannot simply halve, so the guaranteed bound is

\Prob(X \geq 100) \leq 0.1111

Step 3 — normal assumption, for comparison

If $X \sim \mathcal{N}(70, 100)$ :

\Prob(X \geq 100) = \Prob(Z \geq 3) \approx 0.00135

Step 4 — compare

\text{Markov}: 0.70 \qquad \text{Chebyshev}: 0.111 \qquad \text{Normal}: 0.00135

Markov is 500 times too large, Chebyshev 82 times too large. Each additional piece of information — first the variance, then the full shape — tightens the bound by roughly two orders of magnitude.

Answer

Markov $\leq 0.70$ ; Chebyshev $\leq 0.111$ ; normal gives $0.00135$ . The bounds are correct but weak, which is the price of assuming almost nothing.

Jensen's inequality

For a convex function $g$ :

\E[g(X)] \geq g\big(\E[X]\big)

with the inequality reversed for concave $g$ , and equality only when $X$ is constant or $g$ is linear.

Proof via the supporting lineAdvanced

Convexity means the graph of $g$ lies above every tangent line. At the point $\mu = \E[X]$ there is a supporting line with some slope $c$ :

g(x) \;\geq\; g(\mu) + c\,(x - \mu) \qquad \text{for all } x

Take expectations of both sides:

\E[g(X)] \;\geq\; g(\mu) + c\,\big(\E[X] - \mu\big) = g(\mu) + c \cdot 0 = g(\mu)

The linear term vanishes precisely because we expanded about the mean.

Two instances used repeatedly in this curriculum: $g(x) = x^2$ gives $\E[X^2] \geq (\E[X])^2$ , which is variance non-negativity; and $g(x) = -\log x$ gives $\E[-\log X] \geq -\log \E[X]$ , which is the step that produces the ELBO in variational inference.

Hoeffding's inequality

For independent $X_1, \dots, X_n$ with $X_i \in [a_i, b_i]$ , and $\bar{X}$ their mean:

\Prob\big(\lvert \bar{X} - \E[\bar{X}] \rvert \geq t\big) \;\leq\; 2\exp\left(-\frac{2n^2t^2}{\sum_i (b_i - a_i)^2}\right)

For the common case $X_i \in [0,1]$ this simplifies to

\Prob\big(\lvert \bar{X} - \mu \rvert \geq t\big) \;\leq\; 2e^{-2nt^2}

Solved problem 2 · Sample size from Hoeffding

You estimate a classifier's accuracy on $n$ held-out examples. How large must $n$ be so that the estimate is within $0.02$ of the true accuracy with probability at least $0.99$ ?

Step 1 — set up

Each example contributes a $0/1$ correctness indicator, so $X_i \in [0,1]$ and Hoeffding applies in its simplified form. We need

2e^{-2nt^2} \leq \delta \qquad \text{with } t = 0.02, \; \delta = 0.01

Step 2 — solve for n

e^{-2nt^2} \leq \frac{\delta}{2} \quad\Longrightarrow\quad -2nt^2 \leq \ln\frac{\delta}{2} \quad\Longrightarrow\quad n \geq \frac{\ln(2/\delta)}{2t^2}

Step 3 — substitute

\ln\frac{2}{0.01} = \ln 200 \approx 5.2983

2t^2 = 2(0.02)^2 = 2 \times 0.0004 = 0.0008

n \geq \frac{5.2983}{0.0008} = 6622.9 \quad\Longrightarrow\quad n \geq 6623

Step 4 — compare with Chebyshev

Chebyshev needs $\Var(\bar X) = \sigma^2/n$ with $\sigma^2 \leq 0.25$ for a $[0,1]$ variable:

\Prob(\lvert \bar X - \mu\rvert \geq t) \leq \frac{\sigma^2}{nt^2} \leq \frac{0.25}{n(0.0004)}

Setting this to $0.01$ :

n \geq \frac{0.25}{0.01 \times 0.0004} = \frac{0.25}{4\times10^{-6}} = 62{,}500

Nearly ten times more data for the same guarantee.

Step 5 — and the normal approximation

Assuming normality, $t = z\sigma/\sqrt{n}$ with $z = 2.576$ for 99% and $\sigma \leq 0.5$ :

n \geq \left(\frac{2.576 \times 0.5}{0.02}\right)^2 = (64.4)^2 \approx 4148

Answer

Hoeffding requires $n \geq 6{,}623$ ; Chebyshev $62{,}500$ ; the normal approximation $4{,}148$ .

Hoeffding is only 60% more conservative than the normal approximation while requiring no distributional assumption at all — which is why it is the tool of choice for guarantees.

Summary

Inequality	Needs	Bound	Tightness
Markov	$X \geq 0$ , mean	$\E[X]/a$	Very loose
Chebyshev	Mean, variance	$1/k^2$	Loose
Jensen	Convexity	Directional	Exact tool, not a tail bound
Hoeffding	Independence, bounded	$2e^{-2nt^2}$	Tight
Chernoff	Independence, MGF exists	Exponential	Tightest

python

import numpy as np
from scipy import stats

mu, sigma = 70, 10

print(f"Markov     P(X>=100) <= {mu/100:.5f}")
print(f"Chebyshev  P(X>=100) <= {1/3**2:.5f}")
print(f"Normal     P(X>=100)  = {stats.norm.sf(100, mu, sigma):.5f}")

# Sample size for |X̄ - μ| <= 0.02 with 99% confidence.
t, delta = 0.02, 0.01
n_hoeff = np.ceil(np.log(2/delta) / (2 * t**2))
n_cheb = np.ceil(0.25 / (delta * t**2))
n_norm = np.ceil((stats.norm.ppf(1 - delta/2) * 0.5 / t) ** 2)
print(f"\nn needed — Hoeffding {n_hoeff:.0f}  Chebyshev {n_cheb:.0f}  normal {n_norm:.0f}")

# Check Hoeffding empirically at n = 6623.
rng = np.random.default_rng(0)
n = int(n_hoeff)
means = rng.binomial(1, 0.85, size=(20_000, n)).mean(axis=1)
violations = np.mean(np.abs(means - 0.85) >= t)
print(f"observed violation rate {violations:.5f}  <= bound {2*np.exp(-2*n*t**2):.5f}")

Exercise 1

A non-negative variable has mean 5. Bound $\Prob(X \geq 20)$ . Then, told additionally that $\sigma = 2$ , improve it.

Show solution

Markov:

\Prob(X \geq 20) \leq \frac{5}{20} = 0.25

Chebyshev. The threshold is $k$ standard deviations above the mean with

k = \frac{20 - 5}{2} = 7.5

\Prob\big(\lvert X - 5\rvert \geq 15\big) \leq \frac{1}{7.5^2} = \frac{1}{56.25} \approx 0.01778

Adding the variance tightened the bound from $0.25$ to $0.0178$ — a fourteen-fold improvement, for one extra number.

Exercise 2

Use Jensen's inequality to show that the arithmetic mean is at least the geometric mean for positive numbers.

Show solution

Let $X$ take the values $x_1, \dots, x_n > 0$ each with probability $1/n$ . Apply Jensen to the concave function $g(x) = \log x$ , which reverses the inequality:

\E[\log X] \;\leq\; \log \E[X]

The left side is

\E[\log X] = \frac{1}{n}\sum_{i=1}^n \log x_i = \log\left(\prod_{i=1}^n x_i\right)^{1/n}

the log of the geometric mean. The right side is $\log$ of the arithmetic mean. Since $\log$ is strictly increasing, the inequality passes through:

\left(\prod_{i=1}^n x_i\right)^{1/n} \;\leq\; \frac{1}{n}\sum_{i=1}^n x_i

which is AM–GM. Equality holds exactly when $X$ is constant, that is when all $x_i$ are equal — matching the equality condition in Jensen.

This is why the geometric mean is the right average for multiplicative quantities such as growth rates: the arithmetic mean of returns systematically overstates the compounded result.

Next: Laws of Large Numbers, which Chebyshev proves in three lines.