# Accept-Reject Sampling

## Problem Statement

To sample from $$p(x)$$, where $$p(x)$$ is not easy to sample from, but given a sample $$x$$, the density of $$p(x)$$ is easy to evaluate.

## Accept-Reject Sampling

Given that $$p(x) \leq M q(x)$$ for $$0 < M < \infty$$, we can sample $$x \sim p(x)$$ by:

1. Sample $$X \sim q(x)$$, $$U \sim \mathcal{U}[0,1]$$.
2. Accept $$Y=X$$ if $$U < p(X) / M q(X)$$.
3. Return to 1 otherwise.

The correctness of this method can be proven by:

\begin{aligned} P(Y\leq y) &= P\left(X \leq y \,\Big|\, U \leq \frac{p(X)}{M q(X)}\right) = \frac{P\left(X \leq y, U \leq \frac{p(X)}{M q(X)}\right)}{P\left(U \leq \frac{p(X)}{M q(X)}\right)} \\ &= \frac{\int_{-\infty}^y \int_0^{p(x)/M q(x)} \mathrm{d}{u}\,q(x)\,\mathrm{d}{x}} {\int_{-\infty}^{\infty} \int_0^{p(x)/M q(x)} \mathrm{d}{u}\,q(x)\,\mathrm{d}{x}} = \frac{\frac{1}{M}\,\int_{-\infty}^y p(x)\,\mathrm{d}{x}} {\frac{1}{M}\,\int_{-\infty}^{\infty} p(x)\,\mathrm{d}{x}} = \int_{-\infty}^y p(x)\,\mathrm{d}{x} \end{aligned}

The average acceptance rate $$\propto 1/M$$, so a smaller $$M$$ can lead to lower time consumption. On the other hand, the target distribution $$p(x)$$ need not be normalized; $$M$$ can be often estimated again by sampling from $$q(x)$$ in applications, by $$M = \max p(x) / q(x)$$.