I'm researching a method for sampling uniformly from an $n$-dimensional shape, for which conventional rejection sampling may be too slow. I am generating 1,000 points using each method, and wish to compare the quality of their randomness. The points generated using the new method should be identically distributed to those generated by rejection sampling.

My initial approach was to use a two-sample $\chi^2$-test, splitting space up into hypercubes of some size, counting the number of points falling into each hypercube, and then performing Pearson's two-sample $\chi^2$-test on the number of points in each hypercube. Various internet sources say that "any reasonable number of bins" will give similar results for this experiment, but there are no suggestions for what a reasonable number of bins might be.

My questions are:

  1. Is this approach valid, or would I be able to give more sound results using a different statistical test, e.g. some $n$-dimensional analogue to the Kolmogorov Smirnov test?
  2. Given that I can guarantee that all points will fall within an $n$-ball of known radius, what would a sensible method of dividing my space be?


OK, I've done a bit of thinking on this, and I have an algorithm for approaching the problem, but with one limitation. This test will pass iff one data set is a rotation of the other about its mean

  1. Let $X$ be the data set.

  2. Subtract the mean vector from each point in the data set, $X$, such that the data have a mean of 0.

  3. Let $D_x$ be the matrix such that each column is one of the adjusted data points

  4. Let $\Lambda$ be the matrix such that each row is a normalised eigenvector of the covariance matrix of $D_x$

  5. Let $\widetilde{D'_x} = \Lambda D$.

  6. The columns of $\widetilde{D'_x}$ are then the original data adjusted to have mean 0 and covariance 0. Each axis now contains a series of independent points.

  7. Add the mean back on to each point to produce $\widetilde{D_x}$

  8. Repeat the same process for the second data set, $Y$, to produce $\widetilde{D_y}$

  9. Let $\widetilde{D_x}_i$ denote the $i^{th}$ row of $\widetilde{D_x}$.

  10. Run a series of Kolmogorov-Smirnov tests comparing $\widetilde{D_x}_i$ to $\widetilde{D_y}_i$, for each axis $i$.

If all tests pass, then the random vectors are identically distributed, up to a rotation about the mean.

So, we now have a new question, can this method be modified such that it will reject data sets that are rotations of each other? I suspect that this could be accomplished by running another test on the eigenvector matrix $\Lambda$ to check that they're all pointing in roughly the same direction, or ordering the rows of $\Lambda$ in some fixed way. Each row must be orthogonal, so we could probably define some ordering based on the $n$-dimensional analogue of the idea of quadrants in $2$-dimensional space.

  • $\begingroup$ I've just gone ahead and done this, and can confirm that the differences are as I would expect relative to the ranges over which they are sampled. I've also done some marginalised Kolmogorov-Smirnov tests across individual dimensions, and they also pass and fail in roughly the manner I'd expect them to. This, again, is not a sufficient condition, but it is a necessary condition. $\endgroup$ – ymbirtt Aug 28 '13 at 14:43
  • $\begingroup$ You might want to consider the multidimensional version of Ripley's cross-K function. For its null you can simulate using rejection sampling and then compute an envelope of values comparing the alternative sampling procedure to the rejection sampling results. Although it is computationally expensive (cross-K looks at all possible point pairs), this will give both a graphical and formal way to detect subtle differences in the sampling procedures. $\endgroup$ – whuber Aug 28 '13 at 15:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.