= Hoeffding sample size for Bernoulli frequencies
{c}
{title2=$n\geq\lceil\log(2/\delta)/(2\varepsilon^2)\rceil$}
Let $B_1,\ldots,B_n$ be <independent and identically distributed> <Bernoulli random variables> with success <probability> $p$, and let $\widehat p_n=n^{-1}\sum_iB_i$ be their observed frequency, a <sample mean>. Since every <interval> width is one, $V=n$. Substituting $t=n\varepsilon$ into the <Hoeffding inequality> gives
$$
\mathbb P(\widehat p_n-p\geq\varepsilon)\leq e^{-2n\varepsilon^2},\qquad \mathbb P(|\widehat p_n-p|\geq\varepsilon)\leq\min\{1,2e^{-2n\varepsilon^2}\}.
$$
For tolerance $0<\varepsilon<1$ and failure <probability> $0<\delta<1$, solving $2e^{-2n\varepsilon^2}\leq\delta$ yields the sufficient <sample size>
$$
\boxed{n\geq\left\lceil\frac{\log(2/\delta)}{2\varepsilon^2}\right\rceil.}
$$
Here $\log$ is the <natural logarithm>. For $\varepsilon=0.05$ and $\delta=0.05$, \b[$n=738$ guarantees an error smaller than $0.05$ with <probability> at least $0.95$], for every $p\in[0,1]$. The two-sided bound at this <sample size> is approximately $0.0499440$. A specified single direction instead needs $n\geq\lceil\log(1/\delta)/(2\varepsilon^2)\rceil$, or $600$ for these choices. Halving the tolerance multiplies the unrounded sufficient <sample size> by four; reducing the failure <probability> tenfold adds $\log(10)/(2\varepsilon^2)$ before rounding.
This is a conservative sufficient <sample size>, not a necessary minimum. For a specified $p$, the count $K=\sum_iB_i$ has a <binomial distribution>, whose exact upper <tail probability> is
$$
\mathbb P(K\geq k)=\sum_{j=k}^n\binom njp^j(1-p)^{n-j},\qquad k\in\{0,\ldots,n\}.
$$
For $k>np$, the <Hoeffding inequality> bounds this by $\exp[-2(k-np)^2/n]$. An arbitrary frequency threshold uses $k=\lceil n(p+\varepsilon)\rceil$; if $k>n$, the <event> is impossible. The discreteness of the count and its <variance> $np(1-p)$ can make the exact <tail probability> substantially smaller. At $n=100$, $p=1/2$, $k=60$, the exact upper <tail probability> is about $0.0284440$, while the bound is $e^{-2}\approx0.135335$. At $p=1/10$, $k=20$, the same deviation $\varepsilon=0.1$ gives the same bound but an exact upper <tail probability> about $0.00197856$.
\Image[/hoeffding-binomial-tail-comparison.png]
{title=Exact <binomial distribution> tails compared with the <Hoeffding inequality>}
{description=Two original specified models, each with $n=100$ <independent> <Bernoulli trials>. Each dot includes its integer threshold $K\geq k$, with horizontal coordinate $\varepsilon=k/n-p$. Exact finite sums are evaluated with rational arithmetic before conversion for plotting. The <Hoeffding inequality> uses the width one in both panels; it does not use the smaller <variance> at $p=1/10$. These are model probabilities, not measured frequencies.}
Back to article page
