Hypothesis Testing and Stein's Lemma: The KL Divergence as the Error Exponent

Intuition Beginner

You have a coin. You suspect it is biased, but you are not sure. You flip it many times and count the heads. If it is fair, you expect about half heads. If it is biased toward heads, you expect more. After enough flips, you can tell which coin you have with high confidence.

This is the hypothesis testing problem in its simplest form. You observe data and must decide between two explanations — two hypotheses about the distribution that generated the data. The fundamental question: how many samples do you need before you can decide reliably?

The answer depends on how different the two distributions are. If the coin is fair (50/50) versus a coin that lands heads 99 percent of the time, a single flip is often enough. But if the coin is fair versus a coin that is 51/49, you need many flips to tell them apart. The KL divergence — introduced in 46.01.02 — measures exactly this distinguishability.

Stein's lemma gives the precise answer. If you draw n independent samples and require that the probability of a false alarm stays below some small threshold, then the best you can do is make the probability of a miss decay like $2^{-nD}$, where $D$ is the KL divergence between the two distributions. The divergence is the error exponent: it tells you the rate at which your mistakes vanish. Double the divergence, and you need half as many samples to achieve the same reliability.

The trade-off between the two kinds of errors is the heart of the subject. You cannot make both errors small simultaneously — there is always a cost. Stein's lemma pins down one side of this trade-off: fix the false-alarm rate, and the miss rate has a definite, optimal exponential rate given by the KL divergence.

Visual Beginner

Figure: two bar charts side by side. The left shows a Bernoulli(0.5) distribution — two equal bars at 0.5. The right shows a Bernoulli(0.7) distribution — bars at 0.3 and 0.7. Below each pair, the log-likelihood ratio $\log (P(x)/Q(x))$ for each outcome is shown. The two distributions overlap, but the likelihood ratio tells you how to weight the evidence from each observation.

Quantity	Value
$P$ (null)	Bernoulli(0.5)
$Q$ (alternative)	Bernoulli(0.7)
$D(P|Q)$ in bits	0.188
$D(Q|P)$ in bits	0.210
Samples for type II error $<0.01$ (at type I $\le 0.05$)	about 36

The asymmetry is striking: $D(P\Vert Q)\ne D(Q\Vert P)$ in general. Stein's lemma uses $D(P\Vert Q)$ when $P$ is the null, not the other direction. Swapping the hypotheses changes the exponent.

Worked example Beginner

A factory produces light bulbs. Under normal operation, each bulb is good with probability 0.8 (distribution $P$). A faulty machine produces bulbs that are good with probability only 0.5 (distribution $Q$). You test $n$ bulbs. You want to detect the faulty machine without raising too many false alarms.

The KL divergence between $P=\text{Bernoulli}(0.8)$ and $Q=\text{Bernoulli}(0.5)$ is:

$D(P\Vert Q)=0.8{\log }_2(0.8/0.5)+0.2{\log }_2(0.2/0.5)$

Compute each piece. The first term: $0.8\times {\log }_2(1.6)=0.8\times 0.678=0.542$ bits. The second term: $0.2\times {\log }_2(0.4)=0.2\times (-1.322)=-0.264$ bits. Adding them: $D(P\Vert Q)=0.542-0.264=0.278$ bits.

By Stein's lemma, if you hold the false-alarm probability below 5 percent, the miss probability decays as roughly $2^{-0.278n}$. For $n=10$ bulbs, the miss probability is about $2^{-2.78}\approx 0.15$. For $n=20$ bulbs, it drops to about $2^{-5.56}\approx 0.02$. For $n=30$ bulbs, about $2^{-8.34}\approx 0.003$.

With just 30 bulbs, you can distinguish the good machine from the faulty one with miss probability below half a percent while keeping false alarms below 5 percent. The exponent 0.278 bits per sample governs the entire scaling.

Notice the asymmetry. If you swap roles and treat the faulty machine as the null hypothesis, the exponent becomes $D(Q\Vert P)=0.5{\log }_2(0.5/0.8)+0.5{\log }_2(0.5/0.2)=0.5\times (-0.678)+0.5\times 1.322=0.322$ bits. The error decays faster when the alternative is more concentrated (the faulty machine is easier to reject when it is the null).

Check your understanding Beginner

Formal definition Intermediate+

Let $\mathcal{X}$ be a finite alphabet. Let $P$ and $Q$ be two probability distributions on $\mathcal{X}$ with $P\ll Q$ (i.e., $Q(x)=0⟹P(x)=0$). Consider $n$ independent and identically distributed draws $X_1,X_2,\dots ,X_n$ from either $P$ (the null hypothesis $H_0$) or $Q$ (the alternative hypothesis $H_1$).

Definition (Binary hypothesis test). A (possibly randomised) test is a function ${\varphi }_n:{\mathcal{X}}^n\to [0,1]$, where ${\varphi }_n(x^n)$ is the probability of rejecting $H_0$ (accepting $H_1$) after observing the sequence $x^n=(x_1,\dots ,x_n)$.

Definition (Type I and Type II errors). The type I error (false alarm, size) and type II error (miss probability) are:

$${\alpha }_n=P^n({\varphi }_n=1)=\sum _{x^n\in {\mathcal{X}}^n}{P}^n(x^n){\varphi }_n(x^n),$$ $${\beta }_n=Q^n({\varphi }_n=0)=\sum _{x^n\in {\mathcal{X}}^n}{Q}^n(x^n)(1-{\varphi }_n(x^n)).$$

The type I error is the probability of wrongly declaring $H_1$ when $H_0$ is true. The type II error is the probability of wrongly declaring $H_0$ when $H_1$ is true.

Definition (Likelihood ratio test). For a threshold $T>0$, the likelihood ratio test rejects $H_0$ when the ratio of densities exceeds the threshold:

$${\varphi }_n(x^n)=\{\begin{array}{ll}1& \text{if }\frac{P^n(x^n)}{Q^n(x^n)}<T\\ \gamma & \text{if }\frac{P^n(x^n)}{Q^n(x^n)}=T\\ 0& \text{if }\frac{P^n(x^n)}{Q^n(x^n)}>T\end{array}$$

where $\gamma \in [0,1]$ is a randomisation parameter chosen to achieve exact size $\alpha$.

Definition (Error exponent). For a sequence of tests $\{{\varphi }_n\}$ with type I errors ${\alpha }_n\le ϵ$ for all $n$, the type II error exponent is:

$$E=-\underset{n\to \infty }{\mathrm{limsup}}\frac{1}{n}\log {\beta }_n,$$

when the limit exists. This is the exponential rate at which the type II error vanishes.

Counterexamples to common slips

• The exponent is $D(P\Vert Q)$, not $D(Q\Vert P)$. Stein's lemma is asymmetric. The exponent uses the divergence from the null to the alternative. Swapping hypotheses changes the exponent.

• Stein's lemma does not say both errors vanish simultaneously. It fixes the type I error below $ϵ$ and then gives the type II exponent. If you need both errors to vanish at the same rate, the exponent is the Chernoff information, which is smaller than either directional divergence.

• The alphabet must be finite (or the distributions must satisfy regularity conditions). For continuous distributions, Stein's lemma holds under appropriate conditions on the densities, but the proof requires more care with measure-theoretic details.

Key theorem with proof Intermediate+

Theorem (Stein's lemma). Let $P$ and $Q$ be two probability distributions on a finite alphabet $\mathcal{X}$ with $D(P\Vert Q)<\infty$. For any $0<ϵ<1$:

$$\underset{n\to \infty }{\lim }\frac{1}{n}\log \frac{1}{{\beta }_n^{\ast }(ϵ)}=D(P\Vert Q),$$

where ${\beta }_n^{\ast }(ϵ)={\min }_{{\varphi }_n:{\alpha }_n\le ϵ}{\beta }_n$ is the minimum achievable type II error among all tests of size at most $ϵ$.

Equivalently, for any $\delta >0$ and all sufficiently large $n$, the best type II error satisfies:

$$2^{-n(D(P\Vert Q)+\delta )}\le {\beta }_n^{\ast }(ϵ)\le 2^{-n(D(P\Vert Q)-\delta )}.$$

Proof sketch (direct part — achievability). We construct a test that achieves the exponent. The idea is to accept $H_0$ when the empirical distribution (type) of the observed sequence is "close" to $P$ and reject otherwise.

Define the acceptance region:

$$A_n=\left\{x^n\in {\mathcal{X}}^n:\frac{1}{n}\log \frac{P^n(x^n)}{Q^n(x^n)}\ge D(P\Vert Q)-\delta \right\}$$

for a small $\delta >0$. The log-likelihood ratio per sample is:

$$\frac{1}{n}\log \frac{P^n(x^n)}{Q^n(x^n)}=\frac{1}{n}\sum _{i=1}^n\log \frac{P(x_i)}{Q(x_i)}.$$

Under $P$, each term $\log (P(X_i)/Q(X_i))$ has expected value $D(P\Vert Q)$ and finite variance. By the law of large numbers, the average converges to $D(P\Vert Q)$ in probability. Therefore $P^n(A_n)\to 1$, which means the type I error ${\alpha }_n=1-P^n(A_n)\to 0<ϵ$ for all sufficiently large $n$.

The type II error under $Q$ is:

$${\beta }_n=Q^n(A_n)=Q^n\left(\frac{1}{n}\log \frac{P^n}{Q^n}\ge D(P\Vert Q)-\delta \right).$$

We bound this using the large-deviations upper bound. For any $s>0$:

$$Q^n(A_n)\le \sum _{x^n\in A_n}{Q}^n(x^n)\le \sum _{x^n\in A_n}{P}^n(x^n)\cdot 2^{-n(D(P\Vert Q)-\delta )}\le 2^{-n(D(P\Vert Q)-\delta )}.$$

Hence ${\beta }_n\le 2^{-n(D(P\Vert Q)-\delta )}$, achieving the exponent.

Proof sketch (converse — optimality). For the converse, we show that no test can do better. Suppose a test ${\varphi }_n$ has ${\alpha }_n\le ϵ$. Then:

$$1-ϵ\le P^n({\varphi }_n=0)=\sum _{x^n:{\varphi }_n(x^n)=0}{P}^n(x^n).$$

For any $x^n$ with ${\varphi }_n(x^n)=0$:

$$P^n(x^n)=Q^n(x^n)\cdot \frac{P^n(x^n)}{Q^n(x^n)}=Q^n(x^n)\cdot 2^{n\cdot \frac{1}{n}\log \frac{P^n(x^n)}{Q^n(x^n)}}.$$

The type II error is ${\beta }_n=Q^n({\varphi }_n=0)$. Using the method of types or large deviations, one can show that the dominant contribution to ${\beta }_n$ comes from sequences whose log-likelihood ratio is near $D(P\Vert Q)$, and no test can make ${\beta }_n$ vanish faster than $2^{-nD(P\Vert Q)}$. The formal argument uses the fact that for any test with bounded type I error:

$${\beta }_n\ge 2^{-n(D(P\Vert Q)+\delta )}$$

for any $\delta >0$ and all large enough $n$, because the set $\{{\varphi }_n=0\}$ must carry probability at least $1-ϵ$ under $P$, and the cheapest way (in $Q$-probability) to cover such a set is to use the $Q$-probability mass in regions where $P/Q$ is largest, which corresponds to the region near the exponent $D(P\Vert Q)$. $\square$

Bridge. Stein's lemma builds toward the large-deviations framework of Sanov's theorem 37.07.05, where the KL divergence appears as the rate function governing the exponential rarity of atypical empirical distributions; it appears again in channel coding 46.03.01 as the reliability function of the channel, where the error exponent for decoding is governed by a divergence between the output distributions induced by different codewords. The foundational reason Stein's lemma works is that the log-likelihood ratio $\log (P/Q)$ is a sum of i.i.d. random variables under both hypotheses, so the law of large numbers drives it to $D(P\Vert Q)$ under $P$ and to $-D(Q\Vert P)$ under $Q$, creating an exponentially growing gap between the two distributions on their typical sets. This is exactly the mechanism behind the Neyman-Pearson optimality of the likelihood-ratio test 45.02.01 — the NP lemma tells you the test structure is optimal, and Stein's lemma tells you the asymptotic rate at which that optimal test drives the error to zero. The central insight generalises to multiple hypotheses, composite hypotheses, and the Chernoff information for symmetric errors.

Exercises Intermediate+

Lean formalization Intermediate+

Mathlib does not define hypothesis tests on discrete distributions, nor does it provide the error-probability functionals that Stein's lemma requires. The PMF type for probability mass functions exists, and basic properties of the KL divergence on PMF could in principle be developed, but no such development is present. Specifically, Mathlib lacks: a TestFunction type mapping sequences to $[0,1]$, type I and type II error definitions as sums over acceptance/rejection regions, the likelihood-ratio decision rule with threshold and randomisation, and any asymptotic result about error exponents. The Chernoff information — the tilted-sum minimisation over $s\in [0,1]$ — and its relation to the symmetric error exponent are unformalised. A Codex.InformationTheory.SteinLemma module would need to build the test framework on PMF, prove the LLN for the per-sample log-likelihood ratio, and then establish the achievability and converse bounds that constitute Stein's lemma. This unit ships without formalization.

Advanced results Master

The Neyman-Pearson lemma as the finite-sample foundation

Stein's lemma is the asymptotic shadow of the Neyman-Pearson lemma 45.02.01. The NP lemma states that for testing $H_0:P$ against $H_1:Q$ based on $n$ observations, the likelihood-ratio test that rejects when $P^n(x^n)/Q^n(x^n)\le T$ (with randomisation on the boundary) is the unique most powerful test of its size. This is a finite-sample result: it holds for every $n$, not just asymptotically.

The NP lemma gives Stein's lemma because the LR test is optimal at every $n$, so the best achievable type II error ${\beta }_n^{\ast }(ϵ)$ is exactly the type II error of the LR test. The asymptotic behaviour of ${\beta }_n^{\ast }(ϵ)$ is then determined by the large-deviations properties of the log-likelihood ratio under $Q$. Specifically, the acceptance region $A_n=\{P^n/Q^n\ge T_n\}$ satisfies $Q^n(A_n)\doteq 2^{-nD(P\Vert Q)}$ because the log-likelihood ratio concentrates around its $P$-mean $D(P\Vert Q)$, and the $Q$-probability of the region where $P/Q$ is large is exponentially small with rate $D(P\Vert Q)$.

Chernoff information and the symmetric error exponent

Stein's lemma fixes the type I error and gives the type II exponent. A different question asks for the best symmetric error exponent: if both errors must vanish at the same rate, what is the optimal exponent?

Definition (Chernoff information). The Chernoff information between $P$ and $Q$ is:

$$C(P,Q)=-\underset{0\le s\le 1}{\min }\log \sum _{x\in \mathcal{X}}P(x{)}^{1-s}Q(x{)}^s.$$

The function $M(s)={\sum }_{x}P(x{)}^{1-s}Q(x{)}^s$ is the moment-generating function of the log-likelihood ratio evaluated at $s$. It is convex in $s$, with $M(0)=M(1)=1$, so $-\log M(s)\ge 0$ for all $s\in [0,1]$ and the minimum of $-\log M(s)$ is achieved at a unique interior point $s^{\ast }$ (unless $P=Q$, in which case $C=0$).

Theorem (Chernoff, 1952). For testing $H_0:P$ vs $H_1:Q$ with equal prior weights ${\pi }_0={\pi }_1=1/2$, the minimum Bayes error satisfies:

$$P_e^{\ast }(n)=\underset{\varphi }{\min }\frac{1}{2}({\alpha }_n+{\beta }_n)\doteq 2^{-nC(P,Q)},$$

where $\doteq$ denotes equality to first order in the exponent.

The Chernoff information satisfies $C(P,Q)\le \min (D(P\Vert Q),D(Q\Vert P))$ because the symmetric constraint is stronger than fixing one error. It equals $D(P\Vert Q)/2$ when the tilted distribution $P_{s^{\ast }}$ is equidistant from $P$ and $Q$ in divergence, which occurs when the log-likelihood ratio has a symmetric distribution under the tilted measure.

Worked example: for $P=\text{Bernoulli}(0.5)$ and $Q=\text{Bernoulli}(0.7)$, the Chernoff information is approximately $C\approx 0.108$ nats $\approx 0.156$ bits. Compare with $D(P\Vert Q)\approx 0.119$ nats and $D(Q\Vert P)\approx 0.119$ nats. The Chernoff information is smaller than both, reflecting the cost of the symmetric constraint.

The Bayesian formulation

Consider a Bayesian setting with prior probabilities ${\pi }_0$ and ${\pi }_1=1-{\pi }_0$. The Bayes error is:

$$P_e^B(n)=\underset{\varphi }{\min }[{\pi }_0{\alpha }_n+{\pi }_1{\beta }_n].$$

The optimal test is the Bayes rule: reject when ${\pi }_0{P}^n(x^n)<{\pi }_1{Q}^n(x^n)$, i.e., when the likelihood ratio exceeds the prior odds ${\pi }_0/{\pi }_1$. The error exponent is:

$$-\underset{n\to \infty }{\lim }\frac{1}{n}\log P_e^B(n)=C(P,Q),$$

regardless of the prior weights (as long as ${\pi }_0,{\pi }_1>0$). The prior affects the pre-factor but not the exponent. This is because the dominant contribution to the error comes from the "confused" region where $P$ and $Q$ look similar, and the cost of this confusion is governed by the Chernoff information.

When the prior weights are unequal (${\pi }_0\gg {\pi }_1$, say), the Bayes test thresholds at a very high likelihood ratio, which reduces type I error at the cost of type II error. The exponent remains $C(P,Q)$, but the pre-factor shifts: the type II error dominates, and the overall error is approximately ${\pi }_1\cdot 2^{-nC(P,Q)}$.

Relation to large deviations and Sanov's theorem

Stein's lemma is a special case of Sanov's theorem 37.07.05. Sanov's theorem states that the probability of seeing an empirical distribution (type) in a set $E$ under i.i.d. sampling from $P$ is:

$$P^n(\text{type}\in E)\doteq 2^{-nD(P^{\ast }\Vert P)},$$

where $P^{\ast }$ is the distribution in the closure of $E$ closest to $P$ in KL divergence.

For hypothesis testing, the acceptance region $A_n$ consists of sequences whose types lie in a set $E_n$ of "P-like" types. The type II error $Q^n(A_n)$ is the $Q$-probability of seeing a type in $E_n$, which by Sanov is approximately $2^{-nD(P^{\ast }\Vert Q)}$ where $P^{\ast }$ is the closest type in $E_n$ to $Q$. As $n$ grows and the type class refinement increases, $P^{\ast }$ converges to $P$, and the exponent converges to $D(P\Vert Q)$.

The method of types provides an alternative proof of Stein's lemma that avoids the LLN-based argument. The type class $T(P^{\prime })$ of a distribution $P^{\prime }$ has $P^n$-probability approximately $2^{-nD(P^{\prime }\Vert P)}$ by the method of types. The acceptance region is a union of type classes close to $P$, and the total $Q$-probability is the sum over these type classes, each contributing approximately $2^{-nD(P^{\prime }\Vert Q)}$. The dominant type class is the one minimising $D(P^{\prime }\Vert Q)$ subject to $D(P^{\prime }\Vert P)\le \delta$, which gives $P^{\prime }\approx P$ and the exponent $D(P\Vert Q)$.

Synthesis. Stein's lemma is the foundational result that gives the KL divergence its operational meaning as an error exponent: the best achievable type II error rate under a fixed type I constraint is $D(P\Vert Q)$. The bridge is that the Neyman-Pearson lemma determines the test structure (likelihood ratio threshold) and Stein's lemma determines the asymptotic rate (exponential decay with exponent $D(P\Vert Q)$). The Chernoff information generalises this to the symmetric setting, where both errors must vanish simultaneously, and satisfies $C(P,Q)\le D(P\Vert Q)$ because the symmetric constraint is stronger. The central insight builds toward large deviations 37.07.05, where Sanov's theorem shows that the KL divergence is the universal rate function for the rarity of atypical events. This generalises to composite hypotheses, sequential testing, and channel coding, where the error exponent is the divergence between output distributions induced by different messages.

Full proof set Master

Proposition (Data-processing inequality for hypothesis testing). Let $P$ and $Q$ be distributions on $\mathcal{X}$, and let $f:\mathcal{X}\to \mathcal{Y}$ be a deterministic function. Then the optimal type II error based on $n$ observations of $f(X)$ is at least the optimal type II error based on $n$ direct observations of $X$, for any type I constraint.

Proof. Let $P_f=f_{\ast }P$ and $Q_f=f_{\ast }Q$ be the pushforward distributions on $\mathcal{Y}$. Any test $\psi :{\mathcal{Y}}^n\to [0,1]$ on the processed data induces a test $\varphi =\psi \circ f^n:{\mathcal{X}}^n\to [0,1]$ on the raw data with the same type I and type II errors:

$${\alpha }_{\varphi }=P^n(\varphi =1)=P_f^n(\psi =1)={\alpha }_{\psi },$$ $${\beta }_{\varphi }=Q^n(\varphi =0)=Q_f^n(\psi =0)={\beta }_{\psi }.$$

Therefore the set of achievable $(\alpha ,\beta )$ pairs based on $f(X)$ is contained in the set of achievable pairs based on $X$: every test on processed data is also a test on raw data, but not conversely. The optimal type II error based on $f(X)$ is at least as large as the optimal type II error based on $X$:

$${\beta }_n^{\ast ,f}(ϵ)=\underset{\psi :{\alpha }_{\psi }\le ϵ}{\min }{\beta }_{\psi }\ge \underset{\varphi :{\alpha }_{\varphi }\le ϵ}{\min }{\beta }_{\varphi }={\beta }_n^{\ast }(ϵ).$$

By the data-processing inequality for KL divergence, $D(P_f\Vert Q_f)\le D(P\Vert Q)$, so processing reduces both the divergence and the achievable error exponent. $\square$

Proposition (Stein's lemma via the method of types). Let $P$ and $Q$ be distributions on a finite alphabet $\mathcal{X}$ with $D(P\Vert Q)<\infty$. For any $0<ϵ<1$:

$${\beta }_n^{\ast }(ϵ)\doteq 2^{-nD(P\Vert Q)}.$$

Proof (achievability). The set of types (empirical distributions) achievable with $n$ samples from $\mathcal{X}$ is ${\mathcal{P}}_n=\{P^{\prime }:\text{support}(P^{\prime })\subseteq \mathcal{X},n{P}^{\prime }(x)\in \mathbb{Z}\text{ for all }x\}$. For each type $P^{\prime }$, the type class $T(P^{\prime })$ (the set of sequences with empirical distribution $P^{\prime }$) has:

$$|T(P^{\prime })|=2^{nH(P^{\prime })}(1+o(1)),P^n(T(P^{\prime }))=2^{-nD(P^{\prime }\Vert P)}(1+o(1)),$$

by the method of types 46.02.01.

Define the acceptance region as $A_n={\bigcup }_{P^{\prime }\in E_n}T(P^{\prime })$ where:

$$E_n=\{P^{\prime }\in {\mathcal{P}}_n:D(P^{\prime }\Vert P)<\eta \}$$

for small $\eta >0$. Then $P^n(A_n)={\sum }_{P^{\prime }\in E_n}{2}^{-nD(P^{\prime }\Vert P)}(1+o(1))\ge 2^{-n\eta }\cdot |E_n|\cdot (1+o(1))$. Since $|E_n|$ grows polynomially in $n$ and $\eta$ is small, $P^n(A_n)\to 1$, so ${\alpha }_n<ϵ$ for large $n$.

The type II error is:

$${\beta }_n=Q^n(A_n)=\sum _{P^{\prime }\in E_n}{Q}^n(T(P^{\prime }))=\sum _{P^{\prime }\in E_n}{2}^{-nD(P^{\prime }\Vert Q)}(1+o(1)).$$

Since $D(P^{\prime }\Vert Q)$ is continuous and $E_n$ consists of types close to $P$, the minimum of $D(P^{\prime }\Vert Q)$ over $E_n$ is approximately $D(P\Vert Q)$. The sum is dominated by the smallest exponent:

$${\beta }_n\le (\text{poly}(n))\cdot 2^{-n(D(P\Vert Q)-\eta )}=2^{-n(D(P\Vert Q)-\eta +o(1))}.$$

Since $\eta$ is arbitrary, the achievability direction gives ${\beta }_n\le 2^{-n(D(P\Vert Q)-\delta )}$ for any $\delta >0$ and large $n$.

Proof (converse). For any test with ${\alpha }_n\le ϵ$, the acceptance region $A_n$ satisfies $P^n(A_n)\ge 1-ϵ$. Write $A_n={\bigcup }_{P^{\prime }\in F_n}T(P^{\prime })$ for some set of types $F_n$. Then:

$$1-ϵ\le P^n(A_n)=\sum _{P^{\prime }\in F_n}{2}^{-nD(P^{\prime }\Vert P)}(1+o(1))\le |F_n|\cdot 2^{-n{\min }_{P^{\prime }\in F_n}D(P^{\prime }\Vert P)}.$$

For this to hold for large $n$, we need ${\min }_{P^{\prime }\in F_n}D(P^{\prime }\Vert P)\le \delta$ for any $\delta >0$, meaning $F_n$ contains types arbitrarily close to $P$.

The type II error is:

$${\beta }_n=Q^n(A_n)=\sum _{P^{\prime }\in F_n}{2}^{-nD(P^{\prime }\Vert Q)}(1+o(1))\ge 2^{-nD(P^{\ast }\Vert Q)}(1+o(1)),$$

where $P^{\ast }=\arg {\min }_{P^{\prime }\in F_n}D(P^{\prime }\Vert Q)$. Since $F_n$ must contain types close to $P$ (from the type I constraint), $P^{\ast }$ is close to $P$, and $D(P^{\ast }\Vert Q)\le D(P\Vert Q)+\delta$. Therefore ${\beta }_n\ge 2^{-n(D(P\Vert Q)+\delta )}$ for any $\delta >0$ and large $n$. $\square$

Proposition (Chernoff information as the symmetric exponent). For testing $H_0:P$ vs $H_1:Q$ with equal priors, the minimum Bayes error satisfies:

$$-\underset{n\to \infty }{\lim }\frac{1}{n}\log P_e^{\ast }(n)=C(P,Q)=-\underset{0\le s\le 1}{\min }\log M(s),$$

where $M(s)={\sum }_{x}P(x{)}^{1-s}Q(x{)}^s$.

Proof sketch. The Bayes error for prior $({\pi }_0,{\pi }_1)$ is:

$$P_e^{\ast }(n)=\sum _{x^n}\min ({\pi }_0{P}^n(x^n),{\pi }_1{Q}^n(x^n)).$$

By the inequality $\min (a,b)\le a^{1-s}{b}^s$ for any $s\in [0,1]$:

$$P_e^{\ast }(n)\le \sum _{x^n}({\pi }_0{P}^n(x^n){)}^{1-s}({\pi }_1{Q}^n(x^n){)}^s={\pi }_0^{1-s}{\pi }_1^s{\left(\sum _{x}P(x{)}^{1-s}Q(x{)}^s\right)}^n.$$

Taking logs and minimising over $s$:

$$-\frac{1}{n}\log P_e^{\ast }(n)\ge -\log M(s^{\ast })+\frac{1-s^{\ast }}{n}\log \frac{1}{{\pi }_0}+\frac{s^{\ast }}{n}\log \frac{1}{{\pi }_1}\to C(P,Q).$$

For the converse, the optimal test is the Bayes rule with threshold at the prior odds. The error is bounded below by the contribution from the "ambiguous" region where $P/Q\approx {\pi }_1/{\pi }_0$, and this region has $Q$-probability approximately $2^{-nC(P,Q)}$ by the large-deviations analysis of the tilted distribution. $\square$

Connections Master

• 46.01.02 — The KL divergence $D(P\Vert Q)$ defined there is the error exponent in Stein's lemma; this unit gives it its first operational interpretation as the exponential rate of type II error decay in hypothesis testing.
• 45.02.01 — The Neyman-Pearson lemma establishes that the likelihood-ratio test is the unique most powerful test at every sample size $n$; Stein's lemma is the asymptotic ($n\to \infty$) consequence of NP optimality.
• 37.07.05 — Sanov's theorem in large deviations shows that the KL divergence is the universal rate function for the rarity of atypical empirical distributions; Stein's lemma is the specialisation to the hypothesis-testing setting.
• 46.02.01 — The AEP and typical sets provide the structural foundation: the $P$-typical set and $Q$-typical set diverge exponentially, and the divergence rate is $D(P\Vert Q)$.
• 46.03.01 — Channel coding reliability: the error exponent for decoding over a noisy channel is governed by divergences between output distributions induced by different codewords, generalising the hypothesis-testing framework.
• 46.04.02 — The method of types and large deviations for information theory builds directly on the type-class analysis used in the proof of Stein's lemma.

Historical & philosophical context Master

Herman Chernoff introduced the Chernoff information in his 1952 paper "A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the Sum of Observations" (Annals of Mathematical Statistics 23, 493-507). Chernoff was working on the problem of sequential analysis, where the sample size is not fixed in advance but depends on the observations. He identified the best achievable symmetric error exponent as the minimum of the moment-generating function of the log-likelihood ratio, a quantity now known as the Chernoff information. The result unified the Bayesian and frequentist approaches to hypothesis testing by showing that the exponent is the same regardless of the prior weights.

Herman Chernoff and Louis LeCam independently developed the large-deviations approach to hypothesis testing in the 1950s and 1960s. The connection to information theory was made explicit by Thomas Cover in his 1973 paper "Enumerative Source Encoding" (IEEE Transactions on Information Theory 19, 73-77), which used the method of types to give information-theoretic proofs of large-deviations results. Cover and Thomas's 1991 textbook "Elements of Information Theory" (Wiley) synthesised these connections in Chapter 12 (Chapter 11 in the 2006 second edition), where hypothesis testing appears as a direct application of the AEP and typical sets.

The Stein lemma itself is attributed to Herman Chernoff's 1952 paper, though the specific name "Stein's lemma" appears to have entered the information-theory literature through the lecture notes of Edward Thomas (a student of Cover). The result is a special case of the more general large-deviations principle: the probability of a large deviation under one measure, as measured by another, decays at a rate given by the KL divergence. This principle underpins Sanov's theorem, the Gärtner-Ellis theorem, and the contraction principle in large deviations, all of which appear in 37.07.05.

The philosophical significance is that the KL divergence — a quantity that appears unnatural at first glance (it is not symmetric, not a metric, and does not satisfy the triangle inequality) — has a natural operational meaning as the rate at which one distribution becomes distinguishable from another. This operational interpretation justifies the divergence's central role in information theory, statistics, and machine learning.

Bibliography Master

@article{chernoff1952,
  author  = {Chernoff, H.},
  title   = {A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the Sum of Observations},
  journal = {Annals of Mathematical Statistics},
  volume  = {23},
  pages   = {493--507},
  year    = {1952},
}
@book{cover-thomas2006,
  author    = {Cover, T. M. and Thomas, J. A.},
  title     = {Elements of Information Theory},
  edition   = {2nd},
  publisher = {Wiley},
  year      = {2006},
}
@book{csiszar-korner2011,
  author    = {Csisz{\'a}r, I. and K{\"o}rner, J.},
  title     = {Information Theory: Coding Theorems for Discrete Memoryless Systems},
  edition   = {2nd},
  publisher = {Cambridge University Press},
  year      = {2011},
}
@book{lehmann-romano2005,
  author    = {Lehmann, E. L. and Romano, J. P.},
  title     = {Testing Statistical Hypotheses},
  edition   = {3rd},
  publisher = {Springer},
  year      = {2005},
}
@article{cover1973,
  author  = {Cover, T. M.},
  title   = {Enumerative Source Encoding},
  journal = {IEEE Transactions on Information Theory},
  volume  = {19},
  pages   = {73--77},
  year    = {1973},
}
@book{dembo-zeitouni1998,
  author    = {Dembo, A. and Zeitouni, O.},
  title     = {Large Deviations Techniques and Applications},
  edition   = {2nd},
  publisher = {Springer},
  year      = {1998},
}