• error bounds
• geometric terms
• Markov chains
• performance measure
• quarter-plane
• random walk

In this thesis we study steady-state performance measures for random walks in the quarter-plane.
Random walks in the quarter-plane are frequently used to model queueing problems.
At present, several techniques are available to find performance measures for random walks in the quarter-plane.
Performance measures can be readily computed once the invariant measure of a random walk is known.

Various approaches to finding the invariant measure of a random walk in the quarter-plane exist.
Most notably, methods from complex analysis have been used to obtain the generating function of the invariant measure.
The studies of Fayolle et al., Cohen and Boxma show that generating functions of random walks in the quarter-plane can be reduced to the solutions of Riemann boundary value problems.
Another approach is to develop the arithmetic of a special class of quasi-Toeplitz matrix, to solve certain semi-infinite quadratic matrix equations by means of cyclic reduction efficiently.
However, neither of these approaches leads to a closed-form invariant measure.

In this thesis we focus on obtaining performance measures of the following two types: exact results and approximations.
Chen, Boucherie and Goseling characterized the random walks of which the invariant measure is a linear combination of geometric measures, with some restrictive hypotheses on the boundary transition probabilities.
The performance measures of the random walk of which the invariant measure is a sum of geometric terms can be readily computed.
For other random walks, a general approximation scheme is developed, in terms of a random walk with a sum of geometric terms invariant measure, which is obtained by perturbing the transition probabilities along the boundaries of the state space.
A Markov reward approach is used to bound the approximation errors.

We further enlarge the class of random walks of which the performance measures can be obtained exactly, by removing the additional hypotheses that Chen put on the transition probabilities, and extending the classification to this more general case.
The algorithms to compute the invariant measure, and to approximate performance measures of generic random walks, are also generalized.
Necessary and sufficient conditions are given to satisfy some a priori assumptions, that were taken for granted but not addressed in previous works. Finally, some numerical results are exhibited.