(t,m,s)-nets and low discrepancy sequences.
The goal of this page is to show the (t,m,s)-net properties of low discrepancy sequences.
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.
Van der Corput in base b are (0,1)-nets in base b.
Halton sequences are not (t,s)-sequences: the base b is not the same for all dimensions. However, a generalized (t,s)-sequence could be defined, with an extended definition taking into account for different bases.
Sobol sequence is a (t,s)-sequence in base 2 with t=O(slogs). Sobol sequence use the same base b=2 for all dimensions.
The Faure sequences are (0,s)-sequences in base b. Therefore, the Faure sequences are (0,m,s)-nets in base b, for any m≥0. Therefore, Faure sequences achieve the lowest possible value of t, but with increasing b (the smallest prime larger than s).
Niederreiter sequences are (0,s)-sequences defined for any base b, where b is a power of a prime.
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
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:
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.
Sobol sequence : C(b,s,t) grows to infinity, when s increases.
Faure sequences : C(b,s,t) grows to zero, when s increases.
Niederreiter sequences : C(b,s,t) grows to zero, when s increases.
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
// 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"; | ![]() | ![]() |
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"; | ![]() | ![]() |
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 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"); | ![]() | ![]() |
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); | ![]() | ![]() |
[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.