Testing uniformity for continuous probability distributions

Question

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).

Answer 1

This shouldn't be possible without assumptions on $X$. Take any algorithm drawing $m$ samples. Construct a discrete distribution $X$ by drawing $2^m$ samples indepedently and uniformly from $[0,1]$, and let $X$ be uniform on these $2^m$ distinct (w.prob. 1) points. Then $X$ has maximal total variation distance from uniform, but with high prob. you cannot distinguish an $X$ constructed in this way from the uniform distribution with only $m$ samples. We should be able to get essentially the same impossibility by making $X$ a mixture of Gaussians centered at those $2^m$ points with tiny variance, or something similar.

Answer 2

It seems that the situation with continuous distributions is fundamentally different than the finite support one. I believe that Section 2.3 in Random number generation and Monte Carlo methods by J. E. Gentle is a good start.

Answer 3

Update: I've now asked about the claim at another question, where it was proved by Anthony Quas and Iosif Pinelis. Using the number $24/121$ from Iosif's answer, the algorithm in this answer could be improved to using $1/4-\epsilon/8$ as the cutoff between outputting "uniform" and "non-uniform", and requiring only $n>16/\epsilon^2$ samples.

Suppose we restrict to concave distributions, i.e. distributions with densities $f$ for which $$f\left(\frac{a+b}{2}\right) \ge \frac{f(a)+f(b)}{2}$$ for any $a,b\in[0,1]$.

Then there is a simple test on $n$ samples:

• Let $P_1$ be the fraction of samples between $0$ and $\frac14$.
• Let $P_4$ be the fraction of samples between $\frac34$ and $1$.
• If $\min(P_1,P_4) > 1/4-\epsilon/12$, output "uniform"
• If $\min(P_1,P_4) < 1/4-\epsilon/12$, output "non-uniform"

If $n>50/\epsilon^2$, then this test succeeds with probability at least $3/4$ on the uniform distribution, and with probability at least $3/4$ on any concave distribution at total variation distance at least $\epsilon$ from uniform.

The criterion of concavity is broad enough to cover many reasonable distributions that one might compare with the uniform distribution, including the below (illustrated with $\epsilon=1/10$)

We can bound the test's probability of failure for the uniform distribution by \begin{align} &2P\left[\ \ B\left(n,\ \ \ \frac{1}{4}\ \ \ \right)<\frac{1}{4}-\frac{n\epsilon}{12}\right] \\ \sim &2P\left[N\left(\frac{n}{4},\frac{\sqrt{3n}}{4}\right)<\frac{n}{4}-\frac{n\epsilon}{12}\right]\\ = &2\,\Phi\left(-\frac{\sqrt{n}\epsilon}{3\sqrt{3}} \right)\\ < &2\,\Phi\left(-\frac{\sqrt{50}}{3\sqrt{3}} \right)\\ = &0.174 \end{align}

To bound the probability of failure for non-uniform distributions, we need to know that either $[0,1/4]$ or $[3/4,1]$ will be substantially less probable than average.

Claim: If $f(x)$ is concave and positive on $[0,1]$ with $\int_0^1 f(x)dx = 1$ and $$\int_0^1 \max(0,1-f(x))\,dx \ge \epsilon$$ then $$\min\!\left(\int_0^{1/4}f(x)\,dx, \int_{3/4}^1 f(x)\,dx\right) \le \frac14-\frac\epsilon8 $$

If $f$ is the pdf of a distribution, then the first integral is its total variation distance to the uniform distribution; the second and third integrals are the limits of $P_1$ and $P_4$.

I hope that someone will see a clean proof of this claim from some standard properties of concave functions. One can also verify that the examples above satisfy both the hypotheses and the conclusion of the claim.

With the claim, the probability of failure for the non-uniform distributions is bounded by \begin{align} &P\left[B\left(n,\frac{1}{4}-\frac{\epsilon}{8}\right)>\frac{n}{4}-\frac{n\epsilon}{12}\right] \\ \sim &P\left[N\left( \frac{n}{4}-\frac{n\epsilon}{8},\frac{\sqrt{n(2-\epsilon)(6+\epsilon)}}{8}\right) >\frac{n}{4}-\frac{n\epsilon}{12}\right] \\ < &P\left[N\left( 0,\frac{\sqrt{12n}}{8}\right) >\frac{n\epsilon}{24}\right] \\ =&1-\Phi\left(\frac{\sqrt{n}\epsilon}{3\sqrt{12}}\right) \\ <&1-\Phi\left(\frac{\sqrt{50}}{3\sqrt{12}}\right) \\ =&.248 \\ \end{align}