Steady-state simulation of queueing processes: survey of problems and solutions
---
paper_title: The impact of advanced information processing on simulation — An illustrative review

paper_content:

Advanced Information Processing (AIP) techniques are felt to play an important role in next generation simulation tools. Here we will review and illustrate the incorporation of two such AIP techniques in modelling and simulation. Simulation-oriented information-base management systems are considered to auto matize one of the major activities, peripheral to large-scale modelling and model implementation : the management of the descriptive and quantitative data involved. On the other hand, attention is paid to the impact of artificial intelligence techniques in modelling and simulation. Knowledge-based simulation, Al supported model synthesis and some additional topics with respect to integrating Al and the system analysis approach are briefly reviewed.Some concepts are illustrated on the basis of research activities in the Benelux countries.
---
paper_title: A graphical methodology for simulating communication networks

paper_content:

A novel approach for simulating communication networks is discussed and illustrated with two examples of a token-passing network. The method is based on a graphical representation of the network consisting of three components: topology, nodes, and protocols. The topology and nodes are drawn to a network specification. The protocols are drawn by using Petri nets with some extended features. A simulation model can be automatically generated from this representation. Results of the simulation are compared to those of an analytical model, showing excellent agreement. >
---
paper_title: POSE: a Process-Oriented Simulation Environment embedded in SCHEME

paper_content:

POSE is part of a research program to explore potential benefits of new software technologies for various modelling paradigms. It is a SCHEME-based queueing network simulator, whose discus sion serves to demonstrate the suitability of symbolic languages and exploratory programming styles for system simulation.After justifying the use of symbolic languages and an object- oriented approach to model design, basic features of POSE are presented, using a simple example. This is followed by a brief description of the simulator's architecture. A final chapter sum marizes and reflects on our experiences, suggesting that object- oriented simulation environments hosted on powerful personal workstations may well offer major breakthroughs in terms of ef fectiveness and user acceptance. Computational efficiency, while a lesser concern to "investigative simulation," remains unsatisfac tory in simulations used for quantitative predictions. This prob lem may hopefully be overcome through future advances in soft ware and ...
---
paper_title: The Smalltalk simulation environment

paper_content:

The Smalltalk language provides easy to use support for discrete event simulation. Smalltalk is an object oriented language which is descended from Simula. There is a set of Smalltalk classes which directly support simulation. A simulation of a multiprocessor computer architecture with snooper caches and shared global virtual memory has been implemented in Smalltalk. This simulation is discussed here to illustrate the techniques involved.
---
paper_title: Introduction to simulation

paper_content:

This paper offers an introduction to the fundamental concepts of system modeling with emphasis on the application of digital simulation. The topics presented include system modeling, model classification, a discussion of mathematical and simulation models, their distinction and relative advantages, an overview of systems analysis, an example simulation model, and brief discussions of random numbers, random variable generation and simulation languages. The material presented is largely conceptual and requires no prior background in modeling.
---
paper_title: A Perspective on the Use of Control Variables to Increase the Efficiency of Monte Carlo Simulations

paper_content:

This is a survey paper on the application of control variables to increase the efficiency of discrete event simulations. The emphasis is on the practical problems and potential of applying the method in the simulation of complex systems. The basic theory of control variables is reviewed and the equivalence of control variables and multiple estimators is discussed. Techniques for generating control variables are described. Inefficiencies resulting from the statistical estimation of control variable coefficients and the problem of confidence interval generation are treated. This is done both within the context of the method of independent replications and the regenerative method. The application literature is reviewed and the conditions under which control variables could be profitably applied in practical simulations are described. Finally, there is a set of recommended directions for future research.
---
paper_title: A comparison between standardized time series and overlapping batched means

paper_content:

We study several methods for estimating the variance of the sample mean from a stationary stochastic process. Particular emphasis is placed on comparing the recently introduced methods of standardized time series and overlapping batched means . Comparison criteria include estimator bias and variance.
---
paper_title: Statistical Results on Control Variables with Application to Queueing Network Simulation

paper_content:

The development and application of control variables for variance reduction in the simulation of a wide class of closed queueing networks is discussed. These networks allow multiple types of customers, priorities and blocking. Alternative methods of generating confidence intervals from independent replications of a simulation are investigated. A result is given which quantifies the loss in variance reduction caused by the estimation of the optimum control coefficients. This loss is an increasing function of the number of control variables. Good variance reduction is obtained providing that the number of control variables remains small.
---
paper_title: Bias Considerations in Simulation Experiments

paper_content:

This paper uses a first-order autoregressive scheme to investigate the effects of initial conditions in a simulation on the estimation of the population mean of a process of interest. The effects are measured by bias and variance. The results show that the elimination of observations near the beginning of the simulation reduces bias, as intended, but increases the variance, sometimes significantly.
---
paper_title: Simulation studies of mixed traffic on satellite channels using TDMA-reservation protocol

paper_content:

The authors consider a TDMA (time-division multiple-access)-reservation protocol, which is a fully collision-free protocol with submissions of requests for data transmissions in preassigned subchannels, according to synchronous time-division multiplexing. They present the results of simulation studies of this protocol, focusing on its performance in a mixed traffic environment, constituted of classes of users generating different types of messages (from short, typically one-packet-long messages to long multipacket messages). Steady-state throughput-mean-message-delay characteristics for particular classes of users are obtained by applying a specially developed sequential procedure for statistical analysis of simulation output data and using observations collected during a single simulation run rather than a number of independent replications. >
---
paper_title: Estimation and Simulation

paper_content:

A number of papers on estimation procedures for simulation have been published in Management Science and related journals. I believe that many of these are on the wrong track. The purpose of this letter is to indicate what appear to be shortcomings in this literature and to suggest (imperfect) remedies.
---
paper_title: Large-sample theory for standardized time series: an overview

paper_content:

There are two basic approaches to constructing confidence intervals for steady-state parameters from a single simul t on run. The fir t s to consistently estimate the variance constant in the relevant central limit theorem. This is the approach used in the regenerative, spectral, and autoregressive methods. The second approach (standardized time series, STS) due to SCHRUBEN [10] is to “cancel out” the variance constant. This second approach contains the batch means method as a special case. Our goal in this paper is to discuss the large-simple properties of the confidence intervals generated by the STS method. In particular, the asymptotic (as run size becomes large) expected value and variance of the length of these confidence intervals is studied and shown to be inferior to the behavior manifested by intervals constructed using the first approach.
---
paper_title: Overlapping batch means: something for nothing?

paper_content:

Nonoverlapping batch means (NOLBM) is a we11-known approach For estimating the variance of the sample mean. In this paper we consider an overlapping batch means (OLBM) estimator that, based on the same assumptions and batch size as NOLBM, has essentially the same mean and only 2/3 the asymptotic variance of NOLBM. Confidence interval procedures for the mean based on NOLBM and OLBM are discussed. Both estimators are compared to the classical estimator of the variance of the mean based on sums of covariances.
---
paper_title: A survey of research on the simulation startup problem

paper_content:

To reduce the effects of initial conditions on the results of a simulation experiment, several authors have proposed startup policies that specify how to minimize the warmup period and identify the trunca tion point beyond which observations are to be re corded and analyzed. Other approaches to this prob- Zem have used results from time-series analysis and queueing theory. This paper surveys research on the simulation startup problem; a companion paper which follows presents a procedure for evaluating startup policies when the mean of the truncated sample is to be used to estimate the steady-state mean of the underlying process.
---
paper_title: Confidence intervals in discrete event simulation: A comparison of replication and batch means

paper_content:

Suppose that we have enough computer time to make n observations of a stochastic process by means of simulation and would like to construct a confidence interval for the steady-state mean. We can make k independent runs of m observations each (n=k.m) or, alternatively, one run of n observations which we then divide into k batches of length m. These methods are known as replication and batch means, respectively. In this paper, using the probability of coverage and the half length of a confidence interval as criteria for comparison, we empirically show that batch means is superior to replication, but that neither method works well if n is too small. We also show that if m is chosen too small for replication, then the coverage may decrease dramatically as the total sample size n is increased.
---
paper_title: Some Tactical Problems in Digital Simulation

paper_content:

This paper is concerned with the manner in which an investigation by simulated experimentation is conducted, after the model has been formulated and the computer program completed. It considers the problem of estimating the precision of the results obtained, and methods of improving the precision of results. Alternative procedures are discussed and recommendations are given.
---
paper_title: A Sequential Procedure for Determining the Length of a Steady-State Simulation

paper_content:

A common problem faced by simulators is that of constructing a confidence interval for the steady-state mean of a stochastic process. We have reviewed the existing procedures for this problem and found that all but one either produce confidence intervals with coverages which may be considerably lower than desired or have not been adequately tested. Thus, in many cases simulators will have more confidence in their results than is justified. In this paper we present a new sequential procedure based on the method of batch means for constructing a confidence interval with coverage close to the desired level. The procedure has the advantage that it does not explicitly require a stochastic process to have regeneration points. Empirical results for a large number of stochastic systems indicate that the new procedure performs quite well.
---
paper_title: Some Problems of Digital Systems Simulation

paper_content:

Our objective is to discuss the technique of digital system simulation. This procedure has already achieved a considerable stature in industrial and research organizations and promises to attain even greater importance in the future. Yet, with few exceptions 51, the published literature in the area consists of introductory expositions 10 or of descriptions of the solution of a particular problem 7 where the technique itself is correctly relegated to secondary position. The only publication devoted entirely to the topic 12 is a compendium of papers of the latter type with little attempt to summarize or generalize. Simulations are, of course, as varied as the systems which they represent but they do have certain common characteristics and problems. An identification of these problems would at least allow the investigator to anticipate them and plan accordingly. ::: ::: This paper consists of three sections. The first is an attempt to describe characteristics common to many system simulations; the second is a discussion of some problems involved in the construction of a digital simulator; and the third concerns problems that arise in the use of such a simulator.
---
paper_title: Achieving a Confidence Interval for Parameters Estimated by Simulation

paper_content:

This paper presents a procedure for determining the number of simulation observations required to achieve a preassigned confidence interval for means estimated by simulation. This procedure, which is simple to implement and efficient to use, is compared with two other methods for determining the required sample size in a simulation run. The empirical results show that this procedure gives good results in the precision of estimated means and in sample size requirement.
---
paper_title: The Sizes of Simulation Samples Required to Compute Certain Inventory Characteristics with Stated Precision and Confidence

paper_content:

This study presents calculations of sample sizes, measured in number of simulated time periods, required to estimate certain parameters of selected inventory models with specified precision and confidence. In particular, the inventory models used include the classical zero procurement lead-time case, plus selected non-zero procurement lead-time cases having 2-, 5-, and 10-period lead-times. The parameters estimated are the mean number of shortages and of overages per time period, an overage being the amount of stock on hand at the end of the period, with negative amounts or shortages equated to zero. ::: ::: The calculations presented include the number of time periods to be sampled to produce estimates of mean shortages and overages per time period within approximately 100 per cent of the true value, with 95-per-cent confidence. These calculations were done for the procurement lead-time models described above, using 100 different inventory policies with each model, as defined by selected stock-control levels and reorder points. The underlying demand distribution was assumed to be exponential. ::: ::: From this brief study of sample sizes on comparatively simple inventory models, we find that over the range of conditions examined, the sample sizes required to estimate shortages per period and overages per period tend not to be excessive; that is, sample sizes of less than 100 are usually required to obtain the level of precision specified a sample estimate within approximately 100 per cent of the true value at a 95-per-cent confidence level.
---
paper_title: Simulation Modeling and Analysis

paper_content:

From the Publisher: ::: This second edition of Simulation Modeling and Analysis includes a chapter on "Simulation in Manufacturing Systems" and examples. The text is designed for a one-term or two-quarter course in simulation offered in departments of industrial engineering,business,computer science and operations research.
---
paper_title: Grouping Observations in Digital Simulation

paper_content:

This paper presents a method for deriving a confidence interval for a population mean from the output of a simulation run. The method groups the observations on a run into batches and uses these batches as the basic data for analysis. The technique is not new. What is new is the procedure for determining how to group the observations into batches that satisfy certain assumptions necessary for the technique to work correctly. It is inexpensive and requires a moderate knowledge of statistics. The results of testing the method on a single server queuing model with Poisson distributed arrivals of exponentially distributed service times M/M/1, indicate that the proposed technique performs as theory suggests for moderate activity levels. However, for higher activity levels performance is below theoretical expectation for small sample sizes n. As n increases, performance converges to expectation. Moreover, two calculations of the sample sizes needed to obtain results with moderate accuracy indicate that these sample sizes are in a range where the procedure is expected to perform with small error.
---
paper_title: An Analytical Evaluation of Alternative Strategies in Steady-State Simulation

paper_content:

We consider the simple technique of making independent and probabilistically identical simulation replications to estimate the steady-state mean of a stochastic process. For a fixed total sample size, using a first-order autoregressive model with high autocorrelation and time-dependent distributions, we analytically quantify and investigate the effects of the number of replications and of initial deletions of output on several different measures of point estimator and confidence interval quality. This analysis leads to general recommendations on the choice of replications and deletion. In particular, we conclude that deletion of some amount of the initial output in a replication can be an effective and efficient method of dealing with initialization bias; this conclusion differs from several previous studies on the efficacy of deletion.
---
paper_title: Estimating Sample Size in Computing Simulation Experiments

paper_content:

A method is described for estimating and collecting the sample size needed to estimate the mean of a process (with a specified level of statistical precision) in a simulation experiment. Steps are also discussed for incorporating the determination and collection of the sample size into a computer library routine that can be called by the ongoing simulation program. We present the underlying probability model that enables us to denote the variance of the sample mean as a function of the autoregressive representation of the process under study and describe the estimation and testing of the parameters of the autoregressive representation in a way that can easily be "built into" a computer program. Several reliability criteria are discussed for use in determining sample size. Since these criteria assume that the variance of the sample mean is known, an adjustment is necessary to account for the substitution of an estimate for this variance. It is suggested that Student's distribution be used as the sampling distribution, with "equivalent degrees of freedom" determined by analogy with a sequence of independent observations. A bias adjustment is described that can be applied to the beginning of the collected data to reduce the influence of initial conditions on events in the experiment. Four examples are presented using these techniques, and comparisons are made with known theoretical solutions. One unfortunate shortcoming of the proposed procedure is that its performance is directly linked to the initially chosen sample size. Our results show that as this sample size increases, the procedure gives results which agree more closely with predicted results.
---
paper_title: Confidence Intervals for Steady-State Simulations II: A Survey of Sequential Procedures

paper_content:

We continue our survey of methods for constructing confidence intervals for steady-state means via simulation by studying sequential procedures which determine the length of the simulation during the course of the run. Our goal is to provide the simulation practitioner with some guidance as to which published procedures might actually perform well in practice. Empirical results for a variety of stochastic models with known steady-state means suggest that sequential procedures by Fishman and by Law and Carson provide good performance relative to the criterion probability of coverage.
---
paper_title: Examination of simulation output using spectral methods

paper_content:

Spectral procedures that have been developed to estimate the variance of the sample mean of simulation output are presented and evaluated. The evaluation is performed using a single server queueing situation with exponential interarrival and service times. This process is employed because theoretical values are available for use in the evaluation. In addition, the assumptions necessary to apply spectral methods are valid for this process. The results of the evaluation indicate that spectral methods produce unreliable estimates of the variance of the sample mean. Thus, it is concluded that spectral methods will not produce reliable estimates of the variance of the sample mean for general simulation output.
---
paper_title: Confidence Intervals for Steady-State Simulations: I. A Survey of Fixed Sample Size Procedures

paper_content:

We consider the problem of constructing a confidence interval for the steady-state mean of a stochastic process by means of simulation, and study the five main methods which have been proposed replication, batch means, autoregressive representation, spectrum analysis, and regeneration cycles for the case when the length of the simulation is fixed in advance. Comparing the performances of these methods on stochastic models with known steady-state means, we find that the simulator should exercise caution in interpreting the results from a simulation of fixed length, and that the length of a simulation adequate for acceptable performance is highly model-dependent. We also investigate possible sources of error for the methods, and conclude that variance estimator bias is more important than point estimator bias in confidence interval coverage degradation.
---
paper_title: Sequential stopping rules for the regenerative method of simulation

paper_content:

We consider the estimation via simulation of confidence intervals for steady-state response variables for stochastic systems which have a regenerative stochastic structure. Sequential stopping rules are investigated which allow the ratio of the width to the midpoint of an estimated confidence interval to be specified ahead of time. We prove that the resulting confidence intervals are valid asymptotically as the relative width decreases to zero. For various relative widths we empirically investigate the validity of the confidence intervals obtained when the stopping rules are applied to the simulation of queuing systems having a regenerative stochastic structure. For the queuing systems and response variables considered, a relative width of 0.05 is found to be sufficiently small to yield valid confidence intervals in almost all cases. In addition, we empirically compare the sequential stopping rules with a fixed stopping rule.
---
paper_title: Confidence intervals and orthonormally weighted standardized time series

paper_content:

We find new confidence intervals for the mean of a stationary process. The new intervals are based on orthonormally weighted standardized time series and asymptotically have smaller half-length mean and variance than their predecessors.
---
paper_title: An analysis of variance test for normality (complete samples)

paper_content:

The main intent of this paper is to introduce a new statistical procedure for testing a complete sample for normality. The test statistic is obtained by dividing the square of an appropriate linear combination of the sample order statistics by the usual symmetric estimate of variance. This ratio is both scale and origin invariant and hence the statistic is appropriate for a test of the composite hypothesis of normality. Testing for distributional assumptions in general and for normality in particular has been a major area of continuing statistical research-both theoretically and practically. A possible cause of such sustained interest is that many statistical procedures have been derived based on particular distributional assumptions-especially that of normality. Although in many cases the techniques are more robust than the assumptions underlying them, still a knowledge that the underlying assumption is incorrect may temper the use and application of the methods. Moreover, the study of a body of data with the stimulus of a distributional test may encourage consideration of, for example, normalizing transformations and the use of alternate methods such as distribution-free techniques, as well as detection of gross peculiarities such as outliers or errors. The test procedure developed in this paper is defined and some of its analytical properties described in ? 2. Operational information and tables useful in employing the test are detailed in ? 3 (which may be read independently of the rest of the paper). Some examples are given in ? 4. Section 5 consists of an extract from an empirical sampling study of the comparison of the effectiveness of various alternative tests. Discussion and concluding remarks are given in ?6. 2. THE W TEST FOR NORMALITY (COMPLETE SAMPLES) 2 1. Motivation and early work This study was initiated, in part, in an attempt to summarize formally certain indications of probability plots. In particular, could one condense departures from statistical linearity of probability plots into one or a few 'degrees of freedom' in the manner of the application of analysis of variance in regression analysis? In a probability plot, one can consider the regression of the ordered observations on the expected values of the order statistics from a standardized version of the hypothesized distribution-the plot tending to be linear if the hypothesis is true. Hence a possible method of testing the distributional assumptionis by means of an analysis of variance type procedure. Using generalized least squares (the ordered variates are correlated) linear and higher-order
---
paper_title: Correlation among estimators of the variance of the sample mean

paper_content:

Various types of estimators have been proposed for estimating the variance of the sample mean, a fundamental quantity in simulation output analysis. When used with low degrees of freedom, several of these estimators have little bias. But the low degrees of freedom correspond to high variance. One approach to creating estimators with smaller variance while maintaining the negligible bias is to use linear combinations of known estimators. Whether linear combinations provide improved estimators — and, if so, the choice of estimators to be included in the linear combination — depends upon the correlations among the various estimators. Linear combinations of estimators having high positive correlation would provide little improvement while combinations of independent estimators would provide substantial gain. We investigate the correlation among four well-known estimators as a function of the type of stochastic process generating the data, the sample size, the estimator type, and estimator parameters.
---
paper_title: A Sequential Procedure for Determining the Length of a Steady-State Simulation

paper_content:

A common problem faced by simulators is that of constructing a confidence interval for the steady-state mean of a stochastic process. We have reviewed the existing procedures for this problem and found that all but one either produce confidence intervals with coverages which may be considerably lower than desired or have not been adequately tested. Thus, in many cases simulators will have more confidence in their results than is justified. In this paper we present a new sequential procedure based on the method of batch means for constructing a confidence interval with coverage close to the desired level. The procedure has the advantage that it does not explicitly require a stochastic process to have regeneration points. Empirical results for a large number of stochastic systems indicate that the new procedure performs quite well.
---
paper_title: The Almost Regenerative Method for Stochastic System Simulations

paper_content:

The regenerative method for simulations of stochastic systems allows data collection at the entry times to a single recurrent state of the process of interest. Estimates of estimator variance are then easily computed since the generated observations have the desirable property of being independent and identically distributed. Relative to a fixed run length, however, the mean time between entries into this single state may be excessively long for complicated stochastic systems (e.g., a congested network of queues), thus providing few observations and poor variance estimates. The almost regenerative method, a relaxation of the regenerative method, can, under frequently encountered conditions, alleviate this problem by allowing data collection at the entry times to a set of states of the process of interest. Empirical evidence from simulations of simple queueing networks supports the intuitive notion that the almost regenerative method can provide more accurate estimates of estimator variance than the regene...
---
paper_title: Regeneration and Networks of Queues

paper_content:

1 Discrete Event Simulation.- 1.1 Methodological Considerations l.- 1.2 The Generalized Semi-Markov Process Model.- 1.3 Specification of Discrete Event Simulations.- 2 Regenerative Simulation.- 2.1 Regenerative Stochastic Processes.- 2.2 Properties of Regenerative Processes.- 2.3 The Regenerative Method for Simulation Analysis.- 2.4 Implementation Considerations.- 2.5 Theoretical Values for Discrete Time Markov Chains.- 2.6 Theoretical Values for Continuous Time Markov Chains.- 2.7 Efficiency of Regenerative Simulation.- 2.8 Regenerative Generalized Semi-Markov Processes.- 3 Markovian Networks.- 3.1. Markovian Job Stack Processes.- 3.2. Augmented Job Stack Processes.- 3.3. Irreducible, Closed Sets of Recurrent States.- 3.4. The Marked Job Method.- 3.5. Fully Augmented Job Stack Processes.- 3.6. The Labelled Jobs Method.- 3.7. Sequences of Passage Times.- 3.8. Networks with Multiple Job Types.- 3.9. Simulation for Passage Times.- 4 Non-Markovian Networks.- 4.1 Networks with Single States.- 4.2 Regenerative Simulation of Non-Markovian Networks.- 4.3 Single States for Passage Times.- 4.4 Recurrence and Regeneration.- 4.5 The Marked Job Method.- 4.6 Finite Capacity Open Networks.- 4.7 Passage Through Subnetworks.- 4.8 The Underlying Stochastic Structure.- 4.9 The Labelled Jobs Method.- 4.10 Comparison of Methods.- Appendix 1 Limit Theorems for Stochastic Processes.- Appendix 2 Convergence of Passage Times.- Symbol Index.
---
paper_title: Minimal-MSE linear combinations of variance estimators of the sample mean

paper_content:

We continue our investigation of linear combinations of variance-of-the-sample-mean estimators that are parameterized by batch size. First we state the mse-optimal linear-combination weights in terms of the bias vector and the covariance matrix of the component estimators for two cases: weights unconstrained and weights constrained to sum to one. Then we report a small numerical study that demonstrates mse reduction of about 80% for unconstrained weights and about 30% for constrained weights. The mse's and the percent reductions are similar for all four estimator types considered. Such large rose reductions could not be achieved in practice, since they assume knowledge of unknown parameters, which would have to be estimated. Optimal-weight estimation is not considered here.
---
paper_title: Large and small sample comparisons of various variance estimators

paper_content:

The objective of this report is to investigate the behavior of various variance estimators arising in computer simulation experiments. We give large and small sample results pertaining to the bias, variance, and confidence interval performance of nonoverlapping batched means, overlapping batched means, and standardized time series estimators.
---
paper_title: Achieving specific accuracy in simulation output analysis

paper_content:

This paper extends the use of the regenerative property of queueing systems in the analysis of simulation output. In particular, it describes a sequential estimation method which when used with the regenerative property allows results to be obtained with specified statistical accuracy. This method includes a test to check the normality assumption on which the sequential procedure relies. The paper illustrates the method using the empty and idle state as the regenerative state. A second example then describes how using the most frequently entered state as the regenerative state reduces the chance of making a costly error in a preliminary simulation run. The paper also described how a variance reduction method due to Page [9] can be used to obtain a specified accuracy with considerably fewer job completions than are required when no variance reduction technique is applied.
---
paper_title: Asymptotic Properties of Some Confidence Interval Estimators for Simulation Output

paper_content:

The classical confidence interval estimator commonly used in simulation is compared with four new estimators based on standardization of a time series presented in a previous paper. These new interval estimators are shown to have asymptotic properties that strictly dominate the classical estimator when used with data from independent simulation replications or means of batched observations from a single simulation run. Two of the new estimators also can be used with a single unbatched replication of a simulation program, a situation where the classical estimator is not defined.
---
paper_title: Testing independence of simulation subruns: a note on the power of the Von Neumann test

paper_content:

Abstract In simulation experiments confidence intervals may be based on subruns. To test whether subruns are independent the Von Neumann statistic is often used. This note shows that the power of this statistic may be very small. The practical recommendation is to apply the statistic only if at least 100 subruns are available.
---
paper_title: On strong consistency of the variance estimator

paper_content:

One way to construct a confidence interval for the mean constant of a stochastic process, is via consistent estimation of another parameter of the process, namely, the time-average variance constant. In this paper, we discuss strong consistency of the variance estimator for several methods of steady-state output analysis. These are; Batch Means (BM), Overlapping Batch Means (OBM), Spectral methods, and finally, Standardized Time Series (the area estimator of STS). A characterization of the spectral variance estimator is also presented; it is a generalization of OBM. Another estimator, which might be called Overlapping Area estimator, connects the area estimator with spectral methods.
---
paper_title: An introduction to the regenerative method for simulation analysis

paper_content:

Abstract : The purpose of this report is to provide an introduction to the regenerative method for simulation analysis. The simulations are simulations of stochastic systems, i.e., systems with random elements. The regenerative approach leads to a statistical methodology for analyzing the output of those simulations which have the property of 'starting afresh probabilistically' from time to time. The class of such simulations is very large and very important, including simulations of a broad variety of queues and queueing networks, inventory systems, inspection, maintenance, and repair operations, and numerous other situations.
---
paper_title: Evaluation of startup policies in simulation experiments

paper_content:

This paper describes a procedure for evaluating pro posed startup policies that define the initial condi tions and the truncation point in a simulation ex periment. The evaluation procedure involves the tabulation of bias, variance, and mean square error of the sample mean over a fixed range of truncation points and initial conditions. For each policy, the tabulated values are averaged with respect to an empirical truncation-point distribution based on independent model runs. These results are used to construct confidence intervals for the steady-state mean with the same average length for all policies; the corresponding average confidence interval cover age can then be used to compare policies.To illustrate the procedure, several well-known policies are evaluated for two finite-state Markovian queueing systems—α single-server queue with a capac ity of 15 and a machine-repair system with 3 repair- men and 14 machines. The results for both systems indicate that the best initial condition is the most freque...
---
paper_title: Initializing For Bias Reduction: Some Analytical Considerations

paper_content:

We are concerned with simulation studies where the simple method of independent replications and classical statistical techniques are used to construct estimates (point and interval) for a steady-state parameter of interest. This paper describes the results of an analytical study on the effectiveness of stochastic initialization, where the initial state of each replication is picked randomly from an initial state distribution, The initial-state distribution is constructed frorn data observed during a "pilot phase". Using an AR(1) process, and assuming a fixed simulation budget, we show that stochastic initialization is effective in reducing bias in the point estimate and increasing coverage of the interval estimate without unduly increasing variance or mean square error.
---
paper_title: Transient exponential-Erlang queues and steady-state simulation

paper_content:

The transient probabilistic structure of M/E m /1 and E m /M/1 queues initialized in an arbitrary deterministic state is derived in discrete time. Computational algorithms for obtaining the required probabilities are provided, and their application in calculating a variety of system performance measures is illustrated. The results are used to investigate the question of initializing simulations of systems such as these to promote rapid convergence to steady state, if that is the object of the simulation. These results are consistent with earlier studies for transient queueing systems, such as the M/M/s, but allow greater flexibility in specification of interarrival or service-time models inherent in the Erlang distributions.
---
paper_title: Bias Considerations in Simulation Experiments

paper_content:

This paper uses a first-order autoregressive scheme to investigate the effects of initial conditions in a simulation on the estimation of the population mean of a process of interest. The effects are measured by bias and variance. The results show that the elimination of observations near the beginning of the simulation reduces bias, as intended, but increases the variance, sometimes significantly.
---
paper_title: Some Tactical Problems in Digital Simulation

paper_content:

This paper is concerned with the manner in which an investigation by simulated experimentation is conducted, after the model has been formulated and the computer program completed. It considers the problem of estimating the precision of the results obtained, and methods of improving the precision of results. Alternative procedures are discussed and recommendations are given.
---
paper_title: A new approach for dealing with the startup problem in discrete event simulation

paper_content:

This article proposes a practical, data‐based statistical procedure which can be used to reduce or remove bias owing to artificial startup conditions in simulations aimed at estimating steady‐state means. We discuss results of experiments designed to choose good parameter values for this procedure, and present results of extensive testing of the procedure on a variety of stochastic models for which partial analytical results are available. The article closes with two illustrations of the application of the procedure to more complex statistical problems which are more representative of the kinds of purposes for which real‐world steady‐state simulation studies might be undertaken.
---
paper_title: Evaluation of startup policies in simulation experiments

paper_content:

This paper describes a procedure for evaluating pro posed startup policies that define the initial condi tions and the truncation point in a simulation ex periment. The evaluation procedure involves the tabulation of bias, variance, and mean square error of the sample mean over a fixed range of truncation points and initial conditions. For each policy, the tabulated values are averaged with respect to an empirical truncation-point distribution based on independent model runs. These results are used to construct confidence intervals for the steady-state mean with the same average length for all policies; the corresponding average confidence interval cover age can then be used to compare policies.To illustrate the procedure, several well-known policies are evaluated for two finite-state Markovian queueing systems—α single-server queue with a capac ity of 15 and a machine-repair system with 3 repair- men and 14 machines. The results for both systems indicate that the best initial condition is the most freque...
---
paper_title: Evaluation of commonly used rules for detecting “steady state” in computer simulation

paper_content:

A definition of the problem of the initial transient with respect to the steady-state mean value has been formulated. A set of criteria has been set forth by which the efficaacy of any proposed rule may be assessed. Within this framework, five heuristic rules for predicting the approximate end of transiency, four of which have been quoted extensively in the simulation literature, have been evaluated in the M/M/1 situation. All performed poorly and are not suitable for their intended use.
---
paper_title: The relaxation time of two queueing systems in series

paper_content:

This paper deals with the time-dependent behaviour of two queueing systems in series, with a Posson arrival stream and exponential service times. The Laplace transform of the probability p0(t) that the tandem system is empty at time t given that it was empty at time 0 is obtained by reducing the functional equation for the generating function of the joint queue length distribution to a Riemann-Hilbert boundary value problem. From this Laplace transform the relaxation time of p 0(t) is determined for all parameter values, and the first term of the asymptotic expansion of p 0(t)-p 0(∞) as t →∞ is found in the ergodic and in the null recurrent cases.
---
paper_title: Some steady-state problems in simulation

paper_content:

Let X(T) be an integer valued stochastic process, continuous in time, T. By a computer simulation model one can obtain from the interval (O,T) an estimate of the mean, q, of the process by the time average r i (T), where i is the initial state at time 0. One of the problems is when to stop the simulation. Before stopping the simulation we first of all have to be sure that r i (T) is an unbiased estimator for the mean value q. It can be shown that r i (T) in many cases is unbiased only for large values of T, and that this convergence is not necessarily monotonous. It can also be shown that the difference between the expected value of r i (T) and the mean value q is inversely proportional to T. Secondly, before stopping the simulation we have to be sure that the dispersion on r i (T) is small, and it can be shown that this dispersion is inversely proportional to the square root of T.
---
paper_title: A regression technique for determining steady state conditions in time series simulations

paper_content:

In many situations, the simulator finds himself faced with the problem of simulating a time series whose initial state is different from the state of the system after a large number of observations have been made. This is frequently referred to as the problem of the initial bias or the initial tranient problem. In this paper, we borrow from the theory of convergence in distribution to develop a criterion for convergence to a steady state process and then develop estimation techniques based on simple linear regression to determine when the time series under investigation has converged to a steady state process.
---
paper_title: Simulation Using GPSS

paper_content:

Partial table of contents: Basic Concepts in Queuing Systems Modeling. Basic GPSS Modeling Concepts. Sampling from Probability Distributions in GPSS. Intermediate GPSS Modeling Concepts. Advanced GPSS Modeling Concepts. A Summary of Selected GPSS/360 Features Not Otherwise Covered in This Book.
---
paper_title: A relaxation time heuristic for reducing initialization bias in simulation of M/Ek/1 queueing systems

paper_content:

In a previous paper, a heuristic technique was introduced for reducing initialization bias in Monte-Carlo simulation of stationary, infinite-capacity, Markovian queueing systems. The technique differs from many existing methods in that, rather than relying on a statistical analysis of output from preliminary simulation runs, it is based on characteristics of the underlying theoretical model. Experimental results presented earlier provide convincing evidence that use of the heuristic yields an unbiased estimate of the steady-state expected queue length in M/M/1 systems with virtually no cost added to the simulation. We now present results of experiments designed to validate the technique for estimating the steady-state expected number of customers in M/E k /1 queueing systems.
---
paper_title: Some Tactical Problems in Digital Simulation

paper_content:

This paper is concerned with the manner in which an investigation by simulated experimentation is conducted, after the model has been formulated and the computer program completed. It considers the problem of estimating the precision of the results obtained, and methods of improving the precision of results. Alternative procedures are discussed and recommendations are given.
---
paper_title: An Empirical Investigation of the Transient Behavior of Stationary Queueing Systems

paper_content:

This paper examines the transient behavior of infinite-capacity, single-server, Markovian queueing systems. It estimates Q ( t ), the expected number of customers in queue at time t , by numerically solving the sets of simultaneous, first-order differential equations that describe these systems. Empirical results have been drawn from these observations. For small values of t , the behavior of Q ( t ) is strongly influenced by the initial state of the queueing system. For systems with deterministic initial conditions, one can roughly predict which of a small set of patterns this behavior will follow. After an initial period of time and independently of initial conditions, Q ( t ) approaches Q (∞) in a manner that can be approximated through a decaying exponential function. On the basis of experimental evidence, we have developed an expression that provides a good approximation to the observed values of the time constant associated with this exponential function. This expression can also be used to determine an upper bound for the amount of time required until Q ( t ) is close to Q (∞).
---
paper_title: A relaxation time approach for reducing initialization bias in simulation

paper_content:

We introduce a truncation algorithm to reduce the effects of initialization bias on Monte-Carlo simulations of stationary Markovian queueing systems. The heuristic is based on the estimated relaxation time of the underlying model and implementation requires no preliminary test runs or parameter selection. Computational results are presented for M/M/1 systems in which performance of the relaxation time method is compared with other truncation rules.
---
paper_title: Simulation Modeling and Analysis

paper_content:

From the Publisher: ::: This second edition of Simulation Modeling and Analysis includes a chapter on "Simulation in Manufacturing Systems" and examples. The text is designed for a one-term or two-quarter course in simulation offered in departments of industrial engineering,business,computer science and operations research.
---
paper_title: A survey of research on the simulation startup problem

paper_content:

To reduce the effects of initial conditions on the results of a simulation experiment, several authors have proposed startup policies that specify how to minimize the warmup period and identify the trunca tion point beyond which observations are to be re corded and analyzed. Other approaches to this prob- Zem have used results from time-series analysis and queueing theory. This paper surveys research on the simulation startup problem; a companion paper which follows presents a procedure for evaluating startup policies when the mean of the truncated sample is to be used to estimate the steady-state mean of the underlying process.
---
paper_title: Simulation Run Length Control in the Presence of an Initial Transient

paper_content:

This paper studies the estimation of the steady state mean of an output sequence from a discrete event simulation. It considers the problem of the automatic generation of a confidence interval of prespecified width when there is an initial transient present. It explores a procedure based on Schruben's Brownian bridge model for the detection of nonstationarity and a spectral method for estimating the variance of the sample mean. The procedure is evaluated empirically for a variety of output sequences. The performance measures considered are bias, confidence interval coverage, mean confidence interval width, mean run length, and mean amount of deleted data. If the output sequence contains a strong transient, then inclusion of a test for stationarity in the run length control procedure results in point estimates with lower bias, narrower confidence intervals, and shorter run lengths than when no check for stationarity is performed. If the output sequence contains no initial transient, then the performance measures of the procedure with a stationarity test are only slightly degraded from those of the procedure without such a test. If the run length is short relative to the extent of the initial transient, the stationarity tests may not be powerful enough to detect the transient, resulting in a procedure with unreliable point and interval estimates.
---
paper_title: Simulation Run Length Control in the Presence of an Initial Transient

paper_content:

This paper studies the estimation of the steady state mean of an output sequence from a discrete event simulation. It considers the problem of the automatic generation of a confidence interval of prespecified width when there is an initial transient present. It explores a procedure based on Schruben's Brownian bridge model for the detection of nonstationarity and a spectral method for estimating the variance of the sample mean. The procedure is evaluated empirically for a variety of output sequences. The performance measures considered are bias, confidence interval coverage, mean confidence interval width, mean run length, and mean amount of deleted data. If the output sequence contains a strong transient, then inclusion of a test for stationarity in the run length control procedure results in point estimates with lower bias, narrower confidence intervals, and shorter run lengths than when no check for stationarity is performed. If the output sequence contains no initial transient, then the performance measures of the procedure with a stationarity test are only slightly degraded from those of the procedure without such a test. If the run length is short relative to the extent of the initial transient, the stationarity tests may not be powerful enough to detect the transient, resulting in a procedure with unreliable point and interval estimates.
---
paper_title: Batch Size Effects in the Analysis of Simulation Output

paper_content:

Batching is a commonly used method for calculating confidence intervals on the mean of a sequence of correlated observations arising from a simulation experiment. Several recent papers have considered the effect of using batch sizes too small to satisfy assumptions of normality and/or independence, and the resulting incorrect probabilities of the confidence interval covering the mean. This paper quantifies the effects of using batch sizes larger than necessary to satisfy normality and independence assumptions. These effects include (1) correct probability of covering the mean, (2) an increase in expected half length, (3) an increase in the standard deviation and coefficient of variation of the half length, and (4) an increase in the probability of covering points not equal to the mean. For any sample size and independent and normal batch means, the results are (1) the effects of less than 10 batches are large and the effects of more than 30 batches small, and (2) additional batches have lesser effects on ...
---
paper_title: A Sequential Procedure for Determining the Length of a Steady-State Simulation

paper_content:

A common problem faced by simulators is that of constructing a confidence interval for the steady-state mean of a stochastic process. We have reviewed the existing procedures for this problem and found that all but one either produce confidence intervals with coverages which may be considerably lower than desired or have not been adequately tested. Thus, in many cases simulators will have more confidence in their results than is justified. In this paper we present a new sequential procedure based on the method of batch means for constructing a confidence interval with coverage close to the desired level. The procedure has the advantage that it does not explicitly require a stochastic process to have regeneration points. Empirical results for a large number of stochastic systems indicate that the new procedure performs quite well.
---
paper_title: Achieving a Confidence Interval for Parameters Estimated by Simulation

paper_content:

This paper presents a procedure for determining the number of simulation observations required to achieve a preassigned confidence interval for means estimated by simulation. This procedure, which is simple to implement and efficient to use, is compared with two other methods for determining the required sample size in a simulation run. The empirical results show that this procedure gives good results in the precision of estimated means and in sample size requirement.
---
paper_title: Quick simulation of excessive backlogs in networks of queues

paper_content:

We consider stable open Jackson networks and study the rare events of excessive backlogs. Although, these events occur rarely they can be critical, since they can impair the functioning of the network. We attempt to estimate the probability of these events by simulations. Since, the direct simulation of rare events takes a very long time, this procedure is very costly. Instead, we devise a method for changing the network to speed up the simulation of rare events. We try to pursue this idea with the help of Large Deviation theory. This approach, under certain assumptions, results in a system of differential equations which may be difficult to solve. To circumvent this, we develop a heuristic method which gives the rule for changing the network for the purpose of simulations. We illustrate, by examples, that our method of simulations can be several orders of magnitude faster than direct simulations.
---
paper_title: Sensitivity analysis via likelihood ratios

paper_content:

We present a new method of obtaining derivatives of expectations with respect to various parameters. For example, if λ is the rate of a Poisson process, N T is the number of Poisson events in (0, T ),and p is nearly any function of the sample path (e.g. a performance measure in a queuing network), then we show that d / d λ E λ (p) = E λ (( N T /λ - T )p), which yields an obvious algorithm. We have proven that the method works for a wide class of parameters and performance measures in regenerative simulation. We also report on the method's limitations and on some numerical experiments.
---
paper_title: Tests for the verification and validation of computer simulation models

paper_content:

This paper discusses the quantitative as well as qualitative tests which can be run in trying to convince the user of a simulation model that the results are valid
---
paper_title: Discrete-Event System Simulation

paper_content:

This book provides a basic treatment of one of the most widely used operations research tools: discrete-event simulation. Prerequisites are calculus, probability theory, and elementary statistics. Contents, abridged: Introduction to discrete-event system simulation. Mathematical and statistical models. Random numbers. Analysis of simulation data. Index.
---
paper_title: Sensitivity analysis and performance extrapolation for computer simulation models

paper_content:

We present a method for deriving sensitivities of performance measures for computer simulation models. We show that both the sensitivities (derivatives, gradients, Hessians, etc.) and the performance measure can be estimated simultaneously from the same simulation. Our method is based on probability measure transformations derived from the efficient score. We also present a rather general procedure from which perturbation analysis and our method can be viewed as particular cases. Applications to reliability models and stochastic shortest path networks are given.
---
paper_title: Large deviations and rare events in the study of stochastic algorithms

paper_content:

New asymptotics formulas for the mean exit time from an almost stable domain of a discrete-time Markov process are obtained. An original fast simulation method is also proposed. The mathematical background involves the large deviation theorems and approximations by a diffusion process. We are chiefly concerned with the classical Robbins-Monroe algorithm. The validity of the results are tested on examples from the ALOHA system (a satellite type communication algorithm).
---
paper_title: Asynchronous distributed simulation via a sequence of parallel computations

paper_content:

An approach to carrying out asynchronous, distributed simulation on multiprocessor messagepassing architectures is presented. This scheme differs from other distributed simulation schemes because (1) the amount of memory required by all processors together is bounded and is no more than the amount required in sequential simulation and (2) the multiprocessor network is allowed to deadlock, the deadlock is detected, and then the deadlock is broken. Proofs for the correctness of this approach are outlined.
---
paper_title: Simulation Modeling and Analysis

paper_content:

From the Publisher: ::: This second edition of Simulation Modeling and Analysis includes a chapter on "Simulation in Manufacturing Systems" and examples. The text is designed for a one-term or two-quarter course in simulation offered in departments of industrial engineering,business,computer science and operations research.
---
paper_title: The use of graphical models in model validation

paper_content:

The use of graphical models for model specification and in modelling is increasing rapidly. This paper discusses the use of these graphical models in model validation.
---
paper_title: Computer-aided modeling, analysis, and design of communication networks

paper_content:

Computer-aided design, analysis, and simulation techniques for communication networks are surveyed. The focus is on analytic and simulation techniques that are either amendable to, or require, implementation on a computer. Issues relating to the implementation of these techniques on a computer as well as their embodiment in software tools are addressed. Past and present work in these areas is surveyed, the application of these techniques to network performance modeling and analysis is discussed, and promising directions for future research are indicated. >
---
paper_title: Variance reduction in mean time to failure simulations

paper_content:

We describe two variance reduction methods for estimating the mean time to failure (MTTF) in Markovian models of highly reliable systems. The first method is based on a ratio representation of the MTTF and employs importance sampling. The second method is based on a hybrid simulation/analytic technique where the number of simulated transitions are reduced by computing partial results analytically. Experiments with a large example show the effectiveness of both techniques for highly reliable systems.
---
paper_title: Adaptive spectral methods for simulation output analysis

paper_content:

This paper addresses two central problems in simulation methodology: the generation of confidence intervals for the steady state means of the output sequences and the sequential use of these confidence intervals to control the run length. The variance of the sample mean of a covariance stationary process is given approximately by p(0)/N, where p(f) is the spectral density at frequency of and N is the sample size. In an earlier paper we developed a method of confidence interval generation based on the estimation of p(0) through the least squares fit of a quadratic to the logarithm of the periodogram. This method was applied in a run length Control procedure to a sequence of batched means. As the run length increased the batch means were rebatched into larger batch sizes so as to limit storage requirements. In this rebatching the shape of the spectral density changes, gradually becoming flat as N increases. Quadratics were chosen as a compromise between small sample bias and large sample stability. ::: ::: In this paper we consider smoothing techniques which adapt to the changing spectral shape in an attempt to improve both the small and large sample behavior of the method. The techniques considered are polynomial smoothing with the degree selected sequentially using standard regression statistics, polynomial smoothing with the degree selected by cross validation, and smoothing splines with the amount of smoothing determined by cross validation. These techniques were empirically evaluated both for fixed sample sizes and when corporated into the sequential run length control procedure. For fixed sample sizes they did not improve the small sample behavior and only marginally improved the large sample behavior when compared with the quadratic method. Their performance in the sequential procedure was unsatisfactory. Hence, the straightforward quadratic technique recommended in the earlier paper is still recommended as an effective, practical technique for simulation confidence interval generation and run length control.
---

Title: Steady-state simulation of queueing processes: survey of problems and solutions
Section 1: INTRODUCTION
Description 1: This section introduces the context and significance of using computer-based stochastic simulation for performance evaluation, specifically addressing its application to queuing systems with random input and output processes.

Section 2: METHODS OF DATA COLLECTION AND ANALYSIS
Description 2: This section discusses various methods for data collection and analysis used in steady-state simulation, highlighting the approaches to deal with initial nonstationary phases and autocorrelation among observations.

Section 3: PROBLEM OF INITIALIZATION
Description 3: This section elaborates on the challenges of initializing simulations to ensure that the collected data accurately represent the steady-state behavior, also addressing the dilemma of whether or not to delete initial transient data.

Section 4: Duration of the Initial Transient Period
Description 4: This section investigates methods for determining the length of the initial transient period in simulation runs to decide the point from which data should be collected for steady-state analysis.

Section 5: SEQUENTIAL PROCEDURES FOR STEADY-STATE SIMULATION: EXAMPLES
Description 5: This section provides detailed examples of sequential procedures used to stop simulation experiments once the required relative precision of confidence intervals is achieved, ensuring the accuracy of the steady-state estimations.

Section 6: SUMMARY AND GENERAL COMMENTS
Description 6: This section summarizes the key points discussed throughout the paper, offering general comments on the methodologies, their applicability, and the need for further studies and improvements in the field of steady-state simulation of queuing processes.

Section 7: APPENDIX A. ELEMENTARY STATISTICAL CONCEPTS
Description 7: This appendix covers the fundamental statistical concepts necessary to understand the problems discussed in the paper, providing a background on statistical inference in the context of stochastic simulation.

Section 8: APPENDIX B. SPECTRAL ANALYSIS OF VARIANCE
Description 8: This appendix presents the detailed procedure for spectral analysis of variance, used to estimate the variance of the mean in an autocorrelated sequence of observations from a stationary process.