The Sample Complexity of Simple Binary Hypothesis Testing

arXiv:2403.16981v1 Announce Type: cross
Abstract: The sample complexity of simple binary hypothesis testing is the smallest number of i.i.d. samples required to distinguish between two distributions $p$ and $q$ in either: (i) the prior-free setting, with type-I error at most $\alpha$ and type-II error at most $\beta$; or (ii) the Bayesian setting, with Bayes error at most $\delta$ and prior distribution $(\alpha, 1-\alpha)$. This problem has only been studied when $\alpha = \beta$ (prior-free) or $\alpha = 1/2$ (Bayesian), and …

abstract alpha arxiv bayesian beta binary complexity cs.it error free hypothesis math.it math.st prior sample samples simple stat.ml stat.th testing type