ACMD Seminar: Various Approximate Methods To Measure The Uniformity Of Quasirandom Sequences

Maryam Alsolami
Department of Computer Science, Florida State University

Tuesday, April 4, 2023, 1:00-2:00 PM MT (3:00-4:00 PM ET)

A video of this talk will be made available to NIST staff in the Math channel on NISTube, which is accessible from the NIST internal home page. It will be taken down from NISTube after 12 months at which point it can be requested by emailing the ACMD Seminar Chair.

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 than pseudorandom numbers. The most common measure of that uniformity is the star discrepancy. In addition, the main error bound in quasi-Monte Carlo methods, called the Koksma–Hlawka inequality, has a star discrepancy in its formulation. A difficulty with this bound is that computing the star discrepancy is known to be an NP-hard problem, so we have been looking for effective approximate algorithms. The star discrepancy can be thought of as the maximum of a function called the local discrepancy, and we will develop approximate algorithms to maximize this function. In this talk, we introduce a new algorithm for estimating the lower bounds for the star discrepancy. Our algorithm is analogous to the random walk algorithm described in one of our previous papers. 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.

Bio: Maryam Alsolami is a PhD student in the Computer Science department at Florida State University. Her doctoral research is under the direction of Prof. Michael Mascagni. Her work focuses on stochastic computing by using Monte Carlo and quasi-Monte Carlo methods to solve hard problems in mathematics, finance, physics, and other domains. Her master's degree was received in Computer Science from DePaul University. She obtained her Bachelor of Science in Computer Science from Umm Al-Qura University. She has been a Teaching Assistant at Umm Al-Qura University (UQU) in the College of Computers and Information Systems since 2011.

Host: Michael Mascagni

Note: This talk will be recorded to provide access to NIST staff and associates who could not be present to the time of the seminar. The recording will be made available in the Math channel on NISTube, which is accessible only on the NIST internal network. This recording could be released to the public through a Freedom of Information Act (FOIA) request. Do not discuss or visually present any sensitive (CUI/PII/BII) material. Ensure that no inappropriate material or any minors are contained within the background of any recording. (To facilitate this, we request that cameras of attendees are muted except when asking questions.)

Note: Visitors from outside NIST must contact Lochi Orr; at least 24 hours in advance.