From van der Corput to modern constructions of sequences for quasi-Monte Carlo rules

DOI10.1016/J.INDAG.2015.09.001zbMATH Open1335.11063arXiv1506.03764OpenAlexW2962968884MaRDI QIDQ898073FDOQ898073

Friedrich Pillichshammer, Peter Kritzer, Henri Faure

Publication date: 8 December 2015

Published in: Indagationes Mathematicae. New Series (Search for Journal in Brave)

Abstract: In 1935 J.G. van der Corput introduced a sequence which has excellent uniform distribution properties modulo 1. This sequence is based on a very simple digital construction scheme with respect to the binary digit expansion. Nowadays the van der Corput sequence, as it was named later, is the prototype of many uniformly distributed sequences, also in the multi-dimensional case. Such sequences are required as sample nodes in quasi-Monte Carlo algorithms, which are deterministic variants of Monte Carlo rules for numerical integration. Since its introduction many people have studied the van der Corput sequence and generalizations thereof. This led to a huge number of results. On the occasion of the 125th birthday of J.G. van der Corput we survey many interesting results on van der Corput sequences and their generalizations. In this way we move from van der Corput's ideas to the most modern constructions of sequences for quasi-Monte Carlo rules, such as, e.g., generalized Halton sequences or Niederreiter's $(t,s)$-sequences.

Full work available at URL: https://arxiv.org/abs/1506.03764

Recommendations

• scientific article
• Van der Corput sequences towards general \((0,1)\)-sequences in base \(b\)
• Precise distribution properties of the van der Corput sequence and related sequences
• Pseudo-randomness of van der Corput’s sequences
• scientific article; zbMATH DE number 2211253

zbMATH Keywords

uniform distributiondiscrepancyvan der Corput sequence\((t,s)\)-sequencegeneralized Halton sequenceNiederreiter sequence

Mathematics Subject Classification ID

Irregularities of distribution, discrepancy (11K38) Pseudo-random numbers; Monte Carlo methods (11K45) Research exposition (monographs, survey articles) pertaining to number theory (11-02)

Cites Work

• Etude des restes pour les suites de van der Corput generalisees
• Self-similar measures and sequences
• On the discrepancy of the sequence formed by the multiples of an irrational number
• On a sequence of points of interest for numerical quadrature
• On functions with bounded remainder
• On regularities of the distribution of special sequences
• Title not available (Why is that?)
• Irregularities of Distribution. VIII
• Title not available (Why is that?)
• On a Problem of Erdőos in Diophantine Approximation
• Fast generation of low-discrepancy sequences
• On some remarkable properties of the two-dimensional Hammersley point set in base 2
• Improvements on Low Discrepancy One-Dimensional Sequences and Two-Dimensional Point Sets
• Discrepancy and diaphony of digital (0,1)-sequences in prime base
• Precise distribution properties of the van der Corput sequence and related sequences
• Periodic functions with bounded remainder
• Note on irregularities of distribution
• Lemme de Bohl pour les suites de Van der Corput généralisées. (Bohl lemma for the generalized Van der Corput sequences)
• On the discrepancy of \((0,1)\)-sequences.
• Optimal \(L_{p}\)-discrepancy bounds for second order digital sequences
• On the diaphony of one class of one-dimensional sequences
• A metrical lower bound on the star discrepancy of digital sequences
• A variant of Atanassov's method for \((t, s)\)-sequences and \((t, \mathbf{e}, s)\)-sequences
• Van der Corput sequences towards general \((0,1)\)-sequences in base \(b\)
• \(L_2\) discrepancy of linearly digit scrambled Zaremba point sets
• The Supremum Norm of the Discrepancy Function: Recent Results and Connections
• A good permutation for one-dimensional diaphony
• Title not available (Why is that?)
• Optimal order of $L_p$-discrepancy of digit shifted Hammersley point sets in dimension 2
• On Atanassov’s methods for discrepancy bounds of low-discrepancy sequences
• Pseudo-randomness of van der Corput’s sequences
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Sums of distances to the nearest integer and the discrepancy of digital nets
• Title not available (Why is that?)
• Generalized Halton sequences in 2008
• A generalization of NUT digital (0,1)-sequences and best possible lower bounds for star discrepancy
• Title not available (Why is that?)
• An introduction to copulas. Properties and applications
• Randomized Halton sequences
• Title not available (Why is that?)
• On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals
• Monte Carlo and quasi-Monte Carlo sampling
• Introduction to Quasi-Monte Carlo Integration and Applications
• Title not available (Why is that?)
• On Periodic Expansions of Pisot Numbers and Salem Numbers
• Title not available (Why is that?)
• Title not available (Why is that?)
• Sequences, discrepancies and applications
• A sequence has almost nowhere small discrepancy
• Good permutations for extreme discrepancy
• \(L_p\)-discrepancy of the symmetrized van der Corput sequence
• On the star discrepancy of sequences in the unit interval
• On the discrepancy of sequences in the unit-interval
• Rational points on curves over finite fields. Theory and Applications
• Optimal \(\mathcal {L}_{2}\) discrepancy bounds for higher order digital sequences over the finite field \(\mathbb {F}_{2}\)
• Title not available (Why is that?)
• Recent Progress in Improvement of Extreme Discrepancy and Star Discrepancy of One-Dimensional Sequences
• Explicit constructions of point sets and sequences with low discrepancy
• Discrépance quadratique de la suite de van der Corput et de sa symétrique
• Explicit Constructions of Quasi-Monte Carlo Rules for the Numerical Integration of High-Dimensional Periodic Functions
• Walsh Spaces Containing Smooth Functions and Quasi–Monte Carlo Rules of Arbitrary High Order
• Minoration de la discrépance d'une suite quelconque sur T
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• LOWER BOUNDS FOR DISCREPANCY
• Irregularities of distribution, VII
• On irregularities of distribution
• Geometric discrepancy. An illustrated guide
• Low-discrepancy and low-dispersion sequences
• Symmetrization of the van der Corput generalized sequences
• The extreme and \(L^2\) discrepancies of some plane sets
• An improved lower bound for the \(L_2\)-discrepancy
• Discrepancy of Hammersley points in Besov spaces of dominating mixed smoothness
• Discrépance de suites associées à un système de numération (en dimension s)
• Discrépances de suites associées à un système de numération (en dimension un)
• Discrépance et diaphonie en dimension un
• L₂discrepancy of generalized two-dimensional Hammersley point sets scrambled with arbitrary permutations
• Note on irregularities of distribution
• Walsh series analysis of the \(L_2\)-discrepancy of symmetrized point sets
• \(L_p\) discrepancy of generalized two-dimensional Hammersley point sets
• On the discrepancy of generalized Niederreiter sequences
• Title not available (Why is that?)
• The dynamical point of view of low-discrepancy sequences
• High-dimensional integration: The quasi-Monte Carlo way
• Distribution properties of \(G\)-additive functions
• Generalized von Neumann-Kakutani transformation and random-start scrambled Halton sequences
• Almost sure invariance principles for partial sums of weakly dependent random variables
• Title not available (Why is that?)
• Title not available (Why is that?)
• Point sets and sequences with small discrepancy
• Distribution functions for subsequences of the van der Corput sequence
• Title not available (Why is that?)
• Discrepancy and integration in function spaces with dominating mixed smoothness
• Discrepancy of generalized Hammersley type point sets in Besov spaces of dominating mixed smoothness
• On the \(L_2\)-discrepancy for anchored boxes
• On the small ball inequality in all dimensions
• A method for exact calculation of the stardiscrepancy of plane sets applied to the sequences of Hammersley
• On the star-discrepancy of generalized Hammersley sequences in two dimensions
• On the diaphony of the van der Corput-Halton sequence
• Improved upper bounds on the star discrepancy of \((t,m,s)\)-nets and \((t,s)\)-sequences
• Improvements on the star discrepancy of \((t,s)\)-sequences
• New star discrepancy bounds for \((t,m,s)\)-nets and \((t,s)\)-sequences
• Title not available (Why is that?)
• Improved upper bounds for the star discrepancy of digital nets in dimension 3
• Title not available (Why is that?)
• Minoration de discrépance en dimension deux
• Polynomial arithmetic analogue of Halton sequences
• Title not available (Why is that?)
• On two-dimensional sequences composed by one-dimensional uniformly distributed sequences
• Constructions of uniformly distributed sequences using the \(b\)-adic method
• DISTRIBUTION PROPERTIES OF GENERALIZED VAN DER CORPUT–HALTON SEQUENCES AND THEIR SUBSEQUENCES
• Fibonacci, van der Corput and Riesz-Nágy
• Generalized (t, s)-Sequences, Kronecker-Type Sequences, and Diophantine Approximations of Formal Laurent Series
• Title not available (Why is that?)
• Rate of convergence in the central limit theorem for random variables with strong mixing
• Mean-square discrepancies of the Hammersley and Zaremba sequences for arbitrary radix
• L 2 Discrepancy of Two-Dimensional Digitally Shifted Hammersley Point Sets in Base b
• \(L_2\) discrepancy of generalized Zaremba point sets
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the discrepancy of the van der Corput sequence indexed by Fibonacci numbers
• Title not available (Why is that?)
• Discrepancy estimates for index-transformed uniformly distributed sequences
• Title not available (Why is that?)
• LACUNARY SERIES AND INDEPENDENT FUNCTIONS
• Regularities of the distribution of \(\beta\)-adic van der Corput sequences
• New Perspectives on (0,s)-Sequences
• Regularities in the distribution of special sequences
• The dynamics associated with certain digital sequences
• Title not available (Why is that?)
• Quasi-Monte Carlo, low discrepancy sequences, and ergodic transformations
• Van der Corput sequences, Kakutani transforms and one-dimensional numerical integration
• Title not available (Why is that?)
• Cyclic shifts of the van der Corput set
• A thorough analysis of the discrepancy of shifted Hammersley and van der Corput point sets
• Title not available (Why is that?)

Cited In (18)

• Imposition of boundary conditions for elliptic equations in the context of non boundary fitted meshless methods
• On the discrepancy of sequences in the unit-interval
• On Weyl products and uniform distribution modulo one
• Discrepancy Bounds for β $$\boldsymbol{\beta }$$ -adic Halton Sequences
• Low-discrepancy sequences: Atanassov's methods revisited
• On the lower bound of the discrepancy of Halton's sequence. II
• Vandermonde matrices with nodes in the unit disk and the large sieve
• Greedy energy minimization can count in binary: point charges and the van der Corput sequence
• Extreme and periodic $L_2$ discrepancy of plane point sets
• Pair correlations of Halton and Niederreiter sequences are not Poissonian
• Van der Corput sequences, Kakutani transforms and one-dimensional numerical integration
• Guidelines for RBF-FD discretization: numerical experiments on the interplay of a multitude of parameter choices
• Optimal \(L_{p}\)-discrepancy bounds for second order digital sequences
• Optimal periodic \(L_2\)-discrepancy and diaphony bounds for higher order digital sequences
• Lower Bounds on the $$L_p$$ Discrepancy of Digital NUT Sequences
• On the distribution of the van der Corput sequences
• Halton-type sequences in rational bases in the ring of rational integers and in the ring of polynomials over a finite field
• Discrepancy of Digital Sequences: New Results on a Classical QMC Topic

Uses Software

• MinT

This page was built for publication: From van der Corput to modern constructions of sequences for quasi-Monte Carlo rules

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q898073)