Error bounds for last-column-block-augmented truncations of block-structured Markov chains∗ 6 1 HiroyukiMasuyama† 0 2 DepartmentofSystemsScience,GraduateSchoolofInformatics, KyotoUniversity r Kyoto606-8501, Japan p A 7 Abstract ] This paper discusses the error estimation of the last-column-block-augmented R northwest-corner truncation (LC-block-augmented truncation, for short) of block- P . structured Markov chains (BSMCs) in continuous time. We first derive upper h t bounds for the absolute difference between the time-averaged functionals of a a m BSMC and its LC-block-augmented truncation, under the assumption that the [ BSMC satisfies the general f-modulated drift condition. We then establish com- 3 putable bounds for a special case where the BSMC is exponentially ergodic. To v derive such computable bounds for the general case, wepropose amethod that re- 9 8 duces BSMCs to be exponentially ergodic. We also apply the obtained bounds to 4 level-dependentquasi-birth-and-death processes(LD-QBDs),anddiscusstheprop- 3 0 ertiesoftheboundsthoughthenumericalresultsonanM/M/sretrialqueue, which 1. isarepresentativeexampleofLD-QBDs. Finally,wepresentcomputableperturba- 0 tionboundsforthestationary distribution vectorsofBSMCs. 6 1 : v Keywords: Queue, block-structured Markov chain (BSMC), level-dependent quasi- i X birth-and-death process (LD-QBD), last-column-block-augmented northwest-corner r truncation (LC-block-augmented truncation), perturbation bound, Poisson equation, er- a godictheory, Dynkin’sformula MathematicsSubjectClassification: 60J22;37A30;60J28;60K25 1 Introduction Let {(X(t),J(t));t ≥ 0} denote a continuous-time Markov chain with state space F := ∪k∈Z+{k}×Sk, where S = {0,1,...,S } ⊂ Z , Z = {0}∪N, N = {1,2,3,...}. k k + + ∗ ThisworkwassupportedbyGrant-in-AidforScientificResearch(C)ofJapanSocietyforthePromotion ofScienceunderGrantNo.15K00034. †E-mail:[email protected] 1 2 H.Masuyama LetP(t) = (p(t)(k,i;ℓ,j)) denotethetransitionmatrixfunctionof{(X(t),J(t))}, (k,i;ℓ,j)∈F2 i.e., p(t)(k,i;ℓ,j) = P(X(t) = ℓ,J(t) = j | X(0) = k,J(0) = i), t ≥ 0,(k,i;ℓ,j) ∈ F2, where (k,i;ℓ,j) denotes ordered pair ((k,i),(ℓ,j)). We assume that {(X(t),J(t))} is a regular-jump process (see, e.g., Bre´maud [9, Chapter 8, Definition 2.5]). It then follows that {P(t)} is continuous, stable and conservative, which implies that the infinitesimal generator of {(X(t),J(t))} is well-defined (see, e.g., Bre´maud [9, Chapter 8, Theorems 2.1 and 3.4]). Thus, we define Q := (q(k,i;ℓ,j)) as the infinitesimal generator (k,i;ℓ,j)∈F2 of{(X(t),J(t))},i.e., P(t) −I Q = lim , t↓0 t whereI denotestheidentitymatrixwithan appropriateorderaccording tothecontext. We nowassumethatQ hasthefollowingblock-structuredform: L L L L ··· 0 1 2 3 L Q(0;0) Q(0;1) Q(0;2) Q(0;3) ··· 0 L Q(1;0) Q(1;1) Q(1;2) Q(1;3) ··· 1  Q = L2 Q(2;0) Q(2;1) Q(2;2) Q(2;3) ··· , (1.1) L Q(3;0) Q(3;1) Q(3;2) Q(3;3) ...  3  ...  ... ... ... ... ...      where L = {k} × S ⊂ F for k ∈ Z , which is called level k. Markov chains k k + with block-structured infinitesimal generators like Q are called block-structured Markov chains (BSMCs). Typical examples of BSMCs are in block-Toeplitz-like and/or block- Hessenbergforms(includingblock-tridiagonalform),forexample,level-independentGI/G/1- typeMarkovchains(see,e.g.,GrassmannandHeyman[20],Neuts[51]);level-dependent quasi-birth-and-death processes (LD-QBDs) (see, e.g., Latouche and Ramaswami [32, Chapter 12]), and M/G/1-type (skip-free-to-the-left or upper block-Hessenberg) Markov chainsandGI/M/1-type(skip-free-to-the-rightorlowerblock-Hessenberg)Markovchains (see, e.g., Masuyama[43], Masuyamaand Takine[44]). Throughout the paper, we assume that the BSMC {(X(t),J(t))} is ergodic, i.e., ir- reducible and positive recurrent. It then follows that the BSMC {(X(t),J(t))} has the uniquestationarydistributionvector(calledstationarydistributionorstationaryprobabil- ityvector),denotedbyπ := (π(ℓ,j))(ℓ,j)∈F (see, e.g.,Anderson[1,Section5.4,Theorem 4.5]). By definition, πQ = 0, πe = 1, whereedenotesacolumnvectorof1’swithanappropriateorderaccordingtothecontext. Let π(k) = (π(k,i))i∈Sk for k ∈ Z+, which is the subvector of π correspond- ing to level k such that π = (π(0),π(1),...). It is, in general, difficult to compute ErrorBoundsforTruncationsofMarkovChains 3 π = (π(0),π(1),...) because we have to solve an infinite dimensional system of equa- tions. As for the BSMCs with the special structures mentioned above, we can establish the stochastically interpretable expression of the stationary distribution vector by matrix analytic methods (Grassmann and Heyman [20], Latouche and Ramaswami [32], Neuts [51],Zhaoetal.[63])andcanalsoobtaintheanalyticalexpressionofthestationarydistri- bution vector by continued fraction approaches (Hanschke [22], Pearce [52]). However, the construction of such expressions requires an infinite number of computational steps involvingan infinitenumberofblock matricesthatcharacterize thoseBSMCs. To solve this problem practically, we need to truncate infinite iterations (e.g., infinite sums, products and otheralgebraic operations)and/or to truncate theinfinite set of block matrices. The former truncation includes the state-space truncation and is incorporated into many algorithms in the literature (Baumann and Sandmann [7], Bright and Taylor [11], Grassmannand Heyman[21], Masuyama[43], Phung-Ducet al. [53], Takine[58]). On the other hand, the latter truncation can be achieved by the state-space truncation, banded approximation (Zhao et al. [62]), spatial homogenization (Klimenok and Dudin [31], Liuet al. [34], Shinand Pearce [57]), etc. This paper considers the last-column-block-augmented northwest-corner truncation (LC-block-augmentedtruncation,forshort)ofQandthustheBSMC{(X(t),J(t))}(see LiandZhao[35],Masuyama[40,41,42]). TheLC-block-augmentedtruncationisoneof thestate-spacetruncationsandisalsoaspecialcaseofblock-augmentedtruncations(see, e.g., Li and Zhao [35, Section 3] (discrete-time case) and Masuyama [42, Definition 4.1] (continuous-timecase)). Infact,theLC-block-augmentedtruncationisanextensionofthe last-column-augmented northwest-corner truncation (last-column-augmented truncation, forshort)toBSMCs (see, e.g.,Gibsonand Seneta[18]). The reason we focus on the LC-block-augmented truncation is twofold. First, it is shown (Li and Zhao [35, Theorem 3.6] and Masuyama [42, Theorem 4.1]) that the LC-block-augmented truncation yields the best (in a certain sense) approximation to the stationary distribution vector of block-monotone BSMCs among the approximations by block-augmentedtruncations. Noteherethatblockmonotonicityisanextensionof(clas- sical)monotonicity(see Daley[12])to BSMCs (see, e.g., Masuyama[40, Definition 1.1] and Masuyama [42, Definition 3.2] for the definition of block monotonicity). Note also thatblockmonotonicityappearsinthequeuelengthprocessesinsuchrepresentativesemi- MarkovianqueuesasBMAP/GI/1,BMAP/M/sandBMAP/M/∞queues(seeMasuyama [40, 41, 42]). Second, the LC-block-augmented truncation is connected with queueing models with finite capacity. The (possibly embedded) queue length processes in semi- Markovian queues with finite capacity (such as MAP/PH/s/N and MAP/GI/1/N; see, e.g.,Baiocchi[6],Miyazawaetal.[49])canbeconsideredtheLC-block-augmentedtrun- cations of the queue length processes in the corresponding semi-Markovian queues with infinite capacity. Therefore, the estimation of the difference between those finite and in- finite queues is reduced to the error estimation of the LC-block-augmented truncation. Thesearewhywe focuson theLC-block-augmentedtruncation. 4 H.Masuyama We outline the procedure to construct the LC-block-augmented truncation of Q. To this end, we need some symbols and notation. Let | · | denote the cardinality of the set in the vertical bars. Let F = ∪n L ⊂ F and F = F \ F = ∪∞ L for n ∈ Z . n k=0 k n n k=n+1 k + In addition, let k = inf{k ∈ N;S = S forall ℓ ≥ k}. Throughout the paper, unless ∗ ℓ k otherwisestated, weassumethatk = 1,i.e., ∗ S = S forall k ∈ N. k 1 Itshouldbenotedthatthecasewherek ≥ 2can bereducedtothecasewherek = 1by ∗ ∗ relabeling∪k∗−1L ,L ,L ,... as levels0,1,2,..., respectively. ℓ=0 ℓ k∗ k∗+1 Under the above assumption, we define QFn = (q(k,i;ℓ,j))(k,i;ℓ,j)∈(Fn)2 for n ∈ N, which isthe|F |×|F | northwest-cornertruncationofQ,i.e., n n Q(0;0) Q(0;1) ··· Q(0;n−1) Q(0;n) Q(1;0) Q(1;1) ··· Q(1;n−1) Q(1;n)   QF = ... ... ... ... . n    Q(n−1;0) Q(n−1;1) ··· Q(n−1;n−1) Q(n−1;n)     Q(n;0) Q(n;1) ··· Q(n;n−1) Q(n;n)      SincetheBSMC{(X(t),J(t))}isirreducible,QF isnotconservative. Inordertoforma n conservative infinitesimal generator from Q , we augment the last block-column of the F n |Fn|×|Fn|northwest-cornertruncationQFn by ∞ Q(0;m) m=n+1 ∞ Q(1;m)  Pm=n+1. . . . P    ∞ Q(n;m)   m=n+1    We then extend the augmented northwest-corner truncation Q to the order of the orig- P F n inal generator Q in the manner described below, which enables us to perform algebraic operationson theresultinggeneratorand originalgeneratorQ. We now provide a formal definition of the LC-block-augmented truncation of the infinitesimalgeneratorQ. Toshortenexpressions,weusethenotationx∧y = min(x,y). For n ∈ N, let Q := ( q(k,i;ℓ,j)) denote a block-structured infinitesimal (n) (n) (k,i;ℓ,j)∈F2 generatorwhoseblockmatrices Q(k;ℓ) := ( q(k,i;ℓ,j)) ,k,ℓ ∈ Z are (n) (n) (i,j)∈Sk∧1×Sℓ∧1 + givenby Q(k;ℓ), ifk ∈ Z , 0 ≤ ℓ ≤ n−1, +  Q(k;n)+ Q(k;m), ifk ∈ Z+, ℓ = n, Q(k;ℓ) =  (1.2) (n)  m>Xn,m6=k  Q(k;k), ifk = ℓ ≥ n+1,  O, otherwise.   We call (n)Q thelast-column-block-augmented |Fn| × |Fn| northwest-corner truncation (LC-block-augmented truncation,forshort)ofQ. We nowhavethefollowingresult,whoseproofisgiveninAppendixA. ErrorBoundsforTruncationsofMarkovChains 5 Proposition1.1 Let {( X(t), J(t));t ≥ 0} denote a Markov chain with state space (n) (n) Fandinfinitesimalgenerator Q. IftheoriginalgeneratorQisirreducible,then(i)the (n) Markov chain {( X(t), J(t))} (and thus Q) has at least one and at most (S +1) (n) (n) (n) 1 closedcommunicatingclassesinF ;and(ii)hasnoclosedcommunicatingclassesinF . n n Proposition 1.1 shows that the LC-block-augmented truncation Q of the ergodic (n) generator Q may havemorethan one stationarydistributionvector. On the otherhand, it followsfrom Theorem 2.1and Remark 2.2 ofHart and Tweedie[23]that lim P( X(t) = ℓ, J(t) = j | X(0) = k, J(t) = i) (n) (n) (n) (n) n→∞ = P(X(t) = ℓ,J(t) = j | X(0) = k,J(t) = i), t ≥ 0, (k,i;ℓ,j) ∈ F2. From this fact and the ergodicity of Q, we can expect that, in many natural settings, Q has a single closed communicating class in F for all n’s larger than some fi- (n) n nite n ∈ N. Such cases are reduced to the special case where n = 1 by relabeling ∗ ∗ ∪n∗−1L ,L ,L ,... aslevels0,1,2,...,respectively. Thus,forconvenience,weas- ℓ=0 ℓ n∗ n∗+1 sumethat, foreach n ∈ N, Q has asingleclosed communicatingclass in thesub-state (n) spaceF ,whichimpliesthat Qhastheuniqueclosedcommunicatingclassinthewhole n (n) state space F because all the states in F are transient due to Proposition 1.1 (ii). As a n result, Q has the unique stationary distribution vector (see, e.g., Anderson [1, Section (n) 5.4,Theorem 4.5]). Let π := ( π(k,i)) denotetheuniquestationarydistributionvectorof Q, (n) (n) (k,i)∈F (n) which satisfies π Q = 0, πe = 1. (1.3) (n) (n) (n) SinceF istransient,it holds(seeMasuyama[42,Lemma4.2]) that n π(k) = 0 forallk ≥ n+1, (1.4) (n) where (n)π(k) := ((n)π(k,i))i∈Sk∧1 is the subvector of (n)π corresponding to level k. It follows from (1.4) that (1.3) is reduced to a finite dimensional system of equations and thusissolvablenumerically. Therefore, weconsider π tobeacomputableapproxima- (n) tiontothestationarydistributionvectorπ oftheoriginalgeneratorQ. From a practical point of view, it is significant to estimate the error of the approxi- mation π to π, and further, to derive computable error bounds for the approximation (n) π. Several authors have derived computable error bounds for the approximation π. (n) (n) Tweedie [61] and Liu [37] considered the last-column-augmentedtruncation of discrete- timeMarkov chains withoutblock structure, which correspond to the case where S = 0 k for all k ∈ Z in the context of this paper. Tweedie [61] assumed that the original + Markov chain is monotone and geometrically ergodic, and derived a computable upper bound for the total variation distance between the stationary distribution vectors of the original Markov chain and its last-column-augmented truncation. Liu [37] presented a 6 H.Masuyama similarboundundertheassumptionthattheoriginalMarkovchainismonotoneandpoly- nomially ergodic. The monotonicity of Markov chains is crucial to the derivation of the computableboundspresentedin Tweedie[61] andLiu [37]. Without the help of the monotonicity,Herve´ and Ledoux [25] derived an error bound forthestationarydistributionvectorofthelast-column-augmentedtruncationofadiscrete- time Markov chain with geometric ergodicity. However, the computation of Herve´ and Ledoux [25]’s bound needs the second largest eigenvalue of the last-column-augmented truncation and thus the bound is less computation-friendly than the bounds presented in Tweedie [61] and Liu [37]. Masuyama [40, 41] extended the results in Tweedie [61] and Liu [37] to discrete-time block-monotone BSMCs with geometric ergodicity and those with subgeometric ergodicity, respectively. By the uniformization technique (see, e.g., Tijms [59, Section 4.5.2]), the bounds presented in Masuyama [40, 41] are applicable to continuous-timeblock-monotoneBSMCs withboundedinfinitesimalgenerators. There have been some studies on the truncation of continuous-time Markov chains. Zeifman et al. [67] studied the truncation of a weakly ergodic non-time-homogeneous birth-and-death process with bounded transition rates (see also Zeifman et al. [65, 66]). Hart and Tweedie [23] discussed the convergence of the stationary distribution vectors of the augmented northwest-corner truncations of continuous-time Markov chains with monotonicity or exponential ergodicity. Masuyama [42] presented computable upper bounds for the total variation distance between the stationary distribution vectors of a BSMC (with possibly unbounded transition rates) and its LC-block-augmented trunca- tion, under the assumption that the BSMC is block-wise dominated by a Markov chain withblockmonotonicityandexponentialergodicity. In this paper, we do not assume either Q is bounded or block monotone. In addition, we do not necessarily assume that Q has a specified ergodicity, such as exponential er- godicityand polynomialergodicity. Instead, weassumethatQ satisfiesthef-modulated drift condition(seeMeynand Tweedie[45,Equation(7)]and [47, Section14.2.1]): Condition1.1 (f-modulateddrift condition) Thereexistsomeb > 0,K ∈ Z ,column + vectors v := (v(k,i))(k,i)∈F ≥ 0 and f := (f(k,i))(k,i)∈F ≥ esuchthat Qv ≤ −f +b1F , (1.5) K where, for any set C ⊆ F, 1C := (1C(k,i))(k,i)∈F denotes a column vector whose (k,i)th element 1C(k,i) isgiven by 1, (k,i) ∈ C, 1C(k,i) = 0, (k,i) ∈ F\C. (cid:26) Condition 1.1 is the basic condition of this paper. If f = cv for some c > 0, then Condition 1.1 is reduced to the exponential drift condition (i.e., the drift condition for exponential ergodicity; see Meyn and Tweedie [47, Theorem 20.3.2]). On the other hand, if f(k,i) = ϕ(v(k,i)) for some nondecreasing differentiable concave function ErrorBoundsforTruncationsofMarkovChains 7 ϕ : [1,∞) → (0,∞) with lim ϕ′(t) = 0, then Condition1.1 is reduced to the subex- t→∞ ponential drift condition (the drift condition for subexponential ergodicity) presented in Doucet al.[14]. This paper studies the estimate of the absolute difference between the time-averaged functionals of the BSMC {(X(t),J(t));t ≥ 0} and its LC-block-augmented truncation. Let g := (g(k,i))(k,i)∈F denoteanonnegativecolumnvector. It is knownthatifπg < ∞ then the time-average of the functional g(X(t),J(t)) is equal to πg with probability 1 (see, e.g., Bre´maud [9, Chapter8, Theorem6.2]), i.e., 1 T lim g(X(t),J(t))dt = πg withprobability1. T→∞ T Z0 Under Condition 1.1 with different technical conditions, we prove several bounds of twotypes: πg+1 |π − π|g ≤ E(n) foralln ∈ N and 0 ≤ g ≤ f, (1.6) (n) 2 |π − π|g sup (n) ≤ E(n) forall n ∈ N, (1.7) πg 0<g≤f where |·| denotes the vector (resp. matrix) obtained by taking the absolute values of the elements of the vector (resp. matrix) in the vertical bars; and where the function E is called the error decay function and may be different in different bounds. Note here that |πg − πg| ≤ |π − π|g. Note also that (1.5) yields πg ≤ πf ≤ b for 0 ≤ g ≤ f. (n) (n) Thus,from(1.6)and(1.7),weobtaintheboundsfortheapproximation πg tothetime- (n) averaged functionalπg: b+1 |πg − πg| ≤ E(n) for alln ∈ N and 0 ≤ g ≤ f, (n) 2 |πg − πg| sup (n) ≤ E(n) foralln ∈ N. πg 0<g≤f Furthermore, (1.6)(or(1.7))leadsto |π − π|e ≤ E(n), n ∈ N, (n) which isan upperboundforthetotalvariationdistancebetween π and π. (n) We now remark that, as with this paper, Baumann and Sandmann [8] considered a similar condition to Condition 1.1, under which they studied the truncation error of the infinite sum in calculating the time-averaged functional πg. More specifically, they de- rived an upper bound for the relativeerror of the truncated sum π(k,i)g(k,i) to (k,i)∈C thetime-averagedfunctionalπg = π(k,i)g(k,i),where C ⊂ F isa finiteset. (k,i)∈F P The rest of this paper is divided into four sections. In Section 2, we begin with two P factsthatπ− πcanbeexpressedthroughthedeviationmatrixD := (d(k,i;ℓ,j)) (n) (k,i;ℓ,j)∈F2 of the BSMC {(X(t),J(t))} (see (2.2) below); that the deviation matrix D is a solution 8 H.Masuyama of a certain Poisson equation (see (2.1) below). By Dynkin’s formula (see, e.g., Meyn andTweedie[46]),wethenderiveanupperboundfor|D|g underCondition1.1,i.e.,the f-modulated drift condition. Furthermore, using the upper bound for |D|g, we present the bounds of the two types (1.6) and (1.7) in Theorem 2.1 below, which are the founda- tion of the subsequent results of this paper. The error decay function of the fundamental bounds include the implicit factors πv and π. However, if we find two essentially (n) different sets of solutionsto Condition 1.1, say (b,K,v,f) and (b♯,K♯,v♯,f♯) such that lim v(k,i)/f♯(k,i) = 0 for all i ∈ S , then we can remove π from the error k→∞ 1 (n) decay function, which facilitates the qualitative sensitivity analysis of the error decay function. Ontheotherhand,thefactorπv cannotbecomputedbutcanbeestimatedfrom abovewhenQsatisfiestheexponentialdriftcondition. Indeed, ifCondition1.1holdsfor f = cv ≥ e,then(1.5)yieldsπv < b/c. Asaresult,weobtainacomputableerrordecay functionundertheexponentialdriftcondition. In Section 3, we propose a method that reduces the generator Q satisfying Condi- tion 1.1 to be exponentially ergodic. Combining the proposed method and the results in Section 2, we can establish computable error decay functions under the general f- modulated drift condition with some mild technical conditions. As far as we know, such areductionto exponentialergodicityhas notbeen reported intheliterature. In Section 4, we consider LD-QBDs, which emerge as the queue length processes in various state-dependent queues with Markovian environments, such as M/M/s retrial queues and their variants and generalizations (see, e.g., Breuer et al. [10], Dudin and Klimenok [15], Phung-Duc et al. [54, 55]). The study of LD-QBDs and their related queueing models has been a hot topic in queueing theory for the last couple of decades (for an extensive bibliography see, e.g., Artalejo [3, 4], Artalejo and Go´mez-Corral [5]). To demonstrate the usefulness of our error bounds, we apply them to an M/M/s retrial queue and show some numerical results. Furthermore, using the numerical results, we discusstheproperties ofourerror bounds. Finally, in Section 5, we consider the perturbation of the stationary distribution vec- tor π caused by that of the generator Q. The perturbation analysis of Markov chains is closely related to the error estimation of the truncation approximation of Markov chains (see,e.g.,Herve´ andLedoux[25],Liu[39]). Manyperturbationboundshavebeenshown forthestationarydistributionof(time-homogeneous)infinite-stateMarkovchains(Anisi- mov [2], Heidergott et al. [24], Herve´ and Ledoux [25], Kartashov [26, 27, 28], Liu [38, 39], Mitrophanov [48], Mouhoubi and A¨ıssani [50], Tweedie [60], Zeifman and Korolev [64]); though these bounds require specific conditions on ergodicity (such as uniform and exponential ergodicity) and/or include parameters difficult to be identified or calculated (such as the stationary distribution, the ergodic coefficient and other pa- rameters associated with the convergence rate to the steady state). On theother hand, we establishacomputableperturbationboundunderthegeneralf-modulateddriftcondition, by employingthetechnique used to derivetheerror boundsfor theLC-block-augmented truncation. ErrorBoundsforTruncationsofMarkovChains 9 2 Error Bounds for LC-Block-Augmented Truncations This section discusses the error estimation of the time-averaged functions of the LC- block-augmented truncation Q under Condition 1.1. To this end, we focus on the (n) deviation matrix of the Markov chain {(X(t),J(t))}. Using an upper bound associated with the deviation matrix, we derive the fundamental bounds of the two types (1.6) and (1.7). Furthermore, utilizing an additional condition on v and another solution to Con- dition 1.1, we discuss the convergence and simplification of the error decay function of the fundamental bounds. We then consider a special case where Q is an exponentially ergodicgenerator. Inthisspecialcase,weestablishcomputableerrordecayfunctionsand proposea procedureforcomputingthem. 2.1 General case For convenience, we summarize all the assumptions we have made in Section 1, except forCondition1.1. Assumption2.1 Thestochasticprocess{(X(t),J(t))}isanergodicregular-jumpMarkov chainwithinfinitesimalgeneratorQgivenin(1.1). Furthermore,theLC-block-augmented truncation Qhas theuniqueclosedcommunicatingclass inF foreach n ∈ N. (n) n In addition to Assumption 2.1, we assume πv < ∞. It then follows that each ele- ment of ∞|P(t) −eπ|dt is finite (see Meyn and Tweedie [45, Theorem 7]). Based on 0 this, we define D = (d(k,i;ℓ,j)) as the deviation matrix of the Markov chain R (k,i;ℓ,j)∈F2 {(X(t),J(t))},i.e., ∞ D = P(t) −eπ dt. Z0 (cid:0) (cid:1) It is known that the deviation matrix D is a solution to the following Poisson equation (see, e.g., Heidergottet al. [24,Lemma3.1]): −QD = I −eπ withπD = O. (2.1) It isalso known(see Heidergottet al.[24, Section 4.1,Eq. (9)])that π −π = π Q−Q D. (2.2) (n) (n) (n) (cid:0) (cid:1) Therefore, weestimate π −π throughthedeviationmatrixD. (n) To estimate the deviation matrix D, we introduce some symbols. For β > 0, let Φ(β) = (φ(β)(k,i;ℓ,j)) denotea stochasticmatrixsuch that (k,i;ℓ,j)∈F2 ∞ Φ(β) = βe−βtP(t)dt = (I −Q/β)−1 > O, (2.3) Z0 10 H.Masuyama whereΦ(β) > O isduetotheergodicityof{(X(t),J(t))}. ThepositivityofΦ(β) implies thatanyfinitesetC ⊂ Fisapetitesetof{(X(t),J(t))}. Indeed,foranyfinitesetC ⊂ F, let m(β) denotea measureon theBorel σ-algebraB(F) ofF such that C m(β)(ℓ,j) := m(β)({(ℓ,j)}) = min φ(β)(k,i;ℓ,j) > 0, (ℓ,j) ∈ F. C C (k,i)∈C It thenfollowsthat,foranyfiniteset C ⊂ F, φ(β)(k,i;ℓ,j) ≥ m(β)(A), (k,i) ∈ C, A ∈ B(F), (2.4) C (ℓ,j)∈A X whichshowsthatCism(β)-petite(seeMeynandTweedie[47,Sections5.5.2and20.3.3]). C We now define g˘ := (g˘(k,i))(k,i)∈F as a column vector such that 0 ≤ |g˘| ≤ f. From (1.5), wethenhave π|g˘| ≤ πf ≤ b forall 0 ≤ |g˘| ≤ f. (2.5) Thus,itfollowsfrom(2.1)thath := Dg˘ isasolutionofthefollowingPoissonequation: −Qh = g˘−(πg˘)e withπh = 0. (2.6) Lemma 2.1 below presents an upper bound for the solution h = Dg˘ of the Poisson equation(2.6). Lemma 2.1 Suppose that Assumption 2.1 and Condition 1.1 are satisfied. If πv < ∞, then 2b |h| ≤ (|πg˘|+1) v + πv + e forall0 ≤ |g˘| ≤ f, (2.7) (β) " βφ ! # K where φ(β) = sup min φ(β)(k,i;ℓ,j) = sup m(β)(ℓ,j) > 0. (2.8) K (ℓ,j)∈F(k,i)∈FK (ℓ,j)∈F FK Remark 2.1 For continuous-time Markov chains with general state spaces, Glynn and Meyn [19] presented a similar bound, which corresponds to |h| ≤ c (v + e), where 0 c ∈ (0,∞)is anunspecified constant(seeTheorem 3.2therein). 0 (β) Remark 2.2 The bound (2.7) includes the implicit factors |πg˘|, πv and φ . Owing K to (2.5), the first one |πg˘| is bounded from above by b, i.e., |πg˘| ≤ b. Furthermore, if f = cv for some c > 0 (i.e., Condition 1.1 is reduced the exponential drift condition), (β) then the second one πv is also bounded from above by b/c. As for the last one φ , we K willlaterdiscusstheestimationand computationofitin Section 2.2. Proof. For(ℓ,j) ∈ F, leth(ℓ,j) := (h(ℓ,j)(k,i))(k,i)∈F denoteacolumnvectorsuch that τ(ℓ,j) h (k,i) = E g˘(X(t),J(t))dt −(πg˘)E [τ(ℓ,j)], (k,i) ∈ F, (2.9) (ℓ,j) (k,i) (k,i) "Z0 #