Sequential quasi-Monte Carlo

We develop a new class of algorithms, SQMC (Sequential Quasi-Monte Carlo), as a variant of SMC (Sequential Monte Carlo) based on low-discrepancy point sets. The complexity of SQMC is O(N logN), where N is the number of simulations at each iteration, and its error rate is smaller than the Monte Carlo rate O(N−1/2). The only requirement to implement SQMC is the abil-ity to write the simulation of particle xnt given xnt−1 as a deterministic function of xnt−1 and a fixed number of uniform variates. We show that SQMC is amen-able to the same extensions as standard SMC, such as forward smoothing, backward smoothing, unbiased likelihood evaluation, and so on. In partic-ular, SQMC may replace SMC within a PMCMC (particle Markov chain Monte Carlo) algorithm. We establish several convergence results. These convergence results also apply, as a corollary, to the array-RQMC algorithm of L’Ecuyer et al. (2006). We provide numerical evidence that SQMC may significantly outperform SMC in terms of approximation error in practical scenarios