Tianyang Li
0%

Rejection Sampling

Posted on Edited on In /

1. Rejection Sampling

The basic idea of rejection sampling is to sample from a proposal distribution \(q\) different from the target \(\pi\) and then to correct through a rejection step to obtain a sample from \(\pi\).

Algorithm 1 (Rejection Sampling)    Given two densities \(\pi\) and \(q\) on \(\mathbb{X}\) with \(\pi(x) \leq Mq(x)\) for all \(x \in \mathbb{X}\) and some \(0<M<\infty\), we can generate a sample from \(\pi\) as follows:

  1. Draw \(X \sim q\) and \(U \sim \mathcal{U}_{[0, 1]}\).

  2. Accept \(X=x\) as a sample from \(\pi\) if \(\displaystyle U \leq \frac{\pi(X)}{Mq(X)}\);

Theorem 1.1 (Rejection Sampling)    The distribution of the samples accepted by rejection sampling is \(\pi\).

Proof. For any measurable set \(A \subset \mathbb{X}\), we have \[\mathbb{P}(X \in A \mid X\ \text{is accepted})=\frac{\mathbb{P}(X \in A, X\ \text{is accepted})}{\mathbb{P}(X\ \text{is accepted})}.\] Since \[\begin{aligned} \mathbb{P}(X \in A, X\ \text{is accepted})&=\int_\mathbb{X}\int_0^1 \mathbb{I}_A(x) \mathbb{I}_{U \leq \frac{\pi(X)}{Mq(X)}}(u)q(x)\text{d}u\text{d}x \\&=\int_\mathbb{X} \mathbb{I}_A(x)\frac{\pi(x)}{Mq(x)}q(x)\text{d}x \\&=\int_\mathbb{X} \mathbb{I}_A(x)\frac{\pi(x)}{M}\text{d}x \\&=\frac{\pi(A)}{M} \end{aligned}\] and \[\mathbb{P}(X\ \text{is accepted})=\mathbb{P}(X \in \mathbb{X}, X\ \text{is accepted})=\frac{\pi(\mathbb{X})}{M}=\frac{1}{M},\] then \[\mathbb{P}(X \in A \mid X\ \text{is accepted})=\frac{\pi(A)/M}{1/M}=\pi(A).\] Hence the distribution of the accepted values is \(\pi\).

\(\square\)

If we only know \(\pi\) and \(q\) up to some normalizing constant, i.e. \(\displaystyle \pi=\frac{\widetilde{\pi}}{Z_\pi}\) and \(\displaystyle q=\frac{\widetilde{q}}{Z_q}\) where \(\widetilde{\pi}\) and \(\widetilde{q}\) are known, but \(\displaystyle Z_\pi=\int_\mathbb{X} \widetilde{\pi}(x)\text{d}x\) and \(\displaystyle Z_q=\int_\mathbb{X} \widetilde{q}(x)\text{d}x\) are unknown. We can still use rejection sampling since \[\frac{\widetilde{\pi}(x)}{\widetilde{q}(x)} \leq \widetilde{M} \Leftrightarrow \frac{\pi(x)}{q(x)} \leq \widetilde{M}\frac{Z_q}{Z_\pi}=M.\]

Lemma 1.2    Let \(T\) denote the waiting time, that is the number of pairs \((X, U)\) that have to be generated until \(X\) is accepted for the first time. Then \(T\) is geometrically distributed with parameter \(\displaystyle \frac{1}{M}\) and \(\mathbb{E}[T]=M\).

In the unnormalized case, we have \[\mathbb{P}(X\ \text{is accepted})=\frac{1}{M}=\frac{Z_\pi}{\widetilde{M}Z_q}\] and \[\mathbb{E}[T]=M=\frac{Z_q\widetilde{M}}{Z_\pi}\] which can be used to provide unbiased estimates of \(\displaystyle \frac{Z_\pi}{Z_q}\).

2. Example

Example 2.1 (Normal Distribution)    Let \(\displaystyle \widetilde{\pi}(x)=\exp\left(-\frac{1}{2}x^2\right)\) and \(\displaystyle \widetilde{q}(x)=\frac{1}{1+x^2}\). We have \[\frac{\widetilde{\pi}(x)}{\widetilde{q}(x)}=(1+x^2)\exp\left(-\frac{1}{2}x^2\right) \leq \frac{2}{\sqrt{e}}=\widetilde{M}\] which is attained at \(\pm1\). Let \(X \sim \widetilde{q}\), then the probability of acceptance is \[\mathbb{P}\left(U \leq \frac{\widetilde{\pi}(x)}{\widetilde{M}\widetilde{q}(x)}\right)=\frac{1}{M}=\frac{Z_\pi}{\widetilde{M}Z_q}=\frac{\sqrt{2\pi}}{(2/\sqrt{e})\pi}=\sqrt{\frac{e}{2\pi}} \approx 0.66\] and the mean number of trials to success is approximately \(\displaystyle \frac{1}{0.66} \approx 1.52\).