The Acceptance-Rejection (AR) Method

Let X be a random variable with pdf (or pmf) f(x). 

 

Our goal is to generate a sample of X, but it is impossible to draw a sample from $f(x)$ directly.

 

Let Y be a random variable with pdf(or pmf) $g(y)$ such that $f(t) / g(t) \leq c$ for some constant c.  

 

The AR method proceeds as follows:

1. Generate y from the distribution with g.
2. Generate u from Uniform(0,1). 
3. If $u < f(y)/{cg(y)}$, then accept y. i.e., x =y;
   otherwise reject y go to step1. 

Note that g and c are determined by us. 

(We call g as proposal distribution.)

 

 

Ex

Let X ~ Beta(2,2). Then, the pdf is $f(x) = 6x(1-x), 0 < x <1$.

Let g(x) be the Uniform(0,1) density, i.e., $g(x) = 1, 0 < x < 1$.

(We choose the uniform distribution on (0,1) as the proposal distribution.)

 

Note that $f(x) / g(x) = \frac{6x(1-x)}{1} \leq c \equiv c$

 

Hence, we accept if $u < f(y)/cg(y) = y(1-y)$.  

n = 1000
x = rep(0,n) # storage for generated x-values
k = 0 # count of accepted samples

while(k < n){
	u = runif(1)
    y = runif(1)
    
    if(y * (1-y) > u){
    	k = k + 1
        x[k] = y
    }
}

 

 

 

Remark on AR method

Let T be the number of iterations.

It can be shown that $P(Accept) = 1/c$.

Hence, the average number of the accepted samples is $T/c$.

This implies that choosing c as small as possible improves the efficiency of AR method.