Random grid point in a d-dimensional ball I would like to know if there is any standard algorithm to generate
a random grid point inside a d-dimensional ball with a given radius r.

Thanks

Bin Fu
Let $B$ be the ball you want to sample in. Let $B'$ be the ball centered at the same point, but larger in radius by $\sqrt{d}$. Sample a random point in $B'$ Round off to the nearest integer point. Now, if this integer point is in $B$, accept it. Otherwise, discard it and try again.

This works because every point of the original ball is contained in a unit cube in ball $B'$. 

When will this be efficient? You want the ball of $r+ \sqrt{d}$ to be not too much larger than the ball of radius $r$. The ratio of these distances is 

$$ \left(\frac{r+\sqrt{d}}{r}\right)^d = \left(1 + \frac{\sqrt{d}}{r}\right)^d \leq \exp\left({\frac{d^{3/2}}{r}}\right).$$

So it works well if $r &gt; d^{3/2}$.

How do you find a random point in $B'$? Thomas's answer give an algorithm for this.



If $r &lt; d^{3/2}$, use the Metropolis algorithm. Start with a point $P$ in the ball&mdash;the lattice point closest to the center is easiest. Now, repeatedly perform the following steps.


Choose a random coordinate.
Keeping the remaining coordinates fixed, compute the lowest and highest integer values for this coordinate that are still in the ball.
Pick a random value $v$ for this coordinate, and set this coordinate to $v$ in $P$.


This is guaranteed to converge, and there are theorems that will tell you how quickly it will converge ... I am fairly sure that this case is one that converges in polynomial time.