On the Consistency of the Shortest Hamiltonian Path Test

Introduced by Biswas et al. (2014), the shortest Hamiltonian path (SHP) test is a popular nonparametric, multivariate 2-sample test which has the much-desired property that it is exactly distribution-free under the null hypothesis. The test constructs a shortest Hamiltonian path on the pooled sample and counts the number of edges connecting points from different samples. For similar distributions, the test statistic should be relatively large, and for dissimilar distributions, the test statistic should be small. The nature of the SHP makes it quite similar to path construction for the Traveling Salesman Problem (TSP), and exact calculation of the SHP is nondeterministic polynomial (NP) complete. In this paper, we use TSP approximation methods to approximate the SHP. We prove that the SHP test is universally consistent under this implementation, that is, the power of the tests converges to 1, as the samples sizes go to infinity, for all fixed alternatives.