We present a randomized quasi-Monte Carlo method for efficient simulation of Markov chains with totally ordered state spaces. A state-dependent cost is paid at each step and the goal is to estimate the expected total cost up to a stopping time. The method simulates $n$ copies of the chain in parallel, using a highly-uniform point set of cardinality $n$ randomized independently at each step. We have bounds on the convergence rate of the worst-case error and on the variance for special situations. We show, via numerical examples, that the proposed approach can dramatically reduce the variance of the sample average cost over the $n$ copies of the chain compared with standard Monte Carlo (where the $n$ copies are independent).

We consider the pricing of a down-and-out barrier option, as well as its sensitivity analysis, via Monte Carlo simulation. To reduce the variance, we experiment with two flavors of randomized quasi-Monte Carlo (RQMC): a classical approach, where each QMC point corresponds to one simulation run, and a so-called array-RQMC approach, where an independently randomized RQMC point set is used at each time step to advance all copies of the process in parallel to their next observation time. We combine this with a control variate and a change of measure proposed earlier by Glasserman and Staum. This change of measure provides a large efficiency improvement when estimating the sensitivity by finite differences with common random numbers. We find that combining these methods with RQMC boosts their efficiency sometimes by several orders of magnitude, and that array-RQMC gives the best improvement in some cases while classical RQMC wins in other cases.

Randomized Quasi-Monte Carlo (RQMC) methods can be viewed as variance-reduction techniques that can improve the efficiency of Monte Carlo methods in estimating multivariate integrals. RQMC requires a properly randomized highly-uniform point set, whose uniformity can be measured by a variety of criteria known as \emph{discrepancy} measures. Among them, the $L_2$-discrepancy is one of the best known and most convenient measure, in large part because it is not too hard to compute. In this talk, we compare several randomized points sets encountered in practice through their $L_2$-discrepancy, as well as the efficiency improvement we obtain by using them in RQMC simulation for pricing various financial options. Our results indicate that in most cases, the $L_2$-discrepancy is not a good predictor of the efficiency improvement achieved, even if the dimension is low and the number of points is large. We also show, via numerical examples, that surprisingly large efficiency improvements can be achieved with RQMC, even in high dimensions, and that RQMC can be fruitfully combined with other variance reduction techniques.