A Metropolis 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, Kingdom of 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, 2023, vol. 29, issue 2, 161-171

Abstract: In this paper, we introduce a new algorithm for estimating the lower bounds for the star discrepancy of any arbitrary point sets in [ 0 , 1 ] s [0,1]^{s} . Computing the exact star discrepancy is known to be an NP-hard problem, so we have been looking for effective approximation algorithms. The star discrepancy can be thought of as the maximum of a function called the local discrepancy, and we will develop approximation algorithms to maximize this function. Our algorithm is analogous to the random walk algorithm described in one of our previous papers [M. Alsolami and M. Mascagni, A random walk algorithm to estimate a lower bound of the star discrepancy, Monte Carlo Methods Appl. 28 (2022), 4, 341–348.]. We add a statistical technique to the random walk algorithm by implementing the Metropolis algorithm in random walks on each chosen dimension to accept or reject this movement. We call this Metropolis random walk algorithm. In comparison to all previously known techniques, our new algorithm is superior, especially in high dimensions. Also, it can quickly determine the precise value of the star discrepancy in most of our data sets of various sizes and dimensions, or at least the lower bounds of the star discrepancy.

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

Downloads: (external link)
https://doi.org/10.1515/mcma-2023-2005 (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:29:y:2023:i:2:p:161-171:n:3

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

DOI: 10.1515/mcma-2023-2005

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 ().