A Competitive Test for Uniformity of Monotone Distributions
Abstract
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.
Cite
Text
Acharya et al. "A Competitive Test for Uniformity of Monotone Distributions." International Conference on Artificial Intelligence and Statistics, 2013.Markdown
[Acharya et al. "A Competitive Test for Uniformity of Monotone Distributions." International Conference on Artificial Intelligence and Statistics, 2013.](https://mlanthology.org/aistats/2013/acharya2013aistats-competitive/)BibTeX
@inproceedings{acharya2013aistats-competitive,
title = {{A Competitive Test for Uniformity of Monotone Distributions}},
author = {Acharya, Jayadev and Jafarpour, Ashkan and Orlitsky, Alon and Suresh, Ananda Theertha},
booktitle = {International Conference on Artificial Intelligence and Statistics},
year = {2013},
pages = {57-65},
url = {https://mlanthology.org/aistats/2013/acharya2013aistats-competitive/}
}