# 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:

- Chooses a density .
- Finds a constant such that for all .
- Generates a uniform random number .
- Generates a random number from .
- 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:

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