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 \neq 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 \overset{\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 \Omega_0, \Omega_1, and asks to distinguish between H_0: Q \in \Omega_0 and 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, \Omega_0 = P and the alternative hypothesis is the set of all distributions other than P, \Omega_1 = \{F: F \neq 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] \neq \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[1]. There have been many subsequent works on the topic[2][3][4] 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[5], or kernel methods[6][7].

See also

References

  1. ^ Hoeffding, Wassily (April 1965). "Asymptotically Optimal Tests for Multinomial Distributions". The Annals of Mathematical Statistics. 36 (2): 369–401. doi:10.1214/aoms/1177700150. ISSN 0003-4851
  2. ^ Levitan, E. & Merhav, N. (August 2002). "A competitive Neyman-Pearson approach to universal hypothesis testing with applications". IEEE Transactions on Information Theory. 48 (8): 2215–2229. doi:10.1109/TIT.2002.800478. ISSN 0018-9448
  3. ^ Zeitouni, O. & Gutman, M. (March 1991). "On universal hypotheses testing via large deviations". IEEE Transactions on Information Theory. 37 (2): 285–290. doi:10.1109/18.75244
  4. ^ Li, Yun; Nitinawarat, Sirin; Veeravalli, Venugopal V. (July 2014). "Universal Outlier Hypothesis Testing". IEEE Transactions on Information Theory. 60 (7): 4066–4082. arXiv:1302.4776. doi:10.1109/TIT.2014.2317691. ISSN 0018-9448
  5. ^ Yang, Pengfei & Chen, Biao (April 2019). "Robust Kullback-Leibler Divergence and Universal Hypothesis Testing for Continuous Distributions". IEEE Transactions on Information Theory. 65 (4): 2360–2373. arXiv:1711.04238. doi:10.1109/TIT.2018.2879057. ISSN 0018-9448
  6. ^ Zhu, Shengyu; Chen, Biao; Chen, Zhitang; Yang, Pengfei (April 2021). "Asymptotically Optimal One- and Two-Sample Testing With Kernels". IEEE Transactions on Information Theory. 67 (4): 2074–2092. arXiv:1908.10037. doi:10.1109/TIT.2021.3059267. ISSN 0018-9448
  7. ^ Zhu, Shengyu; Chen, Biao; Yang, Pengfei; Chen, Zhitang (2019-04-11). "Universal Hypothesis Testing with Kernels: Asymptotically Optimal Tests for Goodness of Fit". Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics. PMLR. arXiv:1802.07581