Diffusion Approximation in Overloaded Switching Queueing Models

The asymptotic behavior of a queueing process in overloaded state-dependent queueing models (systems and networks) of a switching structure is investigated. A new approach to study fluid and diffusion approximation type theorems (without reflection) in transient and quasi-stationary regimes is suggested. The approach is based on functional limit theorems of averaging principle and diffusion approximation types for so-called Switching processes. Some classes of state-dependent Markov and non-Markov overloaded queueing systems and networks with different types of calls, batch arrival and service, unreliable servers, networks (M _SM,Q /M _SM,Q /1/) ^r switched by a semi-Markov environment and state-dependent polling systems are considered.     

Switching stochastic models and applications in retrial queues

Some special classes of Switching Processes such as Recurrent Processes of a Semi-Markov type and Processes with Semi-Markov Switches are introduced. Limit theorems of Averaging Principle and Diffusion Approximation types are given. Applications to the asymptotic analysis of overloading state-dependent Markov and semi-Markov queueing modelsM _SM,Q /M _SM,Q /1/∞ and retrial queueing systemsM/G/1/w.r in transient conditions are studied. The paper was supported by INTAS Project 96-0828     

On the Asymptotic Solution of Non-Hamiltonian Systems Exhibiting Sustained Resonance

With the exception of some special examples, much of the literature on the formal construction of asymptotic solutions of systems exhibiting sustained resonance concerns Hamiltonian problems, for which the reduced problem is of order two when a single resonance is present. In the Hamiltonian case, the resonance manifold is a curve that is explicitly defined by the governing equations and is independent of the actual sustained resonance solution. When the basic standard form system is non-Hamiltonian, with M slow and N fast variables, the corresponding reduced problem is of order M + 1; in general it involves all of the slow variables, P₁,…, P_M, plus the resonant phase Q. In this paper, the solution of a general non-Hamiltonian system in standard form is formally constructed for the case of a single sustained resonance. First, a well-known example is reviewed, for which the projection of the solutions on the resonance manifold can be derived a priori, independent of the evolution of Q. Then, the general case is solved, using a generalization of the multiple scale method of Kuzmak-Luke, where knowledge of the asymptotic solution for Q (as well as higher-order terms) is needed to define the projection of the solution on the resonance manifold. The results simplify significantly when initial conditions are chosen exactly on the resonance manifold; the modifications necessary for arbitrary initial conditions are also given. Two examples are discussed in detail to illustrate the procedure. The asymptotic results are confirmed for several test cases by comparison with numerical integrations of the exact equations.     

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.     

Robust M-estimators in diffusion processes

Methods of robust estimation in diffusion processes are given by means of M-estimation. It is shown that the asymptotic variance of an M-estimator is obtained by applying a certain integral operator to the influence function and integrating its square. Under the condition of boundedness of the influence function, the existence of an optimal robust M-estimator is shown and an approximately optimal practical method is given. Moreover, as another criterion of robustness we consider a norm of integral type and show that the corresponding optimal robust M-estimator is obtained by solving a boundary value problem of a second order differential equation. Finally, as an illustrative example the Ornstein-Uhlenbeck process is discussed.     

Asymptotic behavior of eigenvalues and random updating schemes

For a stochastic matrix (Q _ij ^T ) _i,j=1 ^M withQ _ij ^T exp(–U(ij)/T) at the off-diagonal positions, we develop an algorithm to evaluate the asymptotic convergence rate of all eigenvalues ofQ _ij ^T asT 0 using Ventcel's optimal graphs. As an application we can compare the convergence rates of some random updating schemes used in image processing.This research was partially supported by the National Science Council, Taiwan and Air Force Office of Scientific Research Contract No. F49620 S5C 0144, and was completed while Tzuu-Shuh Chiang was visiting the Center for Stochastic Processes, Department of Statistics, University of North Carolina, Chapel Hill, NC 27599-3260, USA.     

Nondegenerate cohomology pairing for transitive Lie algebroids,characterization

The Evens-Lu-Weinstein representation (Q _A , D) for a Lie algebroid A on a manifold M is studied in the transitive case. To consider at the same time non-oriented manifolds as well, this representation is slightly modified to (Q _A ^or , D^or) by tensoring by orientation flat line bundle, Q _A ^or =Q_A⊗or (M) and D ^or=D⊗∂ _A ^or . It is shown that the induced cohomology pairing is nondegenerate and that the representation (Q _A ^or , D^or) is the unique (up to isomorphy) line representation for which the top group of compactly supported cohomology is nontrivial. In the case of trivial Lie algebroid A=TM the theorem reduce to the following: the orientation flat bundle (or (M), ∂ _A ^or ) is the unique (up to isomorphy) flat line bundle (ξ, ∇) for which the twisted de Rham complex of compactly supported differential forms on M with values in ξ possesses the nontrivial cohomology group in the top dimension. Finally it is obtained the characterization of transitive Lie algebroids for which the Lie algebroid cohomology with trivial coefficients (or with coefficients in the orientation flat line bundle) gives Poincaré duality. In proofs of these theorems for Lie algebroids it is used the Hochschild-Serre spectral sequence and it is shown the general fact concerning pairings between graded filtered differential ℝ-vector spaces: assuming that the second terms live in the finite rectangular, nondegeneration of the pairing for the second terms (which can be infinite dimensional) implies the same for cohomology spaces.     

Asymptotic analysis for loss probability of queues with finite <Emphasis Type="Italic">GI</Emphasis>/<Emphasis Type="Italic">M</Emphasis>/1 type structure

This paper discusses the asymptotic behavior of the loss probability for general queues with finite GI/M/1 type structure such as GI/M/c/K, SM/M/1/K and GI/MSP/1/K queues. We find an explicit expression for the asymptotic behavior of the loss probability as K tends to infinity. With the result, it is shown that the loss probability tends to 0 at a geometric rate. This research was supported by the MIC (Ministry of Information and Communication), Korea, under the ITRC (Information Technology Research Center) support program supervised by the IITA (Institute of Information Technology Assessment).     

Third-order asymptotic expansion of <Emphasis Type="Italic">M</Emphasis>-estimators for diffusion processes

For an unknown parameter in the drift function of a diffusion process, we consider an M-estimator based on continuously observed data, and obtain its distributional asymptotic expansion up to the third order. Our setting covers the misspecified cases. To represent the coefficients in the asymptotic expansion, we derive some formulas for asymptotic cumulants of stochastic integrals, which are widely applicable to many other problems. Furthermore, asymptotic properties of cumulants of mixing processes will be also studied in a general setting.     

Asymptotic expansions for the conditional sojourn time distribution in the <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">M</Emphasis>/1-PS queue

We consider the M/M/1 queue with processor sharing. We study the conditional sojourn time distribution, conditioned on the customer’s service requirement, in various asymptotic limits. These include large time and/or large service request, and heavy traffic, where the arrival rate is only slightly less than the service rate. The asymptotic formulas relate to, and extend, some results of Morrison (SIAM J. Appl. Math. 45:152–167, [1985]) and Flatto (Ann. Appl. Probab. 7:382–409, [1997]). This work was partly supported by NSF grant DMS 05-03745.     

Independence results for uncountable superstable theories

We prove that the following statement is independent of ZFC+┐CH: IFT is a superstable theory of power <2^ℵ ₀,M≰N are models ofT withQ(M)=Q(N), then there isN′≱N withQ(N)=Q(N′). This generalizes Lachlan’s (1972) result.     

Effect of the initial estimator on the asymptotic behavior of one-step M-estimator

For a general (real) parameter, let M _nbe the M-estimator and M _n ⁽¹⁾ be its one-step version (based on a suitable initial estimator M _n ⁽⁰⁾). It is known that, under certain regularity conditions, n(M _n ⁽¹⁾-M _n)=O _p(1). The asymptotic distribution of n(M _n ⁽¹⁾-M _n) is studied; it is typically non-normal and it reveals the role of the initial estimator M _n ⁽⁰⁾.Work of this author was partially supported by the Office of Naval Research, Contract No. N00014-83-K-0387     

Asymptotic Results and a Markovian Approximation for the M(n)/M(n)/s+GI System

In this paper for the M(n)/M(n)/s+GI system, i.e. for a s-server queueing system where the calls in the queue may leave the system due to impatience, we present new asymptotic results for the intensities of calls leaving the system due to impatience and a Markovian system approximation where these results are applied. Furthermore, we present a new proof for the formulae of the conditional density of the virtual waiting time distributions, recently given by Movaghar for the less general M(n)/M/s+GI system. Also we obtain new explicit expressions for refined virtual waiting time characteristics as a byproduct.     

Asymptotic Analysis of the GI/M/ 1 /n Loss System as n Increases to Infinity

This paper provides the asymptotic analysis of the loss probability in the GI/M/1/n queueing system as n increases to infinity. The approach of this paper is alternative to that of the recent papers of Choi and Kim (2000) and Choi et al. (2000) and based on application of modern Tauberian theorems with remainder. This enables us to simplify the proofs of the results on asymptotic behavior of the loss probability of the abovementioned paper of Choi and Kim (2000) as well as to obtain some new results.     

On finitely generated module whose first nonzero fitting ideal is maximal

Let R be a Noetherian ring and M be a finitely generated R-module. Let I(M) be the first nonzero Fitting ideal of M. The main result of this paper asserts that when I(M) = Q is a regular maximal ideal of R, then M?R∕Q⊕P, for some projective R-module P of constant rank if and only if T(M)?QM. As a consequence, it is shown that if M is an Artinian R-module and I(M) = Q is a regular maximal ideal of R, then M?R∕Q.     

Averaging in Markov Models with Fast Markov Switches and Applications to Queueing Models

An approximation of Markov type queueing models with fast Markov switches by Markov models with averaged transition rates is studied. First, an averaging principle for two-component Markov process (x _n (t), _n (t)) is proved in the following form: if a component x _n () has fast switches, then under some asymptotic mixing conditions the component _n () weakly converges in Skorokhod space to a Markov process with transition rates averaged by some stationary measures constructed by x _n (). The convergence of a stationary distribution of (x _n (), _n ()) is studied as well. The approximation of state-dependent queueing systems of the type M _M,Q /M _M,Q /m/N with fast Markov switches is considered.     

A Mehrotra-type predictor-corrector algorithm with polynomiality andQ-subquadratic convergence

Mehrotra's predictor-corrector algorithm [3] is currently considered to be one of the most practically efficient interior-point methods for linear programming. Recently, Zhang and Zhang [18] studied the global convergence properties of the Mehrotra-type predictor-corrector approach and established polynomial complexity bounds for two interior-point algorithms that use the Mehrotra predictor-corrector approach. In this paper, we study the asymptotic convergence rate for the Mehrotra-type predictor-corrector interior-point algorithms. In particular, we construct an infeasible-interior-point algorithm based on the second algorithm proposed in [18] and show that while retaining a complexity bound ofO(n ^1.5 t)-iterations, under certain conditions the algorithm also possesses aQ-subquadratic convergence, i.e., a convergence ofQ-order 2 with an unboundedQ-factor.Research supported in part by NSF DMS-9102761 and DOE DE-FG02-93ER25171.     

On the index of fractions with square-free denominators in arithmetic progressions

We prove asymptotic formulas for the first and second moments of the index of fractions with square-free denominators of order Q streaming in a given arithmetic progression as Q→∞. A. Zaharescu was supported by NSF grant number DMS-0456615. This research was also partially supported by the CERES Program 4-147/2004 of the Romanian Ministry of Education and Research.     

Asymtotics of <Emphasis Type="Italic">M</Emphasis>-estmation in Non-linear Regression

Consider the standard non-linear regression model y _i = g(x _i , θ ₀)+ε _i , i = 1, ... ,n where g(x, θ) is a continuous function on a bounded closed region X × Θ, θ ₀ is the unknown parameter vector in Θ ⊂ R ^p , {x ₁, x ₂, ... , x _n } is a deterministic design of experiment and {ε₁, ε₂, ... , ε _n } is a sequence of independent random variables. This paper establishes the existences of M-estimates and the asymptotic uniform linearity of M-scores in a family of non-linear regression models when the errors are independent and identically distributed. This result is then used to obtain the asymptotic distribution of a class of M-estimators for a large class of non-linear regression models. At the same time, we point out that Theorem 2 of Wang (1995) (J. of Multivariate Analysis, vol. 54, pp. 227–238, Corrigenda. vol. 55, p. 350) is not correct. This research was supported by the Natural Science Foundation of China (Grant No. 19831010 and grant No. 39930160) and the Doctoral Foundation of China