Monte Carlo and Quasi-Monte Carlo Sampling (Springer Series in Statistics)
By Christiane Lemieux


Publisher:   Springer
Number Of Pages:   376
Publication Date:   2009-02-27
ISBN-10 / ASIN:   0387781641
ISBN-13 / EAN:   9780387781648


Product Description:


Quasi-Monte Carlo methods have become an increasingly popular alternative to Monte Carlo methods over the last two decades. Their successful implementation on practical problems, especially in finance, has motivated the development of several new research areas within this field to which practitioners and researchers from various disciplines currently contribute.

This book presents essential tools for using quasi-Monte Carlo sampling in practice. The first part of the book focuses on issues related to Monte Carlo methods—uniform and non-uniform random number generation, variance reduction techniques—but the material is presented to prepare the readers for the next step, which is to replace the random sampling inherent to Monte Carlo by quasi-random sampling. The second part of the book deals with this next step. Several aspects of quasi-Monte Carlo methods are covered, including constructions, randomizations, the use of ANOVA decompositions, and the concept of effective dimension. The third part of the book is devoted to applications in finance and more advanced statistical tools like Markov chain Monte Carlo and sequential Monte Carlo, with a discussion of their quasi-Monte Carlo counterpart.

The prerequisites for reading this book are a basic knowledge of statistics and enough mathematical maturity to follow through the various techniques used throughout the book. This text is aimed at graduate students in statistics, management science, operations research, engineering, and applied mathematics. It should also be useful to practitioners who want to learn more about Monte Carlo and quasi-Monte Carlo methods and researchers interested in an up-to-date guide to these methods.

Christiane Lemieux is an Associate Professor and the Associate Chair for Actuarial Science in the Department of Statistics and Actuarial Science at the University of Waterloo in Canada. She is an Associate of the Society of Actuaries and was the winner of a “Young Researcher Award in Information-Based Complexity” in 2004.

Contents

1 The Monte Carlo Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Monte Carlo method for integration . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Connection with stochastic simulation . . . . . . . . . . . . . . . . . . . . . 12
1.3 Alternative formulation of the integration problem via f:

       an example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.4 A primer on uniform random number generation . . . . . . . . . . . 22
1.5 Using Monte Carlo to approximate a distribution . . . . . . . . . . . 25
1.6 Two more examples. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2 Sampling from Known Distributions . . . . . . . . . . . . . . . . . . . . . . 41
2.1 Common distributions arising in stochastic models . . . . . . . . . . 42
2.2 Inversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.3 Acceptance-rejection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.4 Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.5 Convolution and other useful identities . . . . . . . . . . . . . . . . . . . . 50
2.6 Multivariate case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3 Pseudorandom Number Generators . . . . . . . . . . . . . . . . . . . . . . . 57
3.1 Basic concepts and definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.2 Generators based on linear recurrences . . . . . . . . . . . . . . . . . . . . 60
3.2.1 Recurrences over Zm for m ≥ 2 . . . . . . . . . . . . . . . . . . . . 61
3.2.2 Recurrences modulo 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.3 Add-with-carry and subtract-with-borrow generators . . . . . . . . 66
3.4 Nonlinear generators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.5 Theoretical and statistical testing . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.5.1 Theoretical tests for MRGs . . . . . . . . . . . . . . . . . . . . . . . . 70
3.5.2 Theoretical tests for PRNGs based on recurrences
modulo 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.5.3 Statistical tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
4 Variance Reduction Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4.2 Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.3 Antithetic variates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.4 Control variates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.5 Importance sampling. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
4.6 Conditional Monte Carlo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
4.7 Stratification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
4.8 Common random numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
4.9 Combinations of techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
5 Quasi–Monte Carlo Constructions . . . . . . . . . . . . . . . . . . . . . . . . 139
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
5.2 Main constructions: basic principles . . . . . . . . . . . . . . . . . . . . . . . 143
5.3 Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
5.4 Digital nets and sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
5.4.1 Sobol’ sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
5.4.2 Faure sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
5.4.3 Niederreiter sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
5.4.4 Improvements to the original constructions
of Halton, Sobol’, Niederreiter, and Faure . . . . . . . . . . . 164
5.4.5 Digital net constructions and extensions . . . . . . . . . . . . . 170
5.5 Recurrence-based point sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
5.6 Quality measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
5.6.1 Discrepancy and related measures . . . . . . . . . . . . . . . . . . 180
5.6.2 Criteria based on Fourier and
Walsh decompositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
5.6.3 Motivation for going beyond error bounds . . . . . . . . . . . 197
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
6 Using Quasi–Monte Carlo in Practice . . . . . . . . . . . . . . . . . . . . . 201
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
6.2 Randomized quasi–Monte Carlo . . . . . . . . . . . . . . . . . . . . . . . . . . 202
6.2.1 Random shift (or rotation sampling) . . . . . . . . . . . . . . . . 204
6.2.2 Digital shift . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
6.2.3 Scrambling and permutations . . . . . . . . . . . . . . . . . . . . . . 206
6.2.4 Partitions and Latin supercube sampling . . . . . . . . . . . . 209
6.2.5 Array-RQMC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
6.2.6 Studying the variance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
6.3 ANOVA decomposition and effective dimension . . . . . . . . . . . . 214
6.3.1 Effective dimension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
6.3.2 Brownian bridge and related techniques . . . . . . . . . . . . . 222
6.3.3 Methods for estimating σ2 and approximating fI (u) . . . . . . . . . . . . . . . . . . . . . . . . . . 225
6.3.4 Using the ANOVA insight to find
good constructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
6.4 Using quasi–Monte Carlo sampling for simulation . . . . . . . . . . . 229
6.5 Suggestions for practitioners . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
Appendix: Tractability, weighted spaces
and component-by-component constructions . . . . . . . . . . . . . . . 241
7 Financial Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
7.1 European option pricing under the lognormal model . . . . . . . . 247
7.2 More complex models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
7.2.1 Heston’s process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
7.2.2 Regime switching model . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
7.2.3 Variance gamma model . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
7.3 Randomized quasi–Monte Carlo methods in finance . . . . . . . . . 260
7.4 Commonly used variance reduction techniques . . . . . . . . . . . . . 273
7.4.1 Antithetic variates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
7.4.2 Control variates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
7.4.3 Importance sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275
7.4.4 Conditional Monte Carlo . . . . . . . . . . . . . . . . . . . . . . . . . . 279
7.4.5 Common random numbers . . . . . . . . . . . . . . . . . . . . . . . . . 281
7.4.6 Moment-matching methods . . . . . . . . . . . . . . . . . . . . . . . . 282
7.5 American option pricing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
7.6 Estimating sensitivities and percentiles . . . . . . . . . . . . . . . . . . . . 288
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
8 Beyond Numerical Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
8.1 Markov Chain Monte Carlo (MCMC) . . . . . . . . . . . . . . . . . . . . . 303
8.1.1 Metropolis-Hastings algorithm . . . . . . . . . . . . . . . . . . . . . 305
8.1.2 Exact sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
8.2 Sequential Monte Carlo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312
8.3 Computer experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
A Review of Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
B Error and Variance Analysis for Halton Sequences . . . . . . . . 341
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369