= Hoeffding confidence interval
{c}
{title2=$r_n=\sqrt{\log(2/\delta)/(2n)}$}
For a fixed positive <sample size> $n$ of <independent and identically distributed> <Bernoulli random variables>, let
$$
r_n=\sqrt{\frac{\log(2/\delta)}{2n}},\qquad C_n=[\max\{0,\widehat p_n-r_n\},\min\{1,\widehat p_n+r_n\}].
$$
The <Hoeffding inequality> makes $C_n$ a conservative <confidence interval> for $p$: $\mathbb P_p(p\in C_n)\geq1-\delta$ for every $p\in[0,1]$. Indeed, exclusion from the closed <interval> implies $|\widehat p_n-p|>r_n$, an <event> contained in the deviation <event> bounded by $\delta$. Clipping to $[0,1]$ retains coverage because $p$ already lies there. For $n=738$, $\delta=0.05$, and an observed frequency $369/738=1/2$, $r_n\approx0.0499924$, giving approximately $[0.450008,0.549992]$.
Coverage concerns repeated <independent> samples: the unknown $p$ is fixed and the <confidence interval> is random. This fixed-$n$ guarantee does not justify repeatedly checking the same bound and stopping as soon as it looks favorable. The <Hoeffding sample size for Bernoulli frequencies> chooses $n$ in advance; guarantees across repeated inspection times require separate control of the additional <events>, for example through a <union bound> with an allocated failure <probability> at each time.
Back to article page
