# Monte Carlo Accept–Reject Method

## Rejection Method for Sampling Random Numbers, Random Variable Simulation

**Why Monte Carlo Rejection Method?**

There are some cases when the inverse Monte Carlo method is not possible, and it is impractical to calculate inverse of CDF (Cumulative Distribution Function) because it may be exceedingly complicated mathematically or contain a special mathematical structure that is difficult to control. In such cases, a practical approach is to use the Accept–Reject Method.

## Pros and Cons:

While this method is a good alternative when the inverse method is difficult, it is a little ** expensive **specially

**when we have to put some of the useless generated random numbers in a trash! and accept only those which satisfy the condition of the problem. It seems wasting random numbers worth it when the mathematical solution of the inverse function is difficult.**

## Steps to implement Monte Carlo Rejection method:

Let’s imagine we have a typical pdf ( probability density function) like below:

**Steps:**

**1- The first step** is scaling the **original** probability density function ( I mean p(x)) by its maximum value and then obtaining:

Accordingly, function f(x) has a maximum value of 1 which occurs at:

**Attention:** Obviously, the rejection method works only if the probability density function is not infinite anywhere and if it is not difficult to determine the location of its maximum value.

**2- The second step** is to make a random number,** u1**, that is uniform in the range [0,1] and use it to obtain an x that is uniformly distributed in range [a,b] or its probability distribution function’s range [a,b] is uniform.

It is easy to generate (simulate) a uniform random number in an interval [a,b]. Just use what recently generated in the rang [0,1] and then calculate this:

**3- The third step** is to compute the f(x) for the value of x obtained above:

**4- The forth step** is to generate another random number, **u2**, that is also uniform in the range [0,1].

**5- The fifth step** which is the interesting part of Monte Carlo rejection method is to do the below comparison.

## What is this comparison standing for?

let’s again have a look at the last picture in a different way! In below you see a rectangular which has a width of 1–0=1 and length (b-a). Inside this rectangular, the f(x) is plotted.

When we choose two different independent uniformly-distributed random variables x and u2 which x is in the range [a,b] and u2 is in the range [0,1], it means we are going to fill the total area of this rectangular with some random dots.

If the below condition is satisfied it mean the random point (random dot) is inside the region under f(x) (see picture above). And if the condition is not satisfied it means the random dots is in the shaded region above f(x). And this is the key to accept or reject the **u1.**

**6- The last step: **If the above condition is true then we accept the **u1** and if it is not, then we reject **u1** and go back to **step 2** and start with another **u1**.

And **u1** is one that responsible to make **x** random variable according to the p(x) as describe above.

## Some useful references:

- Prof. Anatoly Yambartsev website: https://www.ime.usp.br/~yambar/MAE5704/Aula1GeneratingRV-I/aula1slidesT.pdf
- Book:
**Introducing Monte Carlo Methods with R. Series ”Use R!**” springer