Monte Carlo and Quasi-Monte Carlo Methods 2010

Cover......Page 1
Monte Carlo and Quasi-Monte Carlo Methods 2010\r......Page 4
Preface\r......Page 6
Contents\r......Page 10
Randomized Algorithms for Hamiltonian Simulation......Page 14
2.1 Statistical Inference in Finite State CTMC Models......Page 16
2.2 Applications in Genetics......Page 17
3 Previous Algorithms......Page 19
4.1 The Basic Idea......Page 21
4.2 Initialization When the Endpoints Are Equal......Page 22
4.3 Initialization When the Endpoints Are Different......Page 23
4.4 Recursion and Termination......Page 24
5 Numerical Examples......Page 25
5.1 Stratification......Page 26
5.2 Importance Sampling......Page 27
5.3 Quasi Monte Carlo......Page 28
6 Conclusions and Extensions......Page 29
References......Page 32
1 Introduction......Page 34
2 A Large Discrepancy Example......Page 36
3 Monte Carlo, Quasi Monte Carlo, or Not......Page 39
4 The Classical Problem......Page 41
4.1 Two Dimensions......Page 42
4.2 Higher Dimensions......Page 46
4.3 Good Distributions......Page 47
5 Fourier–Walsh Analysis......Page 49
6 Further Reading......Page 50
References......Page 51
1 Introduction......Page 53
1.2 Relation to Numerical Integration......Page 54
1.3.1 Asymptotic Bounds......Page 57
1.3.2 Pre-Asymptotic Bounds......Page 58
1.4 Construction of Small Discrepancy Samples......Page 59
1.5 Calculating the Star Discrepancy......Page 60
2.1 Basic Definitions......Page 63
2.2.1 Cells of an Equidistant Grid......Page 64
2.2.2 Cells of a Non-equidistant Grid......Page 65
2.2.3 A Layer Construction......Page 66
2.2.4 An Essentially Optimal Construction......Page 67
2.3 Bounds for the Bracketing Number......Page 70
3.1 Approximation of the Star Discrepancy......Page 71
3.2 Pre-Asymptotic Bounds via Randomization......Page 72
3.2.1 Point Sets in the d-Dimensional Unit Cube......Page 73
3.2.2 Infinite Dimensional Infinite Sequences......Page 76
3.3 Small Discrepancy Samples via Derandomization......Page 78
3.3.1 Random Experiment......Page 79
3.3.2 Derandomized Construction......Page 80
3.3.3 A Component-by-Component Derandomization......Page 82
4 Conclusion and Open Problems......Page 83
References......Page 85
1 Introduction......Page 89
2 Boundary Sensitivity......Page 95
3 Discretization Error......Page 98
4 Boundary Correction for Simulating Stopped Diffusion Process......Page 100
References......Page 101
1 Introduction and Preliminaries......Page 104
2 Approximation of the Embedding J:Wpr(Q)→Wqs(Q) with s≥0......Page 108
3 Integration Over Lipschitz Domains......Page 116
4 Approximation of Embeddings into Spaces with Negative Degree of Smoothness......Page 120
5 Approximation of J:Wpr(Q)→Wsq*(Q)* – The Algorithm......Page 126
6 Indefinite Integration and Approximation in Spaces of Functions with Dominating Mixed Derivatives......Page 130
7 A Generalization of Indefinite Integration and Tractability of Discrepancy......Page 136
References......Page 140
1 Introduction: Monte Carlo and Randomized Quasi-Monte Carlo......Page 142
2 Randomly-Shifted Lattice Rules......Page 144
3 Adaptive Search for Lattices that Avoid the Large Fourier Coefficients......Page 146
4 ANOVA Decomposition and Projection-Dependent Weights......Page 149
5 Further Heuristics for Choosing the Weights......Page 151
6 Figures of Merit Based on the Spectral Test......Page 153
8 Experimental Methodology......Page 155
9 An Indicator Function......Page 157
10 Example: A Stochastic Activity Network......Page 158
11 Example: Asian Call Option......Page 160
12 Conclusion......Page 165
References......Page 166
1 Introduction......Page 168
1.1 Broad Conclusions, Comparisons, Restrictions and the Value of Exactness......Page 169
2.1 The Exact Algorithm......Page 170
2.2 The Discretisation Schemes......Page 173
3 Some Uni-dimensional Simulation Studies......Page 174
3.1 The Case of EA1......Page 176
3.2 The Case of EA3......Page 184
4 The Multi-dimensional Setting......Page 187
Appendix......Page 189
References......Page 193
1 Introduction......Page 195
2 Polynomial Lattice Point Sets......Page 198
3 The Dual Net......Page 200
4 Quality Measures and Existence Results......Page 201
5 CBC Construction of Polynomial Lattice Point Sets......Page 202
6 Integration of Walsh Series......Page 204
7 Extensible Polynomial Lattice Point Sets......Page 206
8 Integration in Sobolev Spaces......Page 207
9 Higher Order Polynomial Lattice Rules......Page 209
10 Summary and Further Comments......Page 211
References......Page 213
1 Introduction......Page 217
2 Basic Concepts......Page 219
2.1 Quasi-reproducing Kernel Hilbert Spaces......Page 220
2.2 Integration Problem......Page 222
2.3 Function Approximation Problem......Page 223
2.4 Algorithms......Page 224
2.5 Complexity and Tractability......Page 226
3 Results for Integration......Page 227
4.1 Unrestricted Linear Information......Page 229
4.2 Standard Information......Page 231
4.3 L2-Approximation......Page 232
4.4 Randomized Setting......Page 233
References......Page 236
1 Introduction......Page 238
2 Embedding by a Tensor Product Function Space......Page 241
3 Distinguishing Dual Lattice Points......Page 243
4 A Modification of the CKN Weighted-Degree Algorithm......Page 248
5 An Improvement on p......Page 251
6 Conclusion and Future Work......Page 254
References......Page 255
1 Introduction......Page 257
2.1 The Function Space......Page 258
2.2 Sampling Regimes, Cost, and Worst-Case Error......Page 259
3 Results on Fixed Subspace Sampling......Page 262
4 Results on Variable Subspace Sampling......Page 263
References......Page 265
1 Introduction......Page 266
2 The Generator, Its Initialization and Period......Page 270
3 Statistical Testing and Speed of the Generator......Page 271
4 Geometric and Statistical Properties for Matrices with Unitary Determinant......Page 272
5 Geometric and Statistical Properties for q≠1......Page 276
References......Page 280
1.1 Multilevel Monte Carlo......Page 283
1.2 Monte Carlo Greeks......Page 284
1.2.2 Likelihood Ratio Method......Page 285
2.1 Pathwise Sensitivities......Page 286
2.2 Pathwise Sensitivities and Conditional Expectations......Page 287
2.3 Split Pathwise Sensitivities......Page 290
2.4 Vibrato Monte Carlo......Page 291
3 European Digital Call......Page 293
4 European Lookback Call......Page 294
5 European Barrier Call......Page 295
5.2 Conditional Expectations......Page 296
References......Page 297
1 Introduction......Page 298
2 Basic Integral Equation of the Second Kind......Page 300
2.1 From Master Equation to Basic Integral Equation......Page 301
2.2 Decomposition of the Distribution Density......Page 302
3.1 Majorant Frequency Principle......Page 304
3.2 Weight Algorithms and Parametric Estimators......Page 305
4.1.2 Hard Sphere Interaction......Page 307
4.1.3 Distance Threshold Interaction......Page 308
4.2 Fundamental Diagram......Page 309
4.3 Parametric Analysis......Page 310
References......Page 312
1 Introduction......Page 313
2.1 Completely Uniformly Distributed Sequences......Page 314
2.2 Markov Chain Monte Carlo......Page 315
2.3 QMC in MCMC Results......Page 316
3 New Small LFSR Constructions......Page 317
4 Antithetic and Round Trip Sampling......Page 320
5 Empirical Results......Page 322
6 Conclusions......Page 325
References......Page 327
1 Introduction......Page 329
2 Assumptions and Background......Page 333
3 Convergence and Tractability for Λall and Λstd......Page 336
4 Comparison of the Worst and Average Case Settings......Page 339
References......Page 342
1 Introduction......Page 344
2.1 Generalized Halton Sequences......Page 346
2.2 (t,s)-Sequences......Page 347
3 Atanassov\'s Method Applied to (t,s)-Sequences......Page 348
4 Scrambling Halton Sequences with Matrices......Page 351
4.1 Halton Sequences Scrambled with Lower Triangular Matrices......Page 352
4.2 Scrambling Halton Sequences with Admissible Matrices......Page 355
References......Page 361
1 Introduction......Page 362
2 Subsampling Bootstrap Methods......Page 364
2.1 Expectations......Page 365
2.2 Quantiles......Page 366
3 Toy Example......Page 367
4 A Realistic Example......Page 369
References......Page 370
1 Introduction......Page 372
2.1 Safe Height Approximation......Page 374
2.2 MC and QMC Integration Methods......Page 375
2.3 Some Numerical Tests......Page 377
3 Performance Prediction Results......Page 381
References......Page 382
1 Introduction......Page 384
2 Theoretical Results......Page 385
2.1 The First Approach......Page 386
2.2 The Second Approach......Page 388
3.1 The Case of Estimator (13)......Page 391
3.2 The Case of Estimator (15)......Page 392
3.3 Application to Simulation......Page 393
3.4 Computational Time......Page 394
4 Simulation Results......Page 395
References......Page 397
1 Introduction......Page 398
2 Radical Inversion and Stratification......Page 399
3 Enumerating the Halton Sequence per Stratum......Page 400
4 Enumerating Digital (t,s)-Sequences per Elementary Interval......Page 401
4.2 Sobol\' Sequence......Page 403
5 Consistent Image Synthesis......Page 404
5.1 Enumerating the Sobol\' Sequence in Pixels......Page 405
6 Conclusion......Page 406
References......Page 407
1 Introduction......Page 408
2 Stochastic Correlation Model: Two Dimensional Case......Page 410
2.1 Formal Expansion of The Perturbed Joint Default Probability......Page 411
3 Efficient Importance Sampling for the First Passage Time Problem......Page 413
4 Homogenized Importance Sampling Under Stochastic Correlation......Page 414
5 Conclusion......Page 416
References......Page 417
1 Introduction......Page 418
2 Problem Description......Page 420
3.1 Background......Page 421
3.2 Part I: Averaged Sequential Correlated Sampling (ASCS)......Page 422
3.3 Part II: Contributon Map and Mesh Refinement......Page 424
4 Application: Model Problem Analysis......Page 427
References......Page 432
1 Introduction......Page 434
2 Preliminaries......Page 435
3 The Hybrid Weyl Criterion......Page 437
4 Hybrid Diaphony......Page 444
References......Page 447
1 Introduction......Page 449
2 An Intermediate Bound on the Star Discrepancy......Page 452
3 Calculating W(z,n)......Page 456
4 Component-by-Component Construction......Page 458
5 Numerical Results and Summary......Page 463
References......Page 466
1 Introduction......Page 468
2 Variance Reduction Methods to Exponential Interarrival Times......Page 471
3 Generalized Linear Transformation......Page 475
References......Page 482
1 Introduction......Page 484
2 Parallelization as an Additional Problem Dimension......Page 485
3 Algorithms for Partitioning Low Discrepancy Sequences......Page 486
3.1 Preliminaries on Digits and Digital Radical Inverses......Page 488
3.3 Digital (t,s)-Sequences in Base b......Page 489
3.4 Rank-1 Lattice Sequences......Page 491
4.1 Previous Issues with Leapfrogging......Page 492
4.3 Selecting the Number of Jobs......Page 493
References......Page 494
1 Introduction......Page 496
2 Background on Photon Mapping......Page 498
3 Pointwise Consistent Density Estimation......Page 499
3.2 Choice of the Initial Radius r0......Page 500
4 Consistent Functional Approximation......Page 501
4.1 Algorithm......Page 502
4.3 Deterministic Sampling using Quasi-Monte Carlo Points......Page 503
References......Page 505
1 Introduction......Page 507
2 Value Simulation for Smoluchowski Equation......Page 509
2.1 Modeling of the Time Between Collisions......Page 511
2.2 VMIPN to Estimate the Monomer Concentration......Page 512
2.3 VMIPN to Estimate the Monomer and Dimer Concentration......Page 513
2.4 Direct Method Vs. Value Algorithm......Page 515
3 Results of the Numerical Experiments......Page 516
4 Conclusion......Page 517
References......Page 518
1 Introduction......Page 519
2 Simulation of the Coagulation Equation......Page 520
2.1 The QMC Algorithm......Page 522
2.2 Convergence Analysis......Page 524
3 Modeling of SOD Device......Page 527
References......Page 532
1 Introduction......Page 534
2 Regenerative Simulation......Page 537
3 General Results for Regenerative Estimators......Page 538
3.1 Results for θrreg......Page 539
3.3 Results for nreg-seq......Page 540
4 The Median Trick......Page 542
5 Doeblin Chains......Page 543
5.2 Standard One-Run Average and Exponential Inequality......Page 545
5.4 Remarks on Other Schemes......Page 546
6 A Geometric Drift Condition......Page 547
Appendix......Page 548
References......Page 549
1 Introduction......Page 552
2.1 Generation of Extensible Lattices......Page 554
2.2 Distribution Properties of Extensible Lattices......Page 556
2.3 Construction of Generating Vectors......Page 557
2.4 Numerical Investigations......Page 558
3 Integration of Periodic and Non-periodic Functions......Page 559
3.2 Use of Importance Sampling to Periodicize......Page 560
4 Examples......Page 562
5 Summary and Future Work......Page 564
References......Page 566
1 Introduction......Page 567
2 Occupation Times of a Brownian Bridge......Page 569
3 Pricing Occupation Time Options Under a Jump Diffusion......Page 572
4.1 Exact Simulation of the CEV Process......Page 574
4.2 Simulation of Occupation Times for the CEV Processes......Page 575
4.3 The First Hitting Time Approach......Page 576
5 Numerical Results......Page 577
6 Conclusions......Page 579
References......Page 580
1 Introduction......Page 582
2 Problems from Financial Mathematics......Page 583
2.2 A Digital Asian Call Option......Page 584
3 Quasi-Monte Carlo Point Sets......Page 585
3.1 Randomised QMC......Page 586
3.2 Digital Nets and Sequences......Page 587
3.3 QMC on the Digital Asian Call Option......Page 588
3.4 Low Truncation Dimension......Page 589
4 A New Adaptive Algorithm for Low Truncation Dimension......Page 591
4.1 The Sniffer Function: Detecting Interesting Boxes......Page 593
4.2 Localising Points and Shifted Points......Page 594
5 Numerical Results......Page 597
References......Page 599
1 Methodology......Page 604
2 Computing the Discrepancy......Page 606
2.1 Computing Lower Bounds for Star Discrepancy Using a Genetic Algorithm......Page 608
3 Applications......Page 610
4 Conclusions......Page 612
References......Page 613
1 Introduction......Page 615
2 Approximation Based on Simulation and Regression......Page 617
2.1 Markov Chain Monte Carlo Framework......Page 618
2.2 Variance Reduction by Importance Sampling......Page 619
2.2.1 Designing Importance Sampling Distributions with Polynomial Bases......Page 620
2.2.2 The Simulation Algorithm......Page 622
3.1 Test Example: Gravitational Prospecting......Page 623
4 Special Case: Underdetermined Problems......Page 627
References......Page 628
1.1 Motivation......Page 630
1.2 Classical Lattices......Page 631
1.3 Chebyshev Lattices......Page 632
1.4 Computer Search......Page 633
2.1 Exploiting Symmetry......Page 634
3 Reducing the Point Set Creation Cost......Page 637
4.1 Evaluation of the Basis Function......Page 638
5 Search Results......Page 640
6 Conclusion......Page 643
References......Page 645
1 The Problem......Page 646
4 Proof......Page 648
4.1 First Step: The Finite-Dimensional Case......Page 649
4.2 Second Step: A Lemma......Page 651
4.3 Final Step: Putting Everything Together......Page 654
References......Page 656
1 Introduction......Page 657
2 Moment Matching Compound Poisson Approximations......Page 659
3 The 3-Moment Scheme......Page 661
4 High Order Schemes for One-Dimensional Stable-Like Lévy Processes......Page 668
References......Page 673
1 Introduction......Page 674
2 High-Discrepancy Sequences for Isotropic Integrals......Page 675
3 High-Discrepancy Sequences for Kolmogorov Superposition Integrals......Page 677
4 Software Implementation......Page 679
5 Conclusion......Page 681
References......Page 683
1 Introduction......Page 684
2 A Jump-Adapted Milstein Discretisation......Page 685
3 Multilevel Monte Carlo Method......Page 686
4.1 European Call Option......Page 688
4.2 Lookback Option......Page 689
4.3 Barrier Option......Page 691
5 Path-Dependent Rates......Page 692
5.1 Multilevel Treatment......Page 693
5.1.1 Numerical Results......Page 694
6 Conclusions and Future Work......Page 695
References......Page 696
1 Introduction......Page 698
2 Random Models for Hamiltonian Simulation......Page 699
3 Examples of Randomized Algorithms......Page 702
Appendix......Page 707
References......Page 708
Conference Participants......Page 709
Index......Page 718