Simulation and the Monte Carlo Method

Reuven Y. Rubinstein, DSc, was Professor Emeritus in the Faculty of Industrial Engineering and Management at Technion-Israel Institute of Technology. He served as a consultant at numerous large-scale organizations, such as IBM, Motorola, and NEC. The author of over 100 articles and six books, Dr. Rubinstein was also the inventor of the popular score-function method in simulation analysis and generic cross-entropy methods for combinatorial optimization and counting.Dirk P. Kroese, PhD, is a Professor of Mathematics and Statistics in the School of Mathematics and Physics of The University of Queensland, Australia. He has published over 100 articles and four books in a wide range of areas in applied probability and statistics, including Monte Carlo methods, cross-entropy, randomized algorithms, tele-traffic c theory, reliability, computational statistics, applied probability, and stochastic modeling.

• Preface xiiiAcknowledgments xvii1 Preliminaries 11.1 Introduction 11.2 Random Experiments 11.3 Conditional Probability and Independence 21.4 Random Variables and Probability Distributions 41.5 Some Important Distributions 51.6 Expectation 61.7 Joint Distributions 71.8 Functions of Random Variables 111.8.1 Linear Transformations 121.8.2 General Transformations 131.9 Transforms 141.10 Jointly Normal Random Variables 151.11 Limit Theorems 161.12 Poisson Processes 171.13 Markov Processes 191.13.1 Markov Chains 191.13.2 Classification of States 211.13.3 Limiting Behavior 221.13.4 Reversibility 241.13.5 Markov Jump Processes 251.14 Gaussian Processes 271.15 Information 281.15.1 Shannon Entropy 291.15.2 Kullback–Leibler Cross-Entropy 311.15.3 Maximum Likelihood Estimator and Score Function 321.15.4 Fisher Information 331.16 Convex Optimization and Duality 341.16.1 Lagrangian Method 351.16.2 Duality 37Problems 41References 462 Random Number, Random Variable, and Stochastic Process Generation 492.1 Introduction 492.2 Random Number Generation 492.2.1 Multiple Recursive Generators 512.2.2 Modulo 2 Linear Generators 522.3 Random Variable Generation 552.3.1 Inverse-Transform Method 552.3.2 Alias Method 572.3.3 Composition Method 582.3.4 Acceptance–Rejection Method 592.4 Generating from Commonly Used Distributions 622.4.1 Generating Continuous Random Variables 622.4.2 Generating Discrete Random Variables 672.5 Random Vector Generation 702.5.1 Vector Acceptance–Rejection Method 712.5.2 Generating Variables from a Multinormal Distribution 722.5.3 Generating Uniform Random Vectors over a Simplex 732.5.4 Generating Random Vectors Uniformly Distributed over a Unit Hyperball and Hypersphere 742.5.5 Generating Random Vectors Uniformly Distributed inside a Hyperellipsoid 752.6 Generating Poisson Processes 752.7 Generating Markov Chains and Markov Jump Processes 772.7.1 Random Walk on a Graph 782.7.2 Generating Markov Jump Processes 792.8 Generating Gaussian Processes 802.9 Generating Diffusion Processes 812.10 Generating Random Permutations 83Problems 85References 893 Simulation of Discrete-Event Systems 913.1 Introduction 913.2 Simulation Models 923.2.1 Classification of Simulation Models 943.3 Simulation Clock and Event List for DEDS 953.4 Discrete-Event Simulation 973.4.1 Tandem Queue 973.4.2 Repairman Problem 101Problems 103References 1064 Statistical Analysis of Discrete-Event Systems 1074.1 Introduction 1074.2 Estimators and Confidence Intervals 1084.3 Static Simulation Models 1104.4 Dynamic Simulation Models 1124.4.1 Finite-Horizon Simulation 1144.4.2 Steady-State Simulation 1144.5 Bootstrap Method 126Problems 127References 1305 Controlling the Variance 1335.1 Introduction 1335.2 Common and Antithetic Random Variables 1345.3 Control Variables 1375.4 Conditional Monte Carlo 1395.4.1 Variance Reduction for Reliability Models 1415.5 Stratified Sampling 1445.6 Multilevel Monte Carlo 1465.7 Importance Sampling 1495.7.1 Weighted Samples 1495.7.2 Variance Minimization Method 1505.7.3 Cross-Entropy Method 1545.8 Sequential Importance Sampling 1595.9 Sequential Importance Resampling 1655.10 Nonlinear Filtering for Hidden Markov Models 1675.11 Transform Likelihood Ratio Method 1715.12 Preventing the Degeneracy of Importance Sampling 174Problems 179References 1846 Markov Chain Monte Carlo 1876.1 Introduction 1876.2 Metropolis–Hastings Algorithm 1886.3 Hit-and-Run Sampler 1936.4 Gibbs Sampler 1946.5 Ising and Potts Models 1976.5.1 Ising Model 1976.5.2 Potts Model 1986.6 Bayesian Statistics 2006.7 Other Markov Samplers 2026.7.1 Slice Sampler 2046.7.2 Reversible Jump Sampler 2056.8 Simulated Annealing 2086.9 Perfect Sampling 212Problems 214References 2197 Sensitivity Analysis and Monte Carlo Optimization 2217.1 Introduction 2217.2 Score Function Method for Sensitivity Analysis of DESS 2247.3 Simulation-Based Optimization of DESS 2317.3.1 Stochastic Approximation 2327.3.2 Stochastic Counterpart Method 2377.4 Sensitivity Analysis of DEDS 246Problems 252References 2558 Cross-Entropy Method 2578.1 Introduction 2578.2 Estimation of Rare-Event Probabilities 2588.2.1 Root-Finding Problem 2678.2.2 Screening Method for Rare Events 2688.2.3 CE Method Combined with Sampling from the Zero-Variance Distribution 2718.3 CE Method for Optimization 2728.4 Max-Cut Problem 2768.5 Partition Problem 2828.5.1 Empirical Computational Complexity 2838.6 Traveling Salesman Problem 2838.6.1 Incomplete Graphs 2888.6.2 Node Placement 2898.6.3 Case Studies 2908.7 Continuous Optimization 2918.8 Noisy Optimization 2928.9 MinxEnt Method 294Problems 298References 3039 Splitting Method 3079.1 Introduction 3079.2 Counting Self-Avoiding Walks via Splitting 3089.3 Splitting with a Fixed Splitting Factor 3109.4 Splitting with a Fixed Effort 3139.5 Generalized Splitting 3149.6 Adaptive Splitting 3189.7 Application of Splitting to Network Reliability 3219.8 Applications to Counting 3229.9 Case Studies for Counting with Splitting 3259.9.1 Satisfiability (SAT) Problem 3259.9.2 Independent Sets 3309.9.3 Permanent and Counting Perfect Matchings 3329.9.4 Binary Contingency Tables 3349.9.5 Vertex Coloring 3369.10 Splitting as a Sampling Method 3379.11 Splitting for Optimization 3409.11.1 Continuous Optimization 343Problems 344References 34810 Stochastic Enumeration Method 35110.1 Introduction 35110.2 Tree Search and Tree Counting 35210.3 Knuth’s Algorithm for Estimating the Cost of a Tree 35510.4 Stochastic Enumeration 35710.4.1 Combining SE with Oracles 35910.5 Application of SE to Counting 36010.5.1 Counting the Number of Paths in a Network 36010.5.2 Counting SATs 36310.5.3 Counting the Number of Perfect Matchings in a Bipartite Graph 36610.6 Application of SE to Network Reliability 36810.6.1 Numerical Results 370Problems 373References 375Appendix 377A.1 Cholesky Square Root Method 377A.2 Exact Sampling from a Conditional Bernoulli Distribution 378A.3 Exponential Families 379A.4 Sensitivity Analysis 382A.4.1 Convexity Results 383A.4.2 Monotonicity Results 384A.5 A Simple CE Algorithm for Optimizing the Peaks Function 385A.6 Discrete-Time Kalman Filter 385A.7 Bernoulli Disruption Problem 387A.8 Complexity 389A.8.1 Complexity of Rare-Event Algorithms 389A.8.2 Complexity of Randomized Algorithms: FPRAS and FPAUS 390A.8.3 SATs in CNF 394A.8.4 Complexity of Stochastic Programming Problems 395Problems 402References 403Abbreviations and Acronyms 405List of Symbols 407Index 409