0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Not "for a given constant $M$": it has to be an upper bound on $q/p$. $\endgroup$ – Xi'an Sep 3 '16 at 15:18
  • $\begingroup$ 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. $\endgroup$ – Xi'an Sep 3 '16 at 15:45
  • $\begingroup$ 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. $\endgroup$ – mbiron Sep 3 '16 at 16:59

Your Answer

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

Browse other questions tagged or ask your own question.