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:


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


$$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:


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)}$$

  • $\begingroup$ Beautiful, your methodology helped me reason through the process. $\endgroup$ – jII Sep 27 '15 at 2:36
  • $\begingroup$ 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)$? $\endgroup$ – jII Sep 28 '15 at 13:59
  • $\begingroup$ @jesterII yes, you could re-write it like that...don't know why I didn't simplify it earlier. $\endgroup$ – user237392 Sep 28 '15 at 14:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.