Methodology and Computing in Applied Probability, 5, 35±58, 2003 # 2003 Kluwer Academic Publishers. Manufactured in The Netherlands.

Censoring, Factorizations, and Spectral Analysis for Transition Matrices with Block-Repeating Entries YIQIANG Q. ZHAO School of Mathematics and Statistics, Carleton University, Ottawa, Canada K1S 5B6

[email protected]

WEI LI [email protected] Department of Electrical Engineering and Computer Science, University of Toledo, Toledo, OH 43606-3390, USA W. JOHN BRAUN [email protected] Department of Statistical and Actuarial Sciences, University of Western Ontario, London, Canada N6A 5B7 Received April 7, 2000; Revised October 18, 2002; Accepted November 20, 2002 Abstract. In this paper, we use the Markov chain censoring technique to study in®nite state Markov chains whose transition matrices possess block-repeating entries. We demonstrate that a number of important probabilistic measures are invariant under censoring. Informally speaking, these measures involve ®rst passage times or expected numbers of visits to certain levels where other levels are taboo; they are closely related to the so-called fundamental matrix of the Markov chain which is also studied here. Factorization theorems for the characteristic equation of the blocks of the transition matrix are obtained. Necessary and suf®cient conditions are derived for such a Markov chain to be positive recurrent, null recurrent, or transient based either on spectral analysis, or on a property of the fundamental matrix. Explicit expressions are obtained for key probabilistic measures, including the stationary probability vector and the fundamental matrix, which could be potentially used to develop various recursive algorithms for computing these measures. Keywords: block-Toeplitz transition matrices, factorization of characteristic functions, spectral analysis, fundamental matrix, conditions of recurrence and transience AMS 2000 Subject Classification: 60J10, 65C40, 60K25

1.

Introduction

In®nite state Markov chains with block-structured transition matrices constitute a very rich class of stochastic processes, ®nding applications in many areas, including telecommunications, inventory modeling, and queueing systems, for example. Markov chains of GI=M=1 and M=G=1 type are two important special cases which are now very well understood (for example, Neuts, 1980, 1989). The signi®cance of the rate matrix R for the GI=M=1 type case and the matrix G of the fundamental period for the M=G=1 type case has been well documented, and applications of the associated matrix-analytic method are ubiquitous in the literature. Extending matrix-analytic methods to more general block-structured Markov chains has been taken as a challenge by several researchers. Gail et al. (1997) studied non-skip-free GI=M=1 and M=G=1 type Markov chains, obtaining a very useful factorization and

36

ZHAO, LI AND BRAUN

exhibiting the special structure of the R and G matrices for these cases. Grassmann and Heyman (1990, 1993) studied general block-structured transition matrices with the aid of two sequences of matrices which generalize the R and G matrices. We refer to these two sequences as the R and G-measures, respectively. In this paper, we wish to primarily focus on transition matrices having a block-Toeplitz or block-repeating structure. Using the concept of the censored Markov chain which we review in Section 2, we propose to elucidate the properties of the Markov chains generated by such transition matrices. Speci®cally, let fZt ˆ …Xt ; Yt †; t ˆ 0; 1; 2; . . .g be the Markov chain, whose transition matrix P possesses a block structure of the form 3 2 D0 D1 D2 D3





6 D 1 C0 C1 C2





7 7 6 6 D 2 C 1 C0 C1





7 …1† Pˆ6 7; 6 D 3 C 2 C 1 C0





7 5 4 .. .. .. .. .. .. . . . . . . where all Ci for i ˆ 0; +1; +2; . . . are matrices of size m6m, D0 is a matrix of size m0 6m0 and the sizes of all Di for i ˆ +1; +2; . . . are determined accordingly. We are motivated to look at transition matrices having the block-repeating form (1) since they constitute a large class, ®nding numerous applications. In addition, they are a natural generalization of both M=G=1 and GI=M=1 type Markov chains, offering a unifying approach to the study of these very important special cases. In particular, the R and G-measures of Grassmann and Heyman play a crucial role here. We will show that these measures are as important in the study of Markov chains with block-repeating structure as the R and G matrices are in the study of GI=M=1 and M=G=1 type Markov chains. Two other sequences of matrices, carrying probabilistic interpretations and referred to as A and B-measures, are also very useful in the block-repeating context as shown in Zhao et al. (1998). One appealing and useful property of all four sets of measures is their invariance under censoring; this will be elaborated in Section 3. In Section 4, we will demonstrate that the above measures also have a bearing on the study of a particular matrix, called the fundamental matrix, upon which the censoring technique hinges. Some basic characterization results of the Markov chain based on the fundamental matrix will be provided. The stage will then be set to provide, in Section 5, a factorization of the characteristic function of (1) into a product of characteristic functions for the R and G-measures. This is the content of Theorem 14. For matrices of GI=M=1 type and M=G=1 type, we will demonstrate that the factorization obtained by Gail et al. (1997) is equivalent to the factorization obtained here. Characterization results for Markov chains with blockrepeating transition matrices will also be provided in terms of properties of the four probabilistic measures as well as the generalized traf®c intensity. The factorization theorem can also be used to compute the R and G-measures. Other key probabilistic measures, such as the fundamental matrix and the stationary probability vector, can then be ef®ciently determined. Spectral analysis of the R and G matrices has been shown to be very useful in dealing with the GI=M=1 and M=G=1 paradigms (for example, Gail et al., 1996, 1997). We will

CENSORING, FACTORIZATIONS, AND SPECTRAL ANALYSIS

37

show, in Section 6, using the factorization obtained in the preceding section, that spectral analysis of the R and G-measures is also a key to characterize the Markov chains with block-repeating structure. In particular, Theorem 23 gives a general characterization. We close this section with some notational and technical details. The transition matrix P in (1) can be either stochastic or strictly substochastic. By a strictly substochastic matrix we mean that every row sum of the transition matrix is less than or equal to one and there exists at least one row sum which is strictly less than one. The only extra condition imposed is irreducibility, though this condition may not be essential for all of the results presented in this paper. Corresponding results for continuous time Markov chains can be obtained in parallel.

2.

Review of Censoring and the R and G-Measures

The censoring technique (for example, Kemeny et al., 1976; Grassmann and Heyman, 1990; Zhao and Liu, 1996; or Zhao et al., 1998) has been used in the literature in studying various aspects of Markov chains. It should be noted that stochastic complementation (for example, Meyer, 1989) and censoring are synonymous. Censoring can be applied to an arbitrary stochastic process. However, we ®nd that it is most effectively exploited in the context of Markov chains. Consider a discrete-time irreducible Markov chain fXn ; n ˆ 1; 2; . . .g with state space S. Let E be a non-empty subset of S. Suppose that the successive visits of Xn to E take place at time epochs 0 < n1 < n2 <


. Then the process fXtE ˆ Xnt ; t ˆ 1; 2; . . .g is de®ned as the censored process with censoring set E. Alternatively, the n-th transition of the censored process is the n-th time for the Markov chain to visit a state in E. From this de®nition, it follows that sample paths of the censored process are the paths of the original Markov chain whose transitions in the complementary set, Ec , have been deleted. Using the strong Markov property, it can be proved that the censored process is also a Markov chain, called the censored Markov chain. This new process has also been variously called the restricted, watched or embedded Markov chain. If P is the transition matrix of the original Markov chain fXn ; n ˆ 1; 2; . . .g, we can partition P according to subsets E and Ec : c E E  T U : P ˆ Ec E V Q

…2†

The transition matrix, PE , of the censored Markov chain is then given by b PE ˆ T ‡ U QV; …3† P ? k bˆ b with Q k ˆ 0 Q . The matrix Q is called the fundamental matrix. b in (3), we Since our later results are intimately related to the behavior of the term U QV pause to carefully review some probabilistic interpretations. In the following, Ci; j stands for the …i; j†-th entry in a matrix C, and the process referred to is the original Markov chain.

38

ZHAO, LI AND BRAUN

b is the expected number of visits to state j [ Ec before entering E, given that the 1. …Q† i; j process started in state i [ Ec . b is the expected number of visits to state j [ Ec before returning to E, given 2. …U Q† i; j that the process started in state i [ E. b 3. …QV† i; j is the probability that the process enters E, and upon entering E, the ®rst state visited is j [ E, given that the process started in state i [ Ec . b 4. …U QV† i; j is the probability that, upon returning to E, the ®rst state visited is j [ E, given that the process started in state i [ E. We now set up the required notation in order to de®ne the R and G-measures. We begin with an arbitrary block-partitioned transition matrix, stochastic or strictly substochastic: 2 3 P0;0 P0;1 P0;2





6 P1;0 P1;1 P1;2





7 6 7 …4† P ˆ 6 P2;0 P2;1 P2;2





7; 4 5 .. .. .. .. .. . . . . . where Pi;i , for i ˆ 0; 1; . . . , is a matrix of size mi 6mi . Here, the state space S has been partitioned as Sˆ

? [ iˆ0

Li ;

…5†

with Li ˆ f…i; 1†; …i; 2†; . . . ; …i; mi †g:

…6†

For the state …i; r†, i is called the level variable and r the stage or phase variable. We also use the notation L i ˆ

i [ kˆ0

Lk ;

…7†

for the set of all states in levels up to i, and L i denotes the complement of L …i 1† . We also note that, in what follows, if E ˆ L n , then the censored transition matrix, PE , will be denoted by P‰ nŠ. If E ˆ L0 , then PE is denoted by P‰0Š. For 0  i  j, Ri; j is an mi 6mj matrix whose …r; s†-th entry is the expected number of visits to state … j; s† before hitting any state in L … j 1† , given that the process starts in state …i; r†. For i > j  0, Gi; j is an mi 6mj matrix whose …r; s†-th entry is the probability of hitting state … j; s† when the process enters L …i 1† for the ®rst time, given that the process starts in state …i; r†. It should be emphasized that the R-measure is de®ned for i ˆ j, but the G-measure is not. Using the probabilistic interpretations 2 and 3 above, we can establish useful relations b To accomplish this, we between the R and G measures and the fundamental matrix Q. re-partition the matrix P according to L …n 1† , Ln and L …n ‡ 1† :

39

CENSORING, FACTORIZATIONS, AND SPECTRAL ANALYSIS

2

T P ˆ 4 V0 V1 Let



Q0 Qˆ V2

U0 Q0 V2

3 U1 U2 5: Q1

…8†

 U2 ; Q1

b be partitioned accordingly: let Q   H1;1 H1;2 b ; Qˆ H2;1 H2;2 t

and let R< n ˆ …R0;n ; R1;n ; . . . ; Rn 1;n † , where the superscript t stands for the transpose of the matrix. From the second probabilistic interpretation above, it is clear that   H1;1 R< n ˆ …U0 ; U1 † ; …9† H2;1 and using an obvious extension,   H1;1 : Rn;n ˆ …Q0 ; U2 † H2;1

…10†

Similarly, if we let G< n ˆ …Gn;0 ; Gn;1 ; . . . ; Gn;n interpretation can be applied to obtain   V G< n ˆ …H1;1 ; H1;2 † 0 : V1

1 †,

then the third probabilistic …11†

In the block-repeating case (1), the matrices Ri; j and Gi; j only depend on the value of ji jj except for R0; j and Gi;0 (for example, Grassmann and Heyman, 1990 or Zhao et al., 1998). We then de®ne Rk ˆ Ri; j ; for k ˆ 0; 1; . . . ; with k ˆ j

i and j  i > 0;

…12†

Gk ˆ Gi; j ; for k ˆ 1; 2; . . . ; with k ˆ i

j and i > j > 0:

…13†

and All Rk and Gk have a common size m6m.

3.

Invariance of Measures Under Censoring

As mentioned in the Introduction, the censoring technique will be used to attain a uni®ed treatment of transition matrices with block-repeating entries. In this section, we provide some properties of censoring that move us toward this goal. We prove that both the R and G-measures are invariant under censoring. This invariance property plays an important role in derivations dealing with matrices with block-repeating property.

40

ZHAO, LI AND BRAUN

We also show that two other sequences of matrices, the A and B-measures, are invariant under censoring. These measures have probabilistic signi®cance; for example, the stationary probability vector p for a positive recurrent Markov chain or the generalized stationary vector for a null recurrent Markov chain is essentially equivalent to the Ameasure. The section concludes with a result on the invariance of the fundamental matrix under censoring. We begin by collecting a number of useful basic properties of the censored Markov chain. LEMMA 1 Let P be the transition matrix of a Markov chain, which is possibly strictly substochastic, and let E be a subset of the state space. Then, i. ii. iii. iv. v. vi.

P is irreducible if and only if PE is irreducible for all E. P is recurrent if and only if PE is recurrent for all E. P is transient if and only if PE is transient for all E. if P is irreducible, then P is recurrent if and only if PE is recurrent for some E. if P is irreducible, then P is transient if and only if PE is transient for some E. E for E1 ( E2 , PE1 ˆ …PE2 † 1 .

This lemma can be proved easily using the sample path structure of the censored Markov chain, and we omit the details. It is also possible to provide proofs of the invariance properties given later using sample path arguments. However, we prefer to use the expression for the fundamental matrix in partitioned form given in the next lemma (Lemma 2), since it leads to proofs which tie in with the probabilistic interpretations developed earlier. This lemma is also very useful in developing recursive expressions for the R and G-measures; such expressions have potential to be developed into computational schemes for these measures. LEMMA 2 Let Q be a transition matrix with state space S and all states transient. Let E be any non-empty subset of S and let Q be partitioned according to E and its complement Ec :   Q0 U Qˆ : V Q1 P i Then, the fundamental matrix Q^ ˆ ? i ˆ 0 Q is given by   1 1 …I Q0 U Q^1 V† U Q^1 …I Q0 UQ^1 V† ^ Qˆ : …14† Q^1 V…I Q0 UQ^1 V† 1 Q^1 ‡ Q^1 V…I Q0 U Q^1 V† 1 U Q^1 where I is an identity matrix and …I X† inverse of I X if the inverse is not unique.

1

ˆ

P?

iˆ0

Xi is the minimal non-negative

Let Q^ be partitioned according to E and Ec as   H1;1 H1;2 Q^ ˆ : H2;1 H2;2

Proof:

Q^ is the minimal non-negative solution for X of the matrix equation …I (Proposition 5-11 of Kemeny et al., 1976); or

Q†X ˆ I

41

CENSORING, FACTORIZATIONS, AND SPECTRAL ANALYSIS

…I

Q0 †X1;1

VX1;1 ‡ …I …I

UX2;1 ˆ I;

…15†

Q1 †X2;1 ˆ 0;

…16†

UX2;2 ˆ 0;

…17†

Q1 †X2;2 ˆ I;

…18†

Q0 †X1;2

VX1;2 ‡ …I

when X is partitioned according to E and Ec into   X1;1 X1;2 Xˆ : X2;1 X2;2 Equation (16) is equivalent to …I Kemeny et al. (1976) that X2;1 ˆ …I

Q1 †

1

Q1 †X2;1 ˆ VX1;1 . It follows from Proposition 5-11 of

VX1;1 ;

…19†

is the minimal solution of (16) for a ®xed X1;1 , where P non-negative i …I Q1 † 1 ˆ ? Q1 . Therefore, i ˆ 0 Q1 is the minimal non-negative inverse of I H2;1 ˆ …I Q1 † 1 VX1;1 if X1;1 is the minimal non-negative solution of (15). Using (19) in (15), we have …I Q0 †X1;1 U…I Q1 † 1 VX1;1 ˆ I or fI ‰Q0 ‡ U 1 …I Q1 † VŠgX1;1 ˆ I. This implies that H1;1 ˆ ‰I

Q0

U…I

Q1 †

1

Q1 †

1

VŠ

1

and hence H2;1 ˆ …I

V‰I

Q0

VŠ

1

U…I

Q1 †

1

U…I

Q1 †

1

U…I

Q1 †

1

:

We can similarly prove that H1;2 ˆ ‰I

Q0

U…I

H2;2 ˆ …I

Q1 †

1

Q1 †

1

VŠ

1

and fI ‡ V‰I

Q0

VŠ

1

U…I

Q1 †

1

g:

j

For convenience, we put a symmetric expression for Q^ in the following corollary. P? COROLLARY 3 The fundamental matrix Q^ ˆ i ˆ 0 Qi can be also expressed by   1 1 Q^0 ‡ Q^0 U…I Q1 V Q^0 U† V Q^0 Q^0 U…I Q1 V Q^0 U† Q^ ˆ : …20† 1 1 …I Q1 V Q^0 U† V Q^0 …I Q1 V Q^0 U† REMARK 1 The matrix Q in the above lemma could be either stochastic or strictly substochastic. The expressions in (14) and (20) are well known if the size of the matrices involved are all ®nite. We are now ready to demonstrate that the R and G-measures are invariant under censoring. THEOREM 4 For an arbitrary Markov chain whose transition matrix P is partitioned according to levels as in (4), let Ri; j and Gi; j be the R and G-measures, respectively,

42

ZHAO, LI AND BRAUN ‰ nŠ

‰ nŠ

de®ned for the Markov chain P, and let Ri; j and Gi; j be the R and G-measures, respectively, de®ned for the censored Markov chain with censoring set L n . For given 0 ˆ i < j or 1  i  j, ‰ nŠ

Ri; j

ˆ Ri; j ;

…21†

for all n  j; and for given 0  j < i, ‰ nŠ

Gi; j

ˆ Gi; j ;

…22†

for all n  i. Proof: We only prove the ®rst result; the second can be proved similarly. First, assume n ˆ j, and let P be re-partitioned according to L …n 1† , Ln and L …n ‡ 1† as ^ and R< n as in the displays subsequent to (8). Applying (9) together in (8), and de®ne Q, Q, with (14), it becomes clear that ! 1 …I Q0 U2 Q^1 V2 † R< n ˆ …U0 ; U1 † ^ ; Q1 V2 …I Q0 U2 Q^1 V2 † 1 and similarly, using (10) with (14), we have Rn;n

1 …I Q0 U2 Q^1 V2 † ˆ …Q0 ; U2 † ^ Q1 V2 …I Q0 U2 Q^1 V2 †

! :

1

On the other hand, the censored matrix with censoring set L n is given by   T ‡ U1 Q^1 V1 U0 ‡ U1 Q^1 V2 ‰ nŠ ˆ P : V0 ‡ U2 Q^1 V1 Q0 ‡ U2 Q^1 V2 Therefore, ‰ nŠ R< n ˆ …U0 ‡ U1 Q^1 V2 †…I

where

‰ nŠ R< n

ˆ

Q0

U2 Q^1 V2 †

‰ nŠ ‰ nŠ ‰ nŠ t …R0;n ; R1;n ; . . . ; Rn 1;n † .

nŠ ^ R‰ n;n ˆ …Q0 ‡ U2 Q1 V2 †…I

Q0

1

;

Similarly,

U2 Q^1 V2 †

1

:

‰ nŠ Ri;n

Now, Ri;n ˆ for all i  n. The above result, together with (vi) of Lemma 1, implies that (21) is also valid for n > j. In fact, if n > j, we censor the matrix P ®rst using the censoring set L j and we know ‰ jŠ Ri; j ˆ Ri; j . Next, censor the matrix P using the censoring set L n . It follows from (vi) of Lemma 1 that the censored matrix P‰ jŠ can be obtained by censoring P‰ nŠ using the ‰ nŠ ‰ jŠ censoring set L j and therefore Ri; j ˆ Ri; j , the fact just proved above (using P‰ nŠ in place of P ). j REMARK 2 That the R and G-measures are invariant under censoring was observed by Grassmann and Heyman (1990); they also provided a proof to a special case of the above theorem.

CENSORING, FACTORIZATIONS, AND SPECTRAL ANALYSIS

43

As we mentioned earlier, one of the advantages of introducing the R and G-measures is that they can be used to express other interesting measures. For an arbitrary Markov chain de®ned by (4), we de®ne the A and B-measures as follows. For i  0 and j  0 with i 6ˆ j, de®ne Ai; j to be a matrix of size mi 6mj whose …r; s†-th entry is the expected number of visits to state … j; s† before hitting any state in level i, given that the process starts in state …i; r†. For i  0 and j  0, de®ne Bi; j to be a matrix of size mi 6mj . When i 6ˆ j, the …r; s†-th entry of Bi; j is the probability of visiting state … j; s† for the ®rst time before hitting any state in level j, given that the process starts in state …i; r†. When i ˆ j, the …r; s†-th entry of Bi; j is the probability of returning to level j for the ®rst time by hitting state … j; s†, given that the process starts in state …i; r†. For the purpose of this paper, it suf®ces to consider Ai; j for a ®xed i and Bi; j for a ®xed j only. Without loss of generality, we consider only Aj ˆ A0; j and Bi ˆ Bi;0 . To begin to see why the A and B-measures are important, consider the following. In the scalar case, the stationary probability vector p satis®es p ˆ c…1; A1 ; A2 ; . . .†, where c is a normalization constant, when the chain is positive recurrent. In fact, for a recurrent chain, …1; A1 ; A2 ; . . .† is the unique solution, up to multiplication by a constant, of the stationary equations x ˆ xP. In the block case, let the stationary probability vector be partitioned according to levels: p ˆ …p0 ; p1 ; p2 ; . . .†. Then, p ˆ p0 …I; A1 ; A2 ; . . .†, where p0 is the unique solution, up to multiplication by a constant, of p0 ˆ p0 P‰0Š , where I is an identity matrix and P‰0Š is the censored matrix to level 0. p0 can be viewed as the vector-valued normalization constant. The B-measure is a dual of the A-measure. The following recursive formulas for computing the A and B-measures in terms of the R and G-measures were derived by Zhao et al. (1998) when all the block entries have a common size. Their proof can be easily extended to the case of different block sizes. LEMMA 5 Matrices An and Rk;n satisfy 8 if n ˆ 1; < R0;1 ; nP1 An ˆ Ak Rk;n ; if n  2; : R0;n ‡

…23†

kˆ1

and matrices Bn and Gn;k satisfy 8 < G1;0 ; nP1 Bn ˆ Gn;k Bk ; : Gn;0 ‡ kˆ1

if n ˆ 1; if n  2:

:

…24†

As a consequence of Theorem 4 and the above lemma, the A and B-measures are invariant under censoring, as stated in the following corollary. COROLLARY 6 Let Aj and Bi be the respective A and B-measures for a Markov chain ‰ nŠ ‰ nŠ having a transition matrix of the form (4), and let Aj and Bi be the A and B-measures, respectively, de®ned for the censored Markov chain with censoring set L n . For given i and j, ‰ nŠ

Aj

ˆ Aj ;

for all n  j and

…25†

44

ZHAO, LI AND BRAUN ‰ nŠ

Bi

ˆ Bi ;

…26†

for all n  i. When the transition matrix P has the property of repeating blocks as in (1) the result in Lemma 5 can be simpli®ed as follows. COROLLARY 7 For the Markov chain whose transition matrix is given as in (1), matrices An and Bn satisfy 8 if n ˆ 1, < R0;1 ; nP1 An ˆ …27† An k Rk ; if n  2, : R0;n ‡ kˆ1

and Bn ˆ

8 < G1;0 ; : Gn;0 ‡

nP1 kˆ1

if n ˆ 1, Gk Bn

k;

if n  2,

…28†

where Rk and Gk are de®ned as in (12) and (2). It follows from the relations in (9), (10) and (11) that the fundamental matrix Q^ contains essential information about the R and G-measures, and therefore about the A and Bmeasures. Thus, the fundamental matrix merits study in its own right; this we do in the next section, but we ®rst conclude this section by showing that the values in a fundamental matrix are invariant under censoring. THEOREM 8 Let Q be a stochastic or strictly substochastic transition matrix with state spaceP S and all states transient, and let qi; j be the …i; j†-th entry of the fundamental matrix k E Q^ ˆ ? k ˆ 0 Q . Let E be any subset of S containing states i and j, and let Q be the censored matrix with censoring set E. Then, the entry corresponding to states i and j of the cE ˆ P? …QE †k for the censored matrix QE is equal to q . fundamental matrix Q i; j kˆ0 Partition Q according to E and the complement Ec of E:   Q0 U Qˆ : V Q1

Proof:

cE ˆ …I Q b1 V and Q b1 V† 1 , which is equal to the block UQ Then, QE ˆ Q0 ‡ U Q 0 ^ corresponding to E in the fundamental matrix Q according to Lemma 2. j

4.

The Fundamental Matrix

Since the factorization formula will emerge from analysis of the fundamental matrix, and because of already-noted connections with the probabilistic measures de®ned earlier, we use this section to state some additional basic properties of the fundamental matrix. In this section, we will give determinations of the fundamental matrix based on the R and

CENSORING, FACTORIZATIONS, AND SPECTRAL ANALYSIS

45

G-measures, and on the A and B-measures, and we provide necessary and suf®cient conditions for P to be positive recurrent or transient. Consider the irreducible Markov chain de®ned by (1) and let Q be the matrix obtained after deleting the boundary blocks of (1): 2 3 C0 C1 C2





6 C 1 C0 C1





7 6 7 …29† Q ˆ 6C 7: 2 C 1 C0





5 4 .. .. .. .. .. . . . . . b ˆ P? Qi is ®nite (see Proposition 5-3 of Kemeny et al., The fundamental matrix Q iˆ0 b are explicitly related to the R and G measures. 1976). The entries of Q b ˆ …qi; j † THEOREM 9 Let Q i; j [ f1;2;...g , where qi; j are matrices of size m6m. Then, the entries qi; j are determined according to 8 iP1 > > Gi k qk; j ; i>j > > > kˆ1 > > < iP1 P Gi k qk; j ˆ q1;1 ‡ jk ˆ11 qi; k Rj k ; i ˆ j qi; j ˆ q1;1 ‡ > kˆ1 > > > jP1 > > > qi;k Rj k ; i < j: : kˆ1

REMARK 3 In the above theorem, Ri; j and Gi; j are the same R and G-measures for both P in (1) and Q in (29). Proof: Suppose i > j. In order to visit level j, [ik ˆ11 Lk has to be visited ®rst. Conditioning on the ®rst visit to [ik ˆ11 Lk , we see that i 1X m X

qi; j …r; s† ˆ

kˆ1 tˆ1

Gi;k …r; t†qk; j …t; s†;

and because Gi;k ˆ Gi k , the result follows. When i < j, the equation can be proved by using the duality results obtained in Zhao et al. (1999). Speci®cally, let Q ˆ …Qi; j † be the matrix given in (29) and let Q~ ˆ …Q~i; j † be its dual with Q~i; j ˆ diag

1

…p†Qtj;i diag…p†;

whereP diag…p† is the diagonal matrix of the invariant probability vector p of t Cˆ ? stands for the transpose of a matrix. The fundamental matrix i ˆ ? Ci and ^ ~ ~ Q ˆ …~ qi; j † for Q can be expressed as ^~ ˆ diag Q

1

…p†Q^t diag…p†:

Now, it follows from the i > j case that

46

ZHAO, LI AND BRAUN

q~j;i ˆ

j 1 X

G~j

kˆ1

~k;i : kq

Therefore, diag

1

…p†qti; j diag…p† ˆ

j 1 X kˆ1

diag

1

…p†Rtj

t k qi;k diag…p†;

from which it easily follows that qi; j ˆ

j 1 X kˆ1

qi;k Rj

k:

When i ˆ j, the ®rst equation can be obtained using conditioning arguments. In this case, qi;i can be partitioned into two parts. The ®rst part is the number of visits to level i without visiting any level below level i, which is equal to q1;1 because of the repeating property, and the second part is the number of visits to level i by visiting some level below i ®rst, which has the same expression as the ®rst equation in this theorem. The second equality can then be proved using duality results. j To determine all other entries qi; j ; q1;1 is needed. To proceed, we de®ne F0 as the m6m matrix whose …r; s†-th entry is the probability of hitting state …n; s† when the process enters L n for the ®rst time without counting the initial state, given that the process starts in state …n; r†. Later in the paper, we show that F0 is the same as the southeast block in any ‰ nŠ censored matrix, or F0 ˆ Pn;n for any n  1. The relationship between q1;1 and F0 is a special case of Theorem 8. COROLLARY 10 When the censoring set is L1 , we have q1;1 ˆ …I

F0 †

1

.

The fundamental matrix can also be expressed in terms of the A and B-measures. Let S ˆ [? i ˆ 1 Li be the state space of Q. De®ne the A and B-measures for Q. To distinguish the measures de®ned for Q from those for P, we use a bar; for example, we use Ai; j (i  1; j  1 and i 6ˆ j) and Bi; j (i  1 and j  1) to denote the A and B-measures of Q. Since Ri and Gi ; i  0, de®ned for P are independent of the boundary probabilities Di , Rk ˆ Rk

Gk ˆ Gk ;

and

k ˆ 1; 2; . . . :

In this case, the equations given in Corollary 7 become COROLLARY 11 Ak ˆ

kX1 iˆ0

Ai Rk

i

…30†



…31†

and Bk ˆ

kX1 iˆ0

Gk

i Bi ;

where A0 ˆ B0 ˆ I; Ak ˆ A1;k ‡ 1 and Bk ˆ Bk ‡ 1;1 .

47

CENSORING, FACTORIZATIONS, AND SPECTRAL ANALYSIS

The relation between the fundamental matrix and the A and B-measures is then as follows. THEOREM 12 8 iP1 > > > Bk q1;1 Aj i ‡ k ; < kˆ0 qi; j ˆ j 1 P > > > Bi j ‡ k q1;1 Ak ; : kˆ0

Proof:

5.

1ij 1  j  i:

This can be inductively proved using Theorem 9 and Equations (30) and (31). j

Factorization Theorems

In this section, we prove the factorization theorem, one of the main results of this paper. This factorization simpli®es spectral analysis for block-repeating transition matrices, allowing for characterization of the associated Markov chains based on the spectrum of the R and G-measures de®ned in Section 2. A by-product of the factorization theorem is an alternative proof to a very useful condition for characterizing Markov chains, originally obtained using the concept of a Markov-modulated random walk by Asmussen (1987). Note that the transition matrix in (1) contains two regimes, one given by the repeating blocks: Ci , and the other by the boundary blocks: Di . The natural way of studying this class of matrices is to study properties pertaining only to the repeating blocks, and then to study the matrix as a whole. The latter part of this section is devoted to this analysis. We consider only the transition matrix with block-repeating entries P? given in (1). Besides the irreducibility imposed on P, we assume that both P and C ˆ i ˆ ? Ci are stochastic, and C is irreducible. We will not discuss the case where C is strictly substochastic in detail, partly because when C is strictly substochastic, P is automatically positive recurrent. The case where C is reducible can be studied by expressing C in a standard form consisting of irreducible blocks (see Gail et al., 1997 for such a treatment of the GI=M=1 and M=G=1 paradigms). For the R and G-measures, we de®ne the generating functions in block-form: ? X R…z† ˆ Ri z i …32† iˆ1

and G…z† ˆ

? X iˆ1

Gi z

i

:

…33†

We also de®ne the generating function for the repeating blocks Ci : ? X Ci zi : C…z† ˆ iˆ

…34†

?

‰ nŠ i;n

Generalizing the matrix F0 de®ned earlier, we de®ne Fi ˆ Pn

and F

j

‰ nŠ

ˆ Pn;n

j

for

48

ZHAO, LI AND BRAUN

all n > 0 and 0  i; j  n 1. It follows from Theorem 4 that Ri ˆ Fi …I F0 † 1 for 0  i  n 1 and Gj ˆ …I F0 † 1 F j for 1  j  n 1. For convenience, we de®ne 1 G0 ˆ …I F0 † F0 . However, G0 does not have the same probabilistic interpretation as Gi for i  1. In fact, from the expression of R0 and the de®nitionP of G0 we can easily see 1 ? that R0 ˆ G0 upon expansion of the inverse into …I F0 † ˆ i ˆ 0 Fi0 . In the proof of the factorization theorem, we shall make use of the following important result given by Grassmann and Heyman (1990): LEMMA 13 For the transition matrix given in (1), Ri …I

F0 † ˆ Ci ‡

? X kˆ1

Ri ‡ k …I

F0 †Gk ;

i  0;

…35†

and F0 †Gj ˆ C

…I

j

‡

? X kˆ1

Rk …I

F0 †Gj ‡ k ;

j  0:

…36†

Since G is either stochastic or strictly substochastic (see Theorem 3.4 of Zhao et al., 1998), R < ? (see Lemma 8 of Zhao et al., 1999) and C is stochastic, the characteristic functions I R…z†; I G…z† and I C…z† can be in general de®ned at least for z in a open annulus containing the unit circle in its interior: z1 < jzj < z2 for some 0 < z1  1 and z2  1. The following is the main factorization result. THEOREM 14 For the characteristic functions I C…z†; I R…z† and I G…z† de®ned for the transition matrix P given in (1) with both P and C stochastic and irreducible, I Proof:

C…z† ˆ ‰I

R…z†Š…I

F0 †‰I

G…z†Š:

…37†

It follows from Lemma 13 and direct algebraic manipulations that

C ˆ …I R†…I F0 †…I G† ‰I R…z†Š…I F0 †‰I G…z†Š; P? P? P? where C ˆ C…1† ˆ k ˆ ? Ck ; R ˆ R…1† ˆ k ˆ 1 Rk and G ˆ G…1† ˆ k ˆ 1 Gk . It is suf®cient for us to prove I C ˆ …I R†…I F0 †…I G†; or C…z†

C ‡ R…I

F0 †G

F0

…I

F0 †G

R…I

F0 † ˆ 0:

By summing the equations in (35) and (36), we have ? X iˆ0

Ri …I

F0 † ˆ

? X iˆ0

Ci ‡

? X ? X iˆ0 kˆ1

Ri ‡ k …I

F0 †Gk

…38†

F0 †Gi ‡ k :

…39†

and ? X

…I

iˆ1

F0 †Gi ˆ

? X iˆ1

C

i‡

? X ? X iˆ1 kˆ1

Rk …I

Adding the above two equations leads to R0 …I

F0 † ‡ R…I

F0 † ‡ …I

which gives the result, since R0 …I

F0 †G ˆ C ‡ R…I F0 † ˆ F0 .

F0 †G; j

CENSORING, FACTORIZATIONS, AND SPECTRAL ANALYSIS

49

This factorization was obtained by Grassmann (1985) for the scalar case, presented in a slightly different form. Dukhovny (1989a, 1989b, 1990) studied the scalar case, which was called a quasiToeplitz transition matrix, by identifying it with a Riemann boundary value problem. This gives some indication of the dif®culties this class of matrices induces even for the scalar case. Upon close examination of the key expression obtained by Dukhovny for the generating function, we ®nd that it is essentially equivalent to the factorization given in (37). For the block case, a factorization, which will be shown equivalent to (37) later in this section, was obtained by Gail et al. (1997) for Markov chains of GI=M=1 type or M=G=1 type. Since these kinds of Markov chains can be characterized solely in terms of the R or G matrix, the clari®cation of the probabilistic structure of the other factor in the factorization is not necessary. We also note that the R and G-measures provide a minimal nonnegative solution to the factorization matrix equation. This fact was proved by Grassmann and Heyman (1990). Let I C…z† be the characteristic function of the blocks Ci of the transitionP matrix P given ? in (1) with both P and C stochastic and irreducible. Let I X…z† ˆ I Xi zi be a iˆ P1 ? i matrix function in z of size m6m de®ned in 0 < jzj < z2 . Let I Y…z† ˆ I i ˆ 1 Yi z be another matrix function in z of size m6m de®ned in z1 < jzj < ?. And let I Z be a matrix of size m6m. Then the matrices Ri , F0 and Gi , i ˆ 1; 2; . . . , de®ned for P, are the minimal non-negative solution of I

C…z† ˆ ‰I

X…z†Š…I

Z†‰I

Y…z†Š:

This means that if X…z†  0, Y…z†  0 and Z  0 are another non-negative solution of the equation, then X…z†  R…z†, Y…z†  G…z† and Z  F0 . We turn now to a characterization involving the generalized traf®c intensity. For a queueing system, the traf®c intensity can often be de®ned as the ratio of the total arrival rate to the total service rate. The fact that a system is stable if and only if the traf®c intensity is less than one can then be established in many cases. Such a condition is usually easier to examine than other conditions, in practice. For Markov chains of GI=M=1 and M=G=1 type, Neuts (1981, 1989) obtained necessary and suf®cient conditions for ergodicity. These conditions can be viewed as a generalization of those in terms of the traf®c intensity. For the transition matrix in (1), Asmussen (1987) obtained a necessary and suf®cient condition for the process to be positive recurrent, null recurrent or transient, using properties of two dimensional random walks and the drift of Markov chains. Here, we use the factorization to give an alternative proof of the conditions proved by Asmussen. Theorem 9 of Zhao et al. (1999) will be used in the proof, and we state it here. The mvector of ones is denoted by e. THEOREM 15 For (1), let p be the stationary P the Markov chain P de®nedPby P? probability ? vector of C ˆ ? C . Assume that p kC e < ? and k kˆ ? k kˆ ? k ˆ 1 kDk < ?, where e is a column vector of ones. Then, i. P is positive recurrent if and only if pR  p; ii. P is transient if and only if Ge  e; and iii. P is null recurrent if and only if pR ˆ p and Ge ˆ e.

50

ZHAO, LI AND BRAUN

Here, a  b means that each element of a is less than or equal to the corresponding element of b and there is at least one element of a strictly less than the corresponding element of b. THEOREM 16 For (1), let p be the stationary P the Markov chain P de®nedPby P? probability ? vector of C ˆ ? C . Assume that p kC e < ? and k kˆ ? k kˆ ? k ˆ 1 kDk < ?, where e is a column vector of ones. Let P? p kC e r ˆ P?k ˆ 1 k : p k ˆ 1 kC k e Then, i. P is positive recurrent if and only if r < 1; ii. P is transient if and only if r > 1; and iii. P is null recurrent if and only if r ˆ 1. Proof:

p

Take the derivative of the factorization Equation (37), which gives ? X kˆ1

kCk e

p

? X kˆ1

kC

ke

ˆp

? X kˆ1

! kFk …e

Ge†

…p

pR†

? X

! kF

kˆ1

k

e:

P Since P is irreducible, there is no zero column in k Fk and there is no zero row in P j k F k . The rest of the proof follows directly from Theorem 15. REMARK 4 This result is basically a mean drift theorem of the Markov chain (for example, refer to Theorem 7.2.3 of Latouche and Ramaswami, 1999). Another purpose in developing the factorization theorem is to study properties pertaining to the repeating blocks only, studying the matrix at (29); then we can study the matrix (1) as a whole. The rest of this section explores properties of the Markov chain in this direction. The following theorem gives a necessary and suf®cient condition for classifying Markov chains with repeating blocks. THEOREM 17 Let Ak , Bk , Rk and G-measures de®ned for the matrix P Gk be the A, B, R Pand ?      Q as de®ned at (29). Let A ˆ ? i ˆ 0 Ai and B ˆ i ˆ 0 Bi , where A0 ˆ B0 ˆ I. Then i. ii. iii.

A < ? if and only if limk ? ? Rk ˆ 0; B < ? if and only if limk ? ? Gk ˆ 0; and A ˆ ? and B ˆ ? if and only if limk ? ? Rk 6ˆ 0 and limk ? ? Gk 6ˆ 0.

Proof: (iii) is a direct consequence of (i) and (ii). To prove (i), ®rst assume A < ?. It  Hence, I R is invertible. Equivalently, follows from Equation (30) that A ˆ I ‡ AR. Rk ? 0 as k ? ?. To prove the other half of (i), using Equation (30) write

51

CENSORING, FACTORIZATIONS, AND SPECTRAL ANALYSIS M X nˆ1

An ˆ ˆ

M nX1 X nˆ1 kˆ0 M X1 kˆ0

Ak

 A0 R ‡

Ak Rn M X

nˆk‡1 M X1 kˆ1

k

Rn

k

Ak R:

…40†

Repeated application of (40) with A0 ˆ I gives M X nˆ1

An  R ‡ R2 ‡


‡ RM  …I

R†

1

< ?;

since Rk ? 0 as k ? ?. (ii) follows for the same reason as (i).

j

We can now prove the following characterization in terms of the fundamental matrix. P THEOREM 18 Let P be the transition matrix in (1) and assume that ? k ˆ 1 kDk < ?. Then, P i. P is positive recurrent if and only if for any i, ? j ˆ 1 qi; j < ?; P? ii. P is transient if and only if for any j, i ˆ 1 qi; j < ?; andP ? iii. P is null recurrent ifP and only if there exists an i such that j ˆ 1 qi; j ˆ ? and there ? exists a j such that i ˆ 1 qi; j ˆ ?. Proof: (iii) is a direct consequence of (i) and (ii). To prove (i) and (ii), use Theorem 12 and rearrange the terms in the summation. This leads to ! ! ! ? i 1 ? i 1 X X X X Bk q1;1 Bk q1;1 A Ak ˆ qi; j ˆ jˆ1

kˆ0

? X

? X

kˆ1

and

iˆ1

qi; j ˆ

kˆ0

! Bk q1;1

j 1 X kˆ1

kˆ0

! Ak

 1;1 ˆ Bq

The conclusion now follows from Theorem 17.

j 1 X kˆ0

! Ak : j

The following lemma provides recursive formulas for computing R and G-measures in terms of B and A-measures, respectively. LEMMA 19 Let Rn , n  0, and Gn , n  1, be de®ned for P as in (1), and let Ai and Bi , i  1, be de®ned for Q given at (29). Then, Rn …I and

F0 † ˆ

? X iˆ0

Cn ‡ i Bi

…41†

52

ZHAO, LI AND BRAUN

…I

F0 †Gn ˆ

? X iˆ0

Ai C

i:

n

…42†

Proof: First, note that the …r; s†-th element of Fn equals the transition probability from state …1; r† to state …n ‡ 1; s† for the censored Markov chain with censoring set [Kiˆ 1 Li with any K  1 ‡ n. Next, note that the transition probability from state …1; r† to state …n ‡ 1 ‡ i; k† (for the original Markov chain) can be written as Cn ‡ i …r; k† for any k [ f1; 2; . . . ; mg, and i ˆ 0; 1; 2; . . . . Bi …k; s† is equal to the probability of visiting state …n ‡ 1; s† before hitting any other state in level …n ‡ 1†, given that the Markov chain started in state …n ‡ i ‡ 1; k† for any n  0. Thus, the law of total probability gives Fn ˆ Cn ‡

? X iˆ1

Cn ‡ i Bi ;

and the result follows, since B0 ˆ I and Fn ˆ Rn …I The second equation can be similarly derived.

F0 †.

j

Since each Ai can be recursively computed using the G-measure and each Bi can be recursively computed using the R-measure, the above lemma provides a recursive formula for computing Ri in terms of the G-measure and vice versa as expressed below. COROLLARY 20 Let Rn , n  0, and Gn , n  1, be the R and G-measures de®ned for P in (1). Then, ! j ? X X …k† Fn ˆ Rn …I F0 † ˆ Cn ‡ Cn ‡ j Gj ; …43† jˆ1

kˆ1

where ( …k† Gj

ˆ

Gj ; Pj

k‡1 lˆ1

…k 1† Gl Gj l ;

for k ˆ 1; j  1 for j  k  2;

and F

n

ˆ …I

F0 †Gn ˆ C

n

‡

? X jˆ1

C

j X n

j

kˆ1

! …k† Rj

;

…44†

where ( …k† Rj

Proof:

ˆ

Rj ; Pj

k‡1 lˆ1

…k 1† R j l Rl ;

for k ˆ 1; j  1 for j  k  2.

This follows from Lemma 19 and (30) and (31).

De®ne the generating functions for Ak and Bk :

j

CENSORING, FACTORIZATIONS, AND SPECTRAL ANALYSIS

 ˆ A…z†

? X kˆ0

53

Ak zk

and  ˆ B…z†

? X kˆ0

Bk z

k

:

 contains the REMARK 5 Theorem 17 implies that the region of convergence for A…z†  contains closed unit disk for positive recurrent P, while the region of convergence of B…z† the complement of the open unit disk when P is transient.  and B…z†  satisfy the following factorizations: THEOREM 21 The generating functions A…z†  A…z†‰I Proof:

R…z†Š ˆ I

and

 ˆ I: G…z†ŠB…z†

‰I

It follows from (30) and (31) that

 ˆI‡ B…z†

? kX1 X kˆ1 iˆ0

ˆI‡

? X ? X iˆ0 kˆi‡1

ˆI‡

? X kˆ1



i Bi z

Gk

Gk z

Gk

k



i Bi z

k

! k

 B…z†;

which gives the second equation. The ®rst one can be similarly derived.

j

We now consider a special case of the Markov chain (1), where the transition matrix is either banded above, that is Pi; j ˆ 0 whenever i ‡ N < j, for a ®xed N > 0, or banded below, Pi; j ˆ 0, whenever i > j ‡ N. This Markov chain is usually referred to as of GI=M=1 or M=G=1 type with multiple boundaries. We show that the factorization obtained by Gail et al. (1997) and the factorization in Theorem 14 obtained in this paper are equivalent in this case. Since the proof for the Markov chain of M=G=1 type is similar to that of GI=M=1 type, we only discuss the case of M=G=1 type. Consider the transition matrix of a Markov chain of M=G=1 type 2

b0 6 a0 6 6 Pˆ6 0 60 4 .. .

b1 a1 a0 0 .. .

b2 a2 a1 a0 .. .

b3 a3 a2 a1 .. .













.. .

3





7 7


7 7;


7 5 .. .

where aj and bj are MN6MN matrices and are given by

…45†

54

ZHAO, LI AND BRAUN

2

ajN ‡ 1 ajN .. .

ajN

6 a… j 1†N ‡ …N 1† 6 aj ˆ 6 .. 4 . a… j 1†N ‡ 1

a… j




ajN ‡ …N


ajN ‡ …N ..


.


ajN

1†N ‡ 2

(where in a0 , ai ˆ 0, when i < 0) and 2 bjN;1 bjN;0 6 bjN ‡ 1;0 bjN ‡ 1;1 6 bj ˆ 6 .. .. 4 . . bjN ‡ …N 1†;0 bjN ‡ …N 1†;1









bjN;N

1† 2†

bjN ‡ 1;N .. .







bjN ‡ …N

3 7 7 7; 5

…46†

3

1

7 7 7: 5

1

1†;N

…47†

1

Gail et al. (1997) found a factorization (their Corollary 2), which, in terms of our notation, could be readily re-expressed as zN ‰I

C…z†Š ˆ ‰I

q…z†Š‰zN …I

G…z††Š;

…48†

where q…z† is given by N

q…z† ˆ e0 Q…z †

N X1

! j

N

z G

1

jˆ0

j

etN

1:

Here, ej is the M6MN matrix with the identity IM in the j-th block column, and zeroes P? P n 1 otherwise, and Q…z† ˆ n ˆ 1 j ˆ 0 aj zj Gn j 1 and G…C…p† in their paper) can be expressed, in terms of our notation, by 3 2 0


0 0 IM 6 0 0 IM


0 7 7 6 6 .. . .. 7: . .. .. …49† Gˆ6 .


. 7 7 6 5 4 0 0 0


IM GN GN 1 GN 2


G1 Comparing the Equation in (48) with the factorization result in Theorem 14, it is suf®cient to show that I

q…z† ˆ ‰I

R…z†Š…I

F0 †:

Noting that the expression for q…z† contains the last column of Gk , and this last column of Gk can be expressed as …Bk N ‡ 1 ; Bk N ‡ 2 ; . . . ; Bk † for k ˆ 1; 2; . . . with Bi ˆ 0 if i < 0, we can simplify the expression for q…z† as ! ? N ? X1 X X CjN ‡ s ‡ p Bp zNj ‡ s : q…z† ˆ jˆ0 sˆ0

pˆ0

Finally, the equivalence follows from (41) of Lemma 19.

CENSORING, FACTORIZATIONS, AND SPECTRAL ANALYSIS

6.

55

Spectral Analysis

Spectral analysis has always been a standard and important method used in dealing with stochastic or nonnegative matrices. In studying block-structured transition matrices, it is also powerful. This area was developed in the two books by Neuts (1980, 1989) where Markov chains of GI=M=1 and M=G=1 types were studied, and the recent work by Gail et al. (1996, 1997) where the work of Neuts was generalized to allow the block entries themselves to have a repeating structure. The main objective of this section is to characterize the states of the Markov chain in terms of properties of the spectrum. In this section, we assume that both P and C are irreducible stochastic matrices. LEMMA 22 Let P be the transition matrix in (1), let p be theP stationary probability P?vector of C, and let sp…R† and sp…G† be the spectral radii of R ˆ ? R and G ˆ kˆ1 k k ˆ 1 Gk , respectively. Then, both sp…R†  1 and sp…G†  1. Proof: sp…G†  1 follows from G  0 and Ge  e, and sp…R†  1 follows from R  0, pR  p (Lemma 8 of Zhao et al., 1999) with p > 0, elementwise, and the result sp…R†  max i

…pR†i pi

The above spectral property leads to the following characterization of the Markov chain. THEOREM 23 Let P be the transition matrix in (1). P? i. If k ˆ 1 kDk < ?, then P is positive recurrent if and only if sp…R† < 1; ii. P is transient if and only if sp…G† < 1; and iii. P is null recurrent if and only if sp…R† ˆ sp…G† ˆ 1. Proof: (i) Theorem 3.4 of Zhao et al. (1998) says that P is positive recurrent if and only if R0 < ? and limk?? Rk ˆ 0. Since limk?? Rk ˆ 0 if and only if sp…R† < 1, (i) follows from Lemma 25. (ii) For the transition matrix P given in (1), we can construct a dual stochastic matrix P~ such that P is transient if and only if P~ is positive recurrent (Theorem 7 of Zhao et al., 1999). Let p be the invariant probability vector of C. Then Theorem 6 of Zhao et al. (1999) says that G ˆ diag 1 …p†R~t diag …p† where diag …p† is the diagonal matrix whose non-zero ~ Clearly, sp…G† ˆ sp…R†, ~ and the entries are the elements of p and R~ is the R-measure for P. result then follows from (i). (iii) follows from Lemma 22, (i) and (ii). j COROLLARY 24 ‰1

sp…R†Š‰1

sp…G†Š ˆ 0. P? In the above theorem, the condition k ˆ 1 kDk < ? is standard. It can be replaced by a condition on the R-matrices de®ned from level 0 to non-boundary levels. P? LEMMA 25 Let P be the transition matrix in (1). The condition k ˆ 1 kDk < ? implies P? R0 ˆ k ˆ 1 R0;k < ?.

56

ZHAO, LI AND BRAUN

Proof: It suf®ces to show that R0 e < ?, where e is a P column vector of ones. Let i Q^ ˆ …qi; j †i; j ˆ 1;2;... be the fundamental matrix of Q; or Q^ ˆ ? i ˆ 0 Q . By conditioning on the state after the ®rst transition of the process, we can write R0 as R0 ˆ

? X ? X kˆ1 jˆk

Dj qj;1 :

Since q1;1 is ®nite, there exists a scalar constant b > 0 such that q1;1 e  be. Since Ge  e, it follows inductively from Theorem 9 (see Section 4) that qj;1 e  be for all j  1. Then, R0 e  b

? X ? X kˆ1 jˆk

Dj e ˆ b

? X kˆ1

kDk e < ?;

and the result follows.

j

By using the factorization theorem, we can easily see which zeros of det‰I zeros of det‰I R…z†Š ˆ 0 or det‰I G…z†Š ˆ 0.

C…z†Š ˆ 0 are

LEMMA 26 Let R(z) and G(z) be de®ned for the transition matrix P given in (1). Then, (i) all solutions of det‰I R…z†Š ˆ 0 lie in the region jzj  1; (ii) all solutions of det‰I G…z†Š ˆ 0 lie in the region jzj  1. Proof: (i) Let z0 be a zero of det‰I R…z†Š ˆ 0 and assume jz0 j < 1. Then, there exists a non-zero column vector x ˆ …x1 ; x2 ; . . . ; xm †t such that ! ? X k xˆ Rk z0 x: kˆ1

t

Let jxj ˆ …jx1 j; jx2 j; . . . ; jxm j† . We then have jxj 

? X kˆ1

Rk jxj ˆ Rjxj;

where a  b means that each element of a is less than or equal to the corresponding element of b and there is at least one element of a strictly less than the corresponding element of b. It follows from jz0 j < 1 and pR  p (Lemma 8 of Zhao et al., 1999), where p is the positive invariant vector of C, that pjxj < pRjxj  pjxj, which is a contradiction. (ii) Now, suppose that z0 is a zero of det‰I G…z†Š ˆ 0 and jz0 j > 1. A similar argument to that in (i) gives jxj  jxjG, but Ge  e again leads to a contradiction. j REMARK 6 For the scalar case, the above result was proved as Lemma 4.1 of Zhao et al. (1998). The distribution of zeros of det‰I C…z†Š ˆ 0 can be also used to characterize the Markov chain. P? THEOREM 27 Assume that k ˆ 1 kDk < ?. Then,

CENSORING, FACTORIZATIONS, AND SPECTRAL ANALYSIS

57

i. P is positive recurrent if and only if det…I R† 6ˆ 0; ii. P is transient if and only if det…I G† 6ˆ 0; and iii. P is null recurrent if and only if det…I R† ˆ det…I G† ˆ 0. Proof: (i) Suppose that P is positive recurrent and det…I R† ˆ 0. This implies that sp…R† ˆ 1 by Lemma 22. Theorem 23 tells us that P is not positive recurrent, a contradiction. If det…I R† 6ˆ 0, then p…I R† 6ˆ 0; or pR 6ˆ p where p is the invariant probability vector of C. It follows from Lemma 8 of Zhao et al. (1999) that pR  p, which is equivalent to the positive recurrence of P (Theorem 15). The proof of (ii) is similar to that of (i). The proof of (iii) follows from (i) and (ii). j COROLLARY 28 det…I

R† det…I

G† ˆ 0.

An alternative way of characterizing the Markov chain is given below. LEMMA 29 Let R…z† and G…z† be de®ned for P in (1). Then, (i) det…I R† 6ˆ 0 if and only if all solutions of det‰I R…z†Š ˆ 0 reside outside the unit circle: jzj > 1; and (ii) det…I G† 6ˆ 0 if and only if all solutions of det‰I G…z†Š ˆ 0 reside inside the unit circle: jzj < 1. Proof: The proof to both (i) and (ii) in one direction is trivial. Because of Lemma 26, we only need to prove: if det…I R† 6ˆ 0 …det…I G† 6ˆ 0†, then there is no solution of det‰I R…z†Š ˆ 0 …det‰I G…z†Š ˆ 0† residing on the unit circle jzj ˆ 1. Suppose that det…I R† 6ˆ 0 and suppose that there is a z0 with jz0 j ˆ 1 such P that det‰I R…z0 †Š ˆ 0. k Then there must exist a non-zero column vector x such that x ˆ ? k ˆ 1 Rk z0 x. Therefore, jxj  Rjxj. There are two possible cases: either jxj 5 Rjxj or jxj ˆ Rjxj. In the ®rst case, we would have pjxj < pRjxj  pjxj because pR  p (Lemma 8 of Zhao et al., 1999), which produces a contradiction. While in the second case, jxj ˆ Rjxj implies that det…I R† ˆ 0, a contradiction. (ii) is proved in a similar manner. j P? COROLLARY 30 Assume that k ˆ 1 kDk < ?. Then, i. P is positive recurrent if and only if all solutions of det‰I R…z†Š ˆ 0 reside outside the unit circle jzj > 1; ii. P is transient if and only if all solutions of det‰I G…z†Š ˆ 0 reside inside the unit circle jzj < 1; and iii. P is null recurrent if and only if both det‰I R…z†Š ˆ 0 and det‰I G…z†Š ˆ 0 have solutions on the unit circle jzj ˆ 1. Proof:

The result follows from Theorem 27 and Lemma 29.

j

Acknowledgments This work has been supported by grants from the Natural Sciences and Engineering Research Council of Canada. The authors also thank the referee and an associate editor for

58

ZHAO, LI AND BRAUN

valuable comments and suggestions that led to a signi®cantly improved presentation of this work. References S. Asmussen, Applied Probability and Queues, John Wiley & Sons: New York, 1987. A. Dukhovny, ``Markov chains with quasiToeplitz transition matrix,'' Journal of Applied Mathematics and Simulation vol. 2 pp. 71±82, 1989. A. Dukhovny, ``Markov chains with quasiToeplitz transition matrix; ®rst zero hitting,'' Journal of Applied Mathematics and Simulation vol. 2(3) pp. 205±216, 1989b. A. Dukhovny, ``Markov chains with quasiToeplitz transition matrix; applications,'' Journal of Applied Mathematics and Stochastic Analysis vol. 3(2) pp. 141±152, 1990. H. R. Gail, S. L. Hantler, and B. A. Taylor, ``Spectral analysis of M=G=1 and G=M=1 type Markov chains,'' Adv. Appl. Prob. vol. 28 pp. 114±165, 1996. H. R. Gail, S. L. Hantler, and B. A. Taylor, ``M=G=1 and G=M=1 type Markov chains with multiple boundary levels,'' Adv. Appl. Prob. vol. 29 pp. 733±758, 1997. W. K. Grassmann, ``The factorization of queueing equations and their interpretation,'' J. Opl. Res. Soc. vol. 36 pp. 1041±1050, 1985. W. K. Grassmann and D. P. Heyman, ``Equilibrium distribution of block-structured Markov chains with repeating rows,'' J. Appl. Prob. vol. 27 pp. 557±576, 1990. W. K. Grassmann and D. P. Heyman, ``Computation of steady-state probabilities for in®nite-state Markov chains with repeating rows,'' ORSA J. on Computing vol. 5 pp. 292±303, 1993. J. G. Kemeny, J. L. Snell, and A. W. Knapp, Denumerable Markov Chains, 2nd edition, Springer-Verlag: New York, 1976. G. Latouche and V. Ramaswami, Introduction to Matrix Analytic Methods in Stochastic Modelling, SIAM, 1999. C. D. Meyer, ``Stochastic complementation, uncoupling Markov chains, and the theory of nearly reducible systems,'' SIAM Review vol. 31 pp. 240±272, 1989. M. F. Neuts, Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach, The Johns Hopkins University Press: Baltimore, 1981. M. F. Neuts, Structured Stochastic Matrices of M/G/1 Type and Their Applications, Marcel Decker Inc.: New York, 1989. Y. Q. Zhao, W. Li, and W. J. Braun, ``In®nite block-structured transition matrices and their properties,'' Adv. Appl. Prob. vol. 30 pp. 365±384, 1998. Y. Q. Zhao, W. Li, and A. S. Alfa, ``Duality results for block-structured transition matrices,'' J. Appl. Prob. vol. 36 pp. 1045±1057, 1999. Y. Q. Zhao, W. J. Braun, and W. Li, ``Northwest corner and banded matrix approximations to a countable Markov chain,'' Naval Research Logistics vol. 46 pp. 187±197, 1999. Y. Q. Zhao and D. Liu, ``The censored Markov chain and the best augmentation,'' J. Appl. Prob. vol. 33 pp. 623±629, 1996.