Can't understand why rejection sampling works

Question

I want to generate sample points $\{z_i\}$ in an arbitrary 2D shape, e.g. a circle centered at the origin with radius 1. Rejection sampling says:

• Look at 2 uniform random variables over $[0,1]$, $X$ and $Y$.
• Sample $X$ and $Y$, you get $x$ and $y$, let's say.
• Test if $x^2+y^2\leq 1$:
  • if yes, $z=(x,y)$.
  • if no, sample $X$ and $Y$ until the condition is satisfied.

Why does this work, i.e. why does this simulate sampling a random variable $Z$ that is uniformly distributed over a disc?

Answer 1

In general, to sample from a distribution with density $f(x,y)$ on support $\mathcal{S}$, if using a proposal distribution with density $h(x,y)$, we need to find $M$ such that

$$\sup_{(x,y) \in\mathcal{S}} \dfrac{f(x,y)}{h(x,y)} \leq M, $$

so that we can accept a proposed value with probability

$$\alpha = \dfrac{f(x,y)}{Mh(x,y)}\,. $$

Accepting with $\alpha$ is equivaluent to drawing $U \sim U[0,1]$ and accepting if $U < \alpha$.

I am assuming you understand this general premise of rejection sampling. So in this example of drawing samples from the circle using a uniform square proposal,

$$f(x,y) = \dfrac{1}{\pi} \cdot I(\underbrace{x^2 + y^2 <1}_{=\mathcal{S}}) \quad \text{ and }\quad h(x,y) = \dfrac{1}{4} I(-1 < x,y < 1)\,. $$

First, let's find $M$. In the support of $f$,

$$\sup_{x^2 + y^2 \leq 1} \dfrac{f(x,y)}{h(x,y)} = \sup_{x^2 + y^2 \leq 1} \dfrac{ I(x^2 + y^2 \leq 1)/ \pi}{1/4} = \dfrac{4}{\pi} := M\,. $$

So any proposed value from the square will be expected with probability $$ \dfrac{f(x,y)}{M{h(x,y)}} = \dfrac{I(x^2 + y^2 \leq 1)/\pi}{M/{4}} = I(x^2 + y^2 \leq 1)\,.$$

So for any value proposed in the support of $f$, $U\sim U[0,1]$ will always be less than $1$, so we will always accept. There is thus, no need to sample from a $U$, and whenever the sampled point is inside the circle, we can accept it straightaway.

Answer 2

First off you need your $x$ and $y$ distributed between $-1$ and $1$ ($[0,1]$ gives you a quarter of a circle since you're only looking at $y \ge 0$ and $x \ge0$ ).

Then you realise, that you've two lists of randomly distributed variables along the $X$ and $Y$ axis - two lines with a random distribution of points. Combine these and you've a square of randomly distributed points.

You then reject the bits of the square that don't lie within a circle centered at $(0,0)$ - hence the $x^{2}+y^{2}\le1$ - and all the points that satisfy this inequality will lie on the disc and, since the points on the square were uniformly distributed so too will those on the disc.

Answer 3

You have chosen any point in [0,1]x[0,1] with equal probability. Then you removed all of those who are outside the circle.

This does not alter the probability of being selected for each individual point inside the circle (ie: any point inside the circle has still the same probability of being chosen as any other)