rejection sampling

For sampling values from an arbitrary probability distribution function

f(x)

by using an instrumental distribution

g(x)

under the only restriction that

f(x)< Mg(x)

where

M>1

is an appropriate bound on

f(x)/g(x)

. The algorithm goes as follows: sample

x

from

g(x)

and

u

from

U(0,1)

and check whether or not

u . If this holds, accept x as a realization of f(x); if not, reject the value of x and repeat the sampling step.  The validation of this method is the

envelope principle: when simulating the pair

(x,v=u*Mg(x))

, one produces a uniform simulation over the subgraph of

Mg(x)

. Accepting only pairs such that

u then produces pairs (x,v) uniformly distributed over the subgraph of f(x) and thus, marginally, a simulation from f(x) .  Also called the

acceptance-rejection method or "accept-reject algorithm", this method relates to the general field of Monte Carlo techniques, including Markov chain Monte Carlo algorithms that also use a proxy distribution to achieve simulation from the target distribution

f(x)

References

Robert, C.P. and Casella, G. "Monte Carlo Statistical Methods" (second edition). New York: Springer-Verlag, 2004.

<< Previous

Word Browser

Next >>

baleshare
rinderpest
lost, scotland
hang seng composite industry indexes
cantar de gesta
timeline of the texas revolution
ocean waves
dime bar
hemostasis
north african cuisine
congaree vista

baggins family
nicam
battle of the alamo
geza maroczy
henrique mecking
bellabeg
rainforest cafe
disney's animal kingdom
bayer leverkusen
sunnyvale
deshler

franois cvert
telefe
natural selection (computer game)
nevada (disambiguation)
wladyslaw franciszek jablonowski
suicide six (film)
giat bm92 g1 (pamas g1)
surrealist games
cobb
bardhyllus
pete

question
john penn
poisson summation formula
enets people
john penn (governor)
battle of gonzales
roberto carlos (singer)
list of strange units of measurement
conditional mood
framhaldssklinn vestmannaeyjum
bienne