Uniformly sampling from the unit disk

I was asked this puzzle in a recent quant interview and thought it would be interesting to solve this. We are asked to generate points that are uniformly distributed on the unit circle. This is a really elegant question.

A first approach would be to generate points from the unit square distribution - that is pick \(U_1 \sim U[0,1]\) and \(U_2 \sim U[0,1]\), and apply the transform \(U_1' = -1 + 2U_1\), \(U_2' = -1 + 2U_2\), so that the transformed random variables are \(U[-1,1]\). We then accept all points that satisfy \(u_1'^2 + u_2'^2 \leq 1\) and reject all points that violate this condition. However, this is not computationally efficient as we are wasting \(\frac{4 - \pi}{4} \approx 20\%\) of the points.

One thing is, if you divide circle in concentric rings of size \(\Delta R\), note that the further you are away from the origin, the more area the ring contains. However, we would like a distant ring to have the same density as a ring closer to the origin. So, we need to pick more points in the outer ring then in the inner ring. If we pick points with a probability proportional to the square of the distance from the origin, we should end up with a uniform scattering.

Let \(u = F(r) = r^2\). So, \(r = \sqrt{u}\). Thus, \(R \stackrel{def}{=} F^{-1}(U) = \sqrt{U}\) must have the CDF \(F_R(r) = r^2\) and density \(f_R(r) = 2r\). We also pick \(\Theta \sim U[0,2\pi]\). If we project the point \(\left(r, \theta \right)\) onto the \(x\)- and \(y\)-axis, then we have:

\[ \begin{align*} X &= \sqrt{U} \cos \Theta\\ Y &= \sqrt{U} \sin \Theta\\ \end{align*} \]

Then, we have:

\[ \begin{align*} f_{X,Y}(x,y) &= f_{R,\Theta}(r(x,y),\theta(x,y)) \frac{\partial(r,\theta)}{\partial(x,y)}\\ &= 2r \cdot \frac{1}{2\pi} \left|\begin{matrix} \frac{\partial}{\partial x} \frac{1}{\sqrt{x^2 + y^2}} & \frac{\partial}{\partial y} \frac{1}{\sqrt{x^2 + y^2}} \\ \frac{\partial}{\partial x} \arctan (y/x) & \frac{\partial}{\partial y} \arctan (y/x) \end{matrix}\right|\\ &= 2\sqrt{x^2 + y^2} \cdot \frac{1}{2\pi} \left|\begin{matrix} \frac{x}{\sqrt{x^2 + y^2}} & \frac{y}{\sqrt{x^2 + y^2}} \\ -\frac{y}{x^2 + y^2} & \frac{x}{x^2 + y^2} \end{matrix}\right|.\\ & = \frac{1}{\pi} \end{align*} \]

Numerical simulation

import numpy as np
import matplotlib.pyplot as plt
import matplotlib.patches as patches

u = np.random.uniform(low=0.0, high=1.0, size=10000)
r = np.sqrt(u)
theta = 2*np.pi*np.random.uniform(low=0.0, high=1.0, size=10000)
x = r * np.cos(theta)
y = r * np.sin(theta)

# Create fig and axes
fig, ax = plt.subplots()

# Use patches.Circle() to create the circle. The xy argument is a tuple for the center (x,y) and radius is a float
circle = patches.Circle((0.0, 0.0), radius = 1.0, fill=False)

# Add the circle to the axes
ax.add_patch(circle)

# Add the (x,y) samples to the axes using the 'scatter' method
ax.scatter(x, y, color='blue', s=2.5)

# Ensure the aspect ratio is equal so the circle isn't distorted
ax.set_aspect('equal', adjustable='box')

# Set the plot limits
ax.set_xlim(-1,1)
ax.set_ylim(-1,1)

plt.title('Uniform sampling from the unit circle')
plt.show()