WSC 2002 Final Abstracts

Parameter Estimation for ARTA Processes
Bahar Biller (Carnegie Mellon University) and Barry L. Nelson (Northwestern University)

Abstract:
Providing accurate and automated input-modeling support is one of the challenging problems in the application of computer simulation. The models incorporated in current input-modeling software packages often fall short of what is needed because they emphasize independent and identically distributed processes, while dependent time-series processes occur naturally in the simulation of many real-life systems. This paper introduces a statistical methodology for fitting stochastic models to dependent time-series input processes. Specifically, an automated and statistically valid algorithm is presented to fit ARTA (Autoregressive-to-Anything) processes with marginal distributions from the Johnson translation system to stationary univariate time-series data. The use of this algorithm is illustrated via a real-life example.

Properties of the NORTA Method in Higher Dimensions
Soumyadip Ghosh and Shane G. Henderson (Cornell University)

Abstract:
The NORTA method for multivariate generation is a fast general purpose method for generating samples of a random vector with given marginal distributions and given product-moment or rank correlation matrix. However, this method has been shown to fail to work for some feasible correlation matrices. (A matrix is feasible if there exists a random vector with the given marginal distributions and the matrix as the correlation matrix.) We investigate how this feasibility problem behaves as the dimension of the random vector is increased and find the problem to become acute rapidly. We also find that a modified NORTA procedure, augmented by a semidefinite program (SDP) that aims to generate a correlation matrix "close" to the desired one, performs well with increasing dimension.

The Vine Copula Method for Representing High Dimensional Dependent Distributions: Application to Continuous Belief Nets
Dorota Kurowicka and Roger M. Cooke (Delft University of Technology)

Abstract:
High dimensional probabilistic models are often formulated as belief nets (BN’s), that is, as directed acyclic graphs with nodes representing random variables and arcs representing “influence”. BN’s are conditionalized on incoming information to support probabilistic inference in expert system applications. For continuous random variables, an adequate theory of BN’s exists only for the joint normal distribution. In general, an arbitrary correlation matrix is not compatible with arbitrary marginals, and conditionalization is quite intractable. Transforming to normals is unable to reproduce exactly a specified rank correlation matrix. We show that a continuous belief net can be represented as a regular vine, where an arc from node i to j is associated with a (conditional) rank correlation between i and j. Using the elliptical copula and the partial correlation transformation properties, it is very easy to conditionalize the distribution on the value of any node, and hence update the BN.

Two-Stage NP Method with Inheritance
Jumi Kim and Sigurdur Ólafsson (Iowa State University)

Abstract:
The nested partitions method is a flexible and effective framework of optimizing large-scale problems with combinatorial structure. In this paper we consider the nested partitions method for simulation optimization and propose a new variant that uses inheritance to speed convergence. The new nested partitions method with inheritance algorithm performs well for when applied to test problems but it also calls for new analysis of convergence.

Randomized-Direction Stochastic Approximation Algorithms Using Deterministic Sequences
Xiaoping Xiong (University of Maryland), I-Jeng Wang (Johns Hopkins University) and Michael C. Fu (University of Maryland)

Abstract:
We study the convergence and asymptotic normality of a generalized form of stochastic approximation algorithm with deterministic perturbation sequences. Both one-simulation and two-simulation methods are considered. Assuming a special structure of deterministic sequence, we establish sufficient condition on the noise sequence for a.s. convergence of the algorithm. Construction of such a special structure of deterministic sequence follows the discussion of asymptotic normality. Finally we discuss ideas on further research in analysis and design of the deterministic perturbation sequences.

A Combined Procedure for Optimization via Simulation
Juta Pichitlamken (Kasetsart University) and Barry L. Nelson (Northwestern University)

Abstract:
We propose an optimization-via-simulation algorithm for use when the performance measure is estimated via a stochastic, discrete-event simulation, and the decision variables may be subject to deterministic linear integer constraints. Our approach - which consists of a global guidance system, a selection-of-the-best procedure, and local improvement - is globally convergent under very mild conditions.

Estimating Buffer Overflows in Three Stages Using Cross-Entropy
P. T. de Boer (University of Twente), D. P. Kroese (The University of Queensland) and R. Y. Rubinstein (Technion)

Abstract:
In this paper we propose a fast adaptive Importance Sampling method for the efficient simulation of buffer overflow probabilities in queueing networks. The method comprises three stages. First we estimate the minimum Cross-Entropy tilting parameter for a small buffer level; next, we use this as a starting value for the estimation of the optimal tilting parameter for the actual (large) buffer level; finally, the tilting parameter just found is used to estimate the overflow probability of interest. We recognize three distinct properties of the method which together explain why the method works well; we conjecture that they hold for quite general queueing networks. Numerical results support this conjecture and demonstrate the high efficiency of the proposed algorithm.

Estimation of Rare Event Probabilities Using Cross-Entropy
Tito Homem-de-Mello (Ohio State University) and Reuven Y. Rubinstein (Technion, Israel Institute of Technology)

Abstract:
This paper deals with estimation of probabilities of rare events in static simulation models using a fast adaptive two-stage procedure based on importance sampling and Kullback-Liebler's cross-entropy (CE). More specifically, at the first stage we estimate the optimal parameter vector in the importance sampling distribution using CE, and at the second stage we estimate the desired rare event probability using importance sampling (likelihood ratios). Some theoretical aspects of the proposed method, including its convergence, are established. The numerical results presented suggest that the method effectively estimates rare event probabilities.

Sequence Alignment by Rare Event Simulation
Jonathan Keith and Dirk P. Kroese (The University of Queensland)

Abstract:
We present a new stochastic method for finding the optimal alignment of DNA sequences. The method works by generating random paths through a graph (the edit graph) according to a Markov chain. Each path is assigned a score, and these scores are used to modify the transition probabilities of the Markov chain. This procedure converges to a fixed path through the graph, corresponding to the optimal (or near-optimal) sequence alignment. The rules with which to update the transition probabilities are based on Rubinstein's Cross-Entropy Method, a new technique for stochastic optimization. This leads to very simple and natural updating formulas. Due to its versatility, mathematical tractability, and simplicity, the method has great potential for a large class of combinatorial optimization problems, in particular in biological sciences.

A Comparison of Output-Analysis Methods for Simulations of Processes with Multiple Regeneration Sequences
James M. Calvin and Marvin K. Nakayama (New Jersey Institute of Technology)

Abstract:
We compare several simulation estimators for a performance measure of a process having multiple regeneration sequences. We examine the setting of two regeneration sequences. We compare two existing estimators, the permuted estimator and the semi-regenerative estimator, and two new estimators, a type of U-statistic estimator and a type of V-statistic estimator. The last two estimators are obtained by resampling trajectories without and with replacement, respectively. The permuted estimator and the U-statistic estimator turn out to be equivalent, but the others are in general different. We show that when estimating the second moment of a cumulative cycle reward, the semi-regenerative and V-statistic estimators have non-negative bias, with the semi-regenerative bias being larger. The permuted estimator was previously shown to be unbiased. Although some of the estimators have different small-sample properties, they all satisfy central limit theorems with the same asymptotic variance constant.

ASAP2: An Improved Batch Means Procedure for Simulation Output Analysis
Natalie M. Steiger (University of Maine), Emily K. Lada and James R. Wilson (North Carolina State University), Christos Alexopoulos (Georgia Tech ), David Goldsman (Georgia Tech) and Faker Zouaoui (Sabre, Inc.)

Abstract:
We introduce ASAP2, an improved variant of the batch-means algorithm ASAP for steady-state simulation output analysis. ASAP2 operates as follows: the batch size is progressively increased until the batch means pass the Shapiro-Wilk test for multivariate normality; and then ASAP2 delivers a correlation-adjusted confidence interval. The latter adjustment is based on an inverted Cornish-Fisher expansion for the classical batch means t-ratio, where the terms of the expansion are estimated via a first-order autoregressive time series model of the batch means. ASAP2 is a sequential procedure designed to deliver a confidence interval that satisfies a prespecified absolute or relative precision requirement. When used in this way, ASAP2 compares favorably to ASAP and the well-known procedures ABATCH and LBATCH with respect to close conformance to the precision requirement as well as coverage probability and mean and variance of the half-length of the final confidence interval.

On Choosing a Single Criterion for Confidence-Interval Procedures
Bruce Schmeiser (Purdue University) and Yingchieh Yeh (Yuan Ze University)

Abstract:
Stating a confidence interval is a traditional method of indicating the sampling error of a point estimator of a model's performance measure. We propose a single dimensionless criterion, inspired by Schruben's coverage function, for evaluating and comparing the statistical quality of confidence-interval procedures. Procedure quality is usually thought to be multidimensional, composed of the mean (and maybe the variance) of the interval-width distribution and the probability of covering the performance measure (and maybe other values). Our criterion, which we argue lies at the heart of what makes a confidence-interval procedure good or bad, compares a given procedure's intervals to those of an "ideal" procedure. For a given point estimator (such as the sample mean) and given experimental data process (such as a first-order autoregressive process with specified parameters), our single criterion is a function of only the sample size (or other rule that ends sampling).

Panel on Current Issues in Simulation Input Modeling
Russell R. Barton (The Pennsylvania State University), Russell C. H. Cheng (University of Southampton), Stephen E. Chick (INSEAD), Shane G. Henderson (Cornell University), Averill M. Law (Averill Law & Associates ), Lawrence M. Leemis (The College of William & Mary), Bruce W. Schmeiser (Purdue University), Lee W. Schruben (University of California, Berkeley) and James R. Wilson (North Carolina State University)

Abstract:
In recent years, substantial progress has been made in the development of powerful new approaches to modeling and generation of the stochastic input processes driving simulation models. In this panel discussion, we examine some of the central issues and unresolved problems associated with each of these approaches to simulation input modeling.

Confidence Regions for Stochastic Approximation Algorithms
Ming-hua Hsieh (National Chengchi University) and Peter W. Glynn (Stanford University)

Abstract:
In principle, known central limit theorems for stochastic approximation schemes permit the simulationist to provide confidence regions for both the optimum and optimizer of a stochastic optimization problem that is solved by means of such algorithms. Unfortunately, the covariance structure of the limiting normal distribution depends in a complex way on the problem data. In particular, the covariance matrix depends not only on variance constants but also on even more statistically challenging parameters (e.g. the Hessian of the objective function at the optimizer). In this paper, we describe an approach to producing such confidence regions that avoids the necessity of having to explicitly estimate the covariance structure of the limiting normal distribution. This procedure offers an easy way for the simulationist to provide confidence regions in the stochastic optimization setting.

Response Surface Methodology Revisited
Ebru Angün, Jack P.C. Kleijnen, Dick Den Hertog, and Gül Gürkan (Tilburg University)

Abstract:
Response Surface Methodology (RSM) searches for the input combination that optimizes the simulation output. RSM treats the simulation model as a black box. Moreover, this paper assumes that simulation requires much computer time. In the first stages of its search, RSM locally fits first-order polynomials. Next, classic RSM uses steepest descent (SD); unfortunately, SD is scale dependent. Therefore, Part 1 of this paper derives scale independent ‘adapted’ SD (ASD) accounting for covariances between components of the local gradient. Monte Carlo experiments show that ASD indeed gives a better search direction than SD. Part 2 considers multiple outputs, optimizing a stochastic objective function under stochastic and deterministic constraints. This part uses interior point methods and binary search, to derive a scale independent search direction and several step sizes in that direction. Monte Carlo examples demonstrate that a neighborhood of the true optimum can indeed be reached, in a few simulation runs.

A Conservative Adjustment to the ETSS Procedure
E. Jack Chen (BASF Corporation)

Abstract:
Two-stage selection procedures have been widely studied and applied in determining the required sample size (i.e., the number of replications or batches) for selecting the best of k designs. The Enhanced Two-Stage Selection (ETSS) procedure is a heuristic two-stage selection procedure that takes into account not only the variance of samples, but also the difference of sample means when determining the sample sizes. This paper discusses the use of a conservative adjustment with the ETSS procedure to increase the probability of correct selection. We show how the adjustment allocates more simulation replications or batches to more promising designs at the second stage. An experimental performance evaluation demonstrates the efficiency of the adjustment.

Collecting Data and Estimating Parameters for Input Distributions
Michael Freimer (Cornell University) and Lee Schruben (University of California, Berkeley)

Abstract:
An early stage of a simulation study often consists of collecting data in order to parameterize the model. This paper addresses the question of how much data to collect, and from what sources. We use designed experiments to identify important unknown parameters, taking into account the current level of information about them. We develop approaches based on two common forms of analysis of variance: a fixed effects model, and a random effects model.

Joint Criterion for Factor Identification and Parameter Estimation
Stephen E. Chick (INSEAD) and Szu Hui Ng (Singapore Institute of Manufacturing Technology)

Abstract:
One goal in simulation experimentation is to identify which input parameters most significantly influence the mean of simulation output. Another goal is to obtain good parameter estimates for a response model that quantifies how the mean output depends on influential input parameters. The majority of experimental design techniques focus on either one goal or the other. This paper uses a design criterion for follow-up experiments that jointly identifies the important parameters and reduces the variance of parameter estimates. The criterion is entropy-based, and is applied to a critical care facility simulation.

Difficulties in Simulating Queues with Pareto Service
Donald Gross and John F. Shortle (George Mason University) and Martin J. Fischer and Denise M. B. Masi (Mitretek Systems)

Abstract:
M/G/1 queues, where G is a heavy-tailed distribution, have applications in Internet modeling and modeling for insurance claim risk. The Pareto distribution is a special heavy-tailed distribution called a power-tailed distribution, and has been found to serve as adequate models for many of these situations. However, to get the waiting time distribution, one must resort to numerical methods, e.g., simulation. Many difficulties arise in simulating queues with Pareto service and we investigate why this may be so. Even if we are willing to consider truncated Pareto service, there still can be problems in simulating if the truncation point (maximum service time possible) is too large.

Rare-Event Simulation for Infinite Server Queues
Roberto Szechtman and Peter W. Glynn (Stanford University)

Abstract:
We discuss rare-event simulation methodology for computing tail probabilities for infinite-server queues. Our theoretical discussion also offers some new simulation insights into the change-of-measure associated with the Gartner-Ellis theorem of large deviations.

A Balanced Likelihood Ratio approach for Analyzing Rare Events in a Tandem Jackson Network
Bruce C. Shultes (University of Cincinnati)

Abstract:
Balanced likelihood ratio importance sampling methods were originally developed for the analysis of fault-tolerant systems. This paper provides a basis for adapting this approach to analyze the rare event probability that total system size reaches a bound before returning to zero in tandem Jackson networks. An optimal importance sampling distribution for the single server case is derived through direct application of the balanced likelihood ratio approach. The generalization of this approach to larger systems is explored via a two-node tandem Jackson network. A general heuristic approach is outlined along with certain open questions whose answers could lead to a more robust solution. Asymptotic characteristics of the proposed importance sampling approach for the two-node network are discussed. Bounded relative error is only possible under certain conditions. Numerical results illustrate the benefits of the approach.

Simulating M/G/1 Queues with Heavy-Tailed Service
John C. Sees, Jr. (Center for Army Analysis) and John F. Shortle (George Mason University)

Abstract:
We examine the performance and accuracy of simulating M/G/1 queues when the service time is Pareto distributed with shape parameter, alpha, between one and three. Two applications of this problem are in insurance risk and telecommunications. When 2 < alpha ≤ 3, the theoretical distribution of the sample averages of the queue waiting times is a stable distribution. When alpha ≤ 2, the mean waiting time does not exist. We provide a modified quantile simulation method, which is able to solve harder problems than existing methods; in addition, it requires less memory, and allows the user to emphasize accuracy or execution time. We also give numerical examples for other heavy-tailed distributions, such as the lognormal.

A Statistical Process Control Approach for Estimating the Warm-Up Period
Stewart Robinson (University of Warwick)

Abstract:
One means for dealing with initialization bias in simulation experiments is to implement a warm-up period. This requires the correct estimation of the initial transient. A new method for determining the warm-up period, based upon the principles of statistical process control (SPC), is described. The method is tested on empirical data from a simulation model that has been used in a real-life study. In comparing the results to those from two commonly used warm-up methods, it appears that the SPC method performs well. The strengths and weaknesses of the approach are discussed.

Two-Phase Quantile Estimation
E. Jack Chen (BASF Corporation)

Abstract:
This paper discusses the implementation of a two-phase procedure to construct confidence intervals for a simulation estimator of the steady-state quantiles of stochastic processes. We compute sample quantiles at certain grid points and use Lagrange interpolation to estimate the p quantile. The algorithm dynamically increases the sample size so that quantile estimates satisfy the proportional precision at the first phase and the relative or absolute precision at the second phase. We show that the procedure gives asymptotically unbiased quantile estimates. An experimental performance evaluation demonstrates the validity of using grid points and the quasi-independent procedure to estimate quantiles.

A Batch Means Procedure for Mean Value Estimation of Processes Exhibiting Long Range Dependence
Andrés Suárez-González, José C. López-Ardao, Cándido López-García, Miguel Rodríguez-Pérez, Manuel Fernández-Veiga, and María Estrella Estrella Sousa-Vieira (Universidade de Vigo)

Abstract:
Mean value estimation of processes exhibiting Long Range Dependence (LRD) requires a different approach than the techniques applied to those exhibiting Short Range Dependence (SRD), except for the independent replication method. We describe a nonoverlapping batch means method able to deal with LRD processes, the LRD Batch Means method. This method exploits the behavior of Asymptotically Second-order Self-Similar processes: their aggregated processes become well approximated by Fractional Gaussian Noise (FGN) processes for large aggregation levels. Once tested positively this similarity, the method produces a correlation-adjusted confidence interval from an empirical approximation of the distribution of the standardized average for the particular case of FGN processes. Afterwards, we measure its performance over both LRD and SRD processes.