Varun Jog (University of Cambridge)

The sample complexity of simple binary hypothesis testing

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 such that the Type-I and Type-II errors are smaller than some pre-specified thresholds α and β, respectively. Our main contribution is deriving, under mild technical conditions, a formula for the sample complexity in terms of parameters p, q, α, and β, that is tight up to universal multiplicative constants.