A Competitive Test for Uniformity of Monotone Distributions


Jayadev Acharya, Ashkan Jafarpour, Alon Orlitsky, Ananda Suresh ;
Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, PMLR 31:57-65, 2013.


We propose a test that takes random samples drawn from a monotone distribution and decides whether or not the distribution is uniform. The test is nearly optimal in that it uses at most O(n\sqrt\log n) samples, where n is the number of samples that a genie who knew all but one bit about the underlying distribution would need for the same task. Furthermore, we show that any such test would require Ω(n\sqrt\log n) samples for some distributions.

Related Material