Consistency of the Shortest Hamiltonian Path Test

Music City Center 

The shortest Hamiltonian path test, introduced by Biswas et al. (2014), is a widely used nonparametric, multivariate two-sample test. It is one of only three statistical tests with a null test statistic that has a tractable distribution in finite sample sizes. A Hamiltonian path visits each vertex exactly once, and the shortest Hamiltonian path minimizes the total path length. In this test, the shortest Hamiltonian path is constructed from the pooled vertices of two samples, and the test statistic is the number of edges connecting vertices from different samples. The null distribution of this test statistic matches that of the Wald–Wolfowitz Runs test, as it counts the number of runs along the shortest Hamiltonian path. The problem of constructing the shortest Hamiltonian path closely resembles the well-known Traveling Salesman Problem. In this proof, we develop an approximation algorithm for the shortest Hamiltonian path using concepts from the Traveling Salesman Problem and establish that the test is asymptotically consistent.

Nonparametric Tests

Graph Based Tests

Multivariate Statistics

Consistency 

Section on Nonparametric Statistics