Chi-Squared Divergence for Mixture Testing

Why Mixtures Enter Testing Lower Bounds

A difficult testing problem need not have just one alternative. It may be more useful to compare a reference distribution with a mixture of many alternatives, especially when each alternative is indexed by an unknown sign, location, or other nuisance choice. The key calculation is to measure how close that mixture is to the reference distribution. Its chi-squared divergence can be expressed using pairwise products of likelihood ratios, which often makes a complicated mixture manageable.

This tutorial derives that identity and shows how it controls total variation and testing error. The direction of comparison matters throughout: the alternatives in the mixture must be dominated by the reference distribution for the stated chi-squared calculation.

Chi-Squared Divergence and the Mixture Identity

Definition: Let $Q$ and $P$ be probability distributions on the same measurable space, and suppose $Q$ is absolutely continuous with respect to $P$. Write $L=dQ/dP$ for the likelihood ratio. The chi-squared divergence of $Q$ from $P$ is $$ \chi^2(Q\|P)=E_P[(L-1)^2]=E_P[L^2]-1, $$ provided $E_P[L^2]$ is finite. If $Q$ is not absolutely continuous with respect to $P$, this divergence is defined to be infinite.

The expectation form follows because $E_P[L]=1$. This divergence is not symmetric: in general, $\chi^2(Q\|P)$ and $\chi^2(P\|Q)$ differ. For a testing lower bound based on a reference $P$, the useful direction is usually the divergence of the alternative distribution from $P$.

Consider a finite collection $Q_1,\ldots,Q_M$ of distributions, each absolutely continuous with respect to $P$, with likelihood ratios $L_j=dQ_j/dP$. Let $\pi_1,\ldots,\pi_M$ be nonnegative weights summing to one, and define the mixture $\overline Q=\sum_{j=1}^M\pi_j Q_j$. Its likelihood ratio is $\overline L=\sum_j\pi_jL_j$.

Theorem (chi-squared divergence of a finite mixture): If $E_P[L_j^2]$ is finite for every $j$, then $$ \chi^2(\overline Q\|P) =\sum_{j=1}^M\sum_{k=1}^M\pi_j\pi_k E_P[L_jL_k]-1. $$ Equivalently, the divergence is the weighted average of all pairwise likelihood-ratio cross-moments, minus one.

Proof. Since the mixture weights sum to one and each $L_j$ is a density ratio, $E_P[\overline L]=\sum_j\pi_jE_P[L_j]=1$. By the definition of chi-squared divergence,

\begin{aligned} \chi^2(\overline Q\|P) &=E_P[(\overline L-1)^2]\\ &=E_P[\overline L^2]-2E_P[\overline L]+1\\ &=E_P[\overline L^2]-1\\ &=E_P\left[\left(\sum_{j=1}^M\pi_jL_j\right) \left(\sum_{k=1}^M\pi_kL_k\right)\right]-1\\ &=\sum_{j=1}^M\sum_{k=1}^M\pi_j\pi_kE_P[L_jL_k]-1. \end{aligned}

The final expansion is valid because it is a finite sum; the assumed second moments ensure the displayed expectations exist. $\square$

This formula is useful because it exposes interactions between alternatives. The mixture divergence is not generally the weighted average of the individual divergences: the cross-moments $E_P[L_jL_k]$ also contribute.

Worked Example: A Finite-Sample Mixture

Let the sample space be $\{1,2,3,4\}$, with $P$ uniform. Let $Q_1=(1/2,1/2,0,0)$ and $Q_2=(1/2,0,1/2,0)$, and give the two alternatives equal mixture weights.

The mixture is $\overline Q=(1/2,1/4,1/4,0)$. Its probability differences from $P=(1/4,1/4,1/4,1/4)$ are $(1/4,0,0,-1/4)$. Therefore,

\chi^2(\overline Q\|P) =\sum_{x=1}^4\frac{(\overline Q(x)-P(x))^2}{P(x)} =\frac{(1/4)^2}{1/4}+\frac{(-1/4)^2}{1/4} =\frac12.

The total variation distance, defined below, is $1/2\sum_x|\overline Q(x)-P(x)|=1/4$. The pairwise formula gives the same chi-squared value. The likelihood ratios are $L_1=(2,2,0,0)$ and $L_2=(2,0,2,0)$. Thus $E_P[L_1^2]=E_P[L_2^2]=2$, while $E_P[L_1L_2]=1$, and

\chi^2(\overline Q\|P) =\frac14\{2+2+2(1)\}-1 =\frac12.

From Chi-Squared Divergence to Testing Error

Definition: The total variation distance between probability distributions $Q$ and $P$ is $$ \operatorname{TV}(Q,P)=\sup_A |Q(A)-P(A)|, $$ where the supremum is over measurable sets $A$. If $Q$ has likelihood ratio $L=dQ/dP$, then $\operatorname{TV}(Q,P)=\frac12 E_P[|L-1|]$.

Theorem (chi-squared bound on total variation): If $Q\ll P$ and $\chi^2(Q\|P)<\infty$, then $$ \operatorname{TV}(Q,P)\leq \frac12\sqrt{\chi^2(Q\|P)}. $$

Proof. The likelihood-ratio formula for total variation and the Cauchy–Schwarz inequality give

\operatorname{TV}(Q,P) =\frac12 E_P[|L-1|] \leq \frac12\sqrt{E_P[(L-1)^2]}\sqrt{E_P[1^2]} =\frac12\sqrt{\chi^2(Q\|P)},

because $E_P[1^2]=1$. $\square$

A test is a measurable function $\phi$ taking values in $[0,1]$, interpreted as the probability of rejecting $P$. Its type-I error under $P$ is $E_P[\phi]$, and its type-II error under $Q$ is $E_Q[1-\phi]$. The sum of these errors cannot be small when $P$ and $Q$ are close in total variation.

Testing bound: For any test $\phi$ of $P$ against $Q$, $$ E_P[\phi]+E_Q[1-\phi]\geq 1-\operatorname{TV}(Q,P) \geq 1-\frac12\sqrt{\chi^2(Q\|P)}. $$ The last inequality applies when the chi-squared divergence is finite.

To verify the first inequality, rewrite the sum as $1-(E_Q[\phi]-E_P[\phi])$. For any measurable function $\phi$ between zero and one, $E_Q[\phi]-E_P[\phi]\leq \operatorname{TV}(Q,P)$. For example, this follows by writing $\phi(\omega)=\int_0^1\mathbf{1}\{\phi(\omega)>t\}\,dt$ and applying the definition of total variation to each set in the integral. The bound therefore also covers randomized tests.

Worked Example: A Bernoulli Product Mixture

Observe $n=5$ independent Bernoulli trials. Under the reference $P$, each trial has success probability $1/2$. The two alternatives $Q_+$ and $Q_-$ have success probabilities $1/2+a$ and $1/2-a$, respectively, with $a=0.1$. Mix them with equal weights.

For one observation, the likelihood ratios under $Q_+$ and $Q_-$ take values $1+2a,1-2a$ and $1-2a,1+2a$, respectively, for outcomes 1 and 0. Under $P$, each outcome has probability $1/2$. Hence the one-observation second moments are $1+4a^2$, and the cross-moment is $1-4a^2$. Independence makes the corresponding $n$-observation moments their $n$th powers:

E_P[L_+^2]=(1+4a^2)^n,\qquad E_P[L_-^2]=(1+4a^2)^n,\qquad E_P[L_+L_-]=(1-4a^2)^n.

The mixture identity now yields

\chi^2(\overline Q\|P) =\frac12\left\{(1+4a^2)^n+(1-4a^2)^n\right\}-1.

Here $4a^2=0.04$, so $(1.04)^5=1.2166529024$ and $(0.96)^5=0.8153726976$. Thus $\chi^2(\overline Q\|P)=0.0160128$, and

\operatorname{TV}(\overline Q,P) \leq \frac12\sqrt{0.0160128} \approx 0.0633.

Consequently, every test of the reference against this mixture has type-I plus average type-II error at least $1-0.0633=0.9367$. The statement concerns the mixture; it does not say that either component alternative is individually close to $P$.

Worked Example: A Gaussian Sign Mixture

Let $P=N(0,I_d)$, and for each sign vector $v\in\{-1,+1\}^d$, let $Q_v=N(\mu v,I_d)$. Mix uniformly over the $2^d$ sign vectors. The likelihood ratio at $x\in\mathbb{R}^d$ is

L_v(x)=\exp\left(\mu v^\mathsf{T}x-\frac{d\mu^2}{2}\right).

For two sign vectors $v,w$, the Gaussian moment-generating function gives

E_P[L_vL_w] =\exp\left(-d\mu^2+\frac{\mu^2}{2}\|v+w\|_2^2\right) =\exp(\mu^2 v^\mathsf{T}w).

In the last equality, $\|v+w\|_2^2=2d+2v^\mathsf{T}w$. For independent uniform $v,w$, the products $v_jw_j$ are independent signs, so averaging the cross-moment gives

1+\chi^2(\overline Q\|P) =E_{v,w}\!\left[\exp(\mu^2v^\mathsf{T}w)\right] =\{\cosh(\mu^2)\}^d.

For example, take $d=4$ and $\mu^2=0.05$. Then $\cosh(0.05)\approx1.00125026$, so $\chi^2(\overline Q\|P)=\{\cosh(0.05)\}^4-1\approx0.00501$. It follows that $\operatorname{TV}(\overline Q,P)\leq \frac12\sqrt{0.00501}\approx0.0354$. The pairwise identity avoids calculating the density of the full mixture directly.

Using the Bound for Metric Estimation

The testing inequality can be converted into an estimation lower bound when the reference parameter is separated from every parameter in the mixture. Let the parameter values be $\theta_0,\theta_1,\ldots,\theta_M$, with distributions $P=P_{\theta_0}$ and $Q_j=P_{\theta_j}$. Suppose a metric $d$ satisfies $d(\theta_0,\theta_j)\geq\Delta>0$ for all $j$. Form the equal or weighted mixture $\overline Q$ of the $Q_j$'s.

Given an estimator $\hat\theta$, test $P$ against the mixture by setting $\phi=1$ when $d(\hat\theta,\theta_0)\geq\Delta/2$. Under $P$, rejection implies $d(\hat\theta,\theta_0)\geq\Delta/2$. Under $Q_j$, failure to reject implies $d(\hat\theta,\theta_0)<\Delta/2$, and the triangle inequality gives

d(\hat\theta,\theta_j) \geq d(\theta_0,\theta_j)-d(\hat\theta,\theta_0) >\frac{\Delta}{2}.

Thus each testing error is bounded above by $2/\Delta$ times the corresponding expected metric loss. If $R=\sup_{\theta\in\{\theta_0,\ldots,\theta_M\}}E_\theta[d(\hat\theta,\theta)]$, the null risk and the mixture-average alternative risk are each at most $R$. Combining these facts with the testing bound gives the fully explicit conclusion

2R\geq \frac{\Delta}{2} \left\{E_P[\phi]+E_{\overline Q}[1-\phi]\right\} \geq \frac{\Delta}{2}\{1-\operatorname{TV}(\overline Q,P)\}, \qquad R\geq\frac{\Delta}{4} \left\{1-\frac12\sqrt{\chi^2(\overline Q\|P)}\right\}.

When the last bracket is positive, this is a nontrivial lower bound. It is particularly useful when the alternatives are individually numerous, but their mixture has a small chi-squared divergence from the reference.

Common Pitfall: Averaging Individual Divergences

A tempting but generally incorrect shortcut is to bound the mixture divergence by the weighted average of $\chi^2(Q_j\|P)$ and ignore cross-terms. The mixture identity shows why this can fail: it includes $E_P[L_jL_k]$ for distinct alternatives. Those terms can either raise or reduce the final divergence relative to what a calculation based only on diagonal terms suggests. In particular, component distributions can be distinguishable from $P$ even when their mixture equals $P$.

The correction is to compute or bound the full pairwise cross-moment matrix, including diagonal and off-diagonal terms, before applying the total-variation inequality. Also check absolute continuity and finiteness of the second moments; without them the finite chi-squared bound cannot be invoked. Finally, remember that the chi-squared argument gives an upper bound on total variation, which in turn gives a lower bound on testing error.

Check Your Understanding

Use the definitions and derivations above to answer these questions.

What absolute-continuity and moment conditions are needed for the finite-mixture identity?
Why do cross-moments $E_P[L_jL_k]$ appear in the chi-squared divergence of a mixture?
If $\chi^2(Q\|P)=0.36$, what upper bound does the chi-squared inequality give for $\operatorname{TV}(Q,P)$, and what lower bound follows for the sum of testing errors?
In the Bernoulli product example, why is the cross-moment for $Q_+$ and $Q_-$ based on $1-4a^2$, rather than $1+4a^2$?
Which triangle-inequality step ensures that failing to reject the reference implies substantial estimation loss under every separated alternative?