Competitive Closeness Testing

[edit]

Jayadev Acharya, Hirakendu Das, Ashkan Jafarpour, Alon Orlitsky, Shengjun Pan ;
Proceedings of the 24th Annual Conference on Learning Theory, PMLR 19:47-68, 2011.

Abstract

We test whether two sequences are generated by the same distributionor by two different ones.Unlike previous work, we make no assumptions on the distributions’support size. Additionally, we compare our performance to thatof the best possible test.We describe an efficiently-computable algorithm based on\emphpattern maximum likelihood that is near optimal whenever the bestpossible error probability is \le\exp(-14n^2/3)using length-n sequences.

Related Material