Kybernetika 52 no. 5, 757-784, 2016

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

Jasper Goseling, Richard J. Boucherie and Jan-Kees van OmmerenDOI: 10.14736/kyb-2016-5-0757

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:

stationary distribution, random walk, quarter-plane, reflected random walk, error bound, Markov reward approach, linear programming

Classification:

60K25, 60G50, 90B22

paper.pdf

References:

  1. N. Bayer and R. J. Boucherie: On the structure of the space of geometric product-form models. Probab. Engrg. Inform. Sci. 16 (2002), 02, 241-270.   DOI:10.1017/s0269964802162073
  2. D. Bertsimas, I. C. Paschalidis and J. N. Tsitsiklis: Optimization of multiclass queueing networks: Polyhedral and nonlinear characterizations of achievable performance. Ann. Appl. Prob. 4 (1994), 1, 43-75.   DOI:10.1214/aoap/1177005200
  3. R. J. Boucherie and N. M. van Dijk: Monotonicity and error bounds for networks of Erlang loss queues. Queueing Systems 62 (2009), 1-2, 159-193.   DOI:10.1007/s11134-009-9118-9
  4. Y. Chen, X. Bai, R. J. Boucherie and J. Goseling: Performance measures for the two-node queue with finite buffers. Under review at Performance Evaluation.   CrossRef
  5. Y. Chen, R. J. Boucherie and J. Goseling: Invariant measures and error bounds for random walks in the quarter-plane based on sums of geometric terms. Under review at Queueing Systems.   CrossRef
  6. J. W. Cohen and O. J. Boxma: Boundary Value Problems in Queueing System Analysis    CrossRef
  7. D. P. de Farias and B. Van Roy: The linear programming approach to approximate dynamic programming. Oper. Res. 51 (2003), 6, 850-865.   DOI:10.1287/opre.51.6.850.24925
  8. D. P. de Farias and B. Van Roy: A cost-shaping linear program for average-cost approximate dynamic programming with performance guarantees. Math. Oper. Res. 31 (2006), 3, 597-620.   DOI:10.1287/moor.1060.0208
  9. G. Fayolle and R. Iasnogorodski: Two coupled processors: the reduction to a Riemann-Hilbert problem. Probab. Theory Related Fields 47 (1979), 3, 325-351.   DOI:10.1007/bf00535168
  10. G. Fayolle, R. Iasnogorodski and V. Malyshev: Random Walks in the Quarter Plane: Algebraic Methods, Boundary Value Problems, and Applications    CrossRef
  11. J. Goseling, R. J. Boucherie and J. C. W. van Ommeren: Energy-delay tradeoff in a two-way relay with network coding. Perform. Evaluation 70 (2013), 11, 981-994.   DOI:10.1016/j.peva.2013.08.002
  12. D. P. Kroese, W. R. W. Scheinhardt and P. G. Taylor: Spectral properties of the tandem Jackson network, seen as a quasi-birth-and-death process. Ann. Appl. Probab. 14 (2004), 4, 2057-2089.   DOI:10.1214/105051604000000477
  13. S. Kumar and P. R. Kumar: Performance bounds for queueing networks and scheduling policies. IEEE Trans. Automat. Control 39 (1994), 8, 1600-1611.   DOI:10.1109/9.310033
  14. G. Latouche, S. Mahmoodi and P. G. Taylor: Level-phase independent stationary distributions for GI/M/1-type Markov chains with infinitely-many phases. Perform. Evaluation 70 (2013), 9, 551-563.   DOI:10.1016/j.peva.2013.05.004
  15. M. Miyazawa: Tail decay rates in double QBD processes and related reflected random walks. Math. Oper. Res. 34 (2009), 3, 547-575.   DOI:10.1287/moor.1090.0375
  16. J. R. Morrison and P. R. Kumar: New linear program performance bounds for queueing networks. J. Optim. Theory Appl. 100 (1999), 3, 575-597.   DOI:10.1023/a:1022638523391
  17. A. M{ü}ller and D. Stoyan: Comparison Methods for Stochastic Models and Risks. Wiley, 2002.   CrossRef
  18. P. G. Taylor and N. M. van Dijk: Strong stochastic bounds for the stationary distribution of a class of multicomponent performability models. Oper. Res. 46 (1998), 5, 665-674.   DOI:10.1287/opre.46.5.665
  19. N. M. van Dijk: Simple bounds for queueing systems with breakdowns. Perform. Evaluation 8 (1988), 2, 117-128.   DOI:10.1016/0166-5316(88)90017-x
  20. N. M. van Dijk: Sensitivity error bounds for non-exponential stochastic networks. Kybernetika 31 (1995), 2, 175-188.   CrossRef
  21. N. M. van Dijk: Error bounds for arbitrary approximations of "nearly reversible'' Markov chains and a communications example. Kybernetika 33 (1997), 2, 171-184.   CrossRef
  22. N. M. van Dijk: Bounds and error bounds for queueing networks. Ann. Oper. Res. 79 (1998), 295-319.   DOI:10.1023/a:1018978823209
  23. N. M. van Dijk: Error bounds and comparison results: The Markov reward approach for queueing networks. 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.   DOI:10.1007/978-1-4419-6472-4_9
  24. N. M. van Dijk and B. F. Lamond: Simple bounds for finite single-server exponential tandem queues. Oper. Res. 36 (1998), 3, 470-477.   DOI:10.1287/opre.36.3.470
  25. N. M. van Dijk and M. Miyazawa: Error bounds for perturbing nonexponential queues. Math. Oper. Res. 29 (2004), 3, 525-558.   DOI:10.1287/moor.1040.0111
  26. N. M. van Dijk and M. L. Puterman: Perturbation theory for Markov reward processes with applications to queueing systems. Adv. Appl. Probab. 20 (1998), 1, 79-98.   DOI:10.2307/1427271