CONTENTS

Preface xvii
Acknowledgments xix

1 Uniform Random Number Generation 1

1.1 Random Numbers 1
1.1.1 Properties of a Good Random Number Generator 2
1.1.2 Choosing a Good Random Number Generator 3
1.2 Generators Based on Linear Recurrences 4
1.2.1 Linear Congruential Generators 4
1.2.2 Multiple-Recursive Generators 5
1.2.3 Matrix Congruential Generators 6
1.2.4 Modulo 2 Linear Generators 6
1.3 Combined Generators 8
1.4 Other Generators 10
1.5 Tests for Random Number Generators 11
1.5.1 Spectral Test 12
1.5.2 Empirical Tests 14
References 21

vii
viii CONTENTS

2 Quasirandom Number Generation 25

2.1 Multidimensional Integration 25
2.2 Van der Corput and Digital Sequences 27
2.3 Halton Sequences 29
2.4 Faure Sequences 31
2.5 Sobol’ Sequences 33
2.6 Lattice Methods 36
2.7 Randomization and Scrambling 38
References 40

3 Random Variable Generation 43

3.1 Generic Algorithms Based on Common Transformations 44
3.1.1 Inverse-Transform Method 45
3.1.2 Other Transformation Methods 47
3.1.3 Table Lookup Method 55
3.1.4 Alias Method 56
3.1.5 Acceptance–Rejection Method 59
3.1.6 Ratio of Uniforms Method 66
3.2 Generation Methods for Multivariate Random Variables 67
3.2.1 Copulas 68
3.3 Generation Methods for Various Random Objects 70
3.3.1 Generating Order Statistics 70
3.3.2 Generating Uniform Random Vectors in a Simplex 71
3.3.3 Generating Random Vectors Uniformly Distributed in
a Unit Hyperball and Hypersphere 74
3.3.4 Generating Random Vectors Uniformly Distributed in
a Hyperellipsoid 75
3.3.5 Uniform Sampling on a Curve 75
3.3.6 Uniform Sampling on a Surface 76
3.3.7 Generating Random Permutations 79
3.3.8 Exact Sampling From a Conditional Bernoulli
Distribution 80
References 83

4 Probability Distributions 85
4.1 Discrete Distributions 85
4.1.1 Bernoulli Distribution 85
4.1.2 Binomial Distribution 86
4.1.3 Geometric Distribution 91
4.1.4 Hypergeometric Distribution 93
4.1.5 Negative Binomial Distribution 94
 CONTENTS ix

4.1.6 Phase-Type Distribution (Discrete Case) 96

4.1.7 Poisson Distribution 98
4.1.8 Uniform Distribution (Discrete Case) 101
4.2 Continuous Distributions 102
4.2.1 Beta Distribution 102
4.2.2 Cauchy Distribution 106
4.2.3 Exponential Distribution 108
4.2.4 F Distribution 109
4.2.5 Fréchet Distribution 111
4.2.6 Gamma Distribution 112
4.2.7 Gumbel Distribution 116
4.2.8 Laplace Distribution 118
4.2.9 Logistic Distribution 119
4.2.10 Log-Normal Distribution 120
4.2.11 Normal Distribution 122
4.2.12 Pareto Distribution 125
4.2.13 Phase-Type Distribution (Continuous Case) 126
4.2.14 Stable Distribution 129
4.2.15 Student’s t Distribution 131
4.2.16 Uniform Distribution (Continuous Case) 134
4.2.17 Wald Distribution 135
4.2.18 Weibull Distribution 137
4.3 Multivariate Distributions 138
4.3.1 Dirichlet Distribution 139
4.3.2 Multinomial Distribution 141
4.3.3 Multivariate Normal Distribution 143
4.3.4 Multivariate Student’s t Distribution 147
4.3.5 Wishart Distribution 148
References 150

5 Random Process Generation 153

5.1 Gaussian Processes 154
5.1.1 Markovian Gaussian Processes 159
5.1.2 Stationary Gaussian Processes and the FFT 160
5.2 Markov Chains 162
5.3 Markov Jump Processes 166
5.4 Poisson Processes 170
5.4.1 Compound Poisson Process 174
5.5 Wiener Process and Brownian Motion 177
5.6 Stochastic Differential Equations and Diffusion Processes 183
5.6.1 Euler’s Method 185
5.6.2 Milstein’s Method 187
x CONTENTS

5.6.3 Implicit Euler 188

5.6.4 Exact Methods 189
5.6.5 Error and Accuracy 191
5.7 Brownian Bridge 193
5.8 Geometric Brownian Motion 196
5.9 Ornstein–Uhlenbeck Process 198
5.10 Reflected Brownian Motion 200
5.11 Fractional Brownian Motion 203
5.12 Random Fields 206
5.13 Lévy Processes 208
5.13.1 Increasing Lévy Processes 211
5.13.2 Generating Lévy Processes 214
5.14 Time Series 219
References 222

6 Markov Chain Monte Carlo 225

6.1 Metropolis–Hastings Algorithm 226
6.1.1 Independence Sampler 227
6.1.2 Random Walk Sampler 230
6.2 Gibbs Sampler 233
6.3 Specialized Samplers 240
6.3.1 Hit-and-Run Sampler 240
6.3.2 Shake-and-Bake Sampler 251
6.3.3 Metropolis–Gibbs Hybrids 256
6.3.4 Multiple-Try Metropolis–Hastings 257
6.3.5 Auxiliary Variable Methods 259
6.3.6 Reversible Jump Sampler 269
6.4 Implementation Issues 273
6.5 Perfect Sampling 274
References 276

7 Discrete Event Simulation 281

7.1 Simulation Models 281
7.2 Discrete Event Systems 283
7.3 Event-Oriented Approach 285
7.4 More Examples of Discrete Event Simulation 289
7.4.1 Inventory System 289
7.4.2 Tandem Queue 293
7.4.3 Repairman Problem 296
References 300
 CONTENTS xi

8 Statistical Analysis of Simulation Data 301

8.1 Simulation Data 301
8.1.1 Data Visualization 302
8.1.2 Data Summarization 303
8.2 Estimation of Performance Measures for Independent Data 305
8.2.1 Delta Method 308
8.3 Estimation of Steady-State Performance Measures 309
8.3.1 Covariance Method 309
8.3.2 Batch Means Method 311
8.3.3 Regenerative Method 313
8.4 Empirical Cdf 316
8.5 Kernel Density Estimation 319
8.5.1 Least Squares Cross Validation 321
8.5.2 Plug-in Bandwidth Selection 326
8.6 Resampling and the Bootstrap Method 331
8.7 Goodness of Fit 333
8.7.1 Graphical Procedures 334
8.7.2 Kolmogorov–Smirnov Test 336
8.7.3 Anderson–Darling Test 339
8.7.4 χ2 Tests 340
References 343

9 Variance Reduction 347

9.1 Variance Reduction Example 348
9.2 Antithetic Random Variables 349
9.3 Control Variables 351
9.4 Conditional Monte Carlo 354
9.5 Stratified Sampling 356
9.6 Latin Hypercube Sampling 360
9.7 Importance Sampling 362
9.7.1 Minimum-Variance Density 363
9.7.2 Variance Minimization Method 364
9.7.3 Cross-Entropy Method 366
9.7.4 Weighted Importance Sampling 368
9.7.5 Sequential Importance Sampling 369
9.7.6 Response Surface Estimation via Importance Sampling 373
9.8 Quasi Monte Carlo 376
References 379
xii CONTENTS

10 Rare-Event Simulation 381

10.1 Efficiency of Estimators 382
10.2 Importance Sampling Methods for Light Tails 385
10.2.1 Estimation of Stopping Time Probabilities 386
10.2.2 Estimation of Overflow Probabilities 389
10.2.3 Estimation For Compound Poisson Sums 391
10.3 Conditioning Methods for Heavy Tails 393
10.3.1 Estimation for Compound Sums 394
10.3.2 Sum of Nonidentically Distributed Random Variables 396
10.4 State-Dependent Importance Sampling 398
10.5 Cross-Entropy Method for Rare-Event Simulation 404
10.6 Splitting Method 409
References 416

11 Estimation of Derivatives 421

11.1 Gradient Estimation 421
11.2 Finite Difference Method 423
11.3 Infinitesimal Perturbation Analysis 426
11.4 Score Function Method 428
11.4.1 Score Function Method With Importance Sampling 430
11.5 Weak Derivatives 433
11.6 Sensitivity Analysis for Regenerative Processes 435
References 438

12 Randomized Optimization 441

12.1 Stochastic Approximation 441
12.2 Stochastic Counterpart Method 446
12.3 Simulated Annealing 449
12.4 Evolutionary Algorithms 452
12.4.1 Genetic Algorithms 452
12.4.2 Differential Evolution 454
12.4.3 Estimation of Distribution Algorithms 456
12.5 Cross-Entropy Method for Optimization 457
12.6 Other Randomized Optimization Techniques 460
References 461

13 Cross-Entropy Method 463

13.1 Cross-Entropy Method 463
13.2 Cross-Entropy Method for Estimation 464
13.3 Cross-Entropy Method for Optimization 468
13.3.1 Combinatorial Optimization 469
 CONTENTS xiii

13.3.2 Continuous Optimization 471

13.3.3 Constrained Optimization 473
13.3.4 Noisy Optimization 476
References 477

14 Particle Methods 481

14.1 Sequential Monte Carlo 482
14.2 Particle Splitting 485
14.3 Splitting for Static Rare-Event Probability Estimation 486
14.4 Adaptive Splitting Algorithm 493
14.5 Estimation of Multidimensional Integrals 495
14.6 Combinatorial Optimization via Splitting 504
14.6.1 Knapsack Problem 505
14.6.2 Traveling Salesman Problem 506
14.6.3 Quadratic Assignment Problem 508
14.7 Markov Chain Monte Carlo With Splitting 509
References 517

15 Applications to Finance 521

15.1 Standard Model 521
15.2 Pricing via Monte Carlo Simulation 526
15.3 Sensitivities 538
15.3.1 Pathwise Derivative Estimation 540
15.3.2 Score Function Method 542
References 546

16 Applications to Network Reliability 549

16.1 Network Reliability 549
16.2 Evolution Model for a Static Network 551
16.3 Conditional Monte Carlo 554
16.3.1 Leap–Evolve Algorithm 560
16.4 Importance Sampling for Network Reliability 562
16.4.1 Importance Sampling Using Bounds 562
16.4.2 Importance Sampling With Conditional Monte Carlo 565
16.5 Splitting Method 567
16.5.1 Acceleration Using Bounds 573
References 574

17 Applications to Differential Equations 577

17.1 Connections Between Stochastic and Partial Differential
Equations 577
xiv CONTENTS

17.1.1 Boundary Value Problems 579

17.1.2 Terminal Value Problems 584
17.1.3 Terminal–Boundary Problems 585
17.2 Transport Processes and Equations 587
17.2.1 Application to Transport Equations 589
17.2.2 Boltzmann Equation 593
17.3 Connections to ODEs Through Scaling 597
References 602

Appendix A: Probability and Stochastic Processes 605

A.1 Random Experiments and Probability Spaces 605
A.1.1 Properties of a Probability Measure 607
A.2 Random Variables and Probability Distributions 607
A.2.1 Probability Density 610
A.2.2 Joint Distributions 611
A.3 Expectation and Variance 612
A.3.1 Properties of the Expectation 614
A.3.2 Variance 615
A.4 Conditioning and Independence 616
A.4.1 Conditional Probability 616
A.4.2 Independence 616
A.4.3 Covariance 617
A.4.4 Conditional Density and Expectation 618
A.5 Lp Space 619
A.6 Functions of Random Variables 620
A.6.1 Linear Transformations 620
A.6.2 General Transformations 620
A.7 Generating Function and Integral Transforms 621
A.7.1 Probability Generating Function 621
A.7.2 Moment Generating Function and Laplace Transform 621
A.7.3 Characteristic Function 622
A.8 Limit Theorems 623
A.8.1 Modes of Convergence 623
A.8.2 Converse Results on Modes of Convergence 624
A.8.3 Law of Large Numbers and Central Limit Theorem 625
A.9 Stochastic Processes 626
A.9.1 Gaussian Property 627
A.9.2 Markov Property 628
A.9.3 Martingale Property 629
A.9.4 Regenerative Property 630
A.9.5 Stationarity and Reversibility 631
A.10 Markov Chains 632
 CONTENTS xv

A.10.1 Classification of States 633

A.10.2 Limiting Behavior 633
A.10.3 Reversibility 635
A.11 Markov Jump Processes 635
A.11.1 Limiting Behavior 638
A.12 Itô Integral and Itô Processes 639
A.13 Diffusion Processes 643
A.13.1 Kolmogorov Equations 646
A.13.2 Stationary Distribution 648
A.13.3 Feynman–Kac Formula 648
A.13.4 Exit Times 649
References 650

Appendix B: Elements of Mathematical Statistics 653

B.1 Statistical Inference 653
B.1.1 Classical Models 654
B.1.2 Sufficient Statistics 655
B.1.3 Estimation 656
B.1.4 Hypothesis Testing 660
B.2 Likelihood 664
B.2.1 Likelihood Methods for Estimation 667
B.2.2 Numerical Methods for Likelihood Maximization 669
B.2.3 Likelihood Methods for Hypothesis Testing 671
B.3 Bayesian Statistics 672
B.3.1 Conjugacy 675
References 676

Appendix C: Optimization 677

C.1 Optimization Theory 677
C.1.1 Lagrangian Method 683
C.1.2 Duality 684
C.2 Techniques for Optimization 685
C.2.1 Transformation of Constrained Problems 685
C.2.2 Numerical Methods for Optimization and Root Finding 687
C.3 Selected Optimization Problems 694
C.3.1 Satisfiability Problem 694
C.3.2 Knapsack Problem 694
C.3.3 Max-Cut Problem 695
C.3.4 Traveling Salesman Problem 695
C.3.5 Quadratic Assignment Problem 695
C.3.6 Clustering Problem 696
xvi CONTENTS

C.4 Continuous Problems 696

C.4.1 Unconstrained Problems 696
C.4.2 Constrained Problems 697
References 699

Appendix D: Miscellany 701

D.1 Exponential Families 701
D.2 Properties of Distributions 703
D.2.1 Tail Properties 703
D.2.2 Stability Properties 705
D.3 Cholesky Factorization 706
D.4 Discrete Fourier Transform, FFT, and Circulant Matrices 706
D.5 Discrete Cosine Transform 708
D.6 Differentiation 709
D.7 Expectation-Maximization (EM) Algorithm 711
D.8 Poisson Summation Formula 714
D.9 Special Functions 715
D.9.1 Beta Function B(α, β) 715
D.9.2 Incomplete Beta Function Ix (α, β) 715
D.9.3 Error Function erf(x) 715
D.9.4 Digamma function ψ(x) 716
D.9.5 Gamma Function Γ(α) 716
D.9.6 Incomplete Gamma Function P (α, x) 716
D.9.7 Hypergeometric Function 2 F1 (a, b; c; z) 716
D.9.8 Confluent Hypergeometric Function 1 F1 (α; γ; x) 717
D.9.9 Modified Bessel Function of the Second Kind Kν (x) 717
References 717

Acronyms and Abbreviations 719

List of Symbols 721

List of Distributions 724

Index 727