Performance bounds for random walks in the positive orthant

Xinwei Bai

Research output: ThesisPhD Thesis - Research UT, graduation UT

59 Downloads (Pure)

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 multi-dimensional 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 two-dimensional models. First, we obtain a perturbed random walk with state-dependent 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 higher-dimensional models. The long-term goal is to provide insights into behavior of, for instance, large queueing networks, which can be modeled as random walks.
Original languageEnglish
Awarding Institution
  • University of Twente
Supervisors/Advisors
  • Boucherie, Richardus J., Supervisor
  • Goseling, Jasper , Supervisor
Award date20 Sep 2018
Place of PublicationEnschede
Publisher
Print ISBNs978-94-9301-443-5
DOIs
Publication statusPublished - 20 Sep 2018

Fingerprint

Performance Bounds
Random walk
Linear Program
Stationary Measure
Upper and Lower Bounds
Performance Measures
Perturbation
Error Bounds
Queueing Networks
Approximation
Stationary Distribution
Reward
Tail
High-dimensional
Probability Distribution
Horizontal
Vertical

Cite this

Bai, Xinwei . / Performance bounds for random walks in the positive orthant. Enschede : University of Twente, 2018. 145 p.
@phdthesis{5b7f2f1d23344c9484de7ed5f938ee31,
title = "Performance bounds for random walks in the positive orthant",
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 multi-dimensional 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 two-dimensional models. First, we obtain a perturbed random walk with state-dependent 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 higher-dimensional models. The long-term goal is to provide insights into behavior of, for instance, large queueing networks, which can be modeled as random walks.",
author = "Xinwei Bai",
year = "2018",
month = "9",
day = "20",
doi = "10.3990/1.9789493014435",
language = "English",
isbn = "978-94-9301-443-5",
series = "DSI Ph.D. thesis series",
publisher = "University of Twente",
number = "18-010",
address = "Netherlands",
school = "University of Twente",

}

Performance bounds for random walks in the positive orthant. / Bai, Xinwei .

Enschede : University of Twente, 2018. 145 p.

Research output: ThesisPhD 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 multi-dimensional 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 two-dimensional models. First, we obtain a perturbed random walk with state-dependent 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 higher-dimensional models. The long-term 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 multi-dimensional 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 two-dimensional models. First, we obtain a perturbed random walk with state-dependent 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 higher-dimensional models. The long-term 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 - 978-94-9301-443-5

T3 - DSI Ph.D. thesis series

PB - University of Twente

CY - Enschede

ER -

Bai X. Performance bounds for random walks in the positive orthant. Enschede: University of Twente, 2018. 145 p. (DSI Ph.D. thesis series; 18-010). https://doi.org/10.3990/1.9789493014435