Selecting a Divergence for a Lower Bound

Why the Choice of Divergence Matters

A lower bound often reduces to asking whether two probability distributions are hard to distinguish. The testing error is governed directly by total variation, but total variation may be awkward to calculate. Kullback–Leibler, Hellinger, and chi-squared divergence can be easier to evaluate in particular models, or behave more simply for independent observations. The useful choice is the one that both fits the model and yields a nontrivial bound on testing error.

This tutorial compares those four quantities and establishes the conversions most often used in lower-bound arguments. The inequalities have different directions and support conditions, so naming a divergence without checking its orientation and assumptions is not enough.

Definitions and the Testing Target

Let $P$ and $Q$ be probability distributions with densities $p$ and $q$ relative to a common dominating measure $\mu$. For discrete distributions, $\mu$ may be counting measure; for continuous distributions, it may be Lebesgue measure. The definitions below also apply to general probability measures using a suitable dominating measure.

Definition: The total variation distance is $$ \operatorname{TV}(P,Q)=\sup_A |P(A)-Q(A)|=\frac{1}{2}\int |p-q|\,d\mu. $$ The Kullback–Leibler divergence from $P$ to $Q$ is $$ \operatorname{KL}(P\|Q)=\int p\log\!\left(\frac{p}{q}\right)d\mu, $$ with value $+\infty$ if $P$ is not absolutely continuous with respect to $Q$. The squared Hellinger distance and chi-squared divergence, in the conventions used here, are $$ H^2(P,Q)=\int(\sqrt p-\sqrt q)^2\,d\mu,\qquad \chi^2(P\|Q)=\int\left(\frac{p}{q}-1\right)^2q\,d\mu. $$ The chi-squared divergence is defined when $P\ll Q$, and is $+\infty$ otherwise. The Hellinger distance is always finite, with $0\le H^2(P,Q)\le 2$.

The order of the arguments matters for KL and chi-squared divergence: in general, $\operatorname{KL}(P\|Q)\ne\operatorname{KL}(Q\|P)$ and $\chi^2(P\|Q)\ne\chi^2(Q\|P)$. Total variation and Hellinger distance are symmetric. For testing $P$ against $Q$, a test $\phi$ chooses $P$ when $\phi=1$ and $Q$ when $\phi=0$. Its two error probabilities sum to $P(\phi=0)+Q(\phi=1)$.

Theorem: The smallest possible sum of the two testing errors is $1-\operatorname{TV}(P,Q)$. Consequently, if $\operatorname{TV}(P,Q)\le c$, every test has error sum at least $1-c$.

To see this, consider a nonrandomized test that chooses $P$ on a measurable set $A$. Its error sum is $P(A^c)+Q(A)=1-[P(A)-Q(A)]$. Maximizing $P(A)-Q(A)$ gives total variation, attained by $A=\{x:p(x)\ge q(x)\}$. For any randomized test, the error contribution at each $x$ is a weighted average of $p(x)$ and $q(x)$, so it cannot be smaller than $\min\{p(x),q(x)\}$. Integrating gives the same minimum, $\int\min(p,q)d\mu=1-\operatorname{TV}(P,Q)$. $\square$

Conversions That Turn Calculations into Testing Bounds

The central practical question is how a manageable divergence controls total variation. Pinsker’s inequality is the standard conversion from KL:

Theorem (Pinsker’s inequality): If $\operatorname{KL}(P\|Q)<\infty$, then $$ \operatorname{TV}(P,Q)\le \sqrt{\frac{\operatorname{KL}(P\|Q)}{2}}. $$

Here is a proof that also explains the constant. Choose $A=\{p\ge q\}$, so that $P(A)-Q(A)=\operatorname{TV}(P,Q)$. Grouping the densities into $A$ and its complement cannot increase KL: the log-sum inequality gives $$ \operatorname{KL}(P\|Q)\ge a\log\frac{a}{b}+(1-a)\log\frac{1-a}{1-b}, $$ where $a=P(A)$ and $b=Q(A)$. The log-sum inequality follows by applying convexity of $u\log u$ separately on each of the two sets. For fixed $b\in(0,1)$, let the right-hand side be $d(a\|b)$. It satisfies $d(b\|b)=0$, its derivative in $a$ is zero at $a=b$, and $$ \frac{\partial^2}{\partial a^2}\left[d(a\|b)-2(a-b)^2\right] =\frac{1}{a(1-a)}-4\ge 0. $$ Thus $d(a\|b)\ge 2(a-b)^2$, including endpoint cases by continuity. Since $a-b=\operatorname{TV}(P,Q)$, Pinsker’s inequality follows. $\square$

Hellinger distance gives another direct control. Define the affinity $\rho(P,Q)=\int\sqrt{pq}\,d\mu$, so $H^2(P,Q)=2-2\rho(P,Q)$. Cauchy–Schwarz yields $$ \operatorname{TV}(P,Q) \le \frac{1}{2}\left(\int(\sqrt p-\sqrt q)^2d\mu\right)^{1/2} \left(\int(\sqrt p+\sqrt q)^2d\mu\right)^{1/2} \le H(P,Q), $$ because the second integral is $2+2\rho(P,Q)\le4$. Also, when $\operatorname{KL}(P\|Q)$ is finite, Jensen’s inequality under $P$ gives $\operatorname{KL}(P\|Q)\ge -2\log\rho(P,Q)\ge 2(1-\rho(P,Q))=H^2(P,Q)$. These relations are useful, but they do not make the divergences interchangeable: a bound may become loose when converted.

For chi-squared divergence, Cauchy–Schwarz gives a simple control when $P\ll Q$: $$ \operatorname{TV}(P,Q)=\frac{1}{2}\int\left|\frac{p}{q}-1\right|q\,d\mu \le \frac{1}{2}\sqrt{\chi^2(P\|Q)}. $$ The same density ratio appears in both the definition and this bound, which makes chi-squared divergence particularly natural when likelihood ratios are easy to calculate.

Independent Observations: Which Quantities Accumulate Simply?

For $n$ independent observations, write $P^n$ and $Q^n$ for the product distributions. Under the stated finiteness conditions, KL adds, while Hellinger affinity and the chi-squared second moment multiply:

Theorem: If the one-observation quantities are well-defined, then $$ \operatorname{KL}(P^n\|Q^n)=n\operatorname{KL}(P\|Q),\qquad 1+\chi^2(P^n\|Q^n)=\bigl(1+\chi^2(P\|Q)\bigr)^n, $$ and $$ \rho(P^n,Q^n)=\rho(P,Q)^n,\qquad H^2(P^n,Q^n)=2\left[1-\left(1-\frac{H^2(P,Q)}{2}\right)^n\right]. $$

For KL, the product density ratio is $\prod_{i=1}^n p(x_i)/q(x_i)$; its logarithm is a sum. Integrating that sum under $P^n$ gives $n\operatorname{KL}(P\|Q)$. For chi-squared divergence, let $L=p/q$. Under $Q$, $E_Q[L]=1$ and $E_Q[L^2]=1+\chi^2(P\|Q)$. The product likelihood ratio is $\prod_i L(X_i)$, whose squared expectation under $Q^n$ is $(E_Q[L^2])^n$. Subtracting one proves the formula. Finally, the product densities give $\rho(P^n,Q^n)=\prod_i\int\sqrt{pq}\,d\mu=\rho(P,Q)^n$; substituting $\rho=1-H^2/2$ yields the Hellinger identity. These formulas show why a divergence that is small for one observation may still require careful scaling with sample size.

Worked Examples: Matching the Divergence to the Model

Worked Example: Gaussian Location Distributions

Compare $P=N(\delta,\sigma^2)$ and $Q=N(0,\sigma^2)$, with $\sigma>0$. The likelihood ratio is $p(x)/q(x)=\exp(\delta x/\sigma^2-\delta^2/(2\sigma^2))$. Taking its logarithm and expectation under $P$, where $E_P[X]=\delta$, gives $$ \operatorname{KL}(P\|Q)=\frac{\delta^2}{2\sigma^2}. $$ The normal-density integral for the affinity gives $\rho(P,Q)=\exp(-\delta^2/(8\sigma^2))$, hence $H^2(P,Q)=2[1-\exp(-\delta^2/(8\sigma^2))]$. Under $Q$, the likelihood ratio has second moment $\exp(\delta^2/\sigma^2)$, so $\chi^2(P\|Q)=\exp(\delta^2/\sigma^2)-1$.

For $\delta/\sigma=0.5$, these values are $\operatorname{KL}=0.125$, $H^2\approx0.0615$, and $\chi^2\approx0.2840$. The two normal densities cross at $x=\delta/2$; integrating their difference on the side where $p\ge q$ gives $\operatorname{TV}=2\Phi(|\delta|/(2\sigma))-1\approx0.1974$. Pinsker gives the valid, slightly larger upper bound $\sqrt{0.125/2}=0.25$. For $n$ independent observations, KL becomes $0.125n$, while the other product divergences follow the preceding theorem.

Worked Example: A Rare-Event Bernoulli Comparison

Let $P=\operatorname{Bernoulli}(0.01)$ and $Q=\operatorname{Bernoulli}(0.0001)$, where the parameter is the probability of observing 1. Their total variation distance is the difference in success probabilities: $$ \operatorname{TV}(P,Q)=|0.01-0.0001|=0.0099. $$ The KL divergence in the indicated direction is $$ \operatorname{KL}(P\|Q)=0.01\log(100)+0.99\log(0.99/0.9999)\approx0.0362. $$ The chi-squared divergence is $$ \chi^2(P\|Q)=\frac{(0.01-0.0001)^2}{0.0001(1-0.0001)}\approx0.9804, $$ and the reversed divergence is $\chi^2(Q\|P)=(0.01-0.0001)^2/[0.01(1-0.01)]=0.0099$. The squared Hellinger distance is $$ (\sqrt{0.01}-\sqrt{0.0001})^2+(\sqrt{0.99}-\sqrt{0.9999})^2\approx0.00812. $$

The chi-squared bound in the first direction gives only $\operatorname{TV}\le\sqrt{0.9804}/2\approx0.495$, much larger than the exact value $0.0099$. In the reverse direction, the chi-squared divergence is much smaller, though its conversion still gives an upper bound rather than an exact distance. This example illustrates that the direction and numerical size of a divergence can strongly affect the usefulness of its testing bound.

Worked Example: A Support-Sensitive Comparison

Let $P$ put all its mass at 0, and let $Q$ put probability $0.99$ at 0 and $0.01$ at 1. The event $\{1\}$ has probabilities 0 and 0.01, so $\operatorname{TV}(P,Q)=0.01$. Since $P\ll Q$, $$ \operatorname{KL}(P\|Q)=\log(1/0.99)\approx0.01005,\qquad \chi^2(P\|Q)=\frac{(1-0.99)^2}{0.99}+\frac{(0-0.01)^2}{0.01}\approx0.01010. $$ The affinity is $\sqrt{0.99}$, so $H^2(P,Q)=2-2\sqrt{0.99}\approx0.01003$. In the opposite direction, $Q\not\ll P$, because $Q$ assigns positive probability to 1 while $P$ assigns none. Thus $\operatorname{KL}(Q\|P)$ and $\chi^2(Q\|P)$ are infinite, even though the symmetric distances remain finite.

The forward KL, forward chi-squared, or Hellinger calculation can all give useful controls here. Reversing the KL or chi-squared arguments makes those divergences unusable as finite bounds. Always check absolute continuity in the direction actually used.

How to Select a Divergence

A practical selection starts with the target: a testing lower bound needs an upper bound on total variation. Then choose a divergence that can be calculated under the model, checking its direction and support conditions. The following summary captures the main trade-offs.

Quantity	Useful feature	Check before using
Total variation	Directly determines optimal testing error	May be difficult to calculate for complex distributions
KL divergence	Adds over independent observations; often tractable from log likelihoods	Requires absolute continuity in the chosen direction; Pinsker may be loose
Hellinger distance	Symmetric, finite, and has a simple product-affinity formula	Keep track of whether the convention is $H$ or $H^2$
Chi-squared divergence	Useful when a likelihood-ratio second moment is tractable	Requires the chosen numerator distribution to be absolutely continuous with respect to the denominator; can be highly direction-sensitive

A common mistake is to assume that a small-looking KL divergence, or a finite chi-squared divergence, automatically gives a sharp testing conclusion. The correction is to write the actual conversion being used: for example, $\operatorname{TV}\le\sqrt{\operatorname{KL}/2}$ or $\operatorname{TV}\le\sqrt{\chi^2}/2$, and then check whether that upper bound is informative. Another mistake is to reverse the arguments of KL or chi-squared divergence without rechecking support. In lower-bound work, the best divergence is not necessarily the most familiar one; it is the one whose calculation and conversion remain valid and useful for the pair of distributions at hand.

Key takeaway: Total variation is the testing target. KL, Hellinger, and chi-squared divergence are tools for controlling it, with different assumptions, directions, and product-sample behavior. Calculate first, convert second, and verify that the resulting bound is nontrivial.

Check Your Understanding

Use the definitions and conversion inequalities to answer the following.

What is the minimum possible sum of the two testing errors when $\operatorname{TV}(P,Q)=0.3$?
State the absolute-continuity condition needed for finite $\chi^2(P\|Q)$, and explain why reversing its arguments can change the answer.
If $\operatorname{KL}(P\|Q)=0.08$, what upper bound does Pinsker’s inequality give for $\operatorname{TV}(P,Q)$?
For independent observations, which of KL, affinity, and $1+\chi^2$ add or multiply across the product distributions?
Why might a finite chi-squared divergence still produce a weak testing bound?