Approximated Transient Queue Length and Waiting Time Distributions via Steady State Analysis

Abstract

We propose a method to approximate the transient performance measures of a discrete time queueing system via a steady state analysis. The main idea is to approximate the system state at time slot t or on the n-th arrival–-depending on whether we are studying the transient queue length or waiting time distribution–-by the system state after a negative binomially distributed number of slots or arrivals. By increasing the number of phases k of the negative binomial distribution, an accurate approximation of the transient distribution of interest can be obtained.

In order to efficiently obtain the system state after a negative binomially distributed number of slots or arrivals, we introduce so-called reset Markov chains, by inserting reset events into the evolution of the queueing system under consideration. When computing the steady state vector of such a reset Markov chain, we exploit the block triangular block Toeplitz structure of the transition matrices involved and we directly obtain the approximation from its steady state vector. The concept of the reset Markov chains can be applied to a broad class of queueing systems and is demonstrated in full detail on a discrete-time queue with Markovian arrivals and phase-type services (i.e., the D-MAP/PH/1 queue). We focus on the queue length distribution at time t and the waiting time distribution of the n-th customer. Other distributions, e.g., the amount of work left behind by the n-th customer, that can be acquired in a similar way, are briefly touched upon.

Using various numerical examples, it is shown that the method provides good to excellent approximations at low computational costs–-as opposed to a recursive algorithm or a numerical inversion of the Laplace transform or generating function involved–-offering new perspectives to the transient analysis of practical queueing systems.     

Costing Mixed Coxian Phase-type Systems with Poisson Arrivals

Previously, we developed a modeling framework which classifies individuals with respect to their length of stay (LOS) in the transient states of a continuous-time Markov model with a single absorbing state; phase-type models are used for each class of the Markov model. We here add costs and obtain results for moments of total costs in (0, t], for an individual, a cohort arriving at time zero and when arrivals are Poisson. Based on stroke patient data from the Belfast City Hospital we use the overall modelling framework to obtain results for total cost in a given time interval.     

Defective Galton–Watson processes

The Galton–Watson process is a Markov chain modeling the population size of independently reproducing particles giving birth to k offspring with probability p_k, k ? 0. In this paper, we consider defective Galton–Watson processes having defective reproduction laws, so that ∑_{k ? 0}p_k = 1 ? ? for some ? ∈ (0, 1). In this setting, each particle may send the process to a graveyard state Δ with probability ?. Such a Markov chain, having an enhanced state space {0, 1, …}∪{Δ}, gets eventually absorbed either at 0 or at Δ. Assuming that the process has avoided absorption until the observation time t, we are interested in its trajectories as t → ∞ and ? → 0.     

AN INFINITE-PHASE QUASI-BIRTH-AND-DEATH MODEL FOR THE NON-PREEMPTIVE PRIORITY M/PH/1 QUEUE

This paper considers a single server queue that handles arrivals from N classes of customers on a non-preemptive priority basis. Each of the N classes of customers features arrivals from a Poisson process at rate λ _i and class-dependent phase type service. To analyze the queue length and waiting time processes of this queue, we derive a matrix geometric solution for the stationary distribution of the underlying Markov chain. A defining characteristic of the paper is the fact that the number of distinct states represented within the sub-level is countably infinite, rather than finite as is usually assumed. Among the results we obtain in the two-priority case are tractable algorithms for the computation of both the joint distribution for the number of customers present and the marginal distribution of low-priority customers, and an explicit solution for the marginal distribution of the number of high-priority customers. This explicit solution can be expressed completely in terms of the arrival rates and parameters of the two service time distributions. These results are followed by algorithms for the stationary waiting time distributions for high- and low-priority customers. We then address the case of an arbitrary number of priority classes, which we solve by relating it to an equivalent three-priority queue. Numerical examples are also presented.     

The covariance of the number of renewals in a fixed time and the ensuing excess life

The covariance of the number of renewals in a fixed time N ^t and the ensuing excess life time Y ^t is derived using matrix-analytic methods for the stationary PH-renewal process. Specific results for the Erlang and hyperexponential processes are provided to illustrate the ease of computation. Properties concerning the sign and the behavior of the covariance as t→∞ are provided throughout. Parameter estimation for renewal processes which cannot be fully observed serves as the motivation for our derivations. These statistical applications as well as links to estimation for service time distributions in queues shed light on the type of problems for which the covariance is useful.     

Strong approximations for time-varying infinite-server queues with non-renewal arrival and service processes

In real stochastic systems, the arrival and service processes may not be renewal processes. For example, in many telecommunication systems such as internet traffic where data traffic is bursty, the sequence of inter-arrival times and service times are often correlated and dependent. One way to model this non-renewal behavior is to use Markovian Arrival Processes (MAPs) and Markovian Service Processes (MSPs). MAPs and MSPs allow for inter-arrival and service times to be dependent, while providing the analytical tractability of simple Markov processes. To this end, we prove fluid and diffusion limits for MAP_t/MSP_t/∞ queues by constructing a new Poisson process representation for the queueing dynamics and leveraging strong approximations for Poisson processes. As a result, the fluid and diffusion limit theorems illuminate how the dependence structure of the arrival or service processes can affect the sample path behavior of the queueing process. Finally, our Poisson representation for MAPs and MSPs is useful for simulation purposes and may be of independent interest.     

The covariance of the backward and forward recurrence times in a renewal process: the stationary case and asymptotics for the ordinary case

In a Poisson process, it is well-known that the forward and backward recurrence times at a given time point t are independent random variables. In a renewal process, although the joint distribution of these quantities is known (asymptotically), it seems that very few results regarding their covariance function exist. In the present paper, we study this covariance and, in particular, we state both necessary and sufficient conditions for it to be positive, zero or negative in terms of reliability classifications and the coefficient of variation of the underlying inter-renewal and the associated equilibrium distribution. Our results apply either for an ordinary renewal process in the steady state or for a stationary process.     

MARKOV CHAINS SATISFYING SIMPLE DRIFT CONDITIONS FOR SUBGEOMETRIC ERGODICITY

This paper is concerned with ergodic Markov chains satisfying a sequence of drift conditions that imply (f, r)- regularity of the chain, by which subgeometric ergodicity is ensured. An interesting exact trade-off result between the exponents of f and r for a special class of state space models by Tuominen and Tweedie (1994) is extended here from integers to real numbers for general Markov chains satisfying these drift conditions simultaneously as well as standard requirements for ergodic Markov chains. In Section 3, we will illustrate by the state space models that the utilization of these drift conditions is a very convenient way to show subgeometric ergodicity of Markov chains including the exact trade-off between the exponents of f and r.     

On the asymptotic distribution of an estimate of the change point in a failure rate

The failure rate r(t) is assumed to have the shape of the"first"part of the"bathtub"model, i.e.r(t) is non-increasing for t<r and is constant for t> r. Asymptotic distribution of one of the estimates proposed earlier has been investigated in this paper. This leads to a test for the hypothesis HQ r<r ₀ vs H :r>r (where TQ > 0). Asymptotic expression for the power of this test under Pitman alternatives is derived. Some simulations are reported.     

Estimation of the process incapability index

Greenwich and Jahr-Schaffrath (1995) introduced a new index C _pp a simple transformation of the index C _pm , which provides an uncontaminated separation between information concerning process accuracy and process precision. Under the assumption of normality, we first show that the estimators of C _pp proposed by Greenwich and Jahr-Schaffrath (1995) are UMVU estimators. We also show that for the inaccuracy index, the variance of the unbiased estimator is smaller than the mean squared error (MSE) of the natural (biased) estimator for n > 3. In addition, we obtain the r-th moment and the probability density function of these estimators.     

ON THE MAP/G/1 QUEUE WITH LEBESGUE-DOMINATED SERVICE TIME DISTRIBUTION AND LCFS PREEMPTIVE REPEAT SERVICE DISCIPLINE

The present paper contains an analysis of the MAP/G/1 queue with last come first served (LCFS) preemptive repeat service discipline and Lebesgue-dominated service time distribution. The transient distribution is given in terms of a recursive formula. The stationary distribution as well as the stability condition are obtained by means of Markov renewal theory via a QBD representation of the embedded Markov chain at departures and arrivals.     

SDP vs. LP Relaxations for the Moment Approach in Some Performance Evaluation Problems

Abstract

Given a Markov process, we are interested in the numerical computation of the moments of the exit time from a bounded domain. We use a moment approach which, together with appropriate semidefinite positivity moment conditions, yields a sequence of semidefinite programs (or SDP relaxations), depending on the number of moments considered, that provide a sequence of nonincreasing (resp. nondecreasing) upper (resp. lower) bounds. The results are compared to the linear Hausdorff moment conditions approach considered for the LP relaxations in Helmes et al. [Helmes, K., Röhl, S., Stockbridge, R.H. Computing moments of the exit time distribution for Markov processes by linear programming. Oper. Res. 2001, 49, 516–530]. The SDP relaxations are shown to be more general and more precise than the LP relaxations.     

Bayesian prediction of waiting times in stochastic models

The authors show how saddlepoint techniques lead to highly accurate approximations for Bayesian predictive densities and cumulative distribution functions in stochastic model settings where the prior is tractable, but not necessarily the likelihood or the predictand distribution. They consider more specifically models involving predictions associated with waiting times for semi‐Markov processes whose distributions are indexed by an unknown parameter θ. Bayesian prediction for such processes when they are not stationary is also addressed and the inverse‐Gaussian based saddlepoint approximation of Wood, Booth & Butler (1993) is shown to accurately deal with the nonstationarity whereas the normal‐based Lugannani & Rice (1980) approximation cannot, Their methods are illustrated by predicting various waiting times associated with M/M/q and M/G/1 queues. They also discuss modifications to the matrix renewal theory needed for computing the moment generating functions that are used in the saddlepoint methods.     

ON TRANSITION PROBABILITIES OF SKIP-FREE MARKOV CHAINS

Consider an ergodic Markov chain X(t) in continuous time with an infinitesimal matrix Q = (q_ij) defined on a finite state space {0, 1,…, N}. In this note, we prove that if X(t) is skip-free positive (negative, respectively), i.e., q_ij, = 0 for j > i+ 1 (i > j+ 1), then the transition probability p_ij(t) = Pr[X(t)=j | X(0) =i] can be represented as a linear combination of p_0N(t) (p^(m)_(N0)(t)), 0 ≤ m ≤N, where f^(m)(t) denotes the mth derivative of a function f(t) with f⁽⁰⁾(t) =f(t). If X(t) is a birth-death process, then p_ij(t) is represented as a linear combination of p_0N^(m)(t), 0 ≤m≤N - |i-j|.     

Estimation of Parameters of a Clipped MA(1) Process

Let {X _t , t ∈ ?} be a sequence of iid random variables with an absolutely continuous distribution. Let a > 0 and c ∈ ? be some constants. We consider a sequence of 0-1 valued variables {ξ _t , t ∈ ?} obtained by clipping an MA(1) process X _t  ? aX _t?1 at the level c, i.e., ξ _t  = I[X _t  ? aX _t?1 < c] for all t ∈ ?. We deal with the estimation problem in this model. Properties of the estimators of the parameters a and c, the success probability p, and the 1-lag autocorrelation r ₁ are investigated. A numerical study is provided as an illustration of the theoretical results.     

The Moment Bound is Tighter than Chernoff's Bound for Positive Tail Probabilities

Chernoff's bound on P[X ? t] is used almost universally when a tight bound on tail probabilities is required. In this article we show that for all positive t and for all distributions, the moment bound is tighter than Chernoff's bound. By way of example, we demonstrate that the improvement is often substantial.     

PORT Hill and Moment Estimators for Heavy-Tailed Models

In this article, we use the peaks over random threshold (PORT)-methodology, and consider Hill and moment PORT-classes of extreme value index estimators. These classes of estimators are invariant not only to changes in scale, like the classical Hill and moment estimators, but also to changes in location. They are based on the sample of excesses over a random threshold, the order statistic X _[np]+1:n , 0 ≤ p < 1, being p a tuning parameter, which makes them highly flexible. Under convenient restrictions on the underlying model, these classes of estimators are consistent and asymptotically normal for adequate values of k, the number of top order statistics used in the semi-parametric estimation of the extreme value index γ. In practice, there may however appear a stability around a value distant from the target γ when the minimum is chosen for the random threshold, and attention is drawn for the danger of transforming the original data through the subtraction of the minimum. A new bias-corrected moment estimator is also introduced. The exact performance of the new extreme value index PORT-estimators is compared, through a large-scale Monte-Carlo simulation study, with the original Hill and moment estimators, the bias-corrected moment estimator, and one of the minimum-variance reduced-bias (MVRB) extreme value index estimators recently introduced in the literature. As an empirical example we estimate the tail index associated to a set of real data from the field of finance.     

Heine process as a q-analog of the Poisson process—waiting and interarrival times

In this study, we introduce the Heine process, {X_q(t), t > 0}, 0 < q < 1, where the random variable X_q(t), for every t > 0, represents the number of events (occurrences or arrivals) during a time interval (0, t]. The Heine process is introduced as a q-analog of the basic Poisson process. Also, in this study, we prove that the distribution of the waiting time W_{ν, q}, ν ? 1, up to the νth arrival, is a q-Erlang distribution and the interarrival times T_{k, q} = W_{k, q} ? W_{k ? 1, q},?k = 1, 2, …, ν with W_{0, q} = 0 are independent and equidistributed with a q-Exponential distribution.     

Transient Analysis of Large Markov Models with Absorbing States Using Regenerative Randomization

ABSTRACT

In this article, we develop a new method, called regenerative randomization, for the transient analysis of continuous time Markov models with absorbing states. The method has the same good properties as standard randomization: numerical stability, well-controlled computation error, and ability to specify the computation error in advance. The method has a benign behavior for large t and is significantly less costly than standard randomization for large enough models and large enough t. For a class of models, class C, including typical failure/repair reliability models with exponential failure and repair time distributions and repair in every state with failed components, stronger theoretical results are available assessing the efficiency of the method in terms of “visible” model characteristics. A large example belonging to that class is used to illustrate the performance of the method and to show that it can indeed be much faster than standard randomization.     

MRL and MPL Functions of Parallel Systems with INID Components under Double Monitoring

This article investigates parallel systems with n independent but not identically distributed (INID) components. Under the condition that, at time t ₁ (t ₁ > 0) the total number of failures of the components is r (r < n), and at time t ₂ (t ₂ ≥ t ₁) the sys-tem is still working or it has failed, the mean residual life (MRL) function of the parallel system and the mean past lifetime (MPL) function of the components are conducted. Some representations and corresponding properties of the MRL function and the MPL function under several specific conditions are obtained.