Computational investigations of low-discrepancy sequences

TLDR

The study aims to evaluate low‑discrepancy sequences for high‑dimensional quasi‑Monte‑Carlo integration, identify challenges in error estimation and test‑function selection, and propose an empirical error formula. The authors compute maximum‑error estimates for nine test functions up to 400 dimensions to evaluate existing and newly proposed low‑discrepancy generators, and suggest an empirical error formula. The modified Halton sequence and new generalized Halton construction significantly outperform the original Halton sequence, as demonstrated by maximum‑error estimates on nine test functions up to 400 dimensions.

Abstract

The Halton, Sobol, and Faure sequences and the Braaten-Weller construction of the generalized Halton sequence are studied in order to assess their applicability for the quasi Monte Carlo integration with large number of variates. A modification of the Halton sequence (the Halton sequence leaped) and a new construction of the generalized Halton sequence are suggested for unrestricted number of dimensions and are shown to improve considerably on the original Halton sequence. Problems associated with estimation of the error in quasi Monte Carlo integration and with the selection of test functions are identified. Then an estimate of the maximum error of the quasi Monte Carlo integration of nine test functions is computed for up to 400 dimensions and is used to evaluate the known generators mentioned above and the two new generators. An empirical formula for the error of the quasi Monte Carlo integration is suggested.