Interactive demo · Probability and Statistical Inference · Chapter 4

Markov, Chebyshev, Hoeffding and the exact tail

Each inequality of Chapter 4 bounds a tail probability using only a little information: Markov's uses the mean, Chebyshev's the variance, Hoeffding's the range of the observations, and Chernoff's the whole moment generating function. Here the bounds are set against the exact tail of a sample proportion X̄n of n Bernoulli(p) trials, computed from the binomial distribution, and against the exact tail of a standard normal (Exercise 6). The vertical axes are logarithmic: a bound that is off by a factor of 1000 is three grid lines away.

Random variable

Tail

Sample size n

Success probability p

Deviation ε

Threshold t

Moment used by Markov k

Try these

Exact tails are sums of binomial probabilities: two-sided P(|X̄n − p| > ε) and upper P(X̄n − p ≥ ε). Chebyshev: p(1−p)/(nε2), or its one-sided (Cantelli) form σ2/(σ2+ε2) with σ2 = p(1−p)/n. Hoeffding: e−2nε² per tail. Chernoff: e−n kl(p±ε, p) per tail. Markov, for the upper tail only: p/(p+ε). Bounds above 1 are shown at 1.

In the lecture notes