Abstract
This paper studies the subexponential asymptotics of the stationary distribution vector of an asymptotically block-Toeplitz and upper block-Hessenberg (atUBH) Markov chain in discrete time. The atUBH Markov chain is a kind of the upper block-Hessenberg (UBH) one and is a generalization of the M/G/1-type one. The atUBH Markov chain typically arises from semi-Markovian retrial queues, as the queue-length process, its embedded process, or appropriately time-scaled versions of these processes. In this paper, we present subexponential and locally subexponential asymptotic formulas for the stationary distribution vector. We then extend the locally subexponential asymptotic formula to a continuous-time version of the atUBH Markov chain by uniformization and change of time scale. This extension expands the applicability of the locally subexponential asymptotic formula.
Similar content being viewed by others
References
Neuts, M.F.: Structured Stochastic Matrices of M/G/1 Type and Their Applications. Marcel Dekker, New York (1989)
He, Q.-M.: Fundamentals of Matrix-Analytic Methods. Springer, New York (2014)
Masuyama, H.: A new matrix-infinite-product-form solution for upper block-Hessenberg Markov chains and its quasi-algorithmic constructibility. To appear in Advances in Applied Probability 55(1), March 2023 (arXiv:1904.11199v6) (2023)
Masuyama, H.: A sequential update algorithm for computing the stationary distribution vector in upper block-Hessenberg Markov chains. Queueing Syst. 92(1–2), 173–200 (2019)
Kimura, M., Takine, T.: Computing the conditional stationary distribution in Markov chains of level-dependent M/G/1-type. Stoch. Models 34(2), 207–238 (2018)
Klimenok, V., Dudin, A.: Multi-dimensional asymptotically quasi-Toeplitz Markov chains and their application in queueing theory. Queueing Syst. 54(4), 245–259 (2006)
Li, Q.-L., Lian, Z., Liu, L.: An \(RG\)-factorization approach for a BMAP/M/1 generalized processor-sharing queue. Stoch. Models 21(2–3), 507–530 (2005)
Shin, Y.W., Pearce, C.E.M.: An algorithmic approach to the Markov chain with transition probability matrix of upper block-Hessenberg form. Korean J. Comput. Appl. Math. 5(2), 361–384 (1998)
Takine, T.: Analysis and computation of the stationary distribution in a special class of Markov chains of level-dependent M/G/1-type and its application to BMAP/M/\(\infty \) and BMAP/M/\(c+\)M queues. Queueing Syst. 84(1–2), 49–77 (2016)
Kim, B., Kim, J., Kim, J.: Tail asymptotics for the queue size distribution in the MAP/G/1 retrial queue. Queueing Syst. 66(1), 79–94 (2010)
Shang, W., Liu, L., Li, Q.-L.: Tail asymptotics for the queue length in an M/G/1 retrial queue. Queueing Syst. 52(3), 193–198 (2006)
Yamamuro, K.: The queue length in an M/G/1 batch arrival retrial queue. Queueing Syst. 70(2), 187–205 (2012)
Falkenberg, E.: On the asymptotic behaviour of the stationary distribution of Markov chains of M/G/1-type. Stoch. Models 10(1), 75–97 (1994)
Gail, H.R., Hantler, S.L., Taylor, B.A.: Use of characteristic roots for solving infinite state Markov chains. In: Grassmann, W.K. (ed.) Comput. Probab., pp. 205–255. Springer, Boston, MA (2000)
Møller, J.R.: Tail asymptotics for M/G/1-type queueing processes with light-tailed increments. Operations Res. Lett. 28(4), 181–185 (2001)
Takine, T.: Geometric and subexponential asymptotics of Markov chains of M/G/1 type. Math. Operations Res. 29(3), 624–648 (2004)
Kimura, T., Daikoku, K., Masuyama, H., Takahashi, Y.: Light-tailed asymptotics of stationary tail probability vectors of Markov chains of M/G/1 type. Stoch. Models 26(4), 505–548 (2010)
Asmussen, S., Møller, J.R.: Tail asymptotics for M/G/1 type queueing processes with subexponential increments. Queueing Syst. 33(1–3), 153–176 (1999)
Masuyama, H.: Subexponential asymptotics of the stationary distributions of M/G/1-type Markov chains. Eur. J. Operational Res. 213(3), 509–516 (2011)
Kim, B., Kim, J.: A note on the subexponential asymptotics of the stationary distribution of M/G/1 type Markov chains. Eur. J. Operational Res. 220(1), 132–134 (2012)
Li, Q.-L., Zhao, Y.Q.: Heavy-tailed asymptotics of stationary probability vectors of Markov chains of GI/G/1 type. Adv. Appl. Probab. 37(2), 482–509 (2005)
Li, Q.-L., Zhao, Y.Q.: Light-tailed asymptotics of stationary probability vectors of Markov chains of GI/G/1 type. Adv. Appl. Probab. 37(4), 1075–1093 (2005)
Kimura, T., Masuyama, H., Takahashi, Y.: Subexponential asymptotics of the stationary distributions of GI/G/1-type Markov chains. Stoch. Models 29(2), 190–239 (2013)
Masuyama, H.: A sufficient condition for the subexponential asymptotics of GI/G/1-type Markov chains with queueing applications. Ann. Operations Res. 247(1), 65–95 (2016)
Brémaud, P.: Markov Chains: Gibbs Fields, Monte Carlo Simulation and Queues, 2nd edn. Springer, New York (2020)
Zhao, Y.Q., Li, W., Braun, W.J.: Infinite block-structured transition matrices and their properties. Adv. Appl. Probab. 30(2), 365–384 (1998)
Asmussen, S.: Applied Probability and Queues, 2nd edn. Springer, New York (2003)
Takine, T.: Geometric and subexponential asymptotics of Markov chains of M/G/1 type. Technical Report #2003-005, Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, Kyoto, Japan (2003)
Foss, S., Korshunov, D., Zachary, S.: An Introduction to Heavy-Tailed and Subexponential Distributions, 2nd edn. Springer, New York (2013)
Jelenković, P.R., Lazar, A.A.: Subexponential asymptotics of a Markov-modulated random walk with queueing applications. J. Appl. Probab. 35(2), 325–347 (1998)
Acknowledgements
This research was supported in part by JSPS KAKENHI Grant Number JP21K11770.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendices
Appendix A: Proofs of lemmas
This section consists of three subsections, and they are devoted to the proofs of Lemmas 2.3, 3.2, and 3.4, respectively.
1.1 A.1 Proof of Lemma 2.3
First, after some preparation, we prove (2.17) and then (2.18). With these equations, we provide the proofs of (2.19)–(2.21).
To prove (2.17) (and thus the other three equations), we express \(\varvec{G}_n\) by using the powers of a submatrix of \(\varvec{P}\). Let \(\varvec{P}_n\), \(n\in {\mathbb {N}}\), denote a submatrix of \(\varvec{P}\) such that
Let \(\varvec{P}_n^{(m)}(k,\ell )\), \(k,\ell ,m \in {\mathbb {Z}}_+\), denote the \((k,\ell )\)-th block matrix of \((\varvec{P}_n)^m\) partitioned in the same way as \(\varvec{P}_n\). Since \(\varvec{P}_n\) contains the probabilities of transitions avoiding below level n, the elements of \((\varvec{P}_n)^m\) have the following probabilistic interpretation:
for \(k,\ell ,m \in {\mathbb {Z}}_+\) and \(i,j\in {\mathbb {M}}\). This interpretation and (2.3) yield
Substituting (A.2) into (2.4) leads to
Next, we express \(\varvec{G}\) in such a form as the expression (A.3) of \(\varvec{G}_n\). To this end, let
where the second equality is due to (A.1) and the condition (iii) of Assumption 2.1, and where the convergence of this limit is uniform over all the elements. It follows from (A.4) and (2.10) that
It also follows from the probabilistic interpretation of \(\varvec{G}\) (see the proof of Lemma 2.1) that
where \(\varvec{P}_{\infty }^{(m)}(k,\ell )\), \(k,\ell ,m \in {\mathbb {Z}}_+\), denotes the \((k,\ell )\)-th block matrix of \((\varvec{P}_{\infty })^m\).
We prove (2.17) based on the expressions (A.3) and (A.5) of \(\varvec{G}_n\) and \(\varvec{G}\). Since \(\varvec{P}_n\) is substochastic, so is \((\varvec{P}_n)^m\). Therefore, it follows from (A.4) and the dominated convergence theorem that
Furthermore, applying the dominated convergence theorem to (A.3) and then using (A.5), (A.6), and (1.2) (see Remark 2.1), we obtain
which shows that (2.17) holds.
Next, we prove (2.18). It follows from (2.1) and (2.5) that
Applying the dominated convergence theorem to this equation and then using (1.2), (2.13), and (2.17), we obtain
which shows that (2.18) holds.
We move on to the proof of (2.19). Equation (2.14) implies that there exists some \(d \in {\mathbb {N}}\) such that \(\Vert \varvec{\varPhi }^{d} \Vert _{\infty } < 1\), or equivalently,
Equation (2.18) yields \(\lim _{n\rightarrow \infty }(\varvec{\varPhi }_n)^{d}=\varvec{\varPhi }^{d}\). Therefore, there exists some \(\xi \in (0,1)\) and \(N:=N_{\xi } \in {\mathbb {N}}\) such that
Using (2.2), (A.7), and \(\varvec{\varPhi }_n\varvec{e} \le \varvec{e}\), we obtain
which leads to
Therefore, applying the dominated convergence theorem to (2.2) and then using (2.18) and (2.14), we have
which shows that (2.19) holds.
Finally, we provide the proof of (2.20) and (2.21). Since \(\sum _{\ell =0}^{\infty }\varvec{A}_n(\ell )\varvec{e} \le \varvec{e}\) for all \(n \in {\mathbb {Z}}_+\), it follows from (2.6), (2.7), and (A.8) that, for all \(n \in {\mathbb {Z}}_+\),
Combining this and the condition (ii) of Assumption 2.1 leads to
which shows that (2.21) holds. Furthermore, applying the dominated convergence theorem to (2.7) and then using (1.2), (2.17), and (2.19), we obtain
where the last equality is due to (2.15). The above equation shows that (2.20) holds. The proof has been completed.
1.2 A.2 Proof of Lemma 3.2
We provide the proof of (3.10) and omit those of (3.11) and (3.12) because we can prove the latter two in the same way as the first one.
The proof of (3.10) is as follows. Based on (2.11), we fix \(\varepsilon >0\) arbitrarily and \(m_{*}:= m_{*} (\varepsilon ) \in {\mathbb {Z}}_{\ge \tau }\) such that, for all \(m \in {\mathbb {Z}}_{\ge m_*}\),
where the size of \(\varvec{e}\) is equal to M. Recall here that \(\varvec{G}\) is stochastic and thus \(\varvec{G}^m \le \varvec{e}\varvec{e}^{\top }\) for all \(m \in \mathbb {Z_+}\). Using this inequality, (3.6), and \(Y \in {\mathcal {L}}\), we have
which leads to
In addition, since \(\{\overline{\varvec{A}}_n(k);k\in {\mathbb {Z}}_+\}\) is nonincreasing, we obtain
and
Substituting (A.9) into (A.11) divided by \({\mathbb {P}}(Y > k)\), we have
and
It follows from (A.12), (3.6), and \(Y \in {\mathcal {L}}\) that
Letting \(\varepsilon \downarrow 0\) in (A.13) yields
Substituting this into (A.10) results in (3.10).
1.3 A.3 Proof of Lemma 3.4
We provide the proof of (3.18) and omit those of (3.19) and (3.20) because we can prove the latter two in the same way as the first one (see Remark A.1).
To prove (3.18), we derive an inequality that estimates \(\left| \varvec{A}_n(k+i) - \varvec{A}_n(k)\right|\) for \(i=1,2,\dots ,\tau \) in terms of \({\mathbb {P}}(V=k)\), where \(\tau \) is the period of the single recurrent class of \(\varvec{G}\) (see Lemma 2.1). It follows from (3.15) that for any \(\varepsilon > 0\) there exists some \(K:=K_{\varepsilon } \in {\mathbb {Z}}_+\) such that, for all \(k \in {\mathbb {Z}}_{\ge K}\),
Remark A.1
The proofs of (3.19) and (3.20) require the following instead of (A.14):
which follows from (A.14) and (1.2).
In what follows, we prove (3.18) with the inequality (A.14). Fix \(n \in {\mathbb {Z}}_+\) and \(\varepsilon > 0\) arbitrarily. Fix \(K \in {\mathbb {Z}}_+\) such that (A.14) holds for all \(k \in {\mathbb {Z}}_{\ge K}\). Furthermore, fix \(m_{*} \in {\mathbb {Z}}_{\ge \tau }\) such that (A.9) holds for all \(m \in {\mathbb {Z}}_{\ge m_*}\). It then follows from \(\varvec{G} \le \varvec{e}\varvec{e}^{\top } \), (3.16), and \(V \in {\mathcal {L}}\) that
and thus
Using (A.14), we obtain
Substituting (A.9) into (A.16) divided by \({\mathbb {P}}(V > k)\) and then noting that the size of \(\varvec{e}\) in (A.9) is equal to M, we have
It follows from (A.17), (3.16), and \(V \in {\mathcal {L}}\) that
Letting \(\varepsilon \downarrow 0\) in (A.18) yields
Following the above argument, we can obtain
Combining these results leads to
Substituting this into (A.15) and then using \({\mathbb {P}}(V_\mathrm{de} = k) = {\mathbb {P}}(V > k)/{\mathbb {E}}[V]\), we obtain (3.18).
Appendix B: Proof of Theorem 3.1
This section consists of two subsections: Section B.1 contains the main body of the proof of Theorem 3.1; Section B.2 provides those of the lemmas for this theorem.
1.1 B.1 Main body of the proof
We first present upper and lower bounds for the R-matrix \(\varvec{R}_n(k)\) of the atUBH Markov chain. Using them, we derive upper and lower bounds for the stationary distribution vector \(\varvec{\pi }\) together with the convolution forms of the bounds. We then present tail asymptotic results on the components of the convolution forms. Finally, with these preliminary results, we complete the proof of Theorem 3.1.
The following lemma presents upper and lower bounds for \(\varvec{R}_n(k)\).
Lemma B.1
Suppose that Assumptions 2.1 and 3.1 are satisfied. For any \(\varepsilon \in (0,1)\), there then exists some \(n_0:=n_0(\varepsilon ) \in {\mathbb {Z}}_+\) such that \(\lim _{\varepsilon \rightarrow \infty }n_0(\varepsilon ) = \infty \) and the following holds:
where
and
Proof
See Appendix B.2.1. \(\square \)
The upper and lower bounds for \(\varvec{R}_n(k)\) in Lemma B.1 enable us to derive those for \(\varvec{\pi }\), but we need some definitions to describe the derivation. In what follows, unless otherwise stated, fix \(\varepsilon \in (0,1)\) arbitrarily and fix \(n_0=n_0(\varepsilon ) \in {\mathbb {Z}}_+\) such that \(\lim _{\varepsilon \rightarrow \infty }n_0(\varepsilon ) = \infty \) and (B.1) holds. Let \(\varvec{\pi }_{[0,n_0]}\) denote a \(1 \times (M_0 + n_0 M)\) vector such that
Furthermore, let \(\varvec{R}_{[0,n_0]}(k)\), \(k\in {\mathbb {Z}}_+\), denote an \((M_0 + n_0 M) \times M\) matrix such that
We then define \(\varvec{\pi }_{\varepsilon }^+:=(\varvec{\pi }_{\varepsilon }^+(0),\varvec{\pi }_{\varepsilon }^+(1),\dots )\) and \(\varvec{\pi }_{\varepsilon }^-:=(\varvec{\pi }_{\varepsilon }^-(0),\varvec{\pi }_{\varepsilon }^-(1),\dots )\) as nonnegative vectors such that
where combining these equations with (B.2a), (B.3a), and (B.6a) yields
The upper and lower bounds for \(\varvec{\pi }\) are given in the following.
Lemma B.2
If Assumptions 2.1 and 3.1 are satisfied, then
where the matrix sequences \(\{(\varvec{R}_{\varepsilon }^+)^{*m}(k);k\in {\mathbb {Z}}_+\}\) and \(\{(\varvec{R}_{\varepsilon }^-)^{*m}(k);k\in {\mathbb {Z}}_+\}\) are the m-fold convolutions of \(\{\varvec{R}_{\varepsilon }^+(k);k\in {\mathbb {Z}}_+\}\) and \(\{\varvec{R}_{\varepsilon }^-(k);k\in {\mathbb {Z}}_+\}\), respectively.
Proof
See Appendix B.2.2. \(\square \)
Lemmas B.3 and B.4 present the tail asymptotic results on the components of the upper and lower bounds for \(\varvec{\pi }\).
Lemma B.3
Suppose that Assumptions 2.1, 3.1, and 3.2 are satisfied. If \(Y \in {\mathcal {L}}\), then
Proof
See Appendix B.2.3.\(\square \)
Lemma B.4
Suppose that Assumptions 2.1, 3.1, and 3.2 are satisfied. If \(Y \in {\mathcal {L}}\), then, for any \(\varepsilon > 0\),
Proof
See Appendix B.2.4. \(\square \)
We are now ready to prove Theorem 3.1. Applying Proposition D.2 (i) to (B.11) of Lemma B.2 yields
Using (B.5), (B.6), and Lemma B.3, we rewrite the terms involved with \(\varvec{\pi }_{[0,n_0]}\):
With (B.2), we also rewrite the term \(\sum _{\ell =0}^{\infty } \sum _{m=0}^{\infty } (\varvec{R}_{\varepsilon }^+)^{*m}(\ell )\) of (B.16) as
where \(\varvec{R} = \sum _{\ell =1}^{\infty } \varvec{R}(\ell ) \ge \varvec{O}\) and \(\varvec{S}_{\varepsilon }=\sum _{\ell =1}^{\infty }\varvec{S}_{\varepsilon }(\ell ) \ge \varvec{O}\). Note that the spectral radius of \(\varvec{R}\) is less than one (see Lemma 2.2 (i)). Thus, fix \(\varepsilon > 0\) sufficiently small such that the spectral radius of \(\varvec{R} + \varepsilon \varvec{S}_{\varepsilon }\) is less than one. We then have
Furthermore, from (B.19), Lemma B.4, and Proposition D.1 (i), we obtain
Substituting (B.17)–(B.20) into (B.16) yields
Recall here that \(\varvec{\pi }(n) > \varvec{0}\) for all \(n \in {\mathbb {Z}}_+\) and that \(\sup _{n\in {\mathbb {Z}}_+}\varvec{c}_n^{\mathrm{A}} < \infty \) and \(\varvec{c}_n^\mathrm{A} \ne \varvec{0}\) for some \(n\in {\mathbb {N}}\) (see Assumption 3.2). Therefore,
Furthermore, letting \(\varepsilon \downarrow 0\) in (B.21) and then using (2.16) and \(\lim _{\varepsilon \downarrow 0}n_0(\varepsilon ) = \infty \) (see Lemma B.1), we have
From (2.21) and \(\sum _{n=0}^{\infty } \varvec{\pi }(n) \varvec{e}=1\), we obtain
Therefore, using the dominated convergence theorem, we have
Substituting this into (B.23) yields
Similarly, we can show that
Combining (B.10) with (B.24) and (B.25) and then using \(Y \in {\mathcal {S}}\subset {\mathcal {L}}\), we have
which shows that (3.13) holds. Finally, it follows (B.22) and \(\varvec{\varpi } > \varvec{0}\) that the right-hand side of (3.13) is finite and positive. The proof of Theorem 3.1 has been completed.
1.2 B.2 Proofs of the lemmas for Theorem 3.1
This subsection provides the proofs of Lemmas B.1–B.4 for Theorem 3.1 in Sections B.2.1–B.2.4, respectively.
1.2.1 B.2.1 Proof of Lemma B.1
Lemma 2.3 yields
where the convergence is uniform over \((k,m) \in {\mathbb {N}}\times \mathbb {Z_+}\). It thus follows from (2.7) and (B.26) that for any \(\varepsilon \in (0,1)\) there exists some \(n_1:=n_1(\varepsilon ) \in {\mathbb {N}}\) such that \(\lim _{\varepsilon \downarrow 0} n_1(\varepsilon ) = \infty \) and, for all \(n \in {\mathbb {Z}}_{\ge n_1}\),
It also follows from (3.3) and (3.5) that for any \(\varepsilon \in (0,1)\) there exists some integer \(n_0:=n_0(\varepsilon ) \ge n_1\) such that, for all \(n \in {\mathbb {Z}}_{\ge n_0}\),
Applying (B.28) to (B.27) and then using (2.15) and (B.4), we obtain the following: For all \(n \in {\mathbb {Z}}_{\ge n_0}\) and \(k \in {\mathbb {N}}\),
and, similarly,
Finally, we have \(\lim _{\varepsilon \downarrow 0} n_0(\varepsilon ) \ge \lim _{\varepsilon \downarrow 0} n_1(\varepsilon ) = \infty \).
1.2.2 B.2.2 Proof of Lemma B.2
We can readily obtain the convolution forms (B.11) and (B.12) from (B.7) and (B.8), respectively, proceeding as in the proof of Theorem 1 in [16]. Thus, we prove by induction the upper and lower bounds (B.10) for \(\varvec{\pi }(k+n_0)\). Recall that (see (B.2a), (B.3a), and (B.9)),
Therefore, combining (B.7) and (B.8) with (B.6) leads to
These equations, together with (2.8), yield
which shows that (B.10) holds for \(k=1\). As the inductive assumption, suppose that (B.10) holds for \(k=k_*\), that is,
where \(k_*\) is some positive integer. Applying the left inequality in (B.30) to (B.29) with \(k=k_{*}+1\) and then using (B.1) with \(n=\ell +n_0\), we obtain
where the last equality is due to (2.8). Similarly, we can show that
As a result, (B.10) has been proved.
1.2.3 B.2.3 Proof of Lemma B.3
To prove (B.13), it suffices to show that
due to (B.6) and \(Y \in {\mathcal {L}}\).
In what follows, we provide the proof of (B.31). Lemma 2.3 implies that, for \((m,n) \in ({\mathbb {Z}}_+)^2\),
where the convergence is uniform over \((m,n) \in ({\mathbb {Z}}_+)^2\). Therefore, for any fixed \(\delta > 0\) (independently of n), the following inequalities hold for all sufficiently large k:
Applying this inequality to (2.7), we obtain, for all sufficiently large k,
From (B.32a), we have
Applying (3.6) and (3.10) to (B.33), we obtain
Similarly, we have
Letting \(\delta \downarrow 0\) in (B.34) and (B.35) leads to (B.31).
1.2.4 B.2.4 Proof of Lemma B.4
It follows from (2.15) and (B.4) that
Applying (3.11) to (B.36) yields
Furthermore, applying (3.7), (3.8), and (3.12) to (B.37) yields
Therefore, we have
Combining these with (B.2) and (B.3) leads to (B.14) and (B.15), respectively.
Appendix C: Proof of Theorem 3.2
This section outlines the proof of Theorem 3.2, which proceeds as in that of Theorem 3.1. However, instead of Lemmas B.3 and B.4 for Theorem 3.1, we require Lemmas C.1 and C.2.
Lemma C.1
Suppose that Assumptions 2.1, 3.1, and 3.3 are satisfied. If \(V_\mathrm{de} \in {\mathcal {L}}_{[1]}\) (or equivalently, \(V \in {\mathcal {L}}\)), then
Proof
To prove (C.1), it suffices to show that
Fix \(\delta > 0\) arbitrarily and independently of n. Recall that (B.32) holds for all sufficiently large k. Applying (3.16) and (3.18) to (B.32), we obtain
Letting \(\delta \downarrow 0\) in the above inequalities, we have (C.2). \(\square \)
Lemma C.2
Suppose that Assumptions 2.1, 3.1, and 3.3 are satisfied. If \(V_\mathrm{de} \in {\mathcal {L}}_{[1]}\), then, for any \(\varepsilon > 0\),
Proof
As in the proof of Lemma B.4, we can readily prove Lemma C.2, though we use Assumption 3.3 and Lemmas 3.3 and 3.4 instead of Assumption 3.2 and Lemmas 3.1 and 3.2, respectively. The details are omitted. \(\square \)
Using Lemmas C.1, C.2, and B.2, and proceeding as in the proof of Theorem 3.1 (see Appendix B), we can show that Theorem 3.2 holds. To save space, we omit the details.
Appendix D: Convolution of matrix sequences with subexponential tails
The following are fundamental results on the asymptotics of the convolution of matrix sequences associated with subexponential tails.
Proposition D.1
Suppose that \(\{\varvec{M}(k);k\in {\mathbb {Z}}_+\}\) is a sequence of finite-dimensional nonnegative square matrices such that \(\varvec{M}:= \sum _{k=0}^{\infty }\varvec{M}(k) < \infty \) and \(\sum _{n=0}^{\infty }\varvec{M}^n = (\varvec{I} - \varvec{M})^{-1} < \infty \).
-
(i)
If there exist some \(U \in {\mathcal {S}}\) and nonnegative matrix \(\widetilde{\varvec{M}} < \infty \) such that
$$\begin{aligned} \limsup _{k\rightarrow \infty }{\overline{\varvec{M}}(k) \over {\mathbb {P}}(U>k)} \le \widetilde{\varvec{M}}, \end{aligned}$$then
$$\begin{aligned} \limsup _{k\rightarrow \infty } {\overline{\sum _{n=0}^{\infty }\varvec{M}^{*n}}(k) \over {\mathbb {P}}(U>k)} \le (\varvec{I} - \varvec{M})^{-1}\widetilde{\varvec{M}} (\varvec{I} - \varvec{M})^{-1}. \end{aligned}$$In addition, if there exist some \(U \in {\mathcal {S}}_{[1]}\) and nonnegative matrix \(\widetilde{\varvec{M}}' < \infty \) such that
$$\begin{aligned} \limsup _{k\rightarrow \infty }{\varvec{M}(k) \over {\mathbb {P}}(U=k)} \le \widetilde{\varvec{M}}', \end{aligned}$$then
$$\begin{aligned} \limsup _{k\rightarrow \infty } {\sum _{n=0}^{\infty }\varvec{M}^{*n}(k) \over {\mathbb {P}}(U = k)} \le (\varvec{I} - \varvec{M})^{-1}\widetilde{\varvec{M}}' (\varvec{I} - \varvec{M})^{-1}. \end{aligned}$$ -
(ii)
Even replacing “\(\displaystyle \limsup _{k\rightarrow \infty }\)" and “\(\le \)" with “\(\displaystyle \liminf _{k\rightarrow \infty }\)" and “\(\ge \)", respectively, in the statement (i), we have a true statement.
-
(iii)
Even replacing “\(\displaystyle \limsup _{k\rightarrow \infty }\)" and “\(\le \)" with “\(\displaystyle \lim _{k\rightarrow \infty }\)" and “\(=\)", respectively, in the statement (i), we have a true statement.
Remark D.1
Proposition D.1 is a straightforward extension of the combination of [30, Lemma 6] and [23, Proposition A.2.6].
Proposition D.2
Suppose that \(\{\varvec{M}(k);k\in {\mathbb {Z}}_+\}\) and \(\{\varvec{N}(k);k\in {\mathbb {Z}}_+\}\) are finite-dimensional nonnegative matrix sequences such that their convolution \(\varvec{M} * \varvec{N}(k)\) is well-defined. Furthermore, suppose that \(\varvec{M}:= \sum _{k=0}^{\infty }\varvec{M}(k) < \infty \) and \(\varvec{N}:= \sum _{k=0}^{\infty }\varvec{N}(k) < \infty \). Under these conditions, the following hold:
-
(i)
If there exist some \(U \in {\mathcal {S}}\) and nonnegative matrices \(\widetilde{\varvec{M}} < \infty \) and \(\widetilde{\varvec{N}} < \infty \) such that
$$\begin{aligned} \limsup _{k\rightarrow \infty }{\overline{\varvec{M}}(k) \over {\mathbb {P}}(U> k)} \le \widetilde{\varvec{M}}, \qquad \limsup _{k\rightarrow \infty }{\overline{\varvec{N}}(k) \over {\mathbb {P}}(U > k)} \le \widetilde{\varvec{N}}, \end{aligned}$$then
$$\begin{aligned} \limsup _{k\rightarrow \infty } {\overline{\varvec{M} *\varvec{N}}(k) \over {\mathbb {P}}(U > k)} \le \widetilde{\varvec{M}} \varvec{N} + \varvec{M} \widetilde{\varvec{N}}. \end{aligned}$$In addition, if there exist some \(U \in {\mathcal {S}}_{[1]}\) and nonnegative matrices \(\widetilde{\varvec{M}}' < \infty \) and \(\widetilde{\varvec{N}}' < \infty \) such that
$$\begin{aligned} \limsup _{k\rightarrow \infty }{\varvec{M}(k) \over {\mathbb {P}}(U = k)} \le \widetilde{\varvec{M}}', \qquad \limsup _{k\rightarrow \infty }{\varvec{N}(k) \over {\mathbb {P}}(U = k)} \le \widetilde{\varvec{N}}', \end{aligned}$$then
$$\begin{aligned} \limsup _{k\rightarrow \infty } {\varvec{M} *\varvec{N}(k) \over {\mathbb {P}}(U = k)} \le \widetilde{\varvec{M}}' \varvec{N} + \varvec{M} \widetilde{\varvec{N}}'. \end{aligned}$$ -
(ii)
Even replacing “\(\displaystyle \limsup _{k\rightarrow \infty }\)" and “\(\le \)" with “\(\displaystyle \liminf _{k\rightarrow \infty }\)" and “\(\ge \)", respectively, in the statement (i), we have a true statement.
-
(iii)
Even replacing “\(\displaystyle \limsup _{k\rightarrow \infty }\)" and “\(\le \)" with “\(\displaystyle \lim _{k\rightarrow \infty }\)" and “\(=\)", respectively, in the statement (i), we have a true statement.
Remark D.2
Proposition D.2 is a straightforward extension of the combination of [19, Proposition A.3] and [23, Proposition A.2.5].
Rights and permissions
Springer Nature or its licensor holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Masuyama, H. Subexponential asymptotics of asymptotically block-Toeplitz and upper block-Hessenberg Markov chains. Queueing Syst 102, 175–217 (2022). https://doi.org/10.1007/s11134-022-09857-5
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11134-022-09857-5
Keywords
- Subexponential asymptotics
- Upper block-Hessenberg (UBH) Markov chain
- Asymptotically block-Toeplitz structure
- Retrial queue
- Balking queue