Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have the following passage from a set of lecture notes I am working on that I would like to understand a little better.

$\underline{\text{Algorithm for Rejection Sampling}}$:

Given two densities $f$, $g$, with $f(x) < M.g(x)$ for all $x$, and some constant $M$, we can generate a sample from $f$ by

  1. Draw $X \sim g$

  2. Accept $X$ as a sample from $f$ with probability

    $\large \frac{f(X)}{M.g(X)}$

    otherwise go back to step 1.

Now, I understand why this will generate samples from the distribution with density $f$, but I really do not understand how to use this algorithm in practice.

I draw an $X$ from the distribution with density $g$, and then I need to decide whether to keep it, or reject it. I don't understand the condition to accept it... do I accept it if the probability defined in 2. is greater than e.g. 0.5, or maybe 0.7? Is this probability up to me to decide?

Thanks for your insight and thoughts.

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

The way it works is technically for step 2 you draw a uniform random variable on $[0,1]$ and if that random variable ends up being less than the quantity in part 2, you accept the sample. Equivalently, when you draw a proposal $X$, you plug it into part 2 and then throw a biased coin with probability of success equal again to part 2. So if the acceptance ratio is quite low, you're unlikely to accept and if its high, then you are likely to accept

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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