Random walks in the quarter-plane: invariant measures and performance bounds

This monograph focuses on random walks in the quarter-plane. Such random walks are frequently used to model queueing systems and the invariant measure of a random walk is of major importance in studying the performance of these systems. In special cases the invariant measure of a random walk can be expressed as a geometric product-form and performance measures can readily be obtained. In general, however, no tractable closed-form expressions are available for the invariant measure and exact performance measures are not readily obtained. The aim of this monograph is two-fold. On one hand we consider measures that are a sum of geometric terms. We characterize the random walks in the quarter-plane of which the invariant measure is of this form. This extends the class of random walks for which tractable closed-form results can be obtained. On the other hand we develop approximation schemes that provide analytical upper and lower bounds on performance for the case that no tractable closed-form expressions for the invariant measure are available. It is shown that the necessary conditions that are required to have an invariant measure which is a sum of geometric terms are as follows: Each geometric term must individually satisfy the balance equations in the interior of the state space and the geometric terms in an invariant measure must have a pairwise-coupled structure. Moreover, at least one of the coecients in the linear combination must be negative. When the invariant measure of the random walk is a sum of innitely many geometric terms, it is also required that the random walk does not have transitions to the North, Northeast or East in the interior of the state space. Based on the necessary conditions described above, we develop an algorithm which determines whether the invariant measure of a given random walk is a sum of geometric terms. For the case that the invariant measure of this random walk is not a sum of geometric terms, we have developed an approximation scheme to find upper and lower bounds for the performance measures. This approximation scheme is based on a Markov reward approach to error bounds. The bounds determined by our approximation scheme are established in terms of a perturbed random walk of which the invariant measure is a sum of geometric terms. Numerical results reveal that using a perturbed random walk of which the invariant measure is a sum of multiple geometric terms may lead to better bounds than using perturbed random walks of which the invariant measure is of product-form. Finally, we have also extended this approximation scheme to two-dimensional finite random walks.