article

Asymptotics for the stationary distribution in a discrete-time two-dimensional quasi-birth-and-death process

Author:

Toshihisa OzawaAuthors Info & Claims

Queueing Systems: Theory and Applications, Volume 74, Issue 2-3

Pages 109 - 149

https://doi.org/10.1007/s11134-012-9323-9

Published: 01 June 2013 Publication History

Abstract

We consider a discrete-time two-dimensional process $\{(L_{n}^{(1)},L_{n}^{(2)})\}$ on $\mathbb{Z}_{+}^{2}$ with a background process { J _n} on a finite set, where individual processes $\{L_{n}^{(1)}\}$ and $\{L_{n}^{(2)}\}$ are both skip free. We assume that the joint process $\{Y_{n}\}=\{(L_{n}^{(1)},L_{n}^{(2)},J_{n})\}$ is Markovian and that the transition probabilities of the two-dimensional process $\{(L_{n}^{(1)},L_{n}^{(2)})\}$ are modulated depending on the state of the background process { J _n}. This modulation is space homogeneous, but the transition probabilities in the inside of $\mathbb{Z}_{+}^{2}$ and those around the boundary faces may be different. We call this process a discrete-time two-dimensional quasi-birth-and-death (2D-QBD) process, and obtain the decay rates of the stationary distribution in the coordinate directions. We also distinguish the case where the stationary distribution asymptotically decays in the exact geometric form, in the coordinate directions.

References

[1]

Boxma, O.J., Groenendijk, W.P.: Two queues with alternating service and switching times. In: Boxma, O.J., Syski, S. (eds.) Queueing Theory and Its Applications, pp. 261-282. North-Holland, Amsterdam (1988).

[2]

Fayolle, G., Malyshev, V.A., Menshikov, M.V.: Topics in the Constructive Theory of Countable Markov Chains. Cambridge University Press, Cambridge (1995).

[3]

Haque, L., Zhao, Y.Q.: Sufficient conditions for a geometric tail in a QBD process with many countable levels and phases. Stoch. Models 21 (1), 77-99 (2005).

[4]

He, Q.-M., Li, H., Zhao, T.Q.: Light-tailed behavior in QBD processes with countably many phases. Stoch. Models 25 , 50-75 (2009).

[5]

Katou, K., Makimoto, N., Takahashi, Y.: Upper bound for the decay rate of the marginal queue-length distribution in a two-node Markovian queueing system. J. Oper. Res. Soc. Jpn. 47 , 314-338 (2004).

[6]

Katou, K., Makimoto, N., Takahashi, Y.: Upper bound for the decay rate of the joint queue-length distribution in a two-node Markovian queueing system. Queueing Syst. 58 , 161-189 (2008).

Digital Library

[7]

Kijima, M.: Quasi-stationary distributions of single-server phase-type queues. Math. Oper. Res. 18 (2), 423-437 (1993).

Digital Library

[8]

Kingman, J.F.C.: A convexity property of positive matrices. Q. J. Math. 12 , 283-284 (1961).

[9]

Kobayashi, M., Miyazawa, M.: Revisit to the tail asymptotics of the double QBD process: Refinement and complete solutions for the coordinate and diagonal directions. In: Matrix-Analytic Methods in Stochastic Models. Springer, Berlin (2012, to appear).

[10]

Latouche, G., Ramaswami, V.: Introduction to Matrix Analytic Methods in Stochastic Modeling. SIAM, Philadelphia (1999).

[11]

Li, Q.-L., Zhao, Y.Q.: A constructive method for finding ß-invariant measures for transition matrices of M/G/1 type. In: Latouche, G., Taylor, P. (eds.) Matrix-Analytic Methods: Theory and Applications, pp. 237-263. World Scientific, Singapore (2002).

[12]

Li, Q.-L., Zhao, Y.Q.: ß-invariant measures for transition matrices of GI/M/1 type. Stoch. Models 19 (2), 201-233 (2003).

[13]

Li, H., Miyazawa, M., Zhao, Y.Q.: Geometric decay in a QBD process with countable background states with applications to a join-the-shortest-queue model. Stoch. Models 23 (3), 413-438 (2007).

[14]

Li, H., Zhao, Y.Q.: Exact tail asymptotics in a priority queue--characterizations of the nonpreemptive model. Queueing Syst. 68 (2), 165-192 (2011).

Digital Library

[15]

Miyazawa, M., Zhao, Y.Q.: The stationary tail asymptotics in the GI/G/1 type queue with countably many background states. Adv. Appl. Probab. 36 (4), 1231-1251 (2004).

[16]

Miyazawa, M.: Tail decay rates in double QBD processes and related reflected random walks. Math. Oper. Res. 34 (3), 547-575 (2009).

Digital Library

[17]

Miyazawa, M.: Light tail asymptotics in multidimensional reflecting processes for queueing networks. Top 19 (2), 233-299 (2011).

[18]

Motyer, A.J., Taylor, P.G.: Decay rates for quasi-birth-and-death processes with countably many phases and tridiagonal block generators. Adv. Appl. Probab. 38 , 522-544 (2006).

[19]

Neuts, M.F.: Matrix-Geometric Solutions in Stochastic Models. Dover Publications, New York (1994).

[20]

Ozawa, T.: Waiting time distribution in a two-queue model with mixed exhaustive and gated-type K -limited services. In: Hasegawa, T., Takagi, H., Takahashi, Y. (eds.) Performance and Management of Complex Communication Networks, pp. 233-252. Chapman & Hall, London (1998).

[21]

Resing, J.A.C.: Polling systems and multiple branching processes. Queueing Syst. 13 , 409-426 (1993).

[22]

Seneta, E.: Non-negative Matrices and Markov Chains, Revised Printing. Springer, New York (2006).

[23]

Takagi, H.: Queueing analysis of polling models: progress in 1990-1994. In: Dshalalow, J.H. (ed.) Frontiers in Queueing: Models, Methods and Problems, pp. 119-146. CRC Press, Boca Raton (1997).

Digital Library

[24]

Takagi, H.: Analysis and application of polling models. In: Haring, G., Lindemann, C., Reiser, M. (eds.) Performance Evaluation: Origins and Directions. Lecture Notes in Computer Science, pp. 424- 442. Springer, Berlin (2000).

[25]

Takahashi, Y., Fujimoto, K., Makimoto, N.: Geometric decay of the steady-state probabilities in a quasi-birth-and-death process with a countable number of phases. Stoch. Models 17 (1), 1-24 (2001).

[26]

Tweedie, R.L.: Operator-geometric stationary distributions for Markov chains with applications to queueing models. Adv. Appl. Probab. 14 , 368-391 (1982).

[27]

Winands, E.M.M., Adan, I.J.B.F., van Houtum, G.J., Down, D.G.: A state-dependent polling model with k -limited service. Probab. Eng. Inf. Sci. 23 , 385-408 (2009).

Digital Library

[28]

Xue, J., Alfa, A.S.: Geometric tail of queue length of low-priority customers in a nonpreemptive priority MAP/PH/1 queue. Queueing Syst. 69 (1), 45-76 (2011).

Digital Library

Cited By

Ozawa T(2022)Tail asymptotics in any direction of the stationary distribution in a two-dimensional discrete-time QBD processQueueing Systems: Theory and Applications10.1007/s11134-022-09860-w102:1-2(227-267)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s11134-022-09860-w
Zhao Y(2022)The kernel method tail asymptotics analytic approach for stationary probabilities of two-dimensional queueing systemsQueueing Systems: Theory and Applications10.1007/s11134-021-09727-6100:1-2(95-131)Online publication date: 1-Feb-2022
https://dl.acm.org/doi/10.1007/s11134-021-09727-6
Dimitriou I(2021)On partially homogeneous nearest-neighbour random walks in the quarter plane and their application in the analysis of two-dimensional queues with limited state-dependencyQueueing Systems: Theory and Applications10.1007/s11134-021-09705-y98:1-2(95-143)Online publication date: 27-Apr-2021
https://dl.acm.org/doi/10.1007/s11134-021-09705-y
Show More Cited By

Recommendations

Exact asymptotic formulae of the stationary distribution of a discrete-time two-dimensional QBD process

We consider a discrete-time two-dimensional process $$\{(X_{1,n},X_{2,n})\}$${(X1,n,X2,n)} on $$\mathbb {Z}_+^2$$Z+2 with a supplemental process $$\{J_n\}$${Jn} on a finite set, where the individual processes $$\{X_{1,n}\}$${X1,n} and $$\{X_{2,n}\}$${X2,...
Asymptotics for the sojourn time distribution in the queue defined by a general QBD process with a countable phase space

We consider a FIFO queue defined by a QBD process. When the number of phases of the QBD process is finite, it has been proved that the stationary distribution of sojourn times in that queue can be represented as a phase-type distribution. In this paper, ...
Tail asymptotics in any direction of the stationary distribution in a two-dimensional discrete-time QBD process
Abstract
We consider a discrete-time two-dimensional quasi-birth-and-death process (2d-QBD process for short) ${(X_{n}, J_{n})}$ on $Z_{+}^{2} \times S_{0}$ , where $X_{n} = (X_{1, n}, X_{2, n})$ is the level state, $J_{n}$ the phase state (background state) and $S_{0}$ a finite set, and study asymptotic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Queueing Systems: Theory and Applications

Queueing Systems: Theory and Applications Volume 74, Issue 2-3

June 2013

260 pages

ISSN:0257-0130

Issue’s Table of Contents

Copyright © Copyright © 2013 Springer Science+Business Media New York.

Publisher

J. C. Baltzer AG, Science Publishers

United States

Publication History

Published: 01 June 2013

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ozawa T(2022)Tail asymptotics in any direction of the stationary distribution in a two-dimensional discrete-time QBD processQueueing Systems: Theory and Applications10.1007/s11134-022-09860-w102:1-2(227-267)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s11134-022-09860-w
Zhao Y(2022)The kernel method tail asymptotics analytic approach for stationary probabilities of two-dimensional queueing systemsQueueing Systems: Theory and Applications10.1007/s11134-021-09727-6100:1-2(95-131)Online publication date: 1-Feb-2022
https://dl.acm.org/doi/10.1007/s11134-021-09727-6
Dimitriou I(2021)On partially homogeneous nearest-neighbour random walks in the quarter plane and their application in the analysis of two-dimensional queues with limited state-dependencyQueueing Systems: Theory and Applications10.1007/s11134-021-09705-y98:1-2(95-143)Online publication date: 27-Apr-2021
https://dl.acm.org/doi/10.1007/s11134-021-09705-y
Ozawa T(2021)Asymptotic properties of the occupation measure in a multidimensional skip-free Markov-modulated random walkQueueing Systems: Theory and Applications10.1007/s11134-020-09673-997:1-2(125-161)Online publication date: 1-Feb-2021
https://dl.acm.org/doi/10.1007/s11134-020-09673-9
Dimitriou I(2019)Stationary Analysis of a Tandem Queue with Coupled Processors Subject to Global BreakdownsQueueing Theory and Network Applications10.1007/978-3-030-27181-7_15(240-259)Online publication date: 27-Aug-2019
https://dl.acm.org/doi/10.1007/978-3-030-27181-7_15
Ozawa TKobayashi M(2018)Exact asymptotic formulae of the stationary distribution of a discrete-time two-dimensional QBD processQueueing Systems: Theory and Applications10.5555/3288543.328856790:3-4(351-403)Online publication date: 1-Dec-2018
https://dl.acm.org/doi/10.5555/3288543.3288567
Masuyama HSakuma YKobayashi M(2016)Simple error bounds for the QBD approximation of a special class of two dimensional reflecting random walksProceedings of the 11th International Conference on Queueing Theory and Network Applications10.1145/3016032.3016048(1-5)Online publication date: 13-Dec-2016
https://dl.acm.org/doi/10.1145/3016032.3016048
Miyazawa M(2015)A superharmonic vector for a nonnegative matrix with QBD block structure and its application to a Markov-modulated two-dimensional reflecting processQueueing Systems: Theory and Applications10.1007/s11134-015-9454-x81:1(1-48)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1007/s11134-015-9454-x
Miyazawa M(2014)Tail asymptotics of the stationary distribution for a two-node generalized Jackson networkACM SIGMETRICS Performance Evaluation Review10.1145/2667522.266754542:2(70-72)Online publication date: 4-Sep-2014
https://dl.acm.org/doi/10.1145/2667522.2667545

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents