A review of Array-RQMC: Sorting methods and convergence rates


Pierre L'Ecuyer


Universite de Montreal


Fri, 12/02/2016 - 11:05am to 11:55am


RC-2063, The Red Centre, UNSW


Array-RQMC is a method that simulates an array of n dependent realizations of a Markov chain in a way that each chain is generated from its exact probability law, and with the aim that the empirical distribution of the states at a given step of the chain provides a “low-discrepancy” approximation of the theoretical distribution of the state at that step.  At each step, the n copies of the chain are sorted in a particular (multidimensional) order and then moved forward by one step using a randomized quasi-Monte Carlo (RQMC) point set of cardinality n.  When the state has more than one dimension, the performance may depend strongly on the choice of sort strategy.

In this talk, we review Array-RQMC, its variants, sorting strategies, and convergence results.  We are interested in the convergence rate of measures of discrepancy of the states at a given step of the chain, as a function of the sample size n, and also the convergence rate of the variance of the sample average of a (cost) function of the state at a given step, viewed as an estimator of the expected cost. We summarize known convergence rate results and show empirical results that suggest much better convergence rates than those that are proved.  We also compare different types of multivariate sorts to match the chains with the RQMC points, including a sort based on a Hilbert curve.

School Seminar Series: