2
$\begingroup$

Given the hyperannulus, an annulus generalized to arbitrary dimensions with outer radius $r_1$ and inner radius $r_0$. This object would be a ring in $\mathbb{R}^2$ and a spherical shell in $\mathbb{R}^3$.

What is the solution of picking uniformly distributed random multivariate points in this hyperannulus without rejection sampling?

$\endgroup$
1
$\begingroup$

The probability that a point picked uniformly from this thick shell has distance $r$ or less from the origin is $\dfrac{r^n-r_0^n}{r_1^n-r_0^n}$ provided that $r_0 \le r \le r_1$. So if $U$ is uniformly distributed on $(0,1)$, you can take $R=\sqrt[n]{Ur_1^n +(1-U)r_0^n}$ as the radius of the random point.

You also need an $n$-dimensional random direction: one way of doing this is to take $n$ standard normally distributed random variables $X_i$ and divide each of them by their combined norm $\sqrt[2]{\sum_i X_i^2}$ to give a uniformly distributed direction vector.

Scale the random direction vector by the random radius and you have a uniformly distributed random point in this thick shell, though for large $n$ the curse of dimensionality means that it is more likely to be near the outside than the inside of the shell.

$\endgroup$
  • $\begingroup$ Is it possible to somehow cancel out the effect of curse of dimensionality? I guess the behavior you describe is due the fact that the difference between the volume of the hypersphere with radius $r_1$ and the hypersphere with $r_0$ becomes more and more significant as the number of dimensions increase. In spite of that is the uniform distribution still valid in higher dimensions? $\endgroup$ – plasmacel Aug 8 '16 at 14:55
  • $\begingroup$ @plasmacel: Yes: (a) restrict yourself to 1-D cases; or (b) choose $R$ uniformly between $r_0$ and $r_1$ at the cost of no longer having a uniformly distributed point in the thick shell. The curse of dimensionality is that for $n \gt 1$ there is an unavoidably greater area/volume/hypervolume near the outside of the shell than near the inside. $\endgroup$ – Henry Aug 8 '16 at 15:01
  • $\begingroup$ In statistics, there is a real problem in that in high dimensional hyper-spheres and -cubes (used for "Big Data"), few uniformly distributed points are close enough to each other to make interpolation reliable. $\endgroup$ – Henry Aug 8 '16 at 15:06
  • 1
    $\begingroup$ Perhaps you meant you would reject samples if $r_0 \gt |x-x_0|$ or if $|x-x_0| \gt r_1$. If this acceptance region is within the hypercube, then the answer is "yes", for the reason you give. But a further problem is that for high dimensions, you will be rejecting almost all points in the hypercube. $\endgroup$ – Henry Sep 9 '16 at 13:44
  • 1
    $\begingroup$ @plasmacel It is easy enough. Just take the derivative of the cumulative distribution I gave for the radius and divide by the surface area of an $n$ dimensional unit ball. As a check, for $n=2$ it is $\frac{r}{\pi(r_1^2-r_0^2)}$ in the support. What you might do with it is another question $\endgroup$ – Henry May 10 '17 at 22:25

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.