Acceptance–rejection method
Definition taught in Simulation, part of Probability
Acceptance–rejection method
| Type | Definition |
| Taught in | Simulation |
| Part | Probability |
| Worked examples | 1 |
Suppose the target density f is zero outside a finite interval [a,b] and bounded by c=\max f. Draw X uniformly from [a,b] and, independently, Y uniformly from [0,c]. If Y\le f(X), return X. Otherwise repeat.
Examples
Rejection for a beta density
Worked example from Simulation
The density f(x)=6x(1-x) on [0,1] is the \operatorname{Beta}(2,2) law.
Question. Describe a rejection sampler with uniform proposals, find its efficiency, and find the expected number of uniform random numbers it uses per accepted draw.
Solution. The density is largest at x=1/2, where f=1.5, so take c=1.5. Draw X\sim\operatorname{U}[0,1] and Y\sim\operatorname{U}[0,1.5], and accept X if Y\le6X(1-X). The acceptance probability is the area under f, which is 1, over the area of the box, 1.5, so the efficiency is 2/3. The number of proposals until acceptance is geometric with mean 1.5, and each proposal uses two uniforms, so on average 3 uniforms are spent per accepted draw.
Used in
- Taught in Simulation, where the derivation and examples are.
- All 4 questions on Simulation