Sobol' and Halton sequences should start with 0

Methodology
1

This thread is there to enable further discussion on the topic raised in

3

There are two different points in Owen’s paper:

  • First, start the sequence at 0 to preserve the net property
  • Second, scramble things if you want to control the error in a quasi-Monte Carlo algorithm
    In OT, the first point is the responsibility of the LowDiscrepancySequence class and its derived classes, and the second point is the responsibility of the LowDiscrepancyExperiment class
    In my view only the low discrepancy sequences have to be fixed, the LowDiscrepancyExperiment class is correct.
4

Is scrambling (that is, performing random permutations on digits) implemented in OT? Apparently, since all permutations depend on one another, it is computationally expensive.

5

There is no scrambling in OT. Pamphile’s suggestion is excellent on the maths, but adding the 0 in e.g. the current Sobol’ sequence does not seem to be a good idea, because it will make most algorithms fail: scrambling is the correct solution for this. It is rather an improvement than a bug.

I adapted a C++ implementation at:

Below is a list of implementations, based on an analysis done for Scilab in 2013:

(Apparently, my Scilab account was hacked in 2019!)

Perhaps there are more up-to-date implementations as of 2020, e.g. Boost or the GSL ?

Regards,

Michaël

6

Ouppsss sorry for the mess between scrambling and randomization. I may have missed something but I understood that Owen advocated the use of both the initial point at (0,…,0) and scrambling. Am I wrong?

I agree on the fact that it is more an improvement than a bug. Nevertheless, it would be good to allow for the Sobol sequence to start from 0 when needed, which is not currently possible.

7

You are correct. Having the zero is important as well as randomization. So it is good to scramble, but even better to scramble and have the zero. Having the zero without scrambling is less performant than scrambling without zero.

8

From @ArtOwen on Github:

Randomizing by adding a vector \boldsymbol{U} \sim U[0,1]^d and taking the result modulo 1 (ie wraparound) is known as a Cranley-Patterson rotation. They proposed it for lattice rules in the 1970s. It does give you randomized QMC points. But if you use a digital net like a Sobol’ sequence then shifting like this does not produce a new net. It also has an inferior convergence rate increasing variance by a factor of about n for smooth integrands compared to scrambling. Intuitively the problem is that it does not introduce enough randomness.

In the d=1 case, where we don’t need QMC, it is easy to see what is going on. The unrandomized Sobol’ sequence would have x_i = (i-1)/n for 1 \leq i \leq n. Shifting would give points x_i = (i-u)/n for some u in [0,1] after relabeling. Scrambling would give x_i ~ U[(i-1)/n,i/n) independently (i.e., stratified sampling) bringing an error cancellation that shifting does not bring.