Low-Discrepancy Sampling and Power-of-Two Sample Counts

# Optimal number of iterations for quasi-Monte Carlo


# Optimal number of iterations for quasi-Monte Carlo












I'm quoting from Peter Jäckel's book "Monte Carlo Methods in Finance", page 96:

> ...For low-discrepancy numbers, the situation is different. Sobol numbers and other number generators based on integer arithmetic module two, by construction provide additional equidistribution properties whenever the number of iteration is $N=2^n-1$

What's the mathematical incentive behind this choice of iterations?

Does the same apply to Halton sequences?

## Answer by Antoine Savine (score 1, accepted)

https://quant.stackexchange.com/a/42951

I posted a free self contained excerpt of my book Modern Computational Finance that explains Sobol's sequence and in particular its Latin Hypercube property, meaning that each axis is sampled evenly but in a different order for different axes, as long as the number of samples is a power of 2 minus 1. I hope it helps:

https://medium.com/@antoine_savine/sobol-sequence-explained-188f422b246b

Antoine Savine

## Answer by oliversm (score 2)

https://quant.stackexchange.com/a/41402

> Much of what follows can be found in Glasserman (2003), Chapter 5, Monte Carlo methods in financial engineering.

The reason for using low discrepancy numbers is because they are somewhat "equidistributed", meaning that you can guarantee that they fill the unit interval in a regular fashion without having large gaps. (the same is true for the unit square, or unit cube, etc.). In fact this is exactly what is meant by the "low discrepancy", where the discrepancy $D$ of a set of $n$ points $\mathbf{x} = \{x_i\}_{i=1}^n$ in a volume $\mathcal{A}$ is $$ D(\mathbf{x}; \mathcal{A}) = \sup_{A \subseteq \mathcal{A}} \left|\dfrac{\left|\{\mathbf{x} \cap A\}\right|}{n} - \mu(A)\right| $$ where $\mu(A)$ is the volume measure of $A$ the star discrepancy $D^*$ is when $\mathcal{A}$ is taken to be a rectangle. Notice that the discrepancy measures the uniformity of the points, by quantifying how big the voids are (relatively).

The reason we care is because the Koksma-Hlawka inequality bounds the error from the Monte Carlo estimate by a term proportional to $D^*$. Now it was Niederreiter who showed that the minimum in 1-dimension is obtained by equidistant points. However, these scale badly with higher dimension, but low-discrepancy sequences have a star discrepancy scaling with $\mathcal{O}((\log{n})^d/n)$, and so scale very well with dimension (up to about 40 or so). If we consider a 1-dimensional sequence for generating a low-discrepancy sequence, such as either a Sobol or Halton sequence (there are many more), then these begin by sampling points on dyadic intervals. The simplest is the Halton sequence which is to write integers in binary with a single decimal place and then reverse the sequence of digits (e.g. 1,2,3 become 1.0, 10.0, 11.0 which produce 0.1, 0.01, 0.11, etc.). We can see that these sequences are only equidistant (and hence have the minimal star discrepancy) when we have $N=2^n - 1$ (we can drop the $-1$ if we decide to include zero). This is best seen pictorially in 2-dimensions (I have included the zero in the sequence):

Notice in the random points there are large voids, whereas the low discrepancy sobol sequence fills the grid uniformly. However, this uniformity is optimal when there are $2^n$ (or $2^n-1$ if not using the zero) points.