<< Projections Tutorials Efficiency >>

Low Discrepancy >> Low Discrepancy > Tutorials > (t,m,s)-nets

(t,m,s)-nets

(t,m,s)-nets and low discrepancy sequences.

Purpose

The goal of this page is to show the (t,m,s)-net properties of low discrepancy sequences.

Definitions

Definition: Elementary interval in one dimension. Let b be the base, with b≥2. An elementary interval in base b is an interval with integers a and d such that d≥0 and 0≤ a < b^d.

Definition: Elementary interval in base b in s dimensions. Let b be the base, with b≥2. An elementary interval in base b of the hypercube is an interval with integers a_i and d such that d≥0 and 0≤ a_i < b^d_i, for i=1,2,...,s.

Corollary: Volume of an elementary interval in base b. The volume of E is

The following example plots all base-2 elementary intervals with volume 1/2^3=1/8.

scf();
lowdisc_plotbmbox(2,3)

Definition: (t,m,s)-net in base b. Let b≥2, s≥1 and 0≤t≤m be integers. Then a point set with b^m points in is a (t,m,s)-net in base b if every elementary interval in base b with volume contains exactly points.

Comment: Smaller t provides a greater uniformity. At best, we have t=0, for which the smallest volume is achieved, with 1 point by elementary interval.

Corollary: (0,m,s)-net in base b. Let b≥2, s≥1 be integers. Then a point set with points in is a (0,m,s)-net in base b if every elementary interval in base b with volume contains exactly one point.

Definition : (t,s)-sequence in base b. Let b≥2, s≥1 and t≥0 be integers. Then the infinite sequence , , ... of points in is a (t,s) sequence in base b if, for all k≥0 and m≥t, the point set

which has points, is a (t,m,s)-net in base b.

Comment: A smaller base b is preferable because the uniformity properties of (t,m,s)-nets and (t,s)-sequences are exhibited in sets of elementary intervals.

Theorems

The following table presents the quality parameters t of binary (t,s)-sequences. For Sobol sequence, this is the table in section 3.4 of [6]. We consider here the Niederreiter sequence in base 2 (see table II in [5]).

      s                   1 2 3 4 5 6  7  8  9 10 11 12 13
      Niederreiter (b=2)  0 0 1 3 5 8 11 14 18 22 26 30 34
      Sobol               0 0 1 3 5 8 11 15 19 23 27 31 35
    
      s                   14 15 16 17 18 19 20 21 22 23 24 25
      Niederreiter (b=2)  38 43 48 53 58 63 68 73 78 83 89 95
    
      s                   26  27  28  29  30
      Niederreiter (b=2) 101 107 113 119 125
    

Discrepancy

Definition: multi-dimensional interval. The set P is an interval of if:

for j=1,2,...,s.

Definition: star intervals. The I* set is the set of origin-anchored intervals in :

Definition: number of points and volume of an interval. Let x be a sequence of more than n points in . Then x(n) represents the set of the first n points of the sequence x. Let P be an interval. Therefore, A(P,x(n)) is the number of points from x(n) in the interval P. Moreover, is the volume of P:

Definition: star discrepancy. Let x be a sequence of more than n points in . The star discrepancy D*(x) measures the lack of uniformity of the first n points:

Estimate of the mean by a low discrepancy sequence

Theorem (Koksma-Hlawka): Let f from to R be a function where V(f), the variation in the sense of Hardy and Krause, is bounded, therefore, for any sequence of n points x(n), we have

Theorem (Niederreiter): For any (t,s)-sequence in base b, we have

In other words, any (t,s)-sequence is a low discrepancy sequence.

In the previous inequality, the dominating term when n is large is 1/n. However, for moderate n, the factor log(n)^s must be taken into account. Indeed, we the function log(n)^s/n increases for n lower than exp(s). In other words, for increasing values of s, the number of points n required to get into the asymptotic discrepancy rate is larger and larger.

The following table presents the constant C(b,s,t) for several sequences. This is the table 4.2 in [1].

      
s        2     3     4      5      6      7       8       9         10
Halton   0.65  0.81  1.25   2.62   6.13   17.3    52.9    185.5     771.5
Sobol    0.26  0.25  0.541  0.833  1.6    2.6     7.6     19.6      45.0
Faure    0.26  0.13  0.099  0.025  0.019  0.0041  0.0089  2.1x10-3  4.2x10-4
Nieder.  0.26  0.13  0.086  0.025  0.019  0.0041  0.0030  6.1x10-4  4.2x10-4
   
    

Halton sequence

// Get the points 0,1,...,11 (insert zero)
u=lowdisc_ldgen ( 11 , 2 , "halton" );
u = [0,0;u];
//
scf();
subplot(1,2,1);
plot(u(:,1),u(:,2),"bo")
lowdisc_plotelembox([2 3],[2 1])
xtitle("Halton, Volume=1/12, 12 Points");
h = gca();
h.isoview="off";
//
subplot(1,2,2);
plot(u(:,1),u(:,2),"bo")
lowdisc_plotelembox([2 3],[1 1])
xtitle("Halton, Volume=1/6, 12 Points");
h = gca();
h.isoview="off";

Faure sequence

In dimension s=2, the Faure sequence uses the base 2. Moreover, the Faure sequence is a (0,2)-sequence in base 2 (i.e. the quality parameter t is zero). We choose m=4, and check that Faure is a (0,4,2)-net in base 2. Hence, we have to consider b^m=2^4=16 points and check that there are b^t=1 points for any elementary interval of volume 1/b^m=1/16.

Plot 2^4=16 Faure points (insert zero) and plot elementary intervals with volume 1/2^4=1/16 there is 1 point by box.

u=lowdisc_ldgen ( 2^4-1 , 2 , "faure" );
u = [0,0;u];
scf();
lowdisc_plotbmbox(2,4,u);

Plot 2^4=16 Faure points (insert zero) and plot elementary intervals with volume 1/2^3=1/8: there are 2 points by box.

u=lowdisc_ldgen ( 2^4-1 , 2 , "faure" );
u = [0,0;u];
scf();
lowdisc_plotbmbox(2,3,u);

Plot 16 Faure points and plot elementary intervals with volume 1/8 : there are two points by interval. Moreover, the first 8 points fill all intervals (1 point by interval), while the points from 9 to 16 again fill the intervals.

// Get the points 0,1,...,15 (insert zero)
u=lowdisc_ldgen ( 2^4-1 , 2 , "faure" );
u = [0,0;u];
scf();
//
subplot(2,2,1);
plot(u(1:8,1),u(1:8,2),"bo")
plot(u(9:16,1),u(9:16,2),"g*")
legend(["Points 1-8","Points 9-16"]);
lowdisc_plotelembox(2,[3 0]);
xtitle("Faure, Volume=1/8, 16 Points");
h = gca();
h.isoview="off";
//
subplot(2,2,2);
plot(u(1:8,1),u(1:8,2),"bo")
plot(u(9:16,1),u(9:16,2),"g*")
legend(["Points 1-8","Points 9-16"]);
lowdisc_plotelembox(2,[2 1]);
xtitle("Faure, Volume=1/8, 16 Points");
h = gca();
h.isoview="off";
//
subplot(2,2,3);
plot(u(1:8,1),u(1:8,2),"bo")
plot(u(9:16,1),u(9:16,2),"g*")
legend(["Points 1-8","Points 9-16"]);
lowdisc_plotelembox(2,[0 3]);
xtitle("Faure, Volume=1/8, 16 Points");
h = gca();
h.isoview="off";
//
subplot(2,2,4);
plot(u(1:8,1),u(1:8,2),"bo")
plot(u(9:16,1),u(9:16,2),"g*")
legend(["Points 1-8","Points 9-16"]);
lowdisc_plotelembox(2,[1 2]);
xtitle("Faure, Volume=1/8, 16 Points");
h = gca();
h.isoview="off";

Niederreiter base 2 sequence

Plot elementary intervals with Niederreiter (base 2) points (insert zero) Plot elementary intervals with volume 2^4: 2 points by elementary interval. Niederreiter is a (0,5,2)-net in base 2

u=lowdisc_ldgen ( 2^5-1 , 2 , "niederreiter" );
u = [0,0;u];
scf();
lowdisc_plotbmbox(2,4,u);

Plot elementary intervals with Niederreiter (base 2) points (insert zero) Plot elementary intervals with volume 2^3: 4 points by elementary interval. Niederreiter is a (0,5,2)-net in base 2

u=lowdisc_ldgen ( 2^5-1 , 2 , "niederreiter" );
u = [0,0;u];
scf();
lowdisc_plotbmbox(2,3,u);

Sobol sequence

Sobol is a (0,4,2)-net in base 2. Get 2^4=16 points (insert zero). Plot boxes with volume 2^4. There is 1 point by elementary interval. Use 2^2 subdivisions for X1, 2^2 subdivisions for X2.

u=lowdisc_ldgen ( 2^4-1 , 2 , "sobol" , %t );
u = [0,0;u];
h = scf();
lowdisc_plotbmbox(2,4,u);

Sobol is a (0,5,2)-net in base 2. Get 2^6 points (insert zero) Plot boxes with volume 2^5. There are two points by elementary interval. Use 2^3 subdivisions for X1, 2^2 subdivisions for X2.

u=lowdisc_ldgen ( 2^6-1 , 2 , "sobol" );
u = [0,0;u];
h = scf();
plot(u(1:2^5,1),u(1:2^5,2),"bo")
plot(u(2^5+1:2^6,1),u(2^5+1:2^6,2),"g*")
legend(["Points 1-32","Points 33-64"]);
lowdisc_plotelembox(2,[3 2]);
xtitle("Sobol, Volume=1/32, 64 Points");

Leaped sequences and (t,m,s)-nets

A common practice is to use a leaped sequence to improve the correlations in high dimensions. However, we may notice that a leaped sequence may lead to a set which is not a (t,m,s)-net anymore.

For example, let's see the first 12 points of a leaped Halton sequence.

u=lowdisc_ldgen ( 11 , 2 , "halton" , %f );
u = [0,0;u];
//
scf();
subplot(1,2,1);
plot(u(:,1),u(:,2),"bo")
lowdisc_plotelembox([2 3],[2 1])
xtitle("Halton, Volume=1/12, 12 Points");
h = gca();
h.isoview="off";
//
subplot(1,2,2);
plot(u(:,1),u(:,2),"bo")
lowdisc_plotelembox([2 3],[1 1])
xtitle("Halton, Volume=1/6, 12 Points");
h = gca();
h.isoview="off";

Although the unleaped Halton sequence had exactly 1 point by elementary interval, the leaped Halton sequence is not as regular : some intervals are empty (the top left on the left figure), some intervals have more points than expected (the bottom left on the left figure).

The same phenomenon may happen with a leaped Faure sequence.

lds = lowdisc_new("faure");
lds = lowdisc_configure(lds,"-dimension",2);
lds = lowdisc_configure(lds,"-leap",5);
lds = lowdisc_startup (lds);
[lds,u] = lowdisc_next (lds,2^4-1);
lds = lowdisc_destroy(lds);
u = [0,0;u];
scf();
lowdisc_plotbmbox(2,4,u);

Bibliography

[1] "Sur le calcul et la majoration de la discrepance a l'origine", These, Eric Thiemard, Lausanne, EPFL, 2000 Section 4.6 "Les (t,s)-suites et les (t,m,s)-reseaux. and Fig 4.7

[2] "Random number generation and quasi-Monte Carlo methods", H. Niederreiter, CBMS-NSF Series in Applied Mathematics, No. 63, SIAM, Philadelphia, 1992.

[3] "Monte-Carlo methods in Financial Engineering", Paul Glasserman, Springer, 2003 See Section 5.1.4 "Nets and sequences", and Fig. 5.3, page 292

[4] Applications of Scrambled Low Discrepancy Sequences to Exotic Options KS Tan, PP Boyle International AFIR Colloquium Proceedings, Australia, 1997

[5] "Low-discrepancy and low-dispersion sequences", Harald Niederreiter, Journal of Number Theory, Volume 30, 1988, pages 51-70.

[6] "Algorithm 659: Implementing Sobol's quasirandom sequence generator.", P. Bratley and B. L. Fox, 1988. ACM Trans. Math. Softw. 14, 1 (Mar. 1988), 88-100.


Report an issue
<< Projections Tutorials Efficiency >>