Implementation of a Hybrid Randomized quasi-Monte Carlo Sequence using Stratified Sampling

Farrell J. Aultman
fja0568@gmail.com

Abstract

A method for generating Hybrid Randomized quasi-Monte Carlo sequences using Stratified Sampling is introduced. An implementation of the method in the Python programming language is applied to three types of problems: one-dimensional integration, multi-dimensional integration, and the pricing of European call options. Sequences generated using this implementation have been named BFS sequences in this paper. Results from problems using BFS sequences are compared with pseudorandom sequences and random-shift Halton sequences. Favorable numerical results using BFS sequences are obtained, especially for the one-dimensional case.

Introduction

Monte Carlo (MC) and Quasi-Monte Carlo (QMC) methods make use of pseudorandom and low discrepancy sequences, respectively. In some use cases, such as integration, Monte Carlo methods may not perform well because the pseudorandom data that is utilized isn’t sufficiently uniform and exhibits clustering and holes. In such cases, QMC methods perform better because low discrepancy sequences are more uniform. When more than one QMC simulation is performed, a new independent low discrepancy sequence can be generated by permuting the original sequence. This step is necessary because QMC sequences are not random. This technique is called Randomized quasi-Monte Carlo (RQMC). Hybrid sequences are created by combining methods from MC and QMC sequence generation.

In this paper, we will discuss a method to generate hybrid RQMC sequences using Stratified Sampling. Stratified sampling means dividing the sample space into subsets (or strata) and constraining the number of samples drawn from each subset. Glasserman [1] provides a method of stratifying the unit interval (0, 1) and extends this method to the unit hypercube. We will use his method to construct hyperrectangles within the unit hypercube and extend it slightly. We will also address the primary issues associated with stratified sampling, namely

• We must know in advance how many samples will be taken by Hull [3]
• The sequence can’t be extended easily without restarting the simulation
• Stratified sampling is impractical for dimensions greater than about s=5 by Glasserman [1]
• Jittered Stratified sampling or hypercube construction suffers from the “curse of dimensionality” by Jarosz [2]
• Completely dividing the hypercube in sub-hyperrectangles forces the value of N, i.e. one can’t freely pick N

Below is the link to the paper in PDF format:

Implementation of a Hybrid Randomized quasi-Monte Carlo Sequence using Stratified Sampling

Description of source code files:

• 1000.txt: first 1000 primes
• Integration multi dimension.ipynb: multi-dimensional integration
• Plots 2-3 dimension.ipynb: 2 and 3 dimensional plots of different types of sequences
• anderson.py: Anderson-Darling stastistical test
• beasley_springer_moro.py: a method to generate normal distributions
• bfs.py: BFS sequence generation
• box_muller.py: another method to generate normal distributions
• brownian motion.ipynb: pricing of European call options using Monte Carlo
• examples.ipynb: misc problems solved using Monte Carlo
• halton.py: Halton sequence generation
• multi-dimensional integration result plots.ipynb: comparison of different sequences to integration problems
• rand.py: pseudorandom sequence generation
• standard normal.ipynb: generation of standard normal distribution using various sequences and either beasley_springer_moro.py or box_muller.py