9716

Acceptance/Rejection Sampling

With this Demonstration, you can visualize the rejection sampling technique, which is also known as the acceptance-rejection algorithm. Select a target distribution (the distribution from which you would like to generate random samples) and then choose a "threshold value" that influences the likelihood that a candidate sample from a nontarget distribution will be "accepted" as if it were, in fact, from the target distribution. You can change the number of random variates generated and view histograms of both the accepted and the rejected samples.
The exponential distribution and the Cauchy distribution for target distributions are supported on the positive half or whole real line, respectively.

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

DETAILS

Suppose that you want to generate pseudorandom numbers from a random variable with probability distribution , but that other methods (like the method of inverse transforms) do not work well (perhaps because the cumulative distribution function associated with does not have an explicit inverse). Instead, choose a companion random variable with probability density function , making sure that and have the same support (i.e. both vanish and fail to vanish over the same sets of real numbers).
Ideally, the random variable has been chosen in such a way that the cumulative distribution function associated with has an explicit inverse and is easy to simulate using a technique like the method of inverse transforms.
The acceptance-rejection algorithm is then as follows: (1) independently simulate a random number with a uniform distribution over the unit interval and a realization * of the random variable ; and then (2) using a fixed, strictly positive number , accept * as a realization of if , where and are the probability densities of the random variables and , respectively. If is not accepted, it is rejected. This process is continued repeatedly until a target number of realizations of is generated.
Heuristically, the acceptance-rejection method works particularly efficiently when certain conditions are satisfied. First, the target random variable and the companion random variable should have density functions that "look" as similar as possible. In this Demonstration, we use the exponential random variable as a companion random variable for the probability distributions with support on the positive part of the real line (the gamma distribution, chi-square distribution, half-normal distribution, and log-normal distribution). We use the Cauchy distribution as the companion distribution for the probability distributions with support over the whole real line (the normal distribution, the Student t distribution, the Gumbel distribution, and the Laplace distribution).
Second, the strictly positive constant influences the tendency of the algorithm to "accept" instead of "reject". If is particularly large, will be less than with small probability, and the algorithm will throw away many fine proxies for . On the other hand, if is particularly close to zero and is not substantially smaller than , then will probably be accepted. It can be shown that the acceptance-rejection algorithm produces an empirical distribution of pseudorandom numbers that converges the most rapidly to the target distribution if is chosen to be the maximum possible value of over the (common) support of and .
The acceptance-rejection method can be generalized to the Metropolis–Hastings algorithm and is a type of Markov chain Monte Carlo simulation. For further information about the acceptance-rejection algorithm, see [1] or [2].
References
[1] S. M. Ross, Simulation, 4th ed., Boston: Elsevier, 2006.
[2] S. Ghahramani, Fundamentals of Probability, with Stochastic Processes, 3rd ed., New York: Prentice Hall, 2004.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.









 
RELATED RESOURCES
Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2014 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+