# Rejection sampling + bootstrap

Suppose I want to draw $S_q$ samples from measure $q$, and that I already have available $S_p$ samples from a distribution $p$.

For a given constant $M$, I could use rejection sampling by drawing $S_p$ iid random variables $U[0, 1]$ and then accepting if the usual condition holds $$\text{Accept if: } u_s < \frac{q(x_s)}{Mp(x_s)} \> , \> \forall s=1,...,S_p$$

This procedure would get me, on average, about $\frac{S_p}{M}$. I could improve this marginally by choosing $$M^* = \max_{s=1,...,S_p} \frac{q(x_s)}{p(x_s)}$$

Hence, the largest sample from $q$ I could get would be around $\frac{S_p}{M^*}$, which still could be much lower than the desired $S_q$.

Enter the bootstrap. I was wondering if the above procedure could be modified like this:

• $s \leftarrow 0$
• $S = \{\}$
• While $s < S_q$
• Draw $u\sim U[0,1]$
• Draw with replacement a random $x_t$ from the $p$ samples.
• If $u < \frac{q(x_t)}{M^*p(x_s)}$
• Accept: $S \leftarrow S \cup\{x_t\}$
• $s \leftarrow s + 1$

So my question is: would this procedure give me "good" samples from $q$?

• Not "for a given constant $M$": it has to be an upper bound on $q/p$. – Xi'an Sep 3 '16 at 15:18
• The bootstrap approach is converging as $S_p$ grows to infinity but this is nonetheless an approximation of rejection-sampling, with little appeal since you need to simulate from $p$ and compute the acceptance ratio. – Xi'an Sep 3 '16 at 15:45
• Thanks. You are correct about this not being too appealing, but this is not for general use. It is just for this specific algorithm I have which already produces (about a million) samples from $p$, so I was thinking of a way of using those to obtain samples from this other distribution $q$ which is of interest. – mbiron Sep 3 '16 at 16:59