• toeplitz operator
• markov chain
• random walk
• compensation approach
• qbd process

Random walks in the quarter-plane are frequently used to model queueing problems, they belong to the family of Quasi-Birth-Death processes and they are widely studied in literature.
The main purpose of this thesis is to analyze and compare algorithms that allow us to calculate the invariant measure of the random walk when it is modelled as a discrete time Markov chain or as a continuous time Markov process. We do this with two approaches deeply diferent from each other.
The first, based on the works of Bini et al., is an operator approach. The transition operator of this kind of process is semi-infinite, block-tridiagonal, almost block-Toeplitz with semi-infinite almost-Toeplitz blocks; the idea behind this approach is to adapt, to the infinite case, the avaliable algorithms valid for blocks of finite size. To do this we need first to define the right space which these infinite blocks belong to and then to build an arithmetic in it. In particular we focus on the algorithm of Cyclic Reduction and on the matrix geometric approach. We prove that, similarly to the finite case, this algorithm converges to the minimal solution of certain quadratic operator equations from which we can build the invariant probability vector.
The second approach, named compensation approach, is based on the works of Adan. This is a more practical approach that exploits the structure of the equilibrium equations in the interior of the quarter plane by imposing that linear combinations of product forms satisfy these equations. This leads to a kernel equation for the terms appearing in the product forms. Then, it is required that these linear combinations satisfy the equilibrium equations on the boundaries as well. As it turns out, this can be done by alternatingly compensating for the errors on the two boundaries, which eventually leads to infinite series of product forms. Convergence of these series is a crucial issue, some sufficient conditions for the convergence of these series are provided.
After introducing the two approaches and relying on the work of Kapodistria, we provide a comparison of the two approaches on both a theoretical and a computational basis. Some results are stated, in particular we show that eigenvalues and eigenvectors of the operators that we calculate in the first approach can be obtained in the construction of the infinite series of product forms in the compensation approach.
An accurate numerical simulation is carried out relying on test problems taken from the current literature. It turns out that the applicability of the compensation approach is more restricted than the operator approach. On the other hand it shows a better performance in terms of accuracy. In fact the compensation approach provide approximation with very small relative error, whereas the operator approach in the current implementation does not maintain a uniform bound to the relative error, even though the absolute error in the approximation is quite small.
The thesis is organized as follows. In Chapter 1 we describe the problem of the random walk in the quarter plane, we model it as a Markov chain and we recall some of the most important definitions and results about the subject. In Chapter 2 we extend the matrix geometric approach to the infinite case, we introduce the space of Quasi-Toeplitz operators and we describe a machine arithmetic for it. Chapter 3 concerns the Cyclic Reduction algorithm: we recall this algorithm together with its properties valid in the finite case, then we present its extension to the infinite case. In Chapter 4 we describe the compensation approach and we put it in relation with the operator approach. Finally, in Chapter 5 we exhibit the numerical results of our experimentation.