Crafts Of Simulation Programming

E Jack Chen

• Publisher: WSPC
• Year: 2016
• eBook ISBN: 9789814740197
• Topic: Mathematics
• Subtopic: Computer Science General
• Index: Mathematics

Crafts of Simulation Programs is a collection of tools, techniques and theories required to develop and implement simulation models on a computer. This timely book provides the various skills and techniques needed in simulation programming with general-purpose languages. The topics range in difficulty, and several latest fields in simulation output analysis are covered such as samples sizes, order statistics, ranking and selection, comparison with a control, selection with constraints, etc.Presented in the format of research project reports, detailed descriptions, important concepts and techniques are introduced and developed. Each chapter is relatively self-contained and can be used as a study unit. Algorithms have detailed implementations in C and are readable by anyone who has done a little programming. Many chapters include simulation results. It is designed to impart to the readers the statistical techniques used in simulation. This book will prove to be invaluable not only to students and researchers in the fields of simulation programming, but also to teachers of this subject who will find this text useful as a supplement.Contents:Basic Simulation ProgrammingSample Sizes and Stopping RulesGenerating Independent and Identically Distributed Batch MeansDistributions of Order StatisticsOrder Statistics from Correlated Normal Random VariablesHistogram and Quasi-Independent ProcedureMetamodelsDensity EstimationComparing Two AlternativesRanking and SelectionComputing Budget Allocation of Selection ProceduresUsing Common Random Numbers with Selection ProceduresParallel and Distributed SimulationMulti-Objective SelectionGeneric Selection with ConstraintsReadership: Undergraduate, graduate students, researchers and practitioners. Simulation; Random Number Generator; Order Statistics; Ranking and Selection; Quantile; Density

Chapter 1

Basic Simulation Programming

1.1Introduction

Computer simulation is the process of designing and creating a computerized model of a real or proposed system for the purpose of conducting experiments to give us a better understanding of the behavior of the system under study for a given set of conditions. Simulation studies have been used to investigate the characteristics of systems, to assess and analyze risks, for example, the probability of a machine breakdown.

Simulation studies are typically proceed by transforming in a more or less complicated way of a sequence of numbers between 0 and 1 produced by a pseudorandom generator into an observation of the measure of interest. A facility for generating sequences of pseudorandom numbers is a fundamental part of computer simulation systems.

1.2Random Numbers Generators

A portable set of software utilities is described for uniform random-number generation. It provides for multiple generators (streams) running simultaneously, and each generator (stream) has its sequence of numbers partitioned into many long disjoint contiguous substreams. Simple procedure calls allow users to make any generator “jump” ahead/back v steps (random numbers). Implementation issues are discussed. An efficient and portable code is also provided to implement the package.

A collection of random variables x₁, x₂, . . . , x_n random sample if they are independent and identically distributed (i.i.d.). True random numbers cannot be produced by a deterministic algorithm, and hence, random numbers generated by using a recursive equation are referred to as pseudo-random numbers. Usually, in practice, such deterministic algorithms produce a deterministic sequence of values, but externally these values should appear to be drawn independently from a uniform distribution between 0 and 1 (i.e., U(0, 1)). Furthermore, multiple independent streams of random numbers are often required in simulation studies, for instance, to facilitate synchronization for variance-reduction purposes, and for making independent replications. A random number generator (RNG) is an algorithm that starting from an initial seed (or seeds), produces a stream of numbers that behaves as if it was a random sample when analyzed using statistical tests. The RNG is closely related to the Deterministic Random Bit Generators (DRBGs). See [L’Ecuyer (1990)] and references therein for more information on RNGs. We describe a portable set of software utilities for uniform random-number generation. It provides for multiple generators (streams) running simultaneously, and each generator (stream) has its sequence of numbers partitioned into many long disjoint contiguous substreams. The basic underlying generator CMRG (Combined Multiple Recursive Generator) combines two multiple recursive random number generators with a period length of approximately 2¹⁹¹ (≈ 3.1 × 10⁵⁷), good speed, and excellent theoretical properties. See [L’Ecuyer et al. (2002)].

There are a number of methods for generating the random numbers, of which the most popular are the congruential methods (mixed, multiplicative, and additive). The (mixed) linear congruential generators (LCGs) are defined by

x_i = (ax_i−1 + c) mod m, u_i = x_i/m, x₀ ∈{1, · · · , m − 1}, i > 0.

Here m (the modulus) is a positive integer (usually a very large primary number), a (the multiplier) ∈ {0, 1, · · · , m − 1} and c (the increment) is a nonnegative integer. This mathematical notation signifies that x_i is the remainder of (ax_i−1 + c) divided by m. Hence, x_i ∈ {0, 1, · · · , m − 1}. Thus, random variable u_i is a uniform 0, 1 variable. Note that x_i+v = (a^vx_i + c(a^v − 1)/(a − 1)) mod m. Hence, every x_i is completely determined by m, a, c, and x₀. The sequence x_i repeats once it returns to a previously visited value. The period of a generator is the length of a generated steam before it begins to repeat. If u₀ = u_p (where p > 0), then the length p is called the period . The longest possible period for a LCG is m, i.e., m represents the desired number of different values that could be generated for the random numbers. Hence, the modulus m is often taken as a large prime number close to the largest integer directly representable on the computer (i.e., equal or near 2³¹ − 1 for 32-bit computers). If p = m, we say that the generator has full period. The required conditions on how to choose m, a, and c so that the corresponding LCGs will have full period are known, see [Knuth (1998)] or [Law (2014)].

When c > 0, the LCGs are called mixed LCGs. When c = 0, x_i = ax_i−1 mod m, u_i = x_i/m, x₀ ∈ {1, · · · , m − 1}, i > 0. These LCGs are called multiplicative LCGs. Note that if x_i = 0, then all subsequent x_i are identically 0. Thus, the longest possible period for a multiplicative LCG is m − 1. Furthermore, x_i+v = a^vx_i mod m. Most experts now recognize that small LCGs with moduli around 2³¹ or so should no longer be used as general-purpose random-number generators. Not only can one exhaust the period in a few minutes on a PC (personal computer), but more importantly the poor structure of the points can dramatically bias simulation results for sample sizes much smaller than the period length.

One way of extending the basic LCG is to combine two or more LCGs through summation. Another way of extending the basic LCG is to use a higher-order recursion. A multiple recursive random number generator (MRG) , which goes from integer to integer according to the recursion

x_i = (a₁x_i−1 + ··· + a_kx_i−k) mod m, u_i = x_i/m.

A seed x₀, . . . , x_k−2, x_k−1 ∈ {1, . . . , m − 1}, where i, k, and m are positive integers, and a₁, . . . , a_k ∈ {0, 1, . . . , m − 1}. To increase the efficiency and ease the implementation, the MRG algorithm usually set all but two a_i’s to 0. Furthermore, the nonzero a_i should be small. However, these conditions are generally in conflict with those required for having a good lattice structure and statistical robustness. See [Law (2014)] on the lattice structure of pseudorandom numbers. The longest possible period for a MRG is m^k − 1 [L’Ecuyer (1996)]. Other way of extending the basic LCG is the additive congruential RNG (ACRON). The ACRON sets a = 1 and replace c by some random number preceding x_i in the sequence, for example, x_i−1 (so that more than one seed is required to start calculating sequence). [Wilkrmaratna (2008)] indicated that the ACRON is a special case of a multiple recursive generator.

Other classes of RNGs are available, e.g., twisted generalized feedback shift register generators [Matsumoto and Nishimura (1998)]. The RNGs discussed so far are by computational methods. Another approach is by physical methods, e.g., [Kanter et al. (2010)]. The output based on a physical method is usually unpredictable. Thus, this class of random bit generators is commonly known as non-deterministic random bit generators (NRBGs). Those physical devices are unnecessary and unpractical for Monte Carlo methods, because deterministic algorithmic methods are much more convenient. See [Law (2014)] for more information on other methods of generating random numbers.

We discuss the algorithm and impl...

Table of contents

• Cover Page
• Title
• Copyright
• Contents
• Preface
• 1. Basic Simulation Programming
• 2. Sample Sizes and Stopping Rules
• 3. Generating Independent and Identically Distributed Batch Means
• 4. Distributions of Order Statistics
• 5. Order Statistics from Correlated Normal Random Variables
• 6. Histogram and Quasi-Independent Procedure
• 7. Metamodels
• 8. Density Estimation
• 9. Comparing Two Alternatives
• 10. Ranking and Selection
• 11. Computing Budget Allocation of Selection Procedures
• 12. Using Common Random Numbers with Selection Procedures
• 13. Parallel and Distributed Simulation
• 14. Multi-Objective Selection
• 15. Generic Selection with Constraints
• Appendix A Tables of Critical Constants
• Bibliography
• Index