Abstract
This monograph focuses on random walks in the quarterplane. 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 productform and performance measures can readily be obtained. In general, however, no tractable closedform expressions are available for the invariant measure and exact performance measures are not readily obtained. The aim of this monograph is twofold. On one hand we consider measures that are a sum of geometric terms. We characterize the random walks in the quarterplane of which the invariant measure is of this form. This extends the class of random walks for which tractable closedform 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 closedform 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 pairwisecoupled 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 productform. Finally, we have also extended this approximation scheme to twodimensional finite random walks.
Original language  Undefined 

Awarding Institution 

Supervisors/Advisors 

Thesis sponsors  
Award date  22 May 2015 
Place of Publication  Enschede 
Publisher  
Print ISBNs  9789036538503 
DOIs  
Publication status  Published  22 May 2015 
Keywords
 EWI26051
 METIS310479
 IR95853
Cite this
Chen, Y. (2015). Random walks in the quarterplane: invariant measures and performance bounds. Enschede: University of Twente. https://doi.org/10.3990/1.9789036538503