Concentration Inequalities: From Markov and Chebyshev to Chernoff Bounds

Why asymptotic limit theorems aren't enough for randomized algorithms: deriving Markov, Chebyshev, and exponential Chernoff tail bounds.

Beyond Asymptotic Convergence

Let $X_1, X_2, \dots, X_n$ be independent and identically distributed (i.i.d.) random variables with finite mean $\mu = \mathbb{E}[X_i]$. The Weak Law of Large Numbers (WLLN) guarantees that the sample mean $\bar{X}n = \frac{1}{n}\sum{i=1}^n X_i$ converges in probability to $\mu$:

$$\forall \varepsilon > 0, \qquad \lim_{n \to \infty} \mathbb{P}!\left(|\bar{X}_n - \mu| \ge \varepsilon\right) = 0.$$

In theoretical computer science—whether we are analyzing Randomized QuickSort, universal hashing, load balancing, or Monte Carlo error amplification—asymptotic convergence as $n \to \infty$ is not enough. An algorithm executes a finite number of steps $n$, and we need an explicit, non-asymptotic upper bound on the tail probability $\mathbb{P}(|\bar{X}_n - \mu| \ge t)$.

Concentration inequalities provide these finite-sample guarantees. They form a strict hierarchy: the higher the moments we control, the faster the tail probability decays.


1. Markov’s Inequality (First Moment)

Suppose all we know about a random variable $X$ is that it is non-negative ($X \ge 0$) and has finite expectation $\mathbb{E}[X]$.

Theorem (Markov’s Inequality)

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

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

Proof. Let $\mathbb{I}{{X \ge a}}$ be the indicator variable equal to $1$ if $X \ge a$ and $0$ otherwise. Because $X \ge 0$, the deterministic inequality $a \cdot \mathbb{I}{{X \ge a}} \le X$ holds at every point of the sample space. Taking expectations on both sides yields:

$$a \cdot \mathbb{E}!\left[\mathbb{I}_{{X \ge a}}\right] = a \cdot \mathbb{P}(X \ge a) \le \mathbb{E}[X]. \quad \square$$

Algorithmic Application: Las Vegas to Monte Carlo

A Las Vegas randomized algorithm always returns the correct answer, but its running time $T$ is a random variable with expected value $\mathbb{E}[T] = \mu$. By Markov’s inequality, stopping the algorithm if it has not finished after $2\mu$ steps aborts with probability at most $\mathbb{P}(T \ge 2\mu) \le 1/2$. Repeating $k$ independent runs of length $2\mu$ reduces the failure probability from $1/2$ to $2^{-k}$ while bounding worst-case runtime by $2k\mu$.


2. Chebyshev’s Inequality (Second Moment)

Markov’s inequality decays only as $O(1/a)$ and yields no improvement when applied directly to a sum $S_n = \sum_{i=1}^n X_i$, because $\mathbb{E}[S_n]$ and the threshold $n a$ both scale linearly with $n$. To capture cancellation between fluctuations above and below the mean, we move to the second central moment: the variance $\sigma^2 = \text{Var}(X) = \mathbb{E}[(X - \mu)^2]$.

Theorem (Chebyshev’s Inequality)

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

$$\mathbb{P}(|X - \mu| \ge t) \le \frac{\text{Var}(X)}{t^2}.$$

Proof. Since $|X - \mu| \ge t \iff (X - \mu)^2 \ge t^2$ and $(X - \mu)^2 \ge 0$, applying Markov’s inequality to the non-negative variable $Y = (X - \mu)^2$ with threshold $a = t^2$ gives:

$$\mathbb{P}(|X - \mu| \ge t) = \mathbb{P}!\left((X - \mu)^2 \ge t^2\right) \le \frac{\mathbb{E}[(X - \mu)^2]}{t^2} = \frac{\text{Var}(X)}{t^2}. \quad \square$$

Pairwise Independence and the Weak Law of Large Numbers

If $X_1, \dots, X_n$ are pairwise independent with mean $\mu$ and variance $\sigma^2$, their covariance terms vanish: $\text{Var}(\bar{X}n) = \frac{1}{n^2}\sum{i=1}^n \text{Var}(X_i) = \frac{\sigma^2}{n}$. Chebyshev’s inequality then gives:

$$\mathbb{P}(|\bar{X}_n - \mu| \ge \varepsilon) \le \frac{\sigma^2}{n\varepsilon^2}.$$

This immediately proves the Weak Law of Large Numbers and shows that pairwise independence alone guarantees $O(1/n)$ polynomial tail decay—a fact heavily exploited in derandomization and 2-universal hash families where full mutual independence is too costly to construct.


3. Chernoff Bounds (Exponential Moments)

When $X_1, \dots, X_n$ are mutually independent and bounded, $O(1/n)$ polynomial decay is still vastly pessimistic. Because full independence implies that the expectation of a product equals the product of expectations, we can apply Markov’s inequality to the Moment Generating Function (MGF) $\mathbb{E}[e^{\lambda S_n}]$—a technique due to Sergei Bernstein and Herman Chernoff.

For any parameter $\lambda > 0$, since $x \mapsto e^{\lambda x}$ is strictly increasing:

$$\mathbb{P}(S_n \ge a) = \mathbb{P}!\left(e^{\lambda S_n} \ge e^{\lambda a}\right) \le e^{-\lambda a},\mathbb{E}!\left[\prod_{i=1}^n e^{\lambda X_i}\right] = e^{-\lambda a}\prod_{i=1}^n \mathbb{E}!\left[e^{\lambda X_i}\right].$$

Theorem (Multiplicative Chernoff Bounds for Poisson Trials)

Let $X_1, \dots, X_n$ be mutually independent Bernoulli trials with $\mathbb{P}(X_i = 1) = p_i$ and $\mathbb{P}(X_i = 0) = 1 - p_i$. Let $S_n = \sum_{i=1}^n X_i$ and $\mu = \mathbb{E}[S_n] = \sum_{i=1}^n p_i$. For any $\delta \in (0, 1)$:

$$\mathbb{P}!\left(S_n \ge (1 + \delta)\mu\right) \le \left(\frac{e^\delta}{(1+\delta)^{1+\delta}}\right)^\mu \le \exp!\left(-\frac{\delta^2 \mu}{3}\right),$$

$$\mathbb{P}!\left(S_n \le (1 - \delta)\mu\right) \le \left(\frac{e^{-\delta}}{(1-\delta)^{1-\delta}}\right)^\mu \le \exp!\left(-\frac{\delta^2 \mu}{2}\right).$$

Proof (Upper Tail). For each Bernoulli variable $X_i$, using the inequality $1 + x \le e^x$:

$$\mathbb{E}!\left[e^{\lambda X_i}\right] = (1 - p_i) + p_i e^\lambda = 1 + p_i(e^\lambda - 1) \le \exp!\left(p_i(e^\lambda - 1)\right).$$

Multiplying across all $n$ independent variables gives $\mathbb{E}[e^{\lambda S_n}] \le \exp(\mu(e^\lambda - 1))$. Substituting $a = (1+\delta)\mu$ into the exponential Markov bound yields:

$$\mathbb{P}!\left(S_n \ge (1+\delta)\mu\right) \le \exp!\left(\mu(e^\lambda - 1) - \lambda(1+\delta)\mu\right).$$

To minimize the exponent with respect to $\lambda > 0$, we differentiate $\mu(e^\lambda - 1 - \lambda(1+\delta))$ and set the derivative to zero, obtaining the optimal tilting parameter $\lambda^* = \ln(1 + \delta) > 0$. Substituting $\lambda^* = \ln(1 + \delta)$ gives:

$$\mathbb{P}!\left(S_n \ge (1+\delta)\mu\right) \le \left(\frac{e^\delta}{(1+\delta)^{1+\delta}}\right)^\mu.$$

Finally, the elementary Taylor bound $\delta - (1+\delta)\ln(1+\delta) \le -\frac{\delta^2}{2 + 2\delta/3} \le -\frac{\delta^2}{3}$ for $\delta \in (0, 1)$ yields $\exp(-\delta^2\mu / 3)$. $\square$


Quantitative Comparison

Consider $n = 1000$ independent fair coin flips ($\mu = 500$, $\sigma^2 = 250$), and suppose we want to bound the probability of observing at least $750$ heads ($\delta = 0.5$):

InequalityMoments UsedIndependence NeededUpper Bound on $\mathbb{P}(S_{1000} \ge 750)$
Markov$\mathbb{E}[S_n]$None$\le \frac{500}{750} \approx 0.6667$
Chebyshev$\mathbb{E}[S_n], \text{Var}(S_n)$Pairwise ($2$-wise)$\le \frac{250}{250^2} = 0.0040$
Chernoff$\mathbb{E}[e^{\lambda S_n}]$Mutual ($n$-wise)$\le e^{-500(0.25)/3} \approx 7.89 \times 10^{-19}$

Moving from second moments to exponential moments tightens the bound by sixteen orders of magnitude—turning a weak constant probability into certainty at algorithmic scale.