Understanding Sobol sequences

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.

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.

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.

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.