Distribution properties of generalized van der Corput sequences

Abstract

Folgen mit kleiner Diskrepanz erhalten ihre Bedeutung durch ihre Anwendbarkeit in den verschiedensten Gebieten, wie zum Beispiel im Bereich der nummerischen Integration oder der Optimierung. Das Ziel der nummerischen Integration ist es, ein Integral durch eine Summe von gewichteten Funktionswerten zu ersetzen. Um die Punkte, an der die Funktion ausgewertet wird, zu bestimmen stehen verschiedene Methoden zur Verfügung, eine davon ist die Monte Carlo Methode, bei der diese zufällig gewählt werden. Eine andere Möglichkeit besteht darin Folgen mit bestimmten Verteilungs-Eigenschaften zu verwenden, in diesem Fall spricht man von der Quasi-Monte Carlo Methode. Ein großer Vorteil dieser Vorgehensweise besteht darin, dass Punkte zu einem späteren Zeitpunkt eingefügt werden können ohne die ganze Folge neu berechnen zu müssen. Außerdem erlaubt die Approximation eines Integrals mit der Quasi-Monte Carlo Methode eine Zerlegung des Fehlers in einen Term, der nur von dem Integranden f(x) abhängt und einen, der nur von der Folge bestimmt wird. Das ist ein Resultat aus der Formel von Koksma-Hlawka, siehe auch Satz. Ein wichtiger Anwendungsbereich solcher Folgen ist die Finanz- und Versicherungsmathematik, wo hochdimensionale Integrale berechnet werden müssen und gerade diese Methoden sehr erfolgreich sind. In diesem Zusammenhang sind Folgen mit kleiner Diskrepanz, das heißt Folgen deren Diskrepanz von der Ordnung (log N) s ist, wobei s die Dimension der Folge bezeichnet, von besonderer Bedeutung. Ein Beispiel für solche Folgen sind die van der Corput Folgen, die 1935 von J. G. van der Corput eingeführt wurden. Eine Verallgemeinerung dieser Folgen geht auf H. Faure zurück, sie werden permutierte oder verallgemeinerte van der Corput Folgen genannt. Ziel der vorliegenden Arbeit ist es, ein Resultat von M. Drmota, G. Larcher und F. Pillichshammer zu verallgemeinern. Dort wurde ein zentraler Grenzwertsatz für die Diskrepanz von van der Corput Folgen in der Basis 2 gezeigt. Diese Erebnisse sollen nun auf allgemeine Basen erweitert werden, außerdem wird versucht ähnliche Aussagen für verallgemeinerte van der Corput Folgen zu beweisen.<br />

The importance of sequences with low discrepancies arises from various applications, for example in integration and optimization theory. In numerical integration one tries to approximate an integral by a sum of weighted function values. There are different techniques to obtain the nodes, where the function is evaluated. For example, using the Monte Carlo Method they are chosen randomly. Another possibility is to use certain deterministic sequences with given distribution properties, in this case one speaks of Quasi-Monte Carlo Methods. A big advantage of the latter is the possibility to add additional points without recalculating the whole series. Furthermore the Quasi-Monte Carlo integration allows a decomposition of its error term in the product of a term only depending on the sequence and one only depending on the function f(x). This is accomplished by the formula of Koksma-Hlawka. An important application of Quasi-Monte Carlo integration can be found in financial and actuary mathematics. There one needs to evaluate high-dimensional integrals. With the help of Quasi-Monte Carlo methods it is frequently possible to obtain good results for those integrals.<br />In this context low discrepancy sequences are of special interest. This are sequences with a discrepancy of order (log N) s where $s$ is the dimension of the sequence. The van der Corput sequences are one example for low discrepancy sequences. They were first introduced by J. G. van der Corput in 1935. A generalization of these sequences is due to H.<br />Faure, they are called permuted or generalized van der Corput sequences.<br />M. Drmota, G. Larcher and F. Pillichshammer proved a central limit theorem for the discrepancy of the van der Corput sequence in base 2. In this work we want to extend these results to generalized van der Corput sequences and arbitrary bases.