Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Steady-State Solutions of Markov Chains In this chapter, we restrict ourselves to the computation of the steady-state probability vector’ of ergo&c Markov chains. Most of the literature on solution techniques of Markov chains assumes ergodicity of the underlying model. A comprehensive source on algorithms for steady-state solution techniques is the book by Stewart [Stew94]. From Eq. (2.15) and Eq. (2.58), we have v = VP and 0 = nQ, respectively, as points of departure for the study of steady-state solution techniques. Eq. (2.15) can be transformed so that: 0 = Y(P -1). Therefore, both for CTMC and DTMC, a linear system. | Queueing Networks and Markov Chains Gunter Botch Stefan Greiner Hermann de Meer Kishor S. Trivedi Copyright 1998 John Wiley Sons Inc. Print ISBN 0-471-19366-6 Online ISBN 0-471-20058-1 fi K n 1 VsbN Steady-State Solutions of Markov Chains In this chapter we restrict ourselves to the computation of the steady-state probability vector1 of ergodic Markov chains. Most of the literature on solution techniques of Markov chains assumes ergodicity of the underlying model. A comprehensive source on algorithms for steady-state solution techniques is the book by Stewart Stew94 . From Eq. 2.15 and Eq. 2.58 we have v vP and 0 ttQ respectively as points of departure for the study of steady-state solution techniques. Eq. 2.15 can be transformed so that 0 i P-I . 3.1 Therefore both for CTMC and DTMC a linear system of the form 0 xA 3-2 needs to be solved. Due to its type of entries representing the parameters of a Markov chain matrix A is singular and it can be shown that A is of rank n - 1 for any Markov chain of size S n. It follows immediately that the resulting set of equations is not linearly independent and that one of the equations is redundant. To yield a unique positive solution we must impose a normalization condition on the solution x of equation 0 xA. One way to approach the solution of Eq. 3.2 is to directly incorporate the normalization condition xl 1 3.3 xFor the sake of convenience we sometimes use the term steady-state analysis as a shorthand notation. 103 104 STEADY-STATE SOLUTIONS OF MARKOV CHAINS into the Eq. 3.2 . This can be regarded as substituting one of the columns say the last column of matrix A by the unit vector 1 1 1 . 1 T. With a slight abuse of notation we denote the new matrix also by A. The resulting linear system of non-homogeneous equations is b xA b 0 0 . 0 1 . 3.4 An alternative to solving Eq. 3.2 is to separately consider normalization Eq. 3.3 as an additional step in numerical computations. We demonstrate both ways when example studies are .