Uniform Point in the Unit Disk Without Rejection
You have access to an i.i.d. source of uniform random variables $U_1, U_2 \sim \text{Unif}(0,1)$. Construct a function $(X, Y) = f(U_1, U_2)$ such that $(X, Y)$ is uniformly distributed over the unit disk $\{(x, y) \in \mathbb{R}^2 : x^2 + y^2 \le 1\}$, without using rejection sampling.
Prove that your construction produces a uniform distribution by deriving the joint density (or using a measure-preserving argument). Explicitly state any coordinate transformations you use.
Hints
- Think in polar coordinates -- what should the marginal distributions of $R$ and $\Theta$ be for a uniform point on the disk?
- The area element in polar coordinates is $r \, dr \, d\theta$. This means the radius is NOT uniformly distributed -- derive its CDF from the density $f_R(r) = 2r$.
- Use the inverse CDF method: if $F_R(r) = r^2$, then setting $R = \sqrt{U_2}$ and $\Theta = 2\pi U_1$ gives the correct joint density.
Worked Solution
How to Think About It: The naive approach -- generate $(U_1, U_2)$ uniformly on the unit square and reject points outside the disk -- wastes about $1 - \pi/4 \approx 21.5\%$ of samples. The question asks us to avoid this. The key idea is to work in polar coordinates $(R, \Theta)$ and figure out the right marginal distributions so that the resulting $(X, Y)$ is uniform on the disk.
A uniform point on the disk has density $f(x,y) = 1/\pi$ for $x^2 + y^2 \le 1$. In polar coordinates, the area element is $r \, dr \, d\theta$, so the joint density of $(R, \Theta)$ is $f(r, \theta) = r/\pi$ for $r \in [0,1]$, $\theta \in [0, 2\pi)$. Separating: $\Theta \sim \text{Unif}(0, 2\pi)$ and $R$ has density $f_R(r) = 2r$ for $r \in [0,1]$. The CDF of $R$ is $F_R(r) = r^2$, so $R = \sqrt{U}$ by the inverse CDF method.
Approach: Use inverse CDF sampling for the radius and a linear rescaling for the angle, both via uniform inputs.
Formal Solution:
1. Set up polar coordinates. We want $(X, Y)$ uniform on the unit disk. In polar coordinates, $X = R\cos\Theta$, $Y = R\sin\Theta$. The uniform density on the disk is: $$f_{X,Y}(x,y) = \frac{1}{\pi}, \quad x^2 + y^2 \le 1$$
2. Convert to polar. The Jacobian of the transformation $(r, \theta) \mapsto (r\cos\theta, r\sin\theta)$ is $r$. So the joint density in polar coordinates is: $$f_{R,\Theta}(r,\theta) = \frac{1}{\pi} \cdot r = \frac{r}{\pi}, \quad r \in [0,1], \; \theta \in [0, 2\pi)$$
3. Factor the joint density. Since $f_{R,\Theta}(r,\theta) = (2r) \cdot \frac{1}{2\pi}$, we see that $R$ and $\Theta$ are independent with: - $\Theta \sim \text{Unif}(0, 2\pi)$, so set $\Theta = 2\pi U_1$ - $R$ has PDF $f_R(r) = 2r$ on $[0,1]$, giving CDF $F_R(r) = r^2$
- Inverse CDF for $R$. Setting $F_R(R) = U_2$ gives $R^2 = U_2$, so $R = \sqrt{U_2}$.
5. Final construction: $$X = \sqrt{U_2}\cos(2\pi U_1), \quad Y = \sqrt{U_2}\sin(2\pi U_1)$$
6. Verification. The map $(U_1, U_2) \mapsto (\Theta, R^2) = (2\pi U_1, U_2)$ is measure-preserving (linear rescaling of Lebesgue measure). Since $R = \sqrt{U_2}$ and $\Theta = 2\pi U_1$ are the correct marginals and they are independent (because $U_1, U_2$ are independent), the joint density is: $$f_{R,\Theta}(r,\theta) = f_R(r) \cdot f_\Theta(\theta) = 2r \cdot \frac{1}{2\pi} = \frac{r}{\pi}$$ which corresponds to uniform density $1/\pi$ on the disk after the polar-to-Cartesian Jacobian factor.
Answer: Set $X = \sqrt{U_2}\cos(2\pi U_1)$ and $Y = \sqrt{U_2}\sin(2\pi U_1)$. The critical insight is that the radius needs CDF $F_R(r) = r^2$ (not uniform), because the area element in polar coordinates includes a factor of $r$. Taking $R = \sqrt{U}$ corrects for this.
Intuition
The reason you cannot just set $R = U$ (uniform radius) is geometric: there is more area near the boundary of the disk than near the center. A thin annulus at radius $r$ has area proportional to $r$, so you need to oversample larger radii. The CDF $F_R(r) = r^2$ encodes exactly this -- it is the fraction of the disk's area contained within radius $r$. Taking $R = \sqrt{U}$ is the inverse CDF trick applied to this distribution.
This pattern -- adjusting the radial distribution to account for the area element -- appears constantly in Monte Carlo simulation. The same logic applies to generating uniform points on spheres in higher dimensions (where the radial CDF becomes $r^d$ for a $d$-dimensional ball) and to importance sampling schemes where you want to concentrate samples in regions of high integrand value.