= Finite-sample Chernoff error bound
{title2=$p_n^*\leq\tfrac12e^{-nC(P,Q)}$}
For equal <prior probabilities> and <independent and identically distributed> observations on a <finite alphabet>, <minimum sum of errors in a simple hypothesis test> gives
$$
p_n^*=\frac12\sum_{x_1,\ldots,x_n}\min\{P^{\otimes n}(x_1,\ldots,x_n),Q^{\otimes n}(x_1,\ldots,x_n)\}.
$$
For nonnegative $a,b$ and $0<s<1$, $\min(a,b)\leq a^sb^{1-s}$. Applying this termwise and using the <independence of random variables> to factor the sum yields
$$
p_n^*\leq\frac12\left(\sum_xP(x)^sQ(x)^{1-s}\right)^n.
$$
Optimizing $s$, with an <infimum> if needed, proves $p_n^*\leq\tfrac12e^{-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.
Back to article page
