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 distributionfunction by using an instrumental distribution , under the only restriction that where is an appropriate bound on .
Rejection sampling is usually used in cases where the form of makes sampling difficult. Instead of sampling directly from the distribution , we use an envelope distribution where sampling is easier. These samples from are probabilistically accepted or rejected.
This method relates to the general field of Monte Carlo techniques, including
Markov chain Monte Carloalgorithms that also use a proxy distribution to achieve simulation from the target distribution . 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 of . 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 varies, however to obtain acceptance probabilty 1, , which defeats the purpose of sampling.
The algorithm (used by
John von Neumannand dating back to Buffon and his needle) is as follows:
* Sample from and from
* Check whether or not
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. Sie kann genutzt werden, wenn die… … Deutsch Wikipedia