Secure pseudorandom bit generators and point sets with low star-discrepancy

[摘要] The star-discrepancy is a quantitative measure for the irregularity of distribution of a point set in the unit cube that is intimately linked to the integration error of quasi-Monte Carlo algorithms. These popular integration rules are nowadays also applied to very high-dimensional integration problems. Hence multi-dimensional point sets of reasonable size with low discrepancy are badly needed. A seminal result from Heinrich, Novak, Wasilkowski and Wozniakowski shows the existence of a positive number C such that for every dimension d there exists an N-element point set in [0,1)(d) with star-discrepancy of at most C root d/N. This is a pure existence result and explicit constructions of such point sets would be very desirable. The proofs are based on random samples of N-element point sets which are difficult to realize for practical applications. In this paper we propose to use secure pseudorandom bit generators for the generation of point sets with star-discrepancy of order O(root d/N). This proposal is supported theoretically and by means of numerical experiments. (C) 2021 Elsevier B.V. All rights reserved.

[发布日期] 2021-11-01

[关键词] Star-discrepancy;Inverse of star-discrepancy;Polynomial tractability;Pseudorandom numbers