Monte Carlo and Quasi-Monte Carlo Methods 2012

Preface......Page 6
Contents......Page 10
Part I Invited Articles......Page 14
  1 Introduction......Page 15
  2 Benchmark Approach......Page 17
  3 Lie Symmetry Methods......Page 19
  4 Wishart Processes......Page 25
  5 Bivariate MMM......Page 28
  References......Page 32
  1 Introduction......Page 35
  2 The Orthogonal Function Method......Page 37
  3 The Small Ball Inequality......Page 40
   4.1 Approximation Theory: Metric Entropy of Classes with Dominating Mixed Smoothness......Page 42
   4.3 Summary of the Connections......Page 43
  5 Riesz Product Techniques......Page 44
  6 Recent Results......Page 47
   6.1 Other Endpoint Estimates......Page 48
  References......Page 49
 An Introduction to Stochastic Particle Integration Methods: With Applications to Risk and Insurance......Page 51
  1 Introduction to Stochastic Particle Integration......Page 52
   2.1 The Loss Distributional Approach and Risk Management: A Tale of Light to Heavy Tails......Page 54
    2.1.1 A Light Tale of Light Tails......Page 57
    2.1.2 A Heavier Tale of Heavy Tails......Page 58
   2.2 Inferential Challenges for Risk and Insurance: Asymptotics and the Role for Stochastic Particle Integration......Page 60
  3 Selected Topics in Stochastic Integration Methods......Page 62
   3.1 Standard Monte Carlo Techniques for Risk and Insurance......Page 63
   3.2 Importance Sampling Techniques for Risk and Insurance......Page 66
   3.3 Markov Chain Monte Carlo for Risk and Insurance......Page 67
   3.4 Sequential Monte Carlo for Risk and Insurance......Page 69
    3.4.2 An Acceptance-Rejection Markov Model......Page 72
    3.4.3 Feynman-Kac Distributions......Page 73
   3.5 Non-linear McKean Markov Chains......Page 76
    3.5.1 Mean Field Particle Simulation......Page 77
   3.6 A Sequential Monte Carlo Formulation......Page 79
    3.6.1 Some Non-asymptotic Estimates: Finite Sample Accuracy for Particle Integration......Page 80
    3.6.2 Non-asymptotic Estimates for Risk Measure Estimation via Interacting Particle Systems......Page 81
   4.1 Recursions for Loss Distributions: Panjer and Beyond......Page 83
   4.2 Stochastic Particle Methods as Solutions to Panjer Recursions......Page 85
   4.3 Stochastic Particle Solutions to Risk Measure Estimation......Page 87
  References......Page 90
   1.1 Control Variates and Two-Level MLMC......Page 94
   1.2 Multilevel Monte Carlo......Page 95
   1.3 Earlier Related Work......Page 96
  2 MLMC Theorem......Page 97
   3.1 Euler Discretisation......Page 99
   3.2 Milstein Discretisation......Page 100
    3.2.1 Digital Options......Page 101
    3.2.2 Multi-dimensional SDEs......Page 102
    3.3.1 Jump-Diffusion Processes......Page 103
  4 SPDEs......Page 104
   4.1 Elliptic SPDE......Page 105
   4.2 Parabolic SPDE......Page 106
  5 Continuous-Time Markov Chain Simulation......Page 107
   7.1 Nested Simulation......Page 108
   7.2 Truncated Series Expansions......Page 109
   7.4 Multiple Outputs......Page 110
  8 Conclusions......Page 111
  References......Page 112
  1 Introduction......Page 115
  2 Background Probability and Statistics......Page 119
   2.2 CLT Intervals......Page 120
   2.3 Standard Probability Inequalities......Page 121
   3.1 Conservative Variance Estimates......Page 122
   3.2 Conservative Interval Widths......Page 124
   3.3 Algorithm and Proof of Its Success......Page 125
   3.4 Cost of the Algorithm......Page 127
   4.1 Univariate Fooling Functions for Deterministic Algorithms......Page 129
   4.2 Integrating a Single Hump......Page 130
   4.3 Asian Geometric Mean Call Option Pricing......Page 133
  5 Discussion......Page 135
  References......Page 137
 Discrepancy, Integration and Tractability......Page 139
  1 Introduction......Page 140
  2 Discrepancy and Integration in Function Spaces......Page 141
   2.1 Function Spaces of Dominating Mixed Smoothness and Haar Functions......Page 144
   2.2 Discrepancy of Hammersley and Chen-Skriganov Point Sets......Page 147
   2.3 Integration Errors in Besov Spaces of Dominating Mixed Smoothness......Page 148
   3.1 Average Discrepancy as an Empirical Process......Page 150
   3.2 Average Lp-Discrepancy......Page 152
  4 Star Discrepancy of Structured Sets......Page 161
   4.1 Discrepancy with Respect to a Lower Dimensional Subspace......Page 162
   4.2 Approximation of μ0 by Point Sets......Page 163
  5 Importance Sampling and Tractability of High Dimensional Integration......Page 165
   5.1 Optimality of Importance Sampling......Page 166
    5.1.1 Change of Density......Page 169
    5.1.2 Importance Sampling from Change of Density......Page 170
    5.1.3 Tractability of Multivariate Integration......Page 172
    5.1.4 Examples......Page 173
   5.2 Explicit Importance Sampling Densities: Sampling with the Representer......Page 176
  References......Page 180
 Noisy Information: Optimality, Complexity, Tractability......Page 183
  1 Introduction......Page 184
  2 Basics......Page 185
    2.1.1 Information with Bounded Noise......Page 186
    2.2.1 Worst Case Setting......Page 187
    2.2.3 Randomized Setting......Page 188
    3.1.1 Worst Case Setting......Page 189
    3.1.2 Average Case Setting......Page 193
    3.1.3 Equivalence of Different Settings......Page 195
    3.2.1 Worst Case Setting......Page 197
    3.2.2 Average Case Setting......Page 201
    4.1.1 Bounded Noise......Page 202
   4.2 Worst Case and Randomized Complexities......Page 204
    4.2.1 Adaption Versus Nonadaption......Page 205
    4.2.2 Complexity of Integration in Hölder Classes......Page 206
   4.3 Average Case Complexity......Page 212
    4.3.2 Complexity of Approximation with Λ=Λall......Page 213
  5 Tractability......Page 215
    5.1.1 Worst Case Integration in Hölder Classes......Page 216
    5.1.2 Average Case Approximation with Λ=Λall......Page 217
  References......Page 218
Part II Tutorial......Page 220
  1 Introduction......Page 221
    1.1.2 Unbiased Monte Carlo Algorithms......Page 222
    1.1.4 Deterministic Consistent Numerical Algorithms......Page 223
  2 Principles of Light Transport Simulation......Page 224
   2.1 Light Transport Along Paths......Page 225
   2.2 Accelerated Ray Tracing and Visibility......Page 226
   3.1 Uniform Sampling, Stratification, and Discrete Density Approximation......Page 227
   3.2 Error Bounds......Page 229
    3.3.1 Radical Inversion......Page 230
    3.3.3 Halton Sequence and Hammersley Points......Page 232
    3.3.4 Digital (t,s)-Sequences and (t,m,s)-Nets......Page 233
    3.3.5 Rank-1 Lattice Sequences and Rank-1 Lattices......Page 235
    3.4.1 Enumeration in Elementary Intervals......Page 236
    3.4.2 Partitioning Low Discrepancy Sequences......Page 237
    3.4.4 Splitting......Page 238
  4 Deterministic Consistent Image Synthesis......Page 240
   4.2 Depth of Field, Motion Blur, and Spectral Rendering......Page 241
   4.3 Sampling Light Transport Path Segments......Page 243
    4.3.3 Next Event Estimation......Page 244
    4.3.4 Light Tracing......Page 245
    4.4.1 Connecting Path Segments by Proximity......Page 246
    4.4.2 Connecting Path Segments by Shadow Rays......Page 248
    4.4.3 Optimally Combining Techniques......Page 249
  5 State of the Art......Page 253
  References......Page 254
Part III Contributed Articles......Page 258
  1 Introduction......Page 259
  2 The LT Method for Heston Under Log Prices......Page 260
  3 Conditional Sampling on Log-LT......Page 265
  4 The Original LT Method for Heston......Page 268
   5.1 Up-&-Out Call and Put......Page 270
   5.3 Up-&-Out Asian......Page 272
  References......Page 274
 Probabilistic Star Discrepancy Bounds for Double Infinite Random Matrices......Page 276
   1.1 Uniform Distribution and Discrepancy......Page 277
   1.2 The Inverse of the Discrepancy......Page 278
   1.4 Complete Uniform Distribution and Markov Chain Monte Carlo......Page 279
   1.5 Results......Page 281
  2 Proofs......Page 284
  References......Page 291
  1 Introduction......Page 293
  2 Preliminaries......Page 296
  3 The Proof of Theorem 1 (Upper Bound)......Page 298
  References......Page 299
  1 Introduction......Page 301
  2 Preliminaries......Page 302
  3 Banach Space Valued Integration......Page 305
  4 A Multilevel Procedure......Page 312
  5 Scalar Parametric Case......Page 314
  References......Page 320
 Extended Latin Hypercube Sampling for Integration and Simulation......Page 321
  1 Introduction......Page 322
  2 Numerical Integration......Page 324
  3 Simulation of Diffusion......Page 328
  References......Page 333
 A Kernel-Based Collocation Method for Elliptic Partial Differential Equations With Random Coefficients......Page 335
  1 Introduction......Page 336
   1.1 Problem Setting......Page 337
  2 Reproducing Kernels and Matérn Functions......Page 339
  3 Constructing Gaussian Fields by Reproducing Kernels with Differential and Boundary Operators......Page 340
  4 Kernel-Based Collocation Methods......Page 341
   4.1 Random Coefficients as Random Variables......Page 342
    4.1.1 Constructing Kernel-Based Solutions......Page 344
    4.1.2 Convergence Analysis......Page 345
   4.2 Random Coefficients as Stochastic Fields......Page 347
  5 Numerical Examples......Page 348
  References......Page 351
  1 Introduction......Page 352
   2.1 Errors and Convergence in Standard MCMC......Page 353
   2.2 Acceleration by Weighted Subsampling......Page 354
   3.1 Normal Distributions......Page 356
   3.3 Matrix Splitting Form of Stationary Iterative Methods......Page 357
   3.4 Matrix Splittings Give Generalized Gibbs Samplers......Page 358
   3.5 Some (Not So Common) Gibbs Samplers for N(0,A-1)......Page 359
  4 Polynomial Acceleration of Gibbs Sampling......Page 360
   4.2 Chebyshev Acceleration......Page 361
    4.3.1 An Example with d=1010......Page 363
  5 A Conjugate Gradient Sampling Algorithm......Page 364
  6 Discussion......Page 367
  References......Page 368
  1 Introduction......Page 370
  2 MLMC......Page 371
   2.1 Milstein Scheme......Page 373
  3 Antithetic MLMC Estimator......Page 374
  4 Clark-Cameron Example......Page 375
  5 Subsampling of Levy Areas......Page 377
   5.1 Antithetic Subsampling......Page 379
   6.1 Lookback Options......Page 382
   6.2 Barrier Options......Page 383
  7 Conclusions......Page 385
  References......Page 386
  1 Introduction......Page 388
   2.1 Notations......Page 390
   2.2 The Feynman-Kac Measure-Valued Model......Page 391
   2.4 Dobrushin Ergodic Coefficients......Page 392
   2.5 Some Non-Asymptotic Results......Page 394
  3 General Feynman-Kac semigroup analysis......Page 395
  4 The Particular Case of Boltzmann-Gibbs Measures, Interacting Simulated Annealing......Page 397
  5 Conclusion......Page 399
  References......Page 400
  1 Introduction......Page 402
   2.2 The Function Spaces......Page 404
   2.4 Randomized Algorithms, Cost Models, and Errors......Page 406
   2.5 Strong Polynomial Tractability......Page 408
   3.1 Results for General Weights......Page 409
    3.2.1 Product Weights and Finite-Product Weights......Page 414
    3.2.3 Lexicographically-Ordered Weights......Page 416
  References......Page 417
 A Non-empirical Test on the Second to the Sixth Least Significant Bits of Pseudorandom Number Generators......Page 419
  1 Introduction......Page 420
  2 χ2-Discrepancy and Weight Discrepancy Tests......Page 421
  3 Computing the Probability by Enumeration......Page 423
  4 The Results of Tests......Page 425
  5 Conclusion and Future Works......Page 427
  References......Page 428
  1 Introduction......Page 429
  2 Scrambling of Faure and Tezuka and Finite-Row Digital (t,s)-Sequences......Page 432
  3 Discrepancy and Experiments......Page 435
   3.1 Summary of the Numerical Experiments......Page 438
  References......Page 439
  1 Introduction......Page 440
  2 Generated Sets......Page 442
  3 Gerschgorin Circle Theorem and Generated Sets......Page 444
  4 Numerical Examples......Page 449
   4.1 Weighted Hyperbolic Crosses......Page 450
   4.2 Randomly Chosen Index Sets......Page 451
  References......Page 454
 Bayesian Approaches to the Design of Markov Chain Monte Carlo Samplers......Page 456
   1.1 Metropolis-Hastings Sampling......Page 457
   1.2 BAIS......Page 459
   2.1 Bayesian Adaptive Metropolis-Hastings Sampling......Page 460
   2.3 A Random Walk Instance of BAMS......Page 462
  3 A Worked Example: Sampling from a Multimodal Distribution......Page 463
  4 Future Directions......Page 466
  References......Page 467
  1 Introduction......Page 468
  2 Consistent Blockwise Quasi-Monte Carlo Methods......Page 469
   2.1 Low Discrepancy Sequences......Page 470
   2.2 Scrambling......Page 471
   2.3 Replication by Partial Scrambling......Page 472
    2.3.3 General Block Size and (0,1)-Sequences......Page 475
   3.1 Consistent Bidirectional Path Tracing......Page 476
   3.2 Consistent Photon Mapping......Page 477
    3.2.1 Generalizations and Extensions......Page 478
  4 Conclusion......Page 479
  References......Page 480
  1 Introduction......Page 482
  2 Wavelet Approximation......Page 486
   2.1 Adaptive Wavelet Methods for Nonlinear Variational Problems......Page 487
  3 Error Analysis for the Stochastic Convolution......Page 491
  4 Pure Time Discretization......Page 494
  5 Error Analysis for the Nonlinear Random Problem......Page 499
  References......Page 500
  1 Introduction......Page 501
  2 Finite Hybrid Quasi-Random Point Sets......Page 505
  3 A CBC Construction......Page 506
   3.1 Computing the Quantity TN......Page 507
   3.2 The CBC Construction......Page 508
  References......Page 514
  1 Introduction......Page 516
   2.1 Spherical Harmonics......Page 517
   2.2 Karhunen-Loève Expansion on the Unit Sphere......Page 518
   2.3 Quasi-Monte Carlo Integration in Weighted Spaces......Page 521
   3.1 Function Spaces......Page 523
   3.2 The Parametric Variational Formulation......Page 524
   3.3 Regularity of the PDE Solution......Page 525
  4 Spectral Method on the Sphere......Page 527
  5 Combined Error Estimates......Page 529
  6 Numerical Experiments......Page 531
  References......Page 533
 Sampling and Low-Rank Tensor Approximation of the Response Surface......Page 534
  1 Motivation......Page 535
   2.1 Reproducing Kernel Hilbert Space......Page 536
   2.2 Spectral Decomposition......Page 537
  3 Discretisation and Computation......Page 539
   3.1 Sampling by Simulation......Page 540
  4 Constructing the Emulation......Page 541
   4.1 Emulation Instead of Simulation......Page 542
  5 Low-Rank Data Compression......Page 543
  6 Numerical Tests......Page 544
   6.1 Numerical Experiment with Sampling from the Response Surface......Page 546
  7 Conclusion......Page 548
  References......Page 549
  1 Introduction......Page 551
  2 Motivating Application......Page 553
  3 Models and Exploratory Analyses......Page 555
  4 Stochastic EM Algorithm......Page 557
  5 Analysis Results......Page 559
  6 Discussion......Page 562
  References......Page 564
  1 WAFOM and Its Background......Page 566
   2.1 Geometry of Weight and Enumeration......Page 568
   2.2 Combinatorial Inequalities on Volumes of Spheres......Page 570
   2.3 Bounding WAFOM by the Minimum Weight......Page 571
   2.4 Existence of Large Minimum-Weight Point Sets by Probabilistic Argument......Page 573
  References......Page 575
  1 Introduction......Page 577
  2 ANOVA Decomposition and Effective Dimension......Page 579
  3 Convex Piecewise Linear Functions......Page 581
  4 ANOVA Decomposition of Convex Piecewise Linear Functions......Page 583
  5 Generic Smoothness in the Normal Case......Page 588
  6 Dimension Reduction of Piecewise Linear Convex Functions......Page 589
  References......Page 590
  1 Introduction and Results......Page 593
  2 Markov Chains and an Error Bound......Page 597
  3 Densities with Additional Structure......Page 599
  4 Hit-and-Run Algorithm......Page 602
  5 Main Results......Page 605
  References......Page 607
  1 Introduction......Page 609
   2.1 Abstract Saddle Point Problems......Page 610
   2.2 Parametric Operator Families......Page 611
   2.4 Spatial Regularity of Solutions......Page 614
   2.5 Discretization......Page 615
  3 QMC Integration......Page 616
   3.1 Finite Dimensional Setting......Page 617
   3.2 Dimensional Truncation......Page 620
  4 Analysis of QMC and Galerkin Disretization......Page 621
  References......Page 624
  1 Introduction......Page 626
  2 Background on Lattice Rules and the Function Space Setting......Page 628
  3 The Integrand for the Likelihood Problem......Page 630
  4 Bounding the Mixed First Partial Derivatives of the Integrand......Page 631
  5 Bounding the Norm of the Integrand for Specific Densities......Page 636
  6 Choosing the Weights......Page 638
  7 Discussion......Page 640
  References......Page 641
  1 Introduction......Page 643
  2 Linear Systems of Stochastic Hyperbolic Conservation Laws......Page 645
   3.1 Monte Carlo Method......Page 648
   3.2 Finite Difference and Finite Volume Methods......Page 649
   3.3 MC-FDM and MC-FVM Schemes......Page 651
   3.4 MLMC-FDM and MLMC-FVM Schemes......Page 652
  4 Acoustic Isotropic Wave Equation as a Linear Hyperbolic System......Page 654
   5.1 Smooth Wave with Uniformly Distributed Coefficient......Page 656
   5.2 Discontinuous Wave with Normally Distributed Coefficient......Page 657
  6 Conclusion......Page 659
  References......Page 660
Conference Participants......Page 661
Index......Page 679