Competitive Closeness Testing
Abstract
We test whether two sequences are generated by the same distribution or by two different ones. Unlike previous work, we make no assumptions on the distributions’ support size. Additionally, we compare our performance to that of the best possible test. We describe an efficiently-computable algorithm based on pattern maximum likelihood that is near optimal whenever the best possible error probability is $\le\exp(-14n^{2/3})$ using length-$n$ sequences.
Cite
Text
Acharya et al. "Competitive Closeness Testing." Proceedings of the 24th Annual Conference on Learning Theory, 2011.Markdown
[Acharya et al. "Competitive Closeness Testing." Proceedings of the 24th Annual Conference on Learning Theory, 2011.](https://mlanthology.org/colt/2011/acharya2011colt-competitive/)BibTeX
@inproceedings{acharya2011colt-competitive,
title = {{Competitive Closeness Testing}},
author = {Acharya, Jayadev and Das, Hirakendu and Jafarpour, Ashkan and Orlitsky, Alon and Pan, Shengjun},
booktitle = {Proceedings of the 24th Annual Conference on Learning Theory},
year = {2011},
pages = {47-68},
volume = {19},
url = {https://mlanthology.org/colt/2011/acharya2011colt-competitive/}
}