Rejection Sampling - Acceptance-Rejection Method - Accept-Reject Algorithm

Theorem

Let a pair (𝑋,𝑌) have Uniform distribution over the region

• 𝐴 = {(𝑥,𝑦) | 0 ≤ 𝑦 ≤ 𝑓(𝑥)}

for some probability density function 𝑓.

Then 𝑓 is the density of 𝑋

proof

Algorithm

1. find such numbers 𝑎, 𝑏, and 𝑐 that 0 ≤ 𝑓(𝑥) ≤ 𝑐 for 𝑎 ≤ 𝑥 ≤ 𝑏
2. the bounding box stretches along the 𝑥-axis from 𝑎 to 𝑏 and along the 𝑦-axis from 0 to 𝑐
3. obtain Standard Uniform random variables 𝑈 and 𝑉 from a random number generator or a table of random numbers
4. define:
   1. 𝑋 = 𝑎 + (𝑏 − 𝑎)𝑈
   2. 𝑌 = 𝑐𝑉
5. no we can infer:
   1. 𝑋 has 𝑈𝑛𝑖𝑓𝑜𝑟𝑚(𝑎, 𝑏) distribution
   2. 𝑌 has 𝑈𝑛𝑖𝑓𝑜𝑟𝑚(0, 𝑐) distribution
   3. point (𝑋,𝑌) is Uniformly distributed in the bounding box
6. if 𝑌 > 𝑓(𝑋), reject the point and return to step 3. If 𝑌 ≤ 𝑓(𝑋), then 𝑋 is the desired random variable having the density 𝑓(𝑥)

Subpages

• Rejection Method Example - Beta Distribution