• quasi-Toeplitz matrices
• quasi-birth-and-death processes
• matrix equations
• shifting technique

In this thesis, we study methods for computing the invariant probability measure for certain quasi-birth-and-death Markov chains. In particular, we consider the situation of a double QBD, whose transition matrix has the infinite, block-tridiagonal and almost block-Toeplitz form of a QBD, with blocks which are infinite, tridiagonal and almost Toeplitz. This class includes classic situations like the reflected random walk in the quarter plane and the tandem Jackson queue.

For QBDs, the problem of finding the invariant measure can be reduced to computing the minimal non-negative solution of quadratic matrix equations. A lot of literature exists about it in the case of finite-dimensional blocks. For the infinite-dimensional case, recently has been introduced an approach based quasi-Toeplitz matrices, which relies on solving matrix equations in a suitable Banach algebra. Other techniques exist. For example, the "truncation and augmentation" method by Taylor and Latouche, and the compensation approach by Adan.

The aim of this work is to describe the approach based on quasi-Toeplitz matrices and to improve the existing theory in order to handle problematic cases.

A description of the algebra of quasi-Toeplitz matrices is given, with attention to computational issues like the effects of truncation and arithmetic operations. The relation between a suitable factorization of a Laurent matrix polynomial and the solutions of matrix equations is shown. This allows us to prove the quadratic convergence of a classic algorithm, the cyclic reduction. Conditions for the solutions to be quasi-Toeplitz matrices are given, with attention to problematic cases in which this does not happen. To deal with these cases, we introduce a new matrix algebra which extends the class of Quasi-Toeplitz matrices and contains solutions of problematic cases, and we use a shifting technique to solve equations in the extended class.