# acceptance-Rejection Sampling

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

### 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 $c \ |\ c \cdot g(x) \geq f(x)\ \forall x$, accepting samples drawn in successions from $c \cdot g(x)$ with ratio $\frac {f(x)}{c \cdot g(x)}$ 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 $c \cdot g(x)$ (proposal distribution)

At x=7; sampling from $c \cdot g(x)$ will yield a sample that follows the target distribution $f(x)$

At x=9; we will reject samples according to the ratio $\frac {f(x)}{c \cdot g(x)}$ after sampling from $c \cdot g(x)$

Proof

Note the following:

• $Pr(X|accept) = \frac{Pr(accept|X) \times Pr(X)}{Pr(accept)}$ (Bayes' theorem)
• $Pr(accept|X) = \frac{f(x)}{c \cdot g(x)}$
• $Pr(X) = g(x)\frac{}{}$

So, $Pr(accept) = \int^{}_x Pr(accept|X) \times Pr(X) dx$ $= \int^{}_x \frac{f(x)}{c \cdot g(x)} g(x) dx$ $= \frac{1}{c} \int^{}_x f(x) dx$ $= \frac{1}{c}$

Therefore, $Pr(X|accept) = \frac{\frac{f(x)}{c\ \cdot g(x)} \times g(x)}{\frac{1}{c}} = f(x)$ as required.

Procedure (Continuous Case)

• Choose $g(x)$ (a density function that is simple to sample from)
• Find a constant c such that :$c \cdot g(x) \geq f(x)$
1. Let $Y \sim~ g(y)$
2. Let $U \sim~ Unif [0,1]$
3. If $U \leq \frac{f(x)}{c \cdot g(x)}$ then X=Y; else reject and go to step 1

Example:

Suppose we want to sample from Beta(2,1), for $0 \leq x \leq 1$. Recall:

$Beta(2,1) = \frac{\Gamma (2+1)}{\Gamma (2) \Gamma(1)} \times x^1(1-x)^0 = \frac{2!}{1!0!} \times x = 2x$
• Choose $g(x) \sim~ Unif [0,1]$
• Find c: c = 2 (see notes below)
1. Let $Y \sim~ Unif [0,1]$
2. Let $U \sim~ Unif [0,1]$
3. If $U \leq \frac{2Y}{2} = Y$, then X=Y; else go to step 1

$c$ was chosen to be 2 in this example since $\max \left(\frac{f(x)}{g(x)}\right)$ 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) = 2x$, for the interval $0 \leq x \leq 1$.

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: $c = \max \left(\frac{f(x)}{g(x)} \right)= 0.55/0.25 = 2.2$
1. Generate $Y \sim~ Unif \{1,2,3,4\}$
2. Let $U \sim~ Unif [0,1]$
3. If $U \leq \frac{f(x)}{2.2 \times 0.25}$, 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:

$F(x) = \int_0^{\lambda x} \frac{e^{-y}y^{t-1}}{(t-1)!} dy$

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.

Recall that if $X_1, \dots, X_t$ are independent exponential distributions with mean $\lambda$ (in other words, $X_i\sim~ Exp (\lambda)$), then $\Sigma_{i=1}^t X_i \sim~ Gamma (t, \lambda)$
It appears that if we want to sample from the Gamma distribution, we can consider sampling from t independent exponential distributions with mean $\lambda$ (using the Inverse Method) and add them up. Details will be discussed in the next lecture.