Two-Point Bounds for Gaussian Location

Why Gaussian Location Gives a Useful Lower Bound

A minimax lower bound can be obtained by finding two parameter values whose data distributions are difficult to distinguish. If an estimator must perform well at both values, it must also solve the corresponding testing problem. In a Gaussian location model, the comparison is especially transparent: the Kullback–Leibler divergence between two alternatives can be calculated exactly, and its dependence on sample size, noise variance, and separation is explicit.

The calculation is useful because it turns a choice of alternatives into a concrete risk bound. Alternatives that are too close have little separation in the parameter, while alternatives that are too far apart are easy to distinguish. The useful scale is where the two effects balance.

Model and notation: Observe independent random variables $X_1,\ldots,X_n$, each with distribution $N(\theta,\sigma^2)$, where $\sigma^2>0$ is known and $\theta$ belongs to a parameter space $\Theta\subseteq\mathbb{R}$. Write $P_\theta$ for the joint distribution of the sample and $\hat{\theta}$ for an estimator. For two parameter values $\theta_0,\theta_1$, their separation is $\Delta=|\theta_1-\theta_0|$.

The Two-Point Testing Bound

For two distributions $P_0$ and $P_1$, their total variation distance is $\operatorname{TV}(P_0,P_1)=\sup_A|P_0(A)-P_1(A)|$, where the supremum is over measurable events. A test is a measurable rule $\phi$ taking values in $\{0,1\}$, with value $j$ interpreted as choosing alternative $j$. The sum of its two error probabilities cannot be smaller than $1-\operatorname{TV}(P_0,P_1)$. This testing fact is the bridge from distinguishability to estimation risk.

Theorem (two-point bound): Let $(\Theta,d)$ be a metric parameter space, let $\theta_0,\theta_1\in\Theta$ have distance $\Delta=d(\theta_0,\theta_1)>0$, and let $P_0,P_1$ be the corresponding data distributions. For any measurable estimator $\hat{\theta}$ taking values in $\Theta$, and any $q>0$, $$ \max_{j\in\{0,1\}} E_{P_j}\!\left[d(\hat{\theta},\theta_j)^q\right] \ \geq\ \frac{\Delta^q}{2^{q+1}}\left(1-\operatorname{TV}(P_0,P_1)\right). $$

To prove the bound, form a test by choosing whichever of $\theta_0,\theta_1$ is closer to $\hat{\theta}$, resolving a tie in favor of $\theta_0$. If this test is wrong under $P_j$, the triangle inequality forces $d(\hat{\theta},\theta_j)\geq\Delta/2$. Indeed, if the estimate were strictly closer than $\Delta/2$ to the true parameter, it would be farther from the other parameter. Let $A$ be the event that the test chooses 1. Its two error probabilities sum to $P_0(A)+P_1(A^c)=1-\{P_1(A)-P_0(A)\}\geq 1-\operatorname{TV}(P_0,P_1)$. Consequently, $$ E_{P_0}[d(\hat{\theta},\theta_0)^q]+E_{P_1}[d(\hat{\theta},\theta_1)^q] \ \geq\ \left(\frac{\Delta}{2}\right)^q \left(1-\operatorname{TV}(P_0,P_1)\right). $$ The larger of two nonnegative numbers is at least half their sum, proving the result. $\square$

For absolute-error loss, take $q=1$; for squared-error loss, take $q=2$ and the usual distance on the real line. The result does not assume that the estimator is unbiased or that it has any particular form. It also gives a minimax lower bound whenever both alternatives belong to the parameter space: the supremum risk over the full space is at least the maximum risk over those two points.

Calculating the Gaussian Divergence

For distributions with densities $p_0,p_1$ relative to a common measure, the Kullback–Leibler divergence is $D_{\mathrm{KL}}(P_0\|P_1)=E_{P_0}[\log(p_0/p_1)]$, when this expectation is defined. The direction matters in general. For the Gaussian location family, either direction gives the same value.

Result (Gaussian location divergence): If $P_{\theta_0}$ and $P_{\theta_1}$ are the joint laws of $n$ independent $N(\theta_j,\sigma^2)$ observations, then $$ D_{\mathrm{KL}}(P_{\theta_0}\|P_{\theta_1}) =\frac{n(\theta_0-\theta_1)^2}{2\sigma^2} =\frac{n\Delta^2}{2\sigma^2}. $$

For one observation, the normal density is $f_\theta(x)=(2\pi\sigma^2)^{-1/2}\exp\{-(x-\theta)^2/(2\sigma^2)\}$. Its log density ratio is $$ \log\frac{f_{\theta_0}(x)}{f_{\theta_1}(x)} =\frac{(x-\theta_1)^2-(x-\theta_0)^2}{2\sigma^2}. $$

Under $P_{\theta_0}$, $E[X]=\theta_0$ and $E[(X-\theta_0)^2]=\sigma^2$. Thus the expected numerator is $E[(X-\theta_1)^2]-E[(X-\theta_0)^2]=\{(\theta_0-\theta_1)^2+\sigma^2\}-\sigma^2=(\theta_0-\theta_1)^2$. The one-observation divergence is therefore $(\theta_0-\theta_1)^2/(2\sigma^2)$. For independent observations the joint density is the product of the individual densities, so its log ratio is the sum of the $n$ individual log ratios. Taking expectations adds their divergences and gives the stated formula. $\square$

Pinsker’s inequality states that, for probability distributions $P,Q$, $\operatorname{TV}(P,Q)\leq\sqrt{D_{\mathrm{KL}}(P\|Q)/2}$ when the divergence is finite. Combining this inequality with the Gaussian calculation gives $$ \operatorname{TV}(P_{\theta_0},P_{\theta_1}) \leq \frac{\Delta\sqrt{n}}{2\sigma}. $$ The right-hand side can exceed one; in that case it is simply an uninformative upper bound, since total variation itself is at most one.

Choosing the Separation

The two-point theorem and Pinsker’s inequality give a useful explicit conclusion whenever $\Delta\leq\sigma/\sqrt{n}$. In that range, the total variation upper bound is at most $1/2$. For squared-error loss, $$ \max_{j\in\{0,1\}} E_{P_{\theta_j}}[(\hat{\theta}-\theta_j)^2] \ \geq\ \frac{\Delta^2}{8} \left(1-\frac{\Delta\sqrt{n}}{2\sigma}\right) \ \geq\ \frac{\Delta^2}{16}. $$ For absolute-error loss the corresponding bound is at least $\Delta/8$. These inequalities hold for every estimator, so they also lower-bound the minimax risk over any parameter space containing both alternatives.

Worked Example: A Basic Squared-Error Lower Bound

Suppose $n=36$, $\sigma=3$, and the parameter space contains $\theta_0=0$ and $\theta_1=1/2$. Here $\Delta=1/2$, and the divergence is $$ D_{\mathrm{KL}}(P_0\|P_{1/2}) =\frac{36(1/2)^2}{2(3)^2} =\frac{36/4}{18} =\frac12. $$

Pinsker’s inequality gives $\operatorname{TV}(P_0,P_{1/2})\leq\sqrt{(1/2)/2}=1/2$. Therefore, for every estimator, $$ \max_{j\in\{0,1\}}E_{P_j}[(\hat{\theta}-\theta_j)^2] \geq \frac{(1/2)^2}{8}(1-1/2) =\frac{1}{32}\cdot\frac12 =\frac{1}{64}. $$ This is a lower bound on the worst squared-error risk over the two alternatives, not a claim that every estimator attains exactly this risk.

Worked Example: A Bound at the Natural Noise Scale

Let $n=100$, $\sigma=2$, and take $\theta_0=0$, $\theta_1=0.2$. The separation is $\Delta=0.2=\sigma/\sqrt{n}$. Direct calculation gives $$ D_{\mathrm{KL}}(P_0\|P_{0.2}) =\frac{100(0.2)^2}{2(2)^2} =\frac{4}{8} =\frac12. $$

As in the preceding example, total variation is at most $1/2$. The squared-error risk of any estimator must consequently satisfy $$ \max_{j\in\{0,1\}}E_{P_j}[(\hat{\theta}-\theta_j)^2] \geq \frac{(0.2)^2}{8}\cdot\frac12 =\frac{0.04}{16} =0.0025. $$ For absolute-error loss, the same alternatives give the lower bound $\Delta(1-\operatorname{TV})/4\geq 0.2/8=0.025$.

The calculation illustrates the role of sample size: at the selected separation, the divergence remains $1/2$ as $n$ changes if the separation is adjusted to $\sigma/\sqrt n$. The resulting squared-error lower bound scales as $\sigma^2/n$.

Worked Example: Alternatives Can Be Too Far Apart

Take $n=20$, $\sigma=2$, and alternatives $\theta_0=-0.5$, $\theta_1=0.5$. Their separation is $\Delta=1$, so $$ D_{\mathrm{KL}}(P_{-0.5}\|P_{0.5}) =\frac{20(1)^2}{2(2)^2} =\frac{20}{8} =2.5. $$ Pinsker’s inequality would give $\operatorname{TV}\leq\sqrt{2.5/2}=\sqrt{1.25}>1$. Since total variation cannot exceed one, this upper bound supplies no positive lower bound through the two-point theorem.

This does not show that the distributions are identical or that estimation is easy throughout a larger parameter space. It shows only that this particular divergence bound, applied to these widely separated alternatives, is too weak. A smaller separation can yield a more informative comparison.

From a Two-Point Bound to a Minimax Statement

Let $\mathcal{R}(\hat{\theta},\theta)=E_\theta[(\hat{\theta}-\theta)^2]$ and define the minimax risk as $\inf_{\hat{\theta}}\sup_{\theta\in\Theta}\mathcal{R}(\hat{\theta},\theta)$, with the infimum over measurable estimators. If $\Theta$ contains $0$ and $\sigma/\sqrt n$, the preceding argument gives $$ \inf_{\hat{\theta}}\sup_{\theta\in\Theta} E_\theta[(\hat{\theta}-\theta)^2] \geq \frac{\sigma^2}{16n}. $$ Indeed, for each estimator the supremum over $\Theta$ is at least the maximum over those two points, and the two-point bound applies to every estimator before taking the infimum. If $\Theta$ does not contain the selected alternatives, this conclusion cannot be asserted from that pair; alternatives must be chosen inside the parameter space.

The constant $1/16$ is a consequence of this simple argument and Pinsker’s inequality, not necessarily the sharp minimax constant. The main information is the rate and its dependence on noise and sample size. Two-point bounds are particularly effective when the target is to show that no estimator can improve on a certain order of risk.

Common Pitfall

Common mistake: Choosing alternatives far apart because their parameter values are easier to tell apart, then treating a large Kullback–Leibler divergence as evidence of a strong lower bound. The correction is that the testing step needs a substantial probability of error, so the distributions must remain sufficiently close. Check the bound on total variation: if the divergence-based upper bound exceeds one, it gives no control at all. Select a smaller separation, often of order $\sigma/\sqrt n$, and verify both that the alternatives lie in $\Theta$ and that the resulting risk bound is positive.

Key takeaway: For Gaussian location data, the divergence between two $n$-sample alternatives is $n\Delta^2/(2\sigma^2)$. Pairing this exact calculation with a two-point testing bound and Pinsker’s inequality turns a separation of order $\sigma/\sqrt n$ into a squared-error minimax lower bound of order $\sigma^2/n$.

Check Your Understanding

Work through these questions using the two-point bound and the Gaussian divergence formula.

For $n$ independent $N(\theta,\sigma^2)$ observations, calculate the divergence between parameter values $\theta_0$ and $\theta_1$.
Why does a test built from an estimator make an estimation lower bound depend on total variation between the two data distributions?
For squared-error loss, state the two-point lower bound in terms of the separation $\Delta$ and total variation.
If $\Delta=\sigma/\sqrt n$, what upper bound does Pinsker’s inequality give for total variation?
Why does an upper bound on total variation greater than one fail to give a useful positive risk lower bound?