Rejection sampling

In mathematics, rejection sampling is a technique used to generate observations from a distribution. It is also commonly called the acceptance-rejection method or "accept-reject algorithm".

It generates sampling values from an arbitrary probability distribution function f(x) by using an instrumental distribution g(x), under the only restriction that f(x)< M g(x) where M>1 is an appropriate bound on f(x)/g(x).

Rejection sampling is usually used in cases where the form of f(x) makes sampling difficult. Instead of sampling directly from the distribution f(x), we use an envelope distribution Mg(x) where sampling is easier. These samples from Mg(x) are probabilistically accepted or rejected.

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). It forms the basis for algorithms such as the Metropolis algorithm.

The unconditional acceptance probability is the proportion of proposed samples which are accepted, and is the integral over all values of x of Mf(x). If this is high, fewer samples are rejected, and the required number of samples for the target distribution is obtained more quickly. The unconditional acceptance probability is higher the less the ratio f(x)/g(x) varies, however to obtain acceptance probabilty 1, f(x)=g(x), which defeats the purpose of sampling.

Algorithm

The algorithm (used by John von Neumann and dating back to Buffon and his needle) is as follows:
* Sample x from g(x) and u from U(0,1)
* 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).

This means that, with enough replicates, the algorithm generates a sample from the desired distribution f(x). There are a number of extensions to this algorithm, such as the Metropolis algorithm.

Examples

As a simple geometric example, suppose it is desired to generate a random point within the unit circle. Generate a candidate point (x,y) where x and y are independent uniformly distributed between −1 and 1. If it so happens that x^2+y^2 leq 1 then the point is within the unit circle and should be accepted. If not then this point should be rejected and another candidate should be generated.

The ziggurat algorithm, a more advanced example, is used to efficiently generate normally-distributed pseudorandom numbers.

References

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

*J. von Neumann, "Various techniques used in connection with random digits. Monte Carlo methods", Nat. Bureau Standards, 12 (1951), pp. 36–38.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Rejection — The word rejection was first used in 1415. The original meaning was to throw or to throw back .Rejection may mean:* Social rejection, in psychology, an interpersonal situation that occurs when a person or group of people exclude an individual… …   Wikipedia

  • Pseudo-random number sampling — or non uniform pseudo random variate generation is the numerical practice of generating pseudo random numbers that are distributed according to a given probability distribution. Methods of sampling a non uniform distribution are typically based… …   Wikipedia

  • Inverse transform sampling — Inverse transform sampling, also known as the probability integral transform, is a method of generating sample numbers at random from any probability distribution given its cumulative distribution function (cdf). This method is generally… …   Wikipedia

  • Transplant rejection — Classification and external resources Micrograph showing lung transplant rejection. Lung biopsy. H E stain. ICD …   Wikipedia

  • acceptance sampling — Ops a quality control decision making technique used in a manufacturing environment, in which acceptance or rejection of a batch of parts is decided by testing a sample of the batch. The sample is checked against established standards and, if it… …   The ultimate business dictionary

  • List of statistics topics — Please add any Wikipedia articles related to statistics that are not already on this list.The Related changes link in the margin of this page (below search) leads to a list of the most recent changes to the articles listed below. To see the most… …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • Uniform distribution (continuous) — Uniform Probability density function Using maximum convention Cumulative distribution function …   Wikipedia

  • Ziggurat algorithm — The ziggurat algorithm is an algorithm to generate random numbers from a non uniform distribution. It belongs to the class of rejection sampling algorithms and can be used for choosing values from a monotone decreasing probability distribution.… …   Wikipedia

  • Verwerfungsmethode — Die Verwerfungsmethode (auch Acceptance Rejection Verfahren; engl. rejection sampling) ist eine Methode zur Erzeugung von Zufallszahlen zu einer vorgegebenen Verteilung und geht auf John von Neumann zurück.[1] Sie kann genutzt werden, wenn die… …   Deutsch Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.