Analysis of the M X /G/1 Queue Under D-Policy

Abstract

We study the queue length of the M ^X /G/1 queue under D-policy. We derive the queue length PGF at an arbitrary point of time. Then, we derive the mean queue length. As special cases, M/G/1, M ^X /M/1, and M/M/1 queue under D-policy are investigated. Finally, the effects of employing D-policy are discussed.     

Tail Behaviour of the Area Under the Queue Length Process of the Single Server Queue with Regularly Varying Service Times

This paper considers a stable GI∨GI∨1 queue with a regularly varying service time distribution. We derive the tail behaviour of the integral of the queue length process Q(t) over one busy period. We show that the occurrence of a large integral is related to the occurrence of a large maximum of the queueing process over the busy period and we exploit asymptotic results for this variable. We also prove a central limit theorem for ∫₀^t Q(s) ds.AMS subject classification: 60K25, 90B22.     

On multivariate Gaussian tails

Let {X _{n, n} ≥1} be a sequence of standard Gaussian random vectors in ℝ _d ,d ≥ 2. In this paper we derive lower and upper bounds for the tail probabilityP{X _n >t _n } witht _n ∈ ℝ _d some threshold. We improve for instance bounds on Mills ratio obtained by Savage (1962,J. Res. Nat. Bur. Standards Sect. B,66, 93–96). Furthermore, we prove exact asymptotics under fairly general conditions on bothX _n andt _n , as ‖t _n ‖→∞ where the correlation matrix Σ _n ofX _n may also depend onn.     

Heavy Tails in Multi-Server Queue

In this paper, the asymptotic behaviour of the distribution tail of the stationary waiting time W in the GI/GI/2 FCFS queue is studied. Under subexponential-type assumptions on the service time distribution, bounds and sharp asymptotics are given for the probability P{W > x}. We also get asymptotics for the distribution tail of a stationary two-dimensional workload vector and of a stationary queue length. These asymptotics depend heavily on the traffic load. AMS subject classification: 60K25     

On the Potential Theory of One-dimensional Subordinate Brownian Motions with Continuous Components

Suppose that S is a subordinator with a nonzero drift and W is an independent 1-dimensional Brownian motion. We study the subordinate Brownian motion X defined by X _t  = W(S _t ). We give sharp bounds for the Green function of the process X killed upon exiting a bounded open interval and prove a boundary Harnack principle. In the case when S is a stable subordinator with a positive drift, we prove sharp bounds for the Green function of X in (0, ∞ ), and sharp bounds for the Poisson kernel of X in a bounded open interval.     

Asymptotic relation for the density of a multidimensional random evolution with rare poisson switchings

A symmetric random evolution X(t) = (X ₁ (t), …, X _m (t)) controlled by a homogeneous Poisson process with parameter λ > 0 is considered in the Euclidean space ℝ ^m , m ≥ 2. We obtain an asymptotic relation for the transition density p(x, t), t > 0, of the process X(t) as λ → 0 and describe the behavior of p(x, t) near the boundary of the diffusion domain in spaces of different dimensions. Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 60, No. 12, pp. 1631 – 1641, December, 2008.     

Queueing systems fed by many exponential on-off sources: an infinite-intersection approach

In queueing theory, an important class of events can be written as ‘infinite intersections’. For instance, in a queue with constant service rate c, busy periods starting at 0 and exceeding L > 0 are determined by the intersection of the events , i.e., queue Q _t is empty at 0 and for all t∊ [0, L] the amount of traffic A _t arriving in [0,t) exceeds the server capacity. Also the event of exceeding some predefined threshold in a tandem queue, or a priority queue, can be written in terms of this kind of infinite intersections. This paper studies the probability of such infinite intersections in queueing systems fed by a large number n of i.i.d. traffic sources (the so-called ‘many-sources regime’). If the sources are of the exponential on-off type, and the queueing resources are scaled proportional to n, the probabilities under consideration decay exponentially; we explicitly characterize the corresponding decay rate. The techniques used stem from large deviations theory (particularly sample-path large deviations). M. Mandjes is also with Korteweg-de Vries Institute, University of Amsterdam, Amsterdam, the Netherlands, and EURANDOM, Eindhoven, the Netherlands. Work done while P. Mannersalo was on leave at CWI. MSC 2000: 60F10 (Large deviations), 60K25 (Queueing theory)     

On bounds for bulk arrival queues

This paper gives a simple and effective approach pf deriving bounds for bulk arrival queues by making use of the bounds for single arrival queues. With this approach, upper bounds of mean actual/virtual waiting times and mean queue length at random epochs can be derived for the bulk arrival queues GI^X/G/1 and GI^X/G/c (lower bounds can be derived in a similar way). The merit of this approach is shown by comparing the bounds obtained with some existing results in the literature.     

Manifolds polarized by vector bundles

LetX be a complex projective manifold of dimension n and let ε be an ample vector bundle of rank r. Let also τ = τ (X,ε) = min {t ∈ ℝ : K_X + t det ε is nef} be the nef value of the pair (X, ε). In this paper we classify the pairs (X, ε) such that{ Mathematics Subject Classification (2000)14J60; 14J40; 14E30     

Decay rate for a PH/M/2 queue with shortest queue discipline

In this paper, we consider a PH/M/2 queue in which each server has its own queue and arriving customers join the shortest queue. For this model, it has been conjectured that the decay rate of the tail probabilities for the shortest queue length in the steady state is equal to the square of the decay rate for the queue length in the corresponding PH/M/2 model with a single queue. We prove this fact in the sense that the tail probabilities are asymptotically geometric when the difference of the queue sizes and the arrival phase are fixed. Our proof is based on the matrix analytic approach pioneered by Neuts and recent results on the decay rates. AMS subject classifications: 60K25 · 60K20 · 60F10 · 90B22     

On the Erlang Loss Model with Time Dependent Input

We consider the M(t)/M(t)/m/m queue, where the arrival rate λ(t) and service rate μ(t) are arbitrary (smooth) functions of time. Letting p_n(t) be the probability that n servers are occupied at time t (0≤ n≤ m, t > 0), we study this distribution asymptotically, for m→∞ with a comparably large arrival rate λ(t) = O(m) (with μ(t) = O(1)). We use singular perturbation techniques to solve the forward equation for p_n(t) asymptotically. Particular attention is paid to computing the mean number of occupied servers and the blocking probability p_m(t). The analysis involves several different space-time ranges, as well as different initial conditions (we assume that at t = 0 exactly n₀ servers are occupied, 0≤ n₀≤ m). Numerical studies back up the asymptotic analysis. AMS subject classification: 60K25,34E10 Supported in part by NSF grants DMS-99-71656 and DMS-02-02815     

On the Stationary Distribution of the GI X /M Y /1 Queueing System

For the GI ^X /M/1 queue, it has been recently proved that there exist geometric distributions that are stochastic lower and upper bounds for the stationary distribution of the embedded Markov chain at arrival epochs. In this note we observe that this is also true for the GI ^X /M ^Y /1 queue. Moreover, we prove that the stationary distribution of its embedded Markov chain is asymptotically geometric. It is noteworthy that the asymptotic geometric parameter is the same as the geometric parameter of the upper bound. This fact justifies previous numerical findings about the quality of the bounds.     

On the Beck‐Fiala conjecture for random set systems

Motivated by the Beck‐Fiala conjecture, we study discrepancy bounds for random sparse set systems. Concretely, these are set systems (X,Σ), where each element x ∈ X lies in t randomly selected sets of Σ, where t is an integer parameter. We provide new bounds in two regimes of parameters. We show that when |Σ| ≥ |X| the hereditary discrepancy of (X,Σ) is with high probability ; and when |X| ? |Σ|^t the hereditary discrepancy of (X,Σ) is with high probability O(1). The first bound combines the Lovász Local Lemma with a new argument based on partial matchings; the second follows from an analysis of the lattice spanned by sparse vectors.     

Reverse hypercontractivity over manifolds

Suppose thatX is a vector field on a manifoldM whose flow, exptX, exists for all time. If μ is a measure onM for which the induced measuresμ _t ≡(exptX)_* μ are absolutely continuous with respect to μ, it is of interest to establish bounds on theL ^p (μ) norm of the Radon-Nikodym derivativedμ _t /dμ. We establish such bounds in terms of the divergence of the vector fieldX. We then specilizeM to be a complex manifold and derive reverse hypercontractivity bounds and reverse logarithmic Sololev inequalities in some holomorphic function spaces. We give examples onC ^m and on the Riemann surface forz ^1/n . Research supported in part by CONACyT, Mexico, grant 32725-E. Research supported in part by CONACyT, Mexico, grant 32146-E.     

On stochastic integral representation of stable processes with sample paths in Banach spaces

Certain path properties of a symmetric α-stable process X(t) = ∫_Sh(t, s) dM(s), t T, are studied in terms of the kernel h. The existence of an appropriate modification of the kernel h enables one to use results from stable measures on Banach spaces in studying X. Bounds for the moments of the norm of sample paths of X are obtained. This yields definite bounds for the moments of a double α-stable integral. Also, necessary and sufficient conditions for the absolute continuity of sample paths of X are given. Along with the above stochastic integral representation of stable processes, the representation of stable random vectors due to[13], Ann. Probab.9, 624–632) is extensively used and the relationship between these two representations is discussed.     

An application of prophet regions to optimal stopping with a random number of observations

Let X ₁,X ₂ ,?…?be any sequence of nonnegative integrable random variables, and let N∈{1,2 , …} be a random variable with known distribution, independent of X ₁,X ₂ , …. The optimal stopping value sup _t E(X_t I(N≥ t)) is considered for two players: one who has advance knowledge of the value of N, and another who does not. Sharp ratio and difference inequalities relating the two players' optimal values are given in a number of settings. The key to the proofs is an application of a prophet region for arbitrarily dependent random variables by Hill and Kertz [T.P. Hill and R.P. Kertz (1983). Stop rule inequalities for uniformly bounded sequences of random variables. Trans. Amer. Math. Soc., 278, 197–207].     

Superposition of Spatially Interacting Aggregated Continuous Time Markov Chains

A system s{ X(t)} = {X ₁(t),X ₂(t),..., X _N(t)} of N interacting time reversible continuous time Markov chains is considered. The state space of each of the processes {X _i(t)} (i = 1, 2,...,N) is partitioned into two aggregates. Interaction between the processes {X _i(t)},{X ₂(t)},...,{X _N(t)} is introduced by allowing the transition rates of an individual process at time t to depend on the configuration of aggregates occupied by the other N - 1 processes at that time. The motivation for this work comes from ion channel modeling, where {(X}(t)} describes the gating mechanisms of N channels and the partitioning of the state space of {X _i(t)} correspond to whether the channel is conducting or not. Let S(t) denote the number of conducting channels at time t. For a time-reversible class of such processes, expressions are derived for the mean and probability density function of the sojourns of {S(t)} at its different levels when {X(t)} is in equilibrium. Particular attention is paid to the situation when the N channels are located on a circle with nearest neighbor interaction. Necessary and sufficient conditions for a general co-operative multiple channel system to be time reversible are derived.     

Randomly fractionally integrated processes

Philippe et al. [9], [10] introduced two distinct time-varying mutually invertible fractionally integrated filters A(d), B(d) depending on an arbitrary sequence d = (d _t ) _t∈ℤ of real numbers; if the parameter sequence is constant d _t ≡ d, then both filters A(d) and B(d) reduce to the usual fractional integration operator (1 − L)^−d . They also studied partial sums limits of filtered white noise nonstationary processes A(d)ε _t and B(d)ε _t for certain classes of deterministic sequences d. The present paper discusses the randomly fractionally integrated stationary processes X _t ^A = A(d)ε _t and X _t ^B = B(d)ε _t by assuming that d = (d _t , t ∈ ℤ) is a random iid sequence, independent of the noise (ε _t ). In the case where the mean , we show that large sample properties of X ^A and X ^B are similar to FARIMA(0, , 0) process; in particular, their partial sums converge to a fractional Brownian motion with parameter . The most technical part of the paper is the study and characterization of limit distributions of partial sums for nonlinear functions h(X _t ^A ) of a randomly fractionally integrated process X _t ^A with Gaussian noise. We prove that the limit distribution of those sums is determined by a conditional Hermite rank of h. For the special case of a constant deterministic sequence d _t , this reduces to the standard Hermite rank used in Dobrushin and Major [2]. Published in Lietuvos Matematikos Rinkinys, Vol. 47, No. 1, pp. 3–28, January–March, 2007.     

Prophet inequalities for cost of observation stopping problems

Comparisons are made between the expected gain of a prophet (an observer with complete foresight) and the maximal expected gain of a gambler (using only non-anticipating stopping times) observing a sequence of independent, uniformly bounded random variables where a non-negative fixed cost is charged for each observation. Sharp universal bounds are obtained under various restrictions on the cost and the length of the sequence. For example, it is shown for X₁, X₂, … independent, [0, 1]-valued random variables that for all c ≥ 0 and all n ≥ 1 that E(max_{1 ≤ j ≤ n}(X_j − jc)) − sup_{t Tn} E(X_t − tc) ≤ 1/e, where T_n is the collection of all stopping times t which are less than or equal to n almost surely.     

Queue length and waiting time of the M/G/1 queue under the D-policy and multiple vacations

We study the steady-state queue length and waiting time of the M/G/1 queue under the D-policy and multiple server vacations. We derive the queue length PGF and the LSTs of the workload and waiting time. Then, the mean performance measures are derived. Finally, a numerical example is presented and the effects of employing the D-policy are discussed. AMS Subject Classifications 60K25 This work was supported by the SRC/ERC program of MOST/KOSEF grant # R11-2000-073-00000.