Introduction to Chernoff Bounds

Introduction

Flip a fair coin 1000 times. You expect 500 heads. Will you get exactly 500? Almost certainly not. Will you get fewer than 400? Almost certainly not either — and Chernoff bounds tell you precisely how unlikely that is.

A Chernoff bound is a concentration inequality: it says that the sum of many independent, bounded random variables stays very close to its mean, with a tail probability that shrinks exponentially in the gap. Not polynomially, not slowly — exponentially fast.

That exponential shrinkage is the reason randomized algorithms can make probabilistic guarantees. If an algorithm succeeds with probability $1 - 2^{-n}$ , running it once is essentially as good as a deterministic proof. Chernoff bounds are proved with the moment-generating function trick: multiply the Markov inequality by $e^{t X}$ for a free parameter $t$ , optimize $t$ , and watch the tail collapse. The result was published by Herman Chernoff in 1952 and has been sharpened many times since, with a closely related form due to Wassily Hoeffding (1963) covering arbitrary bounded variables.

Try It

Each trial flips $n$ fair coins and records the fraction of heads. Adjust $n$ (the number of flips) and $\delta$ (the allowed deviation from $\tfrac{1}{2}$ ), then click Run trials to see how often the fraction of heads falls outside $[\tfrac{1}{2}-\delta,\, \tfrac{1}{2}+\delta]$ .

<!-- Chernoff / Hoeffding concentration demo: flip n fair coins, count how often the fraction of heads deviates from 0.5 by more than delta. -->
<div class="controls">
  <label>
    <span class="lbl">Flips (n)</span>
    <input type="range" id="nSlider" min="10" max="500" value="50" step="10">
    <span id="nVal">50</span>
  </label>
  <label>
    <span class="lbl">Deviation (δ %)</span>
    <input type="range" id="dSlider" min="1" max="30" value="10" step="1">
    <span id="dVal">0.10</span>
  </label>
  <label>
    <span class="lbl">Trials</span>
    <input type="range" id="tSlider" min="100" max="2000" value="500" step="100">
    <span id="tVal">500</span>
  </label>
</div>
<div class="hint">Each trial flips n fair coins and checks whether the fraction of heads is outside [0.5 − δ, 0.5 + δ]. The red dashed line is the Hoeffding upper bound 2·exp(−2nδ²); the blue line is the measured frequency.</div>
<button id="runBtn" type="button">Run trials</button>
<div id="canvas-wrap"><canvas id="chart" width="480" height="200"></canvas></div>
<div class="results" id="results"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; }
.controls { display: flex; flex-direction: column; gap: .4rem; margin-bottom: .5rem; }
label { display: flex; align-items: center; gap: .4rem; font-size: .88rem; }
.lbl { width: 9rem; flex-shrink: 0; font-weight: 600; }
input[type=range] { flex: 1; }
.hint { font-size: .85rem; color: #555; margin: .4rem 0; line-height: 1.45; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; margin-bottom: .5rem; }
#canvas-wrap { overflow-x: auto; }
canvas { display: block; max-width: 100%; border: 1px solid #dde3e9; border-radius: 6px; background: #f9fbfd; }
.results { font-size: .9rem; margin-top: .5rem; line-height: 1.6; }
.results strong { color: #1d3557; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Chernoff/Hoeffding demo: empirical tail frequency vs Hoeffding bound 2*exp(-2*n*delta^2).

// Read slider values.
const nSlider = document.getElementById('nSlider');
const dSlider = document.getElementById('dSlider');
const tSlider = document.getElementById('tSlider');
const nVal    = document.getElementById('nVal');
const dVal    = document.getElementById('dVal');
const tVal    = document.getElementById('tVal');

// Keep display values in sync with sliders.
function syncLabels() {
  nVal.textContent = nSlider.value;
  dVal.textContent = (parseInt(dSlider.value, 10) / 100).toFixed(2);
  tVal.textContent = tSlider.value;
}
nSlider.addEventListener('input', syncLabels);
dSlider.addEventListener('input', syncLabels);
tSlider.addEventListener('input', syncLabels);
syncLabels();

// Hoeffding bound: Pr[|mean - 0.5| > delta] <= 2*exp(-2*n*delta^2).
function hoeffdingBound(n, delta) {
  return 2 * Math.exp(-2 * n * delta * delta);
}

// Run numTrials coin-flip experiments; return fraction where |frac_heads - 0.5| > delta.
function runTrials(n, delta, numTrials) {
  let outside = 0;
  for (let t = 0; t < numTrials; t++) {
    let heads = 0;
    for (let i = 0; i < n; i++) heads += Math.random() < 0.5 ? 1 : 0;
    const frac = heads / n;
    if (Math.abs(frac - 0.5) > delta) outside++;
  }
  return outside / numTrials;
}

// Draw the chart showing bound vs empirical across a range of n values.
function drawChart(n, delta, numTrials) {
  const canvas = document.getElementById('chart');
  const ctx = canvas.getContext('2d');
  const W = canvas.width, H = canvas.height;
  const PAD = { top: 24, right: 20, bottom: 36, left: 48 };
  ctx.clearRect(0, 0, W, H);

  // Build a series of n values from 10 to nMax for the x-axis.
  const steps = 20;
  const nMax = Math.max(n * 2, 100);
  const ns = Array.from({ length: steps + 1 }, (_, i) => Math.max(10, Math.round((nMax / steps) * i)));
  const empirical = ns.map(ni => runTrials(ni, delta, Math.min(numTrials, 400)));
  const bounds    = ns.map(ni => hoeffdingBound(ni, delta));

  const innerW = W - PAD.left - PAD.right;
  const innerH = H - PAD.top  - PAD.bottom;

  // Draw x and y axes.
  ctx.strokeStyle = '#bbc5ce';
  ctx.lineWidth = 1;
  ctx.beginPath();
  ctx.moveTo(PAD.left, PAD.top);
  ctx.lineTo(PAD.left, PAD.top + innerH);
  ctx.lineTo(PAD.left + innerW, PAD.top + innerH);
  ctx.stroke();

  // Y-axis labels (probability 0..1) with horizontal grid lines.
  ctx.fillStyle = '#555';
  ctx.font = '11px system-ui, sans-serif';
  ctx.textAlign = 'right';
  for (let p = 0; p <= 100; p += 25) {
    const y = PAD.top + innerH - (p / 100) * innerH;
    ctx.fillText((p / 100).toFixed(2), PAD.left - 4, y + 4);
    ctx.strokeStyle = '#e5eaee';
    ctx.lineWidth = 0.7;
    ctx.beginPath(); ctx.moveTo(PAD.left, y); ctx.lineTo(PAD.left + innerW, y); ctx.stroke();
  }

  // X-axis labels: show selected n values.
  ctx.textAlign = 'center';
  ctx.fillStyle = '#555';
  [0, 0.5, 1].forEach(frac => {
    const ni = ns[Math.round(frac * steps)];
    const x  = PAD.left + frac * innerW;
    ctx.fillText(String(ni), x, PAD.top + innerH + 16);
  });

  const xOf = (i) => PAD.left + (i / steps) * innerW;
  const yOf = (v) => PAD.top  + innerH - Math.min(v, 1) * innerH;

  // Plot the Hoeffding bound curve (dashed red).
  ctx.strokeStyle = '#e63946';
  ctx.lineWidth = 2;
  ctx.setLineDash([4, 3]);
  ctx.beginPath();
  bounds.forEach((b, i) => { i === 0 ? ctx.moveTo(xOf(i), yOf(b)) : ctx.lineTo(xOf(i), yOf(b)); });
  ctx.stroke();
  ctx.setLineDash([]);

  // Plot the empirical tail frequency curve (solid blue).
  ctx.strokeStyle = '#1d6fc4';
  ctx.lineWidth = 2;
  ctx.beginPath();
  empirical.forEach((e, i) => { i === 0 ? ctx.moveTo(xOf(i), yOf(e)) : ctx.lineTo(xOf(i), yOf(e)); });
  ctx.stroke();

  // Legend labels.
  ctx.font = '11px system-ui, sans-serif';
  ctx.fillStyle = '#e63946'; ctx.fillRect(PAD.left + 4, PAD.top + 4, 16, 3);
  ctx.fillStyle = '#333'; ctx.textAlign = 'left'; ctx.fillText('Hoeffding bound', PAD.left + 24, PAD.top + 8);
  ctx.fillStyle = '#1d6fc4'; ctx.fillRect(PAD.left + 4, PAD.top + 18, 16, 3);
  ctx.fillStyle = '#333'; ctx.fillText('Empirical frequency', PAD.left + 24, PAD.top + 22);

  // X-axis label.
  ctx.fillStyle = '#555'; ctx.textAlign = 'center';
  ctx.fillText('n', PAD.left + innerW / 2, H - 4);
}

// Run everything and update the results text.
function run() {
  const n        = parseInt(nSlider.value, 10);
  const delta    = parseInt(dSlider.value, 10) / 100;
  const numTrials = parseInt(tSlider.value, 10);

  const empRate  = runTrials(n, delta, numTrials);
  const bound    = hoeffdingBound(n, delta);

  drawChart(n, delta, numTrials);

  const pct = (empRate * 100).toFixed(1);
  const bpct = (bound * 100).toFixed(1);
  document.getElementById('results').innerHTML =
    i18nFmt('For <strong>n = %n%</strong>, δ = %delta%: empirical tail = <strong>%emp%%</strong> of %trials% trials &nbsp;|&nbsp; Hoeffding bound = <strong>%bound%%</strong>.', { n: n, delta: delta.toFixed(2), trials: numTrials,
      emp: pct, bound: bpct });
}

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

<!-- Chernoff / Hoeffding concentration demo: flip n fair coins, count how often the fraction of heads deviates from 0.5 by more than delta. -->
<div class="controls">
  <label>
    <span class="lbl">Flips (n)</span>
    <input type="range" id="nSlider" min="10" max="500" value="50" step="10">
    <span id="nVal">50</span>
  </label>
  <label>
    <span class="lbl">Deviation (δ %)</span>
    <input type="range" id="dSlider" min="1" max="30" value="10" step="1">
    <span id="dVal">0.10</span>
  </label>
  <label>
    <span class="lbl">Trials</span>
    <input type="range" id="tSlider" min="100" max="2000" value="500" step="100">
    <span id="tVal">500</span>
  </label>
</div>
<div class="hint">Each trial flips n fair coins and checks whether the fraction of heads is outside [0.5 − δ, 0.5 + δ]. The red dashed line is the Hoeffding upper bound 2·exp(−2nδ²); the blue line is the measured frequency.</div>
<button id="runBtn" type="button">Run trials</button>
<div id="canvas-wrap"><canvas id="chart" width="480" height="200"></canvas></div>
<div class="results" id="results"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; }
.controls { display: flex; flex-direction: column; gap: .4rem; margin-bottom: .5rem; }
label { display: flex; align-items: center; gap: .4rem; font-size: .88rem; }
.lbl { width: 9rem; flex-shrink: 0; font-weight: 600; }
input[type=range] { flex: 1; }
.hint { font-size: .85rem; color: #555; margin: .4rem 0; line-height: 1.45; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; margin-bottom: .5rem; }
#canvas-wrap { overflow-x: auto; }
canvas { display: block; max-width: 100%; border: 1px solid #dde3e9; border-radius: 6px; background: #f9fbfd; }
.results { font-size: .9rem; margin-top: .5rem; line-height: 1.6; }
.results strong { color: #1d3557; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Chernoff/Hoeffding demo: empirical tail frequency vs Hoeffding bound 2*exp(-2*n*delta^2).

// Read slider values.
const nSlider = document.getElementById('nSlider');
const dSlider = document.getElementById('dSlider');
const tSlider = document.getElementById('tSlider');
const nVal    = document.getElementById('nVal');
const dVal    = document.getElementById('dVal');
const tVal    = document.getElementById('tVal');

// Keep display values in sync with sliders.
function syncLabels() {
  nVal.textContent = nSlider.value;
  dVal.textContent = (parseInt(dSlider.value, 10) / 100).toFixed(2);
  tVal.textContent = tSlider.value;
}
nSlider.addEventListener('input', syncLabels);
dSlider.addEventListener('input', syncLabels);
tSlider.addEventListener('input', syncLabels);
syncLabels();

// Hoeffding bound: Pr[|mean - 0.5| > delta] <= 2*exp(-2*n*delta^2).
function hoeffdingBound(n, delta) {
  return 2 * Math.exp(-2 * n * delta * delta);
}

// Run numTrials coin-flip experiments; return fraction where |frac_heads - 0.5| > delta.
function runTrials(n, delta, numTrials) {
  let outside = 0;
  for (let t = 0; t < numTrials; t++) {
    let heads = 0;
    for (let i = 0; i < n; i++) heads += Math.random() < 0.5 ? 1 : 0;
    const frac = heads / n;
    if (Math.abs(frac - 0.5) > delta) outside++;
  }
  return outside / numTrials;
}

// Draw the chart showing bound vs empirical across a range of n values.
function drawChart(n, delta, numTrials) {
  const canvas = document.getElementById('chart');
  const ctx = canvas.getContext('2d');
  const W = canvas.width, H = canvas.height;
  const PAD = { top: 24, right: 20, bottom: 36, left: 48 };
  ctx.clearRect(0, 0, W, H);

  // Build a series of n values from 10 to nMax for the x-axis.
  const steps = 20;
  const nMax = Math.max(n * 2, 100);
  const ns = Array.from({ length: steps + 1 }, (_, i) => Math.max(10, Math.round((nMax / steps) * i)));
  const empirical = ns.map(ni => runTrials(ni, delta, Math.min(numTrials, 400)));
  const bounds    = ns.map(ni => hoeffdingBound(ni, delta));

  const innerW = W - PAD.left - PAD.right;
  const innerH = H - PAD.top  - PAD.bottom;

  // Draw x and y axes.
  ctx.strokeStyle = '#bbc5ce';
  ctx.lineWidth = 1;
  ctx.beginPath();
  ctx.moveTo(PAD.left, PAD.top);
  ctx.lineTo(PAD.left, PAD.top + innerH);
  ctx.lineTo(PAD.left + innerW, PAD.top + innerH);
  ctx.stroke();

  // Y-axis labels (probability 0..1) with horizontal grid lines.
  ctx.fillStyle = '#555';
  ctx.font = '11px system-ui, sans-serif';
  ctx.textAlign = 'right';
  for (let p = 0; p <= 100; p += 25) {
    const y = PAD.top + innerH - (p / 100) * innerH;
    ctx.fillText((p / 100).toFixed(2), PAD.left - 4, y + 4);
    ctx.strokeStyle = '#e5eaee';
    ctx.lineWidth = 0.7;
    ctx.beginPath(); ctx.moveTo(PAD.left, y); ctx.lineTo(PAD.left + innerW, y); ctx.stroke();
  }

  // X-axis labels: show selected n values.
  ctx.textAlign = 'center';
  ctx.fillStyle = '#555';
  [0, 0.5, 1].forEach(frac => {
    const ni = ns[Math.round(frac * steps)];
    const x  = PAD.left + frac * innerW;
    ctx.fillText(String(ni), x, PAD.top + innerH + 16);
  });

  const xOf = (i) => PAD.left + (i / steps) * innerW;
  const yOf = (v) => PAD.top  + innerH - Math.min(v, 1) * innerH;

  // Plot the Hoeffding bound curve (dashed red).
  ctx.strokeStyle = '#e63946';
  ctx.lineWidth = 2;
  ctx.setLineDash([4, 3]);
  ctx.beginPath();
  bounds.forEach((b, i) => { i === 0 ? ctx.moveTo(xOf(i), yOf(b)) : ctx.lineTo(xOf(i), yOf(b)); });
  ctx.stroke();
  ctx.setLineDash([]);

  // Plot the empirical tail frequency curve (solid blue).
  ctx.strokeStyle = '#1d6fc4';
  ctx.lineWidth = 2;
  ctx.beginPath();
  empirical.forEach((e, i) => { i === 0 ? ctx.moveTo(xOf(i), yOf(e)) : ctx.lineTo(xOf(i), yOf(e)); });
  ctx.stroke();

  // Legend labels.
  ctx.font = '11px system-ui, sans-serif';
  ctx.fillStyle = '#e63946'; ctx.fillRect(PAD.left + 4, PAD.top + 4, 16, 3);
  ctx.fillStyle = '#333'; ctx.textAlign = 'left'; ctx.fillText('Hoeffding bound', PAD.left + 24, PAD.top + 8);
  ctx.fillStyle = '#1d6fc4'; ctx.fillRect(PAD.left + 4, PAD.top + 18, 16, 3);
  ctx.fillStyle = '#333'; ctx.fillText('Empirical frequency', PAD.left + 24, PAD.top + 22);

  // X-axis label.
  ctx.fillStyle = '#555'; ctx.textAlign = 'center';
  ctx.fillText('n', PAD.left + innerW / 2, H - 4);
}

// Run everything and update the results text.
function run() {
  const n        = parseInt(nSlider.value, 10);
  const delta    = parseInt(dSlider.value, 10) / 100;
  const numTrials = parseInt(tSlider.value, 10);

  const empRate  = runTrials(n, delta, numTrials);
  const bound    = hoeffdingBound(n, delta);

  drawChart(n, delta, numTrials);

  const pct = (empRate * 100).toFixed(1);
  const bpct = (bound * 100).toFixed(1);
  document.getElementById('results').innerHTML =
    i18nFmt('For <strong>n = %n%</strong>, δ = %delta%: empirical tail = <strong>%emp%%</strong> of %trials% trials &nbsp;|&nbsp; Hoeffding bound = <strong>%bound%%</strong>.', { n: n, delta: delta.toFixed(2), trials: numTrials,
      emp: pct, bound: bpct });
}

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

Result

Console

The Chernoff bound gives an upper bound of $2e^{-2n\delta^{2}}$ on that tail probability. Notice how the empirical frequency and the bound both collapse to zero as $n$ grows — doubling $n$ roughly squares the probability of a large deviation. That exponential decay is exactly what makes randomized algorithms reliable.

The Real Complexity

Where does the exponential come from? The key is the moment-generating function (MGF) trick.

Let $X = X_{1} + \dots + X_{n}$ where each $X_{i} \in [0,1]$ is independent with $\mathbb{E}[X_{i}] = p$ , so $\mu = np$ . For any $\delta > 0$ and any $t > 0$ :

\Pr[X \geq (1+\delta)\mu] = \Pr[e^{tX} \geq e^{t(1+\delta)\mu}] \leq \frac{\mathbb{E}[e^{tX}]}{e^{t(1+\delta)\mu}}

Because the $X_{i}$ are independent, the expectation factors:

\mathbb{E}[e^{tX}] = \prod_{i=1}^{n} \mathbb{E}[e^{tX_{i}}] \leq \left(e^{(e^{t}-1)p}\right)^{n}

Choosing $t = \ln(1+\delta)$ and simplifying gives the classic upper-tail bound:

\Pr[X \geq (1+\delta)\mu] \leq \left(\frac{e^{\delta}}{(1+\delta)^{1+\delta}}\right)^{\mu}

For $\delta \leq 1$ this is at most $e^{-\mu\delta^{2}/3}$ . The symmetric lower tail is analogous.

Hoeffding's inequality (1963) gives a cleaner form for bounded variables: if $a_{i} \leq X_{i} \leq b_{i}$ then

\Pr\!\left[\frac{X}{n} - p \geq \delta\right] \leq e^{-2n\delta^{2} / \sum_{i}(b_{i}-a_{i})^{2}}

For fair coins ( $a_{i}=0, b_{i}=1$ ) this is $e^{-2n\delta^{2}}$ , which is the formula shown in the demo. The bound is not tight — the true probability is much smaller for large $\delta$ — but it is universal: it applies to any sequence of bounded independent variables regardless of their individual distributions, making it the workhorse of algorithm analysis.

Chernoff-type bounds are closely related to the theory of randomized algorithms and large-deviation theory in probability.

Where It Matters

Chernoff bounds are not just a theoretical curiosity — they are load-bearing in dozens of algorithm families:

Load balancing: if $n$ jobs are assigned uniformly at random to $n$ machines, Chernoff bounds show that the maximum load is $O(\log n / \log\log n)$ with high probability — exponentially unlikely to be much worse.
Hashing and data structures: the number of collisions in a hash table concentrates tightly around its mean, ensuring $O(1)$ expected lookup even under adversarial inputs.
Randomized rounding: when an LP solution is rounded randomly, the Chernoff bound controls how far the integer solution strays from the fractional optimum — the backbone of many approximation algorithms.
PAC learning: in PAC learning a classifier that makes few errors on a random sample is unlikely to make many errors on unseen data — exactly because the empirical error concentrates around the true error.
Streaming algorithms: algorithms like Count-Min Sketch use independent hash functions and rely on Chernoff-type bounds to keep estimate errors small with high probability.
Network routing: a random intermediate node in Valiant's routing scheme means each edge carries roughly equal traffic; Chernoff bounds prove the overload probability is negligible.

The common thread: whenever correctness depends on a sum or average of many independent contributions staying close to its expectation, a Chernoff or Hoeffding bound is the tool that turns "probably close" into a precise, exponentially strong guarantee.

Conclusion

Chernoff bounds make a simple promise: add enough independent bounded random variables and their sum stays close to its mean — not just likely close, but exponentially close. The probability of a large deviation does not drift slowly to zero; it collapses like $e^{-cn}$ .

That exponential guarantee is what turns randomized algorithms from hopeful heuristics into rigorous guarantees. A success probability of $1 - e^{-n}$ is, for practical purposes, certainty. And it is all built from one elegant trick: the moment-generating function, a free parameter, and Markov's inequality applied once in the right way.

The next time a randomized algorithm promises something "with high probability," behind that promise almost certainly sits a Chernoff bound — one of the quietest and most powerful tools in all of algorithm design.

Comments

Loading comments...

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

Cookies & privacy

Chernoff Bounds

How sums of independent random variables stay close to their mean