A Guide to Simulation

1 Introduction.- 1.1. Systems, Models, and Simulation.- 1.2. Verification, Approximation, and Validation.- 1.2.1. Verifying a Program.- 1.2.2. Approximation and Validation.- 1.3. States, Events, and Clocks.- 1.4. Simulation-Types and Examples.- 1.4.1. Synchronous and Asynchronous Discrete-Event Simulation.- 1.4.2. Continuous Simulation.- 1.4.3. Hybrid Simulation.- 1.5. Introduction to Random Numbers.- 1.6. Perspective on Experimental Design and Estimation.- 1.7. Clock Mechanisms.- 1.8. Hints for Simulation Programming.- 1.9. Miscellaneous Problems.- 2 Variance Reduction.- 2.1. Common Random Numbers.- 2.1.1. Informal Approach.- 2.1.2. Formal Development.- 2.1.3. Auxiliary Results.- 2.2. Antithetic Variates.- 2.3. Control Variates.- 2.4. Stratification.- 2.5. Importance Sampling.- 2.6. Conditional Monte Carlo.- 2.7. Jackknifing.- 3 Output Analysis.- 3.1. Introduction.- 3.1.1. Finite-Horizon Versus Steady-State Performance.- 3.1.2. Fixed Sample Size Versus Sequential Sampling.- 3.2. Analysis of Finite-Horizon Performance.- 3.2.1. Absolute Performance Estimation.- 3.2.2. Relative Performance Estimation.- 3.3. Analysis of Steady-State Performance.- 3.3.1. Batch Means.- 3.3.2. Regenerative Methods.- 3.3.3. Spectral Analysis Methods.- 3.3.4. Autoregressive Methods.- 3.3.5. Recommendations.- 3.4. Analysis of Transaction-Based Performance.- 3.5. Indirect Estimation via r = ?s.- 3.6. Problems.- 3.7. Renewal Theory Primer.- 3.8. Standardized Time Series.- 3.8.1. Steady State.- 3.8.2. Transients.- 4 Rational Choice of Input Distributions.- 4.1. Addition and the Normal Distribution.- 4.2. Multiplication and the Lognormal.- 4.3. Memorylessness and the Exponential.- 4.4. Superposition, the Poisson, and the Exponential.- 4.5. Minimization and the Weibull Distribution.- 4.6. A Mixed Empirical and Exponential Distribution.- 4.7. Extreme Values and Spacings.- 4.8. When Not to Use a Theoretical Distribution.- 4.9. Nonstationary Poisson Processes.- 5 Nonuniform Random Numbers.- 5.1. Introduction.- 5.2. General Methods.- 5.2.1. Inversion.- 5.2.2. Tabular Approximation of the Inverse Transform.- 5.2.3. Empirical cdf's.- 5.2.4. A Mixed Empirical and Exponential Distribution.- 5.2.5. Rejection.- 5.2.6. Generalized Rejection.- 5.2.7. Composition.- 5.2.8. The Alias Method for Discrete Distributions.- 5.2.9. Functional Approximations of the Inverse Transform.- 5.2.10. Other Ingenious Methods.- 5.3. Continuous Distributions.- 5.3.1. The Nonstandard Normal Distribution.- 5.3.2. The Multivariate (Dependent) Normal Distribution.- 5.3.3. Symmetric Stable Variates.- 5.3.4. The Cauchy Distribution.- 5.3.5. The Lognormal Distribution.- 5.3.6. The Exponential Distribution.- 5.3.7. The Hyperexponential Distribution.- 5.3.8. The Laplace and Exponential Power Distributions.- 5.3.9. Erlang and Gamma Distributions.- 5.3.10. The Beta Distribution.- 5.3.11. The Chi-square Distribution.- 5.3.12. The F-Distribution.- 5.3.13. The t-Distribution.- 5.3.14. The Weibull Distribution.- 5.3.15. The Gumbel Distribution.- 5.3.16. The Logistic Distribution.- 5.3.17. The Generalized Lambda Distribution.- 5.3.18. Nonhomogeneous Poisson Processes.- 5.4. Discrete Distributions.- 5.4.1. The Binomial Distribution.- 5.4.2. The Poisson Distribution.- 5.4.3. Compound Poisson Distributions.- 5.4.4. The Hypergeometric Distribution.- 5.4.5. The Geometric Distribution.- 5.4.6. The Negative Binomial and Pascal Distributions.- 5.4.7. Multidimensional Poisson Distributions.- 5.5. Problems.- 5.6. Timings.- 6 Uniform Random Numbers.- 6.1. Random Introductory Remarks.- 6.2. What Constitutes Randomness.- 6.3. Classes of Generators.- 6.3.1. Random Devices.- 6.3.2. Tables.- 6.3.3. The Midsquare Method.- 6.3.4. Fibonacci and Additive Congruential Generators.- 6.3.5. Linear Congruential Generators.- 6.3.6. Linear Recursion mod 2 Generators.- 6.3.7. Combinations of Generators.- 6.4. Choosing a Good Generator Based on Theoretical Considerations.- 6.4.1. Serial Correlation of Linear Congruential Generators.- 6.4.2. Cycle Length of Linear Congruential Generators.- 6.4.3. Cycle Length for Tausworthe Generators.- 6.4.4. The Spectral Test.- 6.5. Implementation of Uniform Random Number Generators.- 6.5.1. Multiplicative Generator With Modulus 2.- 6.5.2. Multiplicative Generators With Prime Modulus.- 6.5.3. Implementing the Tausworthe Generator.- 6.6. Empirical Testing of Uniform Random Number Generators.- 6.6.1. Chi-square Tests.- 6.6.2. Kolmogorov-Smirnov Tests.- 6.6.3. Tests Specifically for Uniform Random Number Sequences.- 6.7. Proper Use of a Uniform Random Number Generator.- 6.7.1. Generating Random Integers Uniform Over an Arbitrary Interval.- 6.7.2. Nonrandomness in the Low-order Bits of Multiplicative Generators.- 6.7.3. Linear Congruential Generators and the Box-Muller Method.- 6.8. Exploiting Special Features of Uniform Generators.- 6.8.1. Generating Antithetic Variates With a Multiplicative Congruential Generator.- 6.8.2. Generating a Random Number Stream in Reverse Order.- 6.8.3. Generating Disjoint Sequences.- 7 Simulation Programming.- 7.1. Simulation With General-Purpose Languages.- 7.1.1. The Simplest Possible Clock Mechanism.- 7.1.2. Generating Random Variates.- 7.1.3. Data Structures in Fortran.- 7.1.4. A Complete Simulation in Fortran.- 7.1.5. Fortran Simulation Packages.- 7.1.6. Our Standard Example-the Naive Approach.- 7.1.7. Simulation Using Pascal.- 7.2. Simscript.- 7.2.1. Data Structures in Simscript.- 7.2.2. Simscript and Simulation.- 7.2.3. A Complete Simulation in Simscript.- 7.2.4. The Standard Example in Simscript.- 7.2.5. Processes and Resources.- 7.2.6. Summing-up.- 7.3. GPSS.- 7.3.1. The Basic Concepts.- 7.3.2. Resources in GPSS.- 7.3.3. Generating Random Variates.- 7.3.4. A Complete Simulation in GPSS.- 7.3.5. The Standard Example in GPSS.- 7.3.6. Summing-up.- 7.4. Simula.- 7.4.1. The Class Concept in Simula.- 7.4.2. Simulation Using System Classes and Procedures.- 7.4.3. A Complete Simulation in Simula.- 7.4.4. Demos.- 7.4.5. The Standard Example in Simula With Demos.- 7.4.6. Summing-up.- 7.5. General Considerations in Simulation Programming.- 7.5.1. Language Design.- 7.5.2. System Considerations in Simulation.- 7.5.3. Statistical Considerations.- 8 Programming to Reduce the Variance.- 8.1. Choosing an Input Distribution.- 8.1.1. Using an Exact Method.- 8.1.2. Inverting a Tabulated Distribution.- 8.1.3. Using a Mixed Empirical and Exponential Distribution.- 8.1.4. Testing Robustness.- 8.2. Common Random Numbers.- 8.3. Antithetic Variates.- 8.4. Control Variates.- 8.4.1. The Simple Approach.- 8.4.2. Regression With Splitting.- 8.4.3. Regression With Jackknifing.- 8.5. Stratified Sampling.- 8.6. Importance Sampling.- 8.7. Conditional Monte Carlo.- 8.8. Summary.- Appendix A The Shapiro-Wilk Test for Normality.- Appendix L Routines for Random Number Generation.- Appendix X Examples of Simulation Programming.- References.- Author Index.