Numerical Computations and Tail Asymptotics for Stationary Indices of a Discrete-time Queue

doi:10.1007/s40305-024-00557-w

Abstract

Abstract: This paper considers numerical computations and tail asymptotics for stationary queue length and sojourn time distribution of the Geo/T-IPH/1 queue, where T-IPH denotes the discrete-time phase type distribution defined on a birth and death chain with countably many states. By analysis of probability generating functions, recursive formulas for queue length and sojourn time, and factorial moments of queue length and sojourn time are given. Moreover, a complete characterization of the regions of system parameters for exact tail asymptotic characterizations for such indices is also given, and the results show that there are three types of exact tail asymptotics for the indices in different regions.

Key words: Tail asymptotics, Geometric decay, Geo/T-IPH/1 queue, Stationary indices, Generating functions

CLC Number:

Hong-Bo Zhang. Numerical Computations and Tail Asymptotics for Stationary Indices of a Discrete-time Queue[J]. Journal of the Operations Research Society of China, 2026, 14(2): 730-747.

TrendMD

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.jorsc.shu.edu.cn/EN/10.1007/s40305-024-00557-w

https://www.jorsc.shu.edu.cn/EN/Y2026/V14/I2/730

References

[1] Alfa, A.S.: Discrete time queues and matrix-analytic methods. TOP 10(2), 147–185(2002)
[2] Alfa, A.S.: Markovchain representations of discrete distributions applied to queueing models. Comput. Oper. Res. 31(14), 2365–2385(2004)
[3] Alfa, A.S.: Queueing theory for telecommunications, discrete time modeling of a single node system. Springer, New York (2010)
[4] Adan, I., Wessels, J., Zijm, W.: A compensation approach for two dimensional Markov processes. Adv. Appl. Probab. 25(4), 783–817(1993)
[5] Blanc, J.: The power-series algorithm applied to the shortest-queue model. Oper. Res. 40(1), 157–167(1992)
[6] Boxma, O.J., van Houtum, G.J.: The compensation approach applied to a 2×2 switch. Probab. Eng. Inf. Sci. 7(4), 471–493(1993)
[7] Cidon, I., Sidi, M.: Recursive computation of steady-state probabilities in priority queues. Oper. Res. Lett. 9(4), 249–256(1990)
[8] Dai, H.S., Kong, L.T., Song, Y.: Exact tail asymptotics for a two-stage queue: complete solution via kernel method. RAIRO Oper. Res. 51(4), 1211–1250(2017)
[9] Devos, A., Walraevens, J., Fiems, D., Bruneel, H.: Analysis of a discrete-time two-class randomly alternating service model with Bernoulli arrivals. Queueing Syst. 96(1–2), 133–152(2020)
[10] Dimitriou, I.: The generalized join the shortest orbit queue system: stability, exact tail asymptotics and stationary approximations. Probab. Eng. Inf. Sci. 37(1), 154–191(2023)
[11] Flajolet, P., Odlyzko, A.: Singularity analysis of generating function. SIAM J. Discret. Math. 3(2), 219–240(1990)
[12] Flatto, L., Hahn, S.: Two parallel queues created by arrivals with two demands-I. J. SIAM Appl. Math. 44(5), 1041–1053(1984)
[13] Flatto, L.: Two parallel queues created by arrivals with two demands-II. J. SIAM Appl. Math. 45(5), 861–878(1985)
[14] Haque, L., Zhao, Y.Q., Liu, L.M.: Sufficient conditions for a geometric tail in a QBD process with many countable levels and phases. Stoch. Model. 21(1), 77–99(2005)
[15] Hooghiemstra, G., Keane, M., De Ree, V.S.: Power series of stationary distribution of coupled processor models. J. SIAM Appl. Math. 48(5), 1159–1166(1988)
[16] Hunter, J.J.: Mathematical techniques of applied probability. Academic Press, New York (1983)
[17] Jiang, T., Liu, L., Ye, Q., Chai, X.: Tail asymptotics for service systems with transfers of customers in an alternating environment. Oper. Res. Lett. 47(6), 473–477(2019)
[18] Kim, B., Sohraby, K.: Tail behavior of the queue size and waiting time in a queue with discrete autoregressive arrivals. Adv. Appl. Probab. 38(4), 1116–1131(2006)
[19] 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. Model. 23(3), 413–438(2007)
[20] Li, H., Zhao, Y.Q.: Exact tail asymptotics in a priority queue-characterizations of the preemptive model. Queueing Syst. 63(1–4), 355–381(2009)
[21] Li, H., Zhao, Y.Q.: Exact tail asymptotics in a priority queue-characterizations of the non-preemptive model. Queueing Syst. 68(2), 165–192(2011)
[22] Li, H., Zhao, Y.Q.: Tail asymptotics for a generalized two-demand queueing model-a kernel method. Queueing Syst. 69(1), 77–100(2011)
[23] Liu, B., Zhao, Y.Q.: Tail asymptotics for the M1, M2/G1, G2/1 retrial queue with non-preemptive priority. Queueing Syst. 96(1–2), 169–199(2020)
[24] Liu, B., Min, J., Zhao, Y.Q.: Refined tail asymptotic properties for the MX /G/1 retrial queue. Queueing Syst. 104(1), 65–105(2023)
[25] Miller, D.G.: Computation of steady-state probabilities for M/M/1 priority queue. Oper. Res. 29(5), 945–958(1981)
[26] 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(2), 522–544(2006)
[27] Selen, J., Adan, I.J., Van Leeuwaarden, J.S.: Product-form solutions for a class of structured multidimensional Markov processes. SIAM J. Appl. Math. 74(3), 844–863(2014)
[28] Shi, D.H., Guo, J.L., Liu, L.M.: SPH-distributions and the rectangle-iterative algorithm. In: Chakravarthy, B.R., Alfa, A.S. (eds.) Matrix-analysis methods in stochastic models, pp. 207–224. Marcel Decker, New York (1996)
[29] Song, Y., Liu, Z.M., Dai, H.S.: Exact tail asymptotics for a discrete-time preemptive priority queue. Acta Math. Appl. Sin. 31(1), 43–58(2015)
[30] Song, Y., Liu, Z., Zhao, Y.Q.: Exact tail asymptotics: revisit of a retrial queue with two input streams and two orbits. Ann. Oper. Res. 247(1), 97–120(2016)
[31] 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. Model. 17(1), 1–24(2001)
[32] Tang, J., Zhao, Y.Q.: Stationary tail asymptotics of a tandem queue with feedback. Ann. Oper. Res. 160(1), 173–189(2008)
[33] Walraevens, J., Claeys, D., Phung-Duc, T.: Asymptotics of queue length distributions in priority retrial queues. Perform. Eval. 127–128, 235–252(2018)
[34] White, H., Christie, L.: Queueing with preemptive priorities or with breakdown. Oper. Res. 6(1), 79–95(1958)
[35] Zhang, H.B., Hou, Z.T., Shi, D.H.: Analysis of stationary queue length distribution for Geo/T-IPH/1 queue. J. Oper. Res. Soc. China 1(3), 415–424(2013)
[36] Zhang, H.B., Hou, Z.T.: Some properties of T-IPH distribution, with applications to queueing systems(in chinese). Chin. J. Appl. Probab. Statist. 31(2), 193–198(2015)
[37] Zhang, H.B., Shi, D.H., Hou, Z.T.: Analysis for stationary indices of discrete-time T-IPH/Geo/1 queue. J. Appl. Math. Comput. 47(1–2), 417–428(2015)