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.
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.
code/ch04_inequalities.py (tail_bounds, binom_tail, chernoff_bound, mills_bound, moment_bound; Figures 4.S1 and 4.S3).