Selecting Two Hard Alternatives

Why the Choice of Pair Matters

A two-point lower bound turns an estimation problem into a comparison between two possible data-generating distributions. The key is not merely to find two different parameter values. They must be far apart in the quantity being estimated, yet hard to distinguish from the observations. If either condition fails, the resulting lower bound may say little about the difficulty of the problem.

The earlier material on Le Cam’s method gives the connection between estimation and binary testing. Here the emphasis is on constructing and checking the pair. In particular, closeness must be assessed for the distributions of the entire observed sample, and the parameter values must belong to the model under study.

A Pair-Selection Criterion

Let $\Theta$ be a parameter space, let $P_\theta$ denote the distribution of the data under $\theta$, and suppose the target $g(\theta)$ lies in a metric space with metric $d$. An estimator $T$ takes values in that space. For a power $q>0$, define its worst-case risk by

R(T)=\sup_{\theta\in\Theta} E_\theta\!\left[d\bigl(T,g(\theta)\bigr)^q\right].

For two candidates $\theta_0,\theta_1$, write $\Delta=d(g(\theta_0),g(\theta_1))$. Their data distributions are compared using total variation distance,

\operatorname{TV}(P,Q)=\sup_A |P(A)-Q(A)|.

The following bound makes the design goal precise. It applies when the target space is metric, the estimator is measurable, and the displayed risks are defined (possibly with value $+\infty$).

Theorem: For any $\theta_0,\theta_1\in\Theta$ and $q>0$, $$ \inf_T \sup_{\theta\in\Theta} E_\theta\!\left[d\bigl(T,g(\theta)\bigr)^q\right] \ \geq\ \frac{\Delta^q}{2^{q+1}}\left(1-\operatorname{TV}(P_{\theta_0},P_{\theta_1})\right). $$

To prove it, take any estimator $T$ and turn it into a test: choose the target point nearer to $T$, breaking ties in favor of $\theta_0$. If this test chooses $\theta_1$ when $\theta_0$ is true, then $T$ is at least $\Delta/2$ from $g(\theta_0)$. Indeed, if it were closer than $\Delta/2$, the triangle inequality would make it strictly nearer to $g(\theta_0)$. The same argument shows that a wrong choice under $\theta_1$ incurs distance at least $\Delta/2$ from $g(\theta_1)$.

Let $A$ be the event that the test chooses $\theta_1$. Its two error probabilities sum to $P_{\theta_0}(A)+P_{\theta_1}(A^c)$, which is at least $1-\operatorname{TV}(P_{\theta_0},P_{\theta_1})$ by the definition of total variation. The sum of the two risks is therefore at least $(\Delta/2)^q\bigl(1-\operatorname{TV}(P_{\theta_0},P_{\theta_1})\bigr)$. Their maximum is at least half their sum. The worst-case risk over $\Theta$ is at least this maximum, and taking the infimum over $T$ proves the result. $\square$

Thus a useful pair has positive target separation and total variation bounded away from one. For absolute-error loss, if the pair has $\operatorname{TV}\leq 1/2$, the lower bound is at least $\Delta/8$. A larger separation helps, but only if the distributions remain sufficiently close.

Checking Closeness With Chi-Squared Divergence

When one distribution is absolutely continuous with respect to another, chi-squared divergence can make sample-level closeness easy to verify. Define $\chi^2(P\|Q)=E_Q[(dP/dQ-1)^2]$. Two useful inequalities are collected below. The total variation inequality follows by writing the density difference as $(dP/dQ-1)dQ$ and applying Cauchy–Schwarz; the factor $1/2$ comes from the density formula for total variation.

Result: If $P\ll Q$, then $$ \operatorname{TV}(P,Q)\leq \frac12\sqrt{\chi^2(P\|Q)}. $$ If $P\ll Q$ and $P^n,Q^n$ are the product distributions for $n$ independent observations, then $$ 1+\chi^2(P^n\|Q^n)=\bigl(1+\chi^2(P\|Q)\bigr)^n. $$

For completeness, put $r=dP/dQ$. Since $E_Q[r]=1$, expanding the square gives $1+\chi^2(P\|Q)=E_Q[r^2]$. The product likelihood ratio is $\prod_{i=1}^n r(X_i)$; independence under $Q^n$ gives $E_{Q^n}[(\prod_i r(X_i))^2]=(E_Q[r^2])^n$. Applying the same identity to the product distributions proves the formula. For the first inequality, $\operatorname{TV}(P,Q)=\tfrac12 E_Q[|r-1|]$, and Cauchy–Schwarz gives $E_Q[|r-1|]\leq\sqrt{E_Q[(r-1)^2]}$. $\square$

This calculation suggests a practical scale choice. If a one-observation divergence is of order $\delta^2$, the product divergence is often controlled by choosing $\delta$ of order $1/\sqrt n$. The next example checks that idea in a concrete model.

Worked Example: A Pair in a Three-Category Model

One observation takes values $1,2,3$, with probabilities \[ P_\theta=\left(\frac13+\theta,\frac13-\theta,\frac13\right), \qquad -\frac16\leq\theta\leq\frac16. \] The target is $\theta$, with absolute-error loss, and the data are $n$ independent observations. Choose $\theta_0=-\delta$ and $\theta_1=\delta$, where $\delta=1/(8\sqrt n)$. These are both valid parameter values because $\delta\leq1/8<1/6$, and their target separation is $\Delta=2\delta$.

For one observation, direct calculation gives \[ \chi^2(P_\delta\|P_{-\delta}) =\frac{4\delta^2}{1/3-\delta}+\frac{4\delta^2}{1/3+\delta} =\frac{(8/3)\delta^2}{1/9-\delta^2}. \] Since $\delta\leq1/8<1/6$, the denominator is at least $1/12$, so this divergence is at most $32\delta^2$. For the full sample, the product identity and $1+x\leq e^x$ give \[ \chi^2(P_\delta^n\|P_{-\delta}^n) \leq (1+32\delta^2)^n \leq e^{32n\delta^2}-1 =e^{1/2}-1<1. \] Consequently, $\operatorname{TV}(P_\delta^n,P_{-\delta}^n)<1/2$. The two-point theorem now gives minimax absolute-error risk at least \[ \frac{2\delta}{4}\left(1-\operatorname{TV}(P_\delta^n,P_{-\delta}^n)\right) >\frac{\delta}{4} =\frac{1}{32\sqrt n}. \] The pair is valid, its target separation is explicit, and its sample distributions meet the required closeness condition.

When Total Variation Is More Useful Than KL

A divergence bound is a tool for verifying closeness, not a requirement that must be satisfied at all costs. In particular, Kullback–Leibler divergence can be infinite when the distributions have different supports, even if their total variation distance is small. The next pair shows why it is important to check the chosen comparison’s conditions before relying on it.

Worked Example: Shifted Uniform Distributions

Let one observation have distribution $P_\theta=\operatorname{Uniform}[\theta,\theta+1]$, with $\theta\in[0,1]$. The target is $\theta$, loss is absolute error, and there are $n$ independent observations. Choose $\theta_0=0$ and $\theta_1=\delta=1/(4n)$, both of which belong to the parameter space. Their target separation is $\delta$.

The two sample densities are each one on their respective unit-volume cubes in $\mathbb R^n$, and zero elsewhere. The cubes overlap on $[\delta,1]^n$, whose volume is $(1-\delta)^n$. For two densities, total variation is one minus the integral of their pointwise minimum; hence \[ \operatorname{TV}(P_0^n,P_\delta^n)=1-(1-\delta)^n \leq n\delta=\frac14. \] The inequality follows from $(1-\delta)^n\geq1-n\delta$, valid for $0\leq\delta\leq1$. The two-point bound therefore yields minimax absolute-error risk at least \[ \frac{\delta}{4}\left(1-\operatorname{TV}(P_0^n,P_\delta^n)\right) \geq\frac{3\delta}{16} =\frac{3}{64n}. \] Here $P_\delta$ is not absolutely continuous with respect to $P_0$: the interval $(1,1+\delta]$ has positive probability under $P_\delta$ and zero probability under $P_0$. Thus $\operatorname{KL}(P_\delta\|P_0)=+\infty$, while total variation still certifies the needed closeness.

Choose the Scale, Then Verify the Whole Pair

Selecting alternatives is often a balance between separation and distinguishability. A useful construction starts with a simple path through the parameter space, such as $\theta_0$ and $\theta_0+\delta$, and then asks how the target distance and the sample divergence change with $\delta$. The value of $\delta$ should keep both parameters inside $\Theta$, produce a non-negligible target gap, and keep the total variation of the full-sample distributions below a fixed constant less than one.

Specify the target and loss.
Identify $g(\theta)$, its metric $d$, and the power $q$. Separation in a parameter coordinate is useful only if it separates the target being estimated.

Propose two admissible parameters.
Check explicitly that $\theta_0,\theta_1\in\Theta$, including any boundary or normalization constraints.

Measure separation and sample-level closeness.
Compute $\Delta=d(g(\theta_0),g(\theta_1))$, then bound $\operatorname{TV}(P_{\theta_0},P_{\theta_1})$ for the actual data experiment.

Substitute and inspect the bound.
Use the two-point inequality and check that its dependence on sample size is informative for the problem at hand.

A frequent mistake is to demonstrate that $g(\theta_0)$ and $g(\theta_1)$ are far apart and conclude that the minimax risk must be large. The conclusion does not follow without controlling the distributions: if total variation is close to one, the theorem’s factor $1-\operatorname{TV}$ is close to zero. The correction is to verify both parts of the construction, at the sample level, before interpreting the lower bound. Another warning is to quote a finite divergence formula without checking absolute continuity; the shifted-uniform example shows that this can invalidate the argument even when a direct total-variation calculation succeeds.

Key takeaway: A successful two-point construction is a verified trade-off: admissible alternatives have a substantial target gap, while their complete data distributions remain difficult to distinguish. The lower bound is only as useful as both checks make it.

Check Your Understanding

For each question, identify what must be checked before applying a two-point lower bound.

For absolute-error loss, what lower bound follows when the target separation is $\Delta$ and the total variation distance is at most $1/2$?
Why must closeness be checked for the full-sample distributions rather than only for a single observation?
In the three-category example, why is $\delta=1/(8\sqrt n)$ a valid choice for every positive integer $n$?
What condition permits use of the stated chi-squared product identity?
Why does infinite KL divergence fail to rule out a useful two-point construction in the shifted-uniform example?

Selecting Two Hard Alternatives

What You'll Learn