Competitive Closeness Testing

Jayadev Acharya, Hirakendu Das, Ashkan Jafarpour, Alon Orlitsky, Shengjun Pan ; JMLR W&CP 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\emph{pattern} maximum likelihood that is near optimal whenever the bestpossible error probability is $\le\exp(-14n^{2/3})$using length-$n$ sequences.