13
$\begingroup$

Can someone explain to me in simple terms, how Sobol sequences work? The wikipedia article is fairly technical.

They look pretty interesting. So I shall describe (whatever little I know) in short the results to someone who is not aware of what Sobol sequences do- One can use Sobol sequences to fill up a space with "random" points. The nice thing about it is that the points distribute themselves fairly evenly and therefore sample the space uniformly (to a good extent) without having a pattern per se. Here is the distribution of points in 2D, as number of points increase.

Taken from "Numerical Recipies in C",Press, Teukolsky et all.

As shown in the last figure, putting together all the points also follows the same property - uniform distribution of points.

There has been a related question The mathematics behind Sobol sequences, but that is asking for sources to study about Sobol sequences from, not an explanation.

$\endgroup$

3 Answers 3

6
$\begingroup$

The intuition behind the Sobol sequence is quite simple actually: The idea is to subdivide each dimension in $2^{N}$ points. That is, you will have: $$ x, y, z, ... \in \left\{{k \over 2^N}, k \in \left[0 .. 2^{N}-1\right]\right\} $$

Then, the sequence associate to an index $n \in [0 .. 2^{N}-1]$ a single tuple $\mathbf{p} = (x_n, y_n, z_n, ...)$. The question is how to select each element of the tuple to ensure a good distribution.

Without going into too much details (that you can find in Lemieux' book, Section 4.4.1) it is done using generative matrices $\mbox{C}_x, \mbox{C}_y, \mbox{C}_z, ...$ that convert the binary representation of the index $n = \sum_i n_i 2^i$ to the binary representation of the position on each dimension: $$ x_n = \sum_{k=0}^{N-1} t_k \, 2^{-k-1}, \;\; \mbox{with} \; \mathbf{t} = \mathbf{n} \times \mbox{C}_x, $$ and $t_k$ is the k-th element of $\mathbf{t} = [t_0, ... t_{N-1}]$. Note that the matrix multiplication above is not the classical multiplication but is done modulo 2. The generative matrices are related to the polynomial mentioned above.

Here is an example of matrices you could use in 2D, for $M=6$: $$C_x = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix} \; \; C_y = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 & 1 \end{pmatrix} $$

The property that the next batch of points $n \in [2^{N}, .. 2^{N+1}-1]$ will fill the 'empty spaces' can be understood by the fact that they will project on a finer subdivision of each unit axis.

$\endgroup$
1
$\begingroup$

Sobol sequences belong to the class of Quasi Random Generators (by opposition of Pseudo Random Generators).

Quasi Random Generators by construction minimize the discrepancy between the sub square (ie sub interval). Discrepancy is the (maximum) between 2 points inside sub-interval.

Quasi Random Generators are deterministic generators of points.

Sobol uses initial polynome to generate unform across one dimension. In d dimension, there are d Sobol generators (determined by d polynomes of initilization).

However, Sobol has flaws. The graph you shown is valid only a lower dimensions.

$\endgroup$
1
  • 2
    $\begingroup$ Regarding the flaws, randomize and scrambled version solve this issue. See Broda, Kucherenko et al. etc. Also SciPy's documentation (version 1.7 currently in development). $\endgroup$
    – tupui
    Apr 12, 2021 at 10:42
0
$\begingroup$

Additonnally, good properties of Sobol (uniformity) comes from the choice of Polynonme and initial integers for each dimension. Property A and A' should be satistified for better convergence.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .