# Rejection Sampling

Suppose we have a target distribution $$P(X)$$ known up to a normalizing constant, i.e. $$P(X) = \frac{\tilde{P}(X)}{Z_P}$$ where we know $$\tilde{P}(X)$$. To do so, we need a proposal distribution $$Q(X)$$ from which we know how to sample from, and $$\exists \: k \: : \: kQ(X) \leq P(X)$$.

X0 = Q.sample
U  = Uniform[0, kQ(X0)].sample
if U0 < P_tilde(X0):
X = U0
else:
reject


To see that the samples which are accepted indeed have the same distribution as $$P(X)$$, we see that $Q(\text{Propose } X_0 \text{ and Accept } X_0) = Q(X_0 \text{ and Accept } X_0)\\ = Q(X_0)Q(\text{Accept } X_0|X_0) = Q(X_0)\frac{\tilde{P}(X_0)}{kQ(X_0)}=\frac{\tilde{P}(X_0)}{C}$ Where the last equality holds since there is a $$\frac{\tilde{P}(X_0)}{kQ(X_0)}$$ probability of a random variable sampled uniformly on $$[0, kQ(X_0)]$$ to be less than $$\tilde{P}(X_0)$$, which is the criteria for being accepted.

Marginalizing out $$X_0$$ from the above joint distribution, we get

$Q(\text{Accept } X_0) = \int Q(x_0 \text{ and Accept } x_0) \: dx_0 = \int Q(x_0)\frac{\tilde{P}(x_0)}{kQ(x_0)} \: dx_0 \\ = \frac{\int \tilde{P}(x_0)}{k} \: dx_0 = \frac{Z_P}{k}$

Finally we have $$Q(X_0|\text{Accept } X_0) = \frac{Q(\text{Accept } X_0)Q(\text{Accept } X_0|X_0)}{ Q(\text{Accept } X_0)} = \frac{\tilde{P}(X_0)}{k}\frac{k}{Z_P} = P(X_0)$$.

Notice that we explicitly have the acceptance probability, which is $$\frac{1}{k}$$ if we happen to know $$P$$ explicitly.

## Thoughts

• Put Mackay book example on the high rejection rate of high dimensional Gaussians.

Created: 2022-03-13 Sun 21:44

Validate