Supercanonical Convergence Rates in Quasi-Monte Carlo Simulation of Markov Chains


Pierre L'Ecuyer
University of Montreal

Wednesday, January 18, 2017
4:15 - 5:15 PM
Location: Spilker 232


Abstract:

Consider a discrete-event model (or a Markov chain) that evolves over several time steps, with a state-dependent cost at each step. The goal is to estimate the expected cost (or perhaps the entire distribution of the cost), either at a given step number, or on average over all steps. For a majority of real-life applications, these quantities are too difficult to compute exactly and must be estimated by simulation. The standard Monte Carlo approach is to simulate n independent sample paths of the chain and take the average over those paths. For the mean cost, this gives an unbiased estimator whose error converges as O(n -1/2), which means that one must multiply n by 100 to get one additional decimal digit of accuracy. When estimating the density of the cost instead of just its mean, the convergence rate is even slower. In this talk, we discuss an approach named Array-RQMC which can provide faster convergence rates. The main idea is to simulate the n copies of the chain together and move them forward by using a randomized quasi-Monte Carlo (RQMC) point set of cardinality n at each step, after sorting the n copies in a particular (multidimensional) order. We review Array-RQMC, its variants, sorting strategies, and convergence results. 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.

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html