Universal hypothesis testing

In statistics, universal hypothesis testing is a special case of binary simple hypothesis testing. The universal problem is to distinguish between a simple null hypothesis $H_0:Q=P$, and the most general composite alternative $H_1:Q\ne P$, using independent and identically distributed samples from $Q$. The setting is sometimes referred to as goodness of fit testing, or one-sample testing.

A simple binary hypothesis testing problem involves distinguishing between $H_0:Q=P_0$ and $H_1:Q=P_1$, using samples $X_1,\dots ,X_n\stackrel{\text{i.i.d.}}{\sim }Q$. In the traditional setting of hypothesis testing $P_0,P_1$ are known apriori. A composite version of this problem involves sets of probability distributions ${\mathrm{\Omega }}_0,{\mathrm{\Omega }}_1$, and asks to distinguish between $H_0:Q\in {\mathrm{\Omega }}_0$ and $H_1:Q\in {\mathrm{\Omega }}_1$. In contrast, the universal setting corresponds to the special case of composite hypothesis testing, where the null hypothesis is simple, ${\mathrm{\Omega }}_0=P$ and the alternative hypothesis is the set of all distributions other than $P$, ${\mathrm{\Omega }}_1=\{F:F\ne P\}$. For example, someone might want to know if a particular coin was fair, i.e. $\mathbb{P}[X=H]=\frac{1}{2}=\mathbb{P}[X=T]$ or not, i.e. $\mathbb{P}[X=H]\ne \mathbb{P}[X=T]$, where $H,T$ denote the coin coming up heads or tails.

The asymptotics of universal hypothesis testing were first discussed in Hoeffding's work on optimal tests for multinomial distributions. There have been many subsequent works on the topic in many directions. While Hoeffding's initial results were restricted to distributions with finite supports, later results developed solutions for continuous distributions using extensions of the Kullback-Leibler Divergence, or kernel methods.

See also

• Statistical hypothesis test
• Error exponents in hypothesis testing
• Kullback–Leibler divergence
• Two-sample hypothesis testing
• Student's t-test
• Nonparametric statistics