Concentration Inequalities

Flip a fair coin a thousand times. The fraction of heads will hover near 0.5. It might reach 0.55, but it almost certainly won't hit 0.7. Why not? The coins are random — why does the average behave so predictably?

This is the central question of concentration inequalities: given many independent random numbers, how likely is their average to deviate from the expected value by more than some amount $\varepsilon$?

The answer is a family of tail bounds — mathematical guarantees that the probability of a large deviation is tiny, and that it shrinks fast as the sample grows. Each bound in the hierarchy is stronger than the last: Markov's inequality needs only a positive mean; Chebyshev's needs a variance; Chernoff's and Hoeffding's exploit the structure of bounded variables to give exponentially small tail probabilities.

These bounds underpin randomized algorithms, machine learning generalization theory, and much of modern statistics. Understanding them means understanding why averages are trustworthy.

Each run below flips $n$ fair coins and records the fraction of heads. Repeat this many times to build a histogram of outcomes. The colored lines show the theoretical tail bounds: how often the fraction should fall outside the shaded region around 0.5.

<!-- {{c_html_intro}} -->
<div class="controls">
  <label>{{label_n}} <strong id="nVal">50</strong>
    <input type="range" id="nSlider" min="10" max="500" step="10" value="50">
  </label>
  <label>{{label_eps}} <strong id="epsVal">0.10</strong>
    <input type="range" id="epsSlider" min="1" max="30" step="1" value="10">
  </label>
  <label>{{label_trials}} <strong id="trialsVal">500</strong>
    <input type="range" id="trialsSlider" min="100" max="2000" step="100" value="500">
  </label>
</div>
<canvas id="chart" width="540" height="240"></canvas>
<div class="legend">
  <span class="leg-item"><span class="swatch empirical"></span>{{legend_empirical}}</span>
  <span class="leg-item"><span class="swatch markov"></span>{{legend_markov}}</span>
  <span class="leg-item"><span class="swatch chebyshev"></span>{{legend_chebyshev}}</span>
  <span class="leg-item"><span class="swatch hoeffding"></span>{{legend_hoeffding}}</span>
</div>
<div id="stats" class="stats"></div>
<button id="runBtn" type="button">{{btn_run}}</button>

/* {{c_css_layout}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.controls { display: flex; flex-direction: column; gap: .45rem; margin-bottom: .7rem; }
label { font-size: .85rem; display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; }
input[type=range] { flex: 1; min-width: 120px; max-width: 260px; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 8px; background: #f7fafc; width: 100%; max-width: 540px; }
.legend { display: flex; flex-wrap: wrap; gap: .5rem 1rem; margin: .5rem 0 .3rem; font-size: .8rem; }
.leg-item { display: flex; align-items: center; gap: .35rem; }
.swatch { width: 18px; height: 4px; border-radius: 2px; display: inline-block; }
.swatch.empirical { background: #4a90d9; }
.swatch.markov { background: #e8a838; }
.swatch.chebyshev { background: #d05c5c; }
.swatch.hoeffding { background: #3aaa6a; }
.stats { font-size: .82rem; color: #444; min-height: 2.5em; margin-bottom: .4rem; line-height: 1.5; }
button { font: 600 14px system-ui; padding: .45rem 1rem; background: #1d3557; color: #fff; border: none; border-radius: 8px; cursor: pointer; }
button:hover { background: #274e7a; }

// Code not found

Notice: as you increase $n$, the histogram narrows and the Hoeffding bound (the tightest) tells you exactly how much tighter. Doubling $n$ roughly halves the standard deviation — but the Chernoff/Hoeffding tail shrinks exponentially in $n$, which is much better than the $1/n$ story Chebyshev tells.

The hierarchy runs from weakest (fewest assumptions) to strongest (tightest tails):

Markov's inequality (Andrey Markov, ~1890) — For a non-negative random variable $X$ with mean $\mu$:

$$\Pr[X \ge t] \le \frac{\mu}{t}$$

Needs only that $X \ge 0$. Tells you the average can't be large if $X$ rarely is large — but the bound is loose. Ask "how often does the fraction of heads exceed 0.9?" and Markov says at most $0.5/0.9 \approx 55\%$. The truth for 1000 coins is essentially zero.

Chebyshev's inequality (Pafnuty Chebyshev, 1867) — For any random variable with mean $\mu$ and variance $\sigma^2$:

$$\Pr[|X - \mu| \ge k\sigma] \le \frac{1}{k^2}$$

Uses variance. Guarantees at least 75% of the mass within $2\sigma$, 89% within $3\sigma$ — universally, no matter the distribution. The tail decays as $1/k^2$: polynomial, not great.

Chernoff bounds (Herman Chernoff, 1952) — For sums of independent 0/1 random variables:

$$\Pr\!\left[\frac{S_n}{n} \ge \mu + \varepsilon\right] \le e^{-2n\varepsilon^2}$$

(one of several forms). The tail decays exponentially in $n$. This is why a thousand coin flips almost never lands above 0.55 — the probability is $e^{-2 \cdot 1000 \cdot 0.0025} \approx e^{-5} \approx 0.007$.

Hoeffding's inequality (Wassily Hoeffding, 1963) — Generalizes Chernoff to any bounded variables $X_i \in [a_i, b_i]$:

$$\Pr\!\left[\bar{X}_n - \mu \ge \varepsilon\right] \le \exp\!\left(\frac{-2n^2\varepsilon^2}{\sum_i (b_i - a_i)^2}\right)$$

Same exponential flavor, but works for any bounded (not just Bernoulli) random variables. It is the workhorse of PAC learning: to guarantee a machine-learning algorithm is $\varepsilon$-accurate with probability $1 - \delta$, you need roughly $n = O\!\left(\frac{\log(1/\delta)}{\varepsilon^2}\right)$ samples — a consequence of Hoeffding's bound.

Concentration inequalities are the backbone of any field that must trust a random sample to speak for a whole population:

• Machine learning generalization: Hoeffding (or its relatives like McDiarmid's inequality) gives the canonical proof that a finite training sample generalizes — with $n$ examples you can be $\delta$-confident your error is within $\varepsilon$ of the true risk. This is the core of PAC learning.
• Randomized algorithms: algorithms that flip coins to make decisions (e.g., randomized quicksort, Monte Carlo methods) need tail bounds to guarantee their running time or output quality with high probability.
• Streaming and sketches: algorithms that approximate frequency, distinct elements, or heavy hitters over a stream use Chernoff bounds to size their data structures — small enough to fit in memory, yet accurate enough to be useful.
• Statistics and polling: a poll of $n$ voters estimates the true preference within $\pm 1/\sqrt{n}$ with high probability. This square-root law is a consequence of Chebyshev (or the stronger Hoeffding bound).
• Cryptography and security: many security proofs reduce to "a certain random variable is almost certainly near its mean." Without concentration, the reductions wouldn't close.

Every time you see "$O(\log(1/\delta)/\varepsilon^2)$ samples suffice," that's concentration at work.

The four inequalities form a ladder of power. Markov needs only positivity. Chebyshev adds variance and gives polynomial decay. Chernoff and Hoeffding exploit independence and boundedness to give exponential decay — the reason a thousand coin flips almost never lands far from 0.5, and the reason machine learning algorithms need surprisingly few examples to generalize.

The deep message is that independence amplifies predictability. Each extra independent sample tightens the tail bound exponentially. This is the mathematical reason averages are trustworthy: not because individual outcomes are predictable, but because their combination is.

Concentration inequalities are solved classical mathematics, but their applications keep expanding — into differential privacy, federated learning, and high-dimensional geometry. The next time you trust a sample mean, you are implicitly trusting Markov, Chebyshev, Chernoff, and Hoeffding.