Rejection Sampling From Conditional Distribution

I am familiar with rejection sampling in the univariate case, where we have a proposal $h(x)$ (which we can sample from) for the target density $p(x)$ such that $p(x)<Mh(x)$ at all $x$. We sample $x$ from $h$ and accept each sample with probability $p(x)/(Mh(x))$.

For he appplication of rejection sampling in the multivariate case, suppose we have a joint distribution on the continuous random variables $(X_1,X_2)$ specified by

$$X_1 \sim F(x_1)\\ X_2|\{X_1=x_1\} \sim Q(x_2|x_1)$$.

We can evaluate and simulate from $F$ and $Q$, and we know the maximum value that $Q(x_2|x_1)$ can take for any values of $x_2,x_1$.

How is rejection sampling used to obtain exact samples from the distribution $p(X_1|X_2=s)$ via rejection sampling?

Note that:

$$P(X_1=x_1,X_2=x_2)=F(X_1=x_1)Q(X_2=x_2|X_1=x_1)$$

Now, lets fix the value of $X_2$ to $s$ and calculate the true conditional distribution:

$$P(X_1=x_1,X_2=s)=F(X_1=x_1)Q(X_2=s|X_1=x_1)$$

$$P(X_1=x_1|X_2=s) = \frac{P(X_1=x_1,X_2=s)}{\int_{X_1} P(X_1=z,X_2=s) dz } := p(x_1;s)$$

(I am simply parameterizing $X_2$ for notational simplicity).

I assume you can at least get the numerator of $p(x_1;s)$ analytically within an unknown, positive normalizing constant $K$:

$$p(x_1,s)=Kp(x_1;s)\; \mathrm{where} \; K=\int_{X_1} P(X_1=z,X_2=s) dz$$

Then, you can use whatever means you want to estimate $K$ by numerically solving the integral, it will be a constant for this problem, so you can use a less than computationally efficient method of you need high accuracy.

The strategy will be to let $h(x_1)=F(x_1) \;\mathrm{ and } \;p(x_1)=p(x_1;s)$ in the rejection framework. Therefore, we need to find a suitable $M$, which will ensure $\frac{Mh(x_1)}{p(x_1)}>1$:

The target ratio is:

$$\frac{F(x_1)}{p(x_1)}=\frac{KF(x_1)}{F(x_1)Q(x_2=s|x_1)}=\frac{K}{Q(x_2=s|x_1)}$$

We need to know the lower bound of this fraction. Therefore, you will need to find the $x_1$ that maximizes the denominator:

$$Q^*:=\max_{x_1} Q(x_2=s|x_1)$$

If we set $M=\frac{Q^*}{K}$, then we get:

$$\frac{F(x_1)}{p(x_1)}=\frac{K}{Q(x_2=s|x_1)}\geq \frac{K}{Q^*} \implies \frac{Q^*}{K}F(x_1) \geq p(x_1)$$

So, you will apply your rejection framework by simulating from $F(X_1)$ and accepting that point with probability:

$$P(\mathrm{Accept} \; X_1) = \frac{Kp(x_1)}{Q^*F(x_1)}$$

• Beautiful, your methodology helped me reason through the process. – jII Sep 27 '15 at 2:36
• In the final equation, is the $K$ necessary? In particular, since $p(x_1)=p(x_1,s)/K$, does the numerator $Kp(x_1)$ reduce to $p(x_1,s)$? – jII Sep 28 '15 at 13:59
• @jesterII yes, you could re-write it like that...don't know why I didn't simplify it earlier. – user237392 Sep 28 '15 at 14:03