Geodesic
A linear programming approach to error bounds for random walks in the quarter-plane
Kybernetika, Tome 52 (2016) no. 5, pp. 757-784.

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

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.
DOI : 10.14736/kyb-2016-5-0757
Classification : 60G50, 60K25, 90B22
Keywords: random walk; quarter-plane; reflected random walk; stationary distribution; error bound; Markov reward approach; linear programming 
@article{10_14736_kyb_2016_5_0757,
     author = {Goseling, Jasper and Boucherie, Richard J. and van Ommeren, Jan-Kees},
     title = {A linear programming approach to error bounds for random walks in the quarter-plane},
     journal = {Kybernetika},
     pages = {757--784},
     publisher = {mathdoc},
     volume = {52},
     number = {5},
     year = {2016},
     doi = {10.14736/kyb-2016-5-0757},
     mrnumber = {3602014},
     zbl = {06674938},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2016-5-0757/}
}
TY  - JOUR
AU  - Goseling, Jasper
AU  - Boucherie, Richard J.
AU  - van Ommeren, Jan-Kees
TI  - A linear programming approach to error bounds for random walks in the quarter-plane
JO  - Kybernetika
PY  - 2016
SP  - 757
EP  - 784
VL  - 52
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2016-5-0757/
DO  - 10.14736/kyb-2016-5-0757
LA  - en
ID  - 10_14736_kyb_2016_5_0757
ER  - 
%0 Journal Article
%A Goseling, Jasper
%A Boucherie, Richard J.
%A van Ommeren, Jan-Kees
%T A linear programming approach to error bounds for random walks in the quarter-plane
%J Kybernetika
%D 2016
%P 757-784
%V 52
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2016-5-0757/
%R 10.14736/kyb-2016-5-0757
%G en
%F 10_14736_kyb_2016_5_0757
Goseling, Jasper; Boucherie, Richard J.; van Ommeren, Jan-Kees. A linear programming approach to error bounds for random walks in the quarter-plane. Kybernetika, Tome 52 (2016) no. 5, pp. 757-784. doi : 10.14736/kyb-2016-5-0757. http://geodesic.mathdoc.fr/articles/10.14736/kyb-2016-5-0757/

Cité par Sources :