5
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ The sentence immediately following that doesn't sufficiently explain it? "This is easy to see on the unit interval in one dimension, where such a choice of draws always results in a perfectly regular distribution of points, and can also be confirmed in the empirical discrepancy diagrams of section 8.6 up to dimension 5." $\endgroup$ – LocalVolatility Jun 16 '17 at 12:15
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Just ordered the book, Antoine! Looking forward to ordering the new one as well. Thanks a lot! $\endgroup$ – ZeroCool Dec 7 '18 at 20:32
  • $\begingroup$ Cool, I hope you enjoy it. Looking forward to reading your impressions. Don't hesitate to ask questions too. I can be reached on linkedIn or GoodReads. $\endgroup$ – Antoine Savine Dec 13 '18 at 0:02
2
$\begingroup$

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):

enter image description here

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.

$\endgroup$
  • $\begingroup$ It's not just that they're somewhat equally distributed (density wise), it's that that property is maintained when you project onto subspaces of the total space as well. $\endgroup$ – will Oct 22 '18 at 21:06
  • $\begingroup$ This is reflected in the supremum $\endgroup$ – oliversm Oct 22 '18 at 21:09
  • $\begingroup$ Ah yes, missed that. $\endgroup$ – will Oct 23 '18 at 5:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.