{"id":{"repo_id":"fsu-retro","oai_identifier":"oai:diginole.lib.fsu.edu:fsu_927821"},"canonical_url":"https://search.dev.ndltd.org/etd/fsu-retro/oai:diginole.lib.fsu.edu:fsu_927821","repository":{"repo_id":"fsu-retro","name":"Florida State University","base_url":"https://repository.lib.fsu.edu/oai2"},"display":{"title":"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.","abstract_html":"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.","abstract_has_math":false,"creators":[],"institution":"Florida State University","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["Alsolami, Maryam (author)","Mascagni, Michael (professor directing dissertation)","Ökten, Giray (university representative)","Liu, Xiuwen, 1966- (committee member)","Kumar, Piyush (committee member)","Florida State University (degree granting institution)","College of Arts and Sciences (degree granting college)","Department of Computer Science (degree granting department)"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2023,"date_issued":"2023","date_published":"2023","updated_at":"2026-07-27T19:43:21Z","subjects":["Computer science","Mathematics"],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["fsu:927821","iid: Alsolami_fsu_0071E_17673"],"render_values":[{"text":"fsu:927821","href":null,"code":true},{"text":"iid: Alsolami_fsu_0071E_17673","href":null,"code":true}]}]},"links":{"outbound_url":null,"outbound_label":null,"outbound_source":null},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Alsolami, Maryam (author)","Mascagni, Michael (professor directing dissertation)","Ökten, Giray (university representative)","Liu, Xiuwen, 1966- (committee member)","Kumar, Piyush (committee member)","Florida State University (degree granting institution)","College of Arts and Sciences (degree granting college)","Department of Computer Science (degree granting department)"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2023"]},{"key":"dc:publisher","label":"Institution","values":["Florida State University"]},{"key":"dc:type","label":"Dc Type","values":["Text","doctoral thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer science","Mathematics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["fsu:927821","iid: Alsolami_fsu_0071E_17673"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","A Dissertation submitted to the Department of Computer Science in partial fulfillment of the requirements for the degree of Doctor of Philosophy.","April 25, 2023.","Metropolis algorithm, Metropolis random walk algorithm, Monte Carlo method, Quasi-Monte Carlo method, Random walk algorithm, Star discrepancy","Includes bibliographical references.","Michael Mascagni, Professor Directing Dissertation; Giray Ökten, University Representative; Xiuwen Liu, Committee Member; Piyush Kumar, Committee Member."]},{"key":"dc:format","label":"Dc Format","values":["computer","online resource","1 online resource (96 pages)","application/pdf"]},{"key":"dc:title","label":"Title","values":["Various Approximate Methods to Measure the Uniformity of Quasirandom Sequences"]}]}],"canonical_facts":{"dc:contributor":["Alsolami, Maryam (author)","Mascagni, Michael (professor directing dissertation)","Ökten, Giray (university representative)","Liu, Xiuwen, 1966- (committee member)","Kumar, Piyush (committee member)","Florida State University (degree granting institution)","College of Arts and Sciences (degree granting college)","Department of Computer Science (degree granting department)"],"dc:date":["2023"],"dc:description":["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.","A Dissertation submitted to the Department of Computer Science in partial fulfillment of the requirements for the degree of Doctor of Philosophy.","April 25, 2023.","Metropolis algorithm, Metropolis random walk algorithm, Monte Carlo method, Quasi-Monte Carlo method, Random walk algorithm, Star discrepancy","Includes bibliographical references.","Michael Mascagni, Professor Directing Dissertation; Giray Ökten, University Representative; Xiuwen Liu, Committee Member; Piyush Kumar, Committee Member."],"dc:format":["computer","online resource","1 online resource (96 pages)","application/pdf"],"dc:identifier":["fsu:927821","iid: Alsolami_fsu_0071E_17673"],"dc:language":["English"],"dc:publisher":["Florida State University"],"dc:subject":["Computer science","Mathematics"],"dc:title":["Various Approximate Methods to Measure the Uniformity of Quasirandom Sequences"],"dc:type":["Text","doctoral thesis"]},"updated_at":"2026-07-27T19:43:21Z"}