Handbook of Monte Carlo methods

Cover......Page 1
Title Page......Page 6
Copyright Page......Page 7
Dedication......Page 8
Contents......Page 10
Preface......Page 20
Acknowledgments......Page 22
1.1 Random Numbers......Page 24
1.1.1 Properties of a Good Random Number Generator......Page 25
1.1.2 Choosing a Good Random Number Generator......Page 26
1.2.1 Linear Congruential Generators......Page 27
1.2.2 Multiple-Recursive Generators......Page 28
1.2.4 Modulo 2 Linear Generators......Page 29
1.3 Combined Generators......Page 31
1.4 Other Generators......Page 33
1.5 Tests for Random Number Generators......Page 34
1.5.1 Spectral Test......Page 35
1.5.2 Empirical Tests......Page 37
References......Page 44
2.1 Multidimensional Integration......Page 48
2.2 Van der Corput and Digital Sequences......Page 50
2.3 Halton Sequences......Page 52
2.4 Faure Sequences......Page 54
2.5 Sobol' Sequences......Page 56
2.6 Lattice Methods......Page 59
2.7 Randomization and Scrambling......Page 61
References......Page 63
3 Random Variable Generation......Page 66
3.1 Generic Algorithms Based on Common Transformations......Page 67
3.1.1 Inverse-Transform Method......Page 68
3.1.2 Other Transformation Methods......Page 70
3.1.3 Table Lookup Method......Page 78
3.1.4 Alias Method......Page 79
3.1.5 Acceptance-Rejection Method......Page 82
3.1.6 Ratio of Uniforms Method......Page 89
3.2 Generation Methods for Multivariate Random Variables......Page 90
3.2.1 Copulas......Page 91
3.3.1 Generating Order Statistics......Page 93
3.3.2 Generating Uniform Random Vectors in a Simplex......Page 94
3.3.3 Generating Random Vectors Uniformly Distributed in a Unit Hyperball and Hypersphere......Page 97
3.3.5 Uniform Sampling on a Curve......Page 98
3.3.6 Uniform Sampling on a Surface......Page 99
3.3.7 Generating Random Permutations......Page 102
3.3.8 Exact Sampling From a Conditional Bernoulli Distribution......Page 103
References......Page 106
4.1.1 Bernoulli Distribution......Page 108
4.1.2 Binomial Distribution......Page 109
4.1.3 Geometric Distribution......Page 114
4.1.4 Hypergeometric Distribution......Page 116
4.1.5 Negative Binomial Distribution......Page 117
4.1.6 Phase-Type Distribution (Discrete Case)......Page 119
4.1.7 Poisson Distribution......Page 121
4.1.8 Uniform Distribution (Discrete Case)......Page 124
4.2.1 Beta Distribution......Page 125
4.2.2 Cauchy Distribution......Page 129
4.2.3 Exponential Distribution......Page 131
4.2.4 F Distribution......Page 132
4.2.5 Fréchet Distribution......Page 134
4.2.6 Gamma Distribution......Page 135
4.2.7 Gumbel Distribution......Page 139
4.2.8 Laplace Distribution......Page 141
4.2.9 Logistic Distribution......Page 142
4.2.10 Log-Normal Distribution......Page 143
4.2.11 Normal Distribution......Page 145
4.2.12 Pareto Distribution......Page 148
4.2.13 Phase-Type Distribution (Continuous Case)......Page 149
4.2.14 Stable Distribution......Page 152
4.2.15 Student's t Distribution......Page 154
4.2.16 Uniform Distribution (Continuous Case)......Page 157
4.2.17 Wald Distribution......Page 158
4.2.18 Weibull Distribution......Page 160
4.3 Multivariate Distributions......Page 161
4.3.1 Dirichlet Distribution......Page 162
4.3.2 Multinomial Distribution......Page 164
4.3.3 Multivariate Normal Distribution......Page 166
4.3.4 Multivariate Student's t Distribution......Page 170
4.3.5 Wishart Distribution......Page 171
References......Page 173
5 Random Process Generation......Page 176
5.1 Gaussian Processes......Page 177
5.1.1 Markovian Gaussian Processes......Page 182
5.1.2 Stationary Gaussian Processes and the FFT......Page 183
5.2 Markov Chains......Page 185
5.3 Markov Jump Processes......Page 189
5.4 Poisson Processes......Page 193
5.4.1 Compound Poisson Process......Page 197
5.5 Wiener Process and Brownian Motion......Page 200
5.6 Stochastic Differential Equations and Diffusion Processes......Page 206
5.6.1 Euler's Method......Page 208
5.6.2 Milstein's Method......Page 210
5.6.3 Implicit Euler......Page 211
5.6.4 Exact Methods......Page 212
5.6.5 Error and Accuracy......Page 214
5.7 Brownian Bridge......Page 216
5.8 Geometric Brownian Motion......Page 219
5.9 Ornstein-Uhlenbeck Process......Page 221
5.10 Reflected Brownian Motion......Page 223
5.11 Fractional Brownian Motion......Page 226
5.12 Random Fields......Page 229
5.13 Lévy Processes......Page 231
5.13.1 Increasing Lévy Processes......Page 234
5.13.2 Generating Lévy Processes......Page 237
5.14 Time Series......Page 242
References......Page 245
6 Markov Chain Monte Carlo......Page 248
6.1 Metropolis-Hastings Algorithm......Page 249
6.1.1 Independence Sampler......Page 250
6.1.2 Random Walk Sampler......Page 253
6.2 Gibbs Sampler......Page 256
6.3.1 Hit-and-Run Sampler......Page 263
6.3.2 Shake-and-Bake Sampler......Page 274
6.3.3 Metropolis-Gibbs Hybrids......Page 279
6.3.4 Multiple-Try Metropolis-Hastings......Page 280
6.3.5 Auxiliary Variable Methods......Page 282
6.3.6 Reversible Jump Sampler......Page 292
6.4 Implementation Issues......Page 296
6.5 Perfect Sampling......Page 297
References......Page 299
7.1 Simulation Models......Page 304
7.2 Discrete Event Systems......Page 306
7.3 Event-Oriented Approach......Page 308
7.4.1 Inventory System......Page 312
7.4.2 Tandem Queue......Page 316
7.4.3 Repairman Problem......Page 319
References......Page 323
8.1 Simulation Data......Page 324
8.1.1 Data Visualization......Page 325
8.1.2 Data Summarization......Page 326
8.2 Estimation of Performance Measures for Independent Data......Page 328
8.2.1 Delta Method......Page 331
8.3.1 Covariance Method......Page 332
8.3.2 Batch Means Method......Page 334
8.3.3 Regenerative Method......Page 336
8.4 Empirical Cdf......Page 339
8.5 Kernel Density Estimation......Page 342
8.5.1 Least Squares Cross Validation......Page 344
8.5.2 Plug-in Bandwidth Selection......Page 349
8.6 Resampling and the Bootstrap Method......Page 354
8.7 Goodness of Fit......Page 356
8.7.1 Graphical Procedures......Page 357
8.7.2 Kolmogorov-Smirnov Test......Page 359
8.7.3 Anderson-Darling Test......Page 362
8.7.4 X2 Tests......Page 363
References......Page 366
9 Variance Reduction......Page 370
9.1 Variance Reduction Example......Page 371
9.2 Antithetic Random Variables......Page 372
9.3 Control Variables......Page 374
9.4 Conditional Monte Carlo......Page 377
9.5 Stratified Sampling......Page 379
9.6 Latin Hypercube Sampling......Page 383
9.7 Importance Sampling......Page 385
9.7.1 Minimum-Variance Density......Page 386
9.7.2 Variance Minimization Method......Page 387
9.7.3 Cross-Entropy Method......Page 389
9.7.4 Weighted Importance Sampling......Page 391
9.7.5 Sequential Importance Sampling......Page 392
9.7.6 Response Surface Estimation via Importance Sampling......Page 396
9.8 Quasi Monte Carlo......Page 399
References......Page 402
10 Rare-Event Simulation......Page 404
10.1 Efficiency of Estimators......Page 405
10.2 Importance Sampling Methods for Light Tails......Page 408
10.2.1 Estimation of Stopping Time Probabilities......Page 409
10.2.2 Estimation of Overflow Probabilities......Page 412
10.2.3 Estimation For Compound Poisson Sums......Page 414
10.3 Conditioning Methods for Heavy Tails......Page 416
10.3.1 Estimation for Compound Sums......Page 417
10.3.2 Sum of Nonidentically Distributed Random Variables......Page 419
10.4 State-Dependent Importance Sampling......Page 421
10.5 Cross-Entropy Method for Rare-Event Simulation......Page 427
10.6 Splitting Method......Page 432
References......Page 439
11.1 Gradient Estimation......Page 444
11.2 Finite Difference Method......Page 446
11.3 Infinitesimal Perturbation Analysis......Page 449
11.4 Score Function Method......Page 451
11.4.1 Score Function Method With Importance Sampling......Page 453
11.5 Weak Derivatives......Page 456
11.6 Sensitivity Analysis for Regenerative Processes......Page 458
References......Page 461
12.1 Stochastic Approximation......Page 464
12.2 Stochastic Counterpart Method......Page 469
12.3 Simulated Annealing......Page 472
12.4.1 Genetic Algorithms......Page 475
12.4.2 Differential Evolution......Page 477
12.4.3 Estimation of Distribution Algorithms......Page 479
12.5 Cross-Entropy Method for Optimization......Page 480
12.6 Other Randomized Optimization Techniques......Page 483
References......Page 484
13.1 Cross-Entropy Method......Page 486
13.2 Cross-Entropy Method for Estimation......Page 487
13.3 Cross-Entropy Method for Optimization......Page 491
13.3.1 Combinatorial Optimization......Page 492
13.3.2 Continuous Optimization......Page 494
13.3.3 Constrained Optimization......Page 496
13.3.4 Noisy Optimization......Page 499
References......Page 500
14 Particle Methods......Page 504
14.1 Sequential Monte Carlo......Page 505
14.2 Particle Splitting......Page 508
14.3 Splitting for Static Rare-Event Probability Estimation......Page 509
14.4 Adaptive Splitting Algorithm......Page 516
14.5 Estimation of Multidimensional Integrals......Page 518
14.6 Combinatorial Optimization via Splitting......Page 527
14.6.1 Knapsack Problem......Page 528
14.6.2 Traveling Salesman Problem......Page 529
14.6.3 Quadratic Assignment Problem......Page 531
14.7 Markov Chain Monte Carlo With Splitting......Page 532
References......Page 540
15.1 Standard Model......Page 544
15.2 Pricing via Monte Carlo Simulation......Page 549
15.3 Sensitivities......Page 561
15.3.1 Pathwise Derivative Estimation......Page 563
15.3.2 Score Function Method......Page 565
References......Page 569
16.1 Network Reliability......Page 572
16.2 Evolution Model for a Static Network......Page 574
16.3 Conditional Monte Carlo......Page 577
16.3.1 Leap-Evolve Algorithm......Page 583
16.4.1 Importance Sampling Using Bounds......Page 585
16.4.2 Importance Sampling With Conditional Monte Carlo......Page 588
16.5 Splitting Method......Page 590
16.5.1 Acceleration Using Bounds......Page 596
References......Page 597
17.1 Connections Between Stochastic and Partial Differential Equations......Page 600
17.1.1 Boundary Value Problems......Page 602
17.1.2 Terminal Value Problems......Page 607
17.1.3 Terminal-Boundary Problems......Page 608
17.2 Transport Processes and Equations......Page 610
17.2.1 Application to Transport Equations......Page 612
17.2.2 Boltzmann Equation......Page 616
17.3 Connections to ODEs Through Scaling......Page 620
References......Page 625
A.1 Random Experiments and Probability Spaces......Page 628
A.2 Random Variables and Probability Distributions......Page 630
A.2.1 Probability Density......Page 633
A.2.2 Joint Distributions......Page 634
A.3 Expectation and Variance......Page 635
A.3.1 Properties of the Expectation......Page 637
A.3.2 Variance......Page 638
A.4.2 Independence......Page 639
A.4.3 Covariance......Page 640
A.4.4 Conditional Density and Expectation......Page 641
A.5 Lp Space......Page 642
A.6.2 General Transformations......Page 643
A.7.2 Moment Generating Function and Laplace Transform......Page 644
A.7.3 Characteristic Function......Page 645
A.8.1 Modes of Convergence......Page 646
A.8.2 Converse Results on Modes of Convergence......Page 647
A.8.3 Law of Large Numbers and Central Limit Theorem......Page 648
A.9 Stochastic Processes......Page 649
A.9.1 Gaussian Property......Page 650
A.9.2 Markov Property......Page 651
A.9.3 Martingale Property......Page 652
A.9.4 Regenerative Property......Page 653
A.9.5 Stationarity and Reversibility......Page 654
A. 10 Markov Chains......Page 655
A.10.2 Limiting Behavior......Page 656
A.11 Markov Jump Processes......Page 658
A.11.1 Limiting Behavior......Page 661
A.12 Itô Integral and Itô Processes......Page 662
A.13 Diffusion Processes......Page 666
A.13.1 Kolmogorov Equations......Page 669
A.13.3 Feynman-Kac Formula......Page 671
A.13.4 Exit Times......Page 672
References......Page 673
B.1 Statistical Inference......Page 676
B.1.1 Classical Models......Page 677
B.1.2 Sufficient Statistics......Page 678
B.1.3 Estimation......Page 679
B.1.4 Hypothesis Testing......Page 683
B.2 Likelihood......Page 687
B.2.1 Likelihood Methods for Estimation......Page 690
B.2.2 Numerical Methods for Likelihood Maximization......Page 692
B.2.3 Likelihood Methods for Hypothesis Testing......Page 694
B.3 Bayesian Statistics......Page 695
B.3.1 Conjugacy......Page 698
References......Page 699
C.1 Optimization Theory......Page 700
C.1.1 Lagrangian Method......Page 706
C.1.2 Duality......Page 707
C.2.1 Transformation of Constrained Problems......Page 708
C.2.2 Numerical Methods for Optimization and Root Finding......Page 710
C.3.2 Knapsack Problem......Page 717
C.3.5 Quadratic Assignment Problem......Page 718
C.4.1 Unconstrained Problems......Page 719
C.4.2 Constrained Problems......Page 720
References......Page 722
D.l Exponential Families......Page 724
D.2.1 Tail Properties......Page 726
D.2.2 Stability Properties......Page 728
D.4 Discrete Fourier Transform, FFT, and Circulant Matrices......Page 729
D.5 Discrete Cosine Transform......Page 731
D.6 Differentiation......Page 732
D.7 Expectation-Maximization (EM) Algorithm......Page 734
D.8 Poisson Summation Formula......Page 737
D.9.3 Error Function erf (x)......Page 738
D.9.7 Hypergeometric Function 2F1( a, b;c;z)......Page 739
References......Page 740
Acronyms and Abbreviations......Page 742
List of Symbols......Page 744
List of Distributions......Page 747
Index......Page 750