Sobol Sequence - Good Distributions in The S-dimensional Unit Hypercube

Good Distributions in The S-dimensional Unit Hypercube

Let Is = s be the s-dimensional unit hypercube and f a real integrable function over Is. The original motivation of Sobol was to construct a sequence x_n in Is so that

and the convergence be as fast as possible.

It is more or less clear that for the sum to converge towards the integral, the points x_n should fill Is minimizing the holes. Another good property would be that the projections of x_n on a lower-dimensional face of Is leave very few holes as well. Hence the homogeneous filling of Is does not qualify ; because in lower-dimensions many points will be at the same place, therefore useless for the integral estimation.

These good distributions are called (t,m,s)-nets and (t,s)-sequences in base b. To introduce them, define first an elementary s-interval in base b a subset of Is of the form

, where a_j, d_j are integers and a_jj for all j in {1, ...,s}

Given 2 integers, a (t,m,s)-net in base b is a sequence x_n of bm points of Is such that for all elementary interval P in base b of hypervolume λ(P) = bt-m.

Given a non-negative integer t, a (t,s)-sequence in base b is an infinite sequence of points x_n such that for all integers, the sequence is a (t,m,s)-net in base b.

In his article, Sobol described Π_τ-meshes and LP_τ sequences, which are (t,m,s)-nets and (t,s)-sequences in base 2 respectively. The terms (t,m,s)-nets and (t,s)-sequences in base b (also called Niederreiter sequences) where coined in 1988 by H. Niederreiter. The term Sobol sequences was introduced in late English-speaking papers in comparison with Halton, Faure and other low-discrepancy sequences.