Monte Carlo Methods

Why

Simulation / Compute function expectation

Compute function integral

Suppose we want to find the value of:

    \[\int_{a}^{b}f(x)dx\]

in some region with volume V.
Now, we can estimate this integral by estimating the proportion of random points that fall under f(x), then multiplied by V.

Important in Exotics pricing as there’s no analytical solutions (e.g. Asian Options)

Convergence Rate

The speed Monte Carlo method converges to the correct result as we increase the sample size / number of simulations.

Monte Carlo has convergence rate O(N^{0.5}).

Quasi Monte Carlo has convergence rate O(\frac{1}{N}).

Variance Reduction

Reduce the variance of Monte Carlo simulated result with regard to the true result.

Increase number of simulations

Not very feasible, as in order to decrease variance / noise linearly, we have to increase simulations exponentially.

Importance Sampling

 

Quasi Monte Carlo (QMC)

Low-discrepancy Sequence
Halton Sequence
Sobol Sequence
Faure Sequence

We take any prime number r where r>=2. Any integer n has a unique expansion with base r. We can then generate a sequence of numbers in the interval [0, 1), which are equally spaced within the interval.

For example, r = 3 and n = 7. We can write 7 in the form of base 3 as below:

    \[7 = 2(3^{1}) + 1(3^{0}) = 21_{3}\]

Now, if we reflect this number about its “decimal point”, we get a new number in [0, 1):

    \[1(3^{-1}) + 2(3^{-2}) = \frac{5}{9}\]

We keep on doing this for every number n, we will generate a sequence in interval [0, 1). And we observe that the newly generated number keep filling the gaps in proceeding sequence. For example, for n = 1 to 9, we have below Faure Sequence:

    \[\frac{9}{27}, \frac{18}{27}, \frac{3}{27}, \frac{12}{27}, \frac{21}{27}, \frac{6}{27}, \frac{15}{27}, \frac{24}{27}, \frac{1}{27}, \]

In a general form, for any given number n, we can represent n in base r:

    \[n = \sum_{j=0}^{m}a_{j}(n)r^{j}\]

Then, we can find the corresponding Faure number in interval [0, 1) as follows:

    \[\sum_{j=0}^{m}a_{j}(n)r^{-j-1}\]

One thought on “Monte Carlo Methods”

Leave a Reply

Your email address will not be published.