Stationary Distributions of GI/M/c Queue with PH Type Vacations

We study a GI/M/c type queueing system with vacations in which all servers take vacations together when the system becomes empty. These servers keep taking synchronous vacations until they find waiting customers in the system at a vacation completion instant.The vacation time is a phase-type (PH) distributed random variable. Using embedded Markov chain modeling and the matrix geometric solution methods, we obtain explicit expressions for the stationary probability distributions of the queue length at arrivals and the waiting time. To compare the vacation model with the classical GI/M/c queue without vacations, we prove conditional stochastic decomposition properties for the queue length and the waiting time when all servers are busy. Our model is a generalization of several previous studies.     

基于矩阵分析方法的具有双阶段休假的排队系统驱动的流模型性能分析

基于矩阵分析方法研究了具有单重工作休假和多重休假策略M/M/1排队系统驱动的流模型.首先建立了控制该流模型的微分方程组,利用矩阵分析方法,得出了系统平稳库存量的laplace变换(LT)的矩阵阶乘表达式.进而利用LaplaceStieltjes变换(LST)得出了平稳库存量的期望.最后,通过数值例子展示了系统性能指标与参数的关系.     

Stability of non-Markovian polling systems

A stationary regime for polling systems with general ergodic (G/G) arrival processes at each station is constructed. Mutual independence of the arrival processes is not required. It is shown that the stationary workload so constructed is minimal in the stochastic ordering sense. In the model considered the server switches from station to station in a Markovian fashion, and a specific service policy is applied to each queue. Our hypotheses cover the purely gated, thea-limited, the binomial-gated and other policies. As a by-product we obtain sufficient conditions for the stationary regime of aG/G/1/ queue with multiple server vacations (see Doshi [11]) to be ergodic.Work presented at the INRIA/ORSA Conference on Applied Probability in Engineering, Computer and Communication Sciences, Paris, June 16–18, 1993.     

Random walks on random coset spaces with applications to Furstenberg entropy

We determine the range of Furstenberg entropy for stationary ergodic actions of nonabelian free groups by an explicit construction involving random walks on random coset spaces.     

The Discrete-Time GI/Geo/1 Queue with Multiple Vacations

We study a discrete-time GI/Geo/1 queue with server vacations. In this queueing system, the server takes vacations when the system does not have any waiting customers at a service completion instant or a vacation completion instant. This type of discrete-time queueing model has potential applications in computer or telecommunication network systems. Using matrix-geometric method, we obtain the explicit expressions for the stationary distributions of queue length and waiting time and demonstrate the conditional stochastic decomposition property of the queue length and waiting time in this system.     

Ergodic BSDEs and related PDEs with Neumann boundary conditions

We study a new class of ergodic backward stochastic differential equations (EBSDEs for short) which is linked with semi-linear Neumann type boundary value problems related to ergodic phenomena. The particularity of these problems is that the ergodic constant appears in Neumann boundary conditions. We study the existence and uniqueness of solutions to EBSDEs and the link with partial differential equations. Then we apply these results to optimal ergodic control problems.     

TheM/GI/1 Bernoulli feedback queue with vacations

Feedback may be introduced as a mechanism for scheduling customer service (for example in systems in which customers bring work that is divided into a random number of stages). A model is developed that characterizes the queue length distribution as seen following vacations and service stage completions. We demonstrate the relationship that exists between these distributions. The ergodic waiting time distribution is formulated in such a way as to reveal the effects of server vacations when feedback is introduced.This work was supported in part by NSF Grant No. DDM-8913658.     

Perturbed Markov Chains with Damping Component

The paper is devoted to studies of regularly and singularly perturbed Markov chains with damping component. In such models, a matrix of transition probabilities is regularised by adding a special damping matrix multiplied by a small damping (perturbation) parameter ε. We perform a detailed perturbation analysis for such Markov chains, particularly, give effective upper bounds for the rate of approximation for stationary distributions of unperturbed Markov chains by stationary distributions of perturbed Markov chains with regularised matrices of transition probabilities, asymptotic expansions for approximating stationary distributions with respect to damping parameter, explicit coupling type upper bounds for the rate of convergence in ergodic theorems for n-step transition probabilities, as well as ergodic theorems in triangular array mode.

     

Central Limit Theorem Started at a Point for?Stationary Processes and Additive Functionals of?Reversible Markov Chains

In this paper we study the almost sure central limit theorem started at a point for additive functionals of a stationary and ergodic Markov chain via a martingale approximation in the almost sure sense. Some of the results provide sufficient conditions for general stationary sequences. We use these results to study the quenched CLT for additive functionals of reversible Markov chains.     

Analysis of an SPP/G/1 system with multiple vacations and E-limited service discipline

Many researchers have studied variants of queueing systems with vacations. Most of them have dealt with M/G/1 systems and have explicitly analyzed some of their performance measures, such as queue length, waiting time, and so on. Recently, studies on queueing systems whose arrival processes are not Poissonian have appeared. We consider a single server queueing system with multiple vacations and E-limited service discipline, where messages arrive to the system according to a switched Poisson process. First, we consider the joint probability density functions of the queue length and the elapsed service time or the elapsed vacation time. We derive the equations for these pdf's, which include a finite number of unknown values. Using Rouché's theorem, we determine the values from boundary conditions. Finally, we derive the transform of the stationary queue length distribution explicitly.     

遍历性及其应用──(Ⅰ)基本性质(英)

在一般意义下，给出了函数的遍历性定义．指出遍历函数是比概周期函数、渐近概周期函数及弱概周期函数更广的一类函数．文章讨论了遍历函数的一些性质，其中一个主要结果是给出了一个不等式的明确表达式．     

Stationary distributions of semistochastic processes with disturbances at random times and with random severity

We consider a semistochastic continuous-time continuous-state space random process that undergoes downward disturbances with random severity occurring at random times. Between two consecutive disturbances, the evolution is deterministic, given by an autonomous ordinary differential equation. The times of occurrence of the disturbances are distributed according to a general renewal process. At each disturbance, the process gets multiplied by a continuous random variable (“severity”) supported on [0,1). The inter-disturbance time intervals and the severities are assumed to be independent random variables that also do not depend on the history.We derive an explicit expression for the conditional density connecting two consecutive post-disturbance levels, and an integral equation for the stationary distribution of the post-disturbance levels. We obtain an explicit expression for the stationary distribution of the random process. Several concrete examples are considered to illustrate the methods for solving the integral equations that occur.     

A discussion about the homogenization of moving interfaces

There has been considerable interest lately in the homogenization theory for first- and second-order partial differential equations in periodic/almost periodic and random, stationary, ergodic environments. Of special interest is the study of the averaged behavior of moving interfaces. In this note we revisit the last issue. We present several new results concerning interfaces moving by either oscillatory first-order or curvature dependent coupled with oscillatory forcing normal velocity in periodic environments and analyze in detail their behavior. Under sharp assumptions we show that such fronts may homogenize, get trapped or oscillate.     

Dam processes with state dependent batch sizes and intermittent production processes with state dependent rates

We consider a dam process with a general (state dependent) release rule and a pure jump input process, where the jump sizes are state dependent. We give sufficient conditions under which the process has a stationary version in the case where the jump times and sizes are governed by a marked point process which is point (Palm) stationary and ergodic. We give special attention to the Markov and Markov regenerative cases for which the main stability condition is weakened. We then study an intermittent production process with state dependent rates. We provide sufficient conditions for stability for this process and show that if these conditions are satisfied, then an interesting new relationship exists between the stationary distribution of this process and a dam process of the type we explore here.Supported in part by The Israel Science Foundation, grant no. 372/93-1.     

Law of Large Numbers for Random Walk with Unbounded Jumps and Birth and Death Process with Bounded Jumps in Random Environment

We study a random walk with unbounded jumps in random environment. The environment is stationary and ergodic, uniformly elliptic and decays polynomially with speed \(Dj^{-(3+\varepsilon _0)}\) for some \(D>0\) and small \(\varepsilon _0>0.\) We prove a law of large numbers under the condition that the annealed mean of the hitting time of the lattice of the positive half line is finite. As the second part, we consider a birth and death process with bounded jumps in stationary and ergodic environment whose skeleton process is a random walk with unbounded jumps in random environment. Under a uniform ellipticity condition, we prove a law of large numbers and give the explicit formula of its velocity.     

Exact and approximate correctors for stochastic Hamiltonians: the 1-dimensional case

We perform a qualitative investigation of critical Hamilton–Jacobi equations, with stationary ergodic Hamiltonian, in dimension 1. We show the existence of approximate correctors, give characterizing conditions for the existence of correctors, provide Lax-type representation formulae and establish comparison principles. The results are applied to look into the corresponding effective Hamiltonian and to study a homogenization problem. In the analysis a crucial role is played by tools from stochastic geometry such as, for instance, closed random stationary sets.     

Complexity of nilsystems and systems lacking nilfactors

Nilsystems are a natural generalization of rotations and arise in various contexts, including in the study of multiple ergodic averages in ergodic theory, in the structural analysis of topological dynamical systems, and in asymptotics for patterns in certain subsets of the integers. We show, however, that many natural classes in both measure preserving systems and topological dynamical systems contain no higher order nilsystems as factors, meaning that the only nilsystems they contain as factors are rotations. Our main result is that in the topological setting, nilsystems have a particular type of complexity of polynomial growth, where the polynomial (with explicit degree) is an asymptotic both from below and above. We also deduce several ergodic and topological applications of these results.     

A simple approach for analyzing feedback vacation queues with levy input process

We introduce a simple approach for modeling and analyzing a SII/G/I queue where the server may take repeated vacations. Whenever a busy period ends the server takes a vacation of random duration. At the end of each vacation the server may either take a new vacation or resume service; if the queue is found empty the server always takes a new vacation. Furthermore, the queuing system allows Bernoulli feedback of customers. Three classes of service disciplines, random gated, 1-limited and exhaustive, are considered. The random gated service discipline generalizes several known service disciplines. The customers arrival process is assumed to be a Levy process (i.e., satisfies the stationary and independent increments (SII property). We obtain explicit expressions for several performance measures of the system. These performance measures include the mean and second moment of the cycle time, the mean queue length at the beginning of a cycle of service and the expected delay observed by a customer. Furthermore, our analysis provides a uniform method to get several results previously obtained by Baba, Chiarawongse and Sriniwasan, and Takine, Takagi and Hasegawa.     

Discriminants and Functional Equations for Polynomials Orthogonal on the Unit Circle

We derive raising and lowering operators for orthogonal polynomials on the unit circle and find second order differential and q-difference equations for these polynomials. A general functional equation is found which allows one to relate the zeros of the orthogonal polynomials to the stationary values of an explicit quasi-energy and implies recurrences on the orthogonal polynomial coefficients. We also evaluate the discriminants and quantized discriminants of polynomials orthogonal on the unit circle.     

An algorithmic approach to the Markov chain with transition probability matrix of upper block-Hessenberg form

We present an algorithm to find an approximation for the stationary distribution for the general ergodic spatially-inhomogeneous block-partitioned upper Hessenberg form. Our approximation makes use of an associated upper block-Hessenberg matrix which is spatially homogeneous except for a finite number of blocks. We treat theMAP/G/1 retrial queue and the retrial queue with two types of customer as specific instances and give some numerical examples. The numerical results suggest that our method is superior to the ordinary finite-truncation method.