Simulation and the Monte Carlo Method

Reuven Y. Rubinstein9780470139011, 0470139013, 0470177942, 9780470177945

This book represents one of the first modern day treatments of Monte Carlo Methods (MCM). Since the publication of the first edition, dramatic changes have taken place in the entire field. This long awaited second edition gives a fully updated and comprehensive account of the major topics in Monte Carlo simulation since the early 1980’s. The book is geared to a broad audience of readers in engineering, the physical and life sciences, statistics, computer science, and mathematics. The authors aim to provide an accessible introduction to modern MCM, focusing on the main concepts, while providing a sound foundation for problem solving. For this reason, most ideas are introduced and explained by way of concrete examples, algorithms, and practical experiments.

---

Table of contents :
SIMULATION AND THE MONTE CARLO METHOD……Page 4
CONTENTS……Page 10
Preface……Page 16
Acknowledgments……Page 20
1.1 Random Experiments……Page 22
1.2 Conditional Probability and Independence……Page 23
1.3 Random Variables and Probability Distributions……Page 24
1.4 Some Important Distributions……Page 26
1.5 Expectation……Page 27
1.6 Joint Distributions……Page 28
1.7 Functions of Random Variables……Page 31
1.7.1 Linear Transformations……Page 32
1.8 Transforms……Page 34
1.9 Jointly Normal Random Variables……Page 35
1.10 Limit Theorems……Page 36
1.11 Poisson Processes……Page 37
1.12 Markov Processes……Page 39
1.12.1 Markov Chains……Page 40
1.12.2 Classification of States……Page 41
1.12.3 Limiting Behavior……Page 42
1.12.4 Reversibility……Page 44
1.12.5 Markov Jump Processes……Page 45
1.13 Efficiency of Estimators……Page 47
1.14 Information……Page 49
1.14.1 Shannon Entropy……Page 50
1.14.2 Kullback–Leibler Cross-Entropy……Page 52
1.14.3 The Maximum Likelihood Estimator and the Score Function……Page 53
1.14.4 Fisher Information……Page 54
1.15 Convex Optimization and Duality……Page 55
1.15.1 Lagrangian Method……Page 57
1.15.2 Duality……Page 58
Problems……Page 62
References……Page 67
2.2 Random Number Generation……Page 70
2.3.1 Inverse-Transform Method……Page 72
2.3.3 Composition Method……Page 75
2.3.4 Acceptance-Rejection Method……Page 76
2.4.1 Generating Continuous Random Variables……Page 79
2.4.2 Generating Discrete Random Variables……Page 84
2.5 Random Vector Generation……Page 86
2.5.1 Vector Acceptance-Rejection Method……Page 87
2.5.2 Generating Variables from a Multinomial Distribution……Page 88
2.5.3 Generating Uniform Random Vectors Over a Simplex……Page 89
2.5.4 Generating Random Vectors Uniformly Distributed Over a Unit Hyperball and Hypersphere……Page 90
2.6 Generating Poisson Processes……Page 91
2.7.1 Random Walk on a Graph……Page 93
2.7.2 Generating Markov Jump Processes……Page 94
2.8 Generating Random Permutations……Page 95
Problems……Page 96
References……Page 101
3 Simulation of Discrete-Event Systems……Page 102
3.1 Simulation Models……Page 103
3.1.1 Classification of Simulation Models……Page 105
3.2 Simulation Clock and Event List for DEDS……Page 106
3.3.1 Tandem Queue……Page 108
3.3.2 Repairman Problem……Page 112
Problems……Page 115
References……Page 117
4.1 Introduction……Page 118
4.2 Static Simulation Models……Page 119
4.2.1 Confidence Interval……Page 121
4.3 Dynamic Simulation Models……Page 122
4.3.1 Finite-Horizon Simulation……Page 123
4.3.2 Steady-State Simulation……Page 124
4.4 The Bootstrap Method……Page 134
Problems……Page 136
References……Page 139
5.1 Introduction……Page 140
5.2 Common and Antithetic Random Variables……Page 141
5.3 Control Variables……Page 144
5.4 Conditional Monte Carlo……Page 146
5.4.1 Variance Reduction for Reliability Models……Page 147
5.5 Stratified Sampling……Page 150
5.6 Importance Sampling……Page 152
5.6.2 The Variance Minimization Method……Page 153
5.6.3 The Cross-Entropy Method……Page 157
5.7 Sequential Importance Sampling……Page 162
5.7.1 Nonlinear Filtering for Hidden Markov Models……Page 165
5.8 The Transform Likelihood Ratio Method……Page 169
5.9 Preventing the Degeneracy of Importance Sampling……Page 172
5.9.1 The Two-Stage Screening Algorithm……Page 174
5.9.2 Case Study……Page 179
Problems……Page 182
References……Page 186
6.1 Introduction……Page 188
6.2 The Metropolis–Hastings Algorithm……Page 189
6.3 The Hit-and-Run Sampler……Page 194
6.4 The Gibbs Sampler……Page 196
6.5.1 Ising Model……Page 199
6.5.2 Potts Model……Page 200
6.6 Bayesian Statistics……Page 202
6.7 Other Markov Samplers……Page 204
6.7.1 Slice Sampler……Page 206
6.7.2 Reversible Jump Sampler……Page 207
6.8 Simulated Annealing……Page 210
6.9 Perfect Sampling……Page 213
Problems……Page 215
References……Page 220
7.1 Introduction……Page 222
7.2 The Score Function Method for Sensitivity Analysis of DESS……Page 224
7.3 Simulation-Based Optimization of DESS……Page 232
7.3.1 Stochastic Approximation……Page 233
7.3.2 The Stochastic Counterpart Method……Page 236
7.4 Sensitivity Analysis of DEDS……Page 246
Problems……Page 251
References……Page 254
8.1 Introduction……Page 256
8.2 Estimation of Rare-Event Probabilities……Page 257
8.2.2 The Screening Method for Rare Events……Page 266
8.3 The CE Method for Optimization……Page 270
8.4 The Max-cut Problem……Page 274
8.5 The Partition Problem……Page 280
8.6 The Traveling Salesman Problem……Page 281
8.6.1 Incomplete Graphs……Page 286
8.6.2 Node Placement……Page 287
8.6.3 Case Studies……Page 288
8.7 Continuous Optimization……Page 289
8.8 Noisy Optimization……Page 290
Problems……Page 292
References……Page 296
9.1 Counting Problems……Page 300
9.2 Satisfiability Problem……Page 301
9.2.1 Random K-SAT (K-RSAT)……Page 304
9.3 The Rare-Event Framework for Counting……Page 305
9.3.1 Rare Events for the Satisfiability Problem……Page 308
9.4 Other Randomized Algorithms for Counting……Page 309
9.4.1 X is a Union of Some Sets……Page 312
9.4.2 Complexity of Randomized Algorithms: FPRAS and FPAUS……Page 315
9.5.1 The MinxEnt Method……Page 318
9.5.2 Rare-Event Probability Estimation Using PME……Page 322
9.6 PME for Combinatorial Optimization Problems and Decision Making……Page 327
9.7 Numerical Results……Page 328
Problems……Page 332
References……Page 333
A.1 Cholesky Square Root Method……Page 336
A.2 Exact Sampling from a Conditional Bernoulli Distribution……Page 337
A.3 Exponential Families……Page 338
A.4 Sensitivity Analysis……Page 341
A.4.1 Convexity Results……Page 342
A.4.2 Monotonicity Results……Page 343
A.6 Discrete-time Kalman Filter……Page 344
A.7 Bernoulli Disruption Problem……Page 345
A.8 Complexity of Stochastic Programming Problems……Page 347
Problems……Page 355
References……Page 356
Abbreviations and Acronyms……Page 357
List of Symbols……Page 359
Index……Page 362