Monte Carlo and Quasi-Monte Carlo Methods 2008 (eBook)

Preface 5
Contents 8
Part I Tutorials 12
Monte Carlo and Quasi-Monte Carlo for Statistics 13
Introduction 13
The Bootstrap 14
Permutation Tests 18
MCMC 21
Least Trimmed Squares 23
Other Methods 26
References 26
Monte Carlo Computation in Finance 29
Introduction 29
Overview of Financial Simulation Problems 30
Financial Simulations in Context 33
Multiple Simulation Problems 35
Variance Reduction 38
Risk Management 42
Financial Optimization Problems 43
Sensitivity Analysis 44
Discretization of Stochastic Differential Equations 46
References 48
Part II Invited Articles 53
Particle Markov Chain Monte Carlo for Efficient Numerical Simulation 54
Introduction 54
Sequential Monte Carlo Methods 55
Particle Independent MH Sampler 58
Algorithm 59
Extended Proposal and Target Distributions 59
Structure of the Invariant Distribution and Alternative Algorithm 61
Using All the Particles 62
Particle Marginal MH Sampler and Particle Gibbs Sampler 62
Particle Marginal MH Sampler 63
Particle Gibbs Sampler 64
Extensions and Discussion 65
Application to Markov Jump Processes 66
Conclusion 67
References 69
Computational Complexity of Metropolis-Hastings Methods in High Dimensions 70
Introduction 70
Structure of the Target 71
Product Target 71
Beyond the Product Structure 71
Computational Complexity 73
The Algorithms 74
Complexity 75
A Special Result: Diffusion Limit 76
Open Questions 78
References 80
On Quasi-Monte Carlo Rules Achieving Higher Order Convergence 81
Introduction 81
Higher Order Convergence for Smooth Periodic Functions Using Lattice Rules 84
Lattice Rules 84
Decay of the Fourier Coefficients of Smooth Periodic Functions 84
Numerical Integration 85
Preliminaries 86
The Digital Construction Scheme 86
Walsh Functions 87
Higher Order Convergence of Smooth Functions Using Generalized Digital Nets 88
Decay of the Walsh Coefficients of Smooth Functions 88
Numerical Integration 90
Generalized Digital Nets 91
Construction of Generalized Digital Nets 93
Geometrical Properties of Generalized Digital Nets 95
Geometrical Numerical Integration 98
References 103
Sensitivity Estimates for Compound Sums 105
Introduction 105
Motivating Applications 107
Lévy Processes 107
Stochastic Volatility and Squared Bessel Bridges 108
Locally Continuous Construction 109
Application to the Squared Bessel Bridge 116
Globally Continuous Construction 118
Concluding Remarks 120
References 120
New Perspectives on (0,s)-Sequences 121
Introduction 121
Background Information 122
Framework of Generalized Niederreiter Sequences 126
New Efficient Scramblings of (0,s)-Sequences 128
A Construction Extensible in the Dimension--GF3 130
Numerical Results 131
Conclusion 135
References 136
Variable Subspace Sampling and Multi-level Algorithms 139
Introduction 139
Multi-level Algorithms 141
A Cost Model for Variable Subspace Sampling 145
Analysis of the Multi-level Algorithm 148
General Results 148
Lipschitz Continuous Integrands 151
Minimal Errors in Different Cost Models 156
Optimal Quadrature of Lipschitz Functionals 157
Gaussian Measures 158
Diffusion Processes 160
Concluding Remarks 162
References 163
Markov Chain Monte Carlo Algorithms: Theory and Practice 165
Introduction 165
Asymptotic Convergence 166
Quantitative Convergence Bounds 167
Minorisation Conditions (Small Sets) 168
Drift Conditions 168
An Explicit Convergence Bound 169
A 20-Dimensional Example 169
Adaptive MCMC 171
A Toy Example 171
An Adaptive MCMC Convergence Theorem 172
A 100-Dimensional Example 173
Connection with QMC? 174
Summary 175
References 176
MinT -- New Features and New Results 178
Introduction 178
Basic Notations and Concepts 179
New Features in MinT 183
New Nets based on OOA Propagation Rules 188
A Generalized Matrix-Product Construction for Generalized Codes 191
References 195
Part III Contributed Articles 197
Recursive Computation of Value-at-Risk and Conditional Value-at-Risk using MC and QMC 198
Introduction 199
Design of the VaR-CVaR Stochastic Approximation Algorithm 201
Devise of a VaR-CVaR Procedure (First Phase) 201
Variance Reduction Using Adaptive Recursive Importance Sampling (Final Phase) 204
Quasi-Stochastic Approximation 210
Numerical Illustrations 211
References 213
Adaptive Monte Carlo Algorithms Applied to Heterogeneous Transport Problems 214
Introduction 214
The Model Problem and Equations 217
G1 Solution 222
G2 Solution 223
G3 Solution 225
Summary 228
References 229
Efficient Simulation of Light-Tailed Sums: an Old-Folk Song Sung to a Faster New Tune... 231
Introduction 232
Large Deviations Results for Light Tailed Sums 234
A Proposed Algorithm and Intuitive Analysis 237
Rigorous Efficiency Analysis 241
The Multidimensional Case 250
References 252
Distribution of Digital Explicit Inversive Pseudorandom Numbers and Their Binary Threshold Sequence 253
Introduction 253
Discrepancy Bound 255
Correlation Measure of Order k 260
Linear Complexity Profile 260
References 261
Extensions of Fibonacci Lattice Rules 263
Introduction 263
A Short Course on Lattice Rules 264
Fibonacci Lattice Rules 266
An Extension of Fibonacci Lattice Rules 267
Final Remarks 273
References 274
Efficient Search for Two-Dimensional Rank-1 Lattices with Applications in Graphics 275
Introduction 275
Efficient Search by Restricting the Search Space 277
Approximate Search for MMD Rank-1 Lattices 277
Search for MMD Rank-1 Lattice Sequences 280
Search of Anisotropic Rank-1 Lattices to Approximate Spectra 284
Weighted Norms 285
Applications in Computer Graphics 287
Anti-Aliasing by Anisotropic Rank-1 Lattices 287
Rank-1 Lattice Images and Textures 289
Conclusions 290
References 290
Parallel Random Number Generators Based on Large Order Multiple Recursive Generators 292
Introduction 292
MRGs and Classes of Efficient Generators 294
Searching for Large-Order MRGs 294
Efficient Classes of DL and DT Generators 295
Automatic Generating Method for Parallel MRGs 297
Constructing MRGs with Different Multipliers 297
Construction of Parallel MRGs from DL-k and DT-k 298
References 299
Efficient Numerical Inversion for Financial Simulations 300
Introduction 300
The Automatic Algorithm 302
Considerations for Approximate Densities 303
The Generalized Hyperbolic Distribution 304
The Non-Central Chi-Square Distribution 304
References 307
Equidistribution Properties of Generalized Nets and Sequences 308
Introduction 308
Definition of Digital (t,alpha,beta, n m,s)-Nets and Digital (t,alpha,beta,sigma,s)-Sequences 309
Equidistribution Properties of Generalized Nets and Sequences 314
Definition of (t,alpha,beta, n,m,s)-Nets and (t,alpha,beta,sigma,s)-Sequences 315
Some Properties of (t,alpha,beta, n, m,s)-Nets and (t,alpha,beta,sigma,s)-Sequences 320
References 324
Implementation of a Component-By-Component Algorithm to Generate Small Low-Discrepancy Samples 326
Introduction 326
Description of the Algorithm 328
General Method 328
Implementation Details 331
Numerical Experiments 332
Dependence on the Dimension 333
Analysing the Discrepancy: Rounding Error vs. Placement Error 333
Finetuning the Algorithm 335
Randomization of the Output Set 336
A Hybrid Approach: Extending Halton-Hammersley Point Sets 338
References 340
Quasi-Monte Carlo Simulation of Diffusion in a Spatially Nonhomogeneous Medium 342
Introduction 342
Simulation of Diffusion Using a Random Walk Method 343
Correction to the Steplength 347
QMC Scheme in a Nonhomogeneous Medium 349
Approximation with a Fixed Number of Particles 349
Approximation with a Varying Number of Particles 350
Numerical Examples 351
Constant Diffusion Coefficient and Instantaneous Emission 351
Variable Diffusion Coefficient and Instantaneous Emission 353
Variable Diffusion Coefficient and Non-Instantaneous Emission 353
Conclusion 355
References 357
L2 Discrepancy of Two-Dimensional Digitally Shifted Hammersley Point Sets in Base b 358
Introduction and Statement of the Results 358
Auxiliary Results 362
The Proof of Theorem 1 368
References 371
Vibrato Monte Carlo Sensitivities 372
Introduction 372
Pathwise and LRM Sensitivities 373
Vibrato Monte Carlo 375
Conditional Expectation 375
Vibrato Monte Carlo 376
Efficient Estimators 377
Multivariate Generalisation 379
Optimal Number of Samples 381
Numerical Results 382
Adjoint Pathwise Sensitivity Implementation 383
Conclusions and Future Work 384
References 384
The Weighted Variance Minimization in Jump-Diffusion Stochastic Volatility Models 386
Introduction 386
Estimators with the Minimal Weighted Variance 388
Application to the Options Valuation 392
Approximations 393
Simulation Results 394
References 397
(t,m,s)-Nets and Maximized Minimum Distance, Part II 398
Introduction 398
A New (0, m, 3)-Net in Base 2 with Large Minimum Toroidal Distance 400
Digital Nets and Sequences 400
Reordering the Sobol'-Sequence 401
Construction 402
Permutation-Generated (0,m,2)-Nets in Base 2 with Larger Minimum Toroidal Distance 403
Iterative Construction by Quadrupling Point Sets 404
Direct Construction 407
Implementation for General m 410
Conclusion 411
References 411
Automation of Statistical Tests on Randomness to Obtain Clearer Conclusion 413
Introduction 413
Statistical Tests 414
Adaptive Statistical Test 415
The Results of Tests 416
Weight Distribution Test on FSRs 416
Hamming Weight Test on LCG 417
Crush in TestU01 and the Adaptive Crush 418
Comparison of the Sensitivity 419
Conclusion 420
References 422
On Subsequences of Niederreiter-Halton Sequences 424
Introduction 424
Subsequences 428
Subsequences Indexed by the Solutions of a System of Congruences 430
Subsequences Indexed by Primes 433
Conclusion 437
References 439
Correcting the Bias in Monte Carlo Estimators of American-style Option Values 440
Introduction 440
Bias Correction 442
Applications 446
Stochastic Tree 446
Stochastic Mesh 447
LSM 448
Numerical Results 451
Conclusion 454
References 455
Fast Principal Components Analysis Method for Finance Problems With Unequal Time Steps 456
Background 456
The Use of Monte Carlo in Finance 456
Fast Matrix-Vector Product for the Principal Components Analysis Method 458
Symmetric Semi-Separable Matrices 459
Fast PCA Method and Semi-Separable Matrices 462
Numerical Tests 464
References 465
Adaptive Monte Carlo Algorithms for General Transport Problems 467
Introduction 468
Problem Setting 470
First Generation (G1) Methods: Solution Expansion 473
Second Generation (G2) Methods: Avoiding Expansion 476
Third Generation (G3) Algorithms: Intelligent Mesh Refinement 478
Summary, Conclusions and Future Research Directions 481
References 482
On Array-RQMC for Markov Chains: Mapping Alternatives and Convergence Rates 484
Introduction 484
A Markov Chain Setting 485
The Array-RQMC Algorithm 486
Mapping the Chains to the Points 490
Empirical Investigations of the Convergence Rate 491
Example 1: An Autoregressive Process 491
Example 2: An Asian Option 495
Future Work and Conclusion 497
References 498
Testing the Tests: Using Random Number Generators to Improve Empirical Tests 500
Introduction 500
Two-Level Testing with a Battery of Tests 501
Initial Testing of PseudoDIEHARD in TestU01 502
Overlapping Serial Tests 504
Final TestU01 Results 507
Computation of the Variances for the Monkey Tests 508
References 510
Stochastic Spectral Formulations for Elliptic Problems 512
Introduction 512
The Stochastic Spectral Formulation 514
One Random Step Schemes 514
Quantization 515
Formulation and Asymptotic Properties 517
Error Bounds Based on Confidence Intervals 519
The Unbiased Monte Carlo Case 519
A Basic One Dimensional Example 521
The Biased Monte Carlo Case 522
Other Cases 523
Numerical Results 524
Conclusion 525
References 526
Adaptive (Quasi-)Monte Carlo Methods for Pricing Path-Dependent Options 528
Introduction 528
Path-Integral Decomposition Approach 529
Adaptive Integration Methods 532
Adaptive Importance and Stratified Samplings 532
Sampling from a Multivariate Piecewise Constant PDF 532
Asset Pricing Models 534
The CEV Diffusion Model 534
The Variance Gamma Model 536
Numerical Results 537
Modelling with the VG Process 538
Modelling with the CEV Process 540
Conclusions 542
References 543
Monte Carlo Simulation of Stochastic Integrals when the Cost of Function Evaluation Is Dimension Dependent 544
Introduction 544
Illustrative Example 546
Worst-Case Error Bound 549
Numerical Experiment 556
References 558
Recent Progress in Improvement of Extreme Discrepancy and Star Discrepancy of One-Dimensional Sequences 560
Introduction 560
Main Results 563
Upper and Lower Bounds of s(S84,sigma84) and s*(S60,SigmaA) 563
Proofs 564
Function Psi84,sigma84(x) 565
Proof of Theorem 4 565
Functions Psi+60,sigma60(x) and Psi-60,sigma60(x) 568
Proof of Theorem 5 568
Search Method 569
Conclusions 570
References 570
Discrepancy of Hyperplane Nets and Cyclic Nets 572
Introduction 572
Prerequisites 575
The Results 577
References 585
A PRNG Specialized in Double Precision Floating Point Numbers Using an Affine Transition 587
Introduction 587
Generating Floating Point Numbers 588
LFSR with Lung 589
Affinity Introduced by the Constant Part 590
Reduction from Affine to Linear: Fixed Points 591
Reducible Transition Function in Affine Case 591
Period Certification 592
Computation of the Dimension of Equidistribution 593
Implementation of dSFMT 594
Comparison of Speed 596
Dimension of Equidistribution 597
References 599
On the Behavior of the Weighted Star Discrepancy Bounds for Shifted Lattice Rules 601
Introduction and Background Results 601
Bounds on the Weighted Star Discrepancy 604
The CBC Construction and Random Search Methods 606
Empirical Assessments 607
References 613
Ergodic Estimations of Upscaled Coefficients for Diffusion in Random Velocity Fields 615
Introduction 615
Path Decomposition of Diffusion Coefficients 616
Upscaled Coefficients for Diffusion in Random Fields 617
Exactly Computable Diffusion Coefficients 618
Estimated Upscaled Coefficients for Diffusion in Random Velocity Fields 620
Conclusions 623
References 624
Green's Functions by Monte Carlo 625
Introduction 625
Function Space Sampling and Algorithm Description 626
Examples and Numerics 628
Other Related Proposals 631
Conclusions and Further Work 632
References 634
Tractability of Multivariate Integration for Weighted Korobov Spaces: My 15 Year Partnership with Ian Sloan 635
Introduction 635
Weighted Korobov Spaces 637
Multivariate Integration and Tractability 639
Lower Bounds for F 643
Upper Bounds for F 647
Tractability 648
References 651
Conference Participants 652
Author Index 668