Quasi-Monte Carlo Method - Randomization of Quasi-Monte Carlo

Randomization of Quasi-Monte Carlo

Since the low discrepancy sequence are not random, but deterministic, quasi-Monte Carlo method can be seen as a deterministic algorithm or derandomized algorithm. In this case, we only have the bound (e.g., ε ≤ V(f) D_N) for error, and the error is hard to estimate. In order to recover our ability to analyze and estimate the variance, we can randomize the method (see randomization for the general idea). The resulting method is called the randomized quasi-Monte Carlo method and can be also viewed as a variance reduction technique for the standard Monte Carlo method. Among several methods, the simplest transformation procedure is through random shifting. Let {x₁,...,x_N} be the point set from the low discrepancy sequence. We sample s-dimensional random vector U and mix it with {x₁,...,x_N}. In detail, for each x_j, create

and use the sequence instead of . If we have R replications for Monte Carlo, sample s-dimensional random vector U for each replication. The drawback of randomization is the sacrifice of computation speed. Since we now use a pseudorandom number generator, the method is slower. Still, randomization is useful since the variance and the computation speed are slightly better than that of standard Monte Carlo, from the experimental results in Tuffin (2008)