Non-skip-free M/G/1-type Markov chains and Laurent matrix power series (Q1434422)

The problem of computing the steady state vector \(\pi P= \pi\), where \(P\) is a semi-infinite block matrix, is reduced to inverting a Laurent matrix power series \(A(z)\), which is singular for \(z= 1\), while this second problem is closely related to solving matrix equations and to computing the (block) weak Wiener-Hopf factorization of \(A(z)\), if it exists. The main purpose of this paper is to point out and investigate the computational problems on which is relying the utilization of non-skip-free (positive recurrent)Markov chains of the M/G/1-type, whose usefulness in queuing modelling is well-known. The authors prove for the beginning the equivalence of three related computational problems, i. e. computing Wiener Hopf factorizations, inverting Laurent matrix power series \(A(z)\), and solving power series matrix equations, and then they describe several algorithms devoted to solve these problems. The main computational difficulty is the singularity of the matrix \(A(z)\) for \(z= 1\), for which the authors define a new Laurent matrix power series \(A(z)\), which is singular in \(z= 0\), but analytic, invertible on a suitable domain, and whose solutions are more easily to be computed. Briefly, Section 2 demonstrates the relationship between the problems of solving matrix equations, computing the formal inverse, and the Wiener-Hopf factorization of the Laurent matrix power series \(A(z)\). Section 3 presents how to remove the singularity of the matrix \(A(z)\) at \(z= 1\) by replacing \(A(z)\) with a new matrix function \(\widehat A(z)\) that is singular at \(z= 0\) and in the same points of singularity of \(A(z)\) except for \(z =1\). Section 4 shows a generalized Ramaswami formula for the computation of the steady state vector \(\pi\), describes new algorithms for implementing the new approach, and addresses open problems. Section 5 contains numerical results and illustrates the effectiveness of the proposed method. Summarizing, the combination of the generalized Ramaswami formula with the shifting technique for singularity point of \(A(z)\), and with computational schemes for calculating Wiener-Hopf factorizations or solving matrix equations provide efficient tools for dealing with non-skip-free Markov chains.