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.