probability puzzles
hard | probability |
& are two random points selected uniformly between & . Using them, create a point uniformly random in a circle of radius . (uniform means that the probability density is constant)
Convert Cartesian coordinates to Polar coordinates. And the area of a circle grows with the square of its radius.
and , then take the point as
We could generate a random point in the square and reject it if it is not in the circle. However, the question asks to transform the point, not filter it. We need to somehow manipulate the given random point
Initial Misstep
The coordinates of the point in the circle are then given by where is the radius and is the angle. Thus, we can use polar coordinates, can be converted to the angle and can be used as the radius.
-
Let , its value ranged between to
-
Let , the radius in the polar coordinates, its value is between 0 and 1.
-
The Polar Coordinate can be converted to the cartesian coordinate. Thus, will generate a random point within the disk of radius 1.
-
However, to ensure uniform distribution, we can't just take . This is because points near the center of the circle are much more likely to be chosen if we just use a uniform distribution for the radius. Consider a small ring in the circle with radius and thickness . The area of this ring (which is a very thin circular strip) is . A larger ring has more area and should contain more points. If we take , we end up with the same number of points in each ring. This means that larger rings have a lower density of points. This is not uniform.
Correct Solution
We wish to use as the random point, but we need a way to make it uniform.
Uniform distribution means that the probability of finding a point in any part is proportional to the size of that part.
In the case of 1D range , given is uniform, i.e. (where )
We want the same property for the disk.
Consider an annulus (ring) between radius and (where )
We want the probability to be in proportion to this area, i.e. we want
Taking gives , which is not proportional to the area.
But, with a leap of faith, if we take , we get
(because is uniform in the range )
Thus, we get the desired property.
Therefore, we can take and to get a uniform distribution of points in the disk.