You are here

Scrambled Quasirandom Sequences and Their Applications

Title: Scrambled Quasirandom Sequences and Their Applications.
32 views
4 downloads
Name(s): Chi, Hongmei, author
Mascagni, Michael, professor directing dissertation
Huckaba, Sam, outside committee member
Burmester, Mike, committee member
Van Engelen, Robert, committee member
Srinivasan, Ashok, committee member
Department of Computer Science, degree granting department
Florida State University, degree granting institution
Type of Resource: text
Genre: Text
Issuance: monographic
Date Issued: 2004
Publisher: Florida State University
Place of Publication: Tallahassee, Florida
Physical Form: computer
online resource
Extent: 1 online resource
Language(s): English
Abstract/Description: Quasi-Monte Carlo methods are a variant of ordinary Monte Carlo methods that employ highly uniform quasirandom numbers in place of Monte Carlo's pseudorandom numbers. Monte Carlo methods offer statistical error estimates; however, while quasi-Monte Carlo has a faster convergence rate than normal Monte Carlo, one cannot obtain error estimates from quasi-Monte Carlo sample values by any practical way. A recently proposed method, called randomized quasi-Monte Carlo methods, takes advantage of Monte Carlo and quasi-Monte Carlo methods. Randomness can be brought to bear on quasirandom sequences through scrambling and other related randomization techniques in randomized quasi-Monte Carlo methods, which provide an elegant approach to obtain error estimates for quasi-Monte Carlo based on treating each scrambled sequence as a different and independent random sample. The core of randomized quasi-Monte Carlo is to find an effective and fast algorithm to scramble (randomize) quasirandom sequences. This dissertation surveys research on algorithms and implementations of scrambled quasirandom sequences and proposes some new algorithms to improve the quality of scrambled quasirandom sequences. Besides obtaining error estimates for quasi-Monte Carlo, scrambling techniques provide a natural way to parallelize quasirandom sequences. This scheme is especially suitable for distributed or grid computing. By scrambling a quasirandom sequence we can produce a family of related quasirandom sequences. Finding one or a subset of optimal quasirandom sequences within this family is an interesting problem, as such optimal quasirandom sequences can be quite useful for quasi-Monte Carlo. The process of finding such optimal quasirandom sequences is called the derandomization of a randomized (scrambled) family. We summarize aspects of this technique and propose some new algorithms for finding optimal sequences from the Halton, Faure and Sobol sequences. Finally we explore applications of derandomization.
Identifier: FSU_migr_etd-3823 (IID)
Submitted Note: A Dissertation submitted to the Department of Computer Science in partial fulfillment of the requirements for the degree of Doctor of Philosophy.
Degree Awarded: Summer Semester, 2004.
Date of Defense: June 4, 2004.
Keywords: Parallel Computing, Derandomization, Randomized Quasi-Monte Carlo Methods, Optimal Sequences, Automatic Error Estimation
Bibliography Note: Includes bibliographical references.
Advisory Committee: Michael Mascagni, Professor Directing Dissertation; Sam Huckaba, Outside Committee Member; Mike Burmester, Committee Member; Robert van Engelen, Committee Member; Ashok Srinivasan, Committee Member.
Subject(s): Computer science
Persistent Link to This Record: http://purl.flvc.org/fsu/fd/FSU_migr_etd-3823
Owner Institution: FSU

Choose the citation style.
Chi, H. (2004). Scrambled Quasirandom Sequences and Their Applications. Retrieved from http://purl.flvc.org/fsu/fd/FSU_migr_etd-3823