Revisiting the Tail Asymptotics of the Double QBD Process: Refinement and Complete Solutions for the Coordinate and Diagonal Directions

Masahiro Kobayashi⁷ &
Masakiyo Miyazawa⁷

Part of the book series: Springer Proceedings in Mathematics & Statistics ((PROMS,volume 27))

1946 Accesses
9 Citations

Abstract

We consider a two-dimensional skip-free reflecting random walk on a nonnegative integer quadrant. We are interested in the tail asymptotics of its stationary distribution, provided its existence is assumed. We derive exact tail asymptotics for the stationary probabilities on the coordinate axis. This refines the asymptotic results in the literature and completely solves the tail asymptotic problem on the stationary marginal distributions in the coordinate and diagonal directions. For this, we use the so-called analytic function method in such a way that either generating functions or moment-generating functions are suitably chosen. The results are exemplified by a two-node network with simultaneous arrivals.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic

£29.99 /Month

Get 10 units per month
Download Article/Chapter or eBook
1 Unit = 1 Article or 1 Chapter
Cancel anytime

Buy Now

Chapter: GBP 19.95; Price includes VAT (United Kingdom)

eBook: GBP 71.50; Price includes VAT (United Kingdom)

Softcover Book: GBP 89.99; Price includes VAT (United Kingdom)

Hardcover Book: GBP 89.99; Price includes VAT (United Kingdom)

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Tail asymptotics in any direction of the stationary distribution in a two-dimensional discrete-time QBD process

Article 30 August 2022

Asymptotic expansions in the central limit theorem for a branching Wiener process

Article 16 July 2021

Stein’s method for diffusive limits of queueing processes

Article 02 June 2020

References

Avram, F., Dai, J.G., Hasenbein, J.J.: Explicit solutions for variational problems in the quadrant. Queue. Syst. 37, 259–289 (2001)
Article MathSciNet MATH Google Scholar
Borovkov, A.A., Mogul’skii, A.A.: Large deviations for Markov chains in the positive quadrant. Russ. Math. Surv. 56, 803–916 (2001)
Google Scholar
Dai, J.G., Miyazawa, M.: Reflecting Brownian motion in two dimensions: exact asymptotics for the stationary distribution. Stoch. Syst. 1, 146–208 (2011)
Article Google Scholar
Dai, J.G., Miyazawa, M.: Stationary distribution of a two-dimensional SRBM: geometric views and boundary measures. Submitted for publication (arXiv:1110.1791v1) (2011)
Google Scholar
Fayolle, G., Malyshev, V.A., Menshikov, M.V.: Topics in the Constructive Theory of Countable Markov Chains. Cambridge University Press, Cambridge (1995)
Book MATH Google Scholar
Fayolle, G., Iasnogorodski, R., Malyshev, V.: Random Walks in the Quarter-Plane: Algebraic Methods, Boundary Value Problems and Applications. Springer, New York (1999)
Book MATH Google Scholar
Flajolet, P., Sedqewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009)
Book MATH Google Scholar
Flatto, L., Hahn, S.: Two parallel queues by arrivals with two demands I. SIAM J. Appl. Math. 44, 1041–1053 (1984)
Article MathSciNet MATH Google Scholar
Flatto, L., McKean, H.P.: Two queues in parallel. Comm. Pure Appl. Math. 30, 255–263 (1977)
Article MathSciNet MATH Google Scholar
Foley, R.D., McDonald, D.R.: Bridges and networks: exact asymptotics. Ann. Appl. Probab. 15, 542–586 (2005)
Article MathSciNet MATH Google Scholar
Foley, R.D., McDonald, D.R.: Large deviations of a modified Jackson network: Stability and rough asymptotics. Ann. Appl. Probab. 15, 519–541 (2005)
Article MathSciNet MATH Google Scholar
Guillemin, F., van Leeuwaarden, J.S.H.: Rare event asymptotics for a random walk in the quarter plane. Queue. Syst. 67, 1–32 (2011)
Article MATH Google Scholar
Kobayashi, M., Miyazawa, M.: Tail asymptotics of the stationary distribution of a two dimensional reflecting random walk with unbounded upward jumps. Submitted for publication (2011)
Google Scholar
Li, H., Zhao, Y.Q.: Exact tail asymptotics in a priority queue–characterizations of the preemptive model. Queue. Syst. 63, 355–381 (2009)
Article MATH Google Scholar
Li, H., Zhao, Y.Q.: Tail asymptotics for a generalized two-demand queueing models – a kernel method. Queue. Syst. 69, 77–100 (2011)
Article MATH Google Scholar
Li, H., Zhao, Y.Q.: A kernel method for exact tail asymptotics: random walks in the quarter plane. Preprint (2011)
Google Scholar
Markushevich, A.I.: Theory of Functions, vols. I, II and III, 2nd edn., trans. by R.A. Silverman, reprinted by American Mathematical Society, Providence, Rhode Island (1977)
Google Scholar
Miyazawa, M.: Tail decay rates in double QBD processes and related reflected random walks. Math. Oper. Res. 34, 547–575 (2009)
Article MathSciNet MATH Google Scholar
Miyazawa, M.: Light tail asymptotics in multidimensional reflecting processes for queueing networks. TOP 19, 233–299 (2011)
Article MathSciNet Google Scholar
Miyazawa, M., Rolski, T.: Exact asymptotics for a Levy-driven tandem queue with an intermediate input. Queue. Syst. 63, 323–353 (2009)
Article MathSciNet MATH Google Scholar
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, 1231–1251 (2004)
Article MathSciNet MATH Google Scholar

Download references

Acknowledgements

We are grateful to Mark S. Squillante for encouraging us to complete this work. We are also thankful to the three anonymous referees. This research was supported in part by the Japan Society for the Promotion of Science under Grant No. 21510165.

Author information

Authors and Affiliations

Tokyo University of Science, Noda, Chiba, 278-8510, Japan
Masahiro Kobayashi & Masakiyo Miyazawa

Authors

Masahiro Kobayashi
View author publications
You can also search for this author in PubMed Google Scholar
Masakiyo Miyazawa
View author publications
You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Masakiyo Miyazawa .

Editor information

Editors and Affiliations

, Faculté des Sciences, Univ. Libre de Bruxelles, Blvd. du Triomphe, CP 212, Bruxelles, 1050, Belgium
Guy Latouche
At&T Labs Research, Park Avenue 180, Florham Park, 07932, New Jersey, USA
Vaidyanathan Ramaswami
, IEOR, Columbia University, West 120th Street 500, New York City, 10027, New York, USA
Jay Sethuraman
, Dept of Industrial Engineering and OR, Columbia University, 312 Mudd Bldg., New York, 10027, New York, USA
Karl Sigman
IBM Thomas J. Watson Research Center, Kitchawan Road 1101, Yorktown Heights, 10598, New York, USA
Mark S. Squillante
, IEOR, Columbia University, West 120th Street 500, New York City, 10027, New York, USA
David D. Yao

Appendix

Proof of Lemma 8.6

Note that u ² D ₂(u) is a polynomial of order 2 at least and order 4 at most. For k = 1, 3, let c _k be the coefficients of u ^k in the polynomial u ² D ₂(u). Then,

$$\begin{array}{rcl} & & {c}_{1} = -2(1 - {p}_{00}){p}_{(-1)0} - 4({p}_{(-1)(-1)}{p}_{01} + {p}_{(-1)1}{p}_{0(-1)}) \leq 0, \\ & & {c}_{3} = -2(1 - {p}_{00}){p}_{10} - 4({p}_{1(-1)}{p}_{01} + {p}_{11}{p}_{0(-1)}) \leq 0. \end{array}$$

Hence, if both u ₁ ^(1, max) and − u ₁ ^(1, max) are the solutions of u ² D ₂(u) = 0, then

$$\begin{array}{rcl} 2({c}_{1}{u}_{1}^{(1,\max )} + {c}_{ 3}{({u}_{1}^{(1,\max )})}^{3}) = {({u}_{ 1}^{(1,\max )})}^{2}({D}_{ 2}({u}_{1}^{(1,\max )}) - {D}_{ 2}(-{u}_{1}^{(1,\max )})) = 0.& & \\ \end{array}$$

Since u ₁ ^(1, max) > 0, this holds true if and only if ${c}_{1} = {c}_{3} = 0$, which is equivalent to ${p}_{01} = {p}_{0(-1)} = {p}_{(-1)0} = {p}_{10} = 0$ because p ₀₀ = 1 is impossible. Hence, u ² D ₂(u) = 0 has the two solutions u ₁ ^(1, max) and − u ₁ ^(1, max) if and only if (v-a) does not hold. In this case, we have ${c}_{1} = {c}_{3} = 0$, which implies that u ² D ₂(u) is an even function. Since u ² D ₂(u) = 0 has only real solutions including u ₁ ^(1, max) by Lemmas 8.4 and 8.5, we complete the proof. □

Proof of Lemma 8.7

By (8.17), we have

$$\begin{array}{rcl} {\sum \limits_{i\in \{-1,0,1\}}}{ \sum \limits_{j\in \{-1,0,1\}}}{p}_{ij}{x}^{i}{y}^{j} = 1,\qquad {\sum \limits_{i\in \{-1,0,1\}}}{ \sum \limits_{j\in \{-1,0,1\}}}{(-1)}^{i+j}{p}_{ ij}{x}^{i}{y}^{j} = 1.& & \\ \end{array}$$

Subtracting both sides of these equations we have

$$\begin{array}{rcl}{ p}_{10}x + {p}_{01}y + {p}_{0(-1)}{y}^{-1} + {p}_{ (-1)0}{x}^{-1} = 0.& & \\ \end{array}$$

Since x, y are positive, this equation holds true if and only if

$$\begin{array}{rcl}{ p}_{10} = {p}_{01} = {p}_{0(-1)} = {p}_{(-1)0} = 0.& & \\ \end{array}$$

This is the condition that (v-a) does not hold. □

Rights and permissions

Reprints and permissions

Copyright information

About this paper

Cite this paper

Kobayashi, M., Miyazawa, M. (2013). Revisiting the Tail Asymptotics of the Double QBD Process: Refinement and Complete Solutions for the Coordinate and Diagonal Directions. In: Latouche, G., Ramaswami, V., Sethuraman, J., Sigman, K., Squillante, M., D. Yao, D. (eds) Matrix-Analytic Methods in Stochastic Models. Springer Proceedings in Mathematics & Statistics, vol 27. Springer, New York, NY. https://doi.org/10.1007/978-1-4614-4909-6_8

Download citation

DOI: https://doi.org/10.1007/978-1-4614-4909-6_8
Published: 28 October 2012
Publisher Name: Springer, New York, NY
Print ISBN: 978-1-4614-4908-9
Online ISBN: 978-1-4614-4909-6
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)

Publish with us

Policies and ethics