# Random multivariate in hyperannulus

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?

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.

• 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? – plasmacel Aug 8 '16 at 14:55
• @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. – Henry Aug 8 '16 at 15:01
• 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. – Henry Aug 8 '16 at 15:06
• 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. – Henry Sep 9 '16 at 13:44
• @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 – Henry May 10 '17 at 22:25