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.

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 this Paper

BibTeX
@InProceedings{pmlr-v31-acharya13a, title = {A Competitive Test for Uniformity of Monotone Distributions}, author = {Acharya, Jayadev and Jafarpour, Ashkan and Orlitsky, Alon and Suresh, Ananda}, booktitle = {Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics}, pages = {57--65}, year = {2013}, editor = {Carvalho, Carlos M. and Ravikumar, Pradeep}, volume = {31}, series = {Proceedings of Machine Learning Research}, address = {Scottsdale, Arizona, USA}, month = {29 Apr--01 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v31/acharya13a.pdf}, url = {https://proceedings.mlr.press/v31/acharya13a.html}, 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.} }
Endnote
%0 Conference Paper %T A Competitive Test for Uniformity of Monotone Distributions %A Jayadev Acharya %A Ashkan Jafarpour %A Alon Orlitsky %A Ananda Suresh %B Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2013 %E Carlos M. Carvalho %E Pradeep Ravikumar %F pmlr-v31-acharya13a %I PMLR %P 57--65 %U https://proceedings.mlr.press/v31/acharya13a.html %V 31 %X 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.
RIS
TY - CPAPER TI - A Competitive Test for Uniformity of Monotone Distributions AU - Jayadev Acharya AU - Ashkan Jafarpour AU - Alon Orlitsky AU - Ananda Suresh BT - Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics DA - 2013/04/29 ED - Carlos M. Carvalho ED - Pradeep Ravikumar ID - pmlr-v31-acharya13a PB - PMLR DP - Proceedings of Machine Learning Research VL - 31 SP - 57 EP - 65 L1 - http://proceedings.mlr.press/v31/acharya13a.pdf UR - https://proceedings.mlr.press/v31/acharya13a.html AB - 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. ER -
APA
Acharya, J., Jafarpour, A., Orlitsky, A. & Suresh, A.. (2013). A Competitive Test for Uniformity of Monotone Distributions. Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 31:57-65 Available from https://proceedings.mlr.press/v31/acharya13a.html.

Related Material