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.