IEEE International Parallel and Distributed Processing Symposium (IPDPS)

Parameterization based on randomized quasi-Monte Carlo methods

Giray Ökten, Matthew Willyard

Published Apr 1, 2008• 1 citation

Abstract

We present a theoretical framework where any randomized quasi-Monte Carlo method can be viewed and analyzed as a parameterization method for parallel quasi-Monte Carlo. We present deterministic and stochastic error bounds when different processors of the computing environment run at different speeds. We implement two parameterization methods, both based on randomized quasi-Monte Carlo, and apply them to pricing digital options and collateralized mortgage obligations. Numerical results are used to compare the parameterization methods by their parallel performance as well as their Monte Carlo efficiency.

DOI: 10.1109/ipdps.2008.4536457

Related papers

American option pricing with randomized quasi-Monte Carlo simulations

Maxime Dion, Pierre L’Ecuyer

We study the pricing of American options using least-squares Monte Carlo combined with randomized quasi-Monte Carlo (RQMC), viewed as a variance reduction method. We find that RQMC reduces both the variance and the bias of the option price obtained in an out-of-sample evaluation of the retained policy, and improves the quality of the returned policy on average. Various sampling methods of the underlying stochastic processes are compared and the variance reduction is analyzed in terms of a functional ANOVA decomposition.

Winter Simulation ConferenceDec 1, 201017 citations

Parallel Randomized Quasi-Monte Carlo Simulation for Asian Basket Option Pricing

Yonghong Hu, Da-Qian Chen

High-dimensional derivatives pricing, such as Asian basket options, poses great computational challenges in practice. In this paper, parallel Randomized Quasi-Monte Carlo (RQMC) simulation method is investigated to tackle this kind of intractable problems. By using the intrinsic nature of “embarrassingly parallel”, parallel RQMC algorithm for Asian basket option pricing is effectively implemented using MPI. Numerical experiments are performed on supercomputer DeepComp6800 and the parallel performance is then analyzed. Our parallel algorithm has exerted perfect performance and good scalability. Parallel computing has greatly improved the computational efficiency of derivatives pricing.

Journal of Algorithms & Computational TechnologyMar 1, 20126 citations

Efficient quasi-Monte Carlo sampling for quantum random walks

Emanouil I. Atanassov, Mariya K. Durchova

Quantum random walks are the natural counterpart of the classical random walk, arising when quantum effects are taken into consideration. Many Monte Carlo methods use the classical Brownian motion as a building block. Although it appears naturally in various problems of computational physics, it is also used extensively in the stochastic models used for pricing of financial assets. When quantum random walks are used instead, more complex behaviors can be observed. However, the simulation of a quantum random walk requires more computational resources. By using low-discrepancy sequences instead of pseudorandom numbers, one may hope to decrease the statistical error of the simulation. Another approach for improved efficiency is to use the power of computational accelerators, which are suitable for problems, where a well-ordered sequence of computations is to be performed repeatedly. In our work we concentrated on using GPGPU computing in order to speed-up the operations involved in the generation of the low-discrepancy sequence as well as the subsequent sampling of the quantum random walks. In this work we explain our sampling algorithm and demonstrate its efficiency on model problems from the domain of option pricing.

AIP conference proceedingsJan 1, 20202 citations

Scrambled quasirandom sequences and their applications

Hongmei Chi, Michael Mascagni

Quasi-Monte Carlo methods are a variant of ordinary Monte Carlo methods that employ highly uniform quasirandom numbers in place of Monte Carlo's pseudorandom numbers. Monte Carlo methods offer statistical error estimates; however, while quasi-Monte Carlo has a faster convergence rate than normal Monte Carlo, one cannot obtain error estimates from quasi-Monte Carlo sample values by any practical way. A recently proposed method, called randomized quasi-Monte Carlo methods, takes advantage of Monte Carlo and quasi-Monte Carlo methods. Randomness can be brought to bear on quasirandom sequences through scrambling and other related randomization techniques in randomized quasi-Monte Carlo methods, which provide an elegant approach to obtain error estimates for quasi-Monte Carlo based on treating each scrambled sequence as a different and independent random sample. The core of randomized quasi-Monte Carlo is to find an effective and fast algorithm to scramble (randomize) quasirandom sequences. This dissertation surveys research on algorithms and implementations of scrambled quasirandom sequences and proposes some new algorithms to improve the quality of scrambled quasirandom sequences. Besides obtaining error estimates for quasi-Monte Carlo, scrambling techniques provide a natural way to parallelize quasirandom sequences. This scheme is especially suitable for distributed or grid computing. By scrambling a quasirandom sequence we can produce a family of related quasirandom sequences. Finding one or a subset of optimal quasirandom sequences within this family is an interesting problem, as such optimal quasirandom sequences can be quite useful for quasi-Monte Carlo. The process of finding such optimal quasirandom sequences is called the derandomization of a randomized (scrambled) family. We summarize aspects of this technique and propose some new algorithms for finding optimal sequences from the Halton, Faure and Sobol sequences. Finally we explore applications of derandomization.

Jan 1, 20048 citations

Quasi-Monte Carlo methods for simulation

Pierre L’Ecuyer

Quasi-Monte Carlo (QMC) methods are numerical techniques for estimating large-dimensional integrals, usually over the unit hypercube. They can be applied, at least in principle, to any simulation whose aim is to estimate a mathematical expectation. This covers a very wide range of applications. In this paper, we review some of the key ideas of quasi-Monte Carlo methods from a broad perspective, with emphasis on some recent results. We visit lattice rules in different types of spaces and make the connections between these rules and digital nets, thus covering the two most widely used QMC methods.

International Conference on Machine Learning and CyberneticsMay 6, 20043 citations

Randomized Quasi-Monte Carlo: An Introduction for Practitioners

Pierre L’Ecuyer

We survey basic ideas and results on randomized quasi-Monte Carlo (RQMC) methods, discuss their practical aspects, and give numerical illustrations. RQMC can improve accuracy compared with standard Monte Carlo (MC) when estimating an integral interpreted as a mathematical expectation. RQMC estimators are unbiased and their variance converges at a faster rate (under certain conditions) than MC estimators, as a function of the sample size. Variants of RQMC also work for the simulation of Markov chains, for function approximation and optimization, for solving partial differential equations, etc. In this introductory survey, we look at how RQMC point sets and sequences are constructed, how we measure their uniformity, why they can work for high-dimensional integrals, and how can they work when simulating Markov chains over a large number of steps.

Aug 14, 20162 citations