Two-Point Bounds for Bernoulli Experiments

Why Bernoulli Testing Gives an Estimation Bound

Suppose \(X_1,\ldots,X_n\) are independent Bernoulli observations with unknown success probability \(p\). An estimator \(\hat p\) must use the data to distinguish among possible values of \(p\). If two probabilities are close enough that their data distributions are hard to distinguish, then an estimator cannot reliably be close to both values. This turns a testing calculation into a lower bound on estimation error.

We will use total variation to quantify distinguishability, and Kullback–Leibler divergence to control total variation for product samples. The resulting bound applies to every estimator, not just the sample proportion.

Distances Between Bernoulli Experiments

For probability distributions \(P\) and \(Q\), their total variation distance is $$ \operatorname{TV}(P,Q)=\sup_A |P(A)-Q(A)|. $$ For distributions on a finite sample space, it is also one half of the sum of the absolute differences of their probabilities at each outcome. Total variation lies between zero and one; a smaller value means that no event has very different probabilities under the two distributions.

For a single Bernoulli observation with success probabilities \(p\) and \(q\), the two outcomes are 0 and 1. The finite-space formula therefore gives an especially simple expression.

For \(0<p,q<1\), the Kullback–Leibler divergence, using natural logarithms, is $$ D\bigl(\operatorname{Bernoulli}(p)\,\|\,\operatorname{Bernoulli}(q)\bigr) =p\log\frac{p}{q}+(1-p)\log\frac{1-p}{1-q}. $$ The order matters: in general, this divergence is not symmetric in \(p\) and \(q\). For independent observations, divergence adds across the sample. In this setting that identity follows by writing the product likelihood ratio as a product and taking its expected logarithm: $$ D(P_p^n\|P_q^n) =E_p\left[\sum_{i=1}^n \log\frac{f_p(X_i)}{f_q(X_i)}\right] =nD\bigl(\operatorname{Bernoulli}(p)\,\|\,\operatorname{Bernoulli}(q)\bigr), $$ where \(P_p^n\) is the joint distribution of the \(n\) observations. The expectation of each summand is the one-observation divergence, so the equality holds for \(0<p,q<1\).

The product-sample divergence can be used with Pinsker’s inequality: for probability distributions \(P,Q\), with natural logarithms and \(D(P\|Q)<\infty\), $$ \operatorname{TV}(P,Q)\leq \sqrt{\frac{D(P\|Q)}{2}}. $$ Thus, when the one-observation divergence is of order \((p-q)^2\), the divergence for \(n\) observations is of order \(n(p-q)^2\). Choosing \(|p-q|\) of order \(1/\sqrt n\) keeps this upper bound on total variation bounded away from one.

From Testing Error to Absolute-Error Risk

Take two candidate parameters \(p_0<p_1\), write \(\Delta=p_1-p_0\), and let \(P_0\) and \(P_1\) denote their respective sample distributions. Any estimator can be converted into a test by comparing its value with the midpoint \((p_0+p_1)/2\). If that test selects the wrong parameter, the estimator must be at least \(\Delta/2\) away from the true parameter.

Proof. Define a test that chooses \(p_1\) when \(\hat p\geq(p_0+p_1)/2\), and chooses \(p_0\) otherwise. Let \(A\) be the event that this test chooses \(p_1\). Under \(p_0\), on \(A\), the absolute error is at least \(\Delta/2\). Under \(p_1\), on \(A^c\), the absolute error is greater than \(\Delta/2\), and hence at least \(\Delta/2\). Therefore $$ E_{p_0}|\hat p-p_0|+E_{p_1}|\hat p-p_1| \geq \frac{\Delta}{2}\{P_0(A)+P_1(A^c)\}. $$ The sum of testing errors satisfies $$ P_0(A)+P_1(A^c)=1-\{P_1(A)-P_0(A)\} \geq 1-\operatorname{TV}(P_0,P_1), $$ by the definition of total variation. The larger of two nonnegative risks is at least half their sum. Dividing the preceding risk bound by two proves the result. \(\square\)

This inequality is useful when the alternatives are separated enough to force a meaningful estimation error, while their sample distributions remain difficult to distinguish. For Bernoulli data, a convenient choice centers the pair at \(1/2\), where the divergence has a simple form.

A Minimax Lower Bound for Bernoulli Estimation

Choose \(p_0=1/2\) and \(p_1=1/2+\delta\), where \(\delta=1/(4\sqrt n)\). For every \(n\geq1\), these are valid parameters in \([0,1]\). By product additivity and the preceding calculation, $$ D(P_{p_0}^n\|P_{p_1}^n) =-\frac n2\log\left(1-\frac{1}{4n}\right). $$ For \(0\leq x<1\), \(-\log(1-x)\leq x/(1-x)\). Applying this with \(x=1/(4n)\) gives $$ D(P_{p_0}^n\|P_{p_1}^n) \leq \frac{n}{2}\frac{1/(4n)}{1-1/(4n)} =\frac{n}{2(4n-1)} \leq \frac16, $$ where the last inequality holds for \(n\geq1\). Pinsker’s inequality consequently gives $$ \operatorname{TV}(P_{p_0}^n,P_{p_1}^n) \leq \sqrt{\frac{1}{12}}<\frac12. $$ The two-point theorem, with separation \(\Delta=\delta\), now yields the minimax bound.

Interpretation and a Common Pitfall

The lower bound scales as \(1/\sqrt n\): doubling the sample size does not halve the guaranteed worst-case absolute error. This is a lower bound, not a claim that every estimator has exactly this risk, and the constant \(1/32\) is not intended to be sharp. Its significance is that no estimator can improve the worst-case rate beyond order \(1/\sqrt n\) over the full Bernoulli parameter space.

Common pitfall: It is tempting to argue that because the one-observation total variation is \(|p_1-p_0|\), the \(n\)-observation total variation is \(n|p_1-p_0|\). That is not a valid product-sample identity. Total variation does not generally add exactly this way; the exact distance depends on the joint distributions. Instead, compute or bound a product-sample divergence using its additivity, then apply Pinsker’s inequality. The bound above works precisely because the parameter separation is chosen to shrink with \(n\), keeping the two sample distributions hard to distinguish.