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

Jasper Goseling; Richard J. Boucherie; Jan-Kees van Ommeren

Kybernetika (2016)

  • Volume: 52, Issue: 5, page 757-784
  • ISSN: 0023-5954

Abstract

top
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.

How to cite

top

Goseling, Jasper, Boucherie, Richard J., and van Ommeren, Jan-Kees. "A linear programming approach to error bounds for random walks in the quarter-plane." Kybernetika 52.5 (2016): 757-784. <http://eudml.org/doc/287526>.

@article{Goseling2016,
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.},
author = {Goseling, Jasper, Boucherie, Richard J., van Ommeren, Jan-Kees},
journal = {Kybernetika},
keywords = {random walk; quarter-plane; reflected random walk; stationary distribution; error bound; Markov reward approach; linear programming; random walk; quarter-plane; reflected random walk; stationary distribution; error bound; Markov reward approach; linear programming},
language = {eng},
number = {5},
pages = {757-784},
publisher = {Institute of Information Theory and Automation AS CR},
title = {A linear programming approach to error bounds for random walks in the quarter-plane},
url = {http://eudml.org/doc/287526},
volume = {52},
year = {2016},
}

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
PB - Institute of Information Theory and Automation AS CR
VL - 52
IS - 5
SP - 757
EP - 784
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.
LA - eng
KW - random walk; quarter-plane; reflected random walk; stationary distribution; error bound; Markov reward approach; linear programming; random walk; quarter-plane; reflected random walk; stationary distribution; error bound; Markov reward approach; linear programming
UR - http://eudml.org/doc/287526
ER -

References

top
  1. Bayer, N., Boucherie, R. J., 10.1017/s0269964802162073, Probab. Engrg. Inform. Sci. 16 (2002), 02, 241-270. Zbl1004.60091MR1891475DOI10.1017/s0269964802162073
  2. Bertsimas, D., Paschalidis, I. C., Tsitsiklis, J. N., 10.1214/aoap/1177005200, Ann. Appl. Prob. 4 (1994), 1, 43-75. Zbl0797.60079MR1258173DOI10.1214/aoap/1177005200
  3. Boucherie, R. J., Dijk, N. M. van, 10.1007/s11134-009-9118-9, Queueing Systems 62 (2009), 1-2, 159-193. MR2520746DOI10.1007/s11134-009-9118-9
  4. Chen, Y., Bai, X., Boucherie, R. J., Goseling, J., Performance measures for the two-node queue with finite buffers., Under review at Performance Evaluation. 
  5. Chen, Y., Boucherie, R. J., Goseling, J., Invariant measures and error bounds for random walks in the quarter-plane based on sums of geometric terms., Under review at Queueing Systems. Zbl1348.60068
  6. Cohen, J. W., Boxma, O. J., Boundary Value Problems in Queueing System Analysis Zbl0662.60097
  7. Farias, D. P. de, Roy, B. Van, 10.1287/opre.51.6.850.24925, Oper. Res. 51 (2003), 6, 850-865. MR2019651DOI10.1287/opre.51.6.850.24925
  8. Farias, D. P. de, Roy, B. Van, 10.1287/moor.1060.0208, Math. Oper. Res. 31 (2006), 3, 597-620. MR2254426DOI10.1287/moor.1060.0208
  9. Fayolle, G., Iasnogorodski, R., 10.1007/bf00535168, Probab. Theory Related Fields 47 (1979), 3, 325-351. Zbl0395.68032MR0525314DOI10.1007/bf00535168
  10. Fayolle, G., Iasnogorodski, R., Malyshev, V., Random Walks in the Quarter Plane: Algebraic Methods, Boundary Value Problems, and Applications Zbl0932.60002MR1691900
  11. Goseling, J., Boucherie, R. J., Ommeren, J. C. W. van, 10.1016/j.peva.2013.08.002, Perform. Evaluation 70 (2013), 11, 981-994. DOI10.1016/j.peva.2013.08.002
  12. Kroese, D. P., Scheinhardt, W. R. W., Taylor, P. G., 10.1214/105051604000000477, Ann. Appl. Probab. 14 (2004), 4, 2057-2089. Zbl1078.60078MR2099663DOI10.1214/105051604000000477
  13. Kumar, S., Kumar, P. R., 10.1109/9.310033, IEEE Trans. Automat. Control 39 (1994), 8, 1600-1611. Zbl0812.90049MR1287267DOI10.1109/9.310033
  14. Latouche, G., Mahmoodi, S., Taylor, P. G., 10.1016/j.peva.2013.05.004, Perform. Evaluation 70 (2013), 9, 551-563. DOI10.1016/j.peva.2013.05.004
  15. Miyazawa, M., 10.1287/moor.1090.0375, Math. Oper. Res. 34 (2009), 3, 547-575. Zbl1213.60151MR2555336DOI10.1287/moor.1090.0375
  16. Morrison, J. R., Kumar, P. R., 10.1023/a:1022638523391, J. Optim. Theory Appl. 100 (1999), 3, 575-597. Zbl0949.90019MR1684537DOI10.1023/a:1022638523391
  17. M{ü}ller, A., Stoyan, D., Comparison Methods for Stochastic Models and Risks., Wiley, 2002. Zbl0999.60002MR1889865
  18. Taylor, P. G., Dijk, N. M. van, 10.1287/opre.46.5.665, Oper. Res. 46 (1998), 5, 665-674. MR1653218DOI10.1287/opre.46.5.665
  19. Dijk, N. M. van, 10.1016/0166-5316(88)90017-x, Perform. Evaluation 8 (1988), 2, 117-128. MR0938482DOI10.1016/0166-5316(88)90017-x
  20. Dijk, N. M. van, Sensitivity error bounds for non-exponential stochastic networks., Kybernetika 31 (1995), 2, 175-188. MR1334508
  21. Dijk, N. M. van, Error bounds for arbitrary approximations of "nearly reversible'' Markov chains and a communications example., Kybernetika 33 (1997), 2, 171-184. MR1454277
  22. Dijk, N. M. van, 10.1023/a:1018978823209, Ann. Oper. Res. 79 (1998), 295-319. MR1630884DOI10.1023/a:1018978823209
  23. Dijk, N. M. van, 10.1007/978-1-4419-6472-4_9, In: Queueing Networks: A Fundamental Approacm (R. J. Boucherie and N. M. Van Dijk, eds.), International Series in Operations Research and Management Science 154, Springer, 2011, pp. 397-459. MR2796367DOI10.1007/978-1-4419-6472-4_9
  24. Dijk, N. M. van, Lamond, B. F., 10.1287/opre.36.3.470, Oper. Res. 36 (1998), 3, 470-477. MR0955756DOI10.1287/opre.36.3.470
  25. Dijk, N. M. van, Miyazawa, M., 10.1287/moor.1040.0111, Math. Oper. Res. 29 (2004), 3, 525-558. MR2082617DOI10.1287/moor.1040.0111
  26. Dijk, N. M. van, Puterman, M. L., 10.2307/1427271, Adv. Appl. Probab. 20 (1998), 1, 79-98. MR0932535DOI10.2307/1427271

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.