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.
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
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.
The overall probability of accepting a draw is $1/M$.
Rejection Sampling Theorem
The rejection sampling procedure described above produces draws from $X$ with density $h$.
A routine limiting argument (letting $\epsilon \rightarrow 0$) shows that this implies that $X$ has density $h$.
blog comments powered by Disqus