Theory
It generates sampling values from an arbitrary probability distribution function 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 Carlo algorithms 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, which is . If is low, fewer samples are rejected, and the required number of samples for the target distribution is obtained more quickly. Because must be no less than the maximum of, the unconditional acceptance probability is higher the less that ratio varies, however to obtain acceptance probability 1, which defeats the purpose of sampling.
Read more about this topic: Rejection Sampling
Famous quotes containing the word theory:
“Many people have an oversimplified picture of bonding that could be called the “epoxy” theory of relationships...if you don’t get properly “glued” to your babies at exactly the right time, which only occurs very soon after birth, then you will have missed your chance.”
—Pamela Patrick Novotny (20th century)
“We have our little theory on all human and divine things. Poetry, the workings of genius itself, which, in all times, with one or another meaning, has been called Inspiration, and held to be mysterious and inscrutable, is no longer without its scientific exposition. The building of the lofty rhyme is like any other masonry or bricklaying: we have theories of its rise, height, decline and fall—which latter, it would seem, is now near, among all people.”
—Thomas Carlyle (1795–1881)
“Psychotherapy—The theory that the patient will probably get well anyway, and is certainly a damned ijjit.”
—H.L. (Henry Lewis)