# [R] Question about acception rejection sampling - NOT R question

Greg Snow Greg.Snow at intermountainmail.org
Mon Jul 16 20:51:56 CEST 2007

Not a strict proof, but think of it this way:

The liklihood of getting a particular value of x has 2 parts.  1st x has
to be generated from h, the liklihood of this happening is h(x), 2nd the
point has to be accepted with conditional probability f(x)/(c*h(x)).  If
we multiply we get h(x) * f(x)/ ( c* h(x) ) and the 2 h(x)'s cancel out
leaving the liklihood of getting x as f(x)/c.  The /c just indicates
that approximately 1-1/c points will be rejected and thrown out and the
final normalized distribution is f(x), which was the goal.

Hope this helps,

--
Gregory (Greg) L. Snow Ph.D.
Statistical Data Center
Intermountain Healthcare
greg.snow at intermountainmail.org
(801) 408-8111

> -----Original Message-----
> From: r-help-bounces at stat.math.ethz.ch
> [mailto:r-help-bounces at stat.math.ethz.ch] On Behalf Of Leeds,
> Mark (IED)
> Sent: Friday, July 13, 2007 2:45 PM
> To: r-help at stat.math.ethz.ch
> Subject: [R] Question about acception rejection sampling -
> NOT R question
>
> This is not related to R but I was hoping that someone could
> help me. I am reading the "Understanding the Metropolis
> Hastings Algorithm"
> paper from the American Statistician by Chip and Greenberg,
> 1995, Vol 49, No 4. Right at the beginning they explain the
> algorithm for basic acceptance  rejection sampling in which
> you want to simulate a density from f(x) but it's not easy
> and you are able to generate from another density called
> h(x). The assumption is that there exists some c such that
> f(x) <= c(h(x) for all x
>
> They clearly explain the steps as follows :
>
> 1) generate Z from h(x).
>
> 2) generate u from a Uniform(0,1)
>
> 3) if u is less than or equal to f(Z)/c(h(Z) then return Z as
> the generated RV; otherwise reject it and try again.
>
> I think that, since f(Z)/c(h(z) is U(0,1), then u has the
> distrbution as f(Z)/c(h(Z).
>
> But, I don't understand why the generated and accepted Z's
> have the same density  as f(x) ?
>
> Does someone know where there is a proof of this or if it's
> reasonably to explain, please feel free to explain it.
> They authors definitely believe it's too trivial because they
> don't. The reason I ask is because, if I don't understand
> this then I definitely  won't understand the rest of the
> paper because it gets much more complicated.  I willing to
> track down the proof but I don't know where to look. Thanks.
> --------------------------------------------------------
>
> This is not an offer (or solicitation of an offer) to