Uniform Distribution and Quasi-Monte Carlo Methods

Discrepancy, Integration and Applications

Peter Kritzer, Harald Niederreiter, Friedrich Pillichshammer, Arne Winterhof, Peter Kritzer, Harald Niederreiter, Friedrich Pillichshammer, Arne Winterhof

• Publisher: De Gruyter
• Year: 2014
• Topic: Mathematics
• eBook ISBN:
  9783110375039
• Subtopic: Computer Graphics
• Index: Mathematics

This book is summarizing the results of the workshop "Uniform Distribution and Quasi-Monte Carlo Methods" of the RICAM Special Semester on "Applications of Algebra and Number Theory" in October 2013.

The survey articles in this book focus on number theoretic point constructions, uniform distribution theory, and quasi-Monte Carlo methods. As deterministic versions of the Monte Carlo method, quasi-Monte Carlo rules enjoy increasing popularity, with many fruitful applications in mathematical practice, as for example in finance, computer graphics, and biology.

The goal of this book is to give an overview of recent developments in uniform distribution theory, quasi-Monte Carlo methods, and their applications, presented by leading experts in these vivid fields of research.

Josef Dick and Friedrich Pillichshammer

Explicit constructions of point sets and sequences with low discrepancy

Abstract: In this article we survey recent results on the explicit construction of finite point sets and infinite sequences with optimal order of L_q discrepancy. In 1954, Roth proved a lower bound for the L₂ discrepancy of finite point sets in the unit cube of arbitrary dimension. Later, various authors extended Roth’s result to lower bounds also for the

discrepancy and for infinite sequences. While it has already been known from the early 1980s that Roth’s lower bound is best possible in the order of magnitude, it was a longstanding open question to find explicit constructions of point sets and sequences with optimal order of L₂ discrepancy. This problem was solved by Chen and Skriganov in 2002 for finite point sets and recently by the authors of this article for infinite sequences. These constructions can also be extended to give optimal order of the

discrepancy of finite point sets for q ∈ (1, ∞). The main aim of this article is to give an overview of these constructions and related results.

Keywords:

discrepancy, explicit constructions, digital nets and sequences

Mathematics Subject Classification 2010: 11K06, 11K38

Josef Dick: School of Mathematics and Statistics, The University of New South Wales, Sydney, NSW 2052, Australia, e-mail: [email protected]

Friedrich Pillichshammer : Department of Financial Mathematics, Johannes Kepler University Linz, Altenbergerstraße 69, 4040 Linz, Austria, e-mail: [email protected]

Acknowledgement: We appreciate several comments, suggestions and improvements from our colleagues Dmitriy Bilyk, Peter Kritzer, Harald Niederreiter, Arne Winterhof and from the anonymous referee.

1 Introduction

We consider equidistribution properties of sequences in the s-dimensional unit-cube [0, 1)^s measured by their

discrepancy (see [2, 16, 18, 30, 32]). For a finite set

of points in the s-dimensional unit-cube [0, 1)^s the local discrepancy function is defined as

where t = (t₁, t₂, . . . , t_s) ∈ [0, 1]^S and

denotes the number of indices n with x_n ∈ [0, t₁) × ··· × [0, t_s) =: [0, t). The local discrepancy function measures the difference of the portion of points in an axis-parallel box containing the origin and the volume of this ...

Table of contents

• Title Page
• Copyright Page
• Preface
• Table of Contents
• Metric number theory, lacunary series and systems of dilated functions
• Strong uniformity
• Discrepancy theory and harmonic analysis
• Explicit constructions of point sets and sequences with low discrepancy
• Subsequences of automatic sequences and uniform distribution
• On Atanassov’s methods for discrepancy bounds of low-discrepancy sequences
• The hybrid spectral test: a unifying concept
• Tractability of multivariate analytic problems
• Discrepancy estimates for sequences: new results and open problems
• A short introduction to quasi-Monte Carlo option pricing
• The construction of good lattice rules and polynomial lattice rules
• Index
• Radon Series on Computational and Applied Mathematics