Abstract
We consider methods to establish upper and lower bounds on stationary performance measures of a random walk in the positive orthant. We develop an approximation framework that is based on the Markov reward approach to error bounds, in which we use the stationary performance measure of a perturbed random walk to obtain the upper and lower bounds. The perturbed random walk is constructed such that its stationary performance measure is known explicitly.
This thesis has two parts. In the first part we consider the numerical implementation of the approximation framework. Given an original random walk and a perturbed random walk whose stationary probability distribution is known explicitly, we formulate linear programs that return the upper and lower bounds. Implementations of these linear programs are provided that can be used to obtain numerical bounds for a large class of multidimensional random walks. These linear programs are not always feasible. We establish sufficient conditions under which the linear programs are feasible, i.e.\ under which a bound is provided.
In the second part of this thesis we introduce various classes of random walks that can be used as the perturbed random walk for twodimensional models. First, we obtain a perturbed random walk with statedependent transition rates on the horizontal and the vertical axis. Secondly, we construct a perturbed random walk of which only the transition rates in the tail are different from those of the original random walk. In both cases, we give explicit expressions for the error bounds. Through numerical results, we see that these perturbation schemes can provide tighter upper and lower bounds than existing schemes.
These perturbation schemes are considered as an intermediate step towards developing perturbation frameworks for higherdimensional models. The longterm goal is to provide insights into behavior of, for instance, large queueing networks, which can be modeled as random walks.
This thesis has two parts. In the first part we consider the numerical implementation of the approximation framework. Given an original random walk and a perturbed random walk whose stationary probability distribution is known explicitly, we formulate linear programs that return the upper and lower bounds. Implementations of these linear programs are provided that can be used to obtain numerical bounds for a large class of multidimensional random walks. These linear programs are not always feasible. We establish sufficient conditions under which the linear programs are feasible, i.e.\ under which a bound is provided.
In the second part of this thesis we introduce various classes of random walks that can be used as the perturbed random walk for twodimensional models. First, we obtain a perturbed random walk with statedependent transition rates on the horizontal and the vertical axis. Secondly, we construct a perturbed random walk of which only the transition rates in the tail are different from those of the original random walk. In both cases, we give explicit expressions for the error bounds. Through numerical results, we see that these perturbation schemes can provide tighter upper and lower bounds than existing schemes.
These perturbation schemes are considered as an intermediate step towards developing perturbation frameworks for higherdimensional models. The longterm goal is to provide insights into behavior of, for instance, large queueing networks, which can be modeled as random walks.
Original language  English 

Awarding Institution 

Supervisors/Advisors 

Award date  20 Sep 2018 
Place of Publication  Enschede 
Publisher  
Print ISBNs  9789493014435 
DOIs  
Publication status  Published  20 Sep 2018 