Halton sequences were first introduced in the 1960s as an alternative to pseudo-random number sequences, with the aim of providing better coverage of the area of integration and negative correlation in the simulated probabilities between observations. This is needed in order to achieve variance reduction when using simulation to approximate an integral that does not have a closed-form expression. Such integrals arise in many areas of regional science, for example in the evaluation and estimation of certain types of discrete choice models. While the performance of standard Halton sequences is very good in low dimensions, problems with correlation have been observed between sequences generated from higher primes. This can cause serious problems in the estimation of models with high-dimensional integrals (e.g., models of aspects of spatial choice, such as route or location). Various methods have been proposed to deal with this; one of the most prominent solutions is the scrambled Halton sequence, which uses special predetermined permutations of the coefficients used in the construction of the standard sequence. In this paper, we conduct a detailed analysis of the ability of scrambled Halton sequences to remove the problematic correlation that exists between standard Halton sequences for high primes in the two-dimensional space. The analysis shows that although the scrambled sequences exhibit a lower degree of overall correlation than the standard sequences, for some choices of primes, correlation remains at an unacceptably high level. This paper then proposes an alternative method, based on the idea of using randomly shuffled versions of the one-dimensional standard Halton sequences in the construction of multi-dimensional sequences. We show that the new shuffled sequences produce a significantly higher reduction in correlation than the scrambled sequences, without loss of quality of coverage. Another substantial advantage of this new method is that it can, without any modifications, be used for any number of dimensions, while the use of the scrambled sequences requires the a-priori computation of a matrix of permutations, which for high dimensional problems could lead to significant runtime disadvantages. Repeated runs of the shuffling algorithm will also produce different sequences in different runs, which nevertheless maintain the same quality of one-dimensional coverage. This is not at all the case for the scrambled sequences. In view of the clear advantages in its ability to remove correlation, combined with its runtime and generalization advantages, this paper recommends that this new algorithm should be preferred to the scrambled Halton sequences when dealing with high correlation between standard Halton sequences.
展开▼
