Probabilities for Queueing Systems with Embedded Markov Chains

Abstract

Transition probabilities of embedded Markov chain for single-server queues are considered when the distribution of the inter-arrival time or that of the service time is specified. A comprehensive collection of formulas is derived for the transition probabilities, covering some seventeen flexible families. The corresponding estimation procedures are also derived by the method of moments. It is expected that this work could serve as a useful reference for the modeling of queuing systems with embedded Markov chains.     

Block Two-stage Methods for Singular Systems and Markov Chains

The use of block two-stage methods for the iterative solution of consistent singular linear systems is studied. In these methods, suitable for parallel computations, different blocks, i.e., smaller linear systems, can be solved concurrently by different processors. Each of these smaller systems are solved by an (inner) iterative method. Hypotheses are provided for the convergence of non-stationary methods, i.e., when the number of inner iterations may vary from block to block and from one outer iteration to another. It is shown that the iteration matrix corresponding to one step of the block method is convergent, i.e., that its powers converge to a limit matrix. A theorem on the convergence of the infinite product of matrices with the same eigenspace corresponding to the eigenvalue 1 is proved, and later used as a tool in the convergence analysis of the block method. The methods studied can be used to solve any consistent singular system, including discretizations of certain differential equations. They can also be used to find stationary probability distribution of Markov chains. This last application is considered in detail.     

Markov Chains with Positive Transitions Are Not Determined by Any p-Marginals

 We prove that if is a finite valued stationary Markov Chain with strictly positive probability transitions, then for any natural number p, there exists a continuum of finite valued non Markovian processes which have the p-marginal distributions of X and with positive entropy, whereas for an irrational rotation and essentially bounded real measurable function f with no zero Fourier coefficient on the unit circle with normalized Lebesgue measure, the process is uniquely determined by its three-dimensional distributions in the class of ergodic processes. We give also a family of Gaussian non-Markovian dynamical systems for which the symbolic dynamic associated to the time zero partition has the two-dimensional distributions of a reversible mixing Markov Chain. (Received 22 July 1999; in revised form 24 February 2000)     

A Product Theorem for Markov Chains with Application to PF-Queueing Networks

Queueing networks in random environments represent more realistic models of computer and telecommunication systems than classical product form networks. This is due to the fact that network behaviour often depends on human activities which may vary according to daytime dependent behavioural patterns as well as physiological and mental indexes. In this paper we establish a product connection theorem for Markov chains which contains some corresponding results for spatial processes as well as for queueing networks in random environment as special cases. We demonstrate how our results can be applied to construct an adequate model for wireless networks with hook up capacity.     

Aggregation/Disaggregation Iterative Methods Applied to Leontev Systems and Markov Chains

The paper surveys some recent results on iterative aggregation/disaggregation methods (IAD) for computing stationary probability vectors of stochastic matrices and solutions of Leontev linear systems. A particular attention is paid to fast IAD methods.     

随机环境中的马氏链状态分类

给出了随机环境中马氏链的特征数和状态的定义,讨论了状态间的传递性,自反性,对称性,是经典马氏链相应结果的一般化.并运用位势方法研究了状态间的关系,它们在极限理论的研究中非常有用.     

Contraction Integrated Semigroups and Their Application to Continuous-time Markov Chains

We introduce the notion of the contraction integrated semigroups and give the Lumer-Phillips characterization of the generator, and also the charaterazied generators of isometric integrated semigroups. For their application, a necessary and sufficient condition for q-matrices Q generating a contraction integrated semigroup is given, and a necessary and sufficient condition for a transition function to be a Feller-Reuter-Riley transition function is also given in terms of its q-matrix.     

Expectations for Nonreversible Markov Chains

Bounds are given for an irreducible Markov chain on the probability that the time average of a functional on the state space exceeds its stationary expectation, without assuming reversibility. The bounds are in terms of the singular values of the discrete generator.     

Measure-Valued Differentiation for Markov Chains

This paper addresses the problem of sensitivity analysis for finite-horizon performance measures of general Markov chains. We derive closed-form expressions and associated unbiased gradient estimators for the derivatives of finite products of Markov kernels by measure-valued differentiation (MVD). In the MVD setting, the derivatives of Markov kernels, called -derivatives, are defined with respect to a class of performance functions such that, for any performance measure , the derivative of the integral of g with respect to the one-step transition probability of the Markov chain exists. The MVD approach (i) yields results that can be applied to performance functions out of a predefined class, (ii) allows for a product rule of differentiation, that is, analyzing the derivative of the transition kernel immediately yields finite-horizon results, (iii) provides an operator language approach to the differentiation of Markov chains and (iv) clearly identifies the trade-off between the generality of the performance classes that can be analyzed and the generality of the classes of measures (Markov kernels). The -derivative of a measure can be interpreted in terms of various (unbiased) gradient estimators and the product rule for -differentiation yields a product-rule for various gradient estimators. Part of this work was done while the first author was with EURANDOM, Eindhoven, Netherlands, where he was supported by Deutsche Forschungsgemeinschaft under Grant He3139/1-1. The work of the second author was partially supported by NSERC and FCAR grants of the Government of Canada and Québec.     

Set-Valued Markov Chains and Negative Semitrajectories of Discretized Dynamical Systems

Summary. Computer simulation of dynamical systems involves a phase space which is the finite set of machine arithmetic. Rounding state values of the continuous system to this grid yields a spatially discrete dynamical system, often with different dynamical behaviour. Discretization of an invertible smooth system gives a system with set-valued negative semitrajectories. As the grid is refined, asymptotic behaviour of the semitrajectories follows probabilistic laws which correspond to a set-valued Markov chain, whose transition probabilities can be explicitly calculated. The results are illustrated for two-dimensional dynamical systems obtained by discretization of fractional linear transformations of the unit disc in the complex plane. Received January 9, 2001; accepted January 2, 2002 Online publication April 8, 2002 Communicated by E. Doedel Communicated by E. Doedel rid="     

Markov Chains with Positive Transitions Are Not Determined by Any p -Marginals

 We prove that if is a finite valued stationary Markov Chain with strictly positive probability transitions, then for any natural number p, there exists a continuum of finite valued non Markovian processes which have the p-marginal distributions of X and with positive entropy, whereas for an irrational rotation and essentially bounded real measurable function f with no zero Fourier coefficient on the unit circle with normalized Lebesgue measure, the process is uniquely determined by its three-dimensional distributions in the class of ergodic processes. We give also a family of Gaussian non-Markovian dynamical systems for which the symbolic dynamic associated to the time zero partition has the two-dimensional distributions of a reversible mixing Markov Chain.     

Markov链在教育测量中的应用

将“问题解决”的分析、建模、求解和检验四个阶段作为随机过程的状态得到一Markov链.利用有关随机过程的知识对Markov链进行分类和求解.由此,对学生解决问题的能力进行测量,得到了一些合理结果.     

Markov Integrated Semigroups and their Applications to Continuous-Time Markov Chains

A Markov integrated semigroup G(t) is by definition a weaklystar differentiable and increasing contraction integrated semigroup on l _∞. We obtain a generation theorem for such semigroups and find that they are not integrated C ₀-semigroups unless the generators are bounded. To link up with the continuous-time Markov chains (CTMCs), we show that there exists a one-to-one relationship between Markov integrated semigroups and transition functions. This gives a clear probability explanation of G(t): it is just the mean transition time, and allows us to define and to investigate its q-matrix. For a given q-matrix Q, we give a criterion for the minimal Q-function to be a Feller-Reuter-Riley (FRR) transition function, this criterion gives an answer to a long-time question raised by Reuter and Riley (1972). This research was supported by the China Postdoctoral Science Foundation (No.2005038326).     

一个关于马尔可夫链的极限定理

给出一个关于可列非齐次马尔可夫链M元状态序组出现频率的新形式的强极限定理,所得结论对任意可列非齐次马尔可夫链普遍成立.     

非齐次马尔可夫链的Gesaro—极限定理

本提出了新的非齐次马尔可夫链的遍历条件,并在此条件下,首次证明了非齐次马尔可夫链转移概率的Ｇｅｓａｒｏ－极限定理。另外,本还给出了一个例子,用它表明本的条件确实比Ｄｏｅｂｌｉｎ条件要弱。     

Limit Theorems for General Markov Chains

Siberian Mathematical Journal -     

Self-Interacting Markov Chains: Some Asymptotics

Abstract

Guided by the self-interaction mechanisms introduced in Benaim et al. [2 Benaim , M. , Ledoux , M. , and Raimond , O. 2002 . Self-interacting diffusions . Probab. Theory Related Fields 122 : 1 – 41 . [Google Scholar]] and in [5 Del Moral , P. , and Miclo , L. 2006 . Self-interacting Markov chains . Stochastic Anal. Appl. 24 : 615 – 660 .[Taylor & Francis Online], [Web of Science ®] , [Google Scholar]], we present a more general definition of self-interacting Markov chains (SIMCs) (than in Del Moral and Miclo [5 Del Moral , P. , and Miclo , L. 2006 . Self-interacting Markov chains . Stochastic Anal. Appl. 24 : 615 – 660 .[Taylor & Francis Online], [Web of Science ®] , [Google Scholar]] and Benaim et al. [2 Benaim , M. , Ledoux , M. , and Raimond , O. 2002 . Self-interacting diffusions . Probab. Theory Related Fields 122 : 1 – 41 . [Google Scholar]]). We then establish, for particular self-interaction mechanisms, a stability theorem with error estimation, two central limit theorems, two functional central limit theorems, and the large deviation principle.     

On Transience Conditions for Markov Chains

Siberian Mathematical Journal -     

Translated Poisson Approximation for Markov Chains

The paper is concerned with approximating the distribution of a sum W of integer valued random variables Y _i , 1 ≤ i ≤ n, whose distributions depend on the state of an underlying Markov chain X. The approximation is in terms of a translated Poisson distribution, with mean and variance chosen to be close to those of W, and the error is measured with respect to the total variation norm. Error bounds comparable to those found for normal approximation with respect to the weaker Kolmogorov distance are established, provided that the distribution of the sum of the Y _i ’s between the successive visits of X to a reference state is aperiodic. Without this assumption, approximation in total variation cannot be expected to be good.