Random and Quasi-Random Point Sets

This volume is a collection of survey papers on recent developments in the fields of quasi-Monte Carlo methods and uniform random number generation. We will cover a broad spectrum of questions, from advanced metric number theory to pricing financial derivatives. The Monte Carlo method is one of the most important tools of system modeling. Deterministic algorithms, so-called uniform random number gen­ erators, are used to produce the input for the model systems on computers. Such generators are assessed by theoretical ("a priori") and by empirical tests. In the a priori analysis, we study figures of merit that measure the uniformity of certain high-dimensional "random" point sets. The degree of uniformity is strongly related to the degree of correlations within the random numbers. The quasi-Monte Carlo approach aims at improving the rate of conver­ gence in the Monte Carlo method by number-theoretic techniques. It yields deterministic bounds for the approximation error. The main mathematical tool here are so-called low-discrepancy sequences. These "quasi-random" points are produced by deterministic algorithms and should be as "super"­ uniformly distributed as possible. Hence, both in uniform random number generation and in quasi-Monte Carlo methods, we study the uniformity of deterministically generated point sets in high dimensions. By a (common) abuse oflanguage, one speaks of random and quasi-random point sets. The central questions treated in this book are (i) how to generate, (ii) how to analyze, and (iii) how to apply such high-dimensional point sets.

From Probabilistic Diophantine Approximation to Quadratic Fields.- 1 Part I: Super Irregularity.- 2 Part II: Probabilistic Diophantine Approximation.- 2.1 Local Case: Inhomogeneous Pell Inequalities - Hyperbolas.- 2.2 Beyond Quadratic Irrationals.- 2.3 Global Case: Lattice Points in Tilted Rectangles.- 2.4 Simultaneous Case.- 3 Part III: Quadratic Fields and Continued Fractions.- 3.1 Cesaro Mean of % MathType!MTEF!2!1!+- % feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaaeaaaaaaaaa8 % qadaaeabqaamaacmaabaGaamOBaiabeg7aH9aadaahaaWcbeqaa8qa % caaIXaGaai4laiaaikdaaaaakiaawUhacaGL9baaaSqabeqaniabgg % HiLdaaaa!3F6B!$$ \sum {\left\{ {n{\alpha ^{1/2}}} \right\}} $$ and Quadratic Fields.- 3.2 Hardy-Littlewood Lemma 14.- 4 Part IV: Class Number One Problems.- 4.1 An Attempt to Reduce the Yokoi’s Conjecture to a Finite Amount of Computation.- 5 Part V: Cesaro Mean of % MathType!MTEF!2!1!+- % feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcqaaaaaaaaaWdbe % aadaaeqaWdaeaapeWaaeWaa8aabaWdbmaacmaapaqaa8qacaWGUbGa % eqySdegacaGL7bGaayzFaaGaeyOeI0IaaGymaiaac+cacaaIYaaaca % GLOaGaayzkaaaal8aabaWdbiaad6gaaeqaniabggHiLdaaaa!42C9!$$ \sum\nolimits_n {\left( {\left\{ {n\alpha } \right\} - 1/2} \right)} $$.- 6 References.- On the Assessment of Random and Quasi-Random Point Sets.- 1 Introduction.- 2 Chapter for the Practitioner.- 2.1 Assessing RNGs.- 2.2 Correlation Analysis for RNGs I.- 2.3 Correlation Analysis for RNGs II.- 2.4 Theory vs. Practice I: Leap-Frog Streams.- 2.5 Theory vs. Practice II: Parallel Monte Carlo Integration.- 2.6 Assessing LDPs.- 2.7 Good Lattice Points.- 2.8 GLPs vs. (tms)-Nets.- 2.9 Conclusion.- 3 Mathematical Preliminaries.- 3.1 Haar and Walsh Series.- 3.2 Integration Lattices.- 4 Uniform Distribution Modulo One.- 4.1 The Definition of Uniformly Distributed Sequences.- 4.2 Weyl Sums and Weyl’s Criterion.- 4.3 Remarks.- 5 The Spectral Test.- 5.1 Definition.- 5.2 Properties.- 5.3 Examples.- 5.4 Geometric Interpretation.- 5.5 Remarks.- 6 The Weighted Spectral Test.- 6.1 Definition.- 6.2 Examples and Properties.- 6.3 Remarks.- 7 Discrepancy.- 7.1 Definition.- 7.2 The Inequality of Erdös-Turán-Koksma.- 7.3 Remarks.- 8 Summary.- 9 Acknowledgements.- 10 References.- Lattice Rules: How Well Do They Measure Up?.- 1 Introduction.- 2 Some Basic Properties of Lattice Rules.- 3 A General Approach to Worst-Case and Average-Case Error Analysis.- 3.1 Worst-Case Quadrature Error for Reproducing Kernel Hilbert Spaces.- 3.2 A More General Worst-Case Quadrature Error Analysis.- 3.3 Average-Case Quadrature Error Analysis.- 4 Examples of Other Discrepancies.- 4.1 The ANOVA Decomposition.- 4.2 A Generalization ofP?(L) with Weights.- 4.3 The Periodic Bernoulli Discrepancy — Another Generalization ofP?(L).- 4.4 The Non-Periodic Bernoulli Discrepancy.- 4.5 The Star Discrepancy.- 4.6 The Unanchored Discrepancy.- 4.7 The Wrap-Around Discrepancy.- 4.8 The Symmetric Discrepancy.- 5 Shift-Invariant Kernels and Discrepancies.- 6 Discrepancy Bounds.- 6.1 Upper Bounds forP?(L).- 6.2 A Lower Bound onDF,?,1(P).- 6.3 Quadrature Rules with Different Weights.- 6.4 Copy Rules.- 7 Discrepancies of Integration Lattices and Nets.- 7.1 The Expected Discrepancy of Randomized (0ms)-Nets.- 7 2 Infinite Sequences of Embedded Lattices.- 8 Tractability of High Dimensional Quadrature.- 8.1 Quadrature in Arbitrarily High Dimensions.- 8.2 The Effective Dimension of an Integrand.- 9 Discussion and Conclusion.- 10 References.- Digital Point Sets: Analysis and Application.- 1 Introduction.- 2 The Concept and Basic Properties of Digital Point Sets.- 3 Discrepancy Bounds for Digital Point Sets.- 4 Special Classes of Digital Point Sets and Quality Bounds.- 5 Digital Sequences Based on Formal Laurent Series and Non-Archimedean Diophantine Approximation.- 6 Analysis of Pseudo-Random-Number Generators by Digital Nets.- 7 The Digital Lattice Rule.- 8 Outlook and Open Research Topics.- 9 References.- Random Number Generators: Selection Criteria and Testing.- 1 Introduction.- 2 Design Principles and Figures of Merit.- 2.1 A Roulette Wheel.- 2.2 Sampling from ?t.- 2.3 The Lattice Structure of MRG’s.- 2.4 Equidistribution for Regular Partitions in Cubic Boxes.- 2.5 Other Measures of Divergence.- 3 Empirical Statistical Tests.- 3.1 What are the Good Tests?.- 3.2 Two-Level Tests.- 3.3 Collections of Empirical Tests.- 4 Examples of Empirical Tests.- 4.1 Serial Tests of Equidistribution.- 4.2 Tests Based on Close Points in Space.- 5 Collections of Small RNGs.- 5.1 Small Linear Congruential Generators.- 5.2 Explicit Inversive Congruential Generators.- 5.3 Compound Cubic Congruential Generators.- 6 Systematic Testing for Small RNGs.- 6.1 Serial Tests of Equidistribution for LCGs.- 6.2 Serial Tests of Equidistribution for Nonlinear Generators.- 6.3 A Summary of the Serial Tests Results.- 6.4 Close-Pairs Tests for LCGs.- 6.5 Close-Pairs Tests for Nonlinear Generators.- 6.6 A Summary of the Close-Pairs Tests Results.- 7 How Do Real-Life Generators Fare in These Tests?.- 8 Acknowledgements.- 9 References.- Nets, (ts)-Sequences, and Algebraic Geometry.- 1 Introduction.- 2 Basic Concepts.- 3 The Digital Method.- 4 Background on Algebraic Curves over Finite Fields.- 5 Construction of (ts)-Sequences.- 6 New Constructions of (tms)-Nets.- 7 New Algebraic Curves with Many Rational Points.- 8 References.- Financial Applications of Monte Carlo and Quasi-Monte Carlo Methods.- 1 Introduction.- 2 Monte Carlo Methods for Finance Applications.- 2.1 Preliminaries for Derivative Pricing.- 2.2 Variance Reduction Techniques.- 2.3 Caveats for Computer Implementation.- 3 Speeding Up by Quasi-Monte Carlo Methods.- 3.1 What are Quasi-Monte Carlo Methods?.- 3.2 Generalized Faure Sequences.- 3.3 Numerical Experiments.- 3.4 Discussions.- 4 Future Topics.- 4.1 Monte Carlo Simulations for American Options.- 4.2 Research Issues Related to Quasi-Monte Carlo Methods.- 5 References.