Simulation and the Monte Carlo Method (eBook)

Reuven Y. Rubinstein, Dirk P. Kroese (Autoren)

eBook Download: PDF

2016 | 3. Auflage
John Wiley & Sons (Verlag)
978-1-118-63220-8 (ISBN)

Infos

This accessible new edition explores the major topics in Monte Carlo simulation that have arisen over the past 30 years and presents a sound foundation for problem solving 

Simulation and the Monte Carlo Method, Third Edition reflects the latest developments in the field and presents a fully updated and comprehensive account of the state-of-the-art theory, methods and applications that have emerged in Monte Carlo simulation since the publication of the classic First Edition over more than a quarter of a century ago. While maintaining its accessible and intuitive approach, this revised edition features a wealth of up-to-date information that facilitates a deeper understanding of problem solving across a wide array of subject areas, such as engineering, statistics, computer science, mathematics, and the physical and life sciences. The book begins with a modernized introduction that addresses the basic concepts of probability, Markov processes, and convex optimization. Subsequent chapters discuss the dramatic changes that have occurred in the field of the Monte Carlo method, with coverage of many modern topics including: Markov Chain Monte Carlo, variance reduction techniques such as importance (re-)sampling, and the transform likelihood ratio method, the score function method for sensitivity analysis, the stochastic approximation method and the stochastic counter-part method for Monte Carlo optimization, the cross-entropy method for rare events estimation and combinatorial optimization, and application of Monte Carlo techniques for counting problems. An extensive range of exercises is provided at the end of each chapter, as well as a generous sampling of applied examples.

The Third Edition features a new chapter on the highly versatile splitting method, with applications to rare-event estimation, counting, sampling, and optimization. A second new chapter introduces the stochastic enumeration method, which is a new fast sequential Monte Carlo method for tree search. In addition, the Third Edition features new material on:

• Random number generation, including multiple-recursive generators and the Mersenne Twister

• Simulation of Gaussian processes, Brownian motion, and diffusion processes

• Multilevel Monte Carlo method

• New enhancements of the cross-entropy (CE) method, including the 'improved' CE method, which uses sampling from the zero-variance distribution to find the optimal importance sampling parameters

• Over 100 algorithms in modern pseudo code with flow control

• Over 25 new exercises

Simulation and the Monte Carlo Method, Third Edition is an excellent text for upper-undergraduate and beginning graduate courses in stochastic simulation and Monte Carlo techniques. The book also serves as a valuable reference for professionals who would like to achieve a more formal understanding of 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.

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.

Inhalt

SIMULATION AND THE MONTE CARLO METHOD 3
CONTENTS 9
PREFACE 15
ACKNOWLEDGMENTS 19
CHAPTER 1 PRELIMINARIES 21
1.1 INTRODUCTION 21
1.2 RANDOM EXPERIMENTS 21
1.3 CONDITIONAL PROBABILITY AND INDEPENDENCE 22
1.4 RANDOM VARIABLES AND PROBABILITY DISTRIBUTIONS 24
1.5 SOME IMPORTANT DISTRIBUTIONS 25
1.6 EXPECTATION 26
1.7 JOINT DISTRIBUTIONS 27
1.8 FUNCTIONS OF RANDOM VARIABLES 31
1.8.1 Linear Transformations 32
1.8.2 General Transformations 33
1.9 TRANSFORMS 34
1.10 JOINTLY NORMAL RANDOM VARIABLES 35
1.11 LIMIT THEOREMS 36
1.12 POISSON PROCESSES 37
1.13 MARKOV PROCESSES 39
1.13.1 Markov Chains 39
1.13.2 Classification of States 41
1.13.3 Limiting Behavior 42
1.13.4 Reversibility 44
1.13.5 Markov Jump Processes 45
1.14 GAUSSIAN PROCESSES 47
1.15 INFORMATION 48
1.15.1 Shannon Entropy 49
1.15.2 Kullback–Leibler Cross-Entropy 51
1.15.3 Maximum Likelihood Estimator and Score Function 52
1.15.4 Fisher Information 53
1.16 CONVEX OPTIMIZATION AND DUALITY 54
1.16.1 Lagrangian Method 55
1.16.2 Duality 57
PROBLEMS 61
REFERENCES 66
CHAPTER 2 RANDOM NUMBER, RANDOM VARIABLE, AND STOCHASTIC PROCESS GENERATION 69
2.1 INTRODUCTION 69
2.2 RANDOM NUMBER GENERATION 69
2.2.1 Multiple Recursive Generators 71
2.2.2 Modulo 2 Linear Generators 72
2.3 RANDOM VARIABLE GENERATION 75
2.3.1 Inverse-Transform Method 75
2.3.2 Alias Method 77
2.3.3 Composition Method 78
2.3.4 Acceptance–Rejection Method 79
2.4 GENERATING FROM COMMONLY USED DISTRIBUTIONS 82
2.4.1 Generating Continuous Random Variables 82
2.4.2 Generating Discrete Random Variables 87
2.5 RANDOM VECTOR GENERATION 90
2.5.1 Vector Acceptance–Rejection Method 91
2.5.2 Generating Variables from a Multinormal Distribution 92
2.5.3 Generating Uniform Random Vectors over a Simplex 93
2.5.4 Generating Random Vectors Uniformly Distributed over a Unit Hyperball and Hypersphere 94
2.5.5 Generating Random Vectors Uniformly Distributed inside a Hyperellipsoid 95
2.6 GENERATING POISSON PROCESSES 95
2.7 GENERATING MARKOV CHAINS AND MARKOV JUMP PROCESSES 97
2.7.1 Random Walk on a Graph 98
2.7.2 Generating Markov Jump Processes 99
2.8 GENERATING GAUSSIAN PROCESSES 100
2.9 GENERATING DIFFUSION PROCESSES 101
2.10 GENERATING RANDOM PERMUTATIONS 103
PROBLEMS 105
REFERENCES 109
CHAPTER 3 SIMULATION OF DISCRETE-EVENT SYSTEMS 111
3.1 INTRODUCTION 111
3.2 SIMULATION MODELS 112
3.2.1 Classification of Simulation Models 114
3.3 SIMULATION CLOCK AND EVENT LIST FOR DEDS 115
3.4 DISCRETE-EVENT SIMULATION 117
3.4.1 Tandem Queue 117
3.4.2 Repairman Problem 121
PROBLEMS 123
REFERENCES 126
CHAPTER 4 STATISTICAL ANALYSIS OF DISCRETE-EVENT SYSTEMS 127
4.1 INTRODUCTION 127
4.2 ESTIMATORS AND CONFIDENCE INTERVALS 128
4.3 STATIC SIMULATION MODELS 130
4.4 DYNAMIC SIMULATION MODELS 132
4.4.1 Finite-Horizon Simulation 134
4.4.2 Steady-State Simulation 134
4.5 BOOTSTRAP METHOD 146
PROBLEMS 147
REFERENCES 150
CHAPTER 5 CONTROLLING THE VARIANCE 153
5.1 INTRODUCTION 153
5.2 COMMON AND ANTITHETIC RANDOM VARIABLES 154
5.3 CONTROL VARIABLES 157
5.4 CONDITIONAL MONTE CARLO 159
5.4.1 Variance Reduction for Reliability Models 161
5.5 STRATIFIED SAMPLING 164
5.6 MULTILEVEL MONTE CARLO 166
5.7 IMPORTANCE SAMPLING 169
5.7.1 Weighted Samples 169
5.7.2 Variance Minimization Method 170
5.7.3 Cross-Entropy Method 174
5.8 SEQUENTIAL IMPORTANCE SAMPLING 179
5.9 SEQUENTIAL IMPORTANCE RESAMPLING 185
5.10 NONLINEAR FILTERING FOR HIDDEN MARKOV MODELS 187
5.11 TRANSFORM LIKELIHOOD RATIO METHOD 191
5.12 PREVENTING THE DEGENERACY OF IMPORTANCE SAMPLING 194
PROBLEMS 199
REFERENCES 204
CHAPTER 6 MARKOV CHAIN MONTE CARLO 207
6.1 INTRODUCTION 207
6.2 METROPOLIS–HASTINGS ALGORITHM 208
6.3 HIT-AND-RUN SAMPLER 213
6.4 GIBBS SAMPLER 214
6.5 ISING AND POTTS MODELS 217
6.5.1 Ising Model 217
6.5.2 Potts Model 218
6.6 BAYESIAN STATISTICS 220
6.7 OTHER MARKOV SAMPLERS 222
6.7.1 Slice Sampler 224
6.7.2 Reversible Jump Sampler 225
6.8 SIMULATED ANNEALING 228
6.9 PERFECT SAMPLING 232
PROBLEMS 234
REFERENCES 239
CHAPTER 7 SENSITIVITY ANALYSIS AND MONTE CARLO OPTIMIZATION 241
7.1 INTRODUCTION 241
7.2 SCORE FUNCTION METHOD FOR SENSITIVITY ANALYSIS OF DESS 244
7.3 SIMULATION-BASED OPTIMIZATION OF DESS 251
7.3.1 Stochastic Approximation 252
7.3.2 Stochastic Counterpart Method 257
7.4 SENSITIVITY ANALYSIS OF DEDS 266
PROBLEMS 272
REFERENCES 275
CHAPTER 8 CROSS-ENTROPY METHOD 277
8.1 INTRODUCTION 277
8.2 ESTIMATION OF RARE-EVENT PROBABILITIES 278
8.2.1 Root-Finding Problem 287
8.2.2 Screening Method for Rare Events 288
8.2.3 CE Method Combined with Sampling from the Zero-Variance Distribution 291
8.3 CE METHOD FOR OPTIMIZATION 292
8.4 MAX-CUT PROBLEM 296
8.5 PARTITION PROBLEM 302
8.5.1 Empirical Computational Complexity 303
8.6 TRAVELING SALESMAN PROBLEM 303
8.6.1 Incomplete Graphs 308
8.6.2 Node Placement 309
8.6.3 Case Studies 310
8.7 CONTINUOUS OPTIMIZATION 311
8.8 NOISY OPTIMIZATION 312
8.9 MINXENT METHOD 314
PROBLEMS 318
REFERENCES 323
CHAPTER 9 SPLITTING METHOD 327
9.1 INTRODUCTION 327
9.2 COUNTING SELF-AVOIDING WALKS VIA SPLITTING 328
9.3 SPLITTING WITH A FIXED SPLITTING FACTOR 330
9.4 SPLITTING WITH A FIXED EFFORT 333
9.5 GENERALIZED SPLITTING 334
9.6 ADAPTIVE SPLITTING 338
9.7 APPLICATION OF SPLITTING TO NETWORK RELIABILITY 341
9.8 APPLICATIONS TO COUNTING 342
9.9 CASE STUDIES FOR COUNTING WITH SPLITTING 345
9.9.1 Satisfiability (SAT) Problem 345
9.9.2 Independent Sets 350
9.9.3 Permanent and Counting Perfect Matchings 352
9.9.4 Binary Contingency Tables 354
9.9.5 Vertex Coloring 356
9.10 SPLITTING AS A SAMPLING METHOD 357
9.11 SPLITTING FOR OPTIMIZATION 360
9.11.1 Continuous Optimization 363
PROBLEMS 364
REFERENCES 368
CHAPTER 10 STOCHASTIC ENUMERATION METHOD 371
10.1 INTRODUCTION 371
10.2 TREE SEARCH AND TREE COUNTING 372
10.3 KNUTH’S ALGORITHM FOR ESTIMATING THE COST OF A TREE 375
10.4 STOCHASTIC ENUMERATION 377
10.4.1 Combining SE with Oracles 379
10.5 APPLICATION OF SE TO COUNTING 380
10.5.1 Counting the Number of Paths in a Network 380
10.5.2 Counting SATs 383
10.5.3 Counting the Number of Perfect Matchings in a Bipartite Graph 386
10.6 APPLICATION OF SE TO NETWORK RELIABILITY 388
10.6.1 Numerical Results 390
PROBLEMS 393
REFERENCES 395
APPENDIX 397
A.1 CHOLESKY SQUARE ROOT METHOD 397
A.2 EXACT SAMPLING FROM A CONDITIONAL BERNOULLI DISTRIBUTION 398
A.3 EXPONENTIAL FAMILIES 399
A.4 SENSITIVITY ANALYSIS 402
A.4.1 Convexity Results 403
A.4.2 Monotonicity Results 404
A.5 A SIMPLE CE ALGORITHM FOR OPTIMIZING THE PEAKS FUNCTION 405
A.6 DISCRETE-TIME KALMAN FILTER 405
A.7 BERNOULLI DISRUPTION PROBLEM 407
A.8 COMPLEXITY 409
A.8.1 Complexity of Rare-Event Algorithms 409
A.8.2 Complexity of Randomized Algorithms: FPRAS and FPAUS 410
A.8.3 SATs in CNF 414
A.8.4 Complexity of Stochastic Programming Problems 415
PROBLEMS 422
REFERENCES 423
ABBREVIATIONS AND ACRONYMS 425
LIST OF SYMBOLS 427
INDEX 429
EULA 435

Produkt-Details

• Erscheint lt. Verlag: 20.10.2016
• Reihe/Serie: Wiley Series in Probability and Statistics
• Reihe/Serie: Wiley Series in Probability and Statistics
• Reihe/Serie: Wiley Series in Probability and Statistics
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Mathematik ► Analysis
• Themenwelt: Mathematik / Informatik ► Mathematik ► Statistik
• Themenwelt: Mathematik / Informatik ► Mathematik ► Wahrscheinlichkeit / Kombinatorik
• Themenwelt: Technik
• Schlagworte: and convex optimization • Angewandte Wahrscheinlichkeitsrechnung u. Statistik • Angew. Wahrscheinlichkeitsrechn. u. Statistik / Modelle • application of Monte Carlo techniques for counting problems • Applied Probability & Statistics • Applied Probability & Statistics - Models • cross-entropy method for rare events estimation and combinatorial optimization • importance (re-)sampling • Markov Processes • Monte Carlo Methode • Monte Carlo simulation • ?probability • score function method for sensitivity analysis • Simulation • Spezialthemen Statistik • Statistics • Statistics Special Topics • Statistik • stochastic approximation method • stochastic counter-part method for Monte Carlo optimization • transform likelihood ratio method • variance reduction techniques
• ISBN-10: 1-118-63220-6 / 1118632206
• ISBN-13: 978-1-118-63220-8 / 9781118632208