Quasi-Monte Carlo Methods

Monte Carlo is a very flexible numerical method which can model and price complex instruments when other methods can not. But it has the strong disadvantage of being very time consuming.

The pricing of complex exotic products can take a few seconds when we have to simulate a high number of paths with numerous time steps to get enough accuracy. And if we need to generate scenario analysis or stress testing by changing input parameters, seconds can become minutes or hours…

Computation speed is quickly one key aspect when running Monte Carlo simulations.

Quasi-Monte Carlo simulations are variations of Monte Carlo simulations.

They use low-discrepancy deterministic sequences with better uniformity properties than purely random sequences providing more accurate and efficient estimates compared to traditional Monte Carlo simulations.

Halton or Sobol are two examples of such sequences.

In the slides below, we generate 256 points uniformly distributed with traditional Monte Carlo method. The distribution of these random numbers might exhibit clustering or gaps, which can lead to suboptimal coverage of the space and this can result in inaccuracies in the estimations.

Quasi-Monte Carlo simulations address this issue. They are using low-discrepancy deterministic sequences, which have better uniformity properties than purely random sequences reducing clustering and gaps with a better coverage of the space. In this example we generate 256 points with Sobol sequence. The number of point has to be a power of 2 with this method.

As the sequences are deterministic, it is possible to add some noise, scrambling the numbers to add some randomness.

Quasi-Monte Carlo allows more accurate and efficient estimates for low dimension problems, with a rate of convergence close to O(log(N)^k / N) for a problem of dimension k compared to O(1 / N^0.5) with Monte Carlo simulations.

For a problem of dimension 1 we would get roughly the same accuracy of the estimate with 10^4 quasi-Monte Carlo simulations than with 10^7  Monte Carlo simulations, which allows a huge gain in terms of computation time.

We illustrate this below, with the estimation of the number π by Monte Carlo simulations. We simulate points in a square which side length is two units. The probability that the point is in the disc inside the square which has a radius of 1 is π / 4.

As highlighted on the chart, which shows π estimations by increasing the number of simulations, we start to get a strong accuracy with close to 10000 simulations with Quasi-Monte Carlo. It would require 10M to get similar accuracy with traditional Monte Carlo.

Presentation

Save 10% on All Quant Next Courses with the Coupon Code: QuantNextBlog10

For students and graduates: We offer a 50% discount on all courses, please contact us if you are interested: contact@quant-next.com