An Algorithmic Approach for Sensitivity Analysis of Perturbed Quasi-Birth-and-Death Processes

In this paper, we present an algorithmic approach for sensitivity analysis of stationary and transient performance measures of a perturbed continuous-time level-dependent quasi-birth-and-death (QBD) process with infinitely-many levels. By developing a new LU-type RG-factorization using the censoring technique, we obtain the maximal negative inverse of the infinitesimal generator of the QBD process. The derivatives of the stationary performance measures of the QBD process can then be expressed and computed in terms of the maximal negative inverse, overcoming the computational difficulty arising from the use of group inverses of infinite size in the current literature (see Cao and Chen [11]). We also use a stochastic integral functional to study the transient performance measure of the QBD process and show how to use the algorithmic approach for its sensitivity analysis. As an example, a perturbed MAP/PH/1 queue is also analyzed.     

Phase-type models for cellular networks supporting voice, video and data traffic

This paper presents an analytical model for cellular networks supporting voice, video and data traffic. Self-similar and bursty nature of the incoming traffic causes correlation in inter-arrival times of the incoming traffic. Therefore, arrival of calls is modeled with Markovian arrival process as it allows for the correlation. Call holding times, cell residence times and retrial times are modeled as phase-type distributions. We consider that the cells in a cellular network are statistically homogeneous, so it is enough to investigate a single cell for the performance analysis of the entire networks. With appropriate assumptions, the stochastic process that describes the state of a cell is a Quasi-birth–death (QBD) process. We derive explicit expressions for the infinitesimal generator matrix of this QBD process. Also, expressions for performance measures are obtained. Further, complexity involved in computing the steady-state probabilities is discussed. Finally, queueing examples are provided that can be obtained as particular cases of the proposed analytical model.     

Comments on “multi-server system with single working vacation”

Lin and Ke consider the M/M/R queue with working vacation [Chuen-Horng Lin, Jau-Chuan Ke, Multi-server system with single working vacation, Appl. Math. Modell. (2008), doi:10.1016/j.apm.2008.10.006], and derive a computable explicit form for rate matrix R$\mathfrak{R}$ of the geometric approach and the stationary probabilities of the queue. However, it contains some errors concerning the terminology, notations and the final form of rate matrix R$\mathfrak{R}$. This note shows that the classical Quasi-birth-death (QBD) formulation of the M/M/R queue with working vacation naturally leads to the infinitesimal generator matrix of the QBD process and the probability interpretation of matrices involving in the infinitesimal generator matrix.     

Applications of Compact Superharmonic Functions: Path Regularity and Tightness of Capacities

We establish relations between the existence of the L{\mathcal{L}}-superharmonic functions that have compact level sets (L{\mathcal{L}} being the generator of a right Markov process), the path regularity of the process, and the tightness of the induced capacities. We present several examples in infinite dimensional situations, like the case when L{\mathcal{L}} is the Gross–Laplace operator on an abstract Wiener space and a class of measure-valued branching process associated with a nonlinear perturbation of L{\mathcal{L}}.     

The existence of invariant measures forC[0,1]-valued diffusions

Summary We prove the existence of an invariant measure for processes arising from a perturbation of theC[0,1]-valued Ornstein-Uhlenbeck process with a drift taking values in the Cameron-Martin space. We study the infinitesimal generator, and a partial integration onC[0,1] will yield conditions on the drift which enable us to use arguments of perturbation theory to prove the existence of an invariant measure which is absolutely continuous with respect to the Wiener measure.     

System availability in a shock model under preventive repair and phase‐type distributions

A device that can fail by shocks or ageing under policy N of maintenance is presented. The interarrival times between shocks follow phase‐type distributions depending on the number of cumulated shocks. The successive shocks deteriorate the system, and some of them can be fatal. After a prefixed number k of nonfatal shocks, the device is preventively repaired. After a fatal shock the device is correctively repaired. Repairs are as good as new, and follow phase‐type distributions. The system is governed by a Markov process whose infinitesimal generator, stationary probability vector, and availability are calculated, obtaining well‐structured expressions due to the use of phase‐type distributions. The availability is optimized in terms of the number k of preventive repairs. Copyright © 2009 John Wiley & Sons, Ltd.     

Flux and Lateral Conditions for Symmetric Markov Processes

The purpose of this paper is to give an affirmative answer at infinitesimal generator level to the 40 years old Feller’s boundary problem for symmetric Markov processes with general quasi-closed boundaries. For this, we introduce a new notion of flux functional, which can be intrinsically defined via the minimal process X ⁰ in the interior. We then use it to characterize the L ²-infinitesimal generator of a symmetric process that extends X ⁰. Special attention is paid to the case when the boundary consists of countable many points possessing no accumulation points. Research of Masatoshi Fukushima was supported by Grand-in-Aid for Scientific Research of MEXT No.19540125.     

Über Die Konvergenz Operatorwertiger Cosinusfunktionen mit Gestörtem Infinitesimalen Erzeuger

On convergence of operator cosine functions with perturbed infinitesimal generator. The question under what kind of perturbations a closed linear operatorA remains of the class of infinitesimal generators of operator cosine functions seems to be a rather difficult one and is unsolved in general. In this note we give bounds for the perturbation of operator cosine functions caused byA-bounded perturbationsT ofA under the assumption thatT + A is also a generator.

     

Some <Emphasis Type="Italic">L</Emphasis><Superscript>2</Superscript> properties of semigroups of measures on Lie groups

We investigate the induced action of convolution semigroups of probability measures on Lie groups on the L ²-space of Haar measure. Necessary and sufficient conditions are given for the infinitesimal generator to be self-adjoint and the associated symmetric Dirichlet form is constructed. We show that the generated Markov semigroup is trace-class if and only if the measures have a square-integrable density. Two examples are studied in some depth where the spectrum can be explicitly computed, these being the n-torus and Riemannian symmetric pairs of compact type.     

Quasi-birth-and-death Markov processes with a tree structure and the MMAP[K]/PH[K]/N/LCFS non-preemptive queue

This paper studies a multi-server queueing system with multiple types of customers and last-come-first-served (LCFS) non-preemptive service discipline. First, a quasi-birth-and-death (QBD) Markov process with a tree structure is defined and some classical results of QBD Markov processes are generalized. Second, the MMAP[K]/PH[K]/N/LCFS non-preemptive queue is introduced. Using results of the QBD Markov process with a tree structure, explicit formulas are derived and an efficient algorithm is developed for computing the stationary distribution of queue strings. Numerical examples are presented to show the impact of the correlation and the pattern of the arrival process on the queueing process of each type of customer.     

A impulsive infective transmission SI model for pest control

In this paper, we propose a model with impulsive control of epidemics for pest management. By using Floquet's theorem, small‐amplitude perturbation skills and comparison theorem, we show that there exists a globally asymptotically stable susceptible pest‐eradication periodic solution when the release amount of infective pests is larger than some critical value. However, when the amount of infective pests released is less than this critical value, the system is shown to be permanent, which implies that the trivial periodic susceptible pest‐eradication solution loses its stability. Further, the existence of a positive periodic endemic solution and other rich dynamics are also studied by numerical simulation. Therefore, we can use the amount of release of infective pests to control susceptible pests at desirable low levels. Copyright © 2007 John Wiley & Sons, Ltd.     

Convergence rates for steady-state derivative estimators

We describe various derivative estimators for the case of steady-state performance measures and obtain the order of their convergence rates. These estimatorsdo not use explicitly the regenerative structure of the system. Estimators based on infinitesimal perturbation analysis, likelihood ratios, and different kinds of finite-differences are examined. The theoretical results are illustrated via numerical examples.     

Erratum to the paper “An Integral Delay Inequality and its Applications to Boundary Value Problems”

We consider the infinitesimal generator of the time reversal of a time-homogeneous one-dimensional gap diffusion with state space [0, 1] given by the infinitesimal generator A^o = dD_s⁺ - dk / dm with nonlocal boundary conditions of Feller-Wentzell-type. This leads to an infinitesimal generator which belongs to a class of generators introduced in the earlier note [W1].     

Optimal damping of perturbations in a system with unknown initial conditions

We consider the perturbation damping problem for a system in which, along with an external perturbation bounded in the L ₂-norm, there is an initial perturbation caused by unknown nonzero initial conditions. We state necessary and sufficient conditions for the existence of an optimal control law minimizing the maximum L ₂-norm of the system output for all L ₂-bounded external perturbations and bounded initial states and synthesize this control law.     

On multiplicative perturbations of C 0 -groups and C 0 -cosine operator functions

Certain convolution operators of the form (K f) (t) = A∈t ₀ ^t L(t-s) f(s) ds , where A is the infinitesimal generator of either a C ₀ -group or a C ₀ -cosine family in a Banach space E , are considered. We obtain several lifting results guaranteeing that the continuity of K from L ^p to L ^q implies the continuity of K from L ^p to L ^∈ fty . These results are applied to the study of multiplicative perturbations of C ₀ -groups and C ₀ -cosine families in Banach spaces and to the study of the Maximal Regularly Property (MRP) in L ^p , 1 ≤ p ≤ +∈fty , for second-order Cauchy problem. It is proved that the MRP is equivalent to the boundedness of the infinitesimal generator. April 30, 1999     

Truncation and augmentation of level-independent QBD processes

In the study of quasi-birth-and-death (QBD) processes, the first passage probabilities from states in level one to the boundary level zero are of fundamental importance. These probabilities are organized into a matrix, usually denoted by G.The matrix G is the minimal nonnegative solution of a matrix quadratic equation. If the QBD process is recurrent, then G is stochastic. Otherwise, G is sub-stochastic and the matrix equation has a second solution G_sto, which is stochastic. In this paper, we give a physical interpretation of G_sto in terms of sequences of truncated and augmented QBD processes.As part of the proof of our main result, we derive expressions for the first passage probabilities that a QBD process will hit level k before level zero and vice versa, which are of interest in their own right.The paper concludes with a discussion of the stability of a recursion naturally associated with the matrix equation which defines G and G_sto. In particular, we show that G is a stable equilibrium point of the recursion while G_sto is an unstable equilibrium point if it is different from G.     

Matrix analytic methods for a multi-server retrial queue with buffer

We present numerical methods for obtaining the stationary distribution of states for multi-server retrial queues with Markovian arrival process, phase type service time distribution with two states and finite buffer; and moments of the waiting time. The methods are direct extensions of the ones for the single server retrial queues earlier developed by the authors. The queue is modelled as a level dependent Markov process and the generator for the process is approximated with one which is spacially homogeneous above some levelN. The levelN is chosen such that the probability associated with the homogeneous part of the approximated system is bounded by a small tolerance and the generator is eventually truncated above that level. Solutions are obtained by efficient application of block Gaussian elimination.     

Strongly continuous semigroups of operators generated by systems of pseudodifferential operators in weighted <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript>-spaces

This paper considers semigroups of operators generated by pseudodifferential operators in weighted L _p -spaces of vector functions on \mathbbRⁿ {\mathbb{R}^n} (or on a compact manifold without boundary). Sufficient conditions for a semigroup to be strongly continuous and analytic are obtained, conditions for it to be completely continuous are found, and the distribution of the eigenvalues of its infinitesimal generator is examined. Also, an integral representation that singles out the principal term of the semigroup as t → 0+ is established.     

线性算子双半群的扰动定理

本文研究有界线性算子强连续双半群的扰动问题。文中首先研究与强连续双半群母元有关的算子方程的可解性与算子的相似性。在此基础上证明了在一定条件下可化为指数衰减的强连续双半群经适当扰动后仍是一个可化为指数衰减的强连续双半群。     

A Class of Infinitesimal Generators and Time Reversal for the Corresponding One-Dimensional Markov Processes

A class of infinitesimal generators A of strongly continuous nonnegative contraction semigroups in a subspace of C[0, 1] is introduced. It contains the class of generators of regular gap diffusions. A construction of the Markov process X generated by A gives some stochastic interpretations of the integral term which appears in A. The infinitesimal generator of the time reversal of X (with respect to its life time) is explicitly given. It belongs to the introduced class of generators too. Thus, the considered class is invariant under this transformation. Two examples, the time reversal of gap diffusions with nonlocal boundary conditions and the time reversal of processes with Levy-measure, complete the note.