[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 
> buy/se...{{dropped}}
> ______________________________________________
> R-help at stat.math.ethz.ch mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide 
> http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.

More information about the R-help mailing list