Rejection Sampling - Theory

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:

    No one thinks anything silly is suitable when they are an adolescent. Such an enormous share of their own behavior is silly that they lose all proper perspective on silliness, like a baker who is nauseated by the sight of his own eclairs. This provides another good argument for the emerging theory that the best use of cryogenics is to freeze all human beings when they are between the ages of twelve and nineteen.
    Anna Quindlen (20th century)

    Osteopath—One who argues that all human ills are caused by the pressure of hard bone upon soft tissue. The proof of his theory is to be found in the heads of those who believe it.
    —H.L. (Henry Lewis)

    ... the first reason for psychology’s failure to understand what people are and how they act, is that clinicians and psychiatrists, who are generally the theoreticians on these matters, have essentially made up myths without any evidence to support them; the second reason for psychology’s failure is that personality theory has looked for inner traits when it should have been looking for social context.
    Naomi Weisstein (b. 1939)