Introduction

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.

Try It

Each run below flips nn 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.

<!-- Controls: coin-flip simulation parameters -->
<div class="controls">
  <label>Flips per trial (n): <strong id="nVal">50</strong>
    <input type="range" id="nSlider" min="10" max="500" step="10" value="50">
  </label>
  <label>Deviation ε: <strong id="epsVal">0.10</strong>
    <input type="range" id="epsSlider" min="1" max="30" step="1" value="10">
  </label>
  <label>Number of 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>Empirical tail</span>
  <span class="leg-item"><span class="swatch markov"></span>Markov bound</span>
  <span class="leg-item"><span class="swatch chebyshev"></span>Chebyshev bound</span>
  <span class="leg-item"><span class="swatch hoeffding"></span>Hoeffding bound</span>
</div>
<div id="stats" class="stats"></div>
<button id="runBtn" type="button">Run simulation</button>

/* Layout and color palette for the concentration demo */
* { 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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Concentration inequalities demo: simulate coin flips and compare
// theoretical tail bounds (Markov, Chebyshev, Hoeffding) to empirical results

const nSlider = document.getElementById('nSlider');
const epsSlider = document.getElementById('epsSlider');
const trialsSlider = document.getElementById('trialsSlider');
const nVal = document.getElementById('nVal');
const epsVal = document.getElementById('epsVal');
const trialsVal = document.getElementById('trialsVal');
const statsEl = document.getElementById('stats');
const canvas = document.getElementById('chart');
const ctx = canvas.getContext('2d');

// Update displayed values when sliders change
function updateLabels() {
  nVal.textContent = nSlider.value;
  epsVal.textContent = (epsSlider.value / 100).toFixed(2);
  trialsVal.textContent = trialsSlider.value;
}
nSlider.addEventListener('input', updateLabels);
epsSlider.addEventListener('input', updateLabels);
trialsSlider.addEventListener('input', updateLabels);

// Markov's inequality: Pr[X >= mu + eps] <= mu / (mu + eps) for non-negative X
function markovBound(eps) {
  // For fraction of heads with mu=0.5, bound on upper tail only
  return Math.min(1, 0.5 / (0.5 + eps));
}

// Chebyshev: Pr[|X - mu| >= eps] <= Var(X) / eps^2
function chebyshevBound(n, eps) {
  // Variance of average of n Bernoulli(0.5) = 0.25/n
  const sigma2 = 0.25 / n;
  return Math.min(1, sigma2 / (eps * eps));
}

// Hoeffding: two-sided tail, variables in [0,1], sum of ranges^2 = n
function hoeffdingBound(n, eps) {
  // Two-sided: 2 * exp(-2 * n * eps^2)
  return 2 * Math.exp(-2 * n * eps * eps);
}

// Run trials coin-flip experiments, return fraction of heads each time
function simulate(n, trials) {
  const fracs = [];
  for (let t = 0; t < trials; t++) {
    let heads = 0;
    for (let i = 0; i < n; i++) heads += Math.random() < 0.5 ? 1 : 0;
    fracs.push(heads / n);
  }
  return fracs;
}

// Bin fractions into a histogram with given number of bins
function buildHistogram(fracs, bins) {
  const counts = new Array(bins).fill(0);
  for (const f of fracs) {
    const b = Math.min(bins - 1, Math.floor(f * bins));
    counts[b]++;
  }
  return counts;
}

function run() {
  const n = parseInt(nSlider.value);
  const eps = parseInt(epsSlider.value) / 100;
  const trials = parseInt(trialsSlider.value);

  const fracs = simulate(n, trials);
  const BINS = 50;
  const counts = buildHistogram(fracs, BINS);
  const maxCount = Math.max(...counts);

  // Draw the histogram and bounds on the canvas
  const W = canvas.width;
  const H = canvas.height;
  const PAD = { top: 10, right: 10, bottom: 28, left: 36 };
  const cw = W - PAD.left - PAD.right;
  const ch = H - PAD.top - PAD.bottom;

  ctx.clearRect(0, 0, W, H);

  // Shade the central region [0.5-eps, 0.5+eps] in green
  const lo = Math.max(0, 0.5 - eps);
  const hi = Math.min(1, 0.5 + eps);
  const xLo = PAD.left + lo * cw;
  const xHi = PAD.left + hi * cw;
  ctx.fillStyle = 'rgba(58,170,106,0.12)';
  ctx.fillRect(xLo, PAD.top, xHi - xLo, ch);

  // Draw histogram bars
  const barW = cw / BINS;
  for (let b = 0; b < BINS; b++) {
    const h = (counts[b] / maxCount) * ch;
    const x = PAD.left + b * barW;
    const y = PAD.top + ch - h;
    ctx.fillStyle = '#4a90d9';
    ctx.fillRect(x + 1, y, barW - 2, h);
  }

  // Compute and draw the three theoretical bounds as horizontal lines
  const mBound = markovBound(eps);
  const cBound = chebyshevBound(n, eps);
  const hBound = hoeffdingBound(n, eps);

  function drawHLine(prob, color, label) {
    // Draw a horizontal dashed line at a given tail-probability level
    const yp = PAD.top + ch * (1 - Math.min(prob, 1));
    ctx.strokeStyle = color;
    ctx.lineWidth = 2;
    ctx.setLineDash([5, 3]);
    ctx.beginPath();
    ctx.moveTo(PAD.left, yp);
    ctx.lineTo(PAD.left + cw, yp);
    ctx.stroke();
    ctx.setLineDash([]);
    ctx.fillStyle = color;
    ctx.font = '11px system-ui';
    ctx.fillText(label, PAD.left + cw - 4, yp - 3);
  }

  // Draw axes
  ctx.strokeStyle = '#bbb';
  ctx.lineWidth = 1;
  ctx.beginPath();
  ctx.moveTo(PAD.left, PAD.top);
  ctx.lineTo(PAD.left, PAD.top + ch);
  ctx.lineTo(PAD.left + cw, PAD.top + ch);
  ctx.stroke();

  // x-axis labels: fraction of heads from 0 to 1
  ctx.fillStyle = '#666';
  ctx.font = '10px system-ui';
  for (let v = 0; v <= 1; v += 0.25) {
    const x = PAD.left + v * cw;
    ctx.fillText(v.toFixed(2), x - 8, PAD.top + ch + 16);
  }

  // y-axis labels: probability density (relative)
  for (let p = 0; p <= 1; p += 0.25) {
    const y = PAD.top + ch * (1 - p);
    ctx.fillStyle = '#999';
    ctx.font = '9px system-ui';
    ctx.textAlign = 'right';
    ctx.fillText(p.toFixed(2), PAD.left - 3, y + 3);
  }
  ctx.textAlign = 'left';

  drawHLine(mBound, '#e8a838', 'M');
  drawHLine(cBound, '#d05c5c', 'C');
  drawHLine(hBound, '#3aaa6a', 'H');

  // Count how many trials fell outside the epsilon band
  const outside = fracs.filter(f => Math.abs(f - 0.5) > eps).length;
  const empTail = outside / trials;

  statsEl.innerHTML =
    fmt('<b>n=%n%, &epsilon;=%eps%, trials=%trials%</b><br>Empirical outside: <b>%v%%</b> &nbsp;|&nbsp; Markov: <b>%v2%%</b> &nbsp;|&nbsp; Chebyshev: <b>%v3%%</b> &nbsp;|&nbsp; Hoeffding: <b>%v4%%</b>', { n: n, eps: eps.toFixed(2), trials: trials, v: (empTail * 100).toFixed(1), v2: (mBound * 100).toFixed(1), v3: (cBound * 100).toFixed(1), v4: (hBound * 100).toFixed(1) });

  console.log('Simulation results:', { n, eps, trials, empTail: empTail.toFixed(4), markov: mBound.toFixed(4), chebyshev: cBound.toFixed(4), hoeffding: hBound.toFixed(4) });
}

document.getElementById('runBtn').addEventListener('click', run);
run();
Result
Console

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

The Real Bounds

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

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

Pr⁡[X≥t]≤μt\Pr[X \ge t] \le \frac{\mu}{t}

Needs only that X≥0X \ge 0. Tells you the average can't be large if XX 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≈55%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 σ2\sigma^2:

Pr⁡[∣X−μ∣≥kσ]≤1k2\Pr[|X - \mu| \ge k\sigma] \le \frac{1}{k^2}

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

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

Pr⁡ ⁣[Snn≥μ+ε]≤e−2nε2\Pr\!\left[\frac{S_n}{n} \ge \mu + \varepsilon\right] \le e^{-2n\varepsilon^2}

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

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

Pr⁡ ⁣[Xˉn−μ≥ε]≤exp⁡ ⁣(−2n2ε2∑i(bi−ai)2)\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−δ1 - \delta, you need roughly n=O ⁣(log⁡(1/δ)ε2)n = O\!\left(\frac{\log(1/\delta)}{\varepsilon^2}\right) samples — a consequence of Hoeffding's bound.

Where It Matters

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 nn 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 nn voters estimates the true preference within ±1/n\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/δ)/ε2)O(\log(1/\delta)/\varepsilon^2) samples suffice," that's concentration at work.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/concentration-inequalities/Content licensed under CC BY-NC 4.0.