Advances in Modeling and Simulation: Festschrift for Pierre L'Ecuyer

Description

This book celebrates the career of Pierre L’Ecuyer on the occasion of his 70th birthday. Pierre has made significant contributions to the fields of simulation, modeling, and operations research over the last 40 years. This book contains 20 chapters written by collaborators and experts in the field who, by sharing their latest results, want to recognize the lasting impact of Pierre’s work in their research area. The breadth of the topics covered reflects the remarkable versatility of Pierre's contributions, from deep theoretical results to practical and industry-ready applications. The Festschrift features article from the domains of Monte Carlo and quasi-Monte Carlo methods, Markov chains, sampling and low discrepancy sequences, simulation, rare events, graphics, finance, machine learning, stochastic processes, and tractability. Preface Acknowledgements Biography Contents Monte Carlo Methods for Pricing American Options 1 Introduction 2 American Option Pricing 3 Binomial Tree Method 4 Dynamic Programming Approach 4.1 Regression Methods 4.2 Malliavin Calculus 5 Control Variates 6 Numerical Experiments 7 Conclusion References Remarks on Lévy Process Simulation 1 Introduction 2 Lévy Processes 3 Main Examples 4 The ε–Algorithm 5 Using Complete Monotonicity Structure 6 Numerical Examples 7 Exact Simulation of X(h) and other Methods 8 Maxima, Minima and Other Path Functionals References Exact Sampling for the Maximum of Infinite Memory Gaussian Processes 1 Introduction 2 Basic Strategy 2.1 Milestone Events 2.2 Main Algorithm 3 Intermediate Steps in Algorithm 2 4 Analysis of Algorithm 2 4.1 Output Analysis 4.2 Complexity Analysis 5 Numerical Experiments 6 Conclusion References Truncated Multivariate Student Computations via Exponential Tilting 1 Introduction 2 Review of the Sequentially Tilted Proposal Density 3 Asymptotic Efficiency of the IS Estimator 4 Application to Constrained Linear Regression 5 Tobit Model Application 6 Application to ``Bayesian'' Splines for Non-negative Functions 7 The Reject-Regenerate Sampler 7.1 Nummelin Splitting of Transition Kernel 7.2 Rare-Event Robustness 8 Concluding Remarks References Quasi-Monte Carlo Methods in Portfolio Selection with Many Constraints 1 Introduction 2 Classical Portfolio Selection in a Nutshell 3 Portfolio Optimization with Many Constraints 4 Approximation of the Opportunity Set by Naïve Monte Carlo, and by Exponential Monte Carlo 5 Approximation of the Opportunity Set with Exponential QMC 6 Approximating the Market Portfolio with MC, Exponential MC, and Exponential QMC 7 Approximating the Whole OS with MC, Exponential MC, and Exponential QMC 8 How to Calculate the Dispersion of a Sample Set in an OS? 9 Some Simulation Results 10 Conclusions, Outlook, and Further Practical Problem References Geometric-Moment Contraction of G/G/1 Waiting Times 1 Introduction 2 Main Results 3 Monte Carlo Results 3.1 M/M/1 Queue 3.2 M/G/1 Queues 4 Conclusions References Tractability of Approximation in the Weighted Korobov Space in the Worst-Case Setting 1 Introduction 2 Basic Definitions 2.1 Function Space Setting 2.2 Approximation in script upper H Subscript d comma alpha comma bold italic gammamathcalHd,α,γ 2.3 The Worst-Case Setting 2.4 Useful Relations 2.5 Relations to the Average-Case Setting 2.6 Notions of Tractability 3 The Results for normal upper A normal upper P normal upper P Subscript 2APP2 4 The Results for normal upper A normal upper P normal upper P Subscript normal infinityAPPinfty 5 Overview and Formulation of Open Problems 5.1 Open Problems References Rare-Event Simulation via Neural Networks 1 Introduction 1.1 Background 2 Rare-Event Deep Learning 2.1 Networks and Loss Functions 2.2 Kernel Density Estimation 2.3 Training Procedure 2.4 Rare-Event Distribution 3 Experimental Results 3.1 Learning Normal Distributions 3.2 Normal Distribution Rare-Events 3.3 Learning Sum of Exponential Distributions 4 Conclusions and Further Research References Preintegration is Not Smoothing When Monotonicity Fails 1 Introduction 1.1 Related Work 1.2 The Problem 1.3 Informative Examples 1.4 Outline of This Paper 2 Smoothness Theorems in dd Dimensions 3 A High-Dimensional Example 4 Conclusion References Combined Derivative Estimators 1 Introduction 2 Derivative Estimation 2.1 Background 2.2 Combined Estimators 2.3 Second Derivatives 2.4 Finite Difference Estimators and IPA 2.5 IPA and Randomized Score Functions 2.6 LRM Singularities 2.7 Generalized Likelihood Ratio Method 3 A Barrier Option Example 3.1 The Option Pricing Setting 3.2 The Barrier Option 3.3 A Combined IPA-LRM Estimator of Wang et al. ch10wang 3.4 GLR as a Combined IPA-LRM Estimator 4 Approaching Continuous Time: Averaging Low-Rank GLR Estimators 4.1 Approximating Continuous-Time Sensitivities 4.2 Averaging GLR Estimators 5 Concluding Remarks References A Central Limit Theorem For Empirical Quantiles in the Markov Chain Setting 1 Introduction 2 A Quantile Central Limit Theorem 3 A Uniform CLT for 1-Dependent Sequences 4 A Quantile Central Limit Theorem for Harris Processes 5 The Validity of Non-overlapping Batch-Means Estimation 6 Sufficient Conditions References Simulation of Markov Chains with Continuous State Space by Using Simple Stratified and Sudoku Latin Square Sampling 1 Introduction 2 Markov Chain Simulation with Stratified Sampling 2.1 Classical Monte Carlo 2.2 Simple Stratified Sampling 2.3 Sudoku Latin Square Sampling 3 Variance Bounds 3.1 Classical Monte Carlo 3.2 Simple Stratified Sampling 3.3 Sudoku Latin Square Sampling 4 Numerical Experiments 4.1 An Autoregressive Process 4.2 A European Put Option 4.3 Diffusion 5 Conclusions References Quasi-Random Sampling with Black Box or Acceptance-Rejection Inputs 1 Introduction 2 Methods for the Black Box Setting 2.1 Methods Based on the Empirical Quantile Function 2.2 Methods Based on a Generalized Pareto Approximation in the Tail 3 Combining AR with RQMC 4 Application: Basket Option Pricing 5 Conclusion References A Generalized Transformed Density Rejection Algorithm 1 Introduction 2 Transformed Density Rejection with Inflection Points 3 Determine Signs of Second Derivatives 3.1 Initial Intervals 3.2 Splitting Intervals 4 The Algorithm 5 Applications 5.1 Generalized Hyperbolic Distribution 5.2 Truncated Distributions 5.3 Watson Distributions 6 Conclusions References Fast Automatic Bayesian Cubature Using Sobol' Sampling 1 Introduction 2 Bayesian Cubature 3 Digital Nets and Walsh Kernels 3.1 Digital Sequences 3.2 Covariance Kernels Constructed Via Walsh Functions 3.3 Eigenvector-Eigenvalue Decomposition of the Gram Matrix 4 Numerical Experiments 4.1 Multivariate Gaussian Probability 4.2 Keister's Example 4.3 Asian Option Pricing 4.4 Discussion 5 Conclusion and Future Work References Rendering Along the Hilbert Curve 1 Introduction 2 Visual Error in Image Synthesis 3 Enumerating Pixels Along the Hilbert Curve 3.1 Correlation in Space-Filling Curves 3.2 Blue-Noise Dithered Sampling 4 Progressive Image Synthesis 4.1 Deterministic Cranley-Patterson Rotation 4.2 Randomization 4.3 Contiguous Segments of one Low Discrepancy Sequence 4.4 Partitioning one Low Discrepancy Sequence 5 Results and Discussion 6 Conclusion References Array-RQMC to Speed up the Simulation for Estimating the Hitting-Time Distribution to a Rare Set of a Regenerative System 1 Introduction 2 Regenerative-Simulation-Based Estimators of the Distribution of the Hitting Time to a Rarely Visited Set 2.1 Assumptions and Notations 2.2 Exponential Limit 2.3 Exponential Estimators with Monte Carlo (MC) 2.4 Convolution Estimators with Monte Carlo 3 Array-RQMC Implementation of Regenerative-Simulation-Based Estimators of Quantiles 3.1 RQMC and Array-RQMC 3.2 Array-RQMC Exponential and Convolution Estimators 4 Numerical Illustration of the Gain on the Simulation of an M/M/1 Queue 5 Conclusions References Foundations of Ranking & Selection for Simulation Optimization 1 Introduction 2 Set Up 3 The Normal Means Case 3.1 The Indifference-Zone (IZ) Formulation 3.2 R&S Based on ``Statistical Learning'' 3.3 A Convergence-Rate Perspective 3.4 Doing Better Than ``Rate Optimal'' 3.5 Common Random Numbers 3.6 ``Good Selection'' 3.7 Unknown Variances 3.8 A Note on Asymptotic Analysis 4 Parallel R&S 4.1 New Measures of Efficiency 4.2 New Objectives 4.3 Parting Thoughts 5 Other Formulations 6 Multi-armed Bandits References Where are the Logs? 1 Introduction 2 Background 3 Proof of the Lower Bound 4 Discrepancy and the Case of d equals 1d=1 5 Empirical Investigations for d equals 2d=2 6 Very Large mm for Sobol' Nets 7 Discussion References Network Reliability, Performability Metrics, Rare Events and Standard Monte Carlo 1 Introduction 2 Performability Metrics and Resilience 2.1 The Resilience Metric 2.2 Some Properties of Resilience 3 Using Standard Monte Carlo for Resilience-Based Analysis 3.1 The Standard Estimator 3.2 The Standard Estimator Efficiently Implemented in the Rare Event Case 3.3 Estimating the Resilience 3.4 Improving Algorithm B 3.5 Sensitivity Analysis 4 Examples and Discussions 5 Conclusions References