Nothing Special   »   [go: up one dir, main page]

Skip to main content
Log in

Subexponential asymptotics of asymptotically block-Toeplitz and upper block-Hessenberg Markov chains

  • Published:
Queueing Systems Aims and scope Submit manuscript

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.

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

Access this article

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. Neuts, M.F.: Structured Stochastic Matrices of M/G/1 Type and Their Applications. Marcel Dekker, New York (1989)

    Google Scholar 

  2. He, Q.-M.: Fundamentals of Matrix-Analytic Methods. Springer, New York (2014)

    Book  Google Scholar 

  3. 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)

  4. 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)

    Article  Google Scholar 

  5. 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)

    Article  Google Scholar 

  6. Klimenok, V., Dudin, A.: Multi-dimensional asymptotically quasi-Toeplitz Markov chains and their application in queueing theory. Queueing Syst. 54(4), 245–259 (2006)

    Article  Google Scholar 

  7. 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)

    Article  Google Scholar 

  8. 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)

    Article  Google Scholar 

  9. 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)

    Article  Google Scholar 

  10. 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)

    Article  Google Scholar 

  11. 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)

    Article  Google Scholar 

  12. Yamamuro, K.: The queue length in an M/G/1 batch arrival retrial queue. Queueing Syst. 70(2), 187–205 (2012)

    Article  Google Scholar 

  13. 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)

    Article  Google Scholar 

  14. 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)

    Chapter  Google Scholar 

  15. 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)

    Article  Google Scholar 

  16. Takine, T.: Geometric and subexponential asymptotics of Markov chains of M/G/1 type. Math. Operations Res. 29(3), 624–648 (2004)

    Article  Google Scholar 

  17. 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)

    Article  Google Scholar 

  18. 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)

    Article  Google Scholar 

  19. Masuyama, H.: Subexponential asymptotics of the stationary distributions of M/G/1-type Markov chains. Eur. J. Operational Res. 213(3), 509–516 (2011)

    Article  Google Scholar 

  20. 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)

    Article  Google Scholar 

  21. 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)

    Article  Google Scholar 

  22. 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)

    Article  Google Scholar 

  23. 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)

    Article  Google Scholar 

  24. 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)

    Article  Google Scholar 

  25. Brémaud, P.: Markov Chains: Gibbs Fields, Monte Carlo Simulation and Queues, 2nd edn. Springer, New York (2020)

    Book  Google Scholar 

  26. Zhao, Y.Q., Li, W., Braun, W.J.: Infinite block-structured transition matrices and their properties. Adv. Appl. Probab. 30(2), 365–384 (1998)

    Article  Google Scholar 

  27. Asmussen, S.: Applied Probability and Queues, 2nd edn. Springer, New York (2003)

    Google Scholar 

  28. 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)

  29. Foss, S., Korshunov, D., Zachary, S.: An Introduction to Heavy-Tailed and Subexponential Distributions, 2nd edn. Springer, New York (2013)

    Book  Google Scholar 

  30. 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)

    Article  Google Scholar 

Download references

Acknowledgements

This research was supported in part by JSPS KAKENHI Grant Number JP21K11770.

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Hiroyuki Masuyama.

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

(A.1)

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:

$$\begin{aligned} (\varvec{P}_n^{(m)}(k,\ell ))_{i,j} = {\mathbb {P}}(X_m=n+\ell , J_m =j, \theta _{n-1} > m \mid X_0&= n+k, J_0 = i), \end{aligned}$$

for \(k,\ell ,m \in {\mathbb {Z}}_+\) and \(i,j\in {\mathbb {M}}\). This interpretation and (2.3) yield

$$\begin{aligned} (\varvec{I} - \varvec{\varPhi }_n)^{-1} = \sum _{m=0}^{\infty } \varvec{P}_n^{(m)}(0,0). \end{aligned}$$
(A.2)

Substituting (A.2) into (2.4) leads to

$$\begin{aligned} \varvec{G}_n = \sum _{m=0}^{\infty }\varvec{P}_n^{(m)}(0,0)\varvec{A}_n(-1). \end{aligned}$$
(A.3)

Next, we express \(\varvec{G}\) in such a form as the expression (A.3) of \(\varvec{G}_n\). To this end, let

$$\begin{aligned} \varvec{P}_{\infty } = \left( \begin{array}{ccccc} \varvec{A}(0) &{} \varvec{A}(1) &{} \varvec{A}(2) &{} \varvec{A}(3) &{} \cdots \\ \varvec{A}(-1)&{} \varvec{A}(0) &{} \varvec{A}(1) &{} \varvec{A}(2) &{} \cdots \\ \varvec{O}&{} \varvec{A}(-1)&{} \varvec{A}(0) &{} \varvec{A}(1) &{} \cdots \\ \varvec{O} &{} \varvec{O} &{} \varvec{A}(-1)&{} \varvec{A}(0) &{} \cdots \\ \vdots &{} \vdots &{} \ddots &{} \ddots &{} \ddots \end{array} \right) = \lim _{n\rightarrow \infty }\varvec{P}_n, \end{aligned}$$
(A.4)

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

$$\begin{aligned} \varvec{P}_\mathrm{M/G/1} = \left( \begin{array}{c|cccc} \varvec{A}_0'(0) &{} \gamma \varvec{A}(1) &{} \gamma \varvec{A}(2) &{} \gamma \varvec{A}(3) &{} \cdots \\ \hline \varvec{A}(-1) &{} &{} &{} &{} \\ \varvec{O} &{} &{} &{} &{} \\ \varvec{O} &{} &{} \varvec{P}_{\infty } &{} &{} \\ \vdots &{} &{} &{} &{} \\ \end{array} \right) . \end{aligned}$$

It also follows from the probabilistic interpretation of \(\varvec{G}\) (see the proof of Lemma 2.1) that

$$\begin{aligned} \varvec{G} = \sum _{m=0}^{\infty }\varvec{P}_{\infty }^{(m)}(0,0)\varvec{A}(-1), \end{aligned}$$
(A.5)

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

$$\begin{aligned} \lim _{n\rightarrow \infty }\varvec{P}_n^{(m)}(k,\ell )&= \sum _{k_1,k_2,\dots ,k_{m-1} \in {\mathbb {Z}}_+} \lim _{n\rightarrow \infty } \varvec{P}_n(k,k_1) \varvec{P}_n(k_1,k_2) \cdots \varvec{P}_n(k_{m-1},\ell ) \nonumber \\&= \sum _{k_1,k_2,\dots ,k_{m-1} \in {\mathbb {Z}}_+} \varvec{P}_{\infty }(k,k_1) \varvec{P}_{\infty }(k_1,k_2) \cdots \varvec{P}_{\infty }(k_{m-1},\ell ) \nonumber \\&= \varvec{P}_{\infty }^{(m)}(k,\ell ), \qquad k,\ell ,m \in {\mathbb {Z}}_+. \end{aligned}$$
(A.6)

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

$$\begin{aligned} \lim _{n\rightarrow \infty } \varvec{G}_n = \sum _{m=0}^{\infty }\lim _{n\rightarrow \infty }\varvec{P}_n^{(m)}(0,0)\varvec{A}_n(-1) = \sum _{m=0}^{\infty }\varvec{P}_{\infty }^{(m)}(0,0)\varvec{A}(-1)=\varvec{G}, \end{aligned}$$

which shows that (2.17) holds.

Next, we prove (2.18). It follows from (2.1) and (2.5) that

$$\begin{aligned} \varvec{\varPhi }_n = \sum _{k=0}^{\infty }\varvec{A}_n(k) \prod _{\ell =n+1}^{n+k} \downarrow \varvec{G}_{\ell }. \end{aligned}$$

Applying the dominated convergence theorem to this equation and then using (1.2), (2.13), and (2.17), we obtain

$$\begin{aligned} \lim _{n\rightarrow \infty } \varvec{\varPhi }_n = \sum _{k=0}^{\infty } \lim _{n\rightarrow \infty }\varvec{A}_n(k) \prod _{\ell =n+1}^{n+k} \downarrow \varvec{G}_{\ell } = \sum _{k=0}^{\infty } \varvec{A}(k)\varvec{G}^k=\varvec{\varPhi }, \end{aligned}$$

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,

$$\begin{aligned} \varvec{\varPhi }^{d}\varvec{e} < \varvec{e}. \end{aligned}$$

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

$$\begin{aligned} (\varvec{\varPhi }_n)^{d} \varvec{e} < \xi \varvec{e}\quad \text{ for } \text{ all } n \in {\mathbb {Z}}_{\ge N}. \end{aligned}$$
(A.7)

Using (2.2), (A.7), and \(\varvec{\varPhi }_n\varvec{e} \le \varvec{e}\), we obtain

$$\begin{aligned} (\varvec{I} - \varvec{\varPhi }_n)^{-1}\varvec{e}&= \sum _{\ell =0}^{\infty } \sum _{\nu =0}^{d-1}(\varvec{\varPhi }_n)^{\ell d + \nu } \varvec{e} \\&\le d \sum _{\ell =0}^{\infty } (\varvec{\varPhi }_n)^{\ell d} \varvec{e} \le d \sum _{\ell =0}^{\infty } \xi ^{\ell } \varvec{e} = {d \over 1 - \xi }\varvec{e}~~ \quad \text{ for } \text{ all } n \in {\mathbb {Z}}_{\ge N}, \end{aligned}$$

which leads to

$$\begin{aligned} \sup _{n\in {\mathbb {Z}}_+} \left[ (\varvec{I} - \varvec{\varPhi }_n)^{-1} \varvec{e} \right] \le \psi \varvec{e}\quad \text{ for } \text{ some } \psi > 0. \end{aligned}$$
(A.8)

Therefore, applying the dominated convergence theorem to (2.2) and then using (2.18) and (2.14), we have

$$\begin{aligned} \lim _{n\rightarrow \infty } (\varvec{I} - \varvec{\varPhi }_n)^{-1} = \sum _{m=0}^{\infty }\lim _{n\rightarrow \infty }(\varvec{\varPhi }_n)^m = \sum _{m=0}^{\infty } \varvec{\varPhi }^m = (\varvec{I} - \varvec{\varPhi })^{-1}, \end{aligned}$$

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}}_+\),

$$\begin{aligned} \sum _{k=1}^{\infty } \varvec{R}_n(k) \varvec{e}&= \sum _{k=1}^{\infty } \sum _{m=0}^{\infty } \varvec{A}_n(k+m) \left( \prod _{\ell =n+k+1}^{n+k+m} \downarrow \varvec{G}_{\ell } \right) (\varvec{I} - \varvec{\varPhi }_{n+k})^{-1} \varvec{e} \\&\le \psi \sum _{k=1}^{\infty }\sum _{m=0}^{\infty }\varvec{A}_n(k+m)\varvec{e} \\&= \psi \sum _{\ell =1}^{\infty } \ell \varvec{A}_n(\ell ) \varvec{e}. \end{aligned}$$

Combining this and the condition (ii) of Assumption 2.1 leads to

$$\begin{aligned} \sup _{n \in {\mathbb {Z}}_+} \left\| \sum _{k=1}^{\infty } \varvec{R}_n(k) \right\| _{\infty } \le \psi \sup _{n \in {\mathbb {Z}}_+} \sum _{\ell =1}^{\infty } \ell \Vert \varvec{A}_n(\ell ) \Vert _{\infty } < \infty , \end{aligned}$$

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

$$\begin{aligned} \lim _{n\rightarrow \infty }\varvec{R}_n(k)= & {} \sum _{m=0}^{\infty }\lim _{n\rightarrow \infty }\varvec{A}_n(k+m) \left( \prod _{\ell =n+k+1}^{n+k+m} \downarrow \varvec{G}_{\ell } \right) (\varvec{I} - \varvec{\varPhi }_{n+k})^{-1} \\= & {} \sum _{m=0}^{\infty }\varvec{A}(k+m) \varvec{G}^m (\varvec{I} - \varvec{\varPhi })^{-1} = \varvec{R}(k), \end{aligned}$$

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_*}\),

$$\begin{aligned} \varvec{e}\left( \varvec{g} - {\varepsilon \varvec{e}^{\top } \over \tau } \right) \le {1 \over \tau } \sum _{\ell =0}^{\tau -1} \varvec{G}^{\lfloor m / \tau \rfloor \tau + \ell } \le \varvec{e}\left( \varvec{g} + {\varepsilon \varvec{e}^{\top } \over \tau } \right) , \end{aligned}$$
(A.9)

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

$$\begin{aligned}&\limsup _{k \rightarrow \infty } \sum _{m=0}^{m_{*}-1} { \overline{\varvec{A}}_n(k+m) \varvec{G}^m \over {\mathbb {P}}(Y> k) } \\&\quad \le \sum _{m=0}^{m_{*}-1} \limsup _{k \rightarrow \infty } { \overline{\overline{\varvec{A}}}_n(k+m-1)\varvec{e}\varvec{e}^{\top } - \overline{\overline{\varvec{A}}}_n(k+m)\varvec{e}\varvec{e}^{\top } \over {\mathbb {P}}(Y > k) } = \varvec{O}, \end{aligned}$$

which leads to

$$\begin{aligned} \lim _{k\rightarrow \infty } \sum _{m=0}^{\infty } { \overline{\varvec{A}}_n(k+m) \varvec{G}^m \over {\mathbb {P}}(Y> k) } = \lim _{k \rightarrow \infty } \sum _{m=m_{*}}^{\infty } { \overline{\varvec{A}}_n(k+m) \varvec{G}^m \over {\mathbb {P}}(Y > k) }. \end{aligned}$$
(A.10)

In addition, since \(\{\overline{\varvec{A}}_n(k);k\in {\mathbb {Z}}_+\}\) is nonincreasing, we obtain

$$\begin{aligned} \sum _{m=m_{*}}^{\infty } \overline{\varvec{A}}_n(k+m) \varvec{G}^m&\le \sum _{\nu =\lfloor m_{*}/\tau \rfloor }^{\infty } \sum _{\ell =0}^{\tau -1} \overline{\varvec{A}}_n(k + \nu \tau + \ell ) \varvec{G}^{\nu \tau + \ell } \nonumber \\&\le \sum _{\nu =\lfloor m_{*}/\tau \rfloor }^{\infty } \sum _{\ell =0}^{\tau -1} \left[ {1 \over \tau } \sum _{i=0}^{\tau -1} \overline{\varvec{A}}_n(k + \nu \tau - \tau + i) \right] \varvec{G}^{\nu \tau + \ell } \nonumber \\&= \sum _{\nu =\lfloor m_{*}/\tau \rfloor }^{\infty } \sum _{i=0}^{\tau -1} \overline{\varvec{A}}_n(k + \nu \tau - \tau + i) \cdot {1 \over \tau }\sum _{\ell =0}^{\tau -1} \varvec{G}^{\nu \tau + \ell }, \end{aligned}$$
(A.11a)

and

$$\begin{aligned} \sum _{m=m_{*}}^{\infty } \overline{\varvec{A}}_n(k+m) \varvec{G}^m&\ge \sum _{\nu =\lceil m_{*}/\tau \rceil }^{\infty } \sum _{\ell =0}^{\tau -1} \overline{\varvec{A}}_n(k + \nu \tau + \ell ) \varvec{G}^{\nu \tau + \ell } \nonumber \\&\ge \sum _{\nu =\lceil m_{*}/\tau \rceil }^{\infty } \sum _{\ell =0}^{\tau -1} \left[ {1 \over \tau } \sum _{i=0}^{\tau -1} \overline{\varvec{A}}_n(k + \nu \tau + \tau + i) \right] \varvec{G}^{\nu \tau + \ell } \nonumber \\&= \sum _{\nu =\lceil m_{*}/\tau \rceil }^{\infty } \sum _{i=0}^{\tau -1} \overline{\varvec{A}}_n(k + \nu \tau + \tau + i) \cdot {1 \over \tau }\sum _{\ell =0}^{\tau -1} \varvec{G}^{\nu \tau + \ell }. \end{aligned}$$
(A.11b)

Substituting (A.9) into (A.11) divided by \({\mathbb {P}}(Y > k)\), we have

$$\begin{aligned} \sum _{m=m_{*}}^{\infty } { \overline{\varvec{A}}_n(k+m) \varvec{G}^m \over {\mathbb {P}}(Y> k) }\le & {} \sum _{\nu =\lfloor m_{*}/\tau \rfloor }^{\infty } \sum _{i=0}^{\tau -1} { \overline{\varvec{A}}_n(k + \nu \tau - \tau + i) \varvec{e} \over {\mathbb {P}}(Y> k) } \left( \varvec{g} + {\varepsilon \varvec{e}^{\top } \over \tau } \right) \nonumber \\= & {} { \overline{\overline{\varvec{A}}}_n(k + \lfloor m_{*}/\tau \rfloor \tau - \tau - 1) \varvec{e} \over {\mathbb {P}}(Y > k) } \left( \varvec{g} + {\varepsilon \varvec{e}^{\top } \over \tau } \right) , \end{aligned}$$
(A.12a)

and

$$\begin{aligned} \sum _{m=m_{*}}^{\infty } { \overline{\varvec{A}}_n(k+m) \varvec{G}^m \over {\mathbb {P}}(Y> k) }\ge & {} \sum _{\nu =\lceil m_{*}/\tau \rceil }^{\infty } \sum _{i=0}^{\tau -1} { \overline{\varvec{A}}_n(k + \nu \tau + \tau + i) \varvec{e} \over {\mathbb {P}}(Y> k) } \left( \varvec{g} - {\varepsilon \varvec{e}^{\top } \over \tau } \right) \nonumber \\= & {} { \overline{\overline{\varvec{A}}}_n(k + \lceil m_{*}/\tau \rceil \tau + \tau -1) \varvec{e} \over {\mathbb {P}}(Y > k) } \left( \varvec{g} - {\varepsilon \varvec{e}^{\top } \over \tau } \right) . \end{aligned}$$
(A.12b)

It follows from (A.12), (3.6), and \(Y \in {\mathcal {L}}\) that

$$\begin{aligned} \limsup _{k \rightarrow \infty } \sum _{m=m_{*}}^{\infty } {\overline{\varvec{A}}_n(k+m) \varvec{G}^m \over {\mathbb {P}}(Y > k) }&\le \varvec{c}_n^\mathrm{A}\left( \varvec{g} + {\varepsilon \varvec{e}^{\top } \over \tau } \right) , \end{aligned}$$
(A.13a)
$$\begin{aligned} \liminf _{k \rightarrow \infty } \sum _{m=m_{*}}^{\infty } {\overline{\varvec{A}}_n(k+m) \varvec{G}^m \over {\mathbb {P}}(Y > k) }&\ge \varvec{c}_n^\mathrm{A}\left( \varvec{g} - {\varepsilon \varvec{e}^{\top } \over \tau } \right) . \end{aligned}$$
(A.13b)

Letting \(\varepsilon \downarrow 0\) in (A.13) yields

$$\begin{aligned} \lim _{k \rightarrow \infty } \sum _{m=m_{*}}^{\infty } {\overline{\varvec{A}}_n(k+m) \varvec{G}^m \over {\mathbb {P}}(Y > k) } = \varvec{c}_n^\mathrm{A} \varvec{g}. \end{aligned}$$

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}\),

$$\begin{aligned} \sup _{n\in {\mathbb {Z}}_+} \left| \varvec{A}_n(k+i) - \varvec{A}_n(k)\right| \le \varepsilon \varvec{e}\varvec{e}^{\top } {\mathbb {P}}(V=k),\qquad i=1, 2,\dots ,\tau . \end{aligned}$$
(A.14)

Remark A.1

The proofs of (3.19) and (3.20) require the following instead of (A.14):

$$\begin{aligned} \left| \varvec{A}(k+i) - \varvec{A}(k)\right|&\le \varepsilon \varvec{e}\varvec{e}^{\top } {\mathbb {P}}(V=k), \quad k \in {\mathbb {Z}}_{\ge K},~i=1, 2,\dots ,\tau . \end{aligned}$$

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

$$\begin{aligned}&\limsup _{k \rightarrow \infty } \sum _{m=0}^{m_{*}-1} { \varvec{A}_n(k+m) \varvec{G}^m \over {\mathbb {P}}(V> k) } \\&\quad \le \sum _{m=0}^{m_{*}-1} \limsup _{k \rightarrow \infty } { \overline{\varvec{A}}_n(k+m-1)\varvec{e}\varvec{e}^{\top } - \overline{\varvec{A}}_n(k+m)\varvec{e}\varvec{e}^{\top } \over {\mathbb {P}}(V > k) } = \varvec{O}, \end{aligned}$$

and thus

$$\begin{aligned} \lim _{k\rightarrow \infty } \sum _{m=0}^{\infty } { \varvec{A}_n(k+m) \varvec{G}^m \over {\mathbb {P}}(V> k) } = \lim _{k \rightarrow \infty } \sum _{m=m_{*}}^{\infty } { \varvec{A}_n(k+m) \varvec{G}^m \over {\mathbb {P}}(V > k) }. \end{aligned}$$
(A.15)

Using (A.14), we obtain

$$\begin{aligned} \sum _{m=m_{*}}^{\infty } \varvec{A}_n(k+m) \varvec{G}^m&\le \sum _{\nu =\lfloor m_{*}/\tau \rfloor }^{\infty } \sum _{\ell =0}^{\tau -1} \varvec{A}_n(k + \nu \tau + \ell ) \varvec{G}^{\nu \tau + \ell } \nonumber \\&\le \sum _{\nu =\lfloor m_{*}/\tau \rfloor }^{\infty } \varvec{A}_n(k + \nu \tau ) \sum _{\ell =0}^{\tau -1} \varvec{G}^{\nu \tau + \ell } \nonumber \\&{} \quad + \varepsilon \varvec{e}\varvec{e}^{\top } \sum _{\nu =\lfloor m_{*}/\tau \rfloor }^{\infty } {\mathbb {P}}(V = k + \nu \tau ) \sum _{\ell =0}^{\tau -1} \varvec{G}^{\nu \tau + \ell } \nonumber \\&\le \sum _{\nu =\lfloor m_{*}/\tau \rfloor }^{\infty } {1 \over \tau } \sum _{i=0}^{\tau -1} \varvec{A}_n(k + \nu \tau - i) \cdot \sum _{\ell =0}^{\tau -1} \varvec{G}^{\nu \tau + \ell } \nonumber \\&{} \quad + \varepsilon \varvec{e}\varvec{e}^{\top } \sum _{\nu =\lfloor m_{*}/\tau \rfloor }^{\infty } {1 \over \tau } \sum _{i=0}^{\tau -1} {\mathbb {P}}(V = k + \nu \tau - i) \sum _{\ell =0}^{\tau -1} \varvec{G}^{\nu \tau + \ell } \nonumber \\&{} \quad + \varepsilon \varvec{e}\varvec{e}^{\top } \sum _{\nu =\lfloor m_{*}/\tau \rfloor }^{\infty } {\mathbb {P}}(V = k + \nu \tau ) \sum _{\ell =0}^{\tau -1} \varvec{G}^{\nu \tau + \ell }. \end{aligned}$$
(A.16)

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

$$\begin{aligned} \sum _{m=m_{*}}^{\infty } { \varvec{A}_n(k+m) \varvec{G}^m \over {\mathbb {P}}(V> k) }&\le \sum _{\nu =\lfloor m_{*}/\tau \rfloor }^{\infty } \sum _{i=0}^{\tau -1} { \varvec{A}_n(k + \nu \tau - i) \varvec{e} \over {\mathbb {P}}(V> k) } \left( \varvec{g} + {\varepsilon \varvec{e}^{\top } \over \tau } \right) \nonumber \\&{}~~ + \varepsilon \varvec{e}\varvec{e}^{\top } \sum _{\nu =\lfloor m_{*}/\tau \rfloor }^{\infty } \sum _{i=0}^{\tau -1} {\mathbb {P}}(V = k + \nu \tau - i) \varvec{e}\left( \varvec{g} + {\varepsilon \varvec{e}^{\top } \over \tau } \right) \nonumber \\&{}~~ + \tau \varepsilon \varvec{e}\varvec{e}^{\top } \sum _{\nu =\lfloor m_{*}/\tau \rfloor }^{\infty } {\mathbb {P}}(V = k + \nu \tau ) \varvec{e}\left( \varvec{g} + {\varepsilon \varvec{e}^{\top } \over \tau } \right) \nonumber \\&\le { \overline{\varvec{A}}_n(k + \lfloor m_{*}/\tau \rfloor \tau - \tau ) \varvec{e} \over {\mathbb {P}}(V> k) } \left( \varvec{g} + {\varepsilon \varvec{e}^{\top } \over \tau } \right) , \nonumber \\&{}~~ + \varepsilon (\tau +1) M\varvec{e} {{\mathbb {P}}(V>k + \lfloor m_{*}/\tau \rfloor \tau - \tau ) \over {\mathbb {P}}(V > k)} \left( \varvec{g} + {\varepsilon \varvec{e}^{\top } \over \tau } \right) . \end{aligned}$$
(A.17)

It follows from (A.17), (3.16), and \(V \in {\mathcal {L}}\) that

$$\begin{aligned} \limsup _{k \rightarrow \infty } \sum _{m=m_{*}}^{\infty } {\varvec{A}_n(k+m) \varvec{G}^m \over {\mathbb {P}}(V > k) }&\le \left[ { \widetilde{\varvec{c}}_n^\mathrm{A} \over {\mathbb {E}}[V] } + \varepsilon (\tau +1) M\varvec{e} \right] \left( \varvec{g} + {\varepsilon \varvec{e}^{\top } \over \tau } \right) . \end{aligned}$$
(A.18)

Letting \(\varepsilon \downarrow 0\) in (A.18) yields

$$\begin{aligned} \limsup _{k \rightarrow \infty } \sum _{m=m_{*}}^{\infty } {\varvec{A}_n(k+m) \varvec{G}^m \over {\mathbb {P}}(V > k) } \le {\widetilde{\varvec{c}}_n^\mathrm{A} \varvec{g} \over {\mathbb {E}}[V] }. \end{aligned}$$

Following the above argument, we can obtain

$$\begin{aligned} \liminf _{k \rightarrow \infty } \sum _{m=m_{*}}^{\infty } {\varvec{A}_n(k+m) \varvec{G}^m \over {\mathbb {P}}(V > k) } \ge {\widetilde{\varvec{c}}_n^\mathrm{A} \varvec{g} \over {\mathbb {E}}[V] }. \end{aligned}$$

Combining these results leads to

$$\begin{aligned} \lim _{k \rightarrow \infty } \sum _{m=m_{*}}^{\infty } {\varvec{A}_n(k+m) \varvec{G}^m \over {\mathbb {P}}(V > k) } = {\widetilde{\varvec{c}}_n^\mathrm{A} \varvec{g} \over {\mathbb {E}}[V] }. \end{aligned}$$

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:

$$\begin{aligned} \varvec{R}_{\varepsilon }^-(k) \le \varvec{R}_n(k) \le \varvec{R}_{\varepsilon }^+(k) \quad \text{ for } \text{ all } n \in {\mathbb {Z}}_{\ge n_0} \text{ and } k \in {\mathbb {N}}, \end{aligned}$$
(B.1)

where

figure a
figure b

and

$$\begin{aligned} \varvec{S}_{\varepsilon }(k)&= \sum _{m=0}^{\infty }\varvec{\varDelta }(k+m) \varvec{G}^m (\varvec{I} - \varvec{\varPhi })^{-1} + \overline{\varvec{A}}(k) \varvec{e}\varvec{e}^{\top } + \varepsilon \overline{\varvec{\varDelta }}(k)\varvec{e}\varvec{e}^{\top }, \qquad k \in {\mathbb {N}}. \end{aligned}$$
(B.4)

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

$$\begin{aligned} \varvec{\pi }_{[0,n_0]}&= (\varvec{\pi }(0),\varvec{\pi }(1),\dots ,\varvec{\pi }(n_0)). \end{aligned}$$
(B.5)

Furthermore, let \(\varvec{R}_{[0,n_0]}(k)\), \(k\in {\mathbb {Z}}_+\), denote an \((M_0 + n_0 M) \times M\) matrix such that

$$\begin{aligned} \varvec{R}_{[0,n_0]}(0)&= \varvec{O}, \end{aligned}$$
(B.6a)
$$\begin{aligned} \varvec{R}_{[0,n_0]}(k)&= \left( \begin{array}{c} \varvec{R}_0(k+n_0) \\ \varvec{R}_1(k+n_0-1) \\ \vdots \\ \varvec{R}_{n_0}(k) \end{array} \right) , \qquad k \in {\mathbb {N}}. \end{aligned}$$
(B.6b)

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

$$\begin{aligned} \varvec{\pi }_{\varepsilon }^+(k)&= \varvec{\pi }_{[0,n_0]} \varvec{R}_{[0,n_0]}(k) + \varvec{\pi }_{\varepsilon }^+ * \varvec{R}_{\varepsilon }^+(k), \qquad k \in {\mathbb {Z}}_+, \end{aligned}$$
(B.7)
$$\begin{aligned} \varvec{\pi }_{\varepsilon }^-(k)&= \varvec{\pi }_{[0,n_0]} \varvec{R}_{[0,n_0]}(k) + \varvec{\pi }_{\varepsilon }^- * \varvec{R}_{\varepsilon }^-(k), \qquad k \in {\mathbb {Z}}_+, \end{aligned}$$
(B.8)

where combining these equations with (B.2a), (B.3a), and (B.6a) yields

$$\begin{aligned} \varvec{\pi }_{\varepsilon }^+(0) = \varvec{\pi }_{\varepsilon }^-(0) = \varvec{0}. \end{aligned}$$
(B.9)

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

$$\begin{aligned} \varvec{\pi }_{\varepsilon }^-(k)&\le \varvec{\pi }(k+n_0) \le \varvec{\pi }_{\varepsilon }^+(k), \qquad k \in {\mathbb {N}}, \end{aligned}$$
(B.10)
$$\begin{aligned} \varvec{\pi }_{\varepsilon }^+(k)&= \varvec{\pi }_{[0,n_0]} \varvec{R}_{[0,n_0]} *\sum _{m=0}^{\infty } (\varvec{R}_{\varepsilon }^+)^{*m}(k), \qquad k \in {\mathbb {N}}, \end{aligned}$$
(B.11)
$$\begin{aligned} \varvec{\pi }_{\varepsilon }^-(k)&= \varvec{\pi }_{[0,n_0]} \varvec{R}_{[0,n_0]} *\sum _{m=0}^{\infty } (\varvec{R}_{\varepsilon }^-)^{*m}(k), \qquad k \in {\mathbb {N}}, \end{aligned}$$
(B.12)

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

$$\begin{aligned} \lim _{k\rightarrow \infty }{\overline{\varvec{R}}_{[0,n_0]}(k) \over {\mathbb {P}}(Y > k)}&= \left( \begin{array}{c} \varvec{c}_0^{\mathrm{A}} \\ \varvec{c}_1^{\mathrm{A}} \\ \vdots \\ \varvec{c}_{n_0}^{\mathrm{A}} \end{array} \right) \varvec{g}(\varvec{I} - \varvec{\varPhi })^{-1}. \end{aligned}$$
(B.13)

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\),

$$\begin{aligned} \limsup _{k\rightarrow \infty }{\overline{\varvec{R}}_{\varepsilon }^+(k) \over {\mathbb {P}}(Y > k)}&\le (\varvec{c}_+^{\mathrm{A}} + \varepsilon \varvec{c}^{\varDelta }) \varvec{g}(\varvec{I} - \varvec{\varPhi })^{-1} + \varepsilon (\varvec{c}_+^{\mathrm{A}} + \varepsilon \varvec{c}^{\varDelta }) \varvec{e}^{\top }, \end{aligned}$$
(B.14)
$$\begin{aligned} \liminf _{k\rightarrow \infty }{\overline{\varvec{R}}_{\varepsilon }^-(k) \over {\mathbb {P}}(Y > k)}&\ge \left[ (\varvec{c}_-^{\mathrm{A}} - \varepsilon \varvec{c}^{\varDelta }) \varvec{g}(\varvec{I} - \varvec{\varPhi })^{-1} - \varepsilon (\varvec{c}_+^{\mathrm{A}} + \varepsilon \varvec{c}^{\varDelta })\varvec{e}^{\top } \right] _+. \end{aligned}$$
(B.15)

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

$$\begin{aligned} \limsup _{k\rightarrow \infty } {\overline{\varvec{\pi }}_{\varepsilon }^+(k) \over {\mathbb {P}}(Y> k)}&\le \varvec{\pi }_{[0,n_0]} \lim _{k\rightarrow \infty } {\overline{\varvec{R}}_{[0,n_0]}(k) \over {\mathbb {P}}(Y> k)} \cdot \sum _{\ell =0}^{\infty } \sum _{m=0}^{\infty } (\varvec{R}_{\varepsilon }^+)^{*m}(\ell ) \nonumber \\&\quad {} + \varvec{\pi }_{[0,n_0]} \sum _{\ell =1}^{\infty }\varvec{R}_{[0,n_0]}(\ell ) \cdot \limsup _{k\rightarrow \infty } { \sum _{m=0}^{\infty } \overline{(\varvec{R}_{\varepsilon }^+)^{*m}}(k) \over {\mathbb {P}}(Y > k) }. \end{aligned}$$
(B.16)

Using (B.5), (B.6), and Lemma B.3, we rewrite the terms involved with \(\varvec{\pi }_{[0,n_0]}\):

$$\begin{aligned} \varvec{\pi }_{[0,n_0]} \lim _{k\rightarrow \infty } {\overline{\varvec{R}}_{[0,n_0]}(k) \over {\mathbb {P}}(Y > k)}&= \sum _{n=0}^{n_0} \varvec{\pi }(n) \varvec{c}_n^{\mathrm{A}} \varvec{g}(\varvec{I} - \varvec{\varPhi })^{-1}, \end{aligned}$$
(B.17)
$$\begin{aligned} \varvec{\pi }_{[0,n_0]} \sum _{\ell =1}^{\infty } \varvec{R}_{[0,n_0]}(\ell )&= \sum _{n=0}^{n_0} \varvec{\pi }(n) \sum _{\ell =1}^{\infty } \varvec{R}_n(\ell + n_0 - n) \nonumber \\&= \sum _{n=0}^{n_0} \varvec{\pi }(n) \overline{\varvec{R}}_n(n_0 - n). \end{aligned}$$
(B.18)

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

$$\begin{aligned} \sum _{\ell =0}^{\infty } \sum _{m=0}^{\infty } (\varvec{R}_{\varepsilon }^+)^{*m}(\ell )&= \sum _{m=0}^{\infty } \left[ \sum _{\ell =1}^{\infty } \{\varvec{R}(\ell ) + \varepsilon \varvec{S}_{\varepsilon }(\ell ) \} \right] ^m = \sum _{m=0}^{\infty } ( \varvec{R} + \varepsilon \varvec{S}_{\varepsilon } )^m, \end{aligned}$$

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

$$\begin{aligned} \sum _{\ell =0}^{\infty } \sum _{m=0}^{\infty } (\varvec{R}_{\varepsilon }^+)^{*m}(\ell )&= (\varvec{I} - \varvec{R} - \varepsilon \varvec{S}_{\varepsilon } )^{-1}. \end{aligned}$$
(B.19)

Furthermore, from (B.19), Lemma B.4, and Proposition D.1 (i), we obtain

$$\begin{aligned} \limsup _{k\rightarrow \infty } { \sum _{m=0}^{\infty } \overline{(\varvec{R}_{\varepsilon }^+)^{*m}}(k) \over {\mathbb {P}}(Y > k) }&\le (\varvec{I} - \varvec{R} - \varepsilon \varvec{S}_{\varepsilon } )^{-1} \nonumber \\&\quad {} \times (\varvec{c}_+^{\mathrm{A}} + \varepsilon \varvec{c}^{\varDelta }) \left[ \varvec{g}(\varvec{I} - \varvec{\varPhi })^{-1} + \varepsilon \varvec{e}^{\top } \right] \nonumber \\&\quad {} \times (\varvec{I} - \varvec{R} - \varepsilon \varvec{S}_{\varepsilon } )^{-1}. \end{aligned}$$
(B.20)

Substituting (B.17)–(B.20) into (B.16) yields

$$\begin{aligned} \limsup _{k\rightarrow \infty } {\overline{\varvec{\pi }}_{\varepsilon }^+(k) \over {\mathbb {P}}(Y > k)}&\le \sum _{n=0}^{n_0} \varvec{\pi }(n)\varvec{c}_n^{\mathrm{A}} \varvec{g}(\varvec{I} - \varvec{\varPhi })^{-1} \cdot (\varvec{I} - \varvec{R} - \varepsilon \varvec{S}_{\varepsilon } )^{-1} \nonumber \\&\quad {} + \sum _{n=0}^{n_0} \varvec{\pi }(n) \overline{\varvec{R}}_n(n_0 - n) \cdot (\varvec{I} - \varvec{R} - \varepsilon \varvec{S}_{\varepsilon } )^{-1} (\varvec{c}_+^{\mathrm{A}} + \varepsilon \varvec{c}^{\varDelta }) \nonumber \\&\quad \quad {} \times \left[ \varvec{g}(\varvec{I} - \varvec{\varPhi })^{-1} + \varepsilon \varvec{e}^{\top } \right] (\varvec{I} - \varvec{R} - \varepsilon \varvec{S}_{\varepsilon } )^{-1}. \end{aligned}$$
(B.21)

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,

$$\begin{aligned} 0< \lim _{n_0\rightarrow \infty }\sum _{n=0}^{n_0} \varvec{\pi }(n)\varvec{c}_n^{\mathrm{A}} < \infty . \end{aligned}$$
(B.22)

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

$$\begin{aligned} \lim _{\varepsilon \downarrow 0} \limsup _{k\rightarrow \infty } {\overline{\varvec{\pi }}_{\varepsilon }^+(k) \over {\mathbb {P}}(Y > k)}&\le \sum _{n=0}^{\infty } \varvec{\pi }(n)\varvec{c}_n^{\mathrm{A}} \cdot {\varvec{\varpi } \over -\sigma } \nonumber \\&{} ~~ + \lim _{n_0\rightarrow \infty } \sum _{n=0}^{n_0} \varvec{\pi }(n) \overline{\varvec{R}}_n(n_0 - n) \cdot (\varvec{I} - \varvec{R})^{-1} \varvec{c}_+^{\mathrm{A}} {\varvec{\varpi } \over -\sigma }. \end{aligned}$$
(B.23)

From (2.21) and \(\sum _{n=0}^{\infty } \varvec{\pi }(n) \varvec{e}=1\), we obtain

$$\begin{aligned} \sum _{n=0}^{n_0} \varvec{\pi }(n) \overline{\varvec{R}}_n(n_0 - n) \varvec{e}&\le \sum _{n=0}^{\infty } \varvec{\pi }(n) \sum _{k=1}^{\infty } \varvec{R}_n(k)\varvec{e} \nonumber \\&\le \sum _{n=0}^{\infty } \varvec{\pi }(n) \varvec{e} \sup _{\nu \in {\mathbb {Z}}_+} \left\| \sum _{k=1}^{\infty } \varvec{R}_{\nu }(k) \right\| _{\infty } \nonumber \\&= \sup _{\nu \in {\mathbb {Z}}_+} \left\| \sum _{k=1}^{\infty } \varvec{R}_{\nu }(k) \right\| _{\infty } < \infty . \end{aligned}$$

Therefore, using the dominated convergence theorem, we have

$$\begin{aligned} \lim _{n_0\rightarrow \infty } \sum _{\ell =0}^{n_0} \varvec{\pi }(\ell )\overline{\varvec{R}}_{\ell }(n_0-\ell ) = \sum _{\ell =0}^{\infty } \varvec{\pi }(\ell ) \lim _{n_0\rightarrow \infty } \overline{\varvec{R}}_{\ell }(n_0-\ell ) = \varvec{0}. \end{aligned}$$

Substituting this into (B.23) yields

$$\begin{aligned} \lim _{\varepsilon \downarrow 0} \limsup _{k\rightarrow \infty } {\overline{\varvec{\pi }}_{\varepsilon }^+(k) \over {\mathbb {P}}(Y > k)}&\le \sum _{n=0}^{\infty }\varvec{\pi }(n) \varvec{c}_n^\mathrm{A} \cdot {\varvec{\varpi } \over -\sigma }. \end{aligned}$$
(B.24)

Similarly, we can show that

$$\begin{aligned} \lim _{\varepsilon \downarrow 0} \liminf _{k\rightarrow \infty } {\overline{\varvec{\pi }}_{\varepsilon }^+(k) \over {\mathbb {P}}(Y > k)}&\ge \sum _{n=0}^{\infty }\varvec{\pi }(n) \varvec{c}_n^\mathrm{A} \cdot {\varvec{\varpi } \over -\sigma }. \end{aligned}$$
(B.25)

Combining (B.10) with (B.24) and (B.25) and then using \(Y \in {\mathcal {S}}\subset {\mathcal {L}}\), we have

$$\begin{aligned} \lim _{k\rightarrow \infty } { \overline{\varvec{\pi }}(k) \over {\mathbb {P}}(Y > k) } = \sum _{n=0}^{\infty }\varvec{\pi }(n)\varvec{c}_n^\mathrm{A} \cdot {\varvec{\varpi } \over -\sigma }, \end{aligned}$$

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.1B.4 for Theorem 3.1 in Sections B.2.1B.2.4, respectively.

1.2.1 B.2.1 Proof of Lemma B.1

Lemma 2.3 yields

$$\begin{aligned} \lim _{n\rightarrow \infty }\left( \prod _{\ell =n+k+1}^{n+k+m} \downarrow \varvec{G}_{\ell } \right) (\varvec{I} - \varvec{\varPhi }_{n+k})^{-1} = \varvec{G}^m \left( \varvec{I} - \varvec{\varPhi } \right) ^{-1}, \quad k \in {\mathbb {N}},m \in \mathbb {Z_+,} \end{aligned}$$
(B.26)

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}\),

$$\begin{aligned} \varvec{R}_n(k)&\le \sum _{m=0}^{\infty } \varvec{A}_n(k+m) \left[ \varvec{G}^m \left( \varvec{I} - \varvec{\varPhi } \right) ^{-1} + \varepsilon \varvec{e}\varvec{e}^{\top } \right] , \qquad k \in {\mathbb {N}}, \end{aligned}$$
(B.27a)
$$\begin{aligned} \varvec{R}_n(k)&\ge \sum _{m=0}^{\infty } \varvec{A}_n(k+m) \left[ \varvec{G}^m \left( \varvec{I} - \varvec{\varPhi } \right) ^{-1} - \varepsilon \varvec{e}\varvec{e}^{\top } \right] , \qquad k \in {\mathbb {N}}. \end{aligned}$$
(B.27b)

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}\),

$$\begin{aligned} \varvec{A}(k) - \varepsilon \varvec{\varDelta }(k) \le \varvec{A}_n(k)\le & {} \varvec{A}(k) + \varepsilon \varvec{\varDelta }(k), \qquad k\in {\mathbb {Z}}_{\ge -1}. \end{aligned}$$
(B.28)

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}}\),

$$\begin{aligned} \varvec{R}_n(k)&\ge \sum _{m=0}^{\infty } \left( \varvec{A}(k+m) - \varepsilon \varvec{\varDelta }(k+m) \right) \left[ \varvec{G}^m \left( \varvec{I} - \varvec{\varPhi } \right) ^{-1} - \varepsilon \varvec{e}\varvec{e}^{\top } \right] \\&= \varvec{R}(k) - \varepsilon \Bigg [ \sum _{m=0}^{\infty }\varvec{\varDelta }(k+m) \varvec{G}^m (\varvec{I} - \varvec{\varPhi })^{-1} + \overline{\varvec{A}}(k) \varvec{e}\varvec{e}^{\top } - \varepsilon \overline{\varvec{\varDelta }}(k)\varvec{e}\varvec{e}^{\top } \Bigg ] \\&\ge \varvec{R}(k) - \varepsilon \Bigg [ \sum _{m=0}^{\infty }\varvec{\varDelta }(k+m) \varvec{G}^m (\varvec{I} - \varvec{\varPhi })^{-1} + \overline{\varvec{A}}(k) \varvec{e}\varvec{e}^{\top } + \varepsilon \overline{\varvec{\varDelta }}(k)\varvec{e}\varvec{e}^{\top } \Bigg ] \\&= \varvec{R}(k) - \varepsilon \varvec{S}_{\varepsilon }(k), \end{aligned}$$

and, similarly,

$$\begin{aligned} \varvec{R}_n(k)&\le \varvec{R}(k) + \varepsilon \varvec{S}_{\varepsilon }(k). \end{aligned}$$

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)),

$$\begin{aligned} \varvec{R}_{\varepsilon }^+(0)&=\varvec{R}_{\varepsilon }^-(0)=\varvec{O}, \qquad \varvec{\pi }_{\varepsilon }^+(0) =\varvec{\pi }_{\varepsilon }^-(0)=\varvec{0}. \end{aligned}$$

Therefore, combining (B.7) and (B.8) with (B.6) leads to

$$\begin{aligned} \varvec{\pi }_{\varepsilon }^+(k)&= \sum _{\ell =0}^{n_0} \varvec{\pi }(\ell ) \varvec{R}_{\ell }(k+n_0-\ell ) + \sum _{\ell =1}^{k-1} \varvec{\pi }_{\varepsilon }^+(\ell ) \varvec{R}_{\varepsilon }^+(k-\ell ), \qquad k \in {\mathbb {N}}, \nonumber \\ \varvec{\pi }_{\varepsilon }^-(k)&= \sum _{\ell =0}^{n_0} \varvec{\pi }(\ell ) \varvec{R}_{\ell }(k+n_0-\ell ) + \sum _{\ell =1}^{k-1} \varvec{\pi }_{\varepsilon }^-(\ell ) \varvec{R}_{\varepsilon }^-(k-\ell ), \qquad k \in {\mathbb {N}}. \end{aligned}$$
(B.29)

These equations, together with (2.8), yield

$$\begin{aligned} \varvec{\pi }_{\varepsilon }^+(1) = \varvec{\pi }_{\varepsilon }^-(1)&= \sum _{\ell =0}^{n_0}\varvec{\pi }(\ell )\varvec{R}_{\ell }(n_0+1-\ell ) = \varvec{\pi }(n_0+1), \end{aligned}$$

which shows that (B.10) holds for \(k=1\). As the inductive assumption, suppose that (B.10) holds for \(k=k_*\), that is,

$$\begin{aligned} \varvec{\pi }_{\varepsilon }^-(k) \le \varvec{\pi }(k+n_0) \le \varvec{\pi }_{\varepsilon }^+(k),\qquad k=1,2,\dots ,k_{*}, \end{aligned}$$
(B.30)

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

$$\begin{aligned} \varvec{\pi }_{\varepsilon }^-(k_*+1)&\le \sum _{\ell =0}^{n_0} \varvec{\pi }(\ell ) \varvec{R}_{\ell }(k_{*}+1+n_0-\ell ) + \sum _{\ell =1}^{k_*}\varvec{\pi }(\ell +n_0) \varvec{R}_{\ell +n_0}(k_*+1-\ell ) \\&= \sum _{\ell =0}^{k_{*}+n_0}\varvec{\pi }(\ell )\varvec{R}_{\ell }(k_{*}+1+n_0-\ell ) \\&= \varvec{\pi }(k_{*}+1+n_0), \end{aligned}$$

where the last equality is due to (2.8). Similarly, we can show that

$$\begin{aligned} \varvec{\pi }(k_{*}+1+n_0) \le \varvec{\pi }_{\varepsilon }^+(k_*+1). \end{aligned}$$

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

$$\begin{aligned} \lim _{k\rightarrow \infty }{\overline{\varvec{R}}_n(k) \over {\mathbb {P}}(Y > k)}&= \varvec{c}_n^\mathrm{A}\varvec{g}\left( \varvec{I} - \varvec{\varPhi } \right) ^{-1}, \end{aligned}$$
(B.31)

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\),

$$\begin{aligned} \lim _{k\rightarrow \infty }\left( \prod _{\ell =n+k+1}^{n+k+m} \downarrow \varvec{G}_{\ell } \right) \left( \varvec{I} - \varvec{\varPhi }_{n+k} \right) ^{-1} =\varvec{G}^m \left( \varvec{I} - \varvec{\varPhi } \right) ^{-1}, \end{aligned}$$

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:

$$\begin{aligned} \varvec{G}^m \left( \varvec{I} - \varvec{\varPhi } \right) ^{-1} - \delta \varvec{e}\varvec{e}^{\top }&\le \left( \prod _{\ell =n+k+1}^{n+k+m} \downarrow \varvec{G}_{\ell } \right) \left( \varvec{I} - \varvec{\varPhi }_{n+k} \right) ^{-1} \\&\le \varvec{G}^m \left( \varvec{I} - \varvec{\varPhi } \right) ^{-1} + \delta \varvec{e}\varvec{e}^{\top }. \end{aligned}$$

Applying this inequality to (2.7), we obtain, for all sufficiently large k,

$$\begin{aligned} \varvec{R}_n(k)&\le \sum _{m=0}^{\infty } \varvec{A}_n(k+m) \varvec{G}^m \left( \varvec{I} - \varvec{\varPhi } \right) ^{-1} + \delta \overline{\varvec{A}}_n(k)\varvec{e}\varvec{e}^{\top }, \quad n \in {\mathbb {Z}}_+, \end{aligned}$$
(B.32a)
$$\begin{aligned} \varvec{R}_n(k)&\ge \sum _{m=0}^{\infty } \varvec{A}_n(k+m) \varvec{G}^m \left( \varvec{I} - \varvec{\varPhi } \right) ^{-1} - \delta \overline{\varvec{A}}_n(k)\varvec{e}\varvec{e}^{\top }, \quad n \in {\mathbb {Z}}_+. \end{aligned}$$
(B.32b)

From (B.32a), we have

$$\begin{aligned} \overline{\varvec{R}}_n(k)&\le \sum _{m=0}^{\infty } \overline{\varvec{A}}_n(k+m) \varvec{G}^m \left( \varvec{I} - \varvec{\varPhi } \right) ^{-1} + \delta \overline{\overline{\varvec{A}}}_n(k)\varvec{e}\varvec{e}^{\top },&n&\in {\mathbb {Z}}_+. \end{aligned}$$
(B.33)

Applying (3.6) and (3.10) to (B.33), we obtain

$$\begin{aligned} \limsup _{k\rightarrow \infty } { \overline{\varvec{R}}_n(k) \over {\mathbb {P}}(Y > k) }&\le \varvec{c}_n^\mathrm{A}\varvec{g}\left( \varvec{I} - \varvec{\varPhi } \right) ^{-1} + \delta \varvec{c}_n^\mathrm{A}\varvec{e}^{\top }, \quad n \in {\mathbb {Z}}_+. \end{aligned}$$
(B.34)

Similarly, we have

$$\begin{aligned} \liminf _{k\rightarrow \infty } { \overline{\varvec{R}}_n(k) \over {\mathbb {P}}(Y > k) }&\ge \varvec{c}_n^\mathrm{A}\varvec{g}\left( \varvec{I} - \varvec{\varPhi } \right) ^{-1} - \delta \varvec{c}_n^\mathrm{A}\varvec{e}^{\top }, \quad n \in {\mathbb {Z}}_+. \end{aligned}$$
(B.35)

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

$$\begin{aligned} \overline{\varvec{R}}(k)&= \sum _{m=0}^{\infty }\overline{\varvec{A}}(k+m)\varvec{G}^m(\varvec{I} - \varvec{\varPhi })^{-1}, \end{aligned}$$
(B.36)
$$\begin{aligned} \overline{\varvec{S}}_{\varepsilon }(k)&= \sum _{m=0}^{\infty }\overline{\varvec{\varDelta }}(k+m)\varvec{G}^m(\varvec{I} - \varvec{\varPhi })^{-1} + \overline{\overline{\varvec{A}}}(k)\varvec{e}\varvec{e}^{\top } + \varepsilon \overline{\overline{\varvec{\varDelta }}}(k)\varvec{e}\varvec{e}^{\top }. \end{aligned}$$
(B.37)

Applying (3.11) to (B.36) yields

$$\begin{aligned} \varvec{c}_-^\mathrm{A}\varvec{g}(\varvec{I} - \varvec{\varPhi })^{-1} \le \liminf _{k \rightarrow \infty } {\overline{\varvec{R}}(k) \over {\mathbb {P}}(Y> k) } \le \limsup _{k \rightarrow \infty } {\overline{\varvec{R}}(k) \over {\mathbb {P}}(Y > k) }&\le \varvec{c}_+^\mathrm{A}\varvec{g}(\varvec{I} - \varvec{\varPhi })^{-1}. \end{aligned}$$

Furthermore, applying (3.7), (3.8), and (3.12) to (B.37) yields

$$\begin{aligned} \limsup _{k \rightarrow \infty } {\overline{\varvec{S}}_{\varepsilon }(k) \over {\mathbb {P}}(Y > k) }&\le \varvec{c}^{\varDelta }\varvec{g}(\varvec{I} - \varvec{\varPhi })^{-1} + \varvec{c}_+^{\mathrm{A}}\varvec{e}^{\top } + \varepsilon \varvec{c}^{\varDelta }\varvec{e}^{\top }. \end{aligned}$$

Therefore, we have

$$\begin{aligned} \limsup _{k \rightarrow \infty } { \overline{\varvec{R}}(k) + \varepsilon \overline{\varvec{S}}_{\varepsilon }(k) \over {\mathbb {P}}(Y> k) }&\le \varvec{c}_+^\mathrm{A}\varvec{g}(\varvec{I} - \varvec{\varPhi })^{-1} + \varepsilon \left\{ \varvec{c}^{\varDelta } \varvec{g}(\varvec{I} - \varvec{\varPhi })^{-1} + \varvec{c}_+^{\mathrm{A}}\varvec{e}^{\top } + \varepsilon \varvec{c}^{\varDelta }\varvec{e}^{\top } \right\} \\&= (\varvec{c}_+^{\mathrm{A}} + \varepsilon \varvec{c}^{\varDelta }) \varvec{g}(\varvec{I} - \varvec{\varPhi })^{-1} + \varepsilon (\varvec{c}_+^{\mathrm{A}} + \varepsilon \varvec{c}^{\varDelta }) \varvec{e}^{\top }, \\ \liminf _{k \rightarrow \infty } { \overline{\varvec{R}}(k) - \varepsilon \overline{\varvec{S}}_{\varepsilon }(k) \over {\mathbb {P}}(Y > k) }&\ge \varvec{c}_-^\mathrm{A}\varvec{g}(\varvec{I} - \varvec{\varPhi })^{-1} - \varepsilon \left\{ \varvec{c}^{\varDelta } \varvec{g}(\varvec{I} - \varvec{\varPhi })^{-1} + \varvec{c}_+^{\mathrm{A}}\varvec{e}^{\top } + \varepsilon \varvec{c}^{\varDelta }\varvec{e}^{\top } \right\} \\&= (\varvec{c}_-^{\mathrm{A}} - \varepsilon \varvec{c}^{\varDelta }) \varvec{g}(\varvec{I} - \varvec{\varPhi })^{-1} - \varepsilon (\varvec{c}_+^{\mathrm{A}} + \varepsilon \varvec{c}^{\varDelta }) \varvec{e}^{\top }. \end{aligned}$$

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

$$\begin{aligned} \lim _{k\rightarrow \infty }{\varvec{R}_{[0,n_0]}(k) \over {\mathbb {P}}(V_\mathrm{de} = k)}&= \left( \begin{array}{c} \widetilde{\varvec{c}}_0^{\mathrm{A}} \\ \widetilde{\varvec{c}}_1^{\mathrm{A}} \\ \vdots \\ \widetilde{\varvec{c}}_{n_0}^{\mathrm{A}} \end{array} \right) \varvec{g}(\varvec{I} - \varvec{\varPhi })^{-1}. \end{aligned}$$
(C.1)

Proof

To prove (C.1), it suffices to show that

$$\begin{aligned} \lim _{k\rightarrow \infty } { \varvec{R}_n(k) \over {\mathbb {P}}(V_\mathrm{de} = k) } = \widetilde{\varvec{c}}_n^\mathrm{A}\varvec{g}\left( \varvec{I} - \varvec{\varPhi } \right) ^{-1}, \qquad n \in {\mathbb {Z}}_+. \end{aligned}$$
(C.2)

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

$$\begin{aligned} \limsup _{k\rightarrow \infty } { \varvec{R}_n(k) \over {\mathbb {P}}(V_\mathrm{de} = k) }&\le \widetilde{\varvec{c}}_n^\mathrm{A}\varvec{g}\left( \varvec{I} - \varvec{\varPhi } \right) ^{-1} + \delta \widetilde{\varvec{c}}_n^\mathrm{A}\varvec{e}^{\top }, \quad n \in {\mathbb {Z}}_+, \\ \liminf _{k\rightarrow \infty } { \varvec{R}_n(k) \over {\mathbb {P}}(V_\mathrm{de} = k) }&\ge \widetilde{\varvec{c}}_n^\mathrm{A}\varvec{g}\left( \varvec{I} - \varvec{\varPhi } \right) ^{-1} - \delta \widetilde{\varvec{c}}_n^\mathrm{A}\varvec{e}^{\top }, \quad n \in {\mathbb {Z}}_+. \end{aligned}$$

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\),

$$\begin{aligned} \limsup _{k\rightarrow \infty }{\varvec{R}_{\varepsilon }^+(k) \over {\mathbb {P}}(V_\mathrm{de} = k)}&\le (\widetilde{\varvec{c}}_+^{\mathrm{A}} + \varepsilon \widetilde{\varvec{c}}^{\varDelta }) \varvec{g}(\varvec{I} - \varvec{\varPhi })^{-1} + \varepsilon (\widetilde{\varvec{c}}_+^{\mathrm{A}} + \varepsilon \widetilde{\varvec{c}}^{\varDelta }) \varvec{e}^{\top }, \\ \liminf _{k\rightarrow \infty }{\varvec{R}_{\varepsilon }^-(k) \over {\mathbb {P}}(V_\mathrm{de} = k)}&\ge \left[ (\widetilde{\varvec{c}}_-^{\mathrm{A}} - \varepsilon \widetilde{\varvec{c}}^{\varDelta }) \varvec{g}(\varvec{I} - \varvec{\varPhi })^{-1} - \varepsilon (\widetilde{\varvec{c}}_+^{\mathrm{A}} + \varepsilon \widetilde{\varvec{c}}^{\varDelta })\varvec{e}^{\top } \right] _+. \end{aligned}$$

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 \).

  1. (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}$$
  2. (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.

  3. (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:

  1. (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}$$
  2. (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.

  3. (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.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11134-022-09857-5

Keywords

Mathematics Subject Classification

Navigation