# Acceptance-Rejection Sampling

### From Wiki Course Notes

## Contents |

### Acceptance-Rejection Sampling - May 14, 2009

Today, we continue the discussion on sampling (generating random numbers) from general distributions with the **Acceptance/Rejection Method**.

#### Acceptance/Rejection Method

Suppose we wish to sample from a target distribution *f*(*x*) that is difficult or impossible to sample from directly. Suppose also that we have a proposal distribution *g*(*x*) from which we have a reasonable method of sampling (e.g. the uniform distribution). Then, if there is a constant , accepting samples drawn in successions from with ratio close to 1 will yield a sample that follows the target distribution *f*(*x*); on the other hand we would reject the samples if the ratio is not close to 1.

The following graph shows the pdf of *f*(*x*) (target distribution) and (proposal distribution)

At x=7; sampling from will yield a sample that follows the target distribution *f*(*x*)

At x=9; we will reject samples according to the ratio after sampling from

**Proof**

Note the following:

- (Bayes' theorem)

So,

Therefore, as required.

**Procedure (Continuous Case)**

- Choose
*g*(*x*) (a density function that is simple to sample from) - Find a constant c such that :

- Let
- Let
- If then X=Y; else reject and go to step 1

**Example:**

Suppose we want to sample from Beta(2,1), for . Recall:

- Choose
- Find c: c = 2 (see notes below)

- Let
- Let
- If , then X=Y; else go to step 1

*c* was chosen to be 2 in this example since in this example is 2. This condition is important since it helps us in finding a suitable *c* to apply the Acceptance/Rejection Method.

In MATLAB, the code that demonstrates the result of this example is:

j = 1; while i < 1000 y = rand; u = rand; if u <= y x(j) = y; j = j + 1; i = i + 1; end end hist(x);

The histogram produced here should follow the target distribution, *f*(*x*) = 2*x*, for the interval .

The histogram shows the PDF of a Beta(2,1) distribution as expected.

**The Discrete Case**

The Acceptance/Rejection Method can be extended for discrete target distributions. The difference compared to the continuous case is that the proposal distribution *g*(*x*) must also be discrete distribution. For our purposes, we can consider g(x) to be a discrete uniform distribution on the set of values that X may take on in the target distribution.

**Example**

Suppose we want to sample from a distribution with the following probability mass function (pmf):

P(X=1) = 0.15 P(X=2) = 0.55 P(X=3) = 0.20 P(X=4) = 0.10

- Choose
*g*(*x*) to be the discrete uniform distribution on the set {1,2,3,4} - Find c:

- Generate
- Let
- If , then X=Y; else go to step 1

**Limitations**

If the proposed distribution is very different from the target distribution, we may have to reject a large number of points before a good sample size of the target distribution can be established. It may also be difficult to find such *g*(*x*) that satisfies all the conditions of the procedure.

We will now begin to discuss sampling from specific distributions.

#### Special Technique for sampling from Gamma Distribution

Recall that the cdf of the Gamma distribution is:

If we wish to sample from this distribution, it will be difficult for both the Inverse Method (difficulty in computing the inverse function) and the Acceptance/Rejection Method.

**Additive Property of Gamma Distribution**

Recall that if are independent exponential distributions with mean λ (in other words, ), then

It appears that if we want to sample from the Gamma distribution, we can consider sampling from t independent exponential distributions with mean λ (using the Inverse Method) and add them up. Details will be discussed in the next lecture.