{'fraction_non_alphanumeric': 0.08242238740708352, 'fraction_numerical': 0.0255064859349949, 'mean_word_length': 3.8678609435970204, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 12, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Error bounds for augmented truncations of discrete-time block-monotone Markov chains under subgeometric drift conditions

This paper studies the last-column-block-augmented northwest-corner truncation (LC-block-augmented truncation, for short) of discrete-time block-monotone Markov chains under subgeometric drift conditions. The main result of this paper is to present an upper bound for the total variation distance between the stationary probability vectors of a block-monotone Markov chain and its LC-block-augmented truncation. The main result is extended to Markov chains that themselves may not be block monotone but are block-wise dominated by block-monotone Markov chains satisfying modified drift conditions. Finally, as an application of the obtained results, the GI/G/1-type Markov chain is considered.


Introduction
This paper considers the truncation approximation of discrete-time block-structured Markov chains characterized by an infinite number of block matrices. The typical examples of such Markov chains are M/G/1-, GI/M/1-and GI/G/1-type Markov chains and level-dependent quasibirth-and-death processes (LD-QBDs) (see, e.g., [6] and the references therein) and they appear as the queue length processes of various semi-Markovian queues (see, e.g., [23]).
It is a challenging problem to obtain the stationary probability vectors of block-structured Markov chains characterized by an infinite number of block matrices. To solve this problem, we often use the augmented northwest-corner truncation (augmented truncation, for short). More specifically, we form a finite stochastic matrix by augmenting, in some way, the (finite) northwest-corner truncation of the transition probability matrix and then adopt the stationary probability vector of the resulting finite stochastic matrix as an approximation to that of the original Markov chain.
Although there are infinitely many variations of such augmented truncation, this paper focuses on the last-column-block-augmented northwest-corner truncation (LC-block-augmented truncation, for short) because it is proved that the LC-block-augmentation is the best (in a certain sense) among all the block augmentations if they are applied to the northwest-corner truncations of block-monotone transition probability matrices (see [10,Theorem 3.6] and [20,Theorem 4.1]). Note that block monotonicity is an extension of (classical) monotonicity to block-structured Markov chains [10,Definition 2.5].
The main purpose of this paper is to estimate the error of the stationary probability vector obtained by the LC-block-augmented truncation. There are some related studies on the truncation of Markov chains. Tweedie [24] presented a total-variation-distance error bound for the stationary probability vector of the last-column-augmented northwest-corner truncation of a monotone and geometrically ergodic Markov chain in discrete time. More precisely, Tweedie [24]'s bound is an upper bound for the total variation distance between the stationary probability vectors of the original Markov chain and its last-column-augmented northwest-corner truncation. Hart and Tweedie [5] and Liu [13] discussed the convergence of the stationary probability vectors of the augmented truncations of continuous-time Markov chains with monotonicity and/or exponential ergodicity. Masuyama [18,20] extended Tweedie [24]'s result to block-monotone Markov chains in discrete and continuous time.
Without the monotonicity of Markov chains, Hervé and Ledoux [7] derived a total-variationdistance error bound for the stationary probability vector of the last-column-augmented northwestcorner truncation of a geometrically ergodic Markov chain in discrete time. Zeifman et al. [27] considered a periodic and exponentially weakly ergodic non-time-homogeneous birth-and-death process in continuous time, and they presented a total-variation-distance error bound for the periodic stationary distribution obtained by the truncation of the state space (see also [25,26]).
Basically, all the existing results mentioned above assume geometric ergodicity (exponential ergodicity in continuous time) and thus they are not applicable to Markov chains with subgeometric ergodicity (including polynomial ergodicity). For example, reflected Markov additive processes and GI/G/1-type Markov chains with the heavy-tailed asymptotics [8,14], which typically arise from BMAP/GI/1 queues with subexponential service times and/or batch sizes [15,19]. As far as we know, there are no studies on the error estimation of the augmented truncation of Markov chains with subgeometric ergodicity, except for Liu [12]'s work. Liu [12] derived a total-variation-distance error bound for the stationary probability vector of the last-column-augmented northwest-corner truncation of a monotone and polynomially ergodic Markov chain in discrete time.
In this paper, we consider a block-monotone Markov chain under the drift condition proposed by Douc et al. [3], which covers polynomial ergodicity and other types of subgeometric ergodicity. We first derive an upper bound for the total variation distance between the stationary probability vectors of the original Markov chain and its LC-block-augmented truncation, which is the main result of this paper. We also present a similar bound in the case where the original Markov chain itself may not be block monotone but is block-wise dominated by a block-monotone Markov chain satisfying a modified drift condition with a larger tolerance for boundary exceptions. The modified drift condition strengthens the applicability of the obtained bound. Finally, we provide a detailed procedure for establishing our error bounds for the LC-block-augmented truncations of block-monotone GI/G/1-type Markov chains.
The rest of this paper is divided into five sections. Section 2 provides preliminary results on block-monotone stochastic matrices. Section 3 presents the main result of this paper. Section 4 contains the extension of the main result to possibly non-block-monotone Markov chains that are block-wise dominated by block-monotone Markov chains satisfying the modified drift condition. Section 5 considers the application of the extended result to block-monotone GI/G/1type Markov chains. Finally, Section 6 provides concluding remarks.

Preliminaries
where (k, i; ℓ, j) represents ordered pair ((k, i), (ℓ, j)). Note here that P is row stochastic (stochastic, for short, hereafter), i.e., P e = e, where e denotes a column vector of 1's of an appropriate order. For n ∈ N, let (n) P n := ( (n) p n (k, i; ℓ, j)) (k,i),(ℓ,j)∈F denote a stochastic matrix such that, for i, j ∈ D, (2.1) By definition, P and (n) P n can be partitioned into block matrices with size d. Furthermore, (2.1) implies that (n) P n is in the following form: where F n = {0, 1, . . . , n}×D and O denotes the zero matrix of an appropriate order. Equation (2.2) shows that the sub-state space F \ F n of (n) P n is transient and thus the submatrix (n) P * n of (n) P n does not have any contribution to the stationary probability vector of (n) P n . Therefore, we call the whole matrix (n) P n the last-column-block-augmented (LC-block-augmented) northwest-corner truncation (LC-block-augmented truncation, for short). The LC-block-augmented truncation (n) P n is also called the last-column-block-augmented first-n-block-column truncation in [18]. It should be noted that, since (n) P n n in (2.2) is a finite stochastic matrix, the LC-block-augmented truncation (n) P n always has at least one stationary probability vector (see, e.g., [2, Chapter 3, Theorems 3.1 and 3.3]), which is denoted by (n) π n := ( (n) π n (k, i)) (k,i)∈F .
We now assume that P is irreducible and positive recurrent. We then define π := (π(k, i)) (k,i)∈F as the unique stationary probability vector of P . We also assume, unless otherwise stated, that P is block monotone with block sized d (see [18,Definition 1 where P (k; ℓ) := (p(k, i; ℓ, j)) i,j∈D is the (k, ℓ)th block of P . To shorten the statements on block monotonicity, let BM d denote the set of block-monotone stochastic matrices with block size d. It then follows from P ∈ BM d that a stochastic matrix ∞ m=0 P (k; m) is constant with k ∈ Z + (see [18,Proposition 1.1]). Furthermore, since P is irreducible, the stochastic matrix Ψ := ∞ m=0 P (k; m) is irreducible and thus has the unique stationary probability vector, denoted by ̟ := (̟(i)) i∈D .
Finally, we introduce some symbols and definitions related to block monotonicity. Let where I d denotes the d × d identity matrix (we write I for the identity matrix whose order is clear from the context). Note here that (2.3) is equivalent to We denote by BI d the set of block-increasing column vectors with block size d.

Main result
This section presents an upper bound for (n) π n − π , where · denotes the total variation distance, i.e., Let p m (k, i) := (p m (k, i; ℓ, j)) (ℓ,j)∈F and (n) p m n (k, i) := ( (n) p m n (k, i; ℓ, j)) (ℓ,j)∈F denote probability vectors such that p m (k, i; ℓ, j) and (n) p m n (k, i; ℓ, j) represent the (k, i; ℓ, j)th elements of P m and ( (n) P n ) m , respectively. For any function ϕ(·, ·) on F, let ϕ(k, ̟) = i∈D ̟(i)ϕ(k, i) for k ∈ Z + . We then have It also follows from the second last inequality in the proof of [18,Theorem 3.1] that To estimate the first and second terms on the right hand side of (3.1), we assume the subgeometric drift condition proposed in [3], which is described in Assumption 3.1 below. For the description of the drift condition, let 1 K = (1 K (k, i)) (k,i)∈F , K ∈ Z + denote a column vector such that In addition, for any scalar-valued function θ on (−∞, ∞) and any real-valued column vector a := (a(i)), let θ • a = (θ • a(i)).
Under Assumption 3.1, the irreducible stochastic matrix P is subgeometrically ergodic if P is aperiodic [3, Proposition 2.5]. However, we do not necessarily assume the aperiodicity of P .
We now introduce some symbols according to [3,Section 2]. Let H φ denote a function on Clearly, H φ is an increasing differentiable concave function, and lim x→∞ H φ (x) = ∞ due to the concavity of φ (see [3, section 2]). Thus, the inverse The function r φ is nondecreasing because φ is nondecreasing and H −1 φ is increasing. In addition, it follows from [3, Proposition 2.1] that r φ is log-concave. For convenience, we define r φ (x) = 0 for x < 0.
In what follows, we present two lemmas and the main result of this paper.
Lemma 3.2 Suppose that P ∈ BM d and P is irreducible. If Assumption 3.1 holds, then, for all k ∈ Z + and m ∈ N, where the function r φ is given in (3.5).
Proof. We first prove (3.15). Let τ 0 = inf{n ∈ Z + ; X n = 0} and P (k,i) ( · ) = P( · | X 0 = k, J 0 = i) for (k, i) ∈ F. Following the derivation of [18,Eq. (3.22)] and replacing v by e, we have where the second inequality follows from the fact that P (ℓ,j) (τ 0 > m) ≤ P (ℓ,j) (τ + 0 > m) for m ∈ N and (ℓ, j) ∈ F. Using Markov's inequality, we have Therefore, (3.16) can be proved in the same way as that of (3.15). The details are omitted. ✷ Theorem 3.1 below presents upper bounds for (n) π n − π , which are the main result of this paper. Theorem 3.1 Suppose that P ∈ BM d and P is irreducible. If Assumption 3.1 holds, then, for all n, m ∈ N, where the function r φ is given in (3.5).

Extension of the main result
In this section, we extend Theorem 3.1 to the case where P may not be block monotone but is block-wise dominated by a block-monotone stochastic matrix P = ( p(k, i; ℓ, j)) (k,i),(ℓ,j)∈F . Note here that P ∈ BM d is allowed to be equal to P and thus P ∈ BM d .
Theorem 4.1 Suppose that (i) P ≺ d P ∈ BM d and P is irreducible; and that (ii) there exist a constant b ∈ (0, ∞), a column vector v = (v(k, i)) (k,i)∈F ∈ BI d with v ≥ e and a nondecreasing differentiable concave function φ : [1, ∞) → (0, ∞) with lim t→∞ φ ′ (t) = 0 such that, for some M ∈ N and K ∈ Z + , Let B denote a positive constant such that Under these conditions, the following bound holds for all m, n ∈ N.
In addition, if K = 0, then, for all m, n ∈ N, which holds without (4.2).

Remark 4.1
Although the condition (4.2) ensures the existence of a constant B ∈ (0, ∞) satisfying (4.3), it may seem that the condition (4.2) weakens the applicability of Theorem 4.1. However, that is not necessarily the case. To verify this, we assume that all the conditions of Theorem 4.1 are satisfied, except for (4.2), and that P is aperiodic. Note here that the aperiodicity of P does not make any restriction because (I + P )/2 and (I + P )/2 are aperiodic and π(I + P )/2 = π, π(I + P )/2 = π, We also assume the following mild condition.
Under these conditions, let {b m ; m ∈ N} and {K m ; m ∈ N} denote sequences such that b 1 = b, K 1 = K and, for m = 2, 3, . . . , where λ ∈ (0, 1) is fixed arbitrarily. It then follows from (4.1) that In addition, the aperiodicity of P implies that for any m ∈ N there exists some ν 0 (K m ) ∈ N such that P ν (K m ; 0)e > 0 for all ν ≥ ν 0 (K m ) (see, e.g., [2, Chapter 2, Theorem 4.3]). As a result, if there exists some m ∈ N such that ν 0 (K m ) ≤ mM, then we can obtain a bound similar to (4.4) by using Theorem 4.1.
Proof of Theorem 4.1. Let {( X ν , J ν ); ν ∈ Z + } denote a block-monotone Markov chain with state space F and transition probability matrix P . Conditions (i) and (ii) imply that P is irreducible and positive recurrent and thus has the unique stationary probability vector, denoted by π = ( π(k, i)) (k,i)∈F . It follows from P ≺ d P ∈ BM d and [18, Following the last part of the proof of [18,Theorem 4.1], we have It follows from (4.8) and the triangle inequality that, for m ∈ N, Note that (n) P n is the LC-block-augmented truncation of P . Note also that (n) P n ≺ d P ∈ BM d . Thus, it follows from [18, Proposition 2.3] that ( (n) P n ) M ≺ d P M . Using this relation together with v ∈ BI d and [18, Remark 2.1], we obtain Combining (4.1) and (4.10), we have Pre-multiplying this inequality by (n) π n yields Substituting (4.11) into (4.9) results in .
); ν ∈ Z + } as the M-skeleton of the Markov chain {( X ν , J ν ); ν ∈ Z + } with transition probability matrix P , i.e., Proceeding as in the derivation of the first inequality for p m (k, ̟) − π v at page 97 of [18] (replacing v by e as in the derivation of (3.17)) and using (4.7), we obtain In addition, by Markov's inequality, where Substituting (4.14) into (4.13), we have, for m ∈ N, It should be noted that if K = 0 then Lemma 3.1 yields Combining (4.15) with (4.16) and (4.17), we obtain Substituting (4.18) and (4.19) into (4.12) yields the bound (4.6) in the special case where K = 0.
In what follows, we consider the general case, where K ∈ N. In fact, the following inequality holds (which is proved later): (4.23) Since . It follows from this inequality and (4.20) that The inequality (4.24) implies that the case where K ∈ N is reduced to the special case where K = 0.
To follow the proof of the case where K = 0, we define two functions H φ and r φ , which correspond to the functions H φ and r φ , respectively. Let H φ denote a function on where the second equality results from (3.4), (4.5) and (4.21). Furthermore, let r φ denote a function on [0, ∞) such that We then have where the first, second and third equalities follows from (4.21), (4.25) and (3.5), respectively. In addition, following the derivation of (4.18) and using v in (4.23) and r φ in (4.26) (instead of v and r φ ), we obtain Similarly, Substituting (4.27) and (4.28) into (4.12) yields (4.4). It remains to prove that (4.20) holds.

Applications to GI/G/1-type Markov chains
In this section, we discuss the application of our results to block-monotone GI/G/1-type Markov chains. We first present a procedure for establishing an error bound for the LC-block-augmented truncation of a general block-monotone GI/G/1-type Markov chain. We then consider such a simple special case that the parameters of the error bound are specified.

General case
In this subsection, we consider a general block-monotone GI/G/1-type Markov chain, which satisfies the following assumption.

Assumption 5.1
(i) P ∈ BM d is an irreducible GI/G/1-type transition probability matrix such that where A(−k) = −k ℓ=−∞ A(ℓ) for k ∈ Z + and the diagonal blocks A(0) and B(0) are d × d matrices; and is an irreducible stochastic matrix.

Remark 5.1
The GI/G/1-type transition probability matrix P in (5.1) above is equal to P in (5.1) of [18], though the latter has the block matrices {B(0), B(−1), B(−2), . . . } in the first block column. Indeed, for all k ∈ N, B(−k) must be equal to Recall here that ̟ is the stationary probability vector of Ψ and thus A. Using ̟, we define σ as We then assume the following.
The subject of this subsection is to show how to obtain an upper bound for (n) π n − π by using Theorem 4.1. To apply Theorem 4.1 to P in (5.1), we have to prove that the drift condition (4.1) holds with P being equal to P , that is, Unfortunately, since it is not easy to establish directly the drift condition on P M , we construct a modified transition probability matrix from P and establish a similar drift condition on the Mth power of the modified transition probability matrix. Using the similar drift condition, we derive the desired drift condition on P M .
We define the modified transition probability matrix mentioned above. For N ∈ N, let P N := (p N (k, i; ℓ, j)) (k,i),(ℓ,j)∈F denote a stochastic matrix such that where A N (k), k ∈ Z := {0, ±1, ±2, . . . } is given by It follows from (5.3) and Assumption 5.1 that P ≺ d P N ∈ BM d for N ∈ N. Furthermore, let Assumption 5.2 implies that, for all sufficiently large N ∈ N, In the rest of this subsection, we fix N ∈ N such that (5.6) holds. For M ∈ N, we then define We also obtain the following result. Proof. We consider a Markov additive process {(Y ν , J ν ); ν ∈ Z + } with state space Z × D and kernel {A N (k); k ∈ Z}, which evolves according to the following transition law.
where [ · ] i,j denotes the (i, j)th element of the matrix in the square brackets. Note here that ̟ is the stationary probability vector of the background Markov chain {J ν ; ν ∈ Z + } and thus σ N < 0 is the mean drift of the marginal process {Y ν ; ν ∈ Z + }. In addition, it follows from σ N < 0 that P(lim ν→∞ Y ν = −∞ | Y 0 = i) = 1 for all i ∈ D (see, e.g., [1, Chapter XI, Proposition 2.10]). Therefore, (5.7) holds for some M 0 ∈ N. ✷ To proceed, we fix M ≥ M 0 arbitrarily, where M 0 is some positive integer satisfying (5.7). We denote by P M N (k; ℓ), k, ℓ ∈ Z + the (k, ℓ)th block of the Mth power P M N of P N . It then follows from (5.3) that

and thus
Therefore, we show that P M N satisfies a drift condition similar to (4.1). We now introduce a function V : [0, ∞) → [1, ∞), which plays a key role in establishing the drift condition on P M N .

Remark 5.2 Appendix A provides a sufficient condition for Assumption 5.3 and the typical examples of V .
The key properties of the function V are summarized in Lemmas 5.2 and 5.3 below.

Thus, if r
It is known (see [8, Theorem 2.2] and [14, Theorem 3.1]) that, under Assumptions 5.1 and 5.2, min(r A + , r B + ) > 1 if and only if the GI/G/1-type transition probability matrix P in (5.1) satisfies the geometric drift condition (see Remark 3.1). On the other hand, Assumption 5.3 together with Assumptions 5.1 and 5.2 implies that the GI/G/1-type transition probability matrix P in (5.1) is positive recurrent but does not satisfy the geometric drift condition because r A + = 1, i.e., {A(k); k ∈ Z + } is heavy-tailed (see Remark 5.3). It is also known (see [11,Theorem 3.1]) that if {A(k); k ∈ Z + } is heavy-tailed then so is the stationary probability vector of the ergodic GI/G/1-type transition probability matrix P . Such GI/G/1-type transition probability matrices typically arise from BMAP/GI/1 queues with subexponential service times and/or batch sizes, and these Markov chains have the subexponential stationary probability vectors under some mild technical conditions [15,19] (see also [9,16]). ∈ (0, 1), there exist some δ 0 := δ 0 (ε) > 0 and positive integer K 0 := K 0 (δ 0 , L) ≥ L such that

Lemma 5.3 If Assumption 5.3 holds, then, for any ε
Proof. Recall that V ′ is nondecreasing. Thus, it follows from condition (v) of Assumption 5.3 that In addition, condition (v) of Assumption 5.3 implies that, for any ε ∈ (0, 1), where δ 0 > 0 is sufficiently small depending on ε ∈ (0, 1). Consequently, (5.18) and (5.19) show that the statement of this lemma is true. ✷ To establish the drift condition on P M N , we estimate ∞ ℓ=0 P M N (k; ℓ)V (ℓ)e for sufficiently large k's by using Lemmas 5.1 and 5.3. Lemma 5.1 implies that there exist κ > 0 and ε ∈ (0, 1) such that Furthermore, according to (5.10), there exists some K ∈ {K 0 , K 0 + 1, . . . } such that (ii) δ 0 > 0 and K 0 ∈ {L, L + 1, . . . } such that (5.16) and (5.17) hold; and We then have Proof. It follows from (5.8) and K ≥ K 0 ≥ L that, for k ≥ K + 1, where, by convention, any empty sum (which has no terms) is defined as zero. It also follows from the mean value theorem that, for any k ∈ Z + and −L ≤ ℓ ≤ δ 0 k 1−α , there exists some ξ ∈ (0, 1) such that Substituting (5.24) into the second term in the right hand side of (5.23) yields, for k ≥ K + 1, where the inequality holds because Applying (5.16) and (5.17) to the above inequality, we obtain, for k ≥ K + 1, We are now ready to establish the drift condition on P M N and thus P M . We fix where V −1 denotes the inverse function of the increasing and differentiable function V (see Assumption 5.3). Clearly, v ∈ BM d . Furthermore, it follows from (5.28) that From v ∈ BM d , (5.9) and (5.33), we obtain To use Theorem 4.1, it remains to show that the function φ in (5.28) is qualified for the function φ appearing in Theorem 4.1, which is accomplished by Lemma 5.5 below.
Proof of Lemma 5.5.

Theorem 5.1
Suppose that all the conditions of Lemma 5.4 are satisfied. Furthermore, suppose that P M (K; 0)e > 0, and fix B ∈ (0, ∞) such that BP M (K; 0)e ≥ be, where b is given in (5.32). Under these conditions, we have where the composite function r φ • c φ,B is given by (3.5), (4.5) and (5.28). In addition, if K = 0, then for all m, n ∈ N. . Therefore, lim t→∞ φ(t) = lim t→∞ κV ′ (V −1 (t)) = ∞, which leads to lim x→∞ r φ (x) = ∞, as stated in Remark 3.2. Consequently, we can choose m, n ∈ N such that the error bounds (5.36) and (5.37) are reduced to any desired value less than two.

Special case
In this subsection, we consider the LC-block-augmented truncation of a special block-monotone GI/G/1-type Markov chain, for which we establish an error bound with specified parameters in accordance with Theorem 5.1. To this end, in addition to Assumption 5.1, we assume that P in (5.1) is reduced to where 2 < β 1 < β 2 and ζ( · ) denotes the Riemann zeta function. The matrix P in (5.38) can be regarded as the transition probability matrix of an irreducible reflected Markov additive process [1, Chapter XI, Section 2e]. It is easy to see that the stationary probability vector ̟ of A = ∞ k=−∞ A(k) is given by For convenience, let Note here that 1 < ζ(s 2 ) < ζ(s 1 ) < π 2 /6 for 2 < s 1 < s 2 , which leads to Therefore, from (5.44) and (5.45), we have Applying these two inequalities to (5.46), we obtain σ < 0. i.e., Assumption 5.2 holds. As a result, P in (5.38) has the unique stationary probability vector π.
We have shown that all the conditions of Theorem 5.1 are satisfied. We now fix where b is given in (5.71). It then follows from (5.38), (5.39) and (5.40) that BP (K; 0)e = 2 K bA(−K)e = be.
As a result, using Theorem 5.1, we can derive an error bound for the special case considered here.

Concluding remarks
This paper studied the estimation of the total variation distance between the stationary probability vectors of a discrete-time block-structured Markov chain and its LC-block-augmented truncation. The main contribution of this paper is to present a total-variation-distance error bound for the stationary probability vector of the LC-block-augmented truncation under the assumption that the original Markov chain is block monotone and satisfies the subgeometric drift condition proposed in [3]. This paper is complementary to the author's previous study [18], which considered discrete-time block-monotone Markov chains satisfying the geometric drift condition. The author [20] also considered continuous-time block-monotone Markov chains with exponential ergodicity and derived a total-variation-distance error bound for the stationary probability vector of the LC-block-augmented truncation. The present study and the author's previous ones [18,20] depend on the notion of block monotonicity.
Recently, without block monotonicity (including monotonicity), the author [21] established computable upper bounds for the absolute difference between the time-averaged functionals of a continuous-time block-structured Markov chain and its LC-block-augmented truncation under the assumption that the original Markov chain satisfies the f -modulated drift condition (see [21, Condition 1,1]). The f -modulated drift condition includes the geometric (or exponential in continuous time) drift condition and the subgeometric (or subexponential in continuous time) drift condition proposed in [3] as special cases. Therefore, the error bounds in [21] are widely applicable, though they are more computationally costly than those in this paper and [18,20] with block monotonicity.

A Examples of function V in Assumption 5.3
We begin with the following lemma. Proof. Since V is log-concave and log V (0) ≥ 0, we have, for x, y ≥ 0, and thus V (x + y) ≤ V (x)V (y) for x, y ≥ 0. Using this inequality, we have Therefore, (A.1) implies (5.10).
Next, we prove that (A.2) implies (5.10). To this end, we suppose that (A.2) holds. It then follows that, for any c > 0, ∞ ℓ=0 V (cℓ 1/(1−α) )A * M N (ℓ)e is finite and thus In addition, since V is increasing and convex, and, for any δ > 0, where we write H(x) ≍ g(x) if H is a nonnegative matrix-valued function such that both lim inf x→∞ H(x)/g(x) and lim sup x→∞ H(x)/g(x) are finite and not equal to the zero matrix for a scalar-valued function g that is eventually nonnegative. For i = 1, 2, 3, it follows from A(k) ≍ g i (k) and (5.4) that A N (k) ≍ g i (k). Thus, A * M N (k) ≍ g i (k) for i = 1, 2, 3, which can be readily proved by using the extensions of [9, Proposition A.2.6] to the upper and lower limits.
We will see later, from the examples of the function V , that the decay of the error bound (5.36) is moderately exponential (i.e., heavy-tailed Weibull-like) in Case (a); polynomial in Case (b); and logarithmic in Case (c), as the truncation parameter n increases. Therefore, Cases (a), (b) and (c) are called moderately exponential case, polynomial case, and logarithmic case, respectively.
Finally, we confirm that (5.10) holds. It follows from (A.6), (A.9) and A * M N (k) ≍ exp{−ck α } that there exists some finite C > 0 such that, for all sufficiently large k, which implies that Combining this and Lemma A.1, we have (5.10). Consequently, the function V given in (A.6) satisfies all the conditions of Assumption 5.3.
It remains to show that (5.10) and condition (v) of Assumption 5.3 hold. It follows from (A.14) that Combining these equations with γ 0 − γ < −1, we have (A.2). Therefore, (5.10) holds for α = 0 (see Lemma A.1). As a result, the function V given in (A.13) satisfies all the conditions of Assumption 5.3.