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 ${\displaystyle H_{0}:Q=P}$, and the most general composite alternative ${\displaystyle H_{1}:Q\neq P}$, using independent and identically distributed samples from ${\displaystyle 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 ${\displaystyle H_{0}:Q=P_{0}}$ and ${\displaystyle H_{1}:Q=P_{1}}$, using samples ${\displaystyle X_{1},\dots ,X_{n}{\overset {\text{i.i.d.}}{\sim }}Q}$. In the traditional setting of hypothesis testing ${\displaystyle P_{0},P_{1}}$ are known apriori. A composite version of this problem involves sets of probability distributions ${\displaystyle \Omega _{0},\Omega _{1}}$, and asks to distinguish between ${\displaystyle H_{0}:Q\in \Omega _{0}}$ and ${\displaystyle H_{1}:Q\in \Omega _{1}}$. In contrast, the universal setting corresponds to the special case of composite hypothesis testing, where the null hypothesis is simple, ${\displaystyle \Omega _{0}=P}$ and the alternative hypothesis is the set of all distributions other than ${\displaystyle P}$, ${\displaystyle \Omega _{1}=\{F:F\neq P\}}$. For example, someone might want to know if a particular coin was fair, i.e. ${\displaystyle \mathbb {P} [X=H]={\frac {1}{2}}=\mathbb {P} [X=T]}$ or not, i.e. ${\displaystyle \mathbb {P} [X=H]\neq \mathbb {P} [X=T]}$, where ${\displaystyle 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⁶⁷.