← SciSim / Statistics
Concentration Inequalities
Tier: Graduate
§1 Interactive Simulation — Markov, Chebyshev, Chernoff Bounds
Distribution
Exponential
Mean mu
1.0
Markov bound
Chebyshev bound
True P(X>t)
t query
Distribution
t (query value) 2
n (for LLN) 50
§2 The Idea, Step by Step

From a gut feeling to an exact promise

Suppose your class's average test score is 70. Could half the class have scored above 140? Of course not — if too many people scored extremely high, the average would be dragged up past 70. So just knowing the average already forbids "too many" extreme values. Concentration inequalities turn that gut feeling into precise, guaranteed limits on how rare a big deviation from the average must be.

START — JUST THE AVERAGE (Markov)

Give the average a name: the mean $\mu$. Markov's inequality says that for a quantity that is never negative, the chance it lands at or above a level $t$ is at most $\mu/t$. A worked number: if the average wait at a clinic is $\mu=10$ minutes, then the chance any one patient waits $\ge 50$ minutes is at most $10/50 = 0.20$ — no more than 1 in 5, no matter how the waiting times are distributed. We used only the mean, so the bound is deliberately loose.

BUILD — ADD THE SPREAD (Chebyshev)

If we also know the spread — the variance $\sigma^2$, or the standard deviation $\sigma$ — we can do much better. Chebyshev's inequality says values rarely stray many standard deviations from the mean: $P(|X-\mu|\ge k\sigma)\le 1/k^2$. Landing 3 standard deviations away happens at most $1/9\approx 11\%$ of the time, again for any distribution with that variance.

DEEPEN — THE FULL TAIL (Chernoff & the LLN)

The sharpest classical bound uses the entire moment-generating function $M_X(\lambda)=E[e^{\lambda X}]$. The Chernoff bound, $P(X\ge t)\le \min_{\lambda>0} e^{-\lambda t}M_X(\lambda)$, decays exponentially in $t$ rather than polynomially — which is why it, and its bounded-variable cousin Hoeffding, power learning-theory guarantees. Averaging helps too: for the sample mean of $n$ values, $\operatorname{Var}(\bar X_n)=\sigma^2/n$, so Chebyshev gives $P(|\bar X_n-\mu|\ge\varepsilon)\le \sigma^2/(n\varepsilon^2)\to 0$ — a clean proof of the Weak Law of Large Numbers. In the sim, the t slider sets the deviation you ask about and n sets the sample size for the LLN view.

TRY THIS IN THE SIM ABOVE

(1) On "Bound Comparison," slide $t$ large and watch the true-probability curve plunge far below the Markov and Chebyshev lines — the bounds are guarantees, not estimates. (2) Switch to "LLN via Chebyshev" and raise $n$; see the bound fall like $1/n$. (3) Change the distribution between Exponential, Normal, and Bernoulli — the same bounds still hold, because they assume almost nothing about the distribution's shape.

§3 Mathematical Derivation

Concentration Inequalities — Universal Probability Bounds

Markov: $P(X\ge t)\le E[X]/t$ (for $X\ge0$)

Chebyshev: $P(|X-\mu|\ge k\sigma)\le 1/k^2$

$$\boxed{\textbf{Chernoff:}\quad P(X\ge t)\le\min_\lambda\frac{M_X(\lambda)}{e^{\lambda t}}=\frac{E[e^{\lambda X}]}{e^{\lambda t}}}$$

InequalityAssumptionBoundQuality
MarkovX≥0, finite meanE[X]/tLoose — only uses mean
ChebyshevFinite mean and varianceσ²/(t-μ)²Better — uses variance
ChernoffFinite MGFinf_λ M(λ)e^(-λt)Tight — exponential decay
HoeffdingBounded range [a,b]exp(-2n²ε²/Σ(bi-ai)²)Tight for bounded vars
APPLICATION: LLN BOUND

By Chebyshev: $P(|\bar X_n-\mu|\ge\varepsilon)\le\frac{\sigma^2}{n\varepsilon^2}\to0$. This proves the Weak LLN with explicit convergence rate $O(1/n)$. The bound is simple but loose — true convergence is often exponentially fast.

CHERNOFF VS CHEBYSHEV

For Exponential(1): Chebyshev gives $P(X>3)\le \sigma^2/(3-1)^2=0.25$. The optimal Chernoff bound is $te^{1-t}=3e^{-2}\approx0.406$, while the true value is $e^{-3}\approx0.050$. At this moderate $t$ Chebyshev is actually the tighter of the two; what makes Chernoff valuable is its exponential decay rate — for large $t$ it eventually overtakes every polynomial (variance-based) bound, which is exactly why Chernoff and Hoeffding bounds underpin machine-learning generalization guarantees.

Vershynin — High-Dimensional Probability, Cambridge UP
Mitzenmacher & Upfal — Probability and Computing, Cambridge UP
§4 FAQ
§5 Key Points
Key Insight

Concentration inequalities are distribution-free bounds — no distributional assumption needed beyond moments.
Markov only needs E[X]. Chebyshev needs E[X] and Var(X). Chernoff needs the MGF. These are worst-case bounds: they hold for ALL distributions satisfying the assumption. The trade-off: looser bounds are more general; tighter bounds require stronger assumptions.
📖 Vershynin — High-Dimensional Probability

Vershynin — High-Dimensional Probability, Cambridge UP
Mitzenmacher & Upfal — Probability and Computing