Hoeffding's Inequality

You backtest a signal on 500 trading days and get a 55% hit rate. Is that real edge, or could a coin-flip strategy print 55% out of 500 flips just by luck? Chebyshev's inequality gives a bound, but it's loose — it doesn't use the fact that a hit/miss outcome is bounded between 0 and 1. Hoeffding's inequality uses exactly that boundedness, and the bound it produces shrinks exponentially fast as you collect more data, not just polynomially.

The analogy: a jar of marked coins

Picture a jar with an unknown fraction $p$ of red marbles. You draw $n$ marbles with replacement and compute the fraction that are red. Common sense says this sample fraction should land close to $p$ once $n$ is large — that's the Law of Large Numbers. Hoeffding's inequality is the sharpened version of that common sense: it tells you, for any fixed sample size $n$, exactly how small the probability is that your sample fraction lands more than some given distance from $p$. And critically, that probability shrinks faster and faster — like a bell curve's tail, not like a slowly decaying power — because each marble draw contributes only a small, bounded amount of randomness.

Writing it down

Let $X_1, \ldots, X_n$ be independent random variables, each confined to an interval $[a_i, b_i]$ (bounded — this is the whole trick). Let $\bar{X} = \frac{1}{n}\sum X_i$ be their average and $\mu = E[\bar{X}]$ its true mean. Hoeffding's inequality says: for any $t > 0$,

$$P(|\bar{X} - \mu| \ge t) \le 2\exp\left(-\frac{2n^2t^2}{\sum_{i=1}^n (b_i - a_i)^2}\right).$$

In words: the chance the sample average is off from the true average by more than $t$ decays exponentially in $n$ and in $t^2$, and it decays faster the tighter the bounds $[a_i, b_i]$ are. Wider possible values per draw (a bigger $b_i - a_i$) weaken the bound; more draws or a bigger tolerance $t$ strengthen it, and strengthen it fast.

For the common special case of i.i.d. variables in $[0,1]$ (like win/loss indicators), this simplifies to

$$P(|\bar{X} - \mu| \ge t) \le 2e^{-2nt^2}.$$

Set the decay rate high and watch how quickly the curve collapses toward zero — that collapse rate is exactly what $-2nt^2$ buys you as $n$ grows: doubling $n$ doesn't just halve the bound, it squares how small it gets.

Worked example 1: is 55% out of 500 real?

A signal fires 500 times, hits 275 (55%). Suppose the truth is actually $p = 0.5$ (no edge). What's the chance of seeing a sample average at least 5 percentage points away from 0.5 by luck alone? Here $n = 500$, $t = 0.05$, each observation in $[0,1]$:

$$P(|\bar{X} - 0.5| \ge 0.05) \le 2e^{-2(500)(0.05)^2} = 2e^{-2.5} \approx 2(0.082) = 0.164.$$

So there's up to a 16.4% chance a fair coin produces a result this extreme purely by chance over 500 trials — not negligible. This single backtest is not strong evidence of edge. Compare with 5,000 trials at the same 5% gap: $2e^{-2(5000)(0.05)^2} = 2e^{-25} \approx 3 \times 10^{-11}$ — essentially impossible by luck. The exponential in $n$ is doing real work: 10x the sample size didn't just tighten the bound tenfold, it crushed it by ten orders of magnitude.

Watch the running average settle inside its shrinking envelope as more points are added — Hoeffding's bound is the hard, non-asymptotic version of exactly that shrinking band, giving you a concrete probability at every fixed $n$ rather than just a "it converges eventually" promise.

Worked example 2: how many trades to trust a 2% edge?

You want to be 99% confident your measured average return is within $t = 0.02$ (2 percentage points) of the true mean, and each trade's return, after clipping, sits in $[-1, 1]$ (so $b_i - a_i = 2$). Solve $2e^{-2n(0.02)^2/4} \le 0.01$ for $n$:

$$e^{-0.0002n} \le 0.005 \;\Longrightarrow\; -0.0002n \le \ln(0.005) \approx -5.30 \;\Longrightarrow\; n \ge 26{,}500.$$

You need roughly 26,500 trades before Hoeffding will certify that kind of precision — a sobering number for anyone eyeballing a 200-trade backtest and calling an edge "confirmed."

What this means in practice

• Backtest sample size. Before trusting a hit rate or average return, plug your $n$ and desired precision into Hoeffding's bound. It tells you honestly whether your sample size can even support the claim you want to make.
• A/B testing execution algorithms. Comparing two execution strategies' fill quality (a bounded quantity, like slippage in ticks) is a textbook Hoeffding setting — no need to assume normality.
• Model-free. Unlike a t-test, Hoeffding needs no assumption about the shape of the distribution — only that the values are bounded. That's valuable when returns are skewed or fat-tailed.