10
$\begingroup$

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.

  • 0
    @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.2010-07-20
  • 0
    @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.2010-07-21
  • 0
    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 :)2010-07-21
  • 0
    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.2012-09-08

3 Answers 3

17

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).

  • 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.2010-07-21
  • 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.2011-11-10
  • 0
    @BlueRaja-DannyPflughoeft Nice answer. Deserves +50 bounty and an upvote from my side. Will reward tomorrow.2013-12-23
3

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.

0

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.