Book contents
- Frontmatter
- Dedication
- Contents
- Preface
- Notation
- 1 Introduction
- 2 Quasi–Monte Carlo integration, discrepancy and reproducing kernel Hilbert spaces
- 3 Geometric discrepancy
- 4 Nets and sequences
- 5 Discrepancy estimates and average type results
- 6 Connections to other discrete objects
- 7 Duality theory
- 8 Special constructions of digital nets and sequences
- 9 Propagation rules for digital nets
- 10 Polynomial lattice point sets
- 11 Cyclic digital nets and hyperplane nets
- 12 Multivariate integration in weighted Sobolev spaces
- 13 Randomisation of digital nets
- 14 The decay of the Walsh coefficients of smooth functions
- 15 Arbitrarily high order of convergence of the worst-case error
- 16 Explicit constructions of point sets with the best possible order of L2-discrepancy
- Appendix A Walsh functions
- Appendix B Algebraic function fields
- References
- Index
5 - Discrepancy estimates and average type results
Published online by Cambridge University Press: 05 July 2014
- Frontmatter
- Dedication
- Contents
- Preface
- Notation
- 1 Introduction
- 2 Quasi–Monte Carlo integration, discrepancy and reproducing kernel Hilbert spaces
- 3 Geometric discrepancy
- 4 Nets and sequences
- 5 Discrepancy estimates and average type results
- 6 Connections to other discrete objects
- 7 Duality theory
- 8 Special constructions of digital nets and sequences
- 9 Propagation rules for digital nets
- 10 Polynomial lattice point sets
- 11 Cyclic digital nets and hyperplane nets
- 12 Multivariate integration in weighted Sobolev spaces
- 13 Randomisation of digital nets
- 14 The decay of the Walsh coefficients of smooth functions
- 15 Arbitrarily high order of convergence of the worst-case error
- 16 Explicit constructions of point sets with the best possible order of L2-discrepancy
- Appendix A Walsh functions
- Appendix B Algebraic function fields
- References
- Index
Summary
The motivation for introducing and studying the concept of (t, m, s)-nets and (T, s)- sequences was to generate point sets (also sometimes in high dimensions) with as small a discrepancy as possible. In this chapter we give an overview of theoretical results for the discrepancy of (digital) nets and sequences.
While singular results were already given by Sobol′ [253] and by Faure [68], the first systematic study of the discrepancy of nets was given by Niederreiter [168]. These results can also be found in [177, Chapter 4]. Further results on the star discrepancy of digital nets and sequences, mainly for low dimensions, can be found in [40, 71, 72, 74, 125, 126, 144, 145, 213].
After the work of Niederreiter [172, 177], metrical and average results on the discrepancy of nets and net-sequences were given; see, for instance, [134, 135, 136, 138, 140]. Further, the study of weighted discrepancy of net-type point sets also received considerable attention in recent years (see, for example, [49, 146]).
Even though we have many results for the extreme and star discrepancies, very little is known about concrete theoretical estimates for the Lp-discrepancy, especially for net-type point sets. Singular results in this direction can be found in [20, 22, 75, 142, 143, 212, 244] (results concerning the L2-discrepancy are presented in Chapter 16).
- Type
- Chapter
- Information
- Digital Nets and SequencesDiscrepancy Theory and Quasi–Monte Carlo Integration, pp. 180 - 233Publisher: Cambridge University PressPrint publication year: 2010