What is the probability that a random point in a circle?

Please log in or register to answer this question.

Índice Show

Please log in or register to answer this question.
Related questions
Tools/Functions Provided
The New PDF

← Previous in categoryNext in category →

Suppose you’re given the centre of the circle C (xc,yc). You are also given its radius R. How do you return a random point in a circle (each point in the circle should have the same probability of being returned)?

Tools/Functions Provided

Assume that a function f is provided which returns a random value between 0 and 1.

Approach

It is difficult to think in terms of cartesian coordinates, because the range of x is dependent on y and vice versa. So we think in terms of polar coordinates.

First, we choose a random distance r from the centre C. That is returned by f*R.

Now, we choose a random angle θ. This is returned by f*2π.

0≤r≤R, 0≤θ≤2*π

So, the random point (x,y) is given by (xc+r*cos(θ), yc+r*sin(θ)).

Problems?

The above approach seems good to go. However, does there seem to be a problem with it?

Suppose that distance r can take only two values, R/3 and 2*R/3. So what is the probability that the point is selected from the outer circle (with radius 2*R/3) ? It’s exactly 1/2, because distance is randomly chosen from the two values with equal probability. But this doesn’t seem right, does it?

Inner circle has radius R/3, while outer circle has radius 2*R/3.

If the outer circle has twice the radius, it also has twice the circumference. So, probability of selecting a point from the outer circle(r = 2*R/3) should be double than that of selecting a point from the inner circle(r = R/3).

This shows that the probability distribution function should not be constant with distance, but should be directly proportional to distance.

The New PDF

So, our new probability density function is proportional to distance. Let’s call this probability density function p(r). Then we have:

p(r) = k*r
∫k*r*dr = 1
k = 2/R²

So, our pdf becomes 2*r/R², where r is the radial distance of the point. Our cumulative distribution function now becomes ∫p(r)*dr = r²/R².

Using sqrt(f)*r gives a point at distance x with probability 2*x/R². The proof of this will be covered in the next blog.

Thus, the final desired generation would be:

θ = 2*π*f
r = sqrt(f)*R
x = xc + r*cos(θ)
y = yc + r*sin(θ)

Next article coming soon.

Think about it this way. If you have a rectangle where one axis is radius and one is angle, and you take the points inside this rectangle that are near radius 0. These will all fall very close to the origin (that is close together on the circle.) However, the points near radius R, these will all fall near the edge of the circle (that is, far apart from each other.)

This might give you some idea of why you are getting this behavior.

The factor that's derived on that link tells you how much corresponding area in the rectangle needs to be adjusted to not depend on the radius once it's mapped to the circle.

Edit: So what he writes in the link you share is, "That’s easy enough to do by calculating the inverse of the cumulative distribution, and we get for r:".

The basic premise is here that you can create a variable with a desired distribution from a uniform by mapping the uniform by the inverse function of the cumulative distribution function of the desired probability density function. Why? Just take it for granted for now, but this is a fact.

Here's my somehwat intuitive explanation of the math. The density function f(r) with respect to r has to be proportional to r itself. Understanding this fact is part of any basic calculus books. See sections on polar area elements. Some other posters have mentioned this.

So we'll call it f(r) = C*r;

This turns out to be most of the work. Now, since f(r) should be a probability density, you can easily see that by integrating f(r) over the interval (0,R) you get that C = 2/R^2 (this is an exercise for the reader.)

Thus, f(r) = 2*r/R^2

OK, so that's how you get the formula in the link.

Then, the final part is going from the uniform random variable u in (0,1) you must map by the inverse function of the cumulative distribution function from this desired density f(r). To understand why this is the case you need to find an advanced probability text like Papoulis probably (or derive it yourself.)

Integrating f(r) you get F(r) = r^2/R^2

To find the inverse function of this you set u = r^2/R^2 and then solve for r, which gives you r = R * sqrt(u)

This totally makes sense intuitively too, u = 0 should map to r = 0. Also, u = 1 shoudl map to r = R. Also, it goes by the square root function, which makes sense and matches the link.