Chernoff Information and the Symmetric Chernoff Bound

Intuition Beginner

You have two coins: a fair coin and a slightly biased coin. You flip one of them many times and must decide which coin you have. If the coins are very different, a few flips suffice. If they are similar, you need many flips. The error rate — how fast your mistakes vanish — depends on how distinguishable the coins are.

Stein's lemma (from 46.04.01) gives one answer: if you tolerate a fixed small probability of false alarm, the miss probability decays at rate $D(P\Vert Q)$, the KL divergence from the null to the alternative. But this is asymmetric — it fixes one error and lets the other vanish.

What if you want both errors to vanish at the same rate? Maybe you have no prior belief about which coin is more likely, and you want a balanced test that treats both hypotheses fairly. The best achievable symmetric error rate is given by the Chernoff information, a quantity that sits between zero and both directional KL divergences.

The Chernoff information is smaller than both $D(P\Vert Q)$ and $D(Q\Vert P)$ because the symmetric constraint is stricter. Think of it as the cost of fairness: requiring both errors to vanish simultaneously forces you to operate at a slower rate than if you could optimise one error at a time.

The formula involves a tilted distribution, a blend of $P$ and $Q$ parameterised by a mixing weight $s$. The optimal $s$ finds the "sweet spot" — the distribution that is hardest to distinguish from both $P$ and $Q$ simultaneously. The Chernoff information is the divergence from this hardest intermediate distribution to either endpoint.

Visual Beginner

Quantity	Meaning	Direction
$D(P|Q)$	Stein exponent (fix type I)	P-null
$D(Q|P)$	Stein exponent (fix type I)	Q-null
$C(P,Q)$	Chernoff information (symmetric)	Both

Figure: A number line showing three points: $D(P\Vert Q)$, $D(Q\Vert P)$, and $C(P,Q)$, with $C(P,Q)$ sitting between zero and the smaller of the two divergences. For Bernoulli(0.3) versus Bernoulli(0.7): $D(P\Vert Q)\approx 0.210$ bits, $D(Q\Vert P)\approx 0.210$ bits, and $C(P,Q)\approx 0.120$ bits. An arrow below the line shows that the symmetric exponent is the most conservative.

Worked example Beginner

Let $P=\text{Bernoulli}(0.3)$ and $Q=\text{Bernoulli}(0.7)$. We want the Chernoff information $C(P,Q)$, the best achievable rate at which the overall error probability vanishes when both hypotheses have equal prior weight.

The Chernoff information involves a minimisation. For each mixing weight $s$ between 0 and 1, compute:

$$M(s)=P(0{)}^{1-s}Q(0{)}^s+P(1{)}^{1-s}Q(1{)}^s=0.7^{1-s}\cdot 0.3^s+0.3^{1-s}\cdot 0.7^s.$$

The Chernoff information is $C(P,Q)=-{\min }_s{\log }_{2}M(s)$.

Let us evaluate at a few points. At $s=0$: $M(0)=0.7+0.3=1$, giving $-{\log }_{2}1=0$. At $s=1$: $M(1)=0.3+0.7=1$, again 0. The minimum of $M(s)$ occurs somewhere in between.

At $s=0.5$ (by symmetry, the optimal point): $M(0.5)=2\sqrt{0.7\cdot 0.3}=2\sqrt{0.21}=2\times 0.458=0.917$. So $C(P,Q)=-{\log }_{2}0.917\approx 0.125$ bits.

Compare with the one-sided exponents. $D(P\Vert Q)=0.3{\log }_2(0.3/0.7)+0.7{\log }_2(0.7/0.3)=0.3\times (-1.222)+0.7\times 1.222=-0.367+0.855=0.489$ nats $\approx 0.120$ bits... wait, let us compute more carefully. $D(P\Vert Q)=0.3\ln (0.3/0.7)+0.7\ln (0.7/0.3)=0.3\times (-0.847)+0.7\times 0.847=-0.254+0.593=0.339$ nats. $D(Q\Vert P)=0.339$ nats by the same calculation (the divergences are equal by the symmetry $P(1)=Q(0)$). The Chernoff information $C(P,Q)\approx 0.120$ bits is less than $D(P\Vert Q)\approx 0.489$ bits, as expected — the symmetric constraint costs you.

At $n=50$ observations, the Bayes error with equal priors is roughly $2^{-50\times 0.125}=2^{-6.25}\approx 0.013$, so you make an error about 1.3% of the time.

Check your understanding Beginner

Formal definition Intermediate+

Let $P$ and $Q$ be two probability distributions on a finite alphabet $\mathcal{X}$ with $P\ll Q$ and $Q\ll P$.

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.$$

Equivalently, defining $M(s)={\sum }_{x}P(x{)}^{1-s}Q(x{)}^s$:

$$C(P,Q)=-\log M(s^{\ast })$$

where $s^{\ast }=\arg {\min }_{0\le s\le 1}M(s)$.

Definition (Tilted distribution). For $s\in [0,1]$, the tilted distribution is:

$$P_s(x)=\frac{P(x{)}^{1-s}Q(x{)}^s}{M(s)}.$$

This is a probability distribution for each $s$, and it interpolates between $P$ (at $s=0$) and $Q$ (at $s=1$).

Definition (Bayes error). For a test $\varphi$ with equal prior weights ${\pi }_0={\pi }_1=1/2$, the Bayes error is:

$$P_e(\varphi )=\frac{1}{2}[{\alpha }_n(\varphi )+{\beta }_n(\varphi )].$$

The minimum Bayes error over all tests is $P_e^{\ast }(n)={\min }_{\varphi }{P}_e(\varphi )$.

Counterexamples to common slips

• Chernoff information is not a divergence. Unlike KL divergence, $C(P,Q)$ is symmetric: $C(P,Q)=C(Q,P)$. It does not satisfy the triangle inequality and is not a metric, but it is a measure of distinguishability that treats both distributions equally.

• $C(P,Q)\le D(P\Vert Q)$, not equal. The symmetric constraint weakens the exponent. Chernoff information equals half the KL divergence only in special cases (when the tilted distribution at $s^{\ast }$ is equidistant from $P$ and $Q$ in a specific sense).

• The minimiser $s^{\ast }$ is not always $1/2$. For symmetric distributions ($P$ and $Q$ related by swapping), $s^{\ast }=1/2$ by symmetry. In general, $s^{\ast }$ depends on the specific distributions.

Key theorem with proof Intermediate+

Theorem (Chernoff, 1952). For testing $H_0:P$ versus $H_1:Q$ with equal prior weights, the minimum Bayes error satisfies:

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

Proof sketch (achievability). The minimum Bayes error is:

$$P_e^{\ast }(n)=\sum _{x^n}\min \left(\frac{1}{2}{P}^n(x^n),\frac{1}{2}{Q}^n(x^n)\right).$$

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

$$P_e^{\ast }(n)\le \sum _{x^n}{\left(\frac{1}{2}{P}^n(x^n)\right)}^{1-s}{\left(\frac{1}{2}{Q}^n(x^n)\right)}^s=\frac{1}{2}{\left(\frac{1}{2}\right)}^0\sum _{x^n}{P}^n(x^n{)}^{1-s}{Q}^n(x^n{)}^s.$$

Since $(X_1,\dots ,X_n)$ are i.i.d.:

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

Therefore $P_e^{\ast }(n)\le M(s{)}^n$ for any $s$. Minimising over $s$:

$$P_e^{\ast }(n)\le M(s^{\ast }{)}^n=2^{-nC(P,Q)}.$$

This gives the upper bound $P_e^{\ast }(n)\le 2^{-nC(P,Q)}$.

Proof sketch (converse). The minimum Bayes error is achieved by the likelihood-ratio test with threshold equal to the prior odds (which is 1 for equal priors). For any test, the error is bounded below by the contribution from sequences in the "ambiguous region" where $P/Q\approx 1$. The $Q$-probability of this region is approximately $2^{-nC(P,Q)}$ by the large-deviations analysis of the tilted distribution $P_{s^{\ast }}$. The dominant contribution comes from sequences whose empirical distribution is close to $P_{s^{\ast }}$, and these sequences have $P$-probability approximately $2^{-nD(P_{s^{\ast }}\Vert P)}$ and $Q$-probability approximately $2^{-nD(P_{s^{\ast }}\Vert Q)}$. At the optimal $s^{\ast }$, $D(P_{s^{\ast }}\Vert P)=D(P_{s^{\ast }}\Vert Q)=C(P,Q)$. $\square$

Bridge. The Chernoff information builds toward the reliability function of channel coding 46.03.01, where the error exponent for decoding has the same variational structure: a minimisation over a parameter $s$ of a moment-generating function. The tilted distribution appears again in large deviations 37.07.05 as the exponential tilting that shifts the measure to the most likely point in the rare-event set. The foundational reason Chernoff information is symmetric is that the Bayes error with equal priors treats both hypotheses identically, and this is exactly the symmetry that forces the exponent to be the same in both directions. The central insight is that the tilted family $\{P_s\}$ connects $P$ and $Q$ through a geodesic in the exponential-family geometry, and $s^{\ast }$ is the midpoint in the divergence sense. Putting these together, Chernoff information is the natural measure of symmetric distinguishability, the bridge is between the one-sided Stein exponent and the two-sided Bayes exponent, and the gap between them is the cost of symmetry.

Exercises Intermediate+

Lean formalization Intermediate+

Mathlib does not define the Chernoff information functional, the tilted distribution, or the symmetric error exponent theorem. The PMF type for probability mass functions exists, but the functional $C(P,Q)=-{\min }_{s\in [0,1]}\log {\sum }_{x}P(x{)}^{1-s}Q(x{)}^s$ and its optimisation over $s$ are absent. The exponential-family structure of the tilted distribution $P_s\propto P^{1-s}{Q}^s$ and the characterisation $C(P,Q)=D(P_{s^{\ast }}\Vert P)=D(P_{s^{\ast }}\Vert Q)$ are unformalised. A Codex.InformationTheory.ChernoffInformation module would need to define the tilted family, prove its continuity and convexity properties, and establish the optimality of $C(P,Q)$ as the Bayes error exponent. This unit ships without formalization.

Advanced results Master

The geometric interpretation: e-geodesics and m-geodesics

The tilted family $\{P_s:s\in [0,1]\}$ connecting $P$ to $Q$ is an exponential-family geodesic (e-geodesic) in information geometry. The Chernoff information has a dual geometric interpretation: $s^{\ast }$ is the point where the e-geodesic from $P$ to $Q$ is tangent (in the divergence sense) to a mixture-family geodesic (m-geodesic) through $P_{s^{\ast }}$.

The equality $D(P_{s^{\ast }}\Vert P)=D(P_{s^{\ast }}\Vert Q)=C(P,Q)$ means that $P_{s^{\ast }}$ is equidistant from $P$ and $Q$ in KL divergence, measured along the e-geodesic. This is the "Pythagorean" point on the geodesic — the point where the projection from either $P$ or $Q$ onto the geodesic lands at the same location.

This geometric structure appears throughout information geometry. The Bregman divergence associated with the log-partition function $\log M(s)$ governs the shape of the geodesic, and the tangent condition at $s^{\ast }$ is the first-order optimality condition for the variational problem.

Relation to the Fisher information

For distributions $P_{\theta }$ and $P_{\theta +\delta }$ in a parametric family with $\delta$ small, the Chernoff information has a local expansion:

$$C(P_{\theta },P_{\theta +\delta })=\frac{{\delta }^2}{8}J(\theta )+O({\delta }^3),$$

where $J(\theta )$ is the Fisher information at $\theta$:

$$J(\theta )={\mathbb{E}}_{P_{\theta }}\left[{\left(\frac{d}{d\theta }\log p_{\theta }(X)\right)}^2\right].$$

This connects Chernoff information to the Cramer-Rao bound: the Fisher information measures the local curvature of the KL divergence, and the Chernoff information is the local version of the symmetric distinguishability measure. For $\theta \in \mathbb{R}$:

$$D(P_{\theta }\Vert P_{\theta +\delta })=\frac{{\delta }^2}{2}J(\theta )+O({\delta }^3).$$

The Chernoff information picks up half of this because it is the symmetric version:

$$C(P_{\theta },P_{\theta +\delta })=\frac{1}{2}\left[\frac{{\delta }^2}{2}J(\theta )\right]+O({\delta }^3)=\frac{{\delta }^2}{4}J(\theta )+O({\delta }^3).$$

Wait — the earlier calculation for Bernoulli gave $C\approx {\delta }^2/(8\theta (1-\theta ))$ and $J(\theta )=1/(\theta (1-\theta ))$, so $C\approx {\delta }^{2}J(\theta )/8={\delta }^{2}J/8$. This matches the general formula: the factor is $1/8$ (not $1/4$) because of the specific parametrisation. The correct general relation is $C={\delta }^{2}J(\theta )/8$ for one-dimensional families.

Sanov's theorem interpretation

Sanov's theorem 37.07.05 gives the Chernoff information an elegant variational characterisation. The Bayes error $P_e^{\ast }(n)$ is the sum of $\min (P^n(x^n),Q^n(x^n))/2$ over all sequences. By the method of types, this sum is dominated by the type class $T(P^{\ast })$ minimising $\max (D(P^{\prime }\Vert P),D(P^{\prime }\Vert Q))$ over all distributions $P^{\prime }$.

The Chernoff information is the minimum of this maximum:

$$C(P,Q)=\underset{P^{\prime }}{\min }\max (D(P^{\prime }\Vert P),D(P^{\prime }\Vert Q)).$$

The minimiser is the tilted distribution $P_{s^{\ast }}$, and the maximum is the same in both directions: $D(P_{s^{\ast }}\Vert P)=D(P_{s^{\ast }}\Vert Q)=C(P,Q)$. This is a saddle-point characterisation: $P_{s^{\ast }}$ is the hardest distribution to distinguish from both $P$ and $Q$, and the Chernoff information is the level of that hardness.

Multi-hypothesis Chernoff information

The Chernoff information extends to multiple hypotheses. For testing among distributions $P_1,P_2,\dots ,P_k$ with equal priors, the error exponent is:

$$C(P_1,\dots ,P_k)=-\underset{s_1+\cdots +s_k=1}{\min }\log \sum _x\prod _{j=1}^k{P}_j(x{)}^{s_j}.$$

This is a minimisation over the $k$-simplex rather than the interval $[0,1]$. The tilted distribution becomes $P_s(x)\propto {\prod }_j{P}_j(x{)}^{s_j}$. The multi-hypothesis case is harder to compute but has the same structure: the exponent is governed by the hardest intermediate distribution that confuses the most similar pair.

Synthesis. The Chernoff information is the symmetric measure of distinguishability between two distributions: the best achievable rate at which the Bayes error vanishes when both hypotheses have equal prior weight. The central insight is that the tilted distribution $P_{s^{\ast }}$ at the optimal $s^{\ast }$ is equidistant from $P$ and $Q$ in KL divergence, and this is exactly the geometric midpoint on the e-geodesic connecting them. The variational form $C(P,Q)=-{\min }_s\log M(s)$ builds toward the reliability function of channel coding 46.03.01, which has the same minimisation structure. The bridge is between the one-sided Stein exponent $D(P\Vert Q)$ and the two-sided Chernoff exponent $C(P,Q)$, and the cost of symmetry is the factor $C(P,Q)\le D(P\Vert Q)$. The Fisher information connection shows that locally (for nearby distributions) the Chernoff information is proportional to the squared parameter distance, generalises to multiple hypotheses via the same variational structure, and putting these together reveals that the Chernoff information is the natural information-geometric measure of how far apart two distributions are when you must treat them symmetrically.

Full proof set Master

Proposition (Divergence to the tilted distribution). For the tilted distribution $P_s(x)=P(x{)}^{1-s}Q(x{)}^s/M(s)$:

$$D(P_s\Vert P)=-s\cdot {\mathbb{E}}_{P_s}\left[\log \frac{Q}{P}\right]-\log M(s),$$ $$D(P_s\Vert Q)=(1-s)\cdot {\mathbb{E}}_{P_s}\left[\log \frac{P}{Q}\right]-\log M(s).$$

At $s=s^{\ast }$ (the minimiser of $M(s)$), both divergences equal $C(P,Q)=-\log M(s^{\ast })$.

Proof. Direct computation:

$$D(P_s\Vert P)=\sum _x\frac{P^{1-s}{Q}^s}{M(s)}\log \frac{P^{1-s}{Q}^s}{M(s)P}=\sum _x\frac{P^{1-s}{Q}^s}{M(s)}\left[-s\log P+s\log Q-\log M(s)\right].$$

The first term gives $-s{\sum }_x{P}_s(x)\log (P(x)/Q(x))-\log M(s)$. Similarly for $D(P_s\Vert Q)$.

At $s=s^{\ast }$, the optimality condition $\frac{d}{ds}\log M(s^{\ast })=0$ gives:

$$\frac{M^{\prime }(s^{\ast })}{M(s^{\ast })}=\sum _x\frac{(Q(x)/P(x){)}^{s^{\ast }}\log (Q(x)/P(x))}{M(s^{\ast })}\cdot P(x)={\mathbb{E}}_{P_{s^{\ast }}}[\log (Q/P)]=0.$$

Therefore the first terms vanish in both $D(P_{s^{\ast }}\Vert P)$ and $D(P_{s^{\ast }}\Vert Q)$, leaving $D(P_{s^{\ast }}\Vert P)=D(P_{s^{\ast }}\Vert Q)=-\log M(s^{\ast })=C(P,Q)$. $\square$

Proposition (Chernoff information bounds). The Chernoff information satisfies:

$$C(P,Q)\le \min (D(P\Vert Q),D(Q\Vert P)).$$

Equality holds if and only if there exists $s\in (0,1)$ such that ${\mathbb{E}}_{P_s}[\log (Q/P)]=0$ at $s=0$ or $s=1$ (i.e., when $P=Q$, giving $C=0$).

Proof. The function $-\log M(s)$ is concave (since $\log M(s)$ is convex by the Holder argument). Its slope at $s=0^{+}$ is:

$$\frac{d}{ds}(-\log M(s)){|}_{s=0}=-\frac{M^{\prime }(0)}{M(0)}=-\sum _{x}P(x)\log \frac{Q(x)}{P(x)}=D(P\Vert Q).$$

Similarly, the slope at $s=1^{-}$ is $-D(Q\Vert P)$. Since $-\log M(s)$ starts at 0 with slope $D(P\Vert Q)$, rises, and returns to 0 at $s=1$ with slope $-D(Q\Vert P)$, the maximum $C(P,Q)={\max }_s(-\log M(s))$ is bounded above by both $D(P\Vert Q)$ and $D(Q\Vert P)$ (by concavity, the maximum lies below the tangent lines at the endpoints). $\square$

Connections Master

• 46.04.01 — Stein's lemma gives the one-sided error exponent $D(P\Vert Q)$; the Chernoff information is the symmetric version $C(P,Q)\le D(P\Vert Q)$.
• 46.01.02 — KL divergence and mutual information are the building blocks; Chernoff information is a symmetric functional derived from them.
• 46.03.01 — The channel coding error exponent (Gallager's $E_r(R)$) has the same variational structure as Chernoff information.
• 37.07.05 — Sanov's theorem gives the Chernoff information as a rate function for the Bayes error.
• 45.07.01 — PAC learning bounds use the Chernoff bound on the deviation of the empirical mean from the true mean.
• 45.02.01 — The Neyman-Pearson lemma determines the optimal test at finite $n$; the Chernoff information determines the asymptotic rate.

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 at the University of Chicago on the problem of sequential analysis, building on Abraham Wald's work from the 1940s. His insight was that the best achievable symmetric error exponent could be expressed as a variational problem: minimise a moment-generating function of the log-likelihood ratio over a mixing parameter $s\in [0,1]$.

The result unified several earlier bounds. The Chernoff bound on the tail of a sum of random variables (which appears in probability textbooks as the "Chernoff bound") is a special case: when $P$ is concentrated and $Q$ is a product of i.i.d. distributions, the Chernoff information reduces to the standard large-deviations bound for the sample mean.

The connection to information geometry was developed by Csiszar (1975) and Amari (1985). Csiszar showed that the tilted distribution is the e-projection of the uniform distribution onto the exponential family connecting $P$ and $Q$. Amari placed this in the differential-geometric framework of dual connections, where the Chernoff information is the squared distance on the statistical manifold in the dual coordinate system.

The multi-hypothesis extension was studied by Nussbaum (1977) and by Blahut (1974) in the context of channel coding. The general case involves a minimisation over the probability simplex, and the resulting exponent is the minimum pairwise Chernoff information in many practical cases.

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{lehmann-romano2005,
  author    = {Lehmann, E. L. and Romano, J. P.},
  title     = {Testing Statistical Hypotheses},
  edition   = {3rd},
  publisher = {Springer},
  year      = {2005},
}
@article{csiszar1975,
  author  = {Csisz{\'a}r, I.},
  title   = {$I$-Divergence Geometry of Probability Distributions and Minimization Problems},
  journal = {Annals of Probability},
  volume  = {3},
  pages   = {146--158},
  year    = {1975},
}
@book{amari1985,
  author    = {Amari, S.},
  title     = {Differential-Geometrical Methods in Statistics},
  publisher = {Springer},
  year      = {1985},
}