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?
 A: 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)}$$
