Suppose I can sample from a random variable $X$ which is distributed on a compact interval, say, $[0,1]$. Fix a distance measure between distributions, say total variation. Let $\epsilon\in(0,1)$. How many samples are needed (upper and lower bounds) to test whether $X$ is uniformly distributed or its distribution is $\epsilon$-far from uniform, with probability of success at least $3/4$. References are welcome. In the case of a finite support of size $n$, the minimax complexity is known to be $\Theta(\sqrt{n}/\epsilon^2)$ (cf. A coincidence-based test for uniformity given very sparsely-sampled discrete data by L. Paninski).
Minimax complexity of uniformity testing for (absolutely) continuous probability distributions
Sela Fried
- 135
- 4