Run length not required: Optimal-mse dynamic batch means estimators for steady-state simulations

This paper addresses the estimation of the variance of the sample mean from steady-state simulations without requiring the knowledge of simulation run length a priori. Dynamic batch means is a new and useful approach to implementing the traditional batch means in limited memory without the knowledge of the simulation run length. However, existing dynamic batch means estimators do not allow one to control the value of batch size, which is the performance parameter of the batch means estimators. In this work, an algorithm is proposed based on two dynamic batch means estimators to dynamically estimate the optimal batch size as the simulation runs. The simulation results show that the proposed algorithm requires reasonable computation time and possesses good statistical properties such as small mean-squared-error (mse).     

Joint economic design of EWMA control charts for mean and variance

Control charts with exponentially weighted moving average (EWMA) statistics (mean and variance) are used to jointly monitor the mean and variance of a process. An EWMA cost minimization model is presented to design the joint control scheme based on pure economic or both economic and statistical performance criteria. The pure economic model is extended to the economic-statistical design by adding constraints associated with in-control and out-of-control average run lengths. The quality related production costs are calculated using Taguchi’s quadratic loss function. The optimal values of smoothing constants, sampling interval, sample size, and control chart limits are determined by using a numerical search method. The average run length of the control scheme is computed by using the Markov chain approach. Computational study indicates that optimal sample sizes decrease as the magnitudes of shifts in mean and/or variance increase, and higher values of quality loss coefficient lead to shorter sampling intervals. The sensitivity analysis results regarding the effects of various inputs on the chart parameters provide useful guidelines for designing an EWMA-based process control scheme when there exists an assignable cause generating concurrent changes in process mean and variance.     

Optimization designs and performance comparison of two CUSUM schemes for monitoring process shifts in mean and variance

In statistical process control (SPC), when dealing with a quality characteristic x that is a variable, it is usually necessary to monitor both the mean value and variability. This article proposes an optimization algorithm (called the holistic algorithm) to design the CUSUM charts for this purpose. It facilitates the determination of the charting parameters of the CUSUM charts and considerably or significantly increases their overall detection effectiveness. A single CUSUM chart (called the ABS CUSUM chart) has been developed by the holistic algorithm and fully investigated. This chart is able to detect two-sided mean shifts and increasing variance shifts by inspecting the absolute value of sample mean shift. The results of performance studies show that the overall performance of the ABS CUSUM chart is nearly as good as an optimal 3-CUSUM scheme (a scheme incorporating three individual CUSUM charts). However, since the ABS CUSUM chart is easier for implementation and design, it may be more suitable for many SPC applications in which both mean and variance of a variable have to be monitored.     

Variance Reduction Techniques

Estimating real-world parameter values by means of Monte-Carlo/stochastic simulation is usually accomplished by carrying out a number ‘n’ of computer runs, each using random numbers taken from a pseudo-random number generator. In order to improve the accuracy of the estimate (reduce the estimate's variance), the most common recourse is to increase n, as the estimate's variance is inversely proportional to n. Variance reduction techniques provide an alternative to increasing n. They use statistical approaches which obtain more information from the computer runs conducted, or control and direct the pseudo-random streams to optimize the information likely to be produced by a run.     

A note on levene's tests for equality of variances

Consider testing for equality variances in a one-way analysis of variance. Levene's test is the usual F-test for equality of means computed on psuedo-observations, which one defines as the absolute deviations of the data points from an estimate of the group ‘center’. We show that, asymptotically, Levene's test has the correct level whenever the estimate of group ‘center’ is an estimate of group median. This explains why published Monte-Carlo studies have found that Levene's original proposal of centering at the sample mean has the correct level only for symmetric distributions, while centering at the sample median has correct level even for asymmetric distributions. Generalizations are discussed.     

On the estimation of optimal batch sizes in the analysis of simulation output

The estimation of the variance of point estimators is a classical problem of stochastic simulation. A more specific problem addresses the estimation of the variance of a sample mean from a steady-state autocorrelated process. Many proposed estimators of the variance of the sample mean are parameterized by batch size. A critical problem is to find an appropriate batch size that provides a good tradeoff between bias and variance. This paper proposes a procedure for determining the optimal batch size to minimize the mean squared error of estimators of the variance of the sample mean. This paper also presents the results of empirical studies of the procedure. The experiments involve symmetric two-state Markov chain models, first-order autoregressive processes, seasonal autoregressive processes, and queue-waiting times for several M/M/1 queueing models. The empirical results indicate that the estimation procedure works nearly as well as it would if the parameters of the processes were known.     

Antithetic Bias Reduction for Discrete-Event Simulations

This study presents a technique for reducing the bias induced by arbitrary initial conditions in some discrete simulation studies. The technique relies on compensating the existing bias in a run by purposely introducing a deviation in the counter-direction during the subsequent run. Specifically, after obtaining a sample with initial condition X₀, an antithetic companion run is generated starting from (2X? - X₀). This introduces an adjustment equal and opposite to the indicated deviation, as measured by the distance between the current sample mean X? and the initial condition X₀. Then the overall mean has a significantly lower bias. Application of the technique to first-order autoregressive process and to a machine-repair system revealed that it is capable of reducing, and in most cases practically removing, the transient effects within moderate sample sizes.     

Automated selection of the number of replications for a discrete-event simulation

Selecting an appropriate number of replications to run with a simulation model is important in assuring that the desired accuracy and precision of the results are attained with minimal effort. If too few are selected then accuracy and precision are lost; if too many are selected then valuable time is wasted. Given that simulation is often used by non-specialists, it seems important to provide guidance on the number of replications required with a model. In this paper an algorithm for automatically selecting the number of replications is described. Test results show the algorithm to be effective in obtaining coverage of the expected mean at a given level of precision and in reducing the bias in the estimate of the mean of the simulation output. The algorithm is consistent in selecting the expected number of replications required for a model output.     

An alternative to ratio method in sample surveys

Summary This paper examines a simple transformation which enables the use of product method in place of ratio method. The convenience with the former, proposed by Murthy [3], is that expressions for bias and mean square error (mse) can be exactly evaluated. The optimum situation in the minimum mse sense and allowable departures from this optimum are indicated. The procedure requires a good guess of a certain parameter, which does not seem very restrictive for practice. Two methods for dealing with the bias of the estimator are mentioned. An extension to use multiauxiliary information is outlined.     

Ranking ranks: a ranking algorithm for bootstrapping from the empirical copula

Nonparametric copula models are based on observations whose distributions are generally unknown. Estimation of these copula models is based on pseudo-observations consisting of the ranked data. To determine distributional properties (e.g., the variance) of the models and their estimators, resampling methods such as bootstrapping are involved. These methods require drawing samples with replacement from the ranked data. The newly generated samples have to be reranked and existing ties have to be solved by mid-ranks. Since a large number of samples has to be generated in order to attain a suitable accuracy of the estimate, the speed of the algorithm for reranking the samples highly affects the overall computation time. However, commonly used ranking procedures are computationally expensive and their running time is of order O(n* log(n*) + n*). We discuss a faster, more feasible approach using the specific copula setting with a running time that is only of order O(n + n*), where n denotes the sample size and n* the size of the bootstrap sample. In a simulation study, the algorithm performs up to 9 times faster than Matlab’s tiedrank.m-procedure.     

On the dispersion matrix of variance estimators of the sample mean in the analysis of simulation output

A classical problem of stochastic simulation is how to estimate the variance of point estimators, the prototype problem being the sample mean from a steady-state autocorrelated process. A variety of estimators for the variance of the sample mean have been proposed, all designed to provide robustness to violations of assumptions, small variance, and reasonable computing requirements. Evaluation and comparison of such estimators depend on the ability to calculate their variances.A numerical approach is developed here to calculate the dispersion matrix of a set of estimators expressible as quadratic forms of the data. The approach separates the analysis of the estimator type from the analysis of the data type. The analysis for overlapping-batch-means estimators is developed, as is the analysis for steady-state first-order autoregressive and moving-average data. Closed-form expressions for overlapping-batch-means estimators and independently distributed data are obtained.     

An adaptive estimation of MAVE

Minimum average variance estimation (MAVE, Xia et al. (2002) [29]) is an effective dimension reduction method. It requires no strong probabilistic assumptions on the predictors, and can consistently estimate the central mean subspace. It is applicable to a wide range of models, including time series. However, the least squares criterion used in MAVE will lose its efficiency when the error is not normally distributed. In this article, we propose an adaptive MAVE which can be adaptive to different error distributions. We show that the proposed estimate has the same convergence rate as the original MAVE. An EM algorithm is proposed to implement the new adaptive MAVE. Using both simulation studies and a real data analysis, we demonstrate the superior finite sample performance of the proposed approach over the existing least squares based MAVE when the error distribution is non-normal and the comparable performance when the error is normal.     

Error analysis for regenerative queueing estimators with special reference to gradient estimators via likelihood ratio

The performance of telecommunications systems is typically estimated (either analytically or by simulation) via queueing theoretic models. The gradient of the expected performance with respect to the various parameters (such as arrival rate or service rate) is very important as it not only measures the sensitivity to change, but is also needed for the solution of optimization problems. While the estimator for the expected performance is the sample mean of the simulation experiment, there are several possibilities for the estimator of the gradient. They include the obvious finite difference approximation, but also other recently advocated techniques, such as estimators derived from likelihood ratio transformations or from infinitesimal perturbations. A major problem in deciding upon which estimator to use and in planning the length of the simulation has been the scarcity of analytical error calculations for estimators of queueing models. It is this question that we answer in this paper for the waiting time moments (of arbitrary order) of theM / G / 1 queue by using the queueing analysis technique developed by Shalmon. We present formulas for the error variance of the estimators of expectation and of its gradient as a function of the simulation length; at arbitrary traffic intensity the formulas are recursive, while the heavy traffic approximations are explicit and of very simple form. For the gradient of the mean waiting time with respect to the arrival (or service) rate, and at 1 percent relative precision, the heavy traffic formulas show that the likelihood ratio estimator for the gradient reduces the length of the simulation required by the finite difference estimator by about one order of magnitude; further increasing the relative precision by a factor increases the reduction advantage by the same factor. At any relative precision, it exceeds the length of the simulation required for the estimation of the mean with the same relative precision by about one order of magnitude. While strictly true for theM / G / 1 queue, the formulas can also be used as guidelines in the planning of queueing simulations and of stochastic optimizations of complex queueing systems, particularly those with Poisson arivals.     

The disteribution of a moment estimator for a parameter of the generalized poision distribution

The ratio of the sample variance to the sample mean estimates a simple function of the parameter which measures the departure of the Poisson-Poisson from the Poisson distribution. Moment series to order n²⁴ are given for related estimators. In one case, exact integral formulations are given for the first two moments, enabling a comparison to be made between their asymptotic developments and a computer-oriented extended Taylor series (COETS) algorithm. The integral approach using generating functions is sketched out for the third and fourth moments. Levin's summation algorithm is used on the divergent series and comparative simulation assessments are given.     

Parametric Estimation of a Boolean Segment Process with Stochastic Restoration Estimation

Abstract

We propose a stochastic restoration estimation (SRE) algorithm to estimate the parameters of the length distribution of a boolean segment process. A boolean segment process is a stochastic process obtained by considering the union of independent random segments attached to random points independently scattered on the plane. Each iteration of the SRE algorithm has two steps: first, censored segments are restored; second, based on these restored data, parameter estimations are updated. With a usually straightforward implementation, this algorithm is particularly interesting when censoring effects are difficult to take into account. We illustrate this method in two situations where the parameter of interest is either the mean of the segment length distribution or the variance of its logarithm. Its application to vine shoot length distribution estimation is presented.     

Dispersion of mass and the complexity of randomized geometric algorithms

How much can randomness help computation? Motivated by this general question and by volume computation, one of the few instances where randomness provably helps, we analyze a notion of dispersion and connect it to asymptotic convex geometry. We obtain a nearly quadratic lower bound on the complexity of randomized volume algorithms for convex bodies in Rn (the current best algorithm has complexity roughly n⁴, conjectured to be n³). Our main tools, dispersion of random determinants and dispersion of the length of a random point from a convex body, are of independent interest and applicable more generally; in particular, the latter is closely related to the variance hypothesis from convex geometry. This geometric dispersion also leads to lower bounds for matrix problems and property testing.     

线性混合模型中方差分量的估计与QR分解

在线性混合模型中, 极大似然估计是一种很重要的估计方法, 但是它常常需要通过迭代求解. 应用设计阵的QR分解, 可以把设计阵变换成上三角矩阵. 这样可以降低参与迭代运算的矩阵的阶数, 还可以减少参与运算的数据量, 从而提高运算的速度. 本文讨论了QR分解在EM算法中的应用, 并用模拟的方法验证了QR分解可以极大的提高运算的速度. 本文同时讨论了QR分解在另外一种估计方法, 即ANOVA估计中的应用.     

Offline and online weighted least squares estimation of nonstationary power ARCH processes

This paper proposes two estimation methods based on a weighted least squares criterion for non-(strictly) stationary power ARCH models. The weights are the squared volatilities evaluated at a known value in the parameter space. The first method is adapted for fixed sample size data while the second one allows for online data available in real time. It will be shown that these methods provide consistent and asymptotically Gaussian estimates having asymptotic variance equal to that of the quasi-maximum likelihood estimate (QMLE) regardless of the value of the weighting parameter. Finite-sample performances of the proposed WLS estimates are shown via a simulation study for various sub-classes of power ARCH models.     

对于部分线性模型的乘积调整半参估计

本文使用一种带有乘积调整的半参方法估计部分线性模型的非参数部分并给出所得估计的渐近性质。与传统的非参估计方法相比,我们所使用的半参数方法能够有效的降低所得估计的偏差,而方差不受影响。因此在积分均方误差(MISE)的意义下,该半参数方法要优于传统的估计方法。数值模拟也表明了这一点.     

Size of random Galois lattices and number of closed frequent itemsets

Given a sample of binary random vectors with i.i.d. Bernoulli(p) components, that is equal to 1 (resp. 0) with probability p (resp. 1−p), we first establish a formula for the mean of the size of the random Galois lattice built from this sample, and a more complex one for its variance. Then, noticing that closed α-frequent itemsets are in bijection with closed α-winning coalitions, we establish similar formulas for the mean and the variance of the number of closed α-frequent itemsets. This can be interesting for the study of the complexity of some data mining problems such as association rule mining, sequential pattern mining and classification.