A method to test for uniform distribution over a convex polytope

Question

Assuming I have a convex polytope defined as the intersection of $Ax=b$ and $x>0$ and I have a way to sample points from this object, is there a way I can test for uniformity of these sampled points? I would assume the use of the Chi-Squared test after first partitioning the space into equal area bins, but I'm not sure how I would go about doing that.

Answer 1

What sort of guarantee are you trying to achieve? If you're willing to test (whp) whether the distribution of those points in $N$ equal bins (the partition you decide to create) is either

• uniform vs
• $\epsilon$-far (in total variation distance, i.e. $L_1$ distance) from uniform

then you can do it with $\Theta(\frac{\sqrt{N}}{\epsilon^2}\ln\frac{1}{\delta})$ samples, and you will have the guarantee that, w.p. $1-\delta$,

• if it is uniform, then the test will pass;
• if the distribution has TV distance at least $\epsilon$ from the uniform distribution, it'll fail.

See for instance [Pan08].