Article
Full entry |
PDF
(0.4 MB)
Feedback
PDF
(0.4 MB)
Feedback
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
Summary:
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.
References:
[1] Bayer, N., Boucherie, R. J.: On the structure of the space of geometric product-form models. Probab. Engrg. Inform. Sci. 16 (2002), 02, 241-270. DOI 10.1017/s0269964802162073 | MR 1891475 | Zbl 1004.60091
[2] Bertsimas, D., Paschalidis, I. C., Tsitsiklis, J. N.: 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 | MR 1258173 | Zbl 0797.60079
[3] Boucherie, R. J., Dijk, N. M. van: 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 | MR 2520746
[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. Zbl 1348.60068
[6] Cohen, J. W., Boxma, O. J.: Boundary Value Problems in Queueing System Analysis. Zbl 0662.60097
[7] Farias, D. P. de, Roy, B. Van: The linear programming approach to approximate dynamic programming. Oper. Res. 51 (2003), 6, 850-865. DOI 10.1287/opre.51.6.850.24925 | MR 2019651
[8] Farias, D. P. de, Roy, B. Van: 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 | MR 2254426
[9] Fayolle, G., Iasnogorodski, R.: Two coupled processors: the reduction to a Riemann-Hilbert problem. Probab. Theory Related Fields 47 (1979), 3, 325-351. DOI 10.1007/bf00535168 | MR 0525314 | Zbl 0395.68032
[10] Fayolle, G., Iasnogorodski, R., Malyshev, V.: Random Walks in the Quarter Plane: Algebraic Methods, Boundary Value Problems, and Applications. MR 1691900 | Zbl 0932.60002
[11] Goseling, J., Boucherie, R. J., Ommeren, J. C. W. van: 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] Kroese, D. P., Scheinhardt, W. R. W., Taylor, P. G.: 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 | MR 2099663 | Zbl 1078.60078
[13] Kumar, S., Kumar, P. R.: Performance bounds for queueing networks and scheduling policies. IEEE Trans. Automat. Control 39 (1994), 8, 1600-1611. DOI 10.1109/9.310033 | MR 1287267 | Zbl 0812.90049
[14] Latouche, G., Mahmoodi, S., Taylor, P. G.: 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] Miyazawa, M.: 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 | MR 2555336 | Zbl 1213.60151
[16] Morrison, J. R., Kumar, P. R.: New linear program performance bounds for queueing networks. J. Optim. Theory Appl. 100 (1999), 3, 575-597. DOI 10.1023/a:1022638523391 | MR 1684537 | Zbl 0949.90019
[17] M{ü}ller, A., Stoyan, D.: Comparison Methods for Stochastic Models and Risks. Wiley, 2002. MR 1889865 | Zbl 0999.60002
[18] Taylor, P. G., Dijk, N. M. van: 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 | MR 1653218
[19] Dijk, N. M. van: Simple bounds for queueing systems with breakdowns. Perform. Evaluation 8 (1988), 2, 117-128. DOI 10.1016/0166-5316(88)90017-x | MR 0938482
[20] Dijk, N. M. van: Sensitivity error bounds for non-exponential stochastic networks. Kybernetika 31 (1995), 2, 175-188. MR 1334508
[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. MR 1454277
[22] Dijk, N. M. van: Bounds and error bounds for queueing networks. Ann. Oper. Res. 79 (1998), 295-319. DOI 10.1023/a:1018978823209 | MR 1630884
[23] Dijk, N. M. van: 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 | MR 2796367
[24] Dijk, N. M. van, Lamond, B. F.: Simple bounds for finite single-server exponential tandem queues. Oper. Res. 36 (1998), 3, 470-477. DOI 10.1287/opre.36.3.470 | MR 0955756
[25] Dijk, N. M. van, Miyazawa, M.: Error bounds for perturbing nonexponential queues. Math. Oper. Res. 29 (2004), 3, 525-558. DOI 10.1287/moor.1040.0111 | MR 2082617
[26] Dijk, N. M. van, Puterman, M. L.: Perturbation theory for Markov reward processes with applications to queueing systems. Adv. Appl. Probab. 20 (1998), 1, 79-98. DOI 10.2307/1427271 | MR 0932535
Search
Partner of
