Concentration inequalities

Idea: How far can the mean be off

Concentration inequalities bound large deviations from a little knowledge. The more you know, the stronger the bound.

• Only a mean: Markov
• A variance: Chebyshev
• A range and independence: Hoeffding

Formula: Markov

$P(X\ge a)\le \frac{E[X]}{a}$

For a variable that is never negative, the mean alone bounds the upper tail.

Quick check: A drawdown from its mean

A drawdown has mean $4$ points. What bound does Markov give on the chance it reaches $20$?

Formula: Chebyshev for a sample mean

$P(|\bar{X}-\mu \mid \ge ϵ)\le \frac{{\sigma }^2}{n{ϵ}^2}$

Markov applied to the squared gap: the variance bounds both tails, falling as 1/n.

Example: How many days to believe it

Daily results have variance $25$. How many days keep the mean within $1$ point with failure chance at most $5\%$?

1. Chebyshev: the failure chance is at most $\frac{25}{n}$
2. Need $\frac{25}{n}$ no more than $0.05$
3. So $n=\frac{25}{1\times 0.05}=500$; round up if not whole

Formula: Hoeffding

$P(|\bar{X}-\mu \mid \ge ϵ)\le 2\exp \left(-\frac{2n{ϵ}^2}{w^2}\right)$

Independent draws in a range of width w: the tail falls exponentially in n.

Idea: Which bound wins

A hit rate: $w=1$, variance at most $\frac{1}{4}$, and $ϵ=0.05$.

• $n=240$: Hoeffding $\approx 0.6$, Chebyshev $\frac{5}{12}$ is better
• $n=2000$: Hoeffding $\approx 0.00009$, Chebyshev only $\frac{1}{20}$
• The exponential bound wins deep in the tail, where risk lives

Quick check: Size the sample

Draws lie in a range of width $10$. How many give a Hoeffding exponent of $3$ at $ϵ=1$?

Common mistake: Hoeffding on the wrong data

Fat-tailed daily returns make $w$ a guess, and overlapping windows make $n$ overstate the information.

Instead Check independence and a true range first; otherwise the bound looks rigorous and guarantees nothing.

Idea: A bound is not a forecast

A bound is a guarantee and often loose: at $n=240$ a normal model gives about $0.12$, not $\frac{5}{12}$.

• Testing $100$ strategies multiplies the bound by $100$
• An exponential tail absorbs that; a $\frac{1}{n}$ tail mostly cannot
• Say what you know, solve for n, then check the conditions