Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider the task of generating random points uniformly distributed within a circle of a given radius $r$ that is centered at the origin. Assume that we are given a random number generator $R$ that generates a floating point number uniformly distributed in the range $[0, 1)$.

Consider the following procedure:

  1. Generate a random point $p = (x, y)$ within a square of side $2r$ centered at the origin. This can be easily achieved by:

    a. Using the random number generator $R$ to generate two random numbers $x$ and $y$, where $x, y \in [0, 1)$, and then transforming $x$ and $y$ to the range $[0, r)$ (by multiplying each by $r$).

    b. Flipping a fair coin to decide whether to reflect $p$ around the $x$-axis.

    c. Flipping another fair coin to decide whether to reflect $p$ around the $y$-axis.

  2. Now, if $p$ happens to fall outside the given circle, discard $p$ and generate another point. Repeat the procedure until $p$ falls within the circle.

Is the previous procedure correct? That is, are the random points generated by it uniformly distributed within the given circle? How can one formally [dis]prove it?


Background Info

The task was actually given in Ruby Quiz - Random Points within a Circle (#234). If you're interested, you can check my solution in which I've implemented the procedure described above. I would like to know whether the procedure is mathematically correct or not, but I couldn't figure out how to formally [dis]prove it.

Note that the actual task was to generate random points uniformly distributed within a circle of a given radius and position, but I intentionally left that out in the question because the generated points can be easily translated to their correct positions relative to the given center.

share|improve this question
    
@jacob surely you mean -pi and +pi or 0 and 2pi? And that was exactly what I was thinking :) You have to jump through hoops to do this in Cartesian co-ords, while it is trivial in polar co-ordinates. –  workmad3 Jul 20 '10 at 23:18
    
@workmad3 yeah, -pi and +pi. But I deleted it as my suggestion wasn't uniform and I couldn't work out how to make it uniform. –  Jacob Jul 21 '10 at 17:42
    
I wasn't sure how to get uniformity either, which is why I was looking at suggesting polar co-ords in a comment rather than a complete answer :) –  workmad3 Jul 21 '10 at 22:00
    
Of course, in step 1 you can simply set $x=2r\cdot R-r$, $x=2r\cdot R-r$ instead of generating the signs separately. –  Hagen von Eitzen Sep 8 '12 at 7:13

3 Answers 3

Yes this will work; it's called rejection sampling.

Even better is to generate a point in polar coordinates though: pick θ from [0, 2π) and r2 from [0, R2] (ie. multiply R by the square-root of a random number in [0, 1] - without the square-root it is non-uniform).

share|improve this answer
1  
+1 for nailing down "rejection sampling." I don't think that I would've been able to find the term myself. Still, I can't figure out how to establish, from the rejection sampling procedure, that the uniform distribution of the generated points follows from the uniform distribution of the random number generator. –  Yaser Sulaiman Jul 21 '10 at 18:17
2  
@Yaser: Every non-rejected point trivially has equal probability of being chosen; that is the definition of uniform. The only thing we lose is a guarantee of how long a number will take to generate. –  BlueRaja - Danny Pflughoeft Nov 10 '11 at 22:34
    
@BlueRaja-DannyPflughoeft Nice answer. Deserves +50 bounty and an upvote from my side. Will reward tomorrow. –  Ahaan S. Rungta Dec 23 '13 at 12:23

I'm not saying that your method is the simplest one to obtain uniformly distributed sample points in the disk $D$ of radius $r>0$, but it is certainly correct.

Let $Q:=[{-r},r]^2$ and assume that the points generated in step 1. of your procedure are uniformly distributed in $Q$. For any set $A\subset Q$ denote by $|A|$ the area of $A$ and by $P(A)$ the probability that a sample point $p$ falls on the set $A$. Then one has the well known formula about switching conditionals: $$P(A\,|\,D)={P(A)\>P(D\,|\,A)\over P(D)}\ .$$ Now when $A\subset D$ then $P(D\,|\,A)=1$, and by assumption $$P(A)={|A|\over|Q|},\quad P(D)={|D|\over|Q|}\ .$$ It follows that $$P(A\,|\,D)={|A|\over|D|}\qquad\forall \> A\subset D\ ,$$ as it should be.

share|improve this answer

I'm going to use $P(a,b)$ for probability of x = a, and y = b.

$P(a,b) = P[x = |a|]P[y = |b|] * 1/4$ for any a, b inside the square.

Therefore you are picking a coordinate uniformly inside the square.

Now the problem reduced to the following:

Pick a element uniformly in a set A, then discard ones that are not B (B is a subset of A). Is it the same as pick a element uniformly in the set $A \cap B = B$?

I think this is true, I don't know if the following is a formal proof(haven't done probability in a while). please point out my mistakes.

P(B) is the event that a element in B is picked. P(A) is the event that a element in A is picked.

Pick a x uniformly, we have b \in B is P(x=b|B), it's obviously uniform.

The conditional probability P(B|A) = P(A \cap B)/P(A) = P(B)/P(A) = P(B)

P(A) = 1, w/e you pick are in A.

P(x=b| (B|A)) = P(x=b|B), which is uniform.

Answer to your question: It is uniformly distributed.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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