Monte Carlo Methods for Absolute Beginners

The modern history of Monte Carlo techniques dates back from the 1940’s and the Manhattan project. There are earlier descriptions of Monte Carlo experiments, Buffon’s famous needle experiment is one them, but examples have been traced back to Babylonian and old testament times [13]. As we shall see these techniques are particularly useful in scenarios where it is of interest to perform calculations that involve – explicitly or implicitly – a probability distribution π on a space X (typically X⊂Rnx for some integer n_x), for which closed-form calculations cannot be carried out due to the algebraic complexity of the problem. As we shall see the main principle of Monte Carlo techniques consists of replacing the algebraic representation of π, e.g. 1/2π−−√exp(−12x2) with a sample or population representation of π, e.g. a set of samples X1,X2,…,XN∼iidπ(x)=1/2π−−√exp(−12x2). This proves in practice to be extremely powerful as difficult – if not impossible -exact algebraic calculations are typically replaced with simple calculations in the sample domain. One should however bear in mind that these are randomapproximations of the true quantity of interest. An important scenario where Monte Carlo methods can be of great help is when one is interested in evaluating expectations of functions, say f, of the type Eπ(f(X)) where π is the probability distributions that defines the expectation. The nature of the approach, where algebraic quantities are approximated by random quantities, requires one to quantify the random fluctuations around the true desired value. As we shall see, the power of Monte Carlo techniques lies in the fact that the rate at which the approximation converges towards the true value of interest is immune to the dimension n_x of the space X where π is defined. This is the second interest of Monte Carlo techniques.