A linear programming approach to error bounds for random walks in the quarter-plane

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)

Abstract

We consider the steady-state behavior of random walks in the quarter-plane, in particular, the expected value of performance measures that are component-wise linear over the state space. Since the stationary distribution of a random walk is in general not readily available we establish upper and lower bounds on performance in terms of another random walk with perturbed transition probabilities, for which the stationary distribution is a geometric product-form. The Markov reward approach as developed by van Dijk is used to bound the perturbation error. The main contribution of the work is the formulation of finite linear programs that provide upper and lower bounds to the performance of the original random walk. Most importantly, these linear programs establish bounds on the bias terms. This leverages an important drawback in the application of the Markov reward approach, which in existing literature is based on meticulously crafted bounds on the bias terms.
Original languageEnglish
Pages (from-to)757-784
Number of pages28
JournalKybernetika
Volume52
Issue number5
DOIs
Publication statusPublished - 2016

Fingerprint

Linear programming
Error Bounds
Random walk
Stationary Distribution
Linear Program
Reward
Upper and Lower Bounds
Product Form
Term
Transition Probability
Expected Value
Leverage
Performance Measures
State Space
Perturbation
Formulation

Keywords

  • Error bound
  • Linear programming
  • Markov reward approach
  • Quarter-plane
  • Random walk
  • Reected random walk
  • Stationary distribution

Cite this

@article{6bb5d97ff88a4a9ebb2e995262b7c132,
title = "A linear programming approach to error bounds for random walks in the quarter-plane",
abstract = "We consider the steady-state behavior of random walks in the quarter-plane, in particular, the expected value of performance measures that are component-wise linear over the state space. Since the stationary distribution of a random walk is in general not readily available we establish upper and lower bounds on performance in terms of another random walk with perturbed transition probabilities, for which the stationary distribution is a geometric product-form. The Markov reward approach as developed by van Dijk is used to bound the perturbation error. The main contribution of the work is the formulation of finite linear programs that provide upper and lower bounds to the performance of the original random walk. Most importantly, these linear programs establish bounds on the bias terms. This leverages an important drawback in the application of the Markov reward approach, which in existing literature is based on meticulously crafted bounds on the bias terms.",
keywords = "Error bound, Linear programming, Markov reward approach, Quarter-plane, Random walk, Reected random walk, Stationary distribution",
author = "Jasper Goseling and Boucherie, {Richard J.} and {van Ommeren}, Jan-Kees",
year = "2016",
doi = "10.14736/kyb-2016-5-0757",
language = "English",
volume = "52",
pages = "757--784",
journal = "Kybernetika",
issn = "0023-5954",
publisher = "Academy of Sciences of the Czech Republic",
number = "5",

}

A linear programming approach to error bounds for random walks in the quarter-plane. / Goseling, Jasper; Boucherie, Richard J.; van Ommeren, Jan-Kees.

In: Kybernetika, Vol. 52, No. 5, 2016, p. 757-784.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - A linear programming approach to error bounds for random walks in the quarter-plane

AU - Goseling, Jasper

AU - Boucherie, Richard J.

AU - van Ommeren, Jan-Kees

PY - 2016

Y1 - 2016

N2 - We consider the steady-state behavior of random walks in the quarter-plane, in particular, the expected value of performance measures that are component-wise linear over the state space. Since the stationary distribution of a random walk is in general not readily available we establish upper and lower bounds on performance in terms of another random walk with perturbed transition probabilities, for which the stationary distribution is a geometric product-form. The Markov reward approach as developed by van Dijk is used to bound the perturbation error. The main contribution of the work is the formulation of finite linear programs that provide upper and lower bounds to the performance of the original random walk. Most importantly, these linear programs establish bounds on the bias terms. This leverages an important drawback in the application of the Markov reward approach, which in existing literature is based on meticulously crafted bounds on the bias terms.

AB - We consider the steady-state behavior of random walks in the quarter-plane, in particular, the expected value of performance measures that are component-wise linear over the state space. Since the stationary distribution of a random walk is in general not readily available we establish upper and lower bounds on performance in terms of another random walk with perturbed transition probabilities, for which the stationary distribution is a geometric product-form. The Markov reward approach as developed by van Dijk is used to bound the perturbation error. The main contribution of the work is the formulation of finite linear programs that provide upper and lower bounds to the performance of the original random walk. Most importantly, these linear programs establish bounds on the bias terms. This leverages an important drawback in the application of the Markov reward approach, which in existing literature is based on meticulously crafted bounds on the bias terms.

KW - Error bound

KW - Linear programming

KW - Markov reward approach

KW - Quarter-plane

KW - Random walk

KW - Reected random walk

KW - Stationary distribution

U2 - 10.14736/kyb-2016-5-0757

DO - 10.14736/kyb-2016-5-0757

M3 - Article

VL - 52

SP - 757

EP - 784

JO - Kybernetika

JF - Kybernetika

SN - 0023-5954

IS - 5

ER -