Asymptotic analysis of the M/G/1 queue with a time‐dependent arrival rate

We consider the M/G/1 queue with an arrival rate λ that depends weakly upon time, as λ = λ(εt) where ε is a small parameter. In the asymptotic limit ε → 0, we construct approximations to the probability p _n(t)that η customers are present at time t. We show that the asymptotics are different for several ranges of the (slow) time scale Τ= εt. We employ singular perturbation techniques and relate the various time scales by asymptotic matching. This revised version was published online in June 2006 with corrections to the Cover Date.     

A decomposition theorem and related results for the discriminatory processor sharing queue

In this paper, we study a discriminatory processor sharing queue with Poisson arrivals,K classes and general service times. For this queue, we prove a decomposition theorem for the conditional sojourn time of a tagged customer given the service times and class affiliations of the customers present in the system when the tagged customer arrives. We show that this conditional sojourn time can be decomposed inton+1 components if there aren customers present when the tagged customer arrives. Further, we show that thesen+1 components can be obtained as a solution of a system of non-linear integral equations. These results generalize known results about theM/G/1 egalitarian processor sharing queue.     

Large number of queues in tandem: Scaling properties under back-pressure algorithm

We consider a system with N unit-service-rate queues in tandem, with exogenous arrivals of rate λ at queue 1, under a back-pressure (MaxWeight) algorithm: service at queue n is blocked unless its queue length is greater than that of the next queue n+1. The question addressed is how steady-state queues scale as N→∞. We show that the answer depends on whether λ is below or above the critical value 1/4: in the former case the queues remain uniformly stochastically bounded, while otherwise they grow to infinity.     

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     

Some first passage time problems for the shortest queue model

We consider the symmetric shortest queue (SQ) problem. Here we have a Poisson arrival stream of rate λ feeding two parallel queues, each having an exponential server that works at rate μ. An arrival joins the shorter of the two queues; if both are of equal length the arrival joins either with probability 1/2. We consider the first passage time until one of the queues reaches the value m ₀, and also the time until both reach this level. We give explicit expressions for the first two first passage moments, conditioned on the initial queue lengths, and also the full first passage distribution. We also give some asymptotic results for m ₀→∞ and various values of ρ=λ/μ. H. Yao work was partially supported by PSC-CUNY Research Award 68751-0037. C. Knessl work was supported in part by NSF grants DMS 02-02815 and DMS 05-03745.     

The asymptotic behavior of Chern-Simons Higgs model on a compact Riemann surface with boundary

We study the self-dual Chern-Simons Higgs equation on a compact Riemann surface with the Neumann boundary condition.In the previous paper,we show that the Chern-Simons Higgs equation with parameter λ0 has at least two solutions(uλ1,uλ2) for λ sufficiently large,which satisfy that uλ1→u0 almost everywhere as λ→∞,and that uλ2→∞ almost everywhere as λ→∞,where u 0 is a(negative) Green function on M.In this paper,we study the asymptotic behavior of the solutions as λ→∞,and prove that uλ2-uλ2 converges to a solution of the Kazdan-Warner equation if the geodesic curvature of the boundary M is negative,or the geodesic curvature is nonpositive and the Gauss curvature is negative where the geodesic curvature is zero.     

Asymptotic behavior of eigenvalues of two-parameter nonlinear Sturm-Liouville problems

The nonlinear two-parameter Sturm-Liouville problemu ^"+μg(u)=λf(u) is studied for μ, λ>0. By using Ljusternik-Schnirelman theory on the general level set developed by Zeidler, we shall show the existence of ann-th variational eigenvalue λ=λ_n(μ). Furthermore, for specialf andg, the asymptotic formula of λ₁(μ)) as μ→∞ is established.     

Moderate Deviations for Random Sums of Heavy-Tailed Random Variables

Let {Xn;n≥ 1} be a sequence of independent non-negative random variables with common distribution function F having extended regularly varying tail and finite mean μ = E（X1） and let {N（t）; t ≥0} be a random process taking non-negative integer values with finite mean λ（t） = E（N（t）） and independent of {Xn; n ≥1}. In this paper, asymptotic expressions of P（（X1 ＋… ＋XN（t）） -λ（t）μ 〉 x） uniformly for x ∈[γb（t）, ∞） are obtained, where γ〉 0 and b（t） can be taken to be a positive function with limt→∞ b（t）/λ（t） = 0.     

On samples of independent random vectors in spaces of infinitely increasing dimension

We study the asymptotic behavior of a set of random vectors ξ_i, i = 1,..., m, whose coordinates are independent and identically distributed in a space of infinitely increasing dimension. We investigate the asymptotics of the distribution of the random vectors, the consistency of the sets M _m⁽ⁿ⁾ = ξ₁,..., ξ_m and X _n^λ = x ∈ X _n: ρ(x) ≤ λn, and the mutual location of pairs of vectors. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 50, No. 12, pp. 1706–1711, December, 1998.     

Busy period analysis for <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">PH</Emphasis>/1 queues with workload dependent balking

We consider an M/PH/1 queue with workload-dependent balking. An arriving customer joins the queue and stays until served if and only if the system workload is no more than a fixed level at the time of his arrival. We begin by considering a fluid model where the buffer content changes at a rate determined by an external stochastic process with finite state space. We derive systems of first-order linear differential equations for the mean and LST (Laplace-Stieltjes Transform) of the busy period in this model and solve them explicitly. We obtain the mean and LST of the busy period in the M/PH/1 queue with workload-dependent balking as a special limiting case of this fluid model. We illustrate the results with numerical examples.      

Fluid and diffusion limits for transient sojourn times of processor sharing queues with time varying rates

We provide an approximate analysis of the transient sojourn time for a processor sharing queue with time varying arrival and service rates, where the load can vary over time, including periods of overload. Using the same asymptotic technique as uniform acceleration as demonstrated in [12] and [13], we obtain fluid and diffusion limits for the sojourn time of the M_t/M_t/1 processor-sharing queue. Our analysis is enabled by the introduction of a “virtual customer” which differs from the notion of a “tagged customer” in that the former has no effect on the processing time of the other customers in the system. Our analysis generalizes to non-exponential service and interarrival times, when the fluid and diffusion limits for the queueing process are known.     

On limit distributions emerging in the generalized Birnbaum-Saunders model

We establish that the Birnbaum-Saunders distribution is the equilibrium mixture of the inverse Gaussian distribution and the convolution of this distribution with the chi-square distribution with a single degree of freedom. We give a physical interpretation of this phenomenon in terms of probabilistic models of fatigue life and introduce a general family of so-called crack distributions, which contains, in particular, the normal distribution, the inverse Gaussian distribution, and the Birnbaum-Saunders distributions, as well as others used in applications of the theory of reliability. We pose the problem of isolating these particular distributions lying on the boundary of the parametric space of a crack distribution; to solve this problem, we analyze the asymptotic behavior of the likelihood function of the maximal invariant for a random sample of a crack distribution as the sample size n grows and for large values of the form parameter λ, when the crack distribution is approximated by the normal distribution. In either case, the likelihood function asymptotically depends on the sample data only through the U-statistics Σ _i=1 ⁿ X_i Σ _i=1 ⁿ X _i ⁻¹ . This result allows us to construct asymptotically uniformly most powerful invariant tests for n→∞ or λ→∞; the latter “parametric” scheme of asymptotic analysis of the likelihood is similar to LeCam’s theory of statistical experiments, where large values of n are formally replaced by large values of λ, whereas the sample size n remains fixed. Proceedings of the Seminar on Stability Problems for Stochastic Models, Vologda, Russia, 1998, Part I.     

Asymptotic properties of the algebraic moment range process

Let M _n denote the n-th moment space of the set of all probability measures on the interval [0, 1], P _n the uniform distribution on the set M _n and r _{n + 1} the maximal range of the (n + 1)-th moments corresponding to a random moment point C _n with distribution P _n on M _n . We study several asymptotic properties of the stochastic process (r _⌊nt⌋+1) _t∈[0,T] if n → ∞. In particular weak convergence to a Gaussian process and a large deviation principle are established.      

An infinite combinatorial statement with a poset parameter

We introduce an extension, indexed by a partially ordered set P and cardinal numbers κ,λ, denoted by (κ,<λ)⇝P, of the classical relation (κ,n,λ)→ρ in infinite combinatorics. By definition, (κ,n,λ)→ρ holds if every map F: [κ] ⁿ →[κ]^<λ has a ρ-element free set. For example, Kuratowski’s Free Set Theorem states that (κ,n,λ)→n+1 holds iff κ ≥ λ ⁺ⁿ , where λ ⁺ⁿ denotes the n-th cardinal successor of an infinite cardinal λ. By using the (κ,<λ)⇝P framework, we present a self-contained proof of the first author’s result that (λ ⁺ⁿ ,n,λ)→n+2, for each infinite cardinal λ and each positive integer n, which solves a problem stated in the 1985 monograph of Erdős, Hajnal, Máté, and Rado. Furthermore, by using an order-dimension estimate established in 1971 by Hajnal and Spencer, we prove the relation $(\lambda ^{ + (n - 1)} ,r,\lambda ) \to 2^{\left\lfloor {\tfrac{1} {2}(1 - 2^{ - r} )^{ - n/r} } \right\rfloor } $(\lambda ^{ + (n - 1)} ,r,\lambda ) \to 2^{\left\lfloor {\tfrac{1} {2}(1 - 2^{ - r} )^{ - n/r} } \right\rfloor } , for every infinite cardinal λ and all positive integers n and r with 2≤r<n. For example, (ℵ₂₁₀,4,ℵ₀)→32,768. Other order-dimension estimates yield relations such as (ℵ₁₀₉,4,ℵ₀) → 257 (using an estimate by Füredi and Kahn) and (ℵ₇,4,ℵ₀)→10 (using an exact estimate by Dushnik).     

Small deviations of the maximal element of a sequence of weighted independent random variables

Consider a sequence {X _i } of independent copies of a nonnegative random variable X and let M = sup _{j ≥ 1}λ _j X _j , where {λ _j } is a nonincreasing sequence of positive numbers for which P(M < ∞) = 1. The asymptotic behavior of -logP(M < r) as r → 0 is studied.     

The quotient field as a torsion-free covering module

R will denote a commutative integral domain with quotient fieldQ. A torsion-free cover of a moduleM is a torsion-free moduleF and anR-epimorphism σ:F→M such that given any torsion-free moduleG and λ∈Hom _R (G, M) there exists μ∈Hom _R (G,F) such that σμ=λ. It is known that ifM is a maximal ideal ofR, R→R/M is a torsion-free cover if and only ifR is a maximal valuation ring. LetE denote the injective hull ofR/M thenR→R/M extends to a homomorphismQ→E. We give necessary and sufficient conditions forQ→E to be a torsion-free cover.     

Stationary distribution of queue length in G / M / 1 queue with two-stage service policy

We consider a G / M / 1 queue with two-stage service policy. The server starts to serve with rate of μ₁ customers per unit time until the number of customers in the system reaches λ. At this moment, the service rate is changed to that of μ₂ customers per unit time and this rate continues until the system is empty. We obtain the stationary distribution of the number of customers in the system.     

On conditions for Dirichlet series absolutely convergent in a half-plane to belong to the class of convergence

Let M(σ) = sup{|F(σ + it)|: t ∈ ℝ} and μ(σ) = max {|a _n |exp(σλ_n): n ≥ 0}, σ < 0, for a Dirichlet series {fx995-01} with abscissa of absolute convergence σ_a = 0. We prove that the condition ln ln n = o(ln λ_n), n → ∞, is necessary and sufficient for the equivalence of the relations {fx995-02}, for each series of this type. Translated from Ukrains'kyi Matematychnyi Zhurnal, Vol. 60, No. 6, pp. 851–856, June, 2008.     

Analysis of the M/M/1 Queue with Processor Sharing via Spectral Theory

We show in this paper that the computation of the distribution of the sojourn time of an arbitrary customer in a M/M/1 with the processor sharing discipline (abbreviated to M/M/1 PS queue) can be formulated as a spectral problem for a self-adjoint operator. This approach allows us to improve the existing results for this queue in two directions. First, the orthogonal structure underlying the M/M/1 PS queue is revealed. Second, an integral representation of the distribution of the sojourn time of a customer entering the system while there are n customers in service is obtained.