# 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 .

API:

Examples: