Probability and Statistics for Engineering Lecture 9-11 Notes

Monte Carlo Methods

Introduction and Theoretical Basis

Monte Carlo methods, or Monte Carlo experiments, are a board class of computational algorithms that rely on repeated random sampling to obtain numerical results.

The law of large numbers (or LLN for short) states that the average of the results obtained from a large number of independent random samples converges to the true mean, if it exists.

Law of Large Numbers

Let be a sequence of i.i.d. random variables with Then converges in probability to as : In other words, for any ,

Tip

This is actually the weak law of large numbers.

A special case of the LLN is when Then is the frequency of success, is the probability of success. Then LLN states that suggesting that probability is the long-run frequency which can be approximated by calculateing the frequency from repeated Bernoulli trials.

Therefore, the LLN provides the theoretical basis for the Monte Carlo methods, which essentially calculate probabilities/expectation as long-run frequencies/averages.

Simulation of Random Variables

Generating random numbers is often nontrivial to do. Typically, we use the pseudo-random number generators (or PRNG for short) to generate a sequence of numbers whose properties approximate the properties of sequence of “truly random” numbers.

Example

Obtain numbers from the following distributions based on a uniform distribution random number generator:

2. .

Solution 1. For random variable , define as where . Then it is not difficult to show that . Therefore, for from a uniform distribution random number generator, define then can be considered numbers generated from .

Solution 2. Consider the PMF of : Divide the interval into subintervals: Define if , then can be considered numbers generated from .

For the continuous distributions, we utilize the inverse transformation sampling:

Example

Obtain numbers from the following distributions based on a uniform distribution random number generator:

2. , where is a positive integer

Solution 1. For random variable , its CDF is with inverse function Therefore, for from a uniform distribution random number generator, define then can be considered numbers generated from .

Solution 2. The CDF of Gamma distribution has no closed-form expression, but we can utilize the fact that is the sum of independent . Since in 1. we already knew how to generate numbers from , let be numbers from , define Then can be considered numbers generated from .

Solution 3. To sample from , it is enough to sample from . The CDF of is , which also does not have closed-form expression. We can circumvent this by converting the problem to simulation of two independent random variables. If we have two i.i.d. random variables and both following , let Then is a pair of independent standard normal random variables. Therefore, let be numbers from , define then can be considered numbers generated from . Consequently, can be considered numbers generated from .

To sample from more complicated distributions, we can use the rejection sampling. The rejection sampling can be used given the PDF of the distribution that we would like to sample from, this distribution is called the target distribution.

Since it is difficult to sample from the target distribution, rejection sampling turns to sample from a distribution with PDF , called the proposal distribution, that is easy to sample from, e.g. a uniform distribution.

Then each number generated from is accepted or rejected according to some criterion. Those accepted numbers can be considered numbers sampled from the target distribution .

Theorem

Let have uniform distribution over the region for some PDF with support , then .

Proof. It is essentially a problem of determining the marginal distribution of . Since is uniform over the region , its joint PDF must be a constant. Assume . Thus So

When using as the proposal distribution, the rejection sampling is implemented as:

• Simulate a number from and a number from .
• Then is a point uniformly distributed on a rectangle region.
• If , then reject , otherwise is a desired number from .

However, to avoid the case where the support of is not closed, it is better to choose a proposal distribution satisfying:

• and have the same support
• There is a constant s.t. for all in the support.

Then the rejection sampling is:

• Sample from .
• Sample from , reject if

• otherwise we accept .

Acceptance Probability of Rejection Sampling

For each number sampled from , the probability of accepting it is .

Proof. To make the sampling efficient, the constant should be as small as possible provided t satisfies for all . If possible, then choose

Tip

We only need to know and up to a constant or proportionality. In other words, if and . Then we can do the rejection sampling on and .