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 p logn) 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. Conversely, we show that any such test would require ( n p logn) samples for some distributions.
['Jayadev Acharya', 'Ashkan Jafarpour', 'Alon Orlitsky', 'Ananda Theertha Suresh']
A Competitive Test for Uniformity of Monotone Distributions