Preface ...................................................... xiii
Acknowledgments .............................................. xvii
1. Preliminaries ............................................... 1
1.1. Random Experiments .................................... 1
1.2. Conditional Probability and Independence .............. 2
1.3. Random Variables and Probability Distributions ........ 3
1.4. Some Important Distributions .......................... 5
1.5. Expectation ........................................... 6
1.6. Joint Distributions ................................... 7
1.7. Functions of Random Variables ........................ 10
1.7.1. Linear Transformations ....................... 11
1.7.2. General Transformations ...................... 12
1.8. Transforms ........................................... 13
1.9. Jointly Normal Random Variables ...................... 14
1.10. Limit Theorems ....................................... 15
1.11. Poisson Processes .................................... 16
1.12. Markov Processes ..................................... 18
1.12.1. Markov Chains ................................ 19
1.12.2. Classification of States ..................... 29
1.12.3. Limiting Behavior ............................ 21
1.12.4. Reversibility ................................ 23
1.12.5. Markov Jump Processes ........................ 24
1.13. Efficiency of Estimators ............................. 26
1.13.1. Complexity ................................... 28
1.14. Information .......................................... 28
1.14.1. Shannon Entropy .............................. 29
1.14.2. Kullback-Leibler Cross-Entropy ............... 31
1.14.3. The Maximum Likelihood Estimator and
the Score Function ........................... 32
1.14.4. Fisher Information ........................... 33
1.15. Convex Optimization and Duality ...................... 34
1.15.1. Lagrangian Method ............................ 36
1.15.2. Duality ...................................... 37
Problems ................................................... 41
References ................................................. 46
2. Random Number, Random Variable, and Stochastic Process
Generation ................................................. 49
2.1. Introduction ......................................... 49
2.2. Random Number Generation ............................. 49
2.3. Random Variable Generation ........................... 51
2.3.1. Inverse-Transform Method ...................... 51
2.3.2. Alias Method .................................. 54
2.3.3. Composition Method ............................ 54
2.3.4. Acceptance-Rejection Method ................... 55
2.4. Generating From Commonly Used Distributions .......... 58
2.4.1. Generating Continuous Random Variables ........ 58
2.4.2. Generating Discrete Random Variables .......... 63
2.5. Random Vector Generation ............................. 65
2.5.1. Vector Acceptance-Rejection Method ............ 66
2.5.2. Generating Variables from a Multinomial
Distribution .................................. 67
2.5.3. Generating Uniform Random Vectors Over
a Simplex ..................................... 68
2.5.4. Generating Random Vectors Uniformly
Distributed Over a Unit Hyperball
and Hypersphere ............................... 69
2.5.5. Generating Random Vectors Uniformly
Distributed Over a Hyperellipsoid ............. 70
2.6. Generating Poisson Processes ......................... 70
2.7. Generating Markov Chains and Markov Jump Processes ... 72
2.7.1. Random Walk on a Graph ........................ 72
2.7.2. Generating Markov Jump Processes .............. 73
2.8. Generating Random Permutations ....................... 74
Problems ................................................... 75
References ................................................. 80
3. Simulation of Discrete-Event Systems ....................... 81
3.1. Simulation Models .................................... 82
3.1.1. Classification of S imulation Models .......... 84
3.2. Simulation Clock and Event List for DEDS ............. 85
3.3. Discrete-Event Simulation ............................ 87
3.3.1. Tandem Queue .................................. 87
3.3.2. Repairman Problem ............................. 91
Problems ................................................... 94
References ................................................. 96
4. Statistical Analysis of Discrete-Event Systems ............. 97
4.1. Introduction ......................................... 97
4.2. Static Simulation Models ............................. 98
4.2.1. Confidence Interval .......................... 100
4.3. Dynamic Simulation Models ........................... 101
4.3.1 Finite-Horizon Simulation ..................... 102
4.3.2 Steady-State Simulation ....................... 103
4.4. The Bootstrap Method ................................ 113
Problems .................................................. 115
References ................................................ 118
5. Controlling the Variance .................................. 119
5.1. Introduction ........................................ 119
5.2. Common and Antithetic Random Variables .............. 120
5.3. Control Variables ................................... 123
5.4. Conditional Monte Carlo ............................. 125
5.4.1. Variance Reduction for Reliability Models .... 126
5.5. Stratified Sampling ................................. 129
5.6. Importance Sampling ................................. 131
5.6.1. Weighted Samples ............................. 132
5.6.2. The Variance Minimization Method ............. 132
5.6.3. The Cross-Entropy Method ..................... 136
5.7. Sequential Importance Sampling ...................... 141
5.7.1. Nonlinear Filtering for Hidden Markov
Models .............................................. 144
5.8. The Transform Likelihood Ratio Method ............... 148
5.9. Preventing the Degeneracy of Importance Sampling .... 151
5.9.1. The Two-Stage Screening Algorithm ............ 153
5.9.2. Case Study ................................... 158
Problems .................................................. 161
References ................................................ 165
6. Markov Chain Monte Carlo .................................. 167
6.1. Introduction ........................................ 167
6.2. The Metropolis-Hastings Algorithm ................... 168
6.3. The Hit-and-Run Sampler ............................. 173
6.4. The Gibbs Sampler ................................... 175
6.5. Ising and Potts Models .............................. 178
6.5.1. Ising Model .................................. 178
6.5.2. Potts Model .................................. 179
6.6. Bayesian Statistics ................................. 181
6.7. Other Markov Samplers ............................... 185
6.7.1. Slice Sampler ................................ 185
6.7.2. Reversible Jump Sampler ...................... 186
6.8. Simulated Annealing ................................. 189
6.9. Perfect Sampling .................................... 192
Problems .................................................. 194
References ................................................ 199
7. Sensitivity Analysis and Monte Carlo Optimization ......... 201
7.1. Introduction ........................................ 201
7.2. The Score Function Method for Sensitivity Analysis
of DESS ............................................. 203
7.3. Simulation-Based Optimization of DESS ............... 211
7.3.1. Stochastic Approximation ..................... 212
7.3.2. The Stochastic Counterpart Method ............ 215
7.4. Sensitivity Analysis of DEDS ........................ 225
Problems .................................................. 230
References ................................................ 233
8. The Cross-Entropy Method .................................. 235
8.1. Introduction ........................................ 235
8.2. Estimation of Rare-Event Probabilities .............. 236
8.2.1. The Root-Finding Problem ..................... 245
8.2.2. The Screening Method for Rare Events ......... 245
8.3. The CE Method for Optimization ...................... 249
8.4. The Max-cut Problem ................................. 253
8.5. The Partition Problem ............................... 259
8.5.1. Empirical Computational Complexity ........... 260
8.6. The Traveling Salesman Problem ...................... 260
8.6.1. Incomplete Graphs ............................ 265
8.6.2. Node Placement ............................... 266
8.6.3. Case Studies ................................. 267
8.7. Continuous Optimization ............................. 268
8.8. Noisy Optimization .................................. 269
Problems .................................................. 271
References ................................................ 275
9. Counting via Monte Carlo .................................. 279
9.1. Counting Problems ................................... 279
9.2. Satisfiability Problem .............................. 280
9.2.1. Random K-SAT {K-RSAT) ........................ 283
9.3. The Rare-Event Framework for Counting ............... 284
9.3.1. Rare Events for the Satisfiability Problem ... 287
9.4. Other Randomized Algorithms for Counting ............ 288
9.4.1. X* is a Union of Some Sets ................... 291
9.4.2. Complexity of Randomized Algorithms:
FPRAS and FPAUS .............................. 294
9.4.3. FPRAS for SATs in CNF ........................ 297
9.5. MinxEnt and Parametric MinxEnt ...................... 297
9.5.1. The MinxEnt Method ........................... 297
9.5.2. Rare-Event Probability Estimation Using
PME .......................................... 301
9.6. PME for Combinatorial Optimization Problems
and Decision Making ................................. 306
9.7. Numerical Results ................................... 307
Problems .................................................. 311
References ................................................ 312
Appendix ...................................................... 315
A.1 Cholesky Square Root Method ............................... 315
A.2 Exact Sampling from a Conditional Bernoulli
Distribution .............................................. 316
A.3 Exponential Families ...................................... 317
A.4 Sensitivity Analysis ...................................... 320
A.4.1 Convexity Results ................................... 321
A.4.2 Monotonicity Results ................................ 322
A.5 A Simple CE Algorithm for Optimizing the Peaks Function ... 323
A.6 Discrete-time Kalman Filter ............................... 323
A.7 Bernoulli Disruption Problem .............................. 324
A.8 Complexity of Stochastic Programming Problems ............. 326
Problems .................................................. 334
References ................................................ 335
Abbreviations and Acronyms .................................... 336
List of Symbols ............................................... 338
Index ......................................................... 341
|
