Handbooks in Operations Research and Management Science: Simulation, Volume 13 (Handbooks in Operations Research and Management Science)

This Handbook is a collection of chapters on key issues in the design and analysis of computer simulation experiments on models of stochastic systems. The chapters are tightly focused and written by experts in each area. For the purpose of this volume ''simulation'' refers to the analysis of stochastic processes through the generation of sample paths (realization) of the processes. Attention focuses on design and analysis issues and the goal of this volume is to survey the concepts, principles, tools and techniques that underlie the theory and practice of stochastic simulation design and analysis. Emphasis is placed on the ideas and methods that are likely to remain an intrinsic part of the foundation of the field for the foreseeable future. The chapters provide up-to-date references for both the simulation researcher and the advanced simulation user, but they do not constitute an introductory level 'how to' guide. Computer scientists, financial analysts, industrial engineers, management scientists, operations researchers and many other professionals use stochastic simulation to design, understand and improve communications, financial, manufacturing, logistics, and service systems. A theme that runs throughout these diverse applications is the need to evaluate system performance in the face of uncertainty, including uncertainty in user load, interest rates, demand for product, availability of goods, cost of transportation and equipment failures. * Tightly focused chapters written by experts * Surveys concepts, principles, tools, and techniques that underlie the theory and practice of stochastic simulation design and analysis * Provides an up-to-date reference for both simulation researchers and advanced simulation users Scope of the Handbook......Page 1 A processing network problem......Page 4 A stochastic activity network problem......Page 14 Organization of the Handbook......Page 17 References......Page 18 Introduction......Page 19 Static simulation: Activity networks......Page 21 A model of ambulance operations......Page 27 Finite-horizon performance......Page 28 Steady-state simulation......Page 34 Multiple ambulances......Page 46 Proof of Proposition 15......Page 50 References......Page 52 Introduction......Page 54 Generators based on a deterministic recurrence......Page 55 Quality criteria......Page 56 Links with highly-uniform point sets for quasi-Monte Carlo integration......Page 57 Statistical testing......Page 58 The multiple recursive generator......Page 59 The lattice structure......Page 60 MRG implementation techniques......Page 63 Combined MRGs and LCGs......Page 65 Linear recurrences with carry......Page 66 Computer searches for good parameters and an example......Page 67 A general framework......Page 68 Measures of equidistribution......Page 69 Lattice structure in spaces of polynomials and formal series......Page 70 The LFSR generator......Page 71 The GFSR and twisted GFSR......Page 72 An example......Page 73 Nonlinear RNGs......Page 74 Empirical statistical tests......Page 75 Conclusion, future work and open issues......Page 76 References......Page 77 The main paradigms......Page 81 The inversion method......Page 82 Simple transformations......Page 83 Inversion for integer-valued random variables......Page 86 Mixture methods......Page 87 The rejection method......Page 88 Rejection: a more advanced example......Page 89 The alternating series method......Page 91 Uniformly bounded times......Page 92 Universal generators......Page 95 Indirect problems......Page 97 Characteristic functions......Page 98 Fourier coefficients......Page 99 The moments are known......Page 100 The moment generating function......Page 101 Hazard rates......Page 102 A distributional identity......Page 103 Kolmogorov and Lévy measures......Page 104 Random processes......Page 105 Markov chain methodology......Page 106 The Metropolis-Hastings chain......Page 107 The discrete Metropolis chain......Page 108 Letac's lower bound......Page 109 The Metropolis random walk......Page 110 Universal generators......Page 111 Coupling from the past......Page 112 References......Page 114 Introduction......Page 120 Acceptance/rejection method......Page 123 Conditional distributions......Page 124 Method of copulas......Page 126 Bézier distributions......Page 127 Kernel density estimation......Page 129 Parametric families of joint distributions......Page 130 Constructing partially specified joint distributions......Page 133 Measures of dependence......Page 134 Multivariate time series......Page 137 Transformation-based methods......Page 138 ARTA, NORTA and VARTA processes......Page 139 Chessboard distributions......Page 142 Vine copula method......Page 143 TES processes......Page 144 Mixture methods......Page 145 Conclusion......Page 146 References......Page 147 Arrival processes......Page 151 Poisson processes......Page 152 Variants of Poisson processes......Page 153 Nonhomogeneous Poisson processes......Page 154 Other variants......Page 155 Poisson, renewal and alternating renewal processes......Page 156 Nonhomogeneous Poisson processes......Page 157 Renewal processes......Page 161 Nonhomogeneous Poisson process......Page 162 Hazard-based methods......Page 163 Definitions......Page 164 Competing risks......Page 165 Accelerated life model......Page 166 Lifetime generation......Page 167 Generating random objects......Page 168 Generating a random combination of k integers from {1, 2, ..., n }......Page 169 Random matrices......Page 170 Generating correlation matrices......Page 171 Number of real eigenvalues......Page 172 Random polynomials......Page 173 References......Page 174 Introduction......Page 177 Random-number generation......Page 178 Random-structure generation......Page 180 Application to variance reduction......Page 182 Conclusions and suggestions......Page 185 References......Page 187 Introduction......Page 188 Background......Page 190 Sample averages and time averages......Page 191 Stationary processes......Page 194 Impact of dependence......Page 196 Ergodic and central limit theorems for stationary sequences......Page 197 Analyzing data from independent replications......Page 199 Sequential estimation......Page 200 Quantile estimation......Page 202 Using independent replications to estimate steady-state measures......Page 203 Density estimation......Page 205 The naive estimator......Page 206 Bandwidth selection......Page 207 The variable kernel estimator......Page 209 Bounded domains......Page 210 Density estimation for stationary processes......Page 211 Summary......Page 215 References......Page 217 Introduction......Page 219 Main concepts......Page 221 Bayesian modeling......Page 222 Loss and value of information......Page 227 Uncertainty analysis......Page 230 Computational issues......Page 231 Input distribution and model selection......Page 233 Joint input-output models......Page 234 Bayesian metamodeling......Page 235 Inference of input parameters from output information......Page 238 Ranking and selection......Page 239 Value of information procedures (VIPs)......Page 242 OCBA procedures......Page 243 Comments......Page 244 Discussion and future directions......Page 246 References......Page 247 Introduction......Page 252 Problem formulation and basic results......Page 253 Hilbert spaces......Page 256 A Hilbert space approach to control variates......Page 264 Conditional Monte Carlo in Hilbert space......Page 266 Control variates and conditional Monte Carlo from a Hilbert space perspective......Page 267 Weighted Monte Carlo......Page 268 Stratification techniques......Page 271 Latin hypercube sampling......Page 274 A numerical example......Page 279 Conclusions......Page 280 References......Page 281 Introduction......Page 283 An illustrative example......Page 286 Naive simulation......Page 288 Importance sampling......Page 289 Characterizing good importance sampling distributions......Page 290 Uniformly bounded likelihood ratios......Page 292 Rare-event simulation in a Markovian framework......Page 294 Importance sampling in a Markovian framework......Page 297 Zero-variance measure in Markovian settings......Page 299 Exponentially twisted distributions......Page 300 Random walk in a rare set......Page 301 Probability of hitting a rare set......Page 305 Adaptive importance sampling techniques......Page 308 The zero-variance measure......Page 309 The adaptive Monte Carlo method......Page 310 The cross-entropy method......Page 311 The adaptive stochastic approximation based algorithm......Page 314 Multiplicative Poisson equation and conditional measures......Page 315 Brief review of adaptive schemes in other contexts......Page 318 Single queues......Page 319 Queueing networks......Page 320 Heavy-tailed simulations......Page 322 Financial engineering applications......Page 327 Approaches for importance sampling......Page 330 A light-tailed simulation framework......Page 331 Heavy-tailed value-at-risk: transformations to light tails......Page 332 Conditional importance sampling and zero-variance distributions......Page 333 Credit risk models......Page 336 References......Page 338 Introduction......Page 343 An example......Page 348 A functional ANOVA decomposition......Page 351 Effective dimension......Page 352 Relevance in the simulation context......Page 354 Reducing the effective dimension......Page 355 Constructing quasi-random point sets......Page 356 Lattice rules......Page 357 Digital nets and sequences......Page 358 Recurrence-based point sets......Page 361 Shift modulo 1......Page 363 Digital shift......Page 364 Scrambling......Page 365 Combination with other variance reduction techniques......Page 366 Future directions......Page 367 References......Page 368 Introduction......Page 372 Probability model of a simulation......Page 376 Bias, mean-squared error and variance......Page 377 The classical case: independent replications......Page 378 An initial segment from a single run......Page 381 The asymptotic parameters for a function of a Markov chain......Page 384 Continuous-time Markov chains......Page 385 Poisson's equation......Page 386 Birth-and-death processes......Page 387 Birth-and-death examples......Page 388 Diffusion processes......Page 392 Stochastic-process limits......Page 396 RBM approximations......Page 397 Many-server queues......Page 399 Deleting an initial portion of the run to reduce bias......Page 401 References......Page 402 Introduction......Page 405 The bootstrap concept......Page 407 Basic method......Page 409 Parametric bootstrap......Page 410 Quantiles......Page 412 Confidence intervals by direct bootstrapping......Page 413 Studentization......Page 414 Quantile methods......Page 416 Theory......Page 418 Convergence rates......Page 420 Asymptotic accuracy of EDFs......Page 423 Asymptotic accuracy of confidence intervals......Page 424 Failure of bootstrapping......Page 425 Direct models......Page 426 Metamodels......Page 427 Linear metamodels......Page 428 Uses of metamodels......Page 430 Metamodel comparison and selection......Page 431 Bootstrap comparisons......Page 433 Goodness-of-fit and validation......Page 434 Comparison of different systems......Page 435 Bayesian models......Page 436 Residual sampling......Page 438 Block sampling......Page 439 Spectral resampling......Page 440 References......Page 441 Introduction......Page 444 Motivation......Page 446 Estimators using nonoverlapping batches......Page 448 NBM estimator......Page 449 STS primer......Page 451 Batched area estimator......Page 452 Batched CvM estimator......Page 454 Comparison......Page 456 Overlapping fundamentals......Page 457 OBM estimator......Page 458 Overlapping area estimator......Page 459 Overlapping CvM estimator......Page 460 Comparison......Page 461 Summary and conclusions......Page 462 References......Page 463 Introduction......Page 465 The steady-state simulation problem......Page 466 The regenerative estimator for the TAVC......Page 468 Choice of the optimal regeneration state......Page 471 The regenerative approach to the initial transient and initial bias problems......Page 472 When is a simulation regenerative?......Page 475 When is a GSMP regenerative?......Page 477 Algorithmic identification of regenerative structure......Page 478 A martingale perspective on regeneration......Page 481 Efficiency improvement via regeneration: Computing steady state gradients......Page 484 Efficiency improvement via regeneration: Computing infinite horizon discounted reward......Page 486 References......Page 487 Introduction......Page 489 Basics of ranking and selection......Page 490 Subset-selection formulation......Page 491 Indifference-zone formulation......Page 492 Connection to multiple comparisons......Page 495 Unknown and unequal variances......Page 496 Initial sample size problem......Page 499 Nonnormality of output data......Page 500 Common random numbers......Page 501 The sequential nature of simulation......Page 502 Large number of alternatives......Page 504 Example procedures......Page 505 Application......Page 509 Asymptotic analysis......Page 510 Asymptotic probability of correct selection......Page 511 Asymptotic efficiency......Page 512 Asymptotic sample size......Page 513 Comparisons with a standard......Page 514 Selecting the system most likely to be the best......Page 515 Selecting the largest probability of success......Page 517 Future directions......Page 519 References......Page 520 Introduction......Page 523 Metamodels and simulation......Page 526 Response surface metamodels......Page 527 Regression spline metamodels......Page 528 Spatial correlation (kriging) metamodels......Page 529 Neural network metamodels......Page 531 Metamodel-based optimization......Page 533 Origins and strategy of RSM......Page 536 Choosing a local metamodel form (L2)......Page 537 Designing local metamodel fitting experiments (L3)......Page 540 Replicate runs and variance reduction methods......Page 541 Assessing the adequacy of the metamodel fit (L5/L6/L7)......Page 542 Conducting simulation runs in the search direction (L8/L9)......Page 543 Validation of the optimum: checking performance (L9/L10)......Page 544 Selecting the design region (L1)......Page 545 Check model adequacy: [text=Phase I]ph1 (L5/L6/L7)......Page 546 Conducting simulation runs in the search direction: [text=Phase I]ph1 (L8/L9)......Page 547 Check Model Adequacy: [text=Phase II]ph2 (L5/L6/L7)......Page 549 Conducting simulation runs in the search direction: [text=Phase II]ph2 (L8/L9)......Page 550 Motivation and strategy......Page 551 Selecting the design region (G1)......Page 552 Experiment design (G3)......Page 553 Checking model adequacy (G5, G6, G7)......Page 554 An alternative global `metamodel' based on steady-state behavior......Page 556 Summary......Page 557 References......Page 558 Introduction......Page 563 Gradient-based simulation optimization......Page 565 Stochastic approximation......Page 566 Finite differences......Page 568 Simultaneous perturbations......Page 569 Direct gradient estimation......Page 571 Derivatives of random variables......Page 576 Derivatives of measures......Page 579 Input distribution examples......Page 581 Stochastic activity network......Page 586 Single-server queue......Page 587 (s,S) inventory system......Page 591 Basic theoretical tools......Page 593 Simple guidelines for the simulation practitioner......Page 594 Applications......Page 595 Probing further......Page 597 Future research directions......Page 599 References......Page 600 Introduction......Page 605 A brief review of random search methods......Page 607 Convergence......Page 609 Efficiency......Page 612 Summary......Page 617 References......Page 618 Introduction......Page 620 Background to metaheuristics......Page 622 Accounting for simulation noise......Page 627 Genetic algorithm......Page 630 Tabu search......Page 631 The nested partition method......Page 633 Making convergence statements......Page 634 Future directions......Page 639 References......Page 640 Author Index......Page 642 Subject Index......Page 654 This Handbook is a collection of chapters on key issues in the design and analysis of computer simulation experiments on models of stochastic systems. The chapters are tightly focused and written by experts in each area. For the purpose of this volume “simulation” refers to the analysis of stochastic processes through the generation of sample paths (realization) of the processes.

Attention focuses on design and analysis issues and the goal of this volume is to survey the concepts, principles, tools and techniques that underlie the theory and practice of stochastic simulation design and analysis. Emphasis is placed on the ideas and methods that are likely to remain an intrinsic part of the foundation of the field for the foreseeable future. The chapters provide up-to-date references for both the simulation researcher and the advanced simulation user, but they do not constitute an introductory level ‘how to’ guide.

Computer scientists, financial analysts, industrial engineers, management scientists, operations researchers and many other professionals use stochastic simulation to design, understand and improve communications, financial, manufacturing, logistics, and service systems. A theme that runs throughout these diverse applications is the need to evaluate system performance in the face of uncertainty, including uncertainty in user load, interest rates, demand for product, availability of goods, cost of transportation and equipment failures.

* Tightly focused chapters written by experts
* Surveys concepts, principles, tools, and techniques that underlie the theory and practice of stochastic simulation design and analysis
* Provides an up-to-date reference for both simulation researchers and advanced simulation users