Acceptance-Rejection Sampling: Independence and Proposal Efficiency

Summary

The document explains the role of the two random draws in acceptance-rejection sampling. A candidate is drawn from a proposal density, and a separate uniform draw determines whether that candidate is accepted according to the target-to-proposal density ratio and a bounding constant. The candidate and uniform draw are independent; the uniform draw is not the value used to generate the candidate through the proposal distribution’s inverse cumulative distribution function.

The answer also discusses how the proposal density and bound affect computational efficiency. A loose, conservative bound can cause many rejections and slow sampling, while choosing a proposal that fits the target more closely can reduce rejections. The exchange gives a conceptual explanation rather than a worked numerical example, and it does not specify how to construct or verify an optimal proposal or bound. In implementation, the acceptance test must use the same uniform draw for the acceptance decision and the candidate’s density in the ratio must be evaluated at that candidate.

Key ideas

• The candidate is sampled from the proposal density, while a separate uniform draw controls acceptance.
• The candidate and acceptance uniform are independent random variables.
• The acceptance probability is determined by the target density, proposal density, and bounding constant.
• A loose bounding constant increases rejection rates and sampling time.
• A proposal that better matches the target can improve efficiency.

Tags

# Generate Random Variable Using Acceptance Rejection Method


# Generate Random Variable Using Acceptance Rejection Method












I have a question about acceptance rejection method and really appreciate your advice:

Suppose we want to generate random variable that has probability density function $f(x)$, since we're using acceptance-rejection method, we need another probability density function $g(x)$ and constant $M$ such that $f(x)/g(x)<=M$.

Our first step is: generate random variable $y$ from $g(y)$ and a random variable $v$ from standard uniform distribution $[0,1]$

Here is my doubt: is there one to one mapping between generated random variable $y$ and $v$? In other words, are they independent OR for each $y$, it is derived by cumulative distribution function $G^{-1}(v)$, be aware that we use $v$ in the following step

Our second step is: if $v<={f(x)}/{(M*g(X))}$, accept $x=y$

## Answer by Attack68 (score 2, accepted)

https://quant.stackexchange.com/a/50690

They are independent.

The point is that $y$ is derived from your easily sampled distribution $g$ randomly. Now you have a random test (via $v$) that decides whether to accept $y$ or not as part of the random sample of the harder to sample $f$.

The procedure uses $M$ in the accept-reject method and whilst you can derive conservative estimates with $M$ quite high the number of rejected samples will be very high and so sampling will take a long time. Otherwise you can do some prior analysis to determine a supposed optimal underlying $g$ and low value of $M$ that will still generate a random sample with the distribution of $f$ but the number of rejected samples will be minimised.

Shown in full with attribution under the source's licence. Licence: CC BY-SA 4.0 (Stack Exchange)

This summary was written by Stratmill's research agent from the original; it is not a copy of the source.