Power properties of the two sample test based on the nearest neighbors graph

Abstract

In this paper, we study the problem of testing the equality of two multivariate distributions. One class of tests used for this purpose utilizes geometric graphs constructed using interpoint distances. So far, the asymptotic theory of these tests applies only to graphs, which fall under the stabilizing graphs framework of Penrose and Yukich (Ann. Appl. Probab. 13 (2003) 277–303). We study the case of the K-nearest neighbors graph where K=kN increases with the sample size, which does not fall under the stabilizing graphs framework. Our main result gives detection thresholds for this test in parametrized families when kN=o(N1/4), thus extending the family of graphs where the theoretical behavior is known. We propose a 2-sided version of the test, which removes an exponent gap that plagues the 1-sided test. Our result also shows that increasing the number of nearest neighbors improves the power of the test. This provides a theoretical justification for using denser graphs in testing the equality of two distributions.