From n Bernoulli(p) trials with proportion p̂, Hoeffding's inequality gives the interval p̂ ± εn with εn = √(log(2/α)/(2n)), which contains p with probability at least 1 − α for every n and every p. The usual normal-approximation (Wald) interval p̂ ± zα/2√(p̂(1−p̂)/n) is shorter, but its coverage is only approximately 1 − α, and it can be far lower when n is small or p is near 0 or 1. Simulate intervals, then compare the exact coverage and the expected length of both for every n.
Both intervals are truncated to [0, 1], which does not change whether they contain p. Exact coverage and expected length are sums over the Binomial(n, p) distribution; the curves use n = 1, ..., 100 and then 100 values equally spaced on the log scale up to 10,000. Simulated data sets are seeded, so the same settings always give the same intervals.
code/ch04_inequalities.py (hoeffding_eps, coverage_exact, expected_length, coverage_sim, sample_size_for_length).