Enhanced upper confidence limits via randomized tests in random sampling without replacement

Abstract In this paper we study one-sided hypothesis testing under random sampling without replacement, which frequently appears in the cryptographic problem setting, including the verification of measurement-based quantum computation. Suppose that $n+1$ binary random variables $X_1,\ldots, X_{n+1}$ follow a permutation invariant distribution and n binary random variables $X_1,\ldots, X_{n}$ are observed. Then, we propose randomized tests with a randomization parameter for the expectation of the $(n+1)$ th random variable $X_{n+1}$ under a given significance level $\delta>0$ . Our randomized tests significantly improve the upper confidence limit over deterministic tests. Our problem setting commonly appears in machine learning in addition to cryptographic scenarios by considering adversarial examples. Such studies are essential for expanding the applicable area of statistics. Although this paper addresses only binary random variables, a similar significant improvement by randomized tests can be expected for general non-binary random variables.