# Rejection Sampling Proof Math, CS, Data

In the rejection sampling procedure, we wish to sample from some distribution with density $h$. To accomplish this, we first sample from some dominating distribution with density $g$. First find a value $M$ such that $M g(x) \geq h(x)$ for all $x$. Now, for each draw $Y$ from $g$, you also draw a standard uniform $U$. If $U \leq h(x)/(Mg(x))$, then set $X$ equal to $Y$. Otherwise draw from $g$ again and repeat the process.

It is easy to show that rejection sampling works. First, we’ll need a couple of lemmas, both of which are quite interesting on their own.

## Lemma 1

If $A$ is a random variable whose support is a subset of $[0,1]$, and $U$ is a standard uniform random variable independent of $A$, then

### Proof

Let $f_A$ and $f_U$ be the densities of $A$ and $U$. Because they are independent, their joint density is equal to the product of the two marginal densities.

## Lemma 2

The overall probability of accepting a draw is $1/M$.

### Proof

## Rejection Sampling Theorem

The rejection sampling procedure described above produces draws from $X$ with density $h$.

### Proof

A routine limiting argument (letting $\epsilon \rightarrow 0$) shows that this implies that $X$ has density $h$.

blog comments powered by Disqus