Sobol with 64-bits integers

A while ago, I wondered how to make some implementation of Sobol support 64-bits integers (long) and double floating points. Sobol is the most used quasi random number generator (QRNG) for (quasi) Monte-Carlo simulations.

The standard Sobol algorithms are all coded with 32-bits integers and lead to double floating point numbers which can not be smaller than \( 2^{-31} \). I was recently looking back at the internals at Sobol generators, and noticed that generating with 64-bits integers would not help much.

A key to understanding why is to analyze exactly what is the output that Sobol generates. If one asks for a sequence of N numbers (in dimension D), the output will be a multiple of \( 2^{-L} \) where L is the log-2 of N. The 32 bits only become useful when \( N > 2^{31} \). An implementation with 64-bit integers becomes only useful if we query an extremely long sequence (longer than 1 billion numbers), which is not all that practical in reality. Furthermore, the direction numbers would then require double the amount of memory (which may be relatively large for 20K dimensions).

Another interesting detail I learnt recently was to avoid skipping the first point, when scrambling (or randomization) is applied, as per this article from Owen (2020). In a non-randomized or non-scrambled setting, we skip the first point typically because it is 0, and 0 is often problematic, for example if we need to take the inverse cumulative distribution function, to simulate a specific distribution. What I find slightly surprising is that there is no symmetry between 1 and 0: the point (1, 1) is never generated by a two-dimensional Sobol generator, but (0, 0) is the first number. If we apply some sort of inverse cumulative distribution (and no scrambling), it looks like then the result would be skewed towards negative infinity.

Comments

comments powered by Disqus