Quasi Monte Carlo

The basic Monte Carlo (MC) method tries to approximate some difficult integral stochastically. Suppose we have some function f({\bf x}) defined on the unit cube U^d (i.e. all {\bf x} such that 0 \leq x_i \leq 1). If we can’t explicitly do integrate f over U^d, a Monte-Carlo approximation is:

\int_{U^d} f({\bf x}) d {\bf x} \approx \frac{1}{|{\hat X}|} \sum_{{\hat {\bf x}} \in {\hat X}} f({\hat {\bf x}}).

Basically, you just draw a bunch of random points from U^d, evaluate f at each of them, and then average the results. It is easy to imagine that, as long as f satisfies some notion of smoothness, the approximation will converge to the true integral as we take infinitely many points. There are simple extensions where the random points \hat {\bf x} are drawn non-uniformly from U^d, and then weights (inversely proportional to the probability of sampling a point) are employed when averaging over f({\hat {\bf x}}). If you know that f is close to zero except in some small region, this can be useful to direct attention there. Of course, all of this can be generalized to arbitrary regions, but I am sticking to U^d for simplicity.

Monte Carlo methods are extraordinarily simple and useful. Nevertheless, there is reason to think that we can do better– estimate the integral more accurately with a given number of sampled points. The reason for this is that “extra randomness” is introduced by choosing points randomly. If we draw points uniformly from the unit cube, by random chance, different areas of the cube will have different numbers of points– if we are very unlucky, all the \hat {\bf x} will be in some tiny corner. The idea of quasi monte-carlo (QMC) methods is to choose the points deterministically, to try to guarantee that the sampled points are more evenly spaced.

(We can see immediately that this strategy will probably work much better in small numbers of dimensions. In U^1, we can just choose 0,1/M,2/M,...,1. But if we want to make an d-dimensional “grid”, with M samples in each dimension, we will need M^d total points! We will see below that this intuition is correct– quasi monte carlo tend to work only in small dimensions. Although, it is the “effective” dimensionality that matters…)

There are basically two aspects to quasi monte carlo methods:

  1. How to choose the set of points \hat X.
  2. How fast quasi-monte carlo methods converge.

Despite its importance, I’ll skip the first issue. See chapter 2 of Tim Pillards’ thesis below for a nice overview.

The basic guarantees of covergence are: Regular MC methods converge like O(1/\sqrt{N}), while QMC methods converge like O(\log(N)^d/N), where N is the number of sample points.

Theoretically speaking, for any number of dimensions, QMC methods eventually win. Proof:

\lim_{N\rightarrow \infty} \frac{ \log(N)^d N^{-1}}{ N^{-1/2}}= 0

However, in reality, the crossover point is laughably high when d is large. Nevertheless, it has been found in practice in many application (especially financial applications) that QMC nevertheless can produce better estimates, despite a dimension (e.g. 300) where the convergence results about would note suggest QMC would be better.  People generally explain this by saying that the “intrinsic” dimensions of these problems is not of so high.  (Personally, I suspect the real explanation is messier than this)

References:

Tim Pillards’ thesis: QUASI-MONTE CARLO INTEGRATION OVER A SIMPLEX AND THE ENTIRE SPACE

Wikipedia on Quasi-Monte Carlo methods in finance has some nice figures.

Leave a Reply