A random walk algorithm to estimate a lower bound of the star discrepancy

Alsolami Maryam () and Mascagni Michael ()
Additional contact information
Alsolami Maryam: Department of Computer Science, Florida State University, Tallahassee, FL 32306-4530, USA; and College of Computers and Information Systems, Umm Al-Qura University, Mecca, Saudi Arabia
Mascagni Michael: Department of Computer Science, Florida State University, Tallahassee, FL 32306-4530; and National Institute of Standards & Technology, ITL, Gaithersburg, MD 20899-8910, USA

Monte Carlo Methods and Applications, 2022, vol. 28, issue 4, 341-348

Abstract: In many Monte Carlo applications, one can substitute the use of pseudorandom numbers with quasirandom numbers and achieve improved convergence. This is because quasirandom numbers are more uniform that pseudorandom numbers. The most common measure of that uniformity is the star discrepancy. Moreover, the main error bound in quasi-Monte Carlo methods, called the Koksma–Hlawka inequality, has the star discrepancy in the formulation. A difficulty with this bound is that computing the star discrepancy is very costly. The star discrepancy can be computed by evaluating a function called the local discrepancy at a number of points. The supremum of these local discrepancy values is the star discrepancy. If we have a point set in [ 0 , 1 ] s {[0,1]^{s}} with N members, we need to compute the local discrepancy at N s {N^{s}} points. In fact, computing star discrepancy is NP-hard. In this paper, we will consider an approximate algorithm for a lower bound on the star discrepancy based on using a random walk through some of the N s {N^{s}} points. This approximation is much less expensive that computing the star discrepancy, but still accurate enough to provide information on convergence. Our numerical results show that the random walk algorithm has the same convergence rate as the Monte Carlo method, which is O ( N - 1 2 {O(N^{-\frac{1}{2}}} ).

Keywords: Monte Carlo method; quasi-Monte Carlo method; approximate star discrepancy; random walk (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1515/mcma-2022-2125 (text/html)
For access to full text, subscription to the journal or payment for the individual article is required.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:bpj:mcmeap:v:28:y:2022:i:4:p:341-348:n:4

Ordering information: This journal article can be ordered from
https://www.degruyter.com/journal/key/mcma/html

DOI: 10.1515/mcma-2022-2125

Access Statistics for this article

Monte Carlo Methods and Applications is currently edited by Karl K. Sabelfeld

More articles in Monte Carlo Methods and Applications from De Gruyter
Bibliographic data for series maintained by Peter Golla ().