This 1952 classic by Herman Chernoff, published in The Annals of Mathematical Statistics, is a cornerstone of modern probability and statistics. It introduces what we now call the Chernoff Bound and the Chernoff Information, providing a rigorous way to compare the efficiency of statistical tests when sample sizes are very large.
TL;DR
Chernoff demonstrates that for large samples, the probability of making a statistical error decreases exponentially. He identifies the specific rate of this decay (the "index $\rho$") and uses it to define a measure of asymptotic efficiency that remains accurate even in the extreme "tails" of a distribution where standard normal approximations fail.
What Problem Does This Paper Address?
In classical statistics, we often compare two different tests to see which is "better" or more "efficient." A common measure is the sample size needed to achieve a certain level of power. However, standard methods (like Pitman efficiency) often rely on the Central Limit Theorem and normal approximations.
While the normal approximation works great near the average value of a distribution, it starts to fall apart when we look at the "tails"—the very low-probability events. If you are running a test with millions of observations, you aren't just worried about the average behavior; you are worried about the probability of an extreme error. Chernoff realized that in these large-sample scenarios, the probability of error doesn't just get smaller; it vanishes at an exponential rate. He set out to find a way to calculate that rate precisely.
Methods
The paper moves away from simple variance-based comparisons and dives into Moment Generating Functions (MGFs).
- The $m(a)$ Function: Chernoff defines a function $m(a) = \inf_t e^{-at} M(t)$, where $M(t)$ is the MGF of the random variable. This function essentially captures the "tightest" possible exponential bound on the tail of a sum of independent observations.
- Asymptotic Analysis: He analyzes the behavior of the sum $S_n$ of $n$ observations as $n$ goes to infinity.
- Bayes Solutions: To compare tests, he looks at the "Bayes Solution"—a test that minimizes a weighted sum of Type I errors (false positives) and Type II errors (false negatives).
- The Index $\rho$: He proves that the minimum total error behaves like $\rho^n$, where $\rho$ is a value between 0 and 1. The smaller the $\rho$, the faster the error drops, and the more efficient the test.
Datasets
Not discussed in the paper. As a theoretical statistics paper, it relies on mathematical proofs and closed-form examples (Normal, Binomial, and Chi-square distributions) rather than empirical datasets.
Key Insights and Ideas
- The Power of the Tail: The paper’s most famous contribution is the proof that $P(S_n \le na) \approx [m(a)]^n$. This "Chernoff Bound" is now a staple in randomized algorithms and information theory because it provides a very "sharp" (accurate) upper bound on how often a sum of variables will deviate far from its mean.
- Efficiency as a Ratio of Logs: Chernoff defines the relative efficiency of two tests as $e = \log \rho_1 / \log \rho_2$. This tells you exactly how many more samples you need for Test B to match the error rate of Test A.
- The Information Theory Link: In the final section, Chernoff connects his statistical index to the work of Kullback and Leibler. He shows that his measure of efficiency is essentially a measure of the "information" or "divergence" between two probability distributions.
- Robustness of the Normal Case: He shows that if two hypotheses are very "close" to each other, the complex exponential math simplifies back down to a form that looks like the standard normal distribution, validating why the normal approximation works in those specific cases.
Key Results
- Theorem 1: Establishes the fundamental exponential bound for the tails of sums of independent variables.
- Theorem 3: Formally defines the asymptotic efficiency $e$ and proves it is the correct limit for comparing sample sizes as error probabilities go to zero.
- Quantitative Examples:
- For Normal distributions with the same variance $\sigma^2$ but different means, the index is $\rho = \exp(-(\mu_1 - \mu_0)^2 / 8\sigma^2)$.
- For Binomial distributions, he provides a formula (Equation 5.12) that allows researchers to calculate exactly how fast the error rate drops based on the success probabilities $p_0$ and $p_1$.
Limitations and Future Work
- Independence Assumption: The results are derived for sums of independent observations. Extending this to dependent variables (like Markov chains) is a major area of research that followed this paper.
- Simple Hypotheses: The paper primarily focuses on "simple" hypotheses (where the distribution is fully specified). It notes that "composite" hypotheses (where parameters might fall in a range) are more complex and require further investigation.
- Computational Difficulty: At the time (1952), calculating these indices for complex distributions was mathematically taxing. Chernoff suggests that for very similar distributions, the normal approximation is a "good enough" shortcut.
Summary updated