Monte Carlo method

Monte Carlo methods are methods for solving various kinds of computational problems by using random numbers (or more often pseudo-random numbers), as opposed to deterministic algorithms. Monte Carlo methods are extremely important in computational physics and related applied fields, and have diverse applications from esoteric quantum chromodynamics calculations, to use by engineers in designing heat shields and aerodynamic forms.

Monte Carlo methods were originally practiced under more generic names such as "statistical sampling". The "Monte Carlo" designation is a reference to the famous casino in that area, and was popularized by early pioneers in the field such as Stanislaw Marcin Ulam, Enrico Fermi, Jon von Neumann and Nick Metropolis[?].

Random methods of computation have their roots in the pre-electronic computing era. Perhaps the most famous early use was by Fermi in 1930, when he used a random method to calculate the properties of the newly-discovered neutron. It's well known that Monte Carlo methods were central to the simlulations required for the Manhattan Project. However it was only after electronic computers were first built (from 1945 on) that Monte-Carlo methods began to be studied in depth.

Table of contents 1 Integration 1.1 Integration methods 2 Optimisation 2.1 Optimisation methods 3 To be written 4 References and external links

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 quadrature methods can be very inefficient. To numerically integrate a two-dimensional vector, we would need equally spaced grid points over a two-dimensional surface, so say if you wanted a 10x10 grid, that would be 100 points. If the vector had 100 dimensions, the same spacing on the grid would require 10¹⁰⁰ points — that's far too many to be computed. 100 dimensions is by no means unreasonable, since in many physical problems, a "dimension" is equivalent to a "degree of freedom", and in a three dimensional simulation, there are at least three degrees of freedom per particle.

Monte Carlo methods provide a way out of this exponential time-increase. As long as the function in question is reasonably well-behaved, we can estimate it by randomly selecting points in 100-dimensional space, and taking some kind of "average". By the central limit theorem, we would expect this method to display "1/√N convergerence" -- 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. Unfortunately, doing this precisely is just as hard 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.

Integration methods

• Direct sampling methods
  • Importance sampling[?]
  • Stratified sampling
  • Recursive stratified sampling[?]
  • VEGAS algorithm[?]
• Random walk Monte Carlo including Markov chains
  • Metropolis-Hastings Markov Chain Monte Carlo Sampling

Optimisation

Another powerful and very popular application for random numbers in numerical simulation is in numerical optimisation. Here we have a function of some large-dimensional vector, and we wish to find the minimum of it. Many problems can be phrased in this way: for example a computer chess program could be seen as trying to find the optimal set of, say, 10 moves which produces the best evaluation function at the end. The travelling salesman problem is another optimisation problem.

Most Monte Carlo optimisation methods are based on random walks. Essentially, the program will move around a marker in multi-dimensional space, tending to move in directions which lead to a lower function, but sometimes moving against the gradient.

Optimisation methods

• Genetic algorithms
• Simulated annealing

To be written

• Diffusion and quantum Monte Carlo
• Semiconductor charge transport and the like
• Quasi-random numbers and self avoiding walks
• Assorted random models, e.g. self-organised criticality

References and external links

• Stochastic Simulation in Physics, P. Kevin MacKeown, 1997, ISBN 981-3083-26-3