# Can't understand why rejection sampling works

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?

• @AdamO I think the WLLN is irrelevant, because the question is about the procedure and not about limiting properties of the data. It suffices to demonstrate that when $A$ is a measurable set in the plane, this procedure draws points independently from $A$ with probability proportional to the area of $A \cap D^2$ (where $D^2$ is the unit disk in question). – whuber Feb 25 '19 at 17:21
• @AdamO, the OP hasn't expressed interest in measuring the area of a circle. They prefaced the question with "I want to generate samples". If they were interested in estimating the area, then your comment is valid, given they understand how the samples obtained by rejection sampling are representative. However, they want to know, why the samples obtained are representative. – Greenparker Feb 25 '19 at 18:11
• @Greenparker thanks I see why I misunderstood the question. – AdamO Feb 25 '19 at 18:33

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.

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.

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)