On the multivariate runs test

For independent d-variate random variables X$_1$,…,X$_m$ with common density f and Y$_1$,…,Y$_n$ with common density g, let R$_{m,n}$ be the number of edges in the minimal spanning tree with vertices X$_1$,…,X$_m$, Y$_1$,…,Y$_n$ that connect points from different samples. Friedman and Rafsky conjectured that a test of H$_0$ : f = g that rejects H$_0$ for small values of R$_{m,n}$ should have power against general alternatives. We prove that R$_{m,n}$ is asymptotically distribution-free under H$_0$, and that the multivariate two-sample test based on R$_{m,n}$ is universally consistent.