Chernoff Bounds

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.

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]$.

<!-- {{c_html_intro}} -->
<div class="controls">
  <label>
    <span class="lbl">{{lbl_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">{{lbl_delta}}</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">{{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">{{hint_para}}</div>
<button id="runBtn" type="button">{{btn_run}}</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; }

// Code not found

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.

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.

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.

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.