Monotone iterative methods to Markov chains (Q1904045)

The Markov approach for the steady-state analysis of a stochastic process leads to a singular system of the form \[ xQ= x,\tag{1} \] where the stochastic system matrix \(Q\) is assumed to be irreducible and where the unknown steady-state probability vector \(x\) satisfies the normalization equation \(x\cdot 1^T= 1\). Iterative methods for the problem (1) have received lots of attention in recent years. This paper deals with monotone iterative methods, that is, methods which converge towards the solution from below (or from above), for the computation of the steady-state probability vector \(x\). Contrarily to nonmonotone iterative methods, they can be stopped at any time while providing true bounds on the solution. Consider a nonsingular system \[ xB= b\tag{2} \] and a splitting \(B= M- N\) of \(B\) with \(M\) nonsingular. The system (2) can then be rewritten as \(x= xNM^{- 1}+ bM^{- 1}\), which leads to the iterative process \[ x^{(k+ 1)}= x^{(k)} A+ C,\tag{3} \] where \(A= NM^{- 1}\) and \(C= bM^{- 1}\). Different conditions for the iterative process (3) to converge monotonously are given. A practical method for the transformation of the singular system (1) into a nonsingular system of the form (2) is developed. A successful transformation of the singular system (1) is obtained by normalizing exactly one component of the solution, say \(x_n\). This leads to the nonsingular system \[ yB= y(I- Q)^{*e^T_n},\tag{4} \] where \(e_n= (0,\dots,0,1)\) and \(y\) is defined as \(y_k= x_k/x_n\), \(1\leq k\leq n\), (\(Z^{*z^T}\) denotes the matrix \(Z\) whose last column has been replaced by the column vector \(z^T\)). A very important property of the system (4) is the nonnegativity of the inverse \(B^{- 1}\) of the system matrix \(B\). The main result states that for any weak regular splitting \[ M- N= (I- Q)^{* e^T_n}\quad(M^{- 1}\geq 0,\;NM^{- 1}\geq 0) \] the sequence of iterates generated by the corresponding iterative scheme \[ v^{(k+ 1)}= v^{(k)} NM^{- 1}+ e_n M^{- 1},\quad k\geq 0, \] contains a converging nondecreasing (nonincreasing) subsequence \(\{v^{(i+ kr)}\}_{k\geq 0}\). Unfortunately, the basic iterative methods (power, Jacobi and Gauss-Seidel) may converge very slowly. Furthermore, in order to guarantee the monotonicity of the sequence of iterates, they are required to start with a predefined starting guess which is far from the solution. In this paper, these techniques are improved by allowing more general starting guesses; typically, starting guesses derived from an approximation of the solution. This leads to the following algorithm: Step 1. Compute an approximation \(\widehat x\) of the solution of the system (1). Step 2. Select a weak regular splitting of the matrix \((I- Q)^{* e^T_n}\). Step 3. Select a positive scalar \(\gamma\), and set \(v^{(0)}= \widehat x(1- \gamma)/\widehat x_n\). The construction of \(v^{(0)}\) aims at satisfying the inequality \(v^{(0)}< e_n B^{- 1}\). The selection of \(\gamma\) must be related to the accuracy of the approximation \(\widehat x\) and to the tightness of the bounds which are required. The monotone iterative approach becomes then a verification technique aiming at proving that a selected starting guess is a true bound on the solution or aiming at deriving a true bound from this starting guess. This algorithm is used to bound the availability of a repairable fault-tolerant system.