Generalized Cornish-Fisher expansions

Cornish-Fisher expansions about the normal distribution provide accurate approximations for distributions of estimates and also for the level in the nominal error of confidence intervals. However, there is an advantage is expanding about a skew distribution like the chi-square, since the first order approximations become second order if the skewness is matched. Higher order approximations are also simplified. We demonstrate the method by approximating the distribution of standardized and Studentized linear combinations of means.     

Behaviour of queueing approximations based on sample moments

We investigate moment–based queueing approximations in the presence of sampling error. Let L be the steady–state mean number in the system for a GI/M/1 queue. We focus on the estimation of L under the assumption that only sample moments of the interarrival–time distribution are known. A simulation experiment is carried out for several interarrival–time distributions. For each case, sample moments from the interarrival–time distribution are matched to an approximating phase–type distribution and the corresponding estimate L is obtained. We show that the sampling error in the moments induces bias as well as variability in L. Based on our simulation experiment, we suggest matching only two moments when the sample coefficient of variation is low or when sample size is low; otherwise, matching three moments is preferable.     

Control and recovery from rare congestion events in a large multi-server system

We develop deterministic fluid approximations to describe the recovery from rare congestion events in a large multi-server system in which customer holding times have a general distribution. There are two cases, depending on whether or not we exploit the age distribution (the distribution of elapsed holding times of customers in service). If we do not exploit the age distribution, then the rare congestion event is a large number of customers present. If we do exploit the age distribution, then the rare event is an unusual age distribution, possibly accompanied by a large number of customers present. As an approximation, we represent the large multi-server system as an M/G/∞ model. We prove that, under regularity conditions, the fluid approximations are asymptotically correct as the arrival rate increases. The fluid approximations show the impact upon the recovery time of the holding-time distribution beyond its mean. The recovery time may or not be affected by the holding-time distribution having a long tail, depending on the precise definition of recovery. The fluid approximations can be used to analyze various overload control schemes, such as reducing the arrival rate or interrupting services in progress. We also establish large deviations principles to show that the two kinds of rare events have the same exponentially small order. We give numerical examples showing the effect of the holding-time distribution and the age distribution, focusing especially on the consequences of long-tail distributions. This revised version was published online in June 2006 with corrections to the Cover Date.     

Distribution sensitivity in a highway flow model

We examine a model of traffic flow on a highway segment, where traffic can be impaired by random incidents (usually, collisions). Using analytical and numerical methods, we show the degree of sensitivity that the model exhibits to the distributions of service times (in the queueing model) and incident clearance times. Its sensitivity to the distribution of time until an incident is much less pronounced. Our analytical methods include an M/G_t/∞ analysis (G_t denotes a service process whose distribution changes with time) and a fluid approximation for an M/M/c queue with general distributions for the incident clearance times. Our numerical methods include M/PH₂/c/K models with many servers and with phase‐type distributions for the time until an incident occurs or is cleared. We also investigate different time scalings for the rate of incident occurrence and clearance. Copyright © 2009 John Wiley & Sons, Ltd.     

Approximations for the <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">GI</Emphasis>/<Emphasis Type="Italic">N</Emphasis>+<Emphasis Type="Italic">GI</Emphasis> type call center

In this paper, we propose approximations to compute the steady-state performance measures of the M/GI/N+GI queue receiving Poisson arrivals with N identical servers, and general service and abandonment-time distributions. The approximations are based on scaling a single server M/GI/1+GI queue. For problems involving deterministic and exponential abandon times distributions, we suggest a practical way to compute the waiting time distributions and their moments using the Laplace transform of the workload density function. Our first contribution is numerically computing the workload density function in the M/GI/1+GI queue when the abandon times follow general distributions different from the deterministic and exponential distributions. Then we compute the waiting time distributions and their moments. Next, we scale-up the M/GI/1+GI queue giving rise to our approximations to capture the behavior of the multi-server system. We conduct extensive numerical experiments to test the speed and performance of the approximations, which prove the accuracy of their predictions.      

Queues with service times and interarrival times depending linearly and randomly upon waiting times

We consider a modification of the standardG/G/1 queue with unlimited waiting space and the first-in first-out discipline in which the service times and interarrival times depend linearly and randomly on the waiting times. In this model the waiting times satisfy a modified version of the classical Lindley recursion. We determine when the waiting-time distributions converge to a proper limit and we develop approximations for this steady-state limit, primarily by applying previous results of Vervaat [21] and Brandt [4] for the unrestricted recursionY _n+1=C _n Y _n +X _n . Particularly appealing for applications is a normal approximation for the stationary waiting time distribution in the case when the queue only rarely becomes empty. We also consider the problem of scheduling successive interarrival times at arrival epochs, with the objective of achieving nearly maximal throughput with nearly bounded waiting times, while making the interarrival time sequence relatively smooth. We identify policies depending linearly and deterministically upon the work in the system which meet these objectives reasonably well; with these policies the waiting times are approximately contained in a specified interval a specified fraction of time.     

Numerical approximations for the steady‐state waiting times in a GI/G/1 queue

This paper focuses on easily computable numerical approximations for the distribution and moments of the steadystate waiting times in a stable GI/G/1 queue. The approximation methodology is based on the theory of Fredholm integral equations and involves solving a linear system of equations. Numerical experimentation for various M/G/1 and GI/M/1 queues reveals that the methodology results in estimates for the mean and variance of waiting times within ±1% of the corresponding exact values. Comparisons with competing approaches establish that our methodology is not only more accurate, but also more amenable to obtaining waiting time approximations from the operational data. Approximations are also obtained for the distributions of steadystate idle times and interdeparture times. The approximations presented in this paper are intended to be useful in roughcut analysis and design of manufacturing, telecommunications, and computer systems as well as in the verification of the accuracies of inequalities, bounds, and approximations.     

Exact and approximate numerical solutions of steady-state distributions arising in the queueGI/G/1

In this paper we first obtain, in a unified way, closed-form analytic expressions in terms of roots of the so-called characteristic equation (c.e.), and then discuss the exact numerical solutions of steady-state distributions of (i) actual queueing time, (ii) virtual queueing time, (iii) actual idle time, and (iv) interdeparture time for the queueGI/R/1, whereR denotes the class of distributions whose Laplace-Stieltjes transforms (LSTs) are rational functions (ratios of a polynomial of degree at mostn to a polynomial of degreen). For the purpose of numerical discussions of idle- and interdeparture-time distributions, the interarrival-time distribution is also taken to belong to the classR. It is also shown that numerical computations of the idle-time distribution ofR/G/1 queues can be done even ifG is not taken asR. Throughout the discussions it is assumed that the queue discipline is first-come-first-served (FCFS). For the tail of the actual queueing-time distribution ofGI/R/1, approximations in terms of one or more roots of the c.e. are also discussed. If more than one root is used, they are taken in ascending order of magnitude. Numerical aspects have been tested for a variety of complex interarrival- and service-time distributions. The analysis is not restricted to generalized distributions with phases such as Coxian-n (C _n ), but also covers nonphase type distributions such as uniform (U) and deterministic (D). Some numerical results are also presented in the form of tables and figures. It is expected that the results obtained from the present study should prove to be useful not only to practitioners, but also to queueing theorists who would like to test the accuracies of inequalities, bounds or approximations.     

A numerically efficient method for the MAP/D/1/K queue via rational approximations

The Markovian Arrival Process (MAP), which contains the Markov Modulated Poisson Process (MMPP) and the Phase-Type (PH) renewal processes as special cases, is a convenient traffic model for use in the performance analysis of Asynchronous Transfer Mode (ATM) networks. In ATM networks, packets are of fixed length and the buffering memory in switching nodes is limited to a finite numberK of cells. These motivate us to study the MAP/D/1/K queue. We present an algorithm to compute the stationary virtual waiting time distribution for the MAP/D/1/K queue via rational approximations for the deterministic service time distribution in transform domain. These approximations include the well-known Erlang distributions and the Padé approximations that we propose. Using these approximations, the solution for the queueing system is shown to reduce to the solution of a linear differential equation with suitable boundary conditions. The proposed algorithm has a computational complexity independent of the queue storage capacityK. We show through numerical examples that, the idea of using Padé approximations for the MAP/D/1/K queue can yield very high accuracy with tractable computational load even in the case of large queue capacities.This work was done when the author was with the Bilkent University, Ankara, Turkey and the research was supported by TÜBITAK under Grant No. EEEAG-93.     

Convergence and error-bound analysis for mixed problems in compressible flow

We prove convergence and derive an error bound for a finite difference approximation to the discontinuous solution of the Na-vier-Stokes equations for nonisentropic, compressible flow in one-space dimension. The scheme can be implemented under appropriate mesh conditions, and it is shown that the approximations converge at a rate O(δx^¼). The error is measured in a norm which dominates the sup-norm of the error in the discontinuous variable.     

Waiting-time tail probabilities in queues with long-tail service-time distributions

We consider the standardGI/G/1 queue with unlimited waiting room and the first-in first-out service discipline. We investigate the steady-state waiting-time tail probabilitiesP(W>x) when the service-time distribution has a long-tail distribution, i.e., when the service-time distribution fails to have a finite moment generating function. We have developed algorithms for computing the waiting-time distribution by Laplace transform inversion when the Laplace transforms of the interarrival-time and service-time distributions are known. One algorithm, exploiting Pollaczek's classical contourintegral representation of the Laplace transform, does not require that either of these transforms be rational. To facilitate such calculations, we introduce a convenient two-parameter family of long-tail distributions on the positive half line with explicit Laplace transforms. This family is a Pareto mixture of exponential (PME) distributions. These PME distributions have monotone densities and Pareto-like tails, i.e., are of orderx ^–r forr>1. We use this family of long-tail distributions to investigate the quality of approximations based on asymptotics forP(W>x) asx. We show that the asymptotic approximations with these long-tail service-time distributions can be remarkably inaccurate for typicalx values of interest. We also derive multi-term asymptotic expansions for the waiting-time tail probabilities in theM/G/1 queue. Even three terms of this expansion can be remarkably inaccurate for typicalx values of interest. Thus, we evidently must rely on numerical algorithms for determining the waiting-time tail probabilities in this case. When working with service-time data, we suggest using empirical Laplace transforms.     

A graphical investigation of error bounds for moment-based queueing approximations

Many approximations of queueing performance measures are based on moment matching. Empirical and theoretical results show that although approximations based on two moments are often accurate, two-moment approximations can be arbitrarily bad and sometimes three-moment approximations are far better. In this paper, we investigate graphically error bounds for two- and three-moment approximations of three performance measures forGI/M/ · type models. Our graphical analysis provides insight into the adequacy of two- and three-moment approximations as a function of standardized moments of the interarrival-time distribution. We also discuss how the behavior of these approximations varies with other model parameters and with the performance measure being approximated.     

Nonstationary queues with Interrrupted Poisson arrivals and unreliable/repairable servers

A queueing model having a nonstationary Interrupted Poisson arrival process (IPP(t)),s time-dependent exponential unreliable/repairable servers and finite capacityc is introduced, and an approximation method for analysis of it is developed and tested. Approximations are developed for the time-dependent queue length moments and the system viewpoint waiting time distributions and moments. The approximation involves state-space partitioning and numerically integrating partial-moment differential equations (PMDEs). Surrogate distribution approximations (SDA's) are used to close the system of PMDEs. The approximations allow for analysis using only (s + 1)(s + 6) differential equations for the queue length moments rather than the 2(c + 1)(s +1) equations required by the classic method of numerically integrating the full set of Kolmogorov-forward equations. Effectively hours of cpu time are reduced to minutes for even modest capacity systems. Approximations for waiting time distributions and moments are developed.This research was partially funded by National Science Foundation grant ECS-8404409.     

Bayesian estimation of regression parameters in elliptical measurement error models

The main object of this paper is to discuss the Bayes estimation of the regression coefficients in the elliptically distributed simple regression model with measurement errors. The posterior distribution for the line parameters is obtained in a closed form, considering the following: the ratio of the error variances is known, informative prior distribution for the error variance, and non-informative prior distributions for the regression coefficients and for the incidental parameters. We proved that the posterior distribution of the regression coefficients has at most two real modes. Situations with a single mode are more likely than those with two modes, especially in large samples. The precision of the modal estimators is studied by deriving the Hessian matrix, which although complicated can be computed numerically. The posterior mean is estimated by using the Gibbs sampling algorithm and approximations by normal distributions. The results are applied to a real data set and connections with results in the literature are reported.     

基于加速失效时间模型模拟生存时间应用于检测生存性状位点

对于考察预指定情形下的统计模型的性能、性质及适应性,模拟研究是非常重要的统计工具.作为生存分析中两个最受欢迎的模型之一,由于加速失效时间模型中的因变量是生存时间的对数,且此模型能够以线性形式回归带有易解释的参数的协变量,从而加速失效模型比COX比例风险模型更便于拟合生存数据.首先提出了关于带有广义F-分布的加速失效模型的模拟研究中生成生存时间的方法,然后给出了描述加速失效时间模型的误差分布和相应的生存时间之间的一般的关系式,并给出了广义F-分布是如何生成生存时间的.最后,为证实所建议模拟技术的性能和有效性,将此方法应用于检测生存性状位点的模型中.     

Dominance-based Rough Set Approach to decision under uncertainty and time preference

We consider a problem of decision under uncertainty with outcomes distributed over time. We propose a rough set model based on a combination of time dominance and stochastic dominance. For the sake of simplicity we consider the case of traditional additive probability distribution over the set of states of the world, however, we show that the model is rich enough to handle non-additive probability distributions, and even qualitative ordinal distributions. The rough set approach gives a representation of decision maker’s time-dependent preferences under uncertainty in terms of “if…, then…” decision rules induced from rough approximations of sets of exemplary decisions.     

Refined Approximations for the Ewens Sampling Formula

The Ewens sampling formula is a family of probability distributions over the space of cycle types of permutations of n objects, indexed by a real parameter θ. In the case θ = 1, where the distribution reduces to that induced by the uniform distribution on all permutations, the joint distributions of the numbers of cycles of lengths less than b = o(n) is extremely well approximated by a product of Poisson distributions, having mean 1/j for cycle length j: the error is super-exponentially small with nb^?1. For θ ≠ 1. the analogous approximation, with means adjusted to θ/j, is good, but with error only linear in n^?1b. In this article, it is shown that, by choosing the means of the Poisson distributions more carefully, an error quadratic in n^?1b can be achieved, and that essentially nothing better is possible.     

Approximating Probability Distributions Using Small Sample Spaces

We formulate the notion of a "good approximation" to a probability distribution over a finite abelian group ?. The quality of the approximating distribution is characterized by a parameter ɛ which is a bound on the difference between corresponding Fourier coefficients of the two distributions. It is also required that the sample space of the approximating distribution be of size polynomial in and 1/ɛ. Such approximations are useful in reducing or eliminating the use of randomness in certain randomized algorithms. We demonstrate the existence of such good approximations to arbitrary distributions. In the case of n random variables distributed uniformly and independently over the range , we provide an efficient construction of a good approximation. The approximation constructed has the property that any linear combination of the random variables (modulo d) has essentially the same behavior under the approximating distribution as it does under the uniform distribution over . Our analysis is based on Weil's character sum estimates. We apply this result to the construction of a non-binary linear code where the alphabet symbols appear almost uniformly in each non-zero code-word. Received: September 22, 1990/Revised: First revision November 11, 1990; last revision November 10, 1997     

Two-parameter heavy-traffic limits for infinite-server queues

In order to obtain Markov heavy-traffic approximations for infinite-server queues with general non-exponential service-time distributions and general arrival processes, possibly with time-varying arrival rates, we establish heavy-traffic limits for two-parameter stochastic processes. We consider the random variables Q ^e (t,y) and Q ^r (t,y) representing the number of customers in the system at time t that have elapsed service times less than or equal to time y, or residual service times strictly greater than y. We also consider W ^r (t,y) representing the total amount of work in service time remaining to be done at time t+y for customers in the system at time t. The two-parameter stochastic-process limits in the space D([0,∞),D) of D-valued functions in D draw on, and extend, previous heavy-traffic limits by Glynn and Whitt (Adv. Appl. Probab. 23, 188–209, 1991), where the case of discrete service-time distributions was treated, and Krichagina and Puhalskii (Queueing Syst. 25, 235–280, 1997), where it was shown that the variability of service times is captured by the Kiefer process with second argument set equal to the service-time c.d.f.     

Discretization error of irregular sampling approximations of stochastic integrals

This paper studies the limit distributions for discretization error of irregular sampling approximations of stochastic integral. The irregular sampling approximation was first presented in Hayashi et al.[3], which was more general than the sampling approximation in Lindberg and Rootz′en [10]. As applications, we derive the asymptotic distribution of hedging error and the Euler scheme of stochastic differential equation respectively.