Page 93 - DCAP601_SIMULATION_AND_MODELING

Unit 6: Discrete System Simulation (III)

Use in Mathematics Notes

In general, Monte Carlo methods are used in mathematics to solve various problems by
generating suitable random numbers and observing that fraction of the numbers obeying some
property or properties. The method is useful for obtaining numerical solutions to problems
which are too complicated to solve analytically. The most common application of the Monte
Carlo method is Monte Carlo integration.

Task Analyze the different areas where you can use Monte Carlo methods.

Integration

Deterministic methods of numerical integration operate by taking a number of evenly spaced
samples from a function. In general, this works very well for functions of one variable. However,
for functions of vectors, deterministic quadrate methods can be very inefficient. To numerically
integrate a function of a two-dimensional vector, equally spaced grid points over a two-
dimensional surface are required. For instance a 10x10 grid requires 100 points. If the vector has
100 dimensions, the same spacing on the grid would require 10 100 points – far too many to be
computed. 100 dimensions are by no means unreasonable, since in many physical problems, a
“dimension” is equivalent to a degree of freedom.
Monte Carlo methods provide a way out of this exponential time-increase. As long as the
function in question is reasonably well-behaved, it can be estimated by randomly selecting
points in 100-dimensional space, and taking some kind of average of the function values at these
points. By the law of large numbers, this method will display convergence – i.e., quadrupling
the number of sampled points will halve the error, regardless of the number of dimensions.
A refinement of this method is to somehow make the points random, but more likely to come
from regions of high contribution to the integral than from regions of low contribution. In other
words, the points should be drawn from a distribution similar in form to the integrand.
Understandably, doing this precisely is just as difficult as solving the integral in the first place,
but there are approximate methods available: from simply making up an integrable function
thought to be similar, to one of the adaptive routines discussed in the topics listed below.
A similar approach involves using low-discrepancy sequences instead – the
quasi-Monte Carlo method. Quasi-Monte Carlo methods can often be more efficient at numerical
integration because the sequence “fills” the area better in a sense and samples more of the most
important points that can make the simulation converge to the desired solution more quickly.

Integration Methods
1. Direct sampling methods

(a) Importance sampling
(b) Stratified sampling
(c) Recursive stratified sampling
(d) VEGAS algorithm
2. Random walk Monte Carlo including Markov chains
(a) Metropolis-Hastings algorithm
3. Gibbs sampling

LOVELY PROFESSIONAL UNIVERSITY 87