Abstract
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 
Fingerprint
Cite this
}
Performance bounds for random walks in the positive orthant. / Bai, Xinwei .
Enschede : University of Twente, 2018. 145 p.Research output: Thesis › PhD Thesis  Research UT, graduation UT
TY  THES
T1  Performance bounds for random walks in the positive orthant
AU  Bai, Xinwei
PY  2018/9/20
Y1  2018/9/20
N2  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.
AB  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.
U2  10.3990/1.9789493014435
DO  10.3990/1.9789493014435
M3  PhD Thesis  Research UT, graduation UT
SN  9789493014435
T3  DSI Ph.D. thesis series
PB  University of Twente
CY  Enschede
ER 