A short note on the efficient random sampling of the multi-dimensional pyramid between a simplex and the origin lying in the unit hypercube

Abstract

When estimating how much better a classifier is than random allocation in Q-class ROC analysis, we need to sample from a particular region of the unit hypercube: specifically the region, in the unit hypercube, which lies between the Q − 1 simplex in Q(Q − 1) space and the origin. This report introduces a fast method for randomly sampling this volume, and is compared to rejection sampling of uniform draws from the unit hypercube. The new method is based on sampling from a Dirichlet distribution and shifting these samples using a draw from the Uniform distribution. We show that this method generates random samples within the volume at a probability ≈ 1/(Q(Q − 1)), as opposed to ≈ (Q − 1)Q(Q − 1) /(Q(Q − 1))! for rejection sampling from the unit hypercube. The vast reduction in rejection rates of this method means comparing classifiers in a Q-class ROC framework is now feasible, even for large Q.