Various Approximate Methods to Measure The Uniformity of Quasirandom Sequences

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 dissertation, we introduce new algorithms for estimating the lower bounds for the star discrepancy. The random walk algorithm is based on the Monte Carlo method for computing the star discrepancy using random walks through some of the points in the unit cube [0, 1]s. The second algorithm is analogous to the random walk algorithm; instead of directly accepting the randomly chosen dimension, we apply the Metropolis algorithm to the chosen dimension to accept or reject this movement. We call it the Metropolis random walk algorithm. The implementation of this algorithm is based on the Markov chain Monte Carlo method. This approximation is much less expensive than computing the exact value of the star discrepancy. The random walk algorithm and Metropolis random walk algorithm can find the exact value of the star discrepancy or estimate the lower bound of the star discrepancy in a reasonable time. The findings of our experiment indicate that the estimation of the star discrepancy is obtained without a substantial computational cost. Also, in comparison to all previously known techniques, the Metropolis random walk algorithm is superior, especially in high dimensions.