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)\).