Competitive Closeness Testing
Jayadev Acharya, Hirakendu Das, Ashkan Jafarpour, Alon Orlitsky, Shengjun Pan · 2011
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 ≤ exp(−14n 2/3) using length-n sequences.