MATLAB Examples

# Acceptance-Rejection Methods

The functional form of some distributions makes it difficult or time-consuming to generate random numbers using direct or inversion methods. Acceptance-rejection methods provide an alternative in these cases.

Acceptance-rejection methods begin with uniform random numbers, but require an additional random number generator. If your goal is to generate a random number from a continuous distribution with pdf , acceptance-rejection methods first generate a random number from a continuous distribution with pdf satisfying for some and all .

A continuous acceptance-rejection RNG proceeds as follows:

1. Chooses a density .
2. Finds a constant such that for all .
3. Generates a uniform random number .
4. Generates a random number from .
5. If , accepts and returns . Otherwise, rejects and goes to step 3.

For efficiency, a "cheap" method is necessary for generating random numbers from , and the scalar should be small. The expected number of iterations to produce a single random number is .

The following function implements an acceptance-rejection method for generating random numbers from pdf given , , the RNG grnd for , and the constant :

function X = accrejrnd(f,g,grnd,c,m,n)
X = zeros(m,n); % Preallocate memory
for i = 1:m*n
accept = false;
while accept == false
u = rand();
v = grnd();
if c*u <= f(v)/g(v)
X(i) = v;
accept = true;
end
end
end
end



For example, the function satisfies the conditions for a pdf on (nonnegative and integrates to 1). The exponential pdf with mean 1, , dominates for greater than about 2.2. Thus, you can use rand and exprnd to generate random numbers from :

f = @(x)x.*exp(-(x.^2)/2); g = @(x)exp(-x); grnd = @()exprnd(1); rng('default') % For reproducibility X = accrejrnd(f,g,grnd,2.2,1e4,1); 

The pdf is actually a Rayleigh Distribution with shape parameter 1. This example compares the distribution of random numbers generated by the acceptance-rejection method with those generated by raylrnd:

Y = raylrnd(1,1e4,1); histogram(X) hold on histogram(Y) legend('A-R RNG','Rayleigh RNG') 

The raylrnd function uses a transformation method, expressing a Rayleigh random variable in terms of a chi-square random variable, which you compute using randn.

Acceptance-rejection methods also work for discrete distributions. In this case, the goal is to generate random numbers from a distribution with probability mass , assuming that you have a method for generating random numbers from a distribution with probability mass . The RNG proceeds as follows:

1. Chooses a density .
2. Finds a constant such that for all .
3. Generates a uniform random number .
4. Generates a random number from .
5. If , accepts and returns . Otherwise, rejects and goes to step 3.