How do I evaluate (prove to myself) that a method for picking uniformly distributed values is correct?

Question

To make this more specific, I show a broken procedure for generating random points in a circle and a correct (hopefully) procedure for generating random dates within an interval.

I'd like to be able to precisely explain why one of them is wrong and the other is not, given that they sound very similar. What is so special about polar coordinates, that is not true about the case with dates?

Point in Circle

When placing a random point within a circle, the following is incorrect approach.

Use polar coordinates. First, generate the distance from center of the circle as number in interval [0, r). Then, generate the angle as number in interval [0, 2*pi).

The problem with the method described is that half of such points would lie within distance r/2 from the center, but that is only 1/4 of the surface of the whole circle.

(Anyways, how can one come up with such argument or know for certain there isn't one? It is obvious when it is stated, but I cannot imagine coming up with it myself; I'd just accept the method as correct.)

Random Date

randomdate = startdate + new TimeInterval(
    days: random(from: 0 to: (enddate - startdate).days)
    hours: random(from: 0 to: 23)
    minutes: random(from: 0 to: 59)
)

When proving uniform distribution of values, what exactly am I trying to prove (how come that in the circle example I have to think of area density, which is not necessary in the date example) and how do I go about it, in a general case?

Answer 1

In the nonuniform point-in-circle example, what you do is take a uniform distribution of points on the rectangle $[0, R) \times [0, 2 \pi)$, and map them into the disc using the map $$ f(r, \theta) = (r \cos \theta, r \sin \theta).$$ The Jacobian of this map measures how "dense" the image is at a point compared to the source: we have $$ |D_f(r, \theta)| = \left \lvert \begin{matrix} \frac{\partial f_1}{\partial r} & \frac{\partial f_1}{\partial \theta} \\ \frac{\partial f_2}{\partial r} & \frac{\partial f_2}{\partial \theta} \end{matrix} \right \rvert = \left \lvert \begin{matrix} \cos \theta & -r \sin \theta \\ \sin \theta & r \cos \theta \end{matrix} \right \rvert = r (\cos^2 \theta + \sin^2 \theta) = r $$ and so there is a "stretch factor" independent of the angle, but proportional to the distance from the centre. A way to think about this is that if there was a 1cm coating of paint on the original rectangle $[0, R) \times [0, 2 \pi)$, and then we applied $f$, the paint on the resulting disc would only be $1/r$ cm thick at the point $(r \cos \theta, r \sin \theta)$.

A way to fix this is to use a modified map, corrected for this. For example, if we take $$ g(r, \theta) = (\sqrt{r} \cos \theta, \sqrt{r} \sin \theta) $$ then we find $$ |D_g(r, \theta)| = \left \lvert \begin{matrix} \frac{\partial g_1}{\partial r} & \frac{\partial g_1}{\partial \theta} \\ \frac{\partial g_2}{\partial r} & \frac{\partial g_2}{\partial \theta} \end{matrix} \right \rvert = \left \lvert \begin{matrix} \frac{\cos \theta}{2 \sqrt{r}} & -\sqrt{r} \sin \theta \\ \frac{\sin \theta}{2 \sqrt{r}} & \sqrt{r} \cos \theta \end{matrix} \right \rvert = \frac{1}{2} (\cos^2 \theta + \sin^2 \theta) = \frac{1}{2} $$ And so we get an even distribution of paint (onto disc of radius $\sqrt{R}$, rather than $R$).

Answer 2

This is easy to see with some pictures, but actually proving a drawing methodology is correct requires some calculus.

To make the proof you want, you have to start with a definition of what it is you actually want to prove. You want to prove a particular distribution occurs -- in particular a uniform distribution across a circle. So what does that actually mean?

A uniform distribution across a 2d surface means that, for any given area on that surface $A$, the portion of the probability density function (PDF) of our variable which is contained in $A$ is proportional to the size of the area within $A$, which is notated $|A|$. This means, for any area you pick, the probability of the sampled point falling within that area is proportional to how big it is. This is written formally, $P(A) \propto |A|$.

Note that in this notation, $A$ is fundamentally describing a particular area on the surface while $|A|$ describes the numeric size of that area. $A$ might be "the surface of a basketball court" while $|A|$ is "4700 square feet," which is 94 feet times 50 feet. Keeping track of the difference will be helpful going forward because we'll be introducing more related notation.

You also will want another requirement. Since you want the probability to be 0 outside of the circle, we know that if we pick our area to be the whole circle, the probability that the sampled point falls into this area is 1. Formally, given an area $C$ which is the entire circle, $P(C) = 1$.

With these two equations, $P(A) \propto |A|$ and $P(C) = 1$, we can combine them to get $P(A) = \frac{|A\cap C|}{|C|}$, that is to say the probability of the sample being anywhere in an arbitrary area is equal to the size of the area that intersects the cricle divided by the size of the area of the circle itself. This is the fundamental equation we are trying to prove is true. For convenience going forward, if I can reasonably assume that $A$ is fully contained in the circle, I may abbreviate that equation to $P(A) = \frac{|A|}{|C|}$. I'll only include the "$\cup C$" part in situations where it isn't clear that $A$ is contained in $C$.

So with this, we can prove the validity of the "discard points" approach to generating uniform points along a circle. Here's a picture describing that case

In this picture we see that we sample in 2-d, discarding everything that falls into the red. Points in the middle are uniformly distributed. I've checkerboxed the area to show samples of areas that we might use to prove this. The probability of the point appearing in any one of these boxes is proportional to its area.

Now its area is equal to the width times the height. This is the fundamental reason why drawing 2 1-d uniform values in cartersian space works. You can break the problem into widths and heights independently.

Cartesian coordinates aren't the only ones where this works. Any linearly independent cooardinate system has this property. For example, if you picked your 2 1-d uninform distributions and mapped them with an affine coordinate system (which are linear, but the axes don't intersect at right angles), you'd get a uniform distribution as well:

However, to the transforms you are interested in, you're mapping a circle to a square. The reason for this is obvious. If you don't want to discard points, then you need to map your circle to the entire 2-d space that a pair of uniform distributions can attain.

As an aside, if this is for a computer program, the best answer is to discard the points. You'll spend much more CPU time trying to map a square to a circle than you'd spend discarding 21% of the points. However, in higher dimensions, the difference between a n-sphere and a n-cube get far worse. In the case of a 3d sphere and a 3d cube, you'll discard 48% of your points. If you had a 4d space, it'd be 70% and in 5d spaces it's 83%. This effect is known as the curse of dimensionality, and is a really useful thing to know going forward with statistics.

So what about your transformation, where you sample radius, sample angle, and map that with polar coordinates? In this case, your transform is the transformation from polar coordinates (where $R$ is the desired circle radius):

$$x^\prime = Rx\cdot\cos(2\pi y)$$ $$y^\prime = Rx\cdot\sin(2\pi y)$$

Note what happened here to the boxes. They got distorted. This is why you got the non-uniform distribution. You started with a nice uniform 2d space, but then you distorted it non-linearly.

So how do you fix this? This is where the calculus comes in.

Consider really really really small $A$ areas. In fact, consider "infinitesimally small" areas. Calculus is the study of how such infinitesimals operate. We call this infinitesimal area $dA$, where the $d$ basically notes that this is infinitesimally small and requires calculus to make meaningful.

Using calculus, we can integrate the probability density function over our circle. We can write $\int_{circle}P_A(A)dA = 1$, which says if we add up (integrate) the probability density function values (the $P_A(A)$ part) over small areas(the $dA$ part), times the size of the area itself, the result should equal one. If you're not thinking in calculus terms, this could be done by summing over a finite number of areas $a_1, a_2\ldots a_n$ to get $\sum_{i=1}^n(P_A(a_i)\cdot|a_i|) = 1$ if that is more familiar. It's the same pattern, multiplying a PDF value times the size of an area. However, this is one of the cases where calculus makes things easier, because the equations end up being much simpler.

Of course, we can then solve this to figure out a function for $P_A$. We know $P_A$ should be a constant value, because its a uniform distribution. By taking a derivative, we can reach the intuitive answer: $P_A(A) = \frac{1}{|C|}$ Intuitively if we integrate (or add up) a bunch of $\frac{1}{|C|}\cdot |A|$ values over a circle of size $|C|$, we end up with a total of $\frac{1}{|C|}\cdot|C|=1$

Now note that I subscripted the PDF function, $P_A$. $P_A$ is a function of area. We can change variables to get a PDF function in different variables. The obvious one is cartesian coordinates, x and y. We can do this by figuring out what to substitute in for $dA$. If you've done multivariable calculus, the obvious answer is $dA = dx dy$. If you haven't done multivariable calculus, it should at least seem reasonable that the area of a small region is its size in x multiplied by its size in y. This leads us to the equation $\int\int P_{xy}(x, y)dx dy = 1$. Here I've switched from a PDF which accepts an area $A$ to one which accepts two arguments, x and y. Using the same logic we used to find $P_A$, it's easy to find $P_{xy}$: $P_{xy}(x, y) = \frac{1}{|C|}$. This is nothing profound. It's really just the basis for the solution we showed above, where we reject all points outside of the circle. It shows that we can draw x and y uniformly, then combine them into a point and get a uniform 2d distribution.

The profound bit is coming when we decided to switch to polar. You wanted to do a polar conversion, so we need to think in polar coordinates. So we do another change of variables. One's first instinct might be to declare $dA=dr d\theta$, but that would actually be wrong. The correct answer is $dA=r dr d\theta$. Why? Informally, think about polar coordinates as a bunch of nested rings, each of the same thickness. The inner rings are smaller, so they have a smaller area than the larger rings. In fact, if you have a ring of radius $r$ and you look at a ring of radius $2r$, you see that the larger ring has twice the area of the first. The area of any ring is $2\pi r \Delta r$, where $Delta r$ is the width of the ring. Note that r term that appeared in that equation. That's where the r in $r dr d\theta$ comes from.

More formally, this is what we call the Jacobian. If I do a change of variables to transform from one coordinate system to another, I have to multiply the value of the integrand by the determinate of the Jacobian matrix. If you do the calculus, this determinate is $r$ for converting from rectangular to polar. If you calculate the Jacobian for the cartesian coordinate system (x and y) transform, it turns out to be $1$, which is why we didn't see it before.

So this means $\int_{circle}P_A(A)dA = 1$ transforms to $\int_{circle}P_{r\theta}(r, \theta)\cdot r dr d\theta = 1$. **It is that extra $r$ term which is why your distribution wasn't looking uniform. You must take it into consideration.$$ As before, we want the probability of any point being the same, so we know $P_{r \theta}(r, \theta)=\frac{k}{|C|}$. Thus our final integral is $\int_{circle}\frac{k}{|C|}r dr d\theta = 1$. Note that this is $\frac{k}{|C|}$ rather than $\frac{1}{|C|}$. It turns out that, to make the probabilities for $P_r$ to sum to 1, we actually need $k=2$. Thus $P_{r}(r) = \frac{2r}{|C|}$

Now for the key to making this work, I'm going to define a new PDF, $P_r(r)=\frac{2}{|C|}r$. This is a non-uniform random variable. Using this, I rewrite the above integral as simply $\int_{circle}P_r(r) dr d\theta = 1$. The reason I rewrite it this way is two fold:

• It makes it clear that the larger rings need to have a higher probability
• It is in the form of "integrate a probability density function over an area," which we had before.

Now we can apply Inverse Transform Sampling to generate this distribution from a random distribution. The process is as follows:

• Compute the CDF of the desired distribution. This means integrating $CDF(R) = \int_0^R \frac{2r}{|C|}dr$ which means $CDF(R) = \frac{R^2}{|C|}$
• Invert this CDF, $CDF^{-1}(x) = |C|\sqrt x$
• Take a random uniform variable X, transform it by $X^\prime = CDF^{-1}(X) = |C|\sqrt x$. The resulting distribution is now the distribution we need for $P_r$.

So what just happened? This all says that when we draw for radius and angle, we need to take the square root of the radius first, then transform it from polar to a circle in Cartesian coordinates.