Name:    Prof. Michael Mascagni         
Address: Department of Computer Science and
         School of Computational Science
         Florida State University
         Tallahassee, FL  32306-4530  USA
Offices: 498 Dirac Science Library/172 Love Building
Phone:   +1.850.644.3290
FAX:     +1.850.644.0098

Title:    On the Scrambled Halton Sequence


The Halton sequence is one of the standard (along with (t,s)-sequences and lattice points) low-discrepancy sequences, and thus is widely used in quasi-Monte Carlo applications. One of its important advantages is that the Halton sequence is easy to implement due to its definition via the radical inverse function. However, the original Halton sequence suffers from correlations between radical inverse functions with different bases used for different dimensions. These correlations result in poorly distributed two-dimensional projections. A standard solution to this is to use a randomized (scrambled) version of the Halton sequence. Here, we analyze the correlations in the standard Halton sequence, and based on this analysis propose a new and simpler modified scrambling algorithm. We also provide a number theoretic criterion to choose the optimal scrambling from among a large family of random scramblings. Based on this criterion, we have found the optimal scrambling for up to 60 dimensions for the Halton sequence. This derandomized Halton sequence is then numerically tested and shown empirically to be far superior to the original sequence.

This work is joint with Dr. Hongmei, and is part of her Ph.D. dissertation.

Home | Educational Background | Research Experience | Curriculum Vitae | Research Interests | Research Projects | Recent Papers | Courses | Abstracts of Talks