# Monte Carlo and Quasi-Monte Carlo Sampling / Edition 1

ISBN-10: 1441926763

ISBN-13: 9781441926760

Pub. Date: 12/06/2010

Publisher: Springer New York

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.  See more details below

## Overview

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.

## Product Details

ISBN-13:
9781441926760
Publisher:
Springer New York
Publication date:
12/06/2010
Series:
Springer Series in Statistics
Edition description:
Softcover reprint of hardcover 1st ed. 2009
Pages:
373
Product dimensions:
0.81(w) x 6.14(h) x 9.21(d)

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 <$>{\op Z}_m<$> 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 originalconstructions 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 <$>\sigma_I^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