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 = {Jayadev Acharya and Ashkan Jafarpour and Alon Orlitsky and Ananda Suresh}, pages = {57--65}, year = {2013}, editor = {Carlos M. Carvalho and Pradeep Ravikumar}, 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 = {http://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 %J Proceedings of Machine Learning Research %P 57--65 %U http://proceedings.mlr.press %V 31 %W PMLR %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 PY - 2013/04/29 DA - 2013/04/29 ED - Carlos M. Carvalho ED - Pradeep Ravikumar ID - pmlr-v31-acharya13a PB - PMLR SP - 57 DP - PMLR EP - 65 L1 - http://proceedings.mlr.press/v31/acharya13a.pdf UR - http://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 PMLR 31:57-65

Related Material