Interactive demo · Nonparametric Statistical Inference · Chapter 1

Tail inequalities against exact tails

Each inequality of Section 1.4 bounds the probability that an average strays from its mean, using less and less information: Markov uses the mean, Chebyshev the variance, Hoeffding only the range, Bernstein the range and the variance. Here the data are n Bernoulli(p) trials, so the exact probability P(|X̄n − p| ≥ ε) is a Binomial sum and every bound can be compared with the truth on a log scale. The lower panel does the same for Mill's inequalities and the Normal tail.

Sample size n

Success probability p

Deviation ε

Normal threshold t

Try these

Bounds above 1 are shown as 1. Bernstein (1.29) uses M = max(p, 1−p) and v = np(1−p); its moment version (1.30) uses the same constants, which satisfy its moment condition. Markov is applied to |X̄n − p|, whose mean is computed exactly.

In the lecture notes