<p><strong>Stochastic Simulation  Algorithms and Analysis</strong></p><p></p><p> </p><p> </p><p>Authors<br/>Søren Asmussen Peter W. Glynn<br/>Department of Theoretical Statistics Department of Management Science<br/>Department of Mathematical Sciences and Engineering<br/>Aarhus University Institute for Computational and<br/>Ny Munkegade Mathematical Engineering<br/>DK–8000 Aarhus C, Denmark Stanford University<br/><a href="mailto:asmus@imf.au.dk">asmus@imf.au.dk</a> Stanford, CA 94305–4026<br/><a href="mailto:glynn@stanford.edu">glynn@stanford.edu</a></p><p>Stochastic Simulation  Algorithms and Analysis</p><p>Preface v<br/>Notation xii<br/>I What This Book Is About 1<br/>1 An Illustrative Example: The Single-Server Queue . . . 1<br/>2 TheMonte CarloMethod . . . . . . . . . . . . . . . . 5<br/>3 Second Example: Option Pricing . . . . . . . . . . . . . 6<br/>4 Issues Arising in the Monte Carlo Context . . . . . . . 9<br/>5 Further Examples . . . . . . . . . . . . . . . . . . . . . 13<br/>6 Introductory Exercises . . . . . . . . . . . . . . . . . . 25<br/>Part A: General Methods and Algorithms 29<br/>II Generating Random Objects 30<br/>1 Uniform RandomVariables . . . . . . . . . . . . . . . . 30<br/>2 NonuniformRandomVariables . . . . . . . . . . . . . . 36<br/>3 Multivariate Random Variables . . . . . . . . . . . . . 49<br/>4 Simple Stochastic Processes . . . . . . . . . . . . . . . 59<br/>5 Further Selected Random Objects . . . . . . . . . . . . 62<br/>6 Discrete-Event Systems and GSMPs . . . . . . . . . . 65<br/>III Output Analysis 68<br/>1 Normal Confidence Intervals . . . . . . . . . . . . . . . 68<br/>Contents ix<br/>2 Two-Stage and Sequential Procedures . . . . . . . . . . 71<br/>3 Computing Smooth Functions of Expectations . . . . . 73<br/>4 Computing Roots of Equations Defined by Expectations 77<br/>5 Sectioning, Jackknifing, and Bootstrapping . . . . . . . 80<br/>6 Variance/Bias Trade-Off Issues . . . . . . . . . . . . . 86<br/>7 Multivariate Output Analysis . . . . . . . . . . . . . . 88<br/>8 Small-Sample Theory . . . . . . . . . . . . . . . . . . . 90<br/>9 Simulations Driven by Empirical Distributions . . . . . 91<br/>10 The Simulation Budget . . . . . . . . . . . . . . . . . . 93<br/>IV Steady-State Simulation 96<br/>1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . 96<br/>2 Formulas for the Bias and Variance . . . . . . . . . . . 102<br/>3 Variance Estimation for Stationary Processes . . . . . 104<br/>4 The RegenerativeMethod . . . . . . . . . . . . . . . . 105<br/>5 TheMethod of BatchMeans . . . . . . . . . . . . . . . 109<br/>6 Further Refinements . . . . . . . . . . . . . . . . . . . 110<br/>7 Duality Representations . . . . . . . . . . . . . . . . . 118<br/>8 Perfect Sampling . . . . . . . . . . . . . . . . . . . . . 120<br/>V Variance-Reduction Methods 126<br/>1 Importance Sampling . . . . . . . . . . . . . . . . . . . 127<br/>2 ControlVariates . . . . . . . . . . . . . . . . . . . . . . 138<br/>3 Antithetic Sampling . . . . . . . . . . . . . . . . . . . . 144<br/>4 ConditionalMonte Carlo . . . . . . . . . . . . . . . . . 145<br/>5 Splitting . . . . . . . . . . . . . . . . . . . . . . . . . . 147<br/>6 Common RandomNumbers . . . . . . . . . . . . . . . 149<br/>7 Stratification . . . . . . . . . . . . . . . . . . . . . . . . 150<br/>8 Indirect Estimation . . . . . . . . . . . . . . . . . . . . 155<br/>VI Rare-Event Simulation 158<br/>1 Efficiency Issues . . . . . . . . . . . . . . . . . . . . . . 158<br/>2 Examples of Efficient Algorithms: Light Tails . . . . . 163<br/>3 Examples of Efficient Algorithms: Heavy Tails . . . . . 173<br/>4 Tail Estimation . . . . . . . . . . . . . . . . . . . . . . 178<br/>5 Conditioned Limit Theorems . . . . . . . . . . . . . . . 183<br/>6 Large-Deviations or Optimal-Path Approach . . . . . . 187<br/>7 Markov Chains and the h-Transform . . . . . . . . . . 190<br/>8 Adaptive Importance Sampling via the Cross-Entropy<br/>Method . . . . . . . . . . . . . . . . . . . . . . . . . . . 195<br/>9 Multilevel Splitting . . . . . . . . . . . . . . . . . . . . 201<br/>VII Derivative Estimation 206<br/>1 Finite Differences . . . . . . . . . . . . . . . . . . . . . 209<br/>2 Infinitesimal Perturbation Analysis . . . . . . . . . . . 214<br/>x Contents<br/>3 The Likelihood Ratio Method: Basic Theory . . . . . . 220<br/>4 The Likelihood Ratio Method: Stochastic Processes . . 224<br/>5 Examples and SpecialMethods . . . . . . . . . . . . . 231<br/>VIII Stochastic Optimization 242<br/>1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . 242<br/>2 Stochastic Approximation Algorithms . . . . . . . . . . 243<br/>3 ConvergenceAnalysis . . . . . . . . . . . . . . . . . . . 245<br/>4 Polyak–RuppertAveraging . . . . . . . . . . . . . . . . 250<br/>5 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 253<br/>Part B: Algorithms for Special Models 259<br/>IX Numerical Integration 260<br/>1 Numerical Integration in One Dimension . . . . . . . . 260<br/>2 Numerical Integration in Higher Dimensions . . . . . . 263<br/>3 Quasi-Monte Carlo Integration . . . . . . . . . . . . . . 265<br/>X Stochastic Differential Equations 274<br/>1 Generalities about Stochastic Process Simulation . . . 274<br/>2 BrownianMotion . . . . . . . . . . . . . . . . . . . . . 276<br/>3 The Euler Scheme for SDEs . . . . . . . . . . . . . . . 280<br/>4 The Milstein and Other Higher-Order Schemes . . . . . 287<br/>5 ConvergenceOrders for SDEs: Proofs . . . . . . . . . . 292<br/>6 Approximate Error Distributions for SDEs . . . . . . . 298<br/>7 Multidimensional SDEs . . . . . . . . . . . . . . . . . . 300<br/>8 Reflected Diffusions . . . . . . . . . . . . . . . . . . . . 301<br/>XI Gaussian Processes 306<br/>1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . 306<br/>2 Cholesky Factorization. Prediction . . . . . . . . . . . 311<br/>3 Circulant-Embeddings . . . . . . . . . . . . . . . . . . 314<br/>4 Spectral Simulation. FFT . . . . . . . . . . . . . . . . 316<br/>5 Further Algorithms . . . . . . . . . . . . . . . . . . . . 320<br/>6 Fractional BrownianMotion . . . . . . . . . . . . . . . 321<br/>XII Lévy Processes 325<br/>1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . 325<br/>2 First Remarks on Simulation . . . . . . . . . . . . . . . 331<br/>3 Dealing with the Small Jumps . . . . . . . . . . . . . . 334<br/>4 Series Representations . . . . . . . . . . . . . . . . . . 338<br/>5 Subordination . . . . . . . . . . . . . . . . . . . . . . . 343<br/>6 Variance Reduction . . . . . . . . . . . . . . . . . . . . 344<br/>7 TheMultidimensional Case . . . . . . . . . . . . . . . 346<br/>8 Lévy-Driven SDEs . . . . . . . . . . . . . . . . . . . . . 348<br/>Contents xi<br/>XIII Markov Chain Monte Carlo Methods 350<br/>1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . 350<br/>2 Application Areas . . . . . . . . . . . . . . . . . . . . . 352<br/>3 The Metropolis–Hastings Algorithm . . . . . . . . . . . 361<br/>4 Special Samplers . . . . . . . . . . . . . . . . . . . . . 367<br/>5 The Gibbs Sampler . . . . . . . . . . . . . . . . . . . . 375<br/>XIV Selected Topics and Extended Examples 381<br/>1 Randomized Algorithms for Deterministic Optimization 381<br/>2 Resampling and Particle Filtering . . . . . . . . . . . . 385<br/>3 Counting andMeasuring . . . . . . . . . . . . . . . . . 391<br/>4 MCMC for the Ising Model and Square Ice . . . . . . . 395<br/>5 Exponential Change of Measure in Markov-Modulated<br/>Models . . . . . . . . . . . . . . . . . . . . . . . . . . . 403<br/>6 Further Examples of Change of Measure . . . . . . . . 407<br/>7 Black-BoxAlgorithms . . . . . . . . . . . . . . . . . . . 416<br/>8 Perfect Sampling of Regenerative Processes . . . . . . . 420<br/>9 Parallel Simulation . . . . . . . . . . . . . . . . . . . . 424<br/>10 Branching Processes . . . . . . . . . . . . . . . . . . . 426<br/>11 Importance Sampling for Portfolio VaR . . . . . . . . . 432<br/>12 Importance Sampling for Dependability Models . . . . 435<br/>13 Special Algorithms for the GI/G/1 Queue . . . . . . . 437<br/>Appendix 442<br/>A1 Standard Distributions . . . . . . . . . . . . . . . . . . 442<br/>A2 Some Central Limit Theory . . . . . . . . . . . . . . . 444<br/>A3 FFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444<br/>A4 The EMAlgorithm . . . . . . . . . . . . . . . . . . . . 445<br/>A5 Filtering . . . . . . . . . . . . . . . . . . . . . . . . . . 447<br/>A6 Itô’s Formula . . . . . . . . . . . . . . . . . . . . . . . 448<br/>A7 Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . 450<br/>A8 Integral Formulas . . . . . . . . . . . . . . . . . . . . . 450<br/>Bibliography 452<br/>Web Links 469<br/>Index 471<br/></p>