<p>For the latter, <a href="https://mathoverflow.net/questions/136314/what-is-a-good-method-to-find-random-points-on-the-n-sphere-when-n-is-large/136333#136333">this discussion</a> is a good starting point.  For the former, I guess finding a random point in the ball, rounding it to a grid point, then checking that grid point is in the ball.</p>

CC BY-SA 3.0
2017-06-01T09:23:40.040Z
Your algorithm for the first problem will give a nonuniform distribution, as points near the boundary may have lower probability. You may fix it by starting with a random point in a ball with radius $R+1$ rather than $1$. Either way, this will have good probability of success only if $R=\Omega(d)$ or so.
Emil Jeřábek
CC BY-SA 3.0
2017-06-01T09:44:12.760Z
I meant, rather than $R$, of course.
Emil Jeřábek
CC BY-SA 3.0
2017-06-01T09:47:20.723Z
True, I suppose you could use $R + (n\delta)^{1/n}$ as your sampling ball radius, i.e., add a grid-cell diagonal width ...
jjg
CC BY-SA 3.0
2017-06-01T09:51:05.070Z
You are right, it should be the diagonal width. That is $\sqrt{d}$ (though actually half of it is enough). What is $n$ and $\delta$?
Emil Jeřábek
CC BY-SA 3.0
2017-06-01T10:59:22.963Z
$\delta$ the grid separation, $n$ the dimension (I see I should have used $d$ for that)
jjg
CC BY-SA 3.0
2017-06-01T13:51:12.080Z
Of course that should be $R+(d \delta)^{1/2}$ ....
jjg
CC BY-SA 3.0
2017-06-01T13:53:07.623Z
I see. Since the OP didn’t mention it, I assumed the grid has unit separation, but this doesn’t really matter as everything scales linearly with $\delta$. So, the radius needs to be $R+\frac\delta2\sqrt d$. The expected number of trials is exponential in $\approx d^{3/2}\delta/R$, hence it works well for $R/\delta=\Omega(d^{3/2})$.
Emil Jeřábek
CC BY-SA 3.0
2017-06-03T20:33:31.357Z
@jjg. Thank you so much for your comments. I know that we can sample a random point in a bigger ball B'. But I have no ideas about how much larger of the ball B'. Could you please give some hints? Thanks.
damuzhi
CC BY-SA 3.0
2017-06-03T20:35:20.077Z
@Emil Jeřábek. Thank you so much for your comments. Could you please explain more detail about squrt (d)/2  is enough? Thanks.
damuzhi
CC BY-SA 3.0
2017-06-05T16:38:59.333Z
@PengfeiGu The rejection-sampling-with-rounding algorithm works correctly if the sampled body (here, the larger ball) includes all points $x$ whose nearest grid-point $x'$ is in the target ball of radius $R$. Now, $x-x'$ is a vector whose all coordinates are at most $1/2$ in absolute value (assuming unit grid), hence of Euclidean norm at most $\frac12\sqrt d$. Thus, all such $x$ are included in the ball with radius $R+\frac12\sqrt d$ by the triangle inequality.
Emil Jeřábek
CC BY-SA 3.0
2017-05-31T22:36:34.247Z
2017-05-31T22:36:34.247Z
jjg
<p>In view of a circle with center $(a,b)$ and radius $r$, the points $(x,y)$ on the circle fulfill
$(x-a)^2 + (y-b)^2 = r^2$.
In parametric form, the points are given by $x=a+r\cos\phi$ and $y=b+r\sin\phi$ with angle $\phi$ between 0 and $2\pi$.</p>

<p>Thus finding a random point in the circle is to choose an angle $\phi$ uniformly at random and a number $d$ with $0\leq d\leq r$ uniformly at random. </p>

CC BY-SA 3.0
2017-06-02T17:14:27.543Z
This will not give uniform distribution on the disk. You need larger $d$ to have larger probability.
Emil Jeřábek
CC BY-SA 3.0
2017-06-02T20:28:27.923Z
Indeed, I knew it but have no solution here.
Wuestenfux
CC BY-SA 3.0
2017-06-02T23:36:37.113Z
Why would you post something you know to be wrong? Not to mention it's an easy special case of the other answer.
Sasho Nikolov
CC BY-SA 3.0
2017-06-03T06:28:28.323Z
Easy approximation.
Wuestenfux
CC BY-SA 3.0
2017-06-02T11:56:32.283Z
2017-06-02T11:56:32.283Z
Wuestenfux
<p>I would like to know if there any algorithm to pick a random grid point inside a d-dimensional ball with a given radius R.  And if there any algorithm to pick a random arbitrary point inside a d-dimensional ball with a given radius R. </p>

<p>Thanks.</p>

CC BY-SA 3.0
2017-06-01T19:00:53.113Z
I was also interested in such an algorithm, and I would be pleased if someone could provide at least something close to pseudo code. Browsed almost whole stack overflow and couldn't find anything getting me closer to the answer.
Brian Atkins
CC BY-SA 3.0
2017-06-03T17:13:22.687Z
http://blog.geomblog.org/2013/01/a-sampling-gem-sampling-from-ellp-balls.html
Kaveh
CC BY-SA 3.0
2017-06-12T11:27:54.590Z
The posted answer works well for $R > d^{3/2}$. for smaller $R$, you might want to use the Metropolis algorithm — that should be much more efficient in this case.
Peter Shor 
<randomized-algorithms>
Random point in a d-dimensional ball
damuzhi
# Random point in a d-dimensional ball

(Asked by: username_0 on 2017-05-31)

I would like to know if there any algorithm to pick a random grid point inside a d-dimensional ball with a given radius R. And if there any algorithm to pick a random arbitrary point inside a d-dimensional ball with a given radius R.

Thanks.

**Tags:** randomized-algorithms
> **Comments:**
> **username_1**: I was also interested in such an algorithm, and I would be pleased if someone could provide at least something close to pseudo code. Browsed almost whole stack overflow and couldn't find anything getting me closer to the answer.  
> **username_2**: http://blog.geomblog.org/2013/01/a-sampling-gem-sampling-from-ellp-balls.html  
> **username_3**: The posted answer works well for $R > d^{3/2}$. for smaller $R$, you might want to use the Metropolis algorithm — that should be much more efficient in this case.  

---

## 2 answers

### Answer by username_4 on 2017-05-31. Score: 5

For the latter, [this discussion](https://mathoverflow.net/questions/136314/what-is-a-good-method-to-find-random-points-on-the-n-sphere-when-n-is-large/136333#136333) is a good starting point. For the former, I guess finding a random point in the ball, rounding it to a grid point, then checking that grid point is in the ball.

> **Comments:**
> **username_5**: Your algorithm for the first problem will give a nonuniform distribution, as points near the boundary may have lower probability. You may fix it by starting with a random point in a ball with radius $R+1$ rather than $1$. Either way, this will have good probability of success only if $R=\Omega(d)$ or so.  
> **username_5**: I meant, rather than $R$, of course.  
> **username_4**: True, I suppose you could use $R + (n\delta)^{1/n}$ as your sampling ball radius, i.e., add a grid-cell diagonal width ...  
> **username_5**: You are right, it should be the diagonal width. That is $\sqrt{d}$ (though actually half of it is enough). What is $n$ and $\delta$?  
> **username_4**: $\delta$ the grid separation, $n$ the dimension (I see I should have used $d$ for that)  
> **username_4**: Of course that should be $R+(d \delta)^{1/2}$ ....  
> **username_5**: I see. Since the OP didn’t mention it, I assumed the grid has unit separation, but this doesn’t really matter as everything scales linearly with $\delta$. So, the radius needs to be $R+\frac\delta2\sqrt d$. The expected number of trials is exponential in $\approx d^{3/2}\delta/R$, hence it works well for $R/\delta=\Omega(d^{3/2})$.  
> **username_0**: @jjg. Thank you so much for your comments. I know that we can sample a random point in a bigger ball B'. But I have no ideas about how much larger of the ball B'. Could you please give some hints? Thanks.  
> **username_0**: @Emil Jeřábek. Thank you so much for your comments. Could you please explain more detail about squrt (d)/2  is enough? Thanks.  
> **username_5**: @PengfeiGu The rejection-sampling-with-rounding algorithm works correctly if the sampled body (here, the larger ball) includes all points $x$ whose nearest grid-point $x'$ is in the target ball of radius $R$. Now, $x-x'$ is a vector whose all coordinates are at most $1/2$ in absolute value (assuming unit grid), hence of Euclidean norm at most $\frac12\sqrt d$. Thus, all such $x$ are included in the ball with radius $R+\frac12\sqrt d$ by the triangle inequality.  

---

### Answer by username_6 on 2017-06-02. Score: -9

In view of a circle with center $(a,b)$ and radius $r$, the points $(x,y)$ on the circle fulfill
$(x-a)^2 + (y-b)^2 = r^2$.
In parametric form, the points are given by $x=a+r\cos\phi$ and $y=b+r\sin\phi$ with angle $\phi$ between 0 and $2\pi$.

Thus finding a random point in the circle is to choose an angle $\phi$ uniformly at random and a number $d$ with $0\leq d\leq r$ uniformly at random.

> **Comments:**
> **username_5**: This will not give uniform distribution on the disk. You need larger $d$ to have larger probability.  
> **username_6**: Indeed, I knew it but have no solution here.  
> **username_7**: Why would you post something you know to be wrong? Not to mention it's an easy special case of the other answer.  
> **username_6**: Easy approximation.  

---

