2012/04/30 by Dayu Huang, Sean Meyn
Computer Science · Engineering · Mathematics · #Algorithm #Arithmetic #Computer science #Discrete mathematics #Machine Learning and Algorithms #Mathematics #Notation #Quantum Computing Algorithms and Architecture #Sparse and Compressive Sensing Techniques #cs.IT #math.IT #math.ST #stat.TH
paper · pdf · doi:10.1109/tit.2013.2283266
published as IEEE Transactions on Information Theory, vol.59, no.12, pp.8157,8181, Dec. 2013 · 43 pages, 4 figures
openalex publication_date 2013/11/19 · arxiv created 2014/12/28 · arxiv updated 2014/12/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
The small sample universal hypothesis testing problem is investigated in this paper, in which the number of samplesnis smaller than the number of possible outcomesm. The goal of this paper is to find an appropriate criterion to analyze statistical tests in this setting. A suitable model for analysis is the high-dimensional model in which bothnandmincrease to infinity, andn=o(m). A new performance criterion based on large deviations analysis is proposed and it generalizes the classical error exponent applicable for large sample problems (in whichm=O(n)). This generalized error exponent criterion provides insights that are not available from asymptotic consistency or central limit theorem analysis. The following results are established for the uniform null distribution: 1) The best achievable probability of errorPedecays asPe=exp \-(n2/m) J (1+o(1))\for someJ>0. 2) A class of tests based on separable statistics, including the coincidence-based test, attains the optimal generalized error exponents. 3) Pearson's chi-square test has a zero generalized error exponent and thus its probability of error is asymptotically larger than the optimal test.