Error exponents in hypothesis testing

In statistical hypothesis testing, the error exponent of a hypothesis testing procedure is the rate at which the probabilities of Type I and Type II decay exponentially with the size of the sample used in the test. For example, if the probability of error ${\displaystyle P_{\mathrm {error} }}$ of a test decays as ${\displaystyle e^{-n\beta }}$, where ${\displaystyle n}$ is the sample size, the error exponent is ${\displaystyle \beta }$.

Formally, the error exponent of a test is defined as the limiting value of the ratio of the negative logarithm of the error probability to the sample size for large sample sizes: ${\displaystyle \lim _{n\to \infty }{\frac {-\log P_{\text{error}}}{n}}}$. Error exponents for different hypothesis tests are computed using Sanov's theorem and other results from large deviations theory. There are various methods used to show that an error exponent is achievable, including the likelihood ratio (which is known to be optimal in certain circumstances), and the empirical distribution¹. Error exponents are sometimes referred to as error rates, due to the connection between hypothesis testing and information theory².

Consider a binary hypothesis testing problem in which observations are modeled as independent and identically distributed random variables under each hypothesis. Let ${\displaystyle Y_{1},Y_{2},\ldots ,Y_{n}}$ denote the observations. Let ${\displaystyle f_{0}}$ denote the probability density function of each observation ${\displaystyle Y_{i}}$ under the null hypothesis ${\displaystyle H_{0}}$ and let ${\displaystyle f_{1}}$ denote the probability density function of each observation ${\displaystyle Y_{i}}$ under the alternate hypothesis ${\displaystyle H_{1}}$.

In this case there are two possible error events. Error of type I, also called false positive, occurs when the null hypothesis is true and it is wrongly rejected. Error of type II, also called false negative, occurs when the alternate hypothesis is true and null hypothesis is not rejected. The probability of type I error is denoted ${\displaystyle P(\mathrm {error} \mid H_{0})}$ and the probability of type II error is denoted ${\displaystyle P(\mathrm {error} \mid H_{1})}$. In some fields, the type I error is denoted by ${\displaystyle \alpha _{n}}$ and the type II error is denoted by ${\displaystyle \beta _{n}}$.

In the Neyman–Pearson³ version of binary hypothesis testing, one is interested in minimizing the probability of type II error ${\displaystyle P({\text{error}}\mid H_{1})}$ subject to the constraint that the probability of type I error ${\displaystyle P({\text{error}}\mid H_{0})}$ is less than or equal to a pre-specified level ${\displaystyle \alpha }$. In this setting, the optimal testing procedure is a likelihood-ratio test.⁴ Furthermore, the optimal test guarantees that the type II error probability decays exponentially in the sample size ${\displaystyle n}$ according to ${\displaystyle \lim _{n\to \infty }{\frac {-\log P(\mathrm {error} \mid H_{1})}{n}}=D(f_{0}\parallel f_{1})}$.⁵ The error exponent ${\displaystyle D(f_{0}\parallel f_{1})}$ is the Kullback–Leibler divergence between the probability distributions of the observations under the two hypotheses. This exponent is also referred to as the Chernoff–Stein lemma exponent.

In the Bayesian version of binary hypothesis testing one is interested in minimizing the average error probability under both hypothesis, assuming a prior probability of occurrence on each hypothesis. Let ${\displaystyle \pi _{0}}$ denote the prior probability of hypothesis ${\displaystyle H_{0}}$. In this case the average error probability is given by ${\displaystyle P_{\text{ave}}=\pi _{0}P({\text{error}}\mid H_{0})+(1-\pi _{0})P({\text{error}}\mid H_{1})}$. In this setting again a likelihood ratio test is optimal and the optimal error decays as ${\displaystyle \lim _{n\to \infty }{\frac {-\log P_{\text{ave}}}{n}}=C(f_{0},f_{1})}$ where ${\displaystyle C(f_{0},f_{1})}$ represents the Chernoff-information between the two distributions defined as ${\displaystyle C(f_{0},f_{1})=\max _{\lambda \in [0,1]}\left[-\log \int (f_{0}(x))^{\lambda }(f_{1}(x))^{(1-\lambda )}\,dx\right]}$.⁵

A more explicit tradeoff between the type I and type II error is observed when the type I error is constrained to decay exponentially, and the type II error is minimized. If we require ${\displaystyle P({\text{error}}|H_{0})<e^{-nr}}$ for some ${\displaystyle r<D(f_{1}\|f_{0})}$, then the optimal type II error exponent is described by ${\displaystyle \limsup _{n\to \infty }{\frac {1}{n}}\log P({\text{error}}|H_{1})=-H_{r}(f_{0}\parallel f_{1})}$. Here ${\displaystyle H(f_{0}\parallel f_{1})}$ is the Hoeffding divergence ⁶⁷² described by

${\displaystyle H_{r}(f_{0}\parallel f_{1})=\max _{0\leq s\leq 1}{\frac {\Psi (s)-(1-s)r}{s}}}$ (1)

where ${\displaystyle \Psi (s)=\int dx\ f_{0}(x)^{1-s}f_{1}(x)^{s}}$.

Sometimes, the above considerations are described as the first order error exponents of hypothesis testing, meaning the analysis of

${\displaystyle \lim _{n\to \infty }-{\frac {1}{n}}\log \mathbb {P} _{H_{1}}[{\text{error}}]}$

However, it is also possible to analyze higher order error exponents, for example the second order error exponent. If the first order error exponent is given by ${\displaystyle I_{1}}$, then the second order error exponent is taken to be

${\displaystyle -\lim _{n\to \infty }{\frac {1}{\sqrt {n}}}\left(-\log \left(\mathbb {P} _{H_{1}}[{\text{error}}]\right)-nI_{1}\right)}$

Second order analysis of hypothesis testing has been studied for several types of hypothesis testing problems: simple hypothesis testing⁸, One sample universal hypothesis testing⁹, and two-sample universal problems¹⁰. The second order error exponent is sometimes called the relative entropy variance⁸.