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}