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