# Quasi Monte Carlo¶

Let us note . The goal is to estimate the following probability:

(1)

Quasi-Monte Carlo is a technique which approximates the integral (1) using low discrepancy sequences instead of randomly generated sequences, as follows:

In general, the integral of a function on can be approximated by using some low discrepancy sequence as follows:

The low discrepancy sequence is generated on according to the Lebesgue measure then may be transformed to any measure thanks to the inverse CDF technique in order to approximate the integral :

As the sequence is not randomly generated, we can not use the Central Limit Theorem in order to control the quality of the approximation. This quality is given by the Koksma-Hlawka inequality that we recall here :

where is the discrepancy of the sequence .

For Halton, Inverse Halton and Sobol sequences, we have :

Thus, asymptotically the error converges in , instead of for traditional Monte Carlo. The convergence rate depends on the dimension so one must have .

Examples: