Groupe d’études et de recherche en analyse des décisions

# Sorting methods and convergence rates for Array-RQMC: Some empirical comparisons

## Pierre L'Ecuyer, David Munger, Christian Lécot et Bruno Tuffin

We review the Array-RQMC method, 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.

, 15 pages