Binary hypothesis testing in information theory

For two probability mass functions $P,Q$, a decision region $B_n$ accepts $P^{\otimes n}$. Its two error probabilities are $P^{\otimes n}(B_n^c)$ and $Q^{\otimes n}(B_n)$.

An error exponent is the limiting exponential decay rate of an error probability $p_n$ as sample size $n$ grows. Different constraints on the Type I error and Type II error give different optimal rates. The Chernoff information describes the optimal average-error rate for simple Bayesian hypotheses; Stein's lemma gives the optimal type-II rate when type-I error is held below a fixed nontrivial bound.

For a null hypothesis $H_0$, a Type I error rejects $H_0$ when it is true, while a Type II error accepts $H_0$ when the alternative is true. If a test accepts $H_0$ on an event $A$, their conditional probabilities are $\alpha =P_0(A^c)$ and $\beta =P_1(A)$.

Chernoff information measures how quickly repeated independent evidence can distinguish two fixed probability distributions. Suppose a statistical hypothesis test observes $n$ independent and identically distributed random variables, with common law $P$ under one simple hypothesis and $Q$ under the other. Give the two hypotheses fixed positive prior probabilities, and let $p_n^{\ast }$ be the smallest achievable average error probability. For distinct positive probability mass functions on a common finite alphabet,Here $\ln$ is the natural logarithm, so the error exponent is measured in nats per observation. This optimal rate is unchanged by choosing different fixed positive prior probabilities; the best decision rule and finite-sample error can still change.^[ref]

The interpretation is $p_n^{\ast }=\exp (-nC(P,Q)+o(n))$: a larger Chernoff information means fewer observations are needed at the leading exponential scale. It does not assert the exact finite-sample identity $p_n^{\ast }=e^{-nC(P,Q)}$. The finite-sample Chernoff error bound and the explicit Chernoff information for complementary Bernoulli distributions make this distinction concrete. This is useful when designing repeated measurements or comparing sensors whose output probability distributions differ under two candidate conditions.

For probability mass functions with zero entries, define the affinity for $0<s<1$ and use $C(P,Q)=-\ln {\inf }_{0<s<1}{\sum }_{x}P(x{)}^{s}Q(x{)}^{1-s}$, taking endpoint limits when needed. This avoids an ambiguous $0^0$ convention. Identical laws give $C=0$; disjoint probability supports give $C=\infty$, because one observation separates them perfectly. The displayed finite-rate theorem concerns fixed laws with common positive support, not laws that change with $n$ or arbitrarily dependent repeated observations.

For probability mass functions $P,Q$, their Chernoff affinity at $0<s<1$ is the sum $Z(s)={\sum }_{x}P(x{)}^{s}Q(x{)}^{1-s}$. It weights pointwise agreement between the two laws. The weighted arithmetic-geometric mean inequality gives $P(x{)}^{s}Q(x{)}^{1-s}\le sP(x)+(1-s)Q(x)$, hence $Z(s)\le 1$. With positive common support, $Z(0)=Z(1)=1$. Smaller affinity means a stronger separation at that weighting.

At $s=1/2$, $Z(1/2)={\sum }_x\sqrt{P(x)Q(x)}$ is the Bhattacharyya coefficient. The quantity $-\ln Z(1/2)$ is the Bhattacharyya distance. Allowing all weights $s$ gives Chernoff information at least this large. Symmetry under exchanging $P,Q$ sends $s$ to $1-s$, so Chernoff information is symmetric even though an optimizing weight need not be $1/2$.

For equal prior probabilities and independent and identically distributed observations on a finite alphabet, minimum sum of errors in a simple hypothesis test givesFor nonnegative $a,b$ and $0<s<1$, $\min (a,b)\le a^s{b}^{1-s}$. Applying this termwise and using the independence of random variables to factor the sum yieldsOptimizing $s$, with an infimum if needed, proves $p_n^{\ast }\le \frac{1}{2}{e}^{-nC(P,Q)}$. This short argument gives a bound for every $n$. The theorem identifying the optimal error exponent also needs the converse: no decision rule can achieve a strictly larger limiting exponent. A log-likelihood ratio is a sum of independent contributions, so large deviation principle supplies the relevant converse idea.

Let $P$ be the Bernoulli distribution with success probability $0.2$ and $Q$ the Bernoulli distribution with success probability $0.8$. For $0\le s\le 1$,The two summands have product $0.16$. Their arithmetic mean is at least their geometric mean, with equality at $s=1/2$. ThusThe same argument gives $C=-\ln (2\sqrt{p(1-p)})$ for complementary parameters $0<p<1$. At $p=1/2$ the laws agree and $C=0$.

With equal prior probabilities, count the successes $K$ among $n$ observations. The likelihood ratio is $Q^{\otimes n}/P^{\otimes n}=4^{2K-n}$, so choose $Q$ when $K>n/2$ and $P$ when $K<n/2$. If $n$ is even, either decision or a fair tie randomization gives the same average error at $K=n/2$. Under $P$, $K$ has the binomial distribution with parameters $n,0.2$. Symmetry therefore gives the exact optimal average errorThe last term applies only for even $n$; it represents half the tie probability. Direct finite sums give $p_1^{\ast }=0.2$, $p_5^{\ast }=0.05792$ and $p_{20}^{\ast }\simeq 0.00157912$. Twenty observations reduce the optimal average error to about 0.158%. The finite-sample Chernoff error bound at $n=20$ is $\frac{1}{2}(0.8{)}^{20}\simeq 0.00576461$, a guarantee rather than the exact error.

Reducing the exact error from $p_{20}^{\ast }$ to $p_{50}^{\ast }\simeq 1.29363\times 10^{-6}$ illustrates the value of repeated evidence. The example assumes a single fixed coin law throughout the experiment. If repeated sensor readings share an unmodelled common error, increasing their number need not supply this much independent information.

Stanford's archive records a technical report by Herman Chernoff, dated November 1951, on asymptotic efficiency of hypothesis tests based on sums of observations.^[ref] This is historical source metadata, rather than a claim to have inspected the report's full proof. The modern theorem cited above connects that efficiency question to the log-likelihood ratio accumulated across repeated observations.

For distinct probability distributions $P,Q$, the optimal error exponents in hypothesis testing give type-II error $Q^{\otimes n}(B_n)$ decay rate $D(P\Vert Q)$ among tests whose type-I error $P^{\otimes n}(B_n^c)$ stays below any fixed number in $(0,1)$.

The Neyman-Pearson lemma says that an optimal region accepting $P$ has the likelihood-ratio formwith possible randomization on the boundary.