Monte Carlo methods are often used to obtain solutions to physical or mathematical problems that are difficult or impossible to solve using close-form solutions or applying deterministic algorithms. Through the application of peudo-random number, Monte Carlo methods are able to obtain approximate solution to high-dimensional problems in an efficient manner. There are three distinct problem classes that Monte Carlo methods are applied: optimization, numerical integration and generation of samples from a probability distribution.
In the case of stochastic optimization, the formulation of the problem itself involves random variables and/or random constraints, resulting in objective functions that exhibit randomness. In scenario optimization, samples of each random variables involved are drawn from respective distributions, these samples are then used to solve the scenario optimization program to yield the optimal parameters. In the case of portfolio management, assuming that we have estimation the probability distributions of the stocks involved a year from now, we can use stochastic optimization determine what portion of the fund shall be allocated to each stock to reach our goal (i.e. maximum return with risk below a particular threshold).
For the case of integrating a function over a probability distribution for the purpose of density estimation, we have to solve for \( \mathbb{E}[f(x)] = \int_{x \sim P(X)} {f(x) \, dx} \). We can approximate the solution using Monte Carlo methods by drawing \( N \) samples \( \{ x_1, x_2, ..., x_N \} \) from the probability distribution \( P(X) \), then solve it by calculating: \( \mathbb{E}[f(x)] \approx \frac{1}{N} \, \sum_1^N{f(x_i)} \).
There are times when we encounter complex, high-dimensional mutli-variate distributions and would like to draw samples from such distributions, Monte Carlo methods such as the Metropolis-Hastings, Gibbs Sampling algorithms can be used to efficiently complete the task.
All of the above cases required drawing samples from different probability distributions. Most of the programming languages we use comes with only a basic random number generator which can be used to draw samples from a uniform distribution; to generate samples from non-uniform distribution, we can use various pseudo-random number sampling methods; and these methods are main topics of this chapter.
Sampling from finite discrete distributions:
Sampling from continuous distributions: