Constructions of low-discrepancy point sets and sequences.

• Main Author: Yeo, Anderson Siang Jing.
• Other Authors: Xing Chaoping
• Format: Theses and Dissertations
• Language: English
• Published: 2013
• Subjects: DRNTU::Science::Mathematics
• Online Access: http://hdl.handle.net/10356/52664
• Institution: Nanyang Technological University

Low-discrepancy point sets and sequences play an important role in quasi-Monte Carlo method for numerical integration. They provide good quadrature points for estimating the de nite integrals of functions that cannot be integrated analytically. We study two types of low-discrepancy point sets and sequences. The rst type is Halton sequences, introduced by Halton [8]. Halton sequences are explicitly generated low-discrepancy sequences, where the construction of the terms in Halton sequences is straightforward through the use of the radical inverse function. The second type of low-discrepancy point sets and sequences are (t; m; s)-nets and (t; s)-sequences, introduced by Niederreiter [24]. Both (t; m; s)-nets and (t; s)-sequences are de ned by means of predetermined distribution property of their terms with respect to a class of intervals. General principles for the construction of (t; m; s)-nets and (t; s)-sequences are based on the digital method introduced in [24, Section 6]. This method links the construction of (t; m; s)-nets to the construction of some Fb-linear subspaces of Fms b via duality theory established by Niederreiter and Pirsic [31]. In this thesis, we present four constructions of low-discrepancy point sets and sequences. The following is a brief overview of each construction: The rst construction comes from the direct application of duality theory inspired by the (a+x; b+x; a+b+x)-construction of linear codes, also known as the tripleerror- correcting codes. This construction of digital nets is also called the (a + x; b + x; a + b + x)-construction. This is considered a new construction because it is not a special case of the matrix product construction for digital nets [29] (where the (u; u + v)-construction [2] is a special case). The second construction is a generalization of Halton sequence called the doublyin nite Halton sequence. Many generalizations of Halton sequence that have been proposed, permute the b-adic digits in the b-adic expansion of the index of Halton sequence. Our generalization proceeds in a di erent direction. Instead we expand the index of Halton sequence from the set of non-negative integers to the set of all integers. The construction of the terms of this sequence uses the Monna map, a generalization of the radical inverse function to the set of all integers. The star discrepancy of doubly-in nite Halton sequence can be shown to have the same order of magnitude as the star discrepancy of classical Halton sequence. Moreover, doubly-in nite Halton sequence turns out to be symmetric sequence resulting from the symmetrization of Halton sequence. Symmetric sequence and symmetrization of sequence into symmetric sequence has been studied in relation to L2-discrepancy [40, 41]. Thus doubly-in nite Halton sequence being symmetric sequence gives a result on star discrepancy for symmetric sequence. The third construction is a new Halton-type sequence from global function elds. This construction can be viewed as a generalization of Halton sequence, where the index of the sequence is now taken from elements in a function eld. The generating algorithm of the terms in this sequence is very similar to the generating algorithm of terms in the classical Halton sequence. We use a modi ed radical inverse function for the ring of integers. It turns out that our Halton-type sequence can be t into the framework of (t; s)-sequences as well, which leads to a better star discrepancy bound. This gives an explicit and direct formula for the construction of the terms of (t; s)-sequences, an advantage that is not presented in the digital method for (t; s)- sequences. To our knowledge, this is also the rst general construction for (t; s)- sequences that is not directly based on the digital method. The fourth construction is a digital net derived from algebraic number elds. Thisconstruction utilizes the digital method. However the rows of generating matrices of this digital net are constructed from the residue eld with respect to a prime ideal of a number eld. The rows of these generating matrices depend on the choice of uniformizing parameters from a set of prime ideals which are pairwise coprime and each of these prime ideals are coprime to the prime ideal used to obtain the residue eld. Despite not o ering an improvement to the parameters of digital nets, this construction is rather interesting from the pure mathematics point of view.