|
...methods. We compare permuting to an alternative extension procedure known as batching. We demonstrate the permuting method by applying it to estimators based on the maximum and the area of a normalized path.
Key words: steady-state simulation; confidence intervals; functional central limit theorem
MSC2000 subject classification: Primary: 65C05; secondary: 62M10
OR/MS subject classification: Primary: Simulation/statistical analysis; secondary: statistics/time series
1. Introduction. The goal of many steady-state simulations is to estimate and construct confidence intervals for the steady-state mean [mu] of a stochastic process. Under mild conditions, the time average of a process converges to [mu] with probability one, so constructing a point estimator for [mu] is straightforward: run a long simulation of the process, and use the time average of the process over the simulation as a point estimate for [mu]. Time averages often satisfy a central limit theorem, but the autocorrelations typically present in simulation output make constructing confidence intervals for [mu] based on a central limit theorem a delicate undertaking. A number of techniques have been developed to do this under various assumptions; e.g., see Law and Kelton [10, [section] 9.5].
One such approach is to apply a standardized time series (STS) technique (Schruben [11]). The validity of STS methods depends on the simulated process satisfying a functional central limit theorem (e.g., Billingsley [1]); that is, a suitably centered and scaled version of the process converges to a Brownian motion as the run length grows large. One implements an STS method by applying a "scaling function" b to a standardized version of the original process. Glynn and Iglehart [7] generalize the class of STS methods, study some of their theoretical asymptotic properties, and provide references that establish sufficient conditions under which a functional central limit theorem holds.
If we break the original path into a fixed number m of (nonoverlapping) batches, then each of the batches also satisfies a functional central limit theorem if the original process does. Hence, we can apply an STS method to each of the batches independently, and then combine the results using a p-norm, p [greater than or equal to] 1. Proposed by Schruben [11], this approach, which we call batching, is thus a way to take a given STS scaling function and derive new ones from it. Although batching is asymptotically valid (as run lengths grow to infinity), in practice, finite sample sizes can significantly degrade the performance (e.g., lower coverage) compared to no batching for the same basic STS scaling function. Because each batch is much shorter than the entire run length, the Brownian approximation will typically be worse for each batch than it is for the entire sample path.
In this paper, we introduce an approach for developing new STS methods from existing ones. The idea is based on dividing a sample path into segments and averaging an estimator over all paths obtained by permuting the path segments. (This is similar to an approach we developed for regenerative processes in Calvin and Nakayama [3, 4].) Specifically, suppose that the sample path is split into m equal-length segments, m [greater than or equal to] 2. Then, permuting the segments and piecing them together yields another sample path, which satisfies a functional central limit theorem if the original process does. (Note that we differentiate between the terms segments and batches.) We apply a scaling function b to each permuted sample path, and we obtain the permuted scaling function [[??].sub.m, p] by combining the values of b over all m! permutations using a p-norm, p [greater than or equal to] 1.
When permutations are combined with the 1-norm (i.e., p = 1), the expected value (respectively, variance) of [[??].sub.m, p] applied to the Brownian limit is the same as (respectively, no greater than) that for the nonpermuted scaling function b (see Theorem 5.1). Theorem 5.1 also shows that when p = 2, the mean (respectively, variance) of [[??].sub.m, p] applied to the Brownian limit is no less than (respectively, no greater than) that for the nonpermuted scaling function b. However, because the expected width of the limiting confidence interval also depends on an appropriate quantile point, as well as the expected value of the scaling function applied to the Brownian limit, the results in Theorem 5.1 do not tell the entire story about expected asymptotic confidence-interval widths. But we present theoretical and empirical results showing that permuting typically leads to smaller and less variable confidence intervals compared to the regular (i.e., nonpermuted and nonbatched) STS estimator. While empirical evidence shows that there is some degradation in coverage of confidence intervals based on permuted STS estimators (compared to the regular STS confidence intervals) when sample sizes are small, the effect is less pronounced than for batching for each value of m.
We demonstrate our approach by applying it to two examples of STS methods: the maximum estimator and the area estimator (Schruben [11]). We derive a simple representation of the permuted maximum estimator with m = 2 segments and p = 1. We also consider the case of the permuted maximum estimator for m > 2 and p = 1, but the resulting estimator requires a summation over m! terms, thus limiting the size of m that is feasible in practice. For the permuted area estimator with m [greater than or equal to] 2 and p = 2, we derive a representation that does not require explicitly summing over m! terms, and Calvin and Nakayama [6] present the same for the permuted version of Goldsman and Schruben's [9] weighted area estimator.
For the maximum estimator, analytical calculations show that permuting with m = 2 segments and p = 1 results in roughly a 25% reduction in the mean asymptotic half width of 90% confidence intervals, relative to that of the regular maximum estimator. We also compare analytically the expected asymptotic half widths when permuting m = 2 segments and batching with m = 2 batches, each with p = 1, and show that permuting leads to a slight reduction in expected half width. The asymptotic variability of the half widths is also reduced.
In addition, we show that asymptotically, the permuted area estimator (m [greater than or equal to] 2, p = 2) is equal in distribution to a function of two independent chi-square random variables. We use simulation to estimate the quantile points needed for constructing confidence intervals.
We also ran experiments with our estimators. For the maximum estimator, empirical results for up to m = 5 batches or segments indicate that permuting gives rise to shorter and less variable confidence intervals, compared to the regular maximum, but with virtually no loss in coverage. In contrast, batching also leads to shorter and less variable intervals than the regular maximum, but there is significant degradation in coverage. For the area and weighted area estimators, permuting and batching also improve on the regular estimator, but now with some loss in coverage for both. However, for each value of m [greater than or equal to] 2, batching consistently suffers worse degradation in coverage than permuting (with about the same average and variance of half width), so it appears that permuting outperforms batching in the small-sample context.
The maximum estimator we study has apparently not been considered before in the literature. Schruben [11] developed a similar approach, the standardized maximum, which is based on the maximum of a function divided by a function of the location at which the maximum occurs. In contrast, the maximum estimator we study is based only on the value of the maximum. Tokol et al. [13] propose an STS method based on the maximum of the absolute value.
Our permuting approach can also be used with other STS methods not considered here, but the main purpose of this...
NOTE: All illustrations and photos
have been removed from this article.
More articles from Mathematics of Operations Research
Evolutionary stability for large populations and backward induction., May 01, 2006
Job shop scheduling with unit processing times., May 01, 2006
The Hamilton apportionment method is between the Adams method and the ..., May 01, 2006
A linearly convergent dual-based gradient projection algorithm for qua..., May 01, 2006
Core stability of minimum coloring games., May 01, 2006
Looking for additional articles?
Search our database of over 3 million articles.
Looking for more in-depth information on this industry?
Search our complete database of Industry & Market reports by text, subject, publication
name or publication date.
About Goliath
Whether you're looking for sales prospects, competitive information, company
analysis or best practices in managing your organization,
Goliath can help you meet your business needs.
Our extensive business information databases empower business
professionals with both the breadth and depth of credible,
authoritative information they need to support their business
goals. Whether it be strategic planning, sales prospecting,
company research or defining management best practices -
Goliath is your leading source for accurate information.
|
