How to test uniformity in several dimensions?

Question

Testing for uniformity is something common, however I wonder what are the methods to do it for a multidimensional cloud of points.

Answer 1

The standard method uses Ripley's K function or something derived from it such as an L function. This is a plot that summarizes the average number of neighbors of the points as a function of maximum distance apart ($\rho$). For a uniform distribution in $n$ dimensions, that average ought to behave like $\rho^n$: and it always will for small $\rho$. It departs from such behavior due to clustering, other forms of spatial non-independence, and edge effects ( whence it is crucial to specify the region sampled by the points). Because of this complication--which gets worse as $n$ increases--in most applications a confidence band is erected for the null K function via simulation and the observed K function is overplotted to detect excursions. With some thought and experience, the excursions can be interpreted in terms of tendencies to cluster or not at certain distances.

Examples of a K function and its associated L-function from Dixon (2001), ibid. The L function is constructed so that $L(\rho)-\rho$ for a uniform distribution is the horizontal line at zero: a good visual reference. The dashed lines are confidence bands for this particular study area, computed via simulation. The solid gray trace is the L function for the data. The positive excursion at distances 0-20 m indicates some clustering at these distances.

I posted a worked example in response to a related question at http://stats.stackexchange.com/a/7984, where a plot derived from the K-function for a uniform distribution on a two-dimensional manifold embedded in $\mathbb{R}^3$ is estimated by simulation.

In R, the spatstat functions kest and k3est compute the K-function for $n=2$ and $n=3$, respectively. In more than 3 dimensions you are probably on your own, but the algorithms would be exactly the same. You could do the computations from a distance matrix as computed (with moderate efficiency) by stats::dist.

Answer 2

It turns out that the question is more difficult than I thought. Still, I did my homework and after looking around, I found two methods in addition to Ripley's functions to test uniformity in several dimensions.

I made an R package called unf that implements both tests. You can download it from github at https://github.com/gui11aume/unf. A large part of it is in C so you will need to compile it on your machine with R CMD INSTALL unf. The articles on which the implementation is based are in pdf format in the package.

The first method comes from a reference from @Procrastinator (Testing multivariate uniformity and its applications, Liang et al., 2000) and applies only to test uniformity on the unit hypercube. The idea is to design discrepancy statistics that are asymptotically Gaussian by the Central Limit theorem. This allows to compute a $\chi^2$ statistic, which is the basis of the test.

library(unf)
set.seed(123)
# Put 20 points uniformally in the 5D hypercube.
x <- matrix(runif(100), ncol=20)
liang(x) # Outputs the p-value of the test.
[1] 0.9470392

The second approach is less conventional and uses minimum spanning trees. The initial work was performed by Friedman & Rafsky in 1979 (reference in the package) to test whether two multivariate samples come from the same distribution. The image below illustrates the principle.

Points from two bivariate samples are plotted in red or blue, depending on their original sample (left panel). The minimum spanning tree of the pooled sample in two dimensions is computed (middle panel). This is the tree such that sum of edge lengths is minimum. The tree is decomposed in subtrees where all the points have the same labels (right panel).

In the figure below, I show a case where blue dots are aggregated, which reduces the number of trees at the end of the process, as you can see on the right panel. Friedman and Rafsky have computed the asymptotic distribution of the number of trees that one obtains in the process, which allows to perform a test.

This idea to create a general test for uniformity of a multivariate sample has been developed by Smith and Jain in 1984, and implemented by Ben Pfaff in C (reference in the package). The second sample is generated uniformly in the approximate convex hull of the first sample and the test of Friedman and Rafsky is performed on the two-sample pool.

The advantage of the method is that it tests uniformity on every convex multivariate shape and not only on the hypercube. The strong disadvantage, is that the test has a random component because the second sample is generated at random. Of course, one can repeat the test and average the results to get a reproducible answer, but this is not handy.

Continuing previous R session, here is how it goes.

pfaff(x) # Outputs the p-value of the test.
pfaff(x) # Most likely another p-value.

Feel free to copy/fork the code from github.

Answer 3

Would the pair $(U,Z)$ be dependent unifroms where $U \sim {\rm Uniform}(0,1)$ and $Z=U$ with probability $0<p<1$ and $W$ with probability $1-p$ where $W$ is also ${\rm Uniform}(0,1)$ and independent of $U$?

For independent random variables in $n$ dimensions divide the $n$-dimensional unit cube it a set of smaller disjoint cubes with the same side length. Then do a $\chi^2$ test for uniformity. This will only work well if n is small like 3-5.