Lecture Notes in Mathematics Editors: A. Dold, Heidelberg E Takens, Groningen B. Teissier, Paris
1695
Springer Berlin Heidelberg New York Barcelona Budapest Ho ng Ko ng London Milan Paris Singapore Tokyo
Darald J. Hartfiel
Markov Set-Chains
~ Springer
Author Darald J. Hartfiel Department of Mathematics Texas A&M University College Station, Texas 77843-3368, USA e-mail: hartfiel @math.tamu.edu
Cataloging-in-Publication Data applied for
Die Deutsche Bibliolhek - CIP-Einheitsaufnahme Hartfiei, Darald J.: M a r k o v set-chains / Darald J. Hartfiel, - Berlin ; Heidelberg ; N e w York ; Barcelona ; Budapest ; H o n g K o n g ; L o n d o n ; Milan ; Paris ; Santa Clara ; Singapore ; T o k y o : Springer, 1998 (Lecture notes in mathematics ; 1695) ISBN 3-540-64775-9
Mathematics Subject Classification (1991): 60J 10, 15A51, 52B55, 92H99, 68Q75
ISSN 0075- 8434 ISBN 3-540-64775-9 Springer-Verlag Berlin Heidelberg New York This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer-Verlag. Violations are liable for prosecution under the German Copyright Law. 9 Springer-Verlag Berlin Heidelberg 1998 Printed in Germany The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Typesetting: Camera-ready TEX output by the author SPIN: 10650093 46/3143-543210 - Printed on acid-free paper
Preface These notes give an account of the research done in Markov set-chains. Research papers in this area appear in various journals and date back to 1981. This monograph pulls together this research and shows it as a cohesive whole. I would like to thank Professor Eugene Seneta for his help in writing Chapter 1. In addition, I would like to thank him for the co-authored research which is the basis for Chapter 4. I would also like to thank Ruvane Marvit for his help in locating references for some of the probability results in the Appendix. Finally, I need to thank Robin Campbell whose typing, formatting, etc. produced the camera ready manuscript for this monograph.
Contents
Introduction
3
1
Stochastic Matrices and Their Variants 1.1 A v e r a g i n g effect of stochastic matrices . . . . . . . . . . . . . . . 1.2 T h e coefficient of ergodicity . . . . . . . . . . . . . . . . . . . . . 1.3 N o n n e g a t i v e matrices . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Markov a n d n o n h o m o g e n o u s Markov chains . . . . . . . . . . . . 1.5 Powers of stochastic matrices . . . . . . . . . . . . . . . . . . . . 1.6 N o n h o m o g e n e o u s p r o d u c t s of matrices . . . . . . . . . . . . . . .
3 3 5 8 13 15 19
Introduction to Markov Set-Chains 2.1 Intervals of m a t r i c e s . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Markov set-chains . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Comi6uting steps in a Markov set-chain . . . . . . . . . . . . . . 2.4 Hi-Lo m e t h o d , for c o m p u t i n g b o u n d s at each step . . . . . . . .
27' 28 35 40 46
Convergence of Markov Set-Chains 3.1 U n i f o r m coefficient of ergodicity . . . . . . . . . . . . . . . . . . . 3.2 C o n v e r g e n c e of Markov set-chains . . . . . . . . . . . . . . . . . . 3.3 Eigenvector description of a limit set . . . . . . . . . . . . . . . . 3.4 P r o p e r t i e s of the limit set . . . . . . . . . . . . . . . . . . . . . . 3.5 Cyclic Markov set-chains . . . . . . . . . . . . . . . . . . . . . . . 3.6 Cesaro set-sums . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.7 Cesaro s e t - s u m c o m p u t a t i o n s . . . . . . . . . . . . . . . . . . . . 3.8 L u m p i n g in Markov set-chains . . . . . . . . . . . . . . . . . . . .
59 59 62 67 69 72 75 82 84
Behavior in Markov Set-Chains 4.1 Classification a n d convergence . . . . . . . . . . . . . . . . . . . . 4.2 Weak law of large n u m b e r s . . . . . . . . . . . . . . . . . . . . . 4.3 Behavior in Markov set-chains . . . . . . . . . . . . . . . . . . . . I M o v e m e n t w i t h i n the t r a n s i e n t states . . . . . . . . . . . II M o v e m e n t from a t r a n s i e n t s t a t e to a n a b s o r b i n g s t a t e . . III M o v e m e n t w i t h i n a n ergodic class . . . . . . . . . . . . .
91 91 100 106 106 108 110
CONTENTS
viii
Appendix A.1 A.2 A.3 A.4 A.5
Norms . . . . . . . . . . . . . . . . . . . . . . . . . . O p e r a t i o n s on c o m p a c t sets . . . . . . . . . . . . . . C o n v e x sets, p o l y t o p e s , a n d vertices . . . . . . . . . . . . . . . . D i s t a n c e c n c o m p a c t sets . . . . . . . . . . . . . . . P r o b a b i l i t y results . . . . . . . . . . . . . . . . . . .
115 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
115 115 116 118 121
Bibliography
123
Index
131
Chapter 0
Introduction One of the major problems in mathematics is to predict the behavior of a system. Traditionally, in the mathematical model of a system, the required data is assumed to be exact while in practice this data is estimated. Thus, the mathematical prediction of the system can only be viewed as an approximation. A more realistic way to describe a system is to use intervals which contain the required data. This approach is used in systems of linear equations
Ax = b by assuming that the required data satisfies
P~A<_Q
and
p<_b~q
for some P,Q,p, and q. These matrices are to be determined from data and experience by the user. The solution is then given as the set of all possible solutions to Ax = b where A and b belong to the intervals previously described. Two books, namely Neumaier (1990) and Alefield and Herzberger (1985), have been written on this topic. A book, using somewhat the same approach for differential equations was written by Ben-Haim and Elishakoff (1990). During the past decade the author has developed interval mathematics techniques for nonhomogeneous Markov chains. Thus, instead of considering the classical equation x(k + 1) = x(k)A where A is the transition matrix for the system, the transition matrix is allowed to change with time leading to the equation
x(k + 1) = x(k)Ak where P <_ Ak <_ Q for some P and Q. The set of all possible behaviors of such a system were described and techniques for calculating this set given. In addition, probabilistic results, e.g. a law for large numbers, for interpreting the set of behaviors, were provided.
2
CHAPTER
O. I N T R O D U C T I O N
Publications involving the above work are scattered and thus the research is not known as a cohesive theory. This monograph provides an organized view of this research. The purpose of this monograph is to motivate the use and further development of interval techniques for studying various systems by mathematicians, scientists, engineers, economists, and social scientists. All of these groups use systems that can show fluctuation. Practitioners that use the traditional Markov chain theory for predictions will find this less restrictive approach useful since it provides bounds on the possible behavior rather than an estimate of the behavior. Such bounds can also be used for best/worst case scenarios of the behavior. In addition, this monograph should be of interest to researchers who are interested in limits of sequences of compact sets, how these limits might be calculated theoretically and numerically, as well as how bounds on these limit sets can be found. Finally, we have written the monograph with sufficient examples to demonstrate the theory. Thus, it is not necessary to read the monograph line by line to glean ideas from it. In addition, at the end of each chapter, we have included some additional notes to link the readers to closely related material in the area. Throughout this monograph, unless otherwise stated, we work within the field of real numbers, with n x n matrices and compatible vectors. The standard notation, A = (aij), and vector x = (zi) will be used. In addition, we use the standard notation that e l , . . . , en denote the natural basis vectors in R n and that ~ ei = e. Whether these vectors are row or column vectors will be clear i=1
from context. Finally, throughout the monograph we will use 1-norm and its related matrix norm.
Chapter 1
S t o c h a s t i c M a t r i c e s and Their Variants In this chapter we cover the results of stochastic matrices which are used in the development of Markov chains, nonhomogeneous Markov chains, and Markov set-chains.
1.1
Averaging effect of stochastic matrices
T h e key notion in the theory of finite Markov chains is t h a t of a one-step transition matrix. This is a stochastic matrix.
D e f i n i t i o n 1.1. A matrix A = (aij) is stochastic if aij > 0 for i , j = 1 , . . . , n and ~ aij ---- 1 for i = 1 , . . . , n. J T h e p r o p e r t y of a stochastic matrix utilized in the t h e o r y of Markov chains is its averaging effect. For any n x 1 vector w , m ! n w j <_ ~ a i j w j ~ m~xwj for j j 3 all i. This averaging can yield a contraction of the entries of a vector. Example
1.1. L e t A =
4
:3:t:5
andw=
[i]
. ThenAw=
2.0 . Note t h a t 2.1
the minimal entry in A w is an increase over the minimal entry in w, and the m a x i m a l entry in A w is a decrease over the maximal entry in w. This averaging, put mathematically, was described in one of M a r k o v ' s first papers. Theorem
1.1. L e t w be a n o n n e g a t i v e v e c t o r and A a stochastic m a t r i x .
If
z = Aw then
maxzii - miin zi < 7 - ( A ) ( m a x w i
- miin wi )
(1.1)
4
C H A P T E R 1. S T O C H A S T I C M A T R I C E S A N D T H E I R V A R I A N T S
where T ( A ) = ~1 max,,, __Y~-]aik - ajkl = 1 - mini.jy ~ min{aik,ajk }. k
(1.2)
k
Pro@ For fixed h,h',Zh - Zh, = y~.ujwj where uj = ahj ah,j. Let j ' denote J the indices j for which uj > 0 and j " the indices for which uj < 0, noting that ~uj =0. J Set -
-
o = Zj, ~,, -- F, lu,, I = - Zj,, ~,,, = F_, lu,,, j, j,, 1
1
= ~ ~ lull = ~ ~ J
lahj
--
ah,jl.
J
Then
(
~ I~j,Iw,,
~ luj,, Lwj,,)
< O(miaxwi - Ilfinwi) < T ( A ) ( m a x w , - m~nwi) which completes the proof of (1.1). The alternate form of the expression of T(A), given in (1.2), follows from the identity: for any real numbers x, y, 2 min{x,y} = x + y - I x - Yl, and from the fact that ~ ai, = 1 = ~ aj,. [] 8
8
It is obvious from (1.2) that 0 < T ( A ) < 1.
(1.3)
However, by (1.1), it is clear that those stochastic matrices A for which T ( A ) < 1 have the contractive nature on the difference in the entries of w. Note that 7"(A) < 1 will occur if and only if every pair of rows c~, ~ of A have a common position k such that ac~k > 0 and al~k > 0. Note also that 7-(A) = 0 if and only if A = ev where v is a stochastic vector (a row vector such that ~ vi = 1, vi > 0 i
for all i). D e f i n i t i o n 1.2. For a stochastic matrix A, the quantity T ( A ) defined by (1.2) is called the coefficient of ergodicity of A. If T ( A ) < 1, the matrix A is called scrambling.
1.2. THE COEFFICIENT OF ERGODICITY
1.2
The
coefficient
5
of ergodicity
In this section we prove three properties of the coefficient of ergodicity. These are specified by (1.4), (1.5), (1.6). []~A H < T(A)HSI]
(1.4)
for all real row vectors 5 such t h a t 5e = 0, equality for some 6.
S(Az) < T(A)S(z)
(1.5)
(here, the spread of w, S(w) = m a x Iw~ - w j l ) for all vectors z (perhaps with z,J
complex entries), and equality for some z. IA]_ T(A)
(1.6)
where A is any eigenvalue, other t h a n 1, for A. If A is scrambling then p r o p e r t y (1.4) says t h a t A is contractive on the subspace C = {6: ~e = 0} while p r o p e r t y (1.5) says t h a t A is contractive on the difference of the entries in a vector. In addition, p r o p e r t y (1.4) leads immediately to the submultiplicative property: for A1, A2 stochastic matrices,
T(AIA2) <_T(A~)T(A2)
(1.7)
which can be extended to p r o d u c t s of more stochastic matrices A1,... , Ak
T(A~ ...Ak) <_T(A~) ... T(Ak) and T ( A k) <_ T ( A ) k . To see the i m p o r t a n c e of (1.6) note t h a t if A is a stochastic m a t r i x then
Ae = e so 1 is an eigenvalue of A. Thus, (1.6) shows t h a t 1 is the largest, in modulus, eigenvalue of A. A m a t r i x A such t h a t Ae = ae for some scalar a is called a generalized stochastic matrix. Such matrices can arise as variants of a stochastic m a t r i x P . For example, A = I - P and A = ( I - P + e I I ) where II is a stochastic vector. In addition, A = ( I - P + eli) -1 and A = ( I - P + ell) -1 - el-I, when they exist, are variants of P which provide generalized stochastic matrices t h a t arise in practice. P r o p e r t i e s (1.4), (1.5), and (1.6) can just as easily be shown for generalized stochastic matrices and this is w h a t we will do. T h e results rest on a key lemma. T h e l e m m a uses the following. T w o vectors x, y are sign compatible if xiy~ >_0 for all i. For such vectors,
+ ylL = limb1+ IlyH.
6
CHAPTER 1. STOCHASTIC MATRICES AND THEIR VARIANTS
L e m m a 1.1. Suppose6 E C = {5: 5 e = O } and67 ~0. T h e n there is an index .set Z = I ( 5 ) of ordered pairs (i, j ) , i, j = 1 , . . . , n such that
(i,j)EZ where Af~j > 0 and ei - ej Zs .sign corapatible to 6 f o r all i , j .
Th~,s I1~11 =
F~ ~ j . (i,j)~Z P r o @ T h e proof is by indu(:tion on th(; mmfl)er c(5) of nonzero entries of &. If c(6) = 2, ,~ = ~.~ (~'i - ej) for some i , j which is the desired result. Sul)I)OS(; the h;mma is true for all 6 such t h a t c(?i) = 2 , . . . , k. Consider a 6 such t h a t c(5) = k + 1. Choose p such t h a t lSp] = rain 15~1 and q su(:h t h a t
51r
sign 5q = - s i g n @. Both (:ases being sinfilar, we only argue the case 6p > O. Set ~i' = a -
G(ep
-
eq).
Then (i',~, a n ( 1 % - % ar(; sign coml)atible, 6' E C, and c(6') < c(~). By the induction hylmthesis
~' = Z
~
((~i - ej)
(z,j)Ez where JV'/j > 0 and all ei - ej sign (:ompatible to 5 ~ and thus sign compatible to (f. Thus,
,~ = ,~,,(e,, - ,;,,) + ~
@ - ( e , - ej)
(~,j)Ez t,tl(~ desired result.
[]
We extend the definition of T to any generalize(l stoehasti(: matrix A, with row sums a. Using that ak is the k-th row of A, T(A)
1 IIo, - ,,,~ II 2 i,j 1 = ~ nlax Z lac~ - o,j.~[ =
- max
i,j
= a -- ll.lill Z
nlin{ai.,, ajs }.
T h e th,,or,,nl giving (1.4), f(,r generalized stochastic matrices, follows. Theorem
1.2. l, br any genc.ralizcd stoeh, astic matri:r, A, T(A)
= .,a• ll,~ II
IlaAII. I
1.2. T H E C O E F F I C I E N T O F E R G O D I C I T Y
7
Proof. T h e technique we use is as in establishing formulas for n o r m s of matrices in general. Using L e m m a 1.1, for any ~ E C, II~AII =
Z
1
<_ ~(max
Ila, - a, ll) ~Nj Y
1
< ~ ( m al,Jx l l a , -
ajll)llSII
_< T(A)IIS[I.
Thus, if I1~11= 1, II~AII ~< T(A). To show equality is achieved, let, [ l a p -
aqll -- m a x l l a ~ -
ajll.
Let, 5 =
"t,3
89
1
- eq). T h e n 6 E C, II5N = a and II5AII = 511% - aqll = T ( A ) .
[]
We now establish (1.5) for generalized stochastic matrices. T h e o r e m 1.3. Let A be a generalized stochastic matrix. Then for any vector z (with perhaps complex numbers), S ( A z ) <_ T ( A ) S ( z )
with equality for some z. Proof. We first, prove a useful inequality. For it, let w be a wwtor (entries p e r h a p s complex numbers). Then for any ii E C, by using the expression for as given in L e m m a 1.1 and the triangle inequality,
(i,j)6g
Now let z be a vector (entries perhaps complex numbers). Then
S ( A z ) = m~x laiz - aoz [ = m a x I(., - a j) z[. t,3
Using (1.8), with 5 = ai - a i, we have that
S ( A z ) < -1m a x Ila, - a~ HS(z) -2 ~,j <_ T ( A ) S ( z ) .
8
C H A P T E R 1. S T O C H A S T I C M A T R I C E S A N D T H E I R V A R I A N T S
To show t h a t equality can hold, suppose T ( A ) = ~[lap 1 - %11. Note t h a t - - aq E C. Define a vector w by wi = 1 if 5i > 0, wi = - 1 if (fi < 0 and 0 otherwise. Then ---- a p
S ( A w ) = max [(hi - aj)w[ > I(ap - aq)w] 1,,J n
= E
lapk - aqkl = 2T(A) = T ( A ) S ( w ) .
k=l
Thus, S ( A w ) = T ( A ) S ( w ) and (1.5) follows.
[]
C o r o l l a r y 1.1. Let A be a generalized stochastic matrix with row sum a. Let )~ (perhaps complex) be an eigenvalue of A other than a. Then
I~1 < T ( A ) . Proof. Let w (perhaps complex entries) be an eigenvector belonging to A. By Theorem 1.3, S ( A w ) <_ T ( A ) S ( w ) . And, since A w = i~w, S(Aw) < T ( A ) S ( w )
or
[A[S(w) _< T ( A ) S ( w ) . Now, if S(w) = 0 then all entries in w are equal and A w = aw. Since A ~ a, S(w) ~ O. But, then <
Thus, (1.6) follows.
1.3
[]
Nonnegative matrices
For some of the sequel we need to use the theory of nonnegative matrices, matrices t h a t have nonnegative entries but are not necessarily stochastic. We need the structure results, results due to the nonzero pattern of the entries in a matrix, of this theory. So far we only have that if a stochastic matrix A is scrambling, the nonzero pattern assures T ( A ) < 1, then it is contractive as described in (1.4) and (1.5). We intend to extend these results to other matrices. Inasmuch as detailed accounts of nonnegative matrix theory are available in several books, e.g. Gantmacher (1964), Berman and Plemmons (1979), and Minc (1988), we confine ourselves to an exposition of basic results. Graphs are often used to depict the pattern of nonzero entries of a matrix. D e f i n i t i o n 1.3. Let T = (tij) be a nonnegative matrix. Denote by G(T) the graph having vertex set g = { 1 , . . . ,n} and arc set { ( i , j ) : tij > 0}.
1.3. N O N N E G A T I V E MATRICES
9
Figure 1.1: G r a p h of G(T).
Example1.2. LetT= [i 46O 12] o . In Fig.
1.1 we depict G(T).
We give a n u m b e r of related definitions informally. A path from a vertex i to a vertex j is a sequence of arcs (ko, kl), (kl, k2),. 9 , (kr-1, kr) where k0 = i, kr = j and r > 1. T h e length of this p a t h is r. This is t a n t a m o u n t to t~. )~ > 0, where T k = (tl k)) is the k-th power of T. A p a t h of length 1 from i to i is called a loop, and is t a n t a m o u n t to t~i > 0. If there is a p a t h from i to j and a p a t h from j to i, we say t h a t i and j
communicate and write i -= j. T h e vertices of G(T) (the indices of the m a t r i x T) m a y be classified and grouped as follows. (i) A vertex i is called essential if whenever there is a p a t h from i to some j (we require at least one such j) then there is a p a t h from j to i. All essential vertices (if any) m a y be divided into essential classes, using t h a t - is an equivalence relation on essential vertices, in such a way t h a t all vertices belonging to one class c o m m u n i c a t e but there is no p a t h from a vertex within such a class to a vertex outside the class. (ii) A vertex i is called inessential if it is not essential. Thus i is inessential if there is no p a t h from i to any j (this occurs when the i-th row of T is 0) or there is a p a t h to some j for which there is no p a t h from j to i. All inessential vertices t h a t c o m m u n i c a t e with at least one vertex (perhaps itself) m a y be divided into inessential classes such t h a t all vertices within a class communicate. All such classes are called self-communicating. E a c h remaining inessential vertex (if any) communicates with no vertices and individually forms an inessential class which we call nonsel]-communicating. Once the classification and grouping has been carried out, the concept of p a t h can be defined for classes (of vertices) in the obvious sense. Thus, if gl, g2 are distinct classes, we say t h a t there is a p a t h from C1 to C2, writing gl --+ C2, if there is a p a t h from a vertex in gl to a vertex in g2. In this case, there is a p a t h from every vertex of gl to every vertex of C2.
10
C H A P T E R 1. S T O C H A S T I C M A T R I C E S A N D T H E I R V A R I A N T S
E x a m p l e 1.3. Let
3 T= 4
5 6 7
1 -0 0 0 0 1 i0
2 0 0 0 0 0 1
3 1 0 0 0 0 0
4 0 0 0 0 0 1
5 0 0 1 0 0 1
6 0 0 0 1 0 0
7 0 0 0 0 0 0
I0000000
Then G(T) appears as in Fig. 1.2. From G(T) we get the classes
Figure 1.2: Graph of G(T).
which are
s = {1,3, 5} essential class C2 = {4, 6} inessential class (self-communicating) C3 = {2} inessential class (nonself-eommunicating) C4 = {7} inessential class (nonself-eommunicating).
We note from this example that the "l's" in the matrix could be replaced by any positive entries yielding the same graph and vertex classification: only the positions of the positive entries are important. Although stochastic matrices can not have zero rows, both types of inessential classes can exist. Essential classes, however, always occur. L e m m a 1.2. A nonnegative matrix T with at least one positive entry in each row possesses at least one essential class.
Proof. The proof is by contradiction. Thus, suppose every vertex is inessential. Choose k0 = i, an arbitrary vertex. Then, since the ko-th row of T is not 0,
1.3. NONNEGATIVE MATRICES
11
there is a path from ko to some vertex kl, with no path from kl to ko. Now, kl is also inessential so since the kl-th row of T is not 0, there is a path from vertex kl to a vertex k2 such that there is no path from k2 to kl. Since there is no p a t h from kl to ko, there is no path from k2 to ko either. Thus, we can construct a sequence of n + 1 distinct vertices ko, k l , . . . , kn such that there is no p a t h from kj to ki, j > i, although there is a p a t h from k, to kj. But, since T is n x n, these n + 1 vertices cannot be distinct, which gives a contradiction. [] Any nonnegative matrix T can be put into canonical form by first relabeling tim vertices of G(T) in an appropriate manner. We first take vertices of an essential class (if any) and renumber them consecutively using the lowest integers and follow with the vertices of another essential class (if any). Continue until all essential vertices have been renumbered. The renumbering is then extended sequentially to inessential classes by renumbering the vertices in an inessential class Ci before an inessential class 6'2 if C2 -+ CI. Example
1[00
1.4. Let
1
2
3
4
2 0
0 0
0 1
0 0
4
0
0
0
5
1
1
0
T=3
5
The graph of T is shown in Fig. 1.3, part (a). The graph showing a relabeling of vertices of G(T), as described in the canonical form, is shown in Fig. 1.3, part
(b).
(a)
(b)
Figure 1.3: Graphs of T and T'. The relabeling is equivalent to simultaneously reindexing tile corresponding rows and colunms 1 --+ 4, 3 --+ 1, 5 -+ 3, 4 --+ 5
12
C H A P T E R 1. S T O C H A S T I C M A T R I C E S A N D T H E I R V A R I A N T S
4
2
1 5
4]0001 T=20 0 0 1 0 0 1 5 0 0 3 1 1
0 0 0 0
3 i] "
1(1000]
Then rearranging the rows and columns of T to correspond to the new indexing 1 2 3 4 5
T,=2
0 0 0 3 1 1 0
0 1
4
0
0
0
5
0
1 0
"
Note that G ( T ' ) is the relabeled graph. It is clear that the canonical form will always contain square blocks, one per class, on the main diagonal of the partitioned lower block triangular matrix. D e f i n i t i o n 1.4. A matrix P, with entries O's and l's, having precisely one 1 in each row and each column is called a permutation matrix. A matrix T is cogredient to a matrix T' if there is a permutation matrix P such that P T P t = T I"
The following facts are well-known: (1) p t = p - 1 and (2) forming a matrix T ' = P T P t from a matrix T using a permutation matrix P is tantamount to a simultaneous permutation of the rows and columns of T. Thus, T is cogredient to the canonical form T' of T. E x a m p l e 1.5. For the matrix T of Example 1.4, the relabeling indicates that 1 0 0 0
p =
0 0 0 0 0 0 0 1
.
Then P T P t = T'. The validity of the following result is now self evident. T h e o r e m 1.4. A nonnegative matrix T with no zero rows is cogredient to T1
0
...
0
0
0
...
0]
0
T~
...
0
0
0
...
OJ
o .......
6 .....
..~
I o ........ 6 . . . . .
..
....
>; .......
I..T.~.+;;~....~.~.+.~.,?..-.......T~..+.,=~.....~.~.+.~ ...... 9 ..... .-...~
L Th,1
Th,2
...
Th,g
Th,g+l
Thg+2
...
(1.9) ThJ
1.4. M A R K O V
AND NONHOMOGENOUS
MARKOV
CHAINS
13
where each Ti, i = 1 , . . . ,g, with g > 1, corresponds to an essential class, each Ti, k = g + 1 , . . . , h, corresponds to an inessential class and for each of these k's there is some j such that Tkj ~ 0 (if inessential classes are present). D e f i n i t i o n 1.5. A nonnegative matrix is irreducible if it consists of a single essential class. (Thus, 1 x 1 irreducible matrices contain a positive entry. Some authors allow the 1 x 1 zero matrix to be irreducible). Thus, in particular, all matrices T 1 , T 2 , . . . ,Tg in the canonical form (1.9) are irreducible as are any of the T g + l , . . . ,Th (if present) which are not 1 x 1 zero matrices. The following result, which relates to inessential vertices, if any, is important for stochastic matrices. L e m r n a 1.3. For a nonnegative matrix T with no zero rows and some inessential vertices, there is a path from any inessential vertex to an essential vertex. Proof. Similar to Lemma 1.2.
[]
We need one more definition before we focus on the special properties of powers of stochastic matrices. D e f i n i t i o n 1.6. A nonnegative matrix T is primitive if for some positive integer k, T k = ,(t! k.))_~ > 0 (that is, each tl k) > 0). Clearly, a primitive matrix is irreducible.
1.4
M a r k o v chains and n o n h o m o g e n o u s M a r k o v chains
Markov chains and nonhomogeneous Markov chains are covered in Isaacson and Madsen (1976), Iosifescu (1980), as well as in Seneta (1981). In this section we briefly describe these two chains. A Markov chain is usually described in terms of random variables. For this we consider a sequence of experiments, done in steps of time t l , t 2 , . . . . The outcome of any experiment is one of n states, say S l , . . . , sn. Without loss of generality we can assume that Sk = k for all k. Set S = { S l , . . . , sn} and let X k : S ~ S be a random variable defined for the k-th experiment. We assume P r { X k = sik I X k - 1 = sik_l,.-. ,Xo = Sio} = P r { X k = sik I X k - 1 = 8ik_l} for all k and all states s i ~ , . . . , sio. Simply put, the probability distribution of X k depends only on the state occupied at the end of the previous experiment. We also assume P r { X a = sik I X k - 1 = s ~ _ l } = P r { X a + t = si~ I X k + t - 1 ---- 8i~-1}
14
C H A P T E R 1. S T O C H A S T I C M A T R I C E S A N D T H E I R V A R I A N T S
for all positive integers t and thus P r { X k = sj I X k - 1 = s~} = aij
for all k. These probabilities determine a transition matrix A = [aij] which, using laws of probability, can be used to show P r { X k = sj IX0 = si} = a ~2 !k)
(1.10)
where A k = [a!~)l In addition, if what is known about the process initially is L t 3 J" that it is in si with probability Yi, that is, P r { X o = si} = Yi,
for all i, then, under these conditions, Pr{Xk = sj} = yAkej
where y = ( Y l , . . . , Yn). The sequence {Xk}k_>0 is called a Markov chain. Often, a Markov chain is simply depicted in a diagram form. 81 82
E x a m p l e 1.6. The Markov chain with transition matrix A = ~ [:62:4s] can be diagramed as shown in Fig. 1.4. .2
.6
Figure 1.4: Diagram of A. We will say that the Markov chain is in state sj at step k if Xk = sj. The behavior of a Markov chain concerns its movement among the states as the number of steps increase. From (1.10) it is clear that powers of stochastic matrices play a fundamental role in studying the behavior of a Markov chain. Nonhomogeneous Markov chains adjust the classical Markov chain description by allowing the probabilities for each Xk to change at different steps. Thus, there is a transition matrix at each step, say A1, A 2 , . . . respectively. Analyzing as with Markov chains, if P r { X o = si} = Yi
for all i, then Pr{X~. = sj} = yA1 ... A k e j
(1.11)
where y = ( y l , . . . , y,~). Thus from (1.11), for nonhomogeneous Markov chains, products of stochastic matrices play an important role.
1.5. P O W E R S
1.5
OF STOCHASTIC
Powers
MATRICES
of stochastic
15
matrices
Much of Markov chain theory concerns limits of powers of stochastic matrices. We describe a basic result. For it, we need the following theorem about inessential vertices. T h e o r e m 1.5. Let A be a stochastic matrix with some inessential vertices, and written in canonical f o r m (1.9). Let Q denote the bottom right submatrix of A associated with the inessential vertices. Then, as k --+ 0% Qk __~ O.
Proof. Let the totality of essential vertices be denoted by E and of inessential vertices by I. Then Qk = ,[ a i(k), j ), i , j E I, is the submatrix in the lower right corner of A k = Laij , (k) ), again a stochastic matrix. Taking i C I, by Lemma 1.3, there is a ko(i) and a j ( i ) E E such that a(kO(O) ij(O > O. Thus, E
(ko(i))
aij
> O.
jcE (k+l) (k) Now, since the row sums of Q are at most 1, ~ aij = ~ ~ ais asj _< jEI jGI scI _(k) 9 Thus ~ ~ij ^(k) is non-increasing with k. Now, for ~is
sEl
jEI
k _>ko(i) (ko(i))
E
alk) <- O(i) ---- 1 -- 2_, aiy
jCI
< 1.
jeE
Let 0 = max0(i) and k0 = maxko(i). Then,
iCI
iCI
E _ ( kaij ) < 0 < 1 -
-
jEI for all k > ko and i E I. So, for any integer m _> 1,
E jEI
_(mko+ko) = E E "is-(rnk~a(kO)sj ttiJ jEI sEl < 0E _
Amko) (Zis
sEI < 0 m+l -+ 0 as m --+ ec. Thus, for all i, the non-increasing nonnegative sequence ~ ctij _(k) -+ 0 jEI as k --+ cx~ since a subsequence tends to O. Hence, Qk __+ 0 as k --+ co. [] The type of matrix used in our limit result follows.
16
CHAPTER 1. STOCHASTIC MATRICES AND THEIR VARIANTS
D e f i n i t i o n 1.7. A stochastic matrix A is said to be regular if it corresponds to precisely one essential class of vertices, together with, possibly, some inessential vertices, and the stochastic submatrix A1 of A in the canonical form corresponding to the essential class is primitive. Thus, in canonical form (1.9), A1 appears as follows A21
A2 "
A description of the limit of powers of regular stochastic matrices depends on the following two lemmas. L e m m a 1.4. If a stochastic matrix A is regular then for all sufficiently large k, A k has a positive column. Proof. Considering A in canonical form, it is clear from the definition of primitive that for sufficiently large kl, A~ ~ > 0 and, by Theorem 1.5, that for each i E I there is a j(i) E E such that a ij(i) (s~) > 0. Then A s~+l = A A kl has all columns corresponding to essential vertices strictly positive, and similarly for A s, k > kl. [] The next lemma is a consequence of the averaging effect of a stochastic matrix on a column vector. L e m m a 1.5. Let w be an arbitrary vector and A a stochastic matrix. If z = Aw, then minwj < m i n z j , maxzj <maxwj. J J ~ Pro@ Since zi
=
~aijwj j
and ~ a i y = 1, m ! n w j < ~ a i j w j j 3 j
for all i.
= zi
~_ m a x w j J []
The following theorem is fundamental in the theory of Markov chains. T h e o r e m 1.6. (Ergodic Theorem) If the stochastic matrix A is regular, then A k ---+ ey where y is the stochastic eigenvector of A belonging to the eigenvalue 1. _(k+l)
Proof. Writing A k = (a~k)) we have that uij
(k)
= ~ aisasj , so for fixed j, from 8
Lemma 1.5
9
(k+l)
m/ina~ ) ~ mlnaij
(k+l)
,maxaij
_~ m/axal k)
so the min and max sequences of entries both approach finite limits. Using Lemma 1.4, let k* be an integer such that A s* has a positive column so T ( A k" ) < 1. Then by Theorem 1.1, since A (m+l)k* -~ AS*A ink*, maxal• k'+k*) - ,,~m _ : _ uij _(ink" +k')_< T(AS* )( maxaij(mS') <_ ( T ( A s" ))m __~ 0
.'"~"--:-uiJ-(mk*))
1.5. P O W E R S O F S T O C H A S T I C M A T R I C E S
17
as m -+ co. Thus for fixed j, the min and the max subsequences approach a common limit and thus the j - t h column of A k tends to a vector, say yje. It now follows t h a t A k tends to ey, where y = (yj) is row vector. Since each A k is stochastic so is ey and thus y is a stochastic vector. Finally, (ey)A = ( l i m A k ) A = A(klim~ A k) = A e y = ey. Thus, y is an eigenvector for A belonging to the eigenvalue 1.
[]
We show t h a t part of the Perron-Frobenius theory follows from the previous work. T h e o r e m 1.7. I f A is a stochastic matrix then 1 is one of its eigenvalues. If, in addition, A is regular then (i) the eigenvalue 1 is simple. (ii) all eigenvalues other than 1 are smaller, in modulus, than 1.
(iii)
A has a stochastic eigenvector, say y, belonging to the eigenvalue 1, and lim A k = ey. k --+ o o
Proof. If A is regular, then by Theorem 1.6 lim A k = ey k--~oo
where y is a stochastic vector belonging to the eigenvalue 1. Since ey is rank 1, by considering the Jordan form of A, it follows that the eigenvalue 1 is simple, thus giving (i). Further, by L e m m a 1.4, there is an integer k such t h a t A k has a positive column. Thus, T ( A k) < 1. Then, by Corollary 1.1, if )~ is an eigenvalue of A, other t h a n 1, then
I kl < From this we have (ii). Finally (iii) is the result of Theorem 1.6.
[]
To conclude this section, we show how close a regular stochastic matrix A is from the rank 1 matrix given in Theorem 1.6. T h e o r e m 1.8. Let A be a stochastic matrix which is regular. stochastic eigenvector of A and Y = ey. Then iRA - Y]I - 2T(A).
Let y be the
18
C H A P T E R 1. S T O C H A S T I C M A T R I C E S A N D T H E I R V A R I A N T S
~
Proof. Since yA = y it follows t h a t
y4a4 = y where a4 denotes the i-th row
4=1
of A. T h e n IIA - Y[I = max
-- Yll
Ilak
ak
= max
-
k
yiai i=1
=max
~yi(ak--ai)
k
i=1
<_ max ~ k
yillak - aiH
i=1
n
< ~
y4 max Ilak - a i l l
4=1
<_ max flak - a411 i,k
< 2T(A). []
To show this b o u n d is achievable, we provide an example. E x a m p l e 1.7. We give a 3 x 3 matrix which can easily be generalized to an n x n matrix. For this, let
A=
1-2c e
[i ~
1 - 2e
for e > 0 and small. T h e n y = (1,0,0) while T ( A ) = 111al - a211 = 8 9 ( 1 - 2 e ) + e ) = 1 - e while I I A - Y ] I = I](a2-Y)II = ( l - e ) + ( 1 - 2 e ) + e = Thus, IIA - Yll = 2T(A).
- e) + 2-2e.
To see how fast A k -+ Y we add the following corollary. C o r o l l a r y 1.2. Using the hypothesis of the theorem, if T ( A m) < 1 for some positive integer m, then there are constants K and ~, 0
IIAh - YII <- K ~ h for all positive integers h.
1.6. NONHOMOGENEOUS PRODUCTS OF M A T R I C E S
19
Proof. Write h = mq + r where 0 < r < m. Then IIA h - Y[[ < 2 T ( A h)
<_2T(A mq+r) <_ 2T(Amq)T(A r) _< 2T(Am) q
<_ 2[T(Am)-~] "~q < 2[T(Am)-~]mq+r[T(Am)-~]-r < 27-(Am)-117-(Am)-~]h. Thus, the result follows by letting/3 = [ T ( A m ) ~ ] and K = 2T(Am) -1.
1.6
[]
N o n h o m o g e n e o u s products of stochastic matrices
The ideas of Section 1.5 may be extended to study the behavior of the nonhomogeneous products. For p _> 0, h > 1, define
Fp,h = (f~p,h)) --_ Ap+lAp+2... Ap+h
(Forward Product)
where A1, A 2 , . . . is a fixed sequence of stochastic matrices, and Ak = (aij (k)). We shall say that a forward product is weakly ergodic if and only if
f!p,h) ~,s _ f(p,h) J js --+ 0 as h -+ oc for each i,j, s,p. This is clearly equivalent (see (1.2)) to saying
T(Fp,h) -~ 0
for each
p _> 0
as h - ~ oc. To extend Theorem 1.6 to nonhomogeneous Markov chains requires two lemmas. 1.6. If P and Q are stochastic matrices, Q regular, and PQ or Q P have the same graph (positions of positive entries) as P, then P has a positive
Lemma
col~tmn. Proof. Since Q is regular, by L e m m a 1.4, Qk has a positive column for some k. If PQ ~ P (have the same graphs) then p Q k ~ p so P has at least those columns positive which are positive in Qk. The case Q P ~ P is done similarly. [] 1.7. If Fp,h is regular for each p > O, h > 1, then Fp,h has a positive column for h > t where t is the total number of distinct graphs (nonzero matrix patterns) corresponding to regular matrices. Lemma
C H A P T E R 1. S T O C H A S T I C M A T R I C E S A N D T H E I R V A R I A N T S
20
Proof. For fixed p there must be numbers a, b, 1 < a < b < t + 1 such that Ap+l Ap+2
. . 9A p + a + l
. . 9A p + b
"~ A p + l A p + 2
9 .. Ap+a
since the number of distinct graphs is t. By Lemma 1.6, Ap+l Ap+2 9.. Ap+a has a positive column. Thus, Fp,h has a positive column for h >_ t (this column need not be the same for all h). [] The following is a generalization of Theorem 1.6. T h e o r e m 1.9. If Fp,h is regular for each p >_ O, h > 1, and
min+aij(k) ~ '7 > 0
(1.12)
uniformly for all k >_ 1 (where rain + is the minimum over all positive entries), then Fp,h is weakly ergodie. Proof. Writing h = k t + r , 0 <_ r < t, with t having the meaning as in Lemma 1.7 and p fixed, gp,h = gp,t F~+~,t . . . Fp+ (k- l )t,t Fp+ kt,r (where if r = 0, Fp+kt,r is the identity matrix). Thus, for h ~ t, by (1.7) and
(1.3) T ( F p , h ) < _ ( Hi=0 T(Fp+it,t))T(F,+kt,r)\ k-1
<- ~ I T(Fp+it,t). i~O
By Lemma 1.7, Fp+~t,t has a positive column for all i. From (1.12) rain > 9 , +f(p+it,t) .'i,j -~/t. And using the extreme right of (1.2) we have
_< ( 1 - .yt)k <_ ( 1 Thus T(Fp,h) -+ 0 as h --+ co.
(1.13) []
To give another view of weakly ergodic we need to define the distance between a stochastic matrix and fll ----{A: A is an n x n rank 1 stochastic matrix}. It is clear that fll is a compact convex set. D e f i n i t i o n 1.8. Let F be a stochastic matrix. Then 6(F,f~l) = rain I [ F - A l l .
1.6. N O N H O M O G E N E O U S PRODUCTS OF M A T R I C E S
21
C o r o l l a r y 1.3. Using the hypothesis of the theorem, there are constants K and ~, 0 < ~ < 1, such that 5(Fp,h, ~1) <_ K ~ h
for all positive integers h. Proof. Using Theorem 1.8 there is a stochastic,rank one matrix Yh, which depends on h, such that
5(Fp,h, al) < IIFp,h- Yhll-< 2T(Fp,h). Now using (1.13),
T(Fp,h) <_ (1 --7t) k <_ [(1-- "yt) ] kt _< [(1 - 7t)~]-r[(1 - 7t)~] kt+r _< (1 - ~/t)-1[(1 - 7t)f] h. Thus, the result follows by setting K = 2(1 - ,yt)-I and/~ = (1 - ,),t)~.
[]
Although Fp,h tends to ~1 as h increases, {Fp,h}h>_l need not converge as the following example shows. E x a m p l e 1.8. For all k, let A2k = A and A2k+l = B where
A= Then go,2k = (BA) k ~
[1 0] 1/2
1/2
if]
r~/31/31
rl/3 2/3- I
L2/3 1/3j and F 0 , 2 k + l = B ( A B ) k --~ [1/3 2/3J "
We conclude this chapter by proving a companion theorem to Theorem 1.9, for backward products. For this, let p _> 0, h > 1 and define
Bp,h = (bl p'h)) = Ap+hAp+h+l... Ap+l
(Backward product)
T h e o r e m 1.10. If Bp,h is regular for each p > O, h > 1 and m i n + a o ( k ) _> 7 > 0
uniformly for all k > 1 (where rain + is the minimum over all positive entries), then lim Bp,h -~ Y , a rank one matrix that depends on p. Further, there are h-+oo constants K and 13, 0 < ~ < 1, such that IIBp,t,, - Yll < g~ h-
22
C H A P T E R 1. S T O C H A S T I C M A T R I C E S AND THEIR V A R I A N T S
Proof. Adjusting the proof of Theorem 1.6 for the sequence {Bp,h}h>_l shows that this sequence converges to a matrix, say Y. The proof of T h e o r e m 1.9 shows that Bp,r is weakly ergodic and thus Y is rank one. Since {Bp,h}h>_l converges to a rank one matrix for any p _> 0, for any fixed h >_ 1, {Bp+h,9}g>_lconverges to a rank one matrix, say X. Thus, XBp,h = Y.
(1.14)
If each row in Y is the vector y, (1.14) says that y is in the convex hull of the rows of Bp,h. Thus, for all k,
Nb(kp'h)
-
where b!p'h) is the s-th row of
Yll
-<
max Ilblp'h) - bj(p'h) [I
Bp,h. Hence,
it follows that
IlBp,h -- Yll <- 2T(Bp,h). Finally, the bound follows as in the proof of Corollary 1.3.
Related
[]
research notes
The origins of much of the material in this chapter is rather dated. Theorem 1.1 dates back to Markov (1906) and a version of Theorem 1.2 to Dobrushin (1956). Doeblin (1938) and Seneta (1973, 1981) give a rather detailed historical accounting of the material. Additional research material on the topics in this chapter follows in list form. (a) F u n c t i o n a l s . The functional T was used, in this chapter, to assure convergence of Markov chains as well as to bound subdominant eigenvalues. Here we provide additional information on T as well as provide some other functionals. Seneta (1979) organized and extended previous work on the coefficient of ergodicity, by considering various norms, including
Tp(A) = max IIxAIIp where I1" lip is the p-norm and A is a stochastic matrix. II~llp=t ~oe=l
Tan (1982) found a functional form for the coefficient of ergodicity Too. However, in general it is not as good a tool as that of the original T. In the following year, Tan (1983) introduced another type of coefficient of ergodicity
ap(A) = sup IIAxllp where 7rA = 7r, and observed results similar to those II~llp=l
for the coefficient of ergodicity Tp. A draw back to using ap over ~-p, however, is t h a t it requires the knowledge of 7r. Seneta and Tan (1984), added to the study of Tan. They gave a general definition of what a coefficient of ergodicity should be and introduced a new such coefficient, the Frobenius coefficient r which can also be calculated directly
1.6. NONHOMOGENEOUS PRODUCTS OF MATRICES
23
from the entries of A. Some comparisons of r with Tp are given including cases when r is smaller than some Tp. Also, see Seneta (1993b). Subdominant eigenvalues of a stochastic matrix A indicate, to some extent, the rate of convergence of {A k }k_>o. Thus, bounds on subdominate eigenvalues are important. Bauer et al. (1969) used the coefficient of ergodicity to find upper bounds on subdominant eigenvalues of stochastic matrices. Papers of Seneta (1979, 1983, 1984a), Seneta and Tan (1984) as well as Rothblum and Tan (1985), added to that study. Rothblum and Tan (1985) provided a unified look at the area of upper bounds for subdominant eigenvalues of nonnegative matrices. A good literature survey is given there. The authors also unify various techniques in the literature which define and calculate coefficients of ergodicity. Zenger (1972) compares the coefficient of ergodicity as a bound for subdominant eigenvalues for stochastic matrices to a few other bounds in the literature. He concludes that a bound due to Deutsch and Zenger (1971) is a bit better than the coefficient of ergodicity. Rhodius (1997) also compares different coefficients of ergodicity. Seneta (1993a) demonstrated a variety of other uses of coefficients of ergodicity. These uses include perturbation results about nonhomogeneous Markov chains and the density of diagonalizable matrices in the set of stochastic matrices. A version, Birkhoff's contraction coefficient, of the coefficient of ergodicity has been developed for nonnegative matrices. Using the projective pseudometric d, due to Hilbert, defined on the positive vectors, Birkhoff (1967) proved that for positive matrices A,
T(A) = sup x,y
d(xA, yA) d(x,y)
can be computed as ~-(A)- 1- ~
1+ V/~
where r
min aikajl i,j,k,I ajkail
Bushell (1973) gave elementary proofs of the properties of d while Artzrouni and Li (1995) gave a simple proof of the formula for T(A). Also see Althem (1970) for a variety of cross products as in the definition of r Golubitski et al. (1975), and Hajnal (1976) use T to discuss weak ergodicity and convergence of nonnegative matrix products. Seneta (1984b) also used this approach to give conditions which assure convergence of products of compact sets of nonnegative matrices. Other functionals are also useful in matrix work. Fiedler (1972) introduced measures of irreducibility while finding bounds on I1 - )~1 where A is a subdominant eigenvalue of a doubly stochastic matrix. For any doubly stochastic matrix
24
CHAPTER 1. STOCHASTIC MATRICES AND THEIR VARIANTS
A, he defined
where R s is the compliment of R in { 1 , . . . ,n}. Thus, # measures, in the 1norm, how close A is to a reducible matrix. Christian (1979) extended this work, defining the k-th measure of irreducibility. Hartfiel (1973) defined another measure of irreducibility. For any nonnegative matrix A, he defined # ~ (A) = min (max aij) Rr162 IER Rl~ jER I
and showed how it could be used to find bounds on subdominant eigenvalues, as well as bounds on the stochastic eigenvectors belonging to 1. This work was extended in (1975a) by defining the k-th measure of irreducibility and of full indecomposability. Applications of these measures included bounds on subdominant eigenvalues, bounds on stochastic eigenvectors and rates on the convergence of production processes and Markov chains. A general theory for such measures was given in (1981b). Fiedler (1995) introduced another measure, a bit more complicated, and gave a lower bound on [1 - A] for the subdominant eigenvalue A of a doubly stochastic matrix. (b) P r o d u c t s o f m a t r i c e s . Products of matrices form Markov chains and nonhomogeneous Markov chains. Papers involving products of matrices are cited in Isaacson and Madsen (1976), Iosifescu (1980), and Seneta (1981). Convergence rates of Markov chains, and nonhomogeneous Markov chains, can be found using T. Ismucson and Luecke (1978a) discuss the convergence rate of {A k } in terms of the largest, in modulus, subdominant eigenvalue of A. Leizarowtiz (1992) discusses convergence of {A1 ... Ak}k>O in terms of the limit points of the sequence. Convergence of infinite products of substochastic matrices was considered by Pullman (1966) and Hartfiel (1984). Daubechies and Lagarias (1992) as well as Tsaklidis and Vassiliou (1990) considered convergence of products of matrices with row sums 1 but not necessarily having nonnegative entries. Meyer and Plemmons (1977) considered complex matrix products with spectral radius 1. Smith (1966) considered matrices with spectral radii less than 1 and showed when such products converge to 0. Hartfiel (1974a) was also concerned with conditions which assured that products converge to 0. For nonnegative matrices, Rothblum (1981) as well as Friedland and Schneider (1980) discuss the growth of entries in powers of a nonnegative matrix A in terms of various sums. Here, the spectral radius p(A) = 1 but include matrices such as [o ~2] and [ ~ ] . In Friedland and Schneider (1980), the growth of {Ak}k>0 is handled by considered B(k) = Ak(I + . . . + A q) for some positive integer q.
1.6. NONHOMOGENEOUS PRODUCTS OF MATRICES
25
Cull and Vogt (1973), Freese and Johnson (1974), as well as Geramita and Pullman (1984) discuss asymptotic growth of Leslie matrices, the latter paper describing how to find formulas for the limit of a sequence {Ak}~>0. Finally, Elsner et al. (1990) use the notion of paracontracting (Ax ~ x iff I[Ax]l < Itxll) to discuss convergence of {Ak... A1}k_>0.
Chapter 2
I n t r o d u c t i o n to M a r k o v Set-Chains In this chapter we provide the basic parts which are put together to form a theory for Markov set-chains. Before looking at these parts, it is helpful to give the basic idea which leads to the theory. In applying Markov chains, it has been recognized that the assumption of a constant transition matrix at each step is often unrealistic for applications. Although this is far from uncommon, the point can be made with two examples. E x a m p l e 2.1. Suppose we have a table of coins and at each minute we choose a coin, flip it, and record the result. We would expect that the probability of a head occurring, at step k, to depend on the coin selected. Thus, as k -~ c~, the probabilities would fluctuate. E x a m p l e 2.2. Consider a machine which can be in either of the following two states on a given day (step). so: the machine is down for some portion of the day. sl: the machine works perfectly during the day. We expect that the probabilities of entering either of these two states, at step k, would depend on the various old and new parts in the machine at that time. Thus, as k -+ oc, the probabilities would fluctuate. The study of nonhomogeneous Markov chains is a study which allows change in the transition matrices at each step of time. Thus, if y is the initial probability distribution vector and Ak denotes the transition matrix at the k-th step then yA1 ... Ah is the probability distribution vector at the h-th step. For long run behavior, limits need not exist which, to a great extent, restricts the use of this work. In this monograph we develop a study of Markov set-chains. Markov setchains allow for fluctuating transition matrices at each step in time and yet
28
C H A P T E R 2. INTRODUCTION TO M A R K O V SET-CHAINS
provides a long run limit. Beyond that, much of the theory of classical Markov chains is established in this new setting.
2.1
Intervals of matrices
In Markov set-chains, especially in the computational results, we use the notion of intervals. D e f i n i t i o n 2.1. Define An = {x: x is a 1 • n stochastic vector}. Let p and q be nonnegative 1 x n vectors with p < q (componentwise). Define the corresponding interval in A,~ by [p, q] = {x : x is a 1 • n stochastic vector and p < x < q}. We will assume that p and q are chosen so that [p, q] r 0. It is sometime helpful to view mathematics geometrically. We can view intervals by using models. M o d e l for A2. The set A2 of 1 x 2 stochastic vectors can be viewed in R 2 as the line segment with end points el and e2. See Fig. 2.1, diagram (a). An interval [p, q] in A2 is the intersection of the rectangle, determined by p and q in R 2, and A2. For example, i f p = (.2, .3), q = (.6, .9) then [p,q] appears as Fig. 2.1, diagram (b). e2 . . . .
l ~ . . . . . . .
. . . .
y=.9
y=,3
) r
x=.2
(a)
x=.6
(b)
Figure 2.1: Graph of [(.2,.3), (.6,.9)]. M o d e l for A3. In R 3, Aa, the set of 1 • 3 stochastic vectors, can be seen as the convex hull of el, e2, and e3 as shown in Fig. 2.2, part (a). An interval [p, q] can be viewed as the intersection of the box, determined by p and q in R 3, and A3. See Fig. 2.2, part (b). More particularly, given p = (.1, .1, .2) and q = (.5, .6, .8), to see this intersection in A3 we draw the line segments that represent the intersection of the
29
2.1. INTERVALS OF MATRICES
e 3
e 2
(a)
(b)
Figure 2.2: Graph of A3 and [p, q].
y=.l e3
z=.2 e2
e1
Z=.2
B
I
(a)
x'--.5 (b)
Figure 2.3: Graph of [(.1,.1, .2), (.5, .6, .8)].
x=.l
C H A P T E R 2. I N T R O D U C T I O N TO M A R K O V S E T - C H A I N S
30
planes in R 3 and A3. Thus, z -- .2 and z -- .8 are segments in A3 as shown in Fig. 2.3, p a r t (a). P u t t i n g together, [p, q] in A3 a p p e a r s as shown in Fig. 2.3, p a r t (b). T i g h t intervals are i m p o r t a n t in our work. Definition
2.2. Let [p, q] be an interval. If Pi =
min xi, 9 e[v,q]
qi = m a x xi ~e[v,q]
then pi, q~ are called tight, respectively. If Pi and qi are tight for all i, then the interval [p, q] is called tight. Intervals can be tested for tightness by using the following lemma. 2.1. Let ~, q] be an interval. For each i, (i) pi is tight if and only if pi + ~ qk _> 1.
(2.1)
(ii) qi is tight if and only if qi + ~ k # i Pk _< 1.
(2.2)
Lemma
Proof. We argue (i). Thus, suppose
For the direct implication we argue its contrapositive.
Pi + E q k k#i
< 1.
T h e n there is no x E [p, q] such t h a t xi = Pi- Thus, (i) follows. For the converse implication, for simplicity of notation, we argue the case i = 1. Thus, suppose Pl + ~ qk > 1. Consider x(a) = ap + (1 - a ) ( P l , q2,.-. , qn) where a is a scalar. Since, by definition, [p, q] r 0 it follows t h a t x(0).e
and
x(1).e>_l.
Thus, there is a n a , 0 < a < 1 such t h a t x ( c ~ ) . e = 1. S i n c e p < follows t h a t x(a) e [p, q] and the first c o m p o n e n t of x(a) is pl.
x(a) < q i t []
E x a m p l e 2.3. Let p = (0, .05, .7) and q = (.2, .15, .9). A p p l y i n g (2.1) we have (a) Pl + q2 -4-q3 = 1.05 > 1 (b) ql + p2 + q2 = 1.15 > 1 (c) ql -4- q2 -4- P3 -- 1.05 > 1. Applying (2.2) we have (a) ql -4-P2 -4-P3 <_ .95 < 1 (b) pl + q2 A- P3 <_ .85 <_ 1 (c) P l + P 2 + q 3 <.95<1 Thus, all pk and qk are tight. A n a t u r a l way tight intervals can arise is in estimating a stochastic vector x where the errors are e s t i m a t e d by p = x - e, q = x + ~ w h e r e e, ~ are nonnegative vectors. T h e interval is tight if any c o m p o n e n t error in x can be recovered by adjusting the remaining components. Using L e m m a 2.1 we have the following.
2.1. I N T E R V A L S OF M A T R I C E S
31
C o r o l l a r y 2.1. Let x be a stochastic vector, ~ and ~ nonnegative vectors such thatp=x-e>O andq=x+~<e. If
ci <_ E ~k
and
~, <_ E ~k
for all i, then ~p, q] is a tight interval. If an interval is not tight, we can tighten it. T i g h t I n t e r v a l A l g o r i t h m : Given an interval [p, q] we find the corresponding tight interval [p, ~]. 1. Input p, q. 2. For i = 1 , . . . , n do (a) (To determine Pi.) If Pi + ~ qk --> 1, set Pi = Pi. Otherwise, set k=fii
/~i ---- 1 -- ~ q k . (b) (To determine e/i.) If qi + ~ P~ _< 1, set ~i = qi. Otherwise, set k~i
qi=l
- ~Pk.
3. O u t p u t p, q. E x a m p l e 2.4. Let p = (.2, .2, .3) and q = (.3, .3, .7). Applying (2.1) we see t h a t [p, q] is not tight. Thus, we tighten the interval. 1. For f: (a)
Pl + .3 + .7 > 1
so
Pl = .2
(b) (c)
P2+.3+.7_>1 P3+-3+.3<1.
so 152=.2 Sett53=.4
(a)
q1+.2+.3_~1
so
(b) (c)
q2+.2+.3<_1 q3+-2+.2>1.
so 4 2 = . 3 Setq3=.6.
2. For q: ql----.3
Hence the tight interval is ~, ~] where p = (.2, .2, .4) and ~ = (.3, .3, .6). The graph of [p, q] is shown in Fig. 2.4, part (a). Note t h a t we need to tighten the lines z = .3 and z = .7 to z = .4 and z = .6. The tight interval [p, ~] is shown in Fig. 2.4, part (b). L e m m a 2.2. Let ~, q] be an interval. Application of the Tight Interval Algorithm yields a tight interval ~, ~] with ~, q] = ~, q].
C H A P T E R 2. I N T R O D U C T I O N TO M A R K O V SET-CHAINS
32
e 3 / y=.2 y=.3 z=.7
......
\ /
y=.2
~ - i
/ x=.3
=.
z=A
z=.3 2
'
//
(a)
',
\
i x=.2 x=.3
(b)
Figure 2.4: G r a p h s of interval and tightened interval.
Proof. Note, by the algorithm, t h a t pl ---- Pl or (/51, q 2 , . . . , qn) 9 [P, q]. Either case implies t h a t /31 = min xl. ~[v,q]
Similarly, /3i=
min xi
and
qi=
m a x xi
for all i. Thus, p and ~ provide tight c o m p o n e n t bounds on [p, q]. And
[p,q] = {x:
x 9 [p,q])
= {x : x is 1 x n stochastic vector and/5 < x _< ~} = [P,~]. [] We now show t h a t [p, q] is a convex polytope. A description of the vertices of this convex p o l y t o p e requires the following notion. D e f i n i t i o n 2.3. Let [p, q] be a tight interval and x E [p, q]. If p~ < xi < q~ for some i, then the c o m p o n e n t xi in x is called free. 2.3. Let ~, q] be a tight interval. Then ~9, q] is a convex polytope. A v e c t o r x E [p,q] is a vertex o f ~ , q ] if and only i f x has at most one free component.
Lemma
Proof. We first show t h a t every vector x in [p, q] can be written as a linear combination of vectors with at most one free component. We do this by induction on k, the n u m b e r of free c o m p o n e n t s in x. If k -- 0 or k -- 1, the result is clear. T h u s suppose the result is true for all k < m . Now, let k = m .
2.1.
INTERVALS
33
OF MATRICES
Since k _> 2, x has at least two free components. Suppose these c o m p o n e n t s are in the i-th and j - t h positions. Define s
= ~ x i - p i if x i - p i 4_ qj - x j
[
and
qj - x j if x i - Pi > qj - x j
and w = x - e e l + e e j . Define ef = ~ x j - p j if x j - p j <_ qi - x i
[
qi - xi if x j
-
pj
and
> qi -- x i
and w ~ = x + d e i - e l e j . Note t h a t b o t h w and w ~ are in [p, q] and t h a t b o t h have fewer t h a n m free components. s Set a = ~ % . T h e n 0 < a < 1 and x = a w + ( 1 - a ) w ~. Now, by the induction hypothesis, b o t h w and w I can be written as linear combinations of vectors in [p, q] h a v i n g at most one free component. Substituting such expressions in for w and w ~ shows t h a t x can be written in the same way. We now show t h a t any vector in [p, q] having at most one free c o m p o n e n t is a vertex of [p, q]. For this, let x be such a vector. Write x=
1
1
~w+~z
where
w, z E [ p , q ] .
If x has no free components, then w = z. Suppose x has a free c o m p o n e n t xi. T h e n w k = Zk for all k ~ i. And, since w and z are stochastic, it follows t h a t w i = z i . Hence, w = z and x is a vertex of [p, q]. [] T h e n u m b e r of vertices of an interval is i m p o r t a n t since this n u m b e r indicates when it is practical to c o m p u t e [p, q]. Corollary
2.2. L e t [p,q] be a n i n t e r v a l .
Then
[p,q] c a n h a v e a t m o s t
n2 n-1
vertices.
To construct a vertex choose a coordinate i for the, possibly, free coordinate. T h e r e are n choices. Now, for each remaining coordinate j, j ~ i, there are two choices, p j or q j . Thus, from the p r o d u c t rule there are n2 '~-1 possible vertices. [] Proof.
To indicate the closeness of this b o u n d we give an example. Example
2.5. Let n > 2. Set pl = 0 and ql
and qi = Ln + ~ 1
=
n"
For i > 1, set pi
. We consider . the . interval . [p, q].
=
1
1
n-
Note t h a t (-~,
1) E
[p, q] so [p, q] ~ O. To construct a vertex v, for i > 1 choose vi a s Pi or qi- Set vl = 1 - ~ v i . i:>l
T h e n vl >_ 1 1 -
(n - 1)[~
~q~
= 1-(n-
1)[~+
~ ]
= 0 and vl _< 1 -
EPi
i>1
i>1
~( 1_1)] =2K. Finally, by construction, it is clear t h a t
[p,q]
at least 2 n-1 vertices.
=
has
CHAPTER 2. INTRODUCTION TO M A R K O V SET-CHAINS
34
E x a m p l e 2.6. Let p = (.I, .2, .4) and q = (.3, .4, .6). We c o m p u t e vertices of the tight interval [p, q]. To find vertices, according to L e m m a 2.3, choose a position in the vector for the free variable. For all other positions, put in the lowest or highest possible values. This leads to four feasible vectors. On each vector, insert in the free variable position the value, if possible, t h a t determines a stochastic vector. Check to see if the resulting vector lies in the interval [p, q]. F o r / = 1, (a)
( Z l , .2, .4). Set zl = 1 - .6 = .4. Note .1 _< zl _< .3 is false so this is not a vertex.
(b) (zl, .2, .6). Set Z 1 = 1 - .8 = .2. Since .1 < zl < .3, (.2, .2, .6) is a vertex. (c) (Zl, .4, .4). Set zl = 1 - .8 = .2. Since .1 < zl < .3, (.2, .4, .4) is a vertex. (d) ( z l , . 4 , . 6 ) . vertex.
Set zl = 1 - 1 = 0. Since .1 < zl < .3 is false, this is not a
For i = 2 we have (.1, .3, .6), (.3, .3, .4). For i = 3 we have (.1, .4, .5), (.3, .2, .5). A g r a p h depicting these vertices is given in Fig. 2.5. x=.l
y=.2
~=.4
Figure 2.5: G r a p h of [(.1, .2, .4), (.3, .4, .6)]. In M a r k o v set-chains, m a t r i x intervals are also i m p o r t a n t . Definition
2.4. Define 12n = {A: A is an n x n stochastic matrix}.
Let P and Q be n x n nonnegative matrices with P < Q. Define the corresponding interval in f~n as
[P,Q] -- {A: A is an n x n stochastic m a t r i x with P < A < Q}. We will assume t h a t P and Q are such t h a t [P, Q] r 0.
2.2. M A R K O V SET-CHAINS
35
If P and Q satisfy pij--
min
ai~
AE[P,Q]
and
qij=
"
max a~j AE[P,Q]
for all i and j, then [P, Q] is called tight9 The interval [P, Q] can be constructed by rows9 L e m m a 2.4. Let [P, Q] be an interval9 Then [P, Q] = {A: Ai E [Pi, Q,] ]or all i where Ai
Pi, Qi are the i-th rows o] A, P, Q respectively}9 Thus, the results on vector intervals can be applied, by rows, to any interval [P, Q]. We can use vector intervals to determine if [P, Q] is tight, to show [P, Q] is a convex polytope, and determine its vertices. In addition we can note t h a t [P, Q] has at most (n2'~-1) n vertices and may have (2n-1) n vertices. It is important, in later work, to note that [P, Q] being tight implies simultaneous tightness of the entries in any column of P and of Q. C o r o l l a r y 2.3. Suppose the interval [P, Q] is tight9 Then ]or any integer i,
1 < i < n, there is a matrix A E [P, Q] with i-th column the i-th column o] P and a matrix B E [P, Q] with i-th column the i-th column o] Q.
2.2
Markov set-chains
In this section we define Markov set-chains and provide some basic results about them. D e f i n i t i o n 2.5. Let M be a compact set of n x n stochastic matrices 9 Let s l , . . . , sn be states and consider the set of all nonhomogeneous Markov chains, with these states, having all their transition matrices in M. Thus, we call M a transition set. Define
M 2=MM={A1A2: M k+l = M M k = { A I A 2 :
A1,A2EM} A I E M , A2 E M k}
= {A1...A~:
A1,...,AkEM}.
We call the sequence M, M 2, ... a Markov set-chain. Let So be a compact set of 1 • n stochastic vectors. This set will contain the set of all possible initial distribution vectors for our nonhomogeneous Markov chains9 Thus, we call So an initial distribution s e t .
36
CHAPTER
2.
INTRODUCTION
TO MARKOV
SET-CHAINS
Define
SI
= SoM
Sk+l = SkM
= {x:
x = y A where y C So and A E M}
= {x: x = y A w h e r e y E S k a n d A E M } ---- {X: x = y A 1 . . . A k
where y E So and A 1 , . . . ,Ak E M}.
We call S k the k-th distribution set and So, S o M , . . .
a Markov set-chain with initial distribution set So. An example is helpful. E x a m p l e 2.7. Suppose a plant provides a technical course on safety procedures for its employees. The probability of passing this course is approximated as .9, with some fluctuation, no more than .01, from offering to offering. To model this problem as a Markov set-chain we provide two states, g = graduated and c = taking the course. The transition set is
M=
{ [ c] A = g c
~ a
0 1-a
: .89
}
9
The initial distribution set, perhaps due to this being the first such class, is
So ---={(0, i)}. Now we assume t h a t the change in states, at each offering, can be described by a nonhomogeneous Markov chain (unknown) having each transition matrix in M and initial distribution in So. Then the calculations So, Sl, $ 2 , . . . tell the possible distribution vectors after any offering. For the remainder of this section we will show when interval structures and convex structures are preserved under multiplication by M. It is i m p o r t a n t to note t h a t this is not always possible. For Markov set-chains, interval and convex structures are not necessarily preserved. E x a m p l e 2.8. In this example we show an interval M where M 2 is not convex and thus not an interval 9 Hence, neither interval structures nor convex structures of M are preserved under multiplication by M. Let M be the interval [P, Q] where
2.2. MARKOV SET-CHAINS
37
Then [P, Q] has vertices
~1: [~ ~] ~n~ ~: [~ ~1 Note that
011
EIE2 ---- 88 43_
and
E2E1 =
Ii i]
are both in M 2. Thus, 1 E --~E2 1
K = 1E1E2 + "2 is in convex M 2. Let A , B 6 M and set
[~
AB = K or
[~1-~ ]
[ab+89189188
[i i3]
a(1-b)+89189 =
[i i]
+
Comparing 2,1-entries shows that b = 89 But then the equation involving 1 + the 1,2-entries is ~a - a) = 88which has no solution. Hence, we conclude that K ~ M 2 and thus, M 2 is not convex.
89
For Markov set-chains with initial distribution sets, interval structures are not preserved. E x a m p l e 2.9. We show an interval So and an interval M such that SoM is not an interval. Thus, the interval structure of So is not preserved under multiplication by M. Let M = [P, Q] where
P=
[!1o Ol [i0!] 0
and
Q =
0
0
.
0
The vertices of M are
E1--
0 0
and
E~ =
0 0
38
C H A P T E R 2. I N T R O D U C T I O N T O M A R K O V S E T - C H A I N S
Let So = [p,q] w h e r e p = (1,0, 88 and q = ( 3 , 0 , 43-). T h e n So has vertices v, = ( ~3 , 0 , ~1) and v2 = ( ~1 , 0 , ~3) . Now, if x C So and A E M we can write x = (~vl + (1 - c~)v2
and
A = ~E1 + (1 - ~)E2, b o t h convex sums. T h e n x A = a ~ v l E 1 + a(1 - ~)VlE2 + (1 - c~)~v2E1 + (1 which
is
a
convex
o f v 1 E 1 ---- ( 4 , 16'3 96 ) , v i E 2
sum
(1216, 161,163), v2E2 = ( ~ , 16,3 l ) . where P=
=
--
0~)(1
--
(4,
~)v2E2
96 ' 3 ) ,
v2E1
=
Thus, if S o M is an interval it must be ~,q]
'16'
and
q=
16' 16'
"
Now note t h a t v = (~6, ~ , 9 ) is in ~,q]. But, since viE1 is the only v i E j with 9 as the last component, if x A has this last c o m p o n e n t it m u s t be t h a t x A = viE1. But viE1 ~ v and so S o M is not an interval. T h e g r a p h of S o M and ~, q] can be seen in Fig. 2.6.
I
~
I
Figure 2.6: G r a p h of S o M and
' 16 '
'
16'
"
S o m e w h a t remarkably, if M is an interval [P, Q] and So is convex then the convex structure of So is preserved under multiplication by M . To see this we need a lemma. L e m m a 2.5. Let M be an interval [P,Q]. Let x , y be stochastic vectors and (~,~ nonnegative numbers such that (~ + ~ = 1. For any A, B E M there is a K E M such that ~ x A + ~ y B = ((~x + fly)K.
2.2. M A R K O V SET-CHAINS
39
Proof. To construct K , let X = diag x, Y = diag y and define K = (aX + f Y ) + ( a X A + ~YB) + F where ( a X + f Y ) + is the Moore-Penrose inverse of a X + flY and the entries of F are 0 if axi + flYi > 0 fij : aij o t h e r w i s e . We show t h a t K E M. For this, if axi +/~yi > O,
kij =
axiaij + flyibij _ axi fYi OtXi q- flYi OtXi q- f Y i aij q- -axi + fYi bij
SO
Pij <_ kij <_ qij. On the other hand, if axi + f y i = 0 then kij = aij. Thus, again Pij ~_ kij <~ qij. Hence, P < K < Q. T h a t K is stochastic is clear, thus, K E M. Finally,
(ax + f y ) g = (ax + f y ) [ ( a X + f Y ) + ( a X A + f Y B ) + F] = e ( a X + f Y ) [ ( a X + f Y ) + ( a X A + f Y B ) + F] where e is the vector of l's,
= e(aXA + fYB) since e ( a X + 13Y)F = 0
= axA + f y B . [] Lemma
2 . 6 . Let M be an interval and So convex. Then Sk is convex for any
k.
Proof. The proof is by induction on k. For k -- 0 we have t h a t So is convex by hypothesis. Now, we suppose Sk is convex. Let xA, yB E Sk+l where x, y E Sk and A, B E M. Let a, f be nonnegative constants such t h a t a +/~ -- 1. Then by L e m m a 2.5 there is a K E M such t h a t axA + j3yB -- (ax + f y ) K . Since Sk is convex, a x + j3y E Sk and thus,
axA + f y B C Sk+l. Hence, Sk+l is convex and the result follows.
[]
C H A P T E R 2. I N T R O D U C T I O N T O M A R K O V S E T - C H A I N S
40
A result more useful in later c o m p u t a t i o n a l work follows. T h e o r e m 2.1. Let M be an interval and So a convex polytope. Then Sk is a convex polytope with vertices of the form giEil "'" Ei~ for some vertices g~ of So and some vertices Eij of M .
Proof. L e m m a 2.6 assures t h a t Sk is convex. X A l . . . A k C Sk. Write x = ~ akgk and each k binations of vertices in So and M , respectively. into x A 1 . . . Ak and expanding shows t h a t xA1 of vertices of the form s ... Eik as desired.
To prove the vertex part, let Ai = ~ O~ikEk a s convex comk
Substituting these expressions 9.. Ak is a convex c o m b i n a t i o n []
We have shown t h a t if M is an interval, M 2 need not even be convex. However, we can show t h a t the rows of the matrices in M 2 are convex polytopes. D e f i n i t i o n 2.6. Let M be an interval. For any row i, and any integer k > 1, define M k={x: xisthei-throwofsomeACMk}. C o r o l l a r y 2.4. Let M be an interval. Then for each i, and any integer k >_ 1, Mik is a convex polytope.
Proof. Let So = {ei} and apply the theorem.
2.3
[]
C o m p u t i n g steps in a M a r k o v set-chain
In this section we discuss c o m p u t i n g $1, $ 2 , . . . ,Sm numerically. Our m e t h o d requires t h a t So be a convex p o l y t o p e and M an interval. Thus, from Theorem 2.1, we know t h a t $ 1 , $ 2 , . . . ,Sin are all convex polytopes. Vertices, of course, completely determine convex polytopes. Thus, to c o m p u t e the convex polytopes $ 1 , . . . , Sm it is sufficient to c o m p u t e their vertices which is w h a t we will do. T h e vertices of the convex polytopes $1, $ 2 , . . . , Sm are c o m p u t e d , in general, as follows. A l g o r i t h m t o C o m p u t e V e r t i c e s o f $ 1 , $ 2 , . . . , Sin: Let v~~ -.. ,-r0~ (o) be the vertices of So and E l , . . . , E8 the vertices of M , an interval [P, Q]. We can c o m p u t e the vertices vl m) , 9 99 , ~rm~ (m) of Sm as follows. 1. I n p u t the vertices of So and the vertices of [P, Q].
2. For k = l to m do (a) c o m p u t e Wk = {v}k-1)Ej: i = 1 , . . . ,rk-1 and j = 1 , . . . ,s}. (By T h e o r e m 2.1, Sk = convex Wk.) (b) find the set Vk = {v~k) , 9 99 , -rk' (k) j~ of vertices of Sk from the vectors in Wk. 3. O u t p u t the sets of vertices 1/1, V2,... , Vm.
2.3. COMPUTING STEPS IN A M A R K O V SET-CHAIN
41
Thus, to compute the vertices of Sk, for any k, we must compute the vertices of [P, Q]. By a previous remark (following Lemma 2.4) [P, Q] can have (2n-1) n vertices. A large number of vertices of [P, Q] is not the only problem in computing Sk. As we will see later, the number of vertices of Sk can also grow as k increases. Thus, the set Wk in step 2a can grow as k increases. Its size can make the problem of computing $1,.. 9 , Sm even more impractical. For this monograph, we will consider computing $1,... ,Sm only in R 2 and R 3. And we do these two cases in two examples. E x a m p l e 2.10. Let M be the interval [P, Q] where
[
.35 .25
P=
.55 .65
]
and
[
Q =
.45 .35
.75 "
Let So be the interval [p, q] where p = [.4, .5] and q = [.5, .6]. Computing the vertices of [P, Q], using the remark following Lemma 2.4, we have .35 .35
El=
.35 .25
.65 ] .75 '
E2=
E3=
.25
.55 .75 '
E 4 ---- .35
.65] .65 '
[.45.55] .65
"
The vertices for [p, q] are v~~ = (.4, .6) and v~~ = (.5, .5). Compute
v~~ v~~
=- (.29,.71) : (.33,.67)
v~~ v~~
-= (.30,.70) = (.35,.65)
v~~ vl~
= (.35,.65) -- (.39,61)
v~~ v~~
-= (.35,.65) = (.4,.6).
The vertices of the convex hull of these vertices, namely $1, can be found by noting that (.29,71) has smallest abscissa and thus is a vertex while (.4, .6) has largest abscissa and thus is a vertex. See Fig. 2.7, part a. Now set v~1) : (.29, .71) and v~2) : (.4, .6) and repeat the technique to find $2. In this way, Sk can be computed for any k. Table 2.1 gives the computed vertices of $1, $2, $3, $4, and $5.
Table 2.1 T h e v e r t i c e s vl a n d v2 for Sk, k = 1 , . . . 5 k
~)1
v2
1 2 3 4 5
(.29,.71) (.279,.721) (.2779,.7221) (.27779,.72221) (.277779,.722221)
(.4,.6) (.390,.610) (.3890,.6110) (.3889,.6111) (.38889,.61111)
A sketch of $5 is shown in Fig. 2.7, part (b).
42
C H A P T E R 2. I N T R O D U C T I O N T O M A R K O V S E T - C H A I N S
x • $5
.72.
.79"
.61.
.6
.29
.27
.4 (a)
.39 (b)
Figure 2.7: Graphs of S1 and $5. E x a m p l e 2.11. Let P =
[o.25.50 : .25 .25
and Q =
[o.25.50 : .75 .75
with p = (0,0,0)
and q -- (1, 1, 1). Before making any actual computations, we recall that A3 is an equilateral triangle in R 3. We can put this triangle into R 2, as shown in Fig. 2.8,
Figure 2.8: Graphs of A3 and O(Aa). by using the transformation
[~/2
,/-g/2
It is easily shown that this map preserves convexity as well as distances, i.e. [ ] x C - yC[12 = [[x-y[12
for all
x, y E Aa.
2.3. COMPUTING STEPS IN A MARKOV SET-CHAIN
43
(Here I]" 112 is the 2-norm.) To return points back to A3 we can use
O-l(y)=yC++(1,O,O)
where
C+=
[-~202/2
v~/2
-1/v~
0 ]
v~/3
Given a finite set of points in R 2 there are various techniques to find the vertices of their convex hull. (Preperata and Shamos (1985) give several such techniques.) A simple technique is to begin at the left most point, compare slopes of lines determined from it to the remaining points, choosing the point yielding the largest slope to find the adjacent vertex. See Fig. 2.9, part (a). Continue to find the vertices on the upper polygonal path, and then find the lower polygonal path, of the convex hull, as shown in Fig. 2.9, part b
O
(a)
(b)
Figure 2.9: Constructing a polytope from points. Now [P, Q] has vertices
E1
.25 .25
.50 .75
E2 =
.25 .25
.50 .75
E3 =
.25 .75
.50 .25
E4 =
.25 .75
.50 .25
and [p, q] has vertices
vl = (1, 0, 0),
v2=(0,1,0),
and
v 3 = C 0,0,1).
Computing Eivj for all i and j gives twelve vectors but only four vectors w] = (0,.25,.75), w2 = (0,.75,.25), w3 = (.75,.25,0), w4 = (.25,.75,0) are vertices of $1. Thus, [p, q]M = $1 = conv{wl, w2, w3, wa}. To compute $2 we multiply the four vertices E l , . . . , E4 and the four vertices w l , . . . ,w4. This gives sixteen vectors. Of these, only four are vertices. (If W l , . . . , w~ are the vertices of Sk, many of the vectors wiEj are interior to Sk+l. Some are duplicate vertices while some lie on a segment of the boundary of Sk+l.) This can be continued to compute $ 3 , . . . 9 To allow the study of data, in Table 2.2, we have given the vertices of S0, $2, $4, and S 6.
44
CHAPTER 2. INTRODUCTION TO M A R K O V SET-CHAINS
T a b l e 2.2 T h e v e r t i c e s o f Sk for k - - 0,2,4,6
Sk:
So:
Vertices of Sk 0 0
1
0 1 0
0 0 1
0.25 0.625 0.0625 0.0625
0.6875 0.3125 0.6875 0.3125
0.0625 0.0625 0.25 0.625
$4:
0.5 0.5 0.21875 0.4921875 0.11328125 0.11328125 0.16015625 0.17578125
0.38671875 0.33984375 0.66796875 0.33203125 0.38671875 0.66796875 0.33984375 0.33203125
0.11328125 0.16015625 0.11328125 0.17578125 0.5 0.21875 0.5 0.4921875
$6:
0.454589844 0.454589844 0.204589844 0.440429688 0.198730469 0.428710938 0.196289063 0.422363281 0.132080078 0.194580078 0.132080078 0.222900391 0.135009766 0.136962891 0.237548828 0.244384766
0.413330078 0.350830078 0.663330078 0.336669922 0.666259766 0.333740234 0.666748047 0.333251953 0.413330078 0.350830078 0.663330078 0.336669922 0.666259766 0.666748047 0.333740234 0.333251953
0.132080078 0.194580078 0.132080078 0.222900391 0.135009766 0.237548828 0.136962891 0.244384766 0.454589844 0.454589844 0.204589844 0.440429688 0.198730469 0.196289063 0.428710938 0.422363281
Further, Table 2.3 shows the growth o f t h e vertices as k increases.
T a b l e 2.3 G r o w t h o f v e r t i c e s in Sk
Sk
$1
$2
$3
$4
$5
SO
Number of vertices
4
4
6
8
12
16
2.3. COMPUTING STEPS IN A M A R K O V SET-CHAIN
45
In addition, we show the graph of $4 and the general shape of Sk in Fig 2.10.
(a)
(b)
Figure 2.10: Graph of $4 and general shape of Sk.
When the number of vertices increases too fast, it may be advisable to compute e-approximations to the desired convex polytope. This can be done by adjusting the technique so that if vi,vi+l,vi+2 have been selected for the polygonal path, and [tv~ - V~+l][ < e, ]]vi+l - vi+2[I < e then delete vi+l. The resulting convex polytope is within e, in the Hausdorff metric d, of the convex polytope determined by the algorithm. Of course, with repeated iterations, finding $1, $ 2 , . . . , this error could grow. However, if M is contractive (we will show when this occurs in the next chapter), the following theorem helps access the error between our approximations and the actual set. Let Z be a convex polytope. Define Z as an e-approximation, determined as above, to Z. Thus, d(Z, Z) < e.
T h e o r e m 2.2. Let M be, an interval. Let M is a contractive map, that is
d(XM, Y M ) <_Td(X, Y)
for all compact sets X, Y where T < 1. Then, for any convex polytope X ,
d(XM k,XMM...M)
<_
1- T k 1 I _ T e < _ T----_Te.
CHAPTER 2. INTRODUCTION TO MARKOV SET-CHAINS
46
Proof. First note that d(XM, XM) < e. Thus, d ( X M 2, X M M ) < d(XMM, X M M ) + d(XMM, X M M ) < Td(XM, X M ) + e < Te+e.
H(XM 3, X M M M ) <_d(XM2M, X M M M ) + d ( X M M M , XM1VIM) <_T d ( X M 2, -X---MM) + e _< T ( T ~ + e) + < 7"2e + Te + e. And, more generally
d ( X M k, X M M . . . M) <_d(XMk-IM, X M . . . MM) + d(XM...MM, XM...MM) <_Tk-lc + ... + Te + e l -
T k
1
I _ T e"
-< l _ T e ~
[]
2.4
Hi-Lo method, for computing bounds at each step
As seen in the last section, the number of vertices can be a serious problem when computing the convex polytopes $1,$2,... ,Sin. In R n, for other t h a n very small values of n, we consider this computation impractical. W h a t is practical, however, is the computation of component bounds on the vectors in
Sk, k = l , . . .
,m.
E x a m p l e 2.12. Using
P=
.25 .25
.50 .25
and
Q=
.25 .75
.50 .75
as in Example 2.11, if x E $4 then from the data in Table 2.2, .11328125 _< xl _< .5 .33203125 < x2 _< .66796875 .11328125 _< x3 _<_.5. Lines demonstrating the bounds on the components of $4, as shown in a previous example, are given in Fig. 2.11.
2.4. HI-LO M E T H O D , F O R C O M P U T I N G B O U N D S A T E A C H S T E P
47
\ \
i e
s
~,
I
Figure 2.11: Graph of interval containing St. Note t h a t to compute component bounds on vectors in any compact set Z of R ~ requires us to compute 2n numbers; namely, 11,.. 9 , In and h i , . . 9 , hn where
In<xn~_hn
for all
xEZ.
We will show in this section that these numbers can be calculated without calculating the vertices of M = [P, Q] or calculating the vertices of any $ 1 , . . . , Sin. This will be done by applying the Hi-Lo method, an algorithm which produces tight component bounds on each of M, M 2 , . . . , M TM and on each of $1, $ 2 , . . . , Sin. D e f i n i t i o n 2.7. Matrices L and H are called column tight component bounds on M provided L < A < H f o r a l l A E M, and (i) if I k is the k-th column of L, then there is a matrix A E M with k-th column 1k, and (ii) if h k is the k-th column of H , then there is a matrix A C M with k-th column h k. Recall t h a t by Corollary 2.3, if M is a tight interval [P, Q] then P and Q are column tight component bounds on M. To find column tight component bounds on each of M 2, M 3 , . . . , M m, we provide a general method of taking column tight component bounds L , H on any M k and showing how to find column tight component bounds L, H , on M T M for k = 1 , 2 , . . . , m - 1. Thus, column tight component bounds on M produces column tight component bounds on M2; column tight component bounds on M 2 produces column tight component bounds on M 3, and so on.
48
CHAPTER
2.
INTRODUCTION
TO MARKOV
SET-CHAINS
T h e c o m p u t a t i o n s of L = ([ij) and H = ([zij) are done componentwise. For simplicity of notation we let p, q be the i-th rows of P, Q respectively and l, h the j - t h columns of L, H respectively. We let m be a set of column vectors such t h a t 1 and h are column tight bounds on m. Then, we need to show how to find l, h which are tight bounds on [p, q ] m . We do this by the Hi-Lo m e t h o d . Hi-Lo Method.
Given p , q , l , h
we find tight b o u n d s l , h on ~ , q ] m
where
l<m<_h.
(i) [: Let I = ( 1 1 , . . . , l n ) t. Suppose lil <_ li~ < . . . <_ l i . . Let t be an integer such t h a t qi~ + " "
+ qit + Pi~+~ + Pi,+2 + " "
+ Pi,, ~ 1
and
qil + " " " T qi~ + qit+, T Pit+2 + " " " + Pi~ ~ 1.
T h e n there is a n u m b e r y such t h a t Pi~+~ <_ Y <_ qi,+, and qi~ + " " + qit + Y + Pi~+2 + " " + P i . = 1 .
Define i
fi =
I~ I.Pi
if i = il,...
,it
if i = it+l
(2.3)
if i = it+2,. 99 ,i,~.
These numbers define a 1 • n vector p in [p, q] called a lo v e c t o r . Less technically, the lo vector/5 is the vector in [p, q] which has the m o s t large entries in the positions where l has its small entries. Finally, set [ = fl the lo vector in [p, q] times the low column, 1. (ii) h: Let h = ( h l , . . . , h n ) t. Suppose h i , <_ hi2 <_ . . . <_ h i . . integer such t h a t Pi~ + ' " + p i ~
~_ 1
-i-Pi~+, + q i , + 2 + ' " + q i .
Let s be an
and
Pil + " 9 " + P L + qi~+l T qi,+2 + 9 " 9 + qi~ ~ 1.
T h e n there is a n u m b e r x such t h a t Pi~+~ _< x < qi~+l and Pi~ + " " + Pi. + x + qi.+2 + " " + qin = 1 .
Define Pi ~i =
i f / = i l , . . . ,is
(2.4)
if i = is+l kqi
ifi=is+2,...
,i,~.
These numbers define a 1 • n vector ~ in ~v, q] called a h i v e c t o r .
2.4. HI-LO METHOD, FOR COMPUTING BOUNDS A T E A C H S T E P
49
Less technically, the hi vector c] is the vector in [p, q] which has the most large entries in the positions where h has its large entries. Finally, set h = qh the hi vector in [p, q] times the high column h. A detailed example may be helpful. E x a m p l e 2.13. Let p = (.25, 0, .25), q = (.75, 0, .75), and l=
.25 , .50
h=
.75 . .50
(i) To compute [, order 11 _< 12 _< 13. For the lo vector put the largest possible entries into the first entries. Thus p = (.75,0,.25)
and
[ = f l = .3125. (ii) To compute h, order h3 ~ h2 ( hi. For the hi vector put the largest entries into the first entries. Thus t] = (.75,0,.25)
and
= qh = .6875. Thus, as we will show, .3125 <: ac < .6875 for all a E [p, q] and c E m. And the bounds are tight. We show that l, h, as defined above, provide the desired bounds. T h e o r e m 2.3. Let [p, q] be an interval and l, h column tight bounds ]or a set m o] column vectors. Then [, h are tight bounds on ~9, q]m.
Proof. We obtain this result with a rather general argument. Let k, k be numbers with k < k. Let a,/3 be numbers. Then for any number e>0, ak+~k<(a-~)k+(~+~)k. Thus, increasing the coefficient of k and decreasing the coefficient of k increases the number. To apply this argument, first note that if a E [p, q] and c E m then
aI < ac < ah.
50
CHAPTER
2.
INTRODUCTION
TO MARKOV
SET-CHAINS
By the general argument, al is smallest by choosing a as the lo vector and is largest by choosing a as the hi vector. Thus,
ah
~
Algorithm to C o m p u t e C o m p o n e n t B o u n d s on Mk+1: Given column tight bounds k=l,...
L,H
on
M k,
we find column tight bounds
L,H
on
,m.
To compute L: the columns of L are computed sequentially. 1. Input P, Q, L, H. 2. For j = 1 to n do (computing the j-th column P of L) (A) Define l =
lj
(B) Sort the entries of l li, < li2 <_ ..- ~ li.. (C) F o r i = l t o n d o (a) Search for t such that qiil + " " + qii, + Pit+~ + " " + Pin < 1 qii~ + 9 9 9 + qii, + qii,+~ + Pii,+~ + 9 9 9 + P i . > 1
(b) Define y = 1 -
qii~ . . . . .
qii, - Pii,+2 . . . . .
Pii,,
(c) Define/~i = fi as in (2.3). (D) Define L = (E) Define
[J = L l
3. Define L = [/1 ...
in].
4. Output L. To compute H: the columns of H are computed sequentially. 1. Input P, Q, L, H.
M k+l
for
2.4.
HI-LO METHOD,
FOR
COMPUTING
BOUNDS
AT EACH
STEP
51
. For j = 1 to n do (computing the j-th column hJ of H). (A) Define h = h j (B) Sort the entries of h hi~ <_ h~2 <__ . ' . <_ hi~.
(C) F o r i = l t o n d o (a) Search for s such that + Pi, + Pio+~ + qi.+2 + " " + qi, <_ 1
Pil + " "
Pi~ + "" 9 + Pi, + qio+~ + qi,+2 + "" 9 + qi,, > 1.
(b) Define x = 1 - Pil + "" " + Pi, + qi,+2 + "" " + qi, (c) Define Hi = q as in (2.4).
(D) D e f i n e H =
[ ; 1]
(E) Define hJ = H h 3. Define H = [hi ... ~n]. 4. Output H. Of course, the algorithm can be repeated to find column tight bounds on M k for any k. E x a m p l e 2.14. As in Example 2.11, let
p =
.25 .25
.50 .25
and
Q=
.25 .75
.50 .75
.
In Table 2.4, we list the lower and upper bounds for M 2 , M 4 , and M e. These bounds can be compared to the data for $2, $4, and $6 given in Table 2.2.
52
C H A P T E R 2. I N T R O D U C T I O N T O M A R K O V S E T - C H A I N S
T a b l e 2.4
Mk k = 2:
-[
.25 .0625 .1875
L o w e r a n d u p p e r b o u n d s o n M k f o r k = 2, 4, 6, a n d 44
]
Lower bound Lk .3125 .(1625 .3125 .25 .375 .1875
.332(13125 .3359375
.1796875 .16015625
[
.625 .1875 .3125
]
Upper bound Hk .6875 .1875 .6875 .625 .625 .3125
k = 4:
.11328125 .16015625
I,: = 6:
.132080078 .149169922
.333251953 .15625 .333,1961194 .149169922
.396240234 .666748047 .4545898,14 .,1133311{178.6(~651)3!106 .,|13331)078
k = 44:
.142857143 .142857143
.333333333 .333333333
.'12857143 .42857143
.142857143 .142857143
.33984375 .38671875
.66796875 .664(1625
.666666667 .666666667
.5 .38671875
.42857143 .,12857143
Having computed column tight component bounds on each of M, M 2 , . . . , M m the Hi-Lo method can be applied to compute component bounds on SoM, S o M 2 , . . . , S o M TM. We demonstrate this with an example. E x a m p l e 2.15. A laboratory animal moves within the structure drawn in Fig. 2.12. Given t h a t the animal is in a room, the probability that the animal chooses to stay or go to another room, per step of observation, depends on the physiological state of the animal.
Figure 2.12: Lab structure for animal. Assuming these physiological states represent small changes in the probabilities, the bounds P and Q on the corresponding transition matrices are as given below.
2.4. HI-LO METHOD, FOR COMPUTING BOUNDS A T EACH STEP
A A [.423
B .459 P = B /.029 .677 C L.OOO .478
C .043] .222 / .461j
A A [.473
Q =B /.079 c L.036
B .509 .724 .528
C .093] .272|. .511j
If we now compute the column tight bounds on M 5 we have [.043 L5 = |.031 [.029
.593 .594 .594
.255] ".124 .266| _< A1...A5 _< .111 .269J [.101
.654 .656 .656
Now suppose So = [p, q] where p--- (.4, .1, .2),
q = (.6, .3, .4).
We compute the lo-vector [ for SoM 5. (i) For the first entry of [, order the first column of Ls. .029 < .031 < .043. So the Io vector in So is I = (.4, .2, .4) and
r.o43]
t t.031 / = .0350. L.029J For the second entry in [, note .593 < .594 ___.594 So the lo vector in So is l = (.6, .2, .2) and
r.593]
l/.594 / --.5934. [.594J The third entry of [ is .2600. We now compute the hi-vector f~ for SoM 5. (ii) For the first entry of h, order the first column of//5, .101 < .11I < .124. So the hi vector in So is h = (.6, .2, .2) and [-1241 h [.111[ --.1168 [.101[ The second and third entries of h are .6552 and .3460.
.339] .350| -- Hs.
.351j
53
54
C H A P T E R 2. I N T R O D U C T I O N
TO MARKOV
SET-CHAINS
Thus, (.0350, .5940, .2600) _< xA1 . . . A5 <_ (.1168, .6552, .3460) for any x E S0; A 1 , . . . ,As E M. Hence after 5 steps the probabilities of the laboratory animal being in A is between .0350 and .1168, in B between .5934 and .6552, and in C between .26 and .346. To access the difference in the lower and upper component bounds, it is important to note that IIQ - PIt = .15
Related
research
notes
The basic work in this chapter was taken from Hartfiel (1981a, 1987, 1991a). Problems with uncertainty in empirical or theoretical information arise in areas other than that discussed in this chapter. Below, we review some of the mathematics, arranged according to area, which has been developed in these areas. (a) Ax----b. There are several ways that uncertainty has been handled in systems of linear equations. For the first, an interval technique, let R < S be n x n real matrices and r < s be n x 1 real vectors. The interval equation
[R, S]x = [r, 8]
(1)
denotes the set of all equations A x = b where R < A _< S and r < b < s. Most of the work on interval equations concerns obtaining information on the set S = {x: x is a solution to some equation in [ R , S ] x = [r,s]}. A rather complete study of equation (1) can be found in Alefeld and Herzberger (1983) or Neumaier (1990). These books also provide a large list of references to research on this equation. In addition, Garloff and Schwierz (1980) provide an extensive bibliography of papers on interval mathematics. For the geometry of the solution set see Hartfiel (1980), Alefeld et al. (1997), or the two previously mentioned books. A second method used to handle uncertainty in A and b was described by Samuelson (1955). In this description only the signs § 0 of A and b are known. The corresponding qualitative problem is to decide when this information is sufficient to determine the signs § - , 0 of solutions to A x = b. Lancaster (1962) initiated a mathematical study, using properties of determinants, of this problem. As pointed out by Gorman (1964), Lancaster made mistakes in his paper, which is not particularly unusual, in pioneering work. Lancaster (1964, 1965) followed Gorman's article, and using some of the results there, provided a qualitative result for this problem, in terms of cones or whether the coefficient matrix can be partitioned in a certain way. Maybee and Quirk (1969) published a review paper and the book of Brualdi and Shader (1995) includes more on this problem.
2.4. HI-LO M E T H O D , FOR C O M P U T I N G B O U N D S A T E A C H S T E P
55
(b) x'(t) = A ( t ) z ( t ) . Several methods are available for dealing with inexact data in systems of linear differential equations. For an interval approach, consider R < S where R, S are n • n real matrices. Hartfiel (1985) assumed some conditions on A(t) and described Ct = {x(t): x'(t) = A(t)x(t) where R < A(t) < S}. He showed that C~, the closure of C~, is a convex polytope and gave conditions that assure lim C~ exists, the limit using the Hausdorff metric. The set Ct, both t--~oo compact and convex, may have many extreme points which makes the actual calculation of Ct somewhat impractical. Component bounds for C~, which would make this approach more computationally attractive, however, have not been done. For the system where A(t) = A is known to be constant, Faedo (1953) asks under what conditions does a family of polynomials (or say corresponding characteristic polynomials)
/ ( z ) = z " + a l z ~-1 + . . . + a n
(2)
where ai E [~, f~i] for all i
(3)
have its zeros in the left half-plane. Kharitonov (1978) showed that if the 2n polynomials, whose/-th coefficient is ai or/~ for all i, have zeros in the left halfplane, then all polynomials described by (2) and (3) do also. Remarkably, he then shows that this decision can be made by considering only four polynomials. Karl (1984) extends Kharitonov's work to complex numbers. Bialas (1983) tries to show that all A E [R, S] are stable if and only if the vertex matrices in [R, S] are stable, which may seem reasonable. However, Barmish and Hollot (1984) as well as Karl et al. (1984) show that this is incorrect. A qualitative approach to systems of linear differential equations, also introduced by Samuelson (1955), was studied by Quirk and Rapport (1965) where they considered when a matrix A was stable based on the signs + , - , 0 of its entries. Maybee and Quirk (1969) published an article reviewing qualitative stability while Brualdi and Shader (1995) cover the topic in their book. Lugofet (1992) is another book concerned, in part, with this topic. For additional topics, see Eschenbach and Johnson (1991, 1993), as well as Eschenbach (1993), for work on eigenvalues of qualitative matrices. Fhrther Kaszkurewitz and Bhaya (1989), Bone et al. (1988), as well as Jeffries and Van den Driesche (1991) consider difference equations in this area. Qualitative stability has been used in fields other than economics. For its use in chemistry, see Clarke (1975) and Tyson (1975), in ecology see 3effries (1974), Levins (1974), and Redheffer and Walter (1984). Brualdi and Shader (1995) provide further results on this topic. (c) xk+l = xkAk + bk. For an interval approach to handing uncertainty in this equation, let 0 < P < Q be n x n matrices, and let 0 < p < q and 0 < r < s be
56
CHAPTER 2. INTRODUCTION TO MARKOV SET-CHAINS
1 • n vectors. Hartfiel (1995) considers
[P,Q] = {A: A is and n • n nonnegative matrix where P
< _ ~ a i k <_s~ for alli} k
[p,q]={b:
bisal•
Letting Xo = [l, hi for some 1 • n vectors 0 < l < h, he defines the sequence of sets
Xk+l = Xk[P, Q] + [P,q]. Conditions are given which assure that, in the Hausdorff metric, {Xk}k>l converges. (d) R a n d o m m a t r i x p r o d u c t s . The most studied method of handling uncertainty in data for matrix products is by using random matrices. There are several books on this topic. For example, see Mehta (1991), Carmeli (1983), Cohen et al. (eds.) (1986), and Cristanti et al. (1993). These books also provide larger lists of research papers concerning this topic. (e) S e m i g r o u p s . Stochastic matrices and some sets of nonnegative matrices form compact topological semigroups. All are well studied by topological semigroupers. Schwarz (1964) showed how basic topological semigroup results give information about Markov chains. Mukherjea (1979), as well as Mukherjea and Chaudhuri (1981), uses measures on topological semi-groups and a convolution corresponding to matrix multiplication to establish various results, some of which were known, on matrix products. See Johnson (ed.) (1990) for Mukherjea's survey article on this topic. Topological semigroups can be used to determine limit theorems for matrix products without the use of measures. Hartfiel (1974b) defined for any positive stochastic vector, S(y) = {A: A is stochastic and yA = y}. (Also see Gregory et al. (1992) for some description of this set and Loewy et al. (1991), for a nonnegative generalization of it.) This is a topological semigroup which contains only one rank 1 idempotent. Thus, if each Ai E S(y) is scrambling, then A1A2... Ak must converge to that idempotent regardless of the choices 9A1, A 2 , . . . . More general results are also given there. (f) C a u s a t i v e m a t r i c e s . Harary et al. (1979) use a causative matrix approach to changing data in transition matrices. They considered sequences of stochastic matrices
A1,A2= A1C,
A3= A2C,...
for some constant C where C was called a causative matrix. Thus, Ak+l = A l e k for all k. The behavior of such a system, of course, is determined by C. Much of the theory of causative matrices concerns when matrices A1 and C exist so A1C k is stochastic for all k. The initial work on causative matrices was developed for 2 • 2 matrices. Later, Pullman and Styan (1973) extended this work to n • n matrices. (g) M a r k o v chains. More closely related to Markov set-chains are Markov chains where the fixed transition matrix is uncertain. Courtois and Semal (1984)
2.4. HI-LO METHOD, FOR COMPUTING BOUNDS AT EACH STEP
57
and Hartfiel (1983, 1994a) considered the sequence
A, A 2, ... where A is stochastic and known only within some interval information. If the sequence {Ak}k>_l converges to a rank one matrix (A regular matrix A would assure this), then t h a t rank one matrix has rows formed from the stochastic eigenvector for A. Thus, the set of stochastic eigenvectors belonging to the set of A's is important. The above papers describe, under various settings, this set. Wesselkamper (1982) showed how some of this work can be applied to program schemata.
Chapter 3
Convergence of Markov Set-Chains In this chapter we provide conditions which assure t h a t a Markov set-chain, or related such chain, converges. In addition, we give a description of the limit set.
3.1
U n i f o r m coefficient of ergodicity
To o b t a i n convergence criteria for Markov set-chains, we extend the notion of coefficient of ergodicity 7- to a transition set M . Of course, 7- can vary over M. A b o u n d on this variation, for intervals, follows. Theorem
3.1. L e t M be the interval [P, Q] and A , B E M .
Then
IT(A)- 7-(B)I < IIA- Bll _< IIQ- PII. Proof. For each i, define ~i = bi - ai where ai and bi are the i-th rows of A, B respectively. T h e n 1
T ( A ) = ~ m ~ IIa, - ~11 1
= - m a x It(hi - ei) - (bj - ej)ll 2 i5 1 1 < -~ m a x Nbi - bjll + - m a x llei -
i,j
2
i5
1
< T ( B ) + ~ max([le~ll + Ilejll) %3
1
< T ( B ) + ~(2)m/ax Ileill
< T ( B ) + lib - All.
ejll
60
CHAPTER
3.
CONVERGENCE
OF MARKOV
SET-CHAINS
Similarly, T(B) < T(A) +
lib
- All.
Thus, IT(A) - T(B)I
_< l i b - All.
Finally, using t h a t Pi and qi are the i-th rows of P and Q respectively, l i b - All = m a x Ilbi - ai[I _ miax Ilqi - pill = I1Q - PII.
T h e result follows.
[]
We extend 7- to M by using the largest value of 7- there. D e f i n i t i o n 3.1. For any M , define 7-(M) = m a x 7-(A).
(3.1)
AEM
We call T ( M ) the uniform coefficient of ergodicity for M . Note t h a t since 7- is continuous and M c o m p a c t , the m a x i m u m of 7-(A) over all A E M is achieved and thus equation (3.1) defines 7-(M). Also, note t h a t since 7-(A) _< 1 for all A E M it follows t h a t 7-(M) <_ 1. W h e n M is an interval, a b o u n d on 7-(M) is rather easily c o m p u t e d . Theorem
3.2. Let M be the interval [P, Q]. Then 1 7-(M) < - m a x --2
i,j
max{lq/k-
P3kl,
Iqjk -
Pikl}.
k=l
Proof. Let A E M . T h e n 1 T ( A ) -- = m a x Ilai - aj H 2
i,j
1
= - max ~ 2 i,j
'~
laik - ajkl
k=l n
< -1 m a x ~ --2
i,j
max{lqik - PjkI, Iqjk - Pikl}.
k=l
[] Example
3.1. Let M be an interval where P = [:~ :3] and Q = [:47 :~]. T h e n 1
T ( M ) = ~[max{[.7 - .21, 1.4 - .51} + max{I.5 - .61, 1.8 - .31} ]
= ~[.5 + .5] = .5. If T ( M ) = 1 it can be t h a t T ( M k) < 1 for some k.
3.1. UNIFORM COEFFICIENT OF ERGODICITY Example
61
3.2. Let M be an interval [P,Q] where P =
[.~4 o 0 1 and Q = :4.4 Note t h a t because of the 0 - p a t t e r n of the matrices in M, T(M) = 1. L
[, o 0 ] t o6:6.6 J " However, since
p2 ___ .56 .16
o o0]
.16 .32
and
Q2=
~
[1~176 .96 .36
.16
.36 .72
.36
we have 1
T ( M 2) <_ T ( [ p 2 , Q2]) _< m a x 2{.44 + .36 + 0, .84 + .72 + .36, .80 + .56 + .36} I
= m a x 2{.80, 1.92, 1.72} =
~961
T h e i m p o r t a n c e of the uniform coefficient of ergodicity is t h a t it shows the contractive n a t u r e of a M a r k o v set-chain. 3.3. Let X, Y be nonempty compact subsets of An. Then, using the Hausdorff metric, d(XU, YM) <_T(M)d(X, Y).
Theorem
Proof. By definition of 5 and the continuity of f(z) = min Hz - w H w E Y,~/
5(XM, YM) = m a x ( min [[z - w[I) zEXM
=
wEYM
m i n [ [ 2 - wl]
wEYM
for some 2 E X M . Writing 2 = xA where x E X and A E M we have =
rain IIxA-w[[
wEYM
<_ IIxA - yAll for any y E Y. _< I](x - y)A]l. Since this inequality holds for any y it holds for ~ such t h a t vmi~ Iix-vH = Iix-~]]. Thus
~(XM, YM) <_T(M)Hx - Y[I < T(M) m a x ( m i n IIx - yll) --
xEX
yEY
<_T(M)5(X, Y). Similarly,
~(YM, XM) <_T(M)6(Y, X) and so, d(XM, YM) <_T(M)d(X, Y). []
C H A P T E R 3. C O N V E R G E N C E OF M A R K O V SET-CHAINS
62
Thus, if T ( M ) < 1, M is contractive. Furthermore, we have the following. C o r o l l a r y 3.1. For any positive integers k,r, and s where k = r +s, T ( M k) < T(Mr)T(M~).
3.2
Convergence of Markov set-chains
In this section we develop some basic criteria which assures that a Markov setchain converges. This requires a few preliminary results. D e f i n i t i o n 3.2. For any transition set M, define
Soo = f i A n M k. k=l
We call Soo the limit set for the Markov set-chain, with initial distribution set An, An,AnM,.... We show that S ~ exists for any transition set M and t h a t every Markov set-chain, with An the initial distribution set, converges to Soo. L e m m a 3.1. For a Markov set-chain, with initial distribution set An,
AnM, AnM2,. .. converges to the compact set S ~ . If M is an interval then Soo is convex. Proof. For simplicity of notation we let A = An. Using this, note t h a t A M k+l C_ A M k
for all
k.
From this, S ~ r 0 and compact follows since it is the intersection of compact sets. ghrther, if M is an interval then Theorem 2.1 assures that A M k is convex for each k and thus, S ~ is convex. Now, let e > 0 be given. Suppose there is no integer K such that for k > K ,
d ( A M k, Soo) < e. Then there is a subsequence A M kl, A M k 2 , . . . such t h a t
d ( A M k ' , S ~ ) >>_e for all
i.
Since Soo C A M k' for all i, there is a zi E A M k~ such that d({zi}, Soo) > e. Now, since A is compact and each zi E A it follows t h a t zl, z 2 , . . , has a limit point z C A. And, by the continuity of d, d({z}, Soo) _> e. But, since A M k+l C_ A M k for all k, for any k, Zk E A M k~ for all k > ki, and thus z E A M k'. H e n c e z E A M k for a l l k and so z E Soo. This yields a contradiction from which it follows t h a t AM, A M 2 , . . . converges to Soo. []
3.2. CONVERGENCE OF M A R K O V SET-CHAINS
63
General convergence criteria requires the following notion. D e f i n i t i o n 3.3. Suppose r is an integer such that T ( A 1 . . . A ~ ) < 1 for all A1,.. 9 , Ar E M. Then M is said to be product scrambling and r its scrambling integer. The importance of product scrambling follows. L e m m a 3.2. If M is product scrambling and r its scrambling integer then
T ( M ~) < 1. Further, if s is a positive integer, then T ( M ~+s) <_T(M~). Proof. Since T is continuous and M ~ compact it follows that T achieves a maximum in M r. Since M is product scrambling and r its scrambling number, T ( M ~) = a < 1. The second part of the lemma follows from Corollary 3.1. [] The limit set Soo satisfies the following. C o r o l l a r y 3.2. The limit set Soo satisfies that SooM = S ~ . If M is product
scrambling, then Soo is t)~e only compact subset of An that satisfies this property. Proof. For the first part of the corollary, note that by Theorem 3.3, d(Soo, SooM) <_ d(Soo, A,~M k+l) + d(A,~M k+l, S ~ M ) <_ d(Soo, A~M k+l) + d(A~M k, S~). By Lemma 3.1, d(Soo, A,~M k) converges to 0. Thus,
d( Soo, SooM) = 0 and S ~ M = Soo. For the second part of the corollary, let U be a compact subset of An that satisfies U M = U. If r is the scrambling number for M, then
d(U, Soo) = d(UM r, SooM ~) < T(M~)d(U, S~). Since T ( M ~) < 1, d(U, Soo) -= 0 and U = S ~ .
[]
Our general limit result can now be shown. T h e o r e m 3.4. Suppose M is product scrambling with scrambling integer r. Let
So be a nonempty compact subset of A,~. Then, for any positive integer h, d(SoM h, Soo) <_ Kfl u where g = [T(M*)]-ld(So,Soo) and fl = T(M~)~ < 1. Thus, lim S0M k = k--+~
Scr
64
CHAPTER 3. CONVERGENCE OF M A R K O V SET-CHAINS
Proof. Write h = rq + s where 0 < s < r. Then by Corollary 3.2 d(SoM h, Soo) = d(SoM h, S~oM h)
= d(SoM rq+8, ScoM rq+s) < d(SoM rq, Soo Mrq)
<_T(Mr)qd(So, S~). Now, T(Mr) q = [T(Mr)~] rq = [ T ( M r) 5 ] - ~ [ T ( M ~) ~]~q+s _< [T(M~)]-I [ T ( M ~) }]~q+s
< [T(M~)]-~/3 h. Thus, the theorem follows.
[]
We now extend our results to Markov set-chains. This requires a description of the limit set. D e f i n i t i o n 3.4. Define the limit set of a Markov set-chain as M ~176 = {B: B is a rank one matrix with first row in Soo}.
(3.2)
It follows by Lemma 3.1 that M ~ is compact and that if M is an interval, M ~176 is also convex. We also need an additional definition. D e f i n i t i o n 3.5. Let R be a compact set in ~n. Then R1 = {a: a is an first row of some matrix A E R}. The following theorem is helpful in converting stochastic vector theorems to stochastic matrix theorems.
Let R , T C f~n be compact sets with T containing only rank one matrices. Then
T h e o r e m 3.5 ( M a t r i x C o n v e r s i o n T h e o r e m ) .
d(R,T) <_ d(R1,T~) + 2T(R). Proof. We use the notation that ck denotes the k-th row of C. Let A G R. Let B e T b e such that [ [ a l - b l [ [ _< d(R1,T1). Then B[[ = m/ax [[ai -bi[[ <_ m/ax [[ai - all[ + [[al - b l [ ] _< 2T(R) + d(R1,T1). R C_T + d(R1,Ta) + 2T(R). Let B E T. Let A G R be such that [151-a11[ _< d(Rt,T1). Then, B[I = miax [[ai - bi[[ <_ m/ax I[ai - eli[ + [lal - bl[[ _< 2T(R) + d(RI,T1). T C_ R + d(R~,T~) + 2T(R). P u t together, d(R,T) <_d(R1,T1) + 2T(R).
I[AThus, [[AThus, []
3.2. CONVERGENCE OF M A R K O V SET-CHAINS
65
Using this theorem and (3.2) we have the following consequence of Theorem 3.4. C o r o l l a r y 3.3. Suppose M is product scrambling with scrambling integer r. Then there are constants K and ~, 0 < ~ < 1, such that
d(M h, Moo) < K ~ h. Thus, lim M k = M ~176 k -+ oo
[]
Proof. Let So = {el} and use 2T(M h) < 2[T(Mr)]-I~ h.
Thus, if M is product scrambling and we compute lower bounds Lk and upper bounds Hk on the matrices in M k then {Lk}k>O and {Hk}k>O converge. We write Loo = lim Lk k--+oo
Hoo = lim Hk.
(3.3)
k--~oo
E x a m p l e 3.3. Let M be the interval [P, Q] where P=
[:23:32]
and
Q = [:~
:87].
Computing lower and upper bounds on M ~ , we have [.222222222 Loo = [.222222222
.222222222] [.777777778 .222222222] ,Hoo = i..777777778
.777777778] .777777778]"
We show how Loo and Hoo are used in an applied situation. E x a m p l e 3.4. A machine is listed as either up or down on a work day. The probabilities of the machine changing states depends on the newness of the parts in the machine. If the transition matrices for the corresponding nonhomogeneous Markov chain are bounded by
=
u .05
.75 .85
and
Q=
[.25] .15
.85 .95 '
we can find bounds on the long run probabilities. These bounds are listed in Table 3.1.
66
C H A P T E R 3. C O N V E R G E N C E OF M A R K O V S E T - C H A I N S
T a b l e 3.1. L o w e r a n d u p p e r b o u n d s o n p r o b a b i l i t i e s o f machine breakdown Step k
4
8
12
Lower bound Lk
Upper bound Hk
[.05565 [.05555
[.16675 [.16665
.83325] .83335]
.94435] .94445J
[.055555565..833333326] [.055555555 .833333336J
[.166666675 [.166666665
[.055555555 83333333
[.166666667 94444444
[.055555555
[.166666667
.833333334J
.944444434] .944444444J
.94444444~
In terms of random variables, if the nonhomogeneous Markov chain is in s/ initially (sl = d and s2 = u), define u(k)
ij =
Then, using that A I
/10 if the chain is in sj in step k, and otherwise.
%
.. 9 A k
=
ra!k)1 ~ ~3 J,
E (Uki j)
:
t_(k) tij 9
Thus, for all k > 12 (there was no change Lk or Hk after k > 12), .055555555 < ~/ ~ ~/'il(k) <- - .166666667 .833333334 < zvui2 ~ (k) _< .944444444 regardless of i. Note here that we are not saying {Eulk)}k>l or {E~k)}k>, converges. They may fluctuate, staying between the given bounds. We show L ~ and H ~ of (3.3) are column tight bounds for the matrices in Me%
T h e o r e m 3.6. Let M be an interval [P, Q] which is product scrambling. (i) Given any column of Loo there is a matrix B E M c~ with the same column. (ii) Given any column of Hoo there is a matrix B E M ~ with the same column. Proof. Without loss of generality, we prove (i) only for the first column of L ~ . For this, using that [P, Q] is tight, there is a matrix A E M which has the same first column, say Pl, as P. Let A 1 , A 2 , . . . be the sequence of matrices in M, determined by the Hi-Lo method, such that lim A k . . . A l p l has the k---+ o o same first column as Loo. Then, using backward products, as in Theorem 1.10 lim A k . . . A l a ~ exists for each column ai of A. Thus, lim A k . . . A 1 A =- B, a k--+oo k--+oo rank one matrix in M ~ . And, B has the same first column of L ~ . []
3.3.
EIGENVECTOR
DESCRIPTION
67
OF A LIMIT SET
E x a m p l e 3.5. Continuing Example 2.11 and Example 2.14 for comparison purposes, recall P=
[.oo.25]25 .25 .25
.50 .25
.25 .00
and
Q=
[.0o.75.75] .25 .75
.50 .75
.25 . .00
To compute a matrix B with the same first column as Lo~ we start with a matrix in M having the same first column as P. For this, set A--
.00 .25 .25
.75 .50 .75
.25] .25 . .00
Proceeding as described in the theorem, we get the data shown in Table 3.2. T a b l e 3.2. S o m e a p p r o x i m a t i o n s for t h e m a t r i x B o f T h e o r e m 3.6 After k iterations
Approximation of B after those iterations
k=10
.1446342 .1436949 .1414270
.6418161 .6423664 .6436949
.21354977 .2139387 I .2148781J
k=20
.1428685 .1428625 .1428480
.6428505 .6428540 .6428625
.2142810] .2142835 / .2142895J
k=30
.1428572 .1428572 .1428571
.6428571 .6428571 .6428571
.2142857] .2142857] .2142857J
k=40
".1428572 .1428572 91428572
.6428571 .6428571 .6428571
.2142867] .2142857 I .2142857]
3.3
E i g e n v e c t o r d e s c r i p t i o n of a limit set
In a Markov chain, with regular transition matrix A, noting Theorem 1.6, lim A k = ye where y is the stochastic eigenvector for A belonging to the eigenvector 1. Thus, the limit matrix is described in terms of a stochastic eigenvector. In this section, we also describe the limit set of a Markov set-chain M in terms of stochastic eigenvectors. Before providing this description, we need some preliminary work.
CHAPTER 3. CONVERGENCE OF M A R K O V SET-CHAINS
68
D e f i n i t i o n 3.6. A sequence of matrices taken sequentially from M, M 2 , . . . is called a point sequence 9 Let P denote the limits of all convergent point sequences 9 A description of Moo, in terms of convergent point sequences follows9 L e m m a 3.3. Let M be product scrambling. Then P = M ~176
Proof. Let A E P. Then A is the limit of a point sequence say All,A21A22, A31Aa2A33,.... Let e be a positive constant. Then there is a positive integer N1 such t h a t if k > N1,
IIAk~Ak2... Akk --All < -~.
(3.4)
Since lim M k = M ~ there is a positive integer N2 such that if k > N2 then k--+oo
d(M k, Moo) < ~. Thus, for all k > N2, there is a Ak E M ~ such t h a t JJAklAk~ ...Akk---AkJl < 2" Let N = m a x { N 1 , N 2 ) and k > N. Then by (3.4) and (3.5), J I A - AkJl < e. Thus, A is a limit point of Moo and hence, A E M ~ . Hence, P C_ M ~176 Now let A E Moo. For each k there is a A k l A k 2 . . . Akk E M k such t h a t JlAklAk2... Akk -- All ~_ d(M k, Moo). Since lim (M k, M ~ ) = 0, A is the limit k-+oo
of the point sequence All,A21A22,... 9 Thus, A E P and hence M ~ C P. Putting together, P = Moo.
[]
The stochastic eigenvector description of Moo uses the following9 D e f i n i t i o n 3.7. Let M be product scrambling. For each A E M , let YA denote the stochastic eigenvector, belonging to the eigenvalue 1, of A. Let YA = eyA and define
EI = {YA: A E M} E 2 = {YA1A2: A1,A2 e M )
Ek = {YA1...A~ : A1,... ,Ak E M}
oo
Further define Coo =
[.J Ek. Thus, Coo is the set of rank one matrices YA k----1
where A E M k for some k. Finally, define E = E o o , the closure of E ~ . Theorem
3.7. Let M be product scrambling. Then E --- M ~.
3.4. P R O P E R T I E S OF T H E L I M I T S E T
69
Proof. T h r o u g h o u t the proof we let r denote the scrambling integer for M. We first show that E C M ~ . For this, let Y ~ E ~ . Then there is a positive integer m such that Y C Era. Write Y = ey. Then there is a matrix A1 ... Am E M m having y as an eigenvector. Thus, (A1 ... Am) r is scrambling and by Theorem 1.6 k__, . . l i m(A1 . Am) rk = Y. Let s be a positive integer less than rm. Choose any A 1 , . . . , Arm-1 E M . T h e n - A 1 . . . - A s ( A 1 . . . A m ) ~k E M krm+s. Since l i m [ - A 1 . . . A s ( A 1 . . . A m ) rk] = k-~c~
Y for all s < m r , we have a point sequence A 1 , A 1 A 2 , . . . , A 1 . . . A ~ m - 1 , (A1...Am)~,-AI(A1...Am)r,... ,A1...A~m-I(A1...Am) r, (A1...Am)2r,... , with Y as its limit point. Thus, by L e m m a 3.3, Y E M ~ and so E ~ c_ M ~ . Since M ~ is compact, E C M ~ as well. We now show t h a t M ~ C E. For this, let e be a positive constant. Let A E M ~ . Then since lim M k = M ~ there is a positive integer N1 such t h a t k--~oo
if k > N1, d ( M k, M ~ ) < e/2. Since T ( M r) < 1, there is a positive integer N2 such t h a t if k >_ N2, T ( M k) < e/4. Now let N = max{N1, N2, r}. Then there is a matrix A1 ... AN E M N such that IIA1... AN - All < e/2.
(3.6)
Since M is product scrambling, and N > r, A 1 . . . AN is scrambling and thus by T h e o r e m 1.6, lim (A1 . . . A N ) k = ey k--+cx~
where y is the stochastic eigenvector for A 1 . . . A N . rem 1.8,
Furthermore, by Theo-
IIA1... AN -- eyll < 2 T ( M N) < e/2.
(3.7)
Putting (3.6) and (3.7) together, I l e y - All < e. Thus, A is a limit point of E ~ and so A E E. From this it follows t h a t M ~ C_ E. Putting together, E = M ~ . []
3.4
P r o p e r t i e s of the limit set
In this section we give some qualitative information about limit sets. We use b o t h the diameter A of a set as well as the Hausdorff metric d. We first consider intervals. Theorem Then
3.8. Let M be the interval'[P,Q] and M ' be the interval [P',Q']. d(M, M ' ) <_ miax E k
max{ Iqik - P'ik [, Iq~k - P,k 1}.
CHAPTER
70
3.
CONVERGENCE
Proof. Let A E M and A' E M ' . respectively,
OF MARKOV
SET-CHAINS
T h e n if ai,a~ are the i-th rows of A , A '
IIA - A'II = max Ilai - dil I
laik - a~k I
= max ~ k
< - m iax~-~ max{lqik - P'ikl, Iqik ' -Pikl}. k
[]
From this, the result follows. Theorem
3.9. Let M be the interval [P, Q]. T h e n
A ( M ) _<
IIQ- PII.
Proof. Let A, B E [P, Q]. T h e n if ai, bi, pi, qi the i-th rows of A, B, P, Q respectively, IIA - BII = m a x Ilai - bi II _< max IIqi - pill i
<_ IIO - PII. From this, the result follows.
[]
T h e remaining theorems concern the limit set of a Markov set-chain with an initial distribution set. L e m m a 3.4. Let x, y be stochastic vectors and A 1 , . 9 9 , A k ; B 1 , . . . tic matrices. I f T ( A i ) <_ T and T ( B i ) < T f o r all i, then
IIxA1...Ak
-yB1...Bkll
<_ T k l [ z --Yll + ( T k - 1 + " "
, B k be stochas-
+ 1)g"
where g = m a x [IAi - Bill. i
Proof. T h e proof is by induction on k. For k = 1, we have IIxA1 - y B l l l = IIzA1 - yA1 + yA1 - y B l l l <_ IIxA1 - yAlll + IlYll IIA1 - Bill < Wllx - yll + g. Now suppose the l e m m a holds for all k < m. For k = m we have, using the induction hypothesis,
IIxA1... Am - yB1...
Broil
_< T l l x A i . . . A m - 1 - y U l . . . Bin-ill + g, < T(Tm-lll x<
This is the result of the lemma.
yll+
(T m-2 +"+
1)g) + g
Tmllx - YI[ + ( T m-1 + " " + 1)g. []
3.4. PROPERTIES OF THE LIMIT SET
71
T h e o r e m 3.10. Let M, M be transition sets with T ( M ) < T and T ( M ) <_T. Let X, Y be compact subsets of An. Then d ( X M k , Y - M k) <_T k d ( X , Y ) + (T k-1 + . . . + 1)d(M,M). Thus, if T < 1, d(Soo,Soo) <__l l~Td(M,-M). Proof. Let A 1 . . . A k E M k and x E X. Choose y E Y such that I[x-y[I <-d ( X , Y ) . Choose B1,... ,Bk E M such that I[Ai -Bi[[ _< d(M,M) for all i. Then Lemma 3.4 assures that [[xA1...Ak - y B 1 . . . B k [ [ <_Tk[Ix-Yl[ + (Tk-1 + " " + 1)s ~ Tkd(X, Y) + (T k-1 + . . . + 1)d(M, M). Hence 5(XMk, y-~k) <_7_kd(X ' y) + (Tk_ 1 + ' " + 1)d(M, M). Similarly, 5 ( Y - M k , X M k) <_T k d ( X , Y ) + (T k-1 + . . . + 1)d(M,M). Thus, the result follows.
[]
This theorem shows that ~ can give an upper bound on the magnification of error, d(M, M), in computing say S~. Thus, ~ can indicate the condition of the Markov set-chain. This theorem also implies the continuity result that if M tends to M then Soo tends to S~. The last theorem of this section concerns the diameter of S~. T h e o r e m 3.11. Let So C_An. Then A(SoM k) < T ( M ) k A ( X ) + ( T k - l ( M ) + 9- - + 1)A(M). Thus, i f T ( M ) < 1, A(Soo) _<
1 1 - T(M)
A(M).
Proof. Let xA1 ... Ak and yB1 99 Bk be in SoM k. Then by Lemma 3.4, I]xA1...Ak - yB1...BkH <_T(M)kll z - YH + (T(M) k-1 + " " + 1)C. Thus A(Sk) < T(M)kA(So) + (T(M) k-1 + . . . + 1)A(M). Taking limits, the result follows.
[]
E x a m p l e 3.6. We let M be an interval where P=
[.75 .12
.23] .86
and
Q = [.77 .14
.25] .88 "
72
C H A P T E R 3. C O N V E R G E N C E OF M A R K O V S E T - C H A I N S
After 40 iterations there was no change in the first 3 digits of the component bounds on M k. Thus, to those digits, [.324 L ~ = [.324
.622] .622J
[.378 H ~ = [.378
and
.676] .6761"
Now, A(M) <
[IO- PII =
.04
and
T ( M ) < ~[(.77 - . 1 2 ) + (.88 -.23)]
= ~[.65 + .65] = .65. Using Theorem 3.11, 1
A ( S ~ ) _< 1 - T ( M ) A M < 2.86 x .04 < .114 while the actual diameter is
A(S~o) = 11[.324, .676]
-
[.378, .622] II
= 1.324 -.3781 + 1.676 - . 6 2 2 I = .054 + .054 = .108. The bound on A(M ~176is as that of A ( S ~ ) and the actual value of A ( M ~ ) is that of A(S~o).
3.5
Cyclic
Markov
set-chains
In this section we extend the notion of Markov set-chains to cyclic Markov set-chains and determine convergence criteria for them. D e f i n i t i o n 3.8. Let M1,... , Mw be transition sets. For i -- 1, 2 , . . . define M~ = Mj
if i = j(modw).
Then M1, M 1 M 2 . . . is called a cyclic Markov set-chain with cycle length w. Further, for any compact subset So of An, So, SoM1, SoM1M2, . . .
is called a cyclic Markov set-chain with initial distribution set So.
3.5.
CYCLIC MARKOV SET-CHAINS
73
The theory for cyclic Markov set-chains is as that of Markov set-chains and so we simply state the major result of this theory. T h e o r e m 3.12. Given a cyclic Markov set-chain, with interval transition sets, of cycle length w, define, for any prechosen i,
M = Mi+l ... Mi+~. I f M is product scrambling then lim M k = M ~ . k --+ o o
C o r o l l a r y 3.4. Using the hypothesis of the theorem, lim M1 999Mi+kw = M ~ k ---~o o
for any preehosen i. Proof.
By the theorem, lim M k is a set of rank one matrices. Since products k--+oo
average, lim M 1 . . . Mi+kw = M , . . . Mi lim M k = M ~ . k---+~
[]
k--+oo
Computationally, for cyclic Markov set-chains, as with Markov set-chains, we compute component bounds on the various products. This requires that the transition sets be intervals. For bounds on a product
AIA2 . . . A t , noting that
Pt <- At <_ Qt we use the rows in [ P t - l , Q t - 1 ] and the Hi-Lo method to find L2 a n d / / 2 such that L2 <_ A t - l At <_ tt2. Then, using the rows in [Pt-2, Qt-2] and the Hi-Lo method we can find L3 and //3 such that L3 <_ A t - 2 A t - l A t <_ 1t3. We can continue to find bounds on A ~ . . . A t - 1At for any s. Since we are considering a cyclic product, it is not necessary to stop at s = 1. The product can be continued adding additional cycles
A1 ... AwA1 ... At for longer run calculations. E x a m p l e 3.7. As a cyclic problem we consider the seasonal habits of coffee drinkers. For simplicity we classify coffee drinkers into two states: d = drinkers (1-3 cups/day) and hd = heavy drinkers (4+ cups/day). The classification of a coffee drinker can change at different seasons of the year. For simplicity we group the seasons Summer-Fall and Winter-Spring. Allowing for some fluctuation, we
74
CHAPTER 3. CONVERGENCE OF M A R K O V SET-CHAINS
let M1 be the transition set from Summer-Fall to Winter-Spring and M2 the transition set from Winter-Spring to Summer-Fall. The corresponding intervals are given below hd
~1= [~ 0:] [001 1111 ~= ([0~ ~0,][~1 o11) Calculations are given in Table 3.3 and Table 3.4 Table 3.3. B o u n d s on p r o d u c t s e n d i n g in M2 Product of k matrices k=2
k=4
k=68
Lower bound Lk
Upper bound on Hk
[ .09900 .890801 [.819.149] .163 .801
E.11020 .911001 E.199 ~55 .837 1811
[.473.421] .473 .421
[.579.527] .579 .527
Table 3.4. B o u n d s on p r o d u c t s e n d i n g in M1 Product of k matrices
k=l k=3
k=5
k=oo
Lower bound Lk
[89o o911 [.801.163] .080.900
Upper bound Hk
[Olo 1111 [.837.199] .100.920
[7202221 [77~271 l .145 .819 .181 .855 [.421.4731 [.527.5791 .421 .473 .527 .579
Geometrically, we observe that, to three digits, the cyclic products, with initial distribution set So, ending in M2 (in Summer-Fall), say SoM1M2... M1M2 tends to C2 = convex{(.473, .527), (.579, .421)}
3.6. CESARO SET-SUMS
75
while those ending in M1 (in Winter-Spring), say S o M I M 2 . . . MIM2M1 tends to C1 = convex{(.421, .579), (.527, .473)}. The placement of C1 and C2 in A2 is shown in Fig. 3.1.
Figure 3.1: Cyclic behavior of coffee drinkers. Thus, coffee drinkers d increase in the Summer-Fall, bounded by .473 < d < .579 and decrease in the Winter-Spring, bounded by .421 < d < .527.
3.6
Cesaro set-sums
This section introduces Cesaro set-sums and shows when such sums converge. D e f i n i t i o n 3.9. Given a cyclic Markov set-chain with interval transition sets and having cycle length w, define I+MI+'"+M1...Mm-I={I+AI+"
+A1...Am-I:
A~EMiforalli}.
Then (I + M1 + ' " + M1 .. M m - 1 ) / m is the Cesaro set-sum of cyclic length w. For a compact convex So, define Cm : So(I + M1 + " " ~- MI ... M m - 1 ) / m as a Cesaro set-sum with initial distribution set So. Note that the Cesaro set-sum contains all Cesaro sums of nonhomogeneous Markov chains having transition matrices Ak E Mk. For the shape of Cesaro set-sums we have the following.
76
CHAPTER 3. CONVERGENCE OF M A R K O V SET-CHAINS
T h e o r e m 3.13.
Cm iS a compact convex set.
Proof. Let x ( I + A l + . . " + A 1 . . . Am-1)/m, y ( I + B l + " "+B1... B m - 1 ) / m E C m and a,/3 nonnegative constants such that a + ~3 = 1. Construct K 1 , . . . , Kin-1 as in Lemma 2.5 (ax +/~y)K1 = axA1 +/3yB1 (axA1 + ~3yB1)K2 = axA1A2 +/3yBIB2
(axA1 ... Am-2 +/3yB1 ... Bm-2)Km-1 = axA1 ... A,~-I +/3yB1 ... Bin-1 where Ki E Mi. Then
(ax + /3Y) ( I T KI + ' " +
KI""Km-1)
(ax + /3y) + (axA1 + /3yB1) + ' " + ( a x A 1 . . . A m _ l + /3yB1...Bm-1) m
OL( x''~-xA1 -[-'''-['xAI"''Am-1)m -[-]3( y-~yB1 -~''''[-yBI'''Brn-1)m Thus, Cm is convex. That Cm is compact follows since sums and products of compact sets are compact. [] More particularly, we have the following.
Cm is a convex polytope with vertices of the form gi(I + E1 + . . . + E l . . . E m - 1 ) / m over all vertices Ei of Ao and all vertices Ej of Mj, (j mod w).
C o r o l l a r y 3.5. If So is a convex polytope then
Proof. Theorem 3.13 shows that Cm is a convex set. Thus, we need only show that the vertices are of the form given in the theorem. Let x ( I + A1 -k ...-b A 1 . . . A m - 1 ) / m E C m write x = ~ a k E k where each k
For all i, write Ai = ~ a i k E i k where each Eik is a k vertex of Mi (i mod w). Substituting these expressions into x ( I + A1 + "" + A 1 . . . A , ~ - l ) / m and expanding yields that x(I + A1 + . - . + AI ... A m - 1 ) / m is a convex combination of vertices of the form $i(I + E1 + "" + E1 ... E m - 1 ) / m as desired. [] gk is a vertex of So.
This result can be extended to Cesaro set-sums as follows. D e f i n i t i o n 3.10. For a Cesaro set-sum, define [(I+Ml+---+M1...Mm_l)/m]i={x:
x is the i-th row of some
A e (I + M1 + . . . --b M I . . . M m - 1 ) / m } .
3.6. C E S A R O S E T - S U M S
77
C o r o l l a r y 3.6. For a Cesaro set-sum, and any i, [(I + M1 + ... + M 1 . . . M m - 1 ) / m ] i is a convex polytope.
Proof. Let S0 : {e~} and apply Corollary 3.5.
[]
We now show criteria under which Cesaro set-sums converges. As with Markov set-chains this will require a sequence of preliminary results. The first of these determines a special limit set. L e m m a 3.5. For any Cesaro set-sum with cycle length w and initial distribu-
tion set A,~, Cw~+l C Cw~. Proof. For simplicity of notation, let A = AN and ~
= I +'"+
M1...Mm-1.
The proof is by induction on k. If k = 1 we have to show C~2 C_ C~. For this, we arrange the w 2 terms of C,~ into groups of w terms. We have
Cw2 ~- ~i (~/w) -~-Xiil...iw
(~/w)
Since AM1 ... M(k+l),~ C_ A M 1 . . . Mk~ for all k,
l-cw.
c W
W
W
By convexity of C~, C~: C_ Cw which yields the initial step of the induction. Now suppose the result holds for all k < m. For k = m + l before,
< --A
W
c
wm
W
+ ... + 1 A M 1 . . . M w m ( w _ l )
W
we have as
wm
W
c_ C ~ . From this the result follows.
[]
C H A P T E R 3. C O N V E R G E N C E OF M A R K O V SET-CHAINS
78
This l e m m a gives us a special limit set. D e f i n i t i o n 3.11. Given a Cesaro set-sum with cycle length w and initial distribution set An, define (x)
Coo = N C ~ k=l
as the Cesaro limit set of the Cesaro set-sum with this initial distribution set. 3.14. For any Cesaro set-sum with cycle length w and initial distribution set An, lim Cw k = Coo.
Theorem
k ---~oo
To obtain convergence rates we need two remarks. R e m a r k 1. Let A1, A 2 , . . . be n • n stochastic matrices with T ( A i ) <_ T < 1 for all i. Then, using Theorem 1.2,
T(I+AI+...+A1...Am_I) m
< 1 1 -ml-T"
Proof. Note "-]- Q [ -~- A I -~- " " " -{- A I " " "
~- 7~ ( I ) "~ "]- ( A 1 ) -~- " " -{- "-]-( A I " " A m
< I+T+...+T
~-~
m
< - -1 -ml-T'
1
[] Remark Y
2. Using the hypothesis of Remark 1, for any stochastic vectors x and
x (I+A1 <2 -
Proof. Let
+"" A +im ...Am-1
1 1 ml-T" B
=
I+AI+...+A1...Am_I. Then m
IlxB - yB[[ = II(~ - y)BII IIx - y [ I T ( B ) 1 1 <2---ml-T" [] A convergence rate for the special limit result follows.
3.6. C E S A R O S E T - S U M S
79
C o r o l l a r y 3.7. Under the hypothesis of the theorem and that T ( M i ) <_ T < 1 2 1 ]or each i, d( Cw~ , Coo) <_ ~-~ 1-7-"
Proof. Since C ~ + , C C~k, for all t >_ 0 it follows t h a t 5 ( C ~ + , , C ~ ) 1r For this, let now show t h a t 5 ( C ~ , C~k+,) < - 2v 1_--:-
= 0. We
x ( I + . . . + A 1 . . . A ~ k _ l ) / w k C Cw~. Using any A ~ E M ~ , define A=I+--.+A1...A~k_I
and u s i n g w t copies of A,
B = (I + . . . + A1 . . . A ~ _ I )
+ AI...Aw~(I+""
+ (A1...Aw,)~'-I(I +-"
+ A1...Aw~_I) +""
+ A1...A~,-,).
Note t h a t x B / w k+t E C~k+~ for any x E A~. Now, define A = A + ... + A, the sum of w t copies of A. Then, applying R e m a r k 2,
I I x A / w k - :~:B/w T M II = IlxA/wk+~
- xB/wk+~ll
< 2wtT(A) --
< -
wk+t
2(1 + . . . + 7 ~ - 1 ) W k
-
1 < 2 -wkl_T" Thus,/i(C~,~ Cw~+,) < '
-- ~
2
1
1---:-~"
Finally, since lim C~,~+~ = Coo, it follows t h a t t-~oo
2
1
d(C~,, Coo) < wk 1 --7-" [] We extend the previous work to Cesaro set-sums in general. We use the notation that if m, w are positive integers then we can write
m = uo w~
+ Ul wl
~- 9 9 9 -~- U k w k
where 0 < ui < w for all i. L e m m a 3.6. If a Cesaro set-sum o/cycle length w is such that T ( M i ) < T < 1 for all i, then
d(u~176 m
m
< - 2 w ( km+ l )
1-T
where Cm has initial distribution set So and Cwo , . . 9 , Cwk have initial distribution sets An.
80
C H A P T E R 3.
CONVERGENCE
P r o @ We first show that Cm C ~ ~ 1 7 6 --
x ( I + A1 + ' "
m
+
t a w ~
" "
"
OF MARKOV
SET-CHAINS
/-* + UkWk m t~wk' For this, let
+ A1 . . . A m - 1 ) / m
9 Cm.
Now, group the terms so that there are uow ~ terms in the first group followed by UlW 1 terms in the second group, etc. Thus, we have x ( I + A1 + . . . + A 1 . . . Auo~,O_l)/m + ' "
+ x ( A 1 . . . A8 + . . . + A 1 . . . A m - 1 ) / r n
where uow ~ + 999 + U k _ l w k - 1 = 8. Now arrange the first group into Uo groups of w ~ terms, the second group into ul groups of w 1 terms, etc. Thus, we have (x + xA1 + ... + x A i . . . A u o w O _ l ) / m + ... + [ x ( A t . . . A , + . . . + At...A,+,,,~_t) + . . . + x ( A l . . . A t
+... + AI...A,,,_I)llm
where t = uo w~ + . . . + (uk -- 1)w k. Rewrite this as [(x)I + ( x A , ) I + . . . + ( x A 1 . . . A~,o,oO_l)I]/m + . . - + [ ( x A 1 . . . A , ) ( I + A~+, + . . " + A~+I . . . A ~ + ~ - I ) +... + (xA1...At)(I
+ At+l + " " + A t + l . . . A m - 1 ) ] / m .
Thus, since Cwo,... , C ~ are all convex, x( I + A1 + . . . +
U0 w0 _
A1 . . . A m - 1 ) / m 9 - - U w o m
~1 w l _.
+ --C~1 m
+ ...+
?.tk w k
m
C~.
Hence, we have that Cm c_ So, a ( C m , :Cwo + . . . + We now consider
noW ~
m
Uk W k
,(u:o
C~o + . . . +
U k wk
m
C~.
) =o
C~o + ' "
+
m
C~,Cm
)
9
For this let y o , . . . , Yk 9 So and U0 w0
y =
m
yoI +
UlW 1
Yl (I + ".. +
m
A~1) . . . . . A(1) w l _ 9 2~ I w
UkWkyk(I + ... + A~k) . . . A ~ 2 _ l ) l w k 9 m
UO wO
1 + " ' " "tUk w k
C~o + ... +
m
cw~.
m
Construct a sequence from M1, M 2 , . . . by repeating A~k),.
9
9
,
_(k) Uk 2tw~
times,
then repeating A~ k - l ) , . . . , A(wks times and finally A~~ , A(~ This gives a sequence of m - 1 matrices. Using this sequence, define for any z 9 So, x
=
z(I
zl(k) "*2 zl(k) + A~k! + "'1
+''"
zl(k)a(k) ~'2
+ "*1
A~o)
. . . . . .
A U(o)o - - 1~1 ] l rn
9 Crn.
81
3.6. C E S A R O S E T - S U M S
Then, arrange corresponding terms, by Remark 2, ltx -
yll < 2. u~176+... + 2 ukwk (1 +.-- + T ~ - 1 ) -
m
m
9
wk
1
<_2
+...+
< 2(k + 1)w -
m
1 -T
1 l-T"
Thus, ukWkcw~,C,~) < 2 ( k + l ) w m m
(U~176
l-T"
[]
Prom this the result follows.
T h e o r e m 3.15. If a Cesaro set-sum has cycle length w, initial distribution set So, and T ( M i ) < 1 for all i, then
d(c
,coo) <
+ 1)
-
Thus,
m
1 l - T "
lim Cm = Coo with convergence rate 0 ( k~m ) .
m --+oo
Proof. For any m, write m = UoW~ + u l w 1 + -.. + ukw k. Set Rk :
u ~ 1 7 6Cwo nt- u l w l Cwl -4- . . . -t- u k w k Cw~
m
m
m
where Cwo, ... , C ~ have initial distribution sets An. Applying Lemma 3.6 and Corollary 3.7 to C~0,... , C ~ in Rk, d(Cm, Coo) <_ d(Cm, Rk) + d(Rk, Coo) •k wk 2 ) ]
< [ 2 w (k + 1) + ( u ~ ~ w2~ + " ' +
__ m wk
1 1-T
_< [2w(~+l)__ +2w(k+l)]m 1 - T I < 4w(k + 1) -
m
1 l-T"
Since w k <_ m < w k+l, k l n w < lnm.
Thus, in m
k+l<~w+l. By substitution, d(Cm,C~) < --
4w{ ln~ + 1) ~lnw m
1 1--7""
[]
C H A P T E R 3. C O N V E R G E N C E OF M A R K O V S E T - C H A I N S
82
We now convert this result to a matrix result. D e f i n i t i o n 3.12. Define the limit set of a Cesaro set-sum as E ~176 = {B: B is a rank one stochastic matrix with first row in Coo}. It follows from Theorem 3.13 that ~ o o is a compact convex set. 3.16. If a Cesaro sum has cycle length w and is such that T(Mi) ~ T < 1 for all i, then Theorem
(
d (I + . . . + M 1 . . . M m - 1 ) / m ,
E~176<
{lnrn 1)
4w~i-Y-dw §
Thus, lira ( I + . . . + M 1 . . . M m - 1 / m )
1
2
1
1---r + ml-T"
m
-
-
= ~.
k --.~ o o
Proof. This is a consequence of the Matrix Conversion Theorem.
3.7
[]
Cesaro set-sum c o m p u t a t i o n s
In this section we show how to find tight bounds on the matrices in
(I + M1 + . . . + M 1 . . .
Mm-1)/m
when each Mi is an interval. To compute bounds on the j - t h column, just note that
11 ~ [Am-l]j ~__hi where 11 and hi are the j - t h columns of Pro-1 and Qm-1 respectively, and the subscript j in [Am-1]j denotes the j - t h column of Am-1. Thus,
ej § ll <_ [I + Am-1]j <_ ej § hi and so
1
1
~(ej § /1) __~5[ 1 §
1
Am-1]j <_ ~(ej + hi).
Now using [P,~-2, Q,~-2], we apply the Hi-Lo method to compute bounds
12~Am-2(~[I+Am-1])
or
J 2l 1 A 2h 52<~( m-2 + Am-2Am-1)j <_ -~ 2. Thus,
-1 ej
2l 2 <_ l ( I + A m _ 2 + A m _ 2 A m _ l ) j
1 2 h 2. < -~ej+-~
C o n t i n u i n g we have 1
-eJ+m
m - llm_l
m
1
-<-(I+AI+"'+AI"Am-1)J<-m
1
- m e3+
m - 1
m
hm-1.
If more terms are desirable, the technique can be continued through another cycle.
3.7. CESARO SET-SUM COMPUTATIONS
83
E x a m p l e 3.8. We use the transition sets from Example 3.7 involving coffee drinkers. Thus, M I = ([.~9
.019],[.901 All]) ,
M e = ([.19
.809],[.~1
.31])"
The results of the computations are given in Table 3.5 and Table 3.6. Table 3.5. B o u n d s ending in M1 are given below Sum of k terms k = 1000
k = 2000
k = 3000
Lower bound Lk
Upper bound Hk
[.457.443] [ 55s 547] .444
.453
.548 .557
[.451.445] .445 .450
[.555.550] .550 .556
[.44~176
[.554.551]
.446 .449
.551 .554
Table 3.6. B o u n d s ending in M2 are below Sum of k terms k = 1001
k = 2001
k = 3001
Lower bound Lk
Upper bound Hk
[.457.443] [.558.547] [.451.445] [.555.550] [.44~176 [ ~ ~1] .444
.453
.548 .557
.446
.450
.550 .555
.446 .450
.551 .554
Putting this in terms of random variables, if the nonhomogeneous Markov chain is initially in sl, where sl = d and s2 = hd, define
u~--{lo o~ft~~176 Define lt--1 k----0
84
CHAPTER 3. CONVERGENCE OF MARKOV SET-CHAINS
the average number of times the chain is in sj in t steps. Then t--1
E(v}])) : 71 E E(uI~ )) k----0 ----
--
a
t where al ~ = 5ij, the Kronecker 5. For t _> 2000 the bounds (approximate), independent of i, are
44 <
55
.44 <_ E(v}~ )) < .55
(rounding to 2 digits).
So, the expected average number of coffee drinkers is between .44 and .55 which is also the expected average number of heavy coffee drinkers.
3.8
L u m p i n g in M a r k o v set-chains
To describe the lumping of a stochastic matrix requires some preliminary notation. For this, let r l , . . . , r r be a sequence of positive integers such t h a t rl + -.. + rr = n. Let f be a n x 1 vector of l ' s and partition f =
such f t h a t fi is ri x 1. Let L be an n x n nonnegative matrix and partition L so t h a t its ij-th submatrix Lij is ri x rj. If there are scalars aij such t h a t Lijfj = aijfi for all i, j then L is said to be lumpable. The r x r matrix L = [aij] is called the lumped matmx of L. Extending this a bit further, if z = (zl,... ,zr) is a 1 x n nonnegative vector partitioned compatibly to L then 2 = (zlfl,... , Zrfr) is the lumped vector for z. In classical Markov chains, if a stochastic lumpable matrix A has stochastic eigenvector y then the stochastic matrix A has stochastic eigenvector ~. Thus, the behavior of a Markov chain having a rather large number of states can be more coarsely analyzed through a Markov chain with fewer states. For this section we will assume that M is an interval [P, Q] where b o t h P and Q are lumpable. The sequence M, M 2 , . . . will be called a lumpable Markov set-chain. The Markov set-chain M determined from P and Q will be called the
lumped Markov set-chain. Before proceeding we need to remark that if P and Q are tight then P and Q need not be tight. E x a m p l e 3.9. Let P = [1] and Q = [3] be 4 x 4 matrices. Applying L e m m a 2.1 we see t h a t P and Q are tight. Now, if P and Q are partitioned into four 2 x 2 submatrices we have P = [92-] and Q = [6]. Again applying L e m m a 2.1 we see that P and Q are not tight.
3.8. L U M P I N G I N M A R K O V S E T - C H A I N S
85
T h e m a j o r result in lumpable Markov set-chains follows. 3 . 1 7 . Let M be an interval [/9, Q] for a lumpable Markov set-chain and x a stochastic vector. Then 2 M = x M .
Theorem
Proof. We suppose t h a t the partitioning of P and Q is as t h a t of L in the i n t r o d u c t o r y remarks of this section. Thus, x = ( X l , . . . , xr) where each xi is l• We first show t h a t 2 M C__ x M . For this, let z E 2 M . T h e n there is an A C M so t h a t z = 2A. We now construct an A E M such t h a t 2 A = x A . For this, note t h a t P < A <_ Q. Thus, for all i, j there is a scalar a i j such t h a t O~ijPij q- (1 -- aij)C]ij = aij, a convex sum. Define A so t h a t Aij = o~ijPij q- ( 1 - a i j ) O i j for all i , j . Checking properties, it is clear by its definition t h a t P _< A < Q. To show A E M , note that, in partitioned form, Af =
A~kfk k:l
]I =
E(aikPik
+ (1 -- ~ik)Qik)fk
kk=l
Thus, A is stochastic and hence _4 E M . To complete this p a r t of the proof, define
F:
rsl
s?. o ........ .. .. oj01, , = ,,.,,l o
LO
o...
/.j
[o
...
o
/.
.........o .....
Note t h a t ~ = x F , --A = F r A Y and t h a t by the definition of A, F F t A F A p p l y i n g these observations, we have t h a t
2A = (xF)(FtAF) = x(FFtAF)
= AF.
= xAF = xA.
Thus, it follows t h a t 2 M C_ x M . We now need to show t h a t x M C 2 M . For this, let z E x M . T h e n there is an A E M such t h a t z = x A . To complete the proof we need to construct an A E M such t h a t 2 A = x A . Define x + = ( x + , . . . , x+), partitioned as is x, such t h a t
~xi/(xifi)
x'+ = [(l/~,)f~
if x i f i > O, and
otherwise.
Define A = [x+A~jfj]. We now need to show t h a t A E M . To show t h a t P < A < Q, note t h a t
?tij =- x + A i j f j < x + Q i j f j -= X+(lijfi =- Klij(x+ fi) = (tij.
86
C H A P T E R 3. C O N V E R G E N C E OF M A R K O V S E T - C H A I N S
Similarly, Pij _< gij. To show that A is stochastic, observe that
k----1
k----1
k=l
Hence, A E M. Finally, 9 -A=
~2kakj =
Xkfk)(X Aks
=
xkfkX
k----1
-=
Hence, z M C_ ~ M . From this it follows that ~M = x M .
[]
A consequence of this theorem follows. C o r o l l a r y 3.8. For k = 0, 1,... , Sk+l = S k M . And from this corollary, we have the desired result. C o r o l l a r y 3.9. If lim Sk = Soo exists, then so does lim Sk. And lim Sk = k -~ ~
k --~ o o
k --* o o
-Soo. Proof. Note that S k F = -Sk by (3.8). Thus, lim Sk = lim S k F = SooF = k---~c~
k---~oo
500.
[]
An example demonstrating lumping follows. E x a m p l e 3.10. Let M be an interval where p =
.5 :4 .4
.2 .2 .3
.2 .2 .1
Q =
.6 .6 .6
.3 .3 .2
.2 ] .3 . .4
Then, using the partitioning,
Looking at M and computing bounds on lim Sk = S ~ yields that if (Yl, 92) E k---~oo
Soo then .444444444 _< Yl -< .6
and
.4 _< 92 _< .555555556.
Thus, for any (yl,Y2,Y3) E Soo, .444444444_ Yl _< .6
and
.4 < Y2 + Y3 _< .555555556.
3.8. LUMPING IN M A R K O V SET-CHAINS
87
Computing bounds on Soo yields that if (yl,y2,y3) E Soo, .444444444 < yl <_ .6 .217444444 _< Y2 _< .282555556 .174444444 < Y3 _< .281111111. Summing bounds on Y2 + y3and comparing those to the bound on Y2 may seem to contradict the theorem. However, the individual bounds on yl, Y2, and Y3 do not imply that Y2 and Y3 belong to the same vector.
Related research notes The basic material in this chapter was taken from Hartfiel (1981a, 1991b, 1993a, 1993b, 1994b) and Seneta (1984b). As in the previous two chapters we provide a review of related work. And, as before we put these in list form. (a) P r o d u c t s a n d 0 - p a t t e r n s . Convergence of a Markov set-chain can be assured if "/'(M r) < 1 for some positive integer r. When this occurs depends on the 0-pattern (the ij-th positions containing O's) of the matrices in M. We review some of the research on this problem. A set S = ( A 1 , . . . , At}, where each Ai is a nonnegative matrix, is a scrambling set if there is an integer ~ such that any product of A's of length ~ or more is 1 n scrambling. Paz (1965) showed that if S is scrambling, then ~ < ~(3 - 2 n ~ l +1). Also see Wolfowitz (1963) and Paz (1971). Cohen and Sellers (1982) define S to be a primitive set if there is an integer ~ such that every product of the A's of length ~ is positive. They show that if S is primitive, then ~ < 2 n - 2. Of course, if n is large, checking all such products from S would be impractical. A more practical approach is to describe scrambling or primitive sets in terms of the individual A's. For some such sets, see Seneta (1981). In addition to those, Rhodius (1989), using work of Deutsch and Zenger (1971), described almost scrambling matrices. A matrix is almost scrambling if for each i, j either there is a k such that aik > O, ajk > 0 or in one of the rows the i and j entries are not 0. He shows that in any set S of such matrices, any product A~1 ... Ain_l must be scrambling. Antonisse and Tyms (1977) gave a bit more complicated description for a set that is positive. Also see Hajnal (1976) and Cohen (1979). For primitive sets, we can let S be any set of fully indecomposable matrices. Basic results about fully indecomposable matrices can be found in Marcus and Minc (1964), in Fenner and Loizou (1971), as well as in Schwarz (1973). Also see a historical article of Schneider (1977). Lewin (1971) essentially showed that any product of n - 1 matrices in S is positive. Lewin's work was generalized by Hartfiel (1975a) using a notion of k-th measure of full indecomposability. (b) P r o d u c t s a n d s l o w l y v a r y i n g m a t r i c e s . A problem which is somewhat related to Markov set-chains concerns products of matrices which vary slowly. Such products were considered by Ostrowski (1973) who found upper bounds when the products involve complex matrices and by Artzrouni (1983, 1986,
88
CHAPTER 3. CONVERGENCE OF M A R K O V SET-CHAINS
1991) for products involving nonnegative matrices. Trench (1995) considered a similar problem, studying the convergence of products (I + Ak) ... (I + A1). (c) S u m s of m a t r i c e s . Convergence of Cesaro sums for Markov chains can be found in Gantmacher (1964) as well as in Isaacson and Madsen (1976). Work on Cesaro sums for nonhomogeneous Markov chains can be found in Hartfiel (1975b) as well as in Bowerman, et al. (1977). Also see Chatterjee and Seneta (1977). (d) P e r t u r b a t i o n . Let A be an irreducible stochastic matrix and E a matrix such that A + E is irreducible and stochastic. Let w be the stochastic eigenveetor for A belonging to 1 and ~ that for A + E . Perturbation theory, for this problem, studies the closeness of w to ~. We review two such results. Funderlic and Meyer (1985, 1986) showed that max
Iw, -
<
4
where
5j = minaij and 5j is positive for some j. Seneta (1988a) improved the bound to
i
1
--
IIEll
Seneta (1993b) introduced the coefficient of ergodicity into this bound by proving that 1 LIw - ~ll <- 1 - T ( A ) IIE[I
which gave 1 as a condition number for this eigenvector problem. This condition number can be compared to that for Markov set-chains. (e) S p e c t r u m . Classically, the convergence of {Ak}k>_l is shown by considering the largest, in modulus, eigenvalue of A. Such a notion has also been developed for {A1 ... Ak}k>_l. Rota and Strang (1960) introduced a notion of joint spectral radius. Daubechies and Lagarias (1992) presented a special ease of this radius. They defined, for a finite set of matrices ~ , the joint spectral radius/5 ( ~ ) -limsup (jhk ( ~ , I1" II)) 3 where I1" II is any norm and k--+oo
/Sk(E, II'll)=liIsup
Ai
: AiC E
forl
.
k--~oo
This generalizes the result that for a square matrix A, p(A) = lim {IAkll ~ where
p(A) = max{I,Xl: ,~ is
an eigenvalue of A}. Thus, at least intuitively, ~ (Y'~) k
gives something like the largest, in modulus, eigenvalue of H A i . Daubechies 4=1
and Lagarias state a conjecture to this effect. They use the "geometric mean eigenvalue" to discuss convergence of products of matrices in }-~.
3.8. LUMPING IN M A R K O V SET-CHAINS
89
Artzrouni (1986) asks if nonnegative matrices A1, A2,.. 9 are varying slowing is p(A1 ... Ak) ~ p(A1).., p(Ak). Johnson and Bru (1990) gave some answer to this question by showing that
rain \ x k - 2 . ] min
"
~
min
p(AIA2 ...Ak) <- p(A1)p(A2).., p(Ak) ~
max \ X k - 2 ] m a x
where Aixl = p(Ai)xi for i = 1,... ,k and ~ = (Ja-~l,w2,... ~ , ~), of min and max concerning the entries of the vector.
""
~k
max
subscripts
Chapter 4
B e h a v i o r in M a r k o v Set-Chains In this chapter we show how Markov set-chains are applied in the classical work of chain behavior 9 For this, we let M be an interval [P, Q] for a Markov set-chain. Let {Xk )k_>O be a nonhomogeneous Markov chain with transition matrices in M. In studying behavior of the nonhomogeneous Markov chain we are concerned with its state to state movement as the steps increase. We develop work of this kind in this chapter.
4.1
C l a s s i f i c a t i o n a n d c o n v e r g e n c e o f M a r k o v setchains
In this section we describe three types of Markov set-chains, in terms of the states s l , . . . , sn, and show that each of these types of Markov set-chains converges. We begin by classifying the states S l , . . . , sn of a Markov set-chain. Since M is an interval [P, Q], we do this using the structure of Q. By applying simultaneous row and column permutations (see Section 1.3), Q can be put into the form
where
Q1 o
0 Q2
9149 ...
0 0
o o
:
9149 ...
".
". 9
:
:
0 Or+l,1
0 Qr+l,2
... ...
Q~ Qr+l,r
o Qr+l
... .9
08,1
08,2
.-.
Qs,r
Q,,~+I
...
0 0
0 0
:
:
o 0
o 0
08,8-1 Q~
(4.1)
C H A P T E R 4. B E H A V I O R IN M A R K O V S E T - C H A I N S
92
(1) r > _ l , (2) Q~. is n.i • ni and irreducible for all k = 1 , . . . ,r, and (3) if t > r, Qt,k # 0 for some k = 1 , . . . t - 1. In tile remaining work we will assume t h a t P, Q and all matrices in [P, Q] have undergone the same simultaneous row and column p e r m u t a t i o n s and t h a t each of these matrices has been partitioned, with corresponding notation, as the form (4.1). In addition, if Q is a submatrix of Q we use the n o t a t i o n A to denote the corresponding submatrix in A, for any n x n matrix A. Using this notation, define
[p, Q] = {,4: A 9 [P, 0]}. It is easily seen t h a t [P, Q] is a c o m p a c t convex set. T h e classification of states follows. D e f i n i t i o n 4.1. Let M be an interval [P,Q] for a Markov set-chain. Let Ci be the set of states corresponding to Qi. We classify the states of the Markov set-chain as follows.
(i) If i < r then Ci is called a closed. If lim [Pi,Qi] k exists and consists k--+ o o
only of positive rank 1 matrices, then Ci, and each of its states, is called ergodic. If Ci is ergodic and a singleton, then Ci, and its state, are called absorbing. (ii) If i > r then Ci is called open. Further, if l i m [Pi, Qi]k = {0}, then C,, and each of its states, is called transient. There are some rather simple sufficient conditions which can be used to determine if a class is ergodic or transient. Theorem
4.1. Let M be an interval [P, Q] for a Markov set-chain.
(i) For i <_ r, Ci is ergodic if Pi is primitive. (ii) For i > r, Ci is transient if lim Q/k = 0. k -4 oo
Proof. For the proof of (i), since Pi is primitive, there is a positive integer s such t h a t P [ has positive entries. Thus, P~ <_ .41 .-. A~ for all A 1 , . . . , A~ 9 [Pi, Qi]. By L e m m a 3.2, T([Pi, Qi] ~) < 1 and so by Corollary a.3, lim [Pi, Qi] k = [Pi, Qi] ~~ k ~oo
Now let p be the smallest entry in P/~. Then, since premultiplication of a column of a matrix by a stochastic matrix averages the column entries in t h a t matrix, for any positive integer k, (A1 . . . . 4kAk+l
. . . .
4k+s)ij > p
for all i,j and A 1 , . . . , A k + , 9 [Pi,Qi]. Thus, every matrix in [Pi,Qi] ~176 has all its entries at least, as large as p and thus, all matrices in [Pi, Qi] ~176 are positive. P r o p e r t y (ii) is obvious. []
4.1. CLASSIFICATION AND CONVERGENCE
93
The classification of states can now be used to describe the fundamental types of Markov set-chains. D e f i n i t i o n 4.2. Let M be an interval [P,Q] for a Markov set-chain. Markov set-chain is
The
(i) ergodic if it has only one class and that class is ergodic. (ii) regular if it has only one closed class, and that class is ergodic, while all open classes are transient. (iii) absorbing it each of its closed classes is a singleton and each of its open classes is transient. Of course, if the Markov set-chain is ergodic then lim M k = M ~ k---+oo
We now
show that convergence also holds for regular and absorbing Markov set-chains. The results require a preliminary theorem. T h e o r e m 4.2. Suppose a Markov set-chain, with ]lI an interval [P, Q], has all of its open classes transient. Let [P,Q] be the submatrix of [P,Q] that corresponds precisely to those transient classes. Then lira [P, ~]k = {0}. k ---+o o
Proof. The proof is by induction on the number of transient classes of the Markov set-chain. If there is only one transient class the result follows immediately from the definition of transient class. Now, suppose the theorem holds for m transient classes. If the Markov setchain has m + 1 transient classes, any matrix B E [P, Q] can be partitioned as is Q and then repartitioned Br+l Br+2,~+l
0 Br+2
0 0 =
.............................
Bs,r+l
[~1
Bs,r+2
0 ]
B21
B2
999 Bs
where s = r + m + 1 and B2 = Bs. Compatibly, repartition ~=
[
el P21
0 P2
]
and
0]
Q=
Q2 1
"
Then, since the class belonging to [P2, Q2] is a transient class, lim [P2,Q2] k = k---~oo
{0}. And, by the induction hypothesis, lira [P1,Q1] k = {0}. Thus, given any k--+oo
positive constant e, there is a positive integer N such that if k > N then
d({O},[P1,Q1] k) < e / 3
and
d({0},[P2,Q2] k) < e / 3 .
o ] and T2 = [D1 Now let T1 = [ ~U2~U2 ~ 2 ~ 2o ] be in [fi,~]k, partitioned as is B. Then IIClll
< e/3,
[[C2][ < e/3,
[]Dl[[ < e/3,
and
[]D2[] < e/3.
C H A P T E R 4. B E H A V I O R I N M A R K O V S E T - C H A I N S
94 Calculating,
T1T2=
IV1 0] [9 1 0] [ C1DI 0 ] C21 C2 921 D2 --C21DI+C2D21 62L)2 "
Since IIC2~II <_ 1, IID2111 <_ 1, IJCIDllJ <_ (e/3) 2, IJC2D21I _< (e/3) 2, and thus
IlC2101 + C2D2111 < IIU2tll IIDllJ + IIU211liD2, II < e/3 + e/3 = 2e/3 it follows that IIT~T=II ~ (2e/3) + (e/3) 2 < 2e/3 + e/3 : e. Hence,
d({O},[-P,-Q]k) <_ e forall
k >_ 2N.
Thus, lim [P,Q] k = {0}.
[]
k--+oo
C o r o l l a r y 4.1. Using the hypothesis of the theorem, there are constants K and fl, with 0 < fl < 1, such that d({0}, [~,~]h) _< g ~ h
for all positive integers h. Proof. Since, by Theorem 4.2, lim [P, Q]k = 0, given any positive constant e
k--+oo
there is a positive integer N such that if k > N, d({0}, [P, ~]k) < e. Thus, if B 1 , . . . , BN are any matrices in [P,Q] then lIB1 ... BNII < e. Now for any positive integer h, write
h=qN+r
where
0
Then, for any B 1 , . . . , Bh e [P, Q]
[[B1... BhJl
<_
[IB1... BN[I
.. .
HB(a-~)N+I... BqNIJ
_< (~)qN <s
(s
qN+r
<_ c-l(c-h ) h. The result follows by setting K = e-1 and j3 = e-~.
[]
The convergence result for regular Markov set-chains can now be established. T h e o r e m 4.3. Let M be an interval [P, Q] for a regular Markov set-chain. Then lim M k : M ~176 k--+oo
4.1. CLASSIFICATION AND CONVERGENCE
95
Proof. By the definition of regular, the Markov set-chain has only one ergodic class C1 and all of its other classes C2,. 99 , Cs are transient. Since C1 is ergodic lim [P1, Q1] k = [P1, Q1] ~176 contains only positive rank one matrices. k-+oo
Let e be a constant such that 0 < e < 1, where P and Q are n x n. Since lim [P1, Q1]k = [P1, Q1] ~176 we can find a positive integer N1 such that if k _> N1,
k--~cx3
d([P1, Q1]k, [P1, Q1] ~176< e. Thus, for k > N1, every matrix A E [P1, Q1] k can be written as A = F + E where F E [P1,Q1]~176 and I]EII < e. Now, if C1 contains nl states, the entries in some column of F are at least 1/nl and since 1 A has a positive column. ~ < n1 < - n--7' Let C = C2 tO .-. tO Cs and P , Q the corresponding submatrices in P, Q respectively. By Theorem 4.2, lim [~,~]k = {0}. Thus, there is a positive k--+ oo
integer N2 such t h a t for k _> N2, d([P,Q] k, {0}) < e. For any such k, if B 9
[ ~ , ~ ] k , I[Bll < e. Now let N = max{N1, N2} and let A 1 , . . . , AN; B1,... , BN 9 [P, Q]. Partitioning according to ergodic and transient classes, we can write FAll A22 0 A1 . . . A N = LA21
]
and
[.1, 01
B1... BN : [B21
B22
Calculating,
(AI""AN)(BI""BN)=
0fro,, 0]
[A21 A22 LB21 B22 [
AliBi1
= [A21B11+A22B21
0
]
A22B22J '
Recall t h a t Bll must have a positive column, say the j-th, and, since IIA2211 < e < ~, A21 can have no rows of O's. Thus, AliBi1 and A21B11 have their j - t h columns positive and so (A1... AN)(B1... BN) has its j - t h column positive. This implies t h a t "]-(Fo,2g) < 1 for any FO,2N E [P, Q]2N. And, since 7- is continuous and [P, Q]2N compact it follows that T ( M 2N) < 1. Hence M is product scrambling and thus, by Corollary 3.3, lim M k = M ~. [] k--+oo
C o r o l l a r y 4.2. Using the hypothesis of the theorem, there exist constants K
and/3, 0
[]
Absorbing Markov set-chains are also convergent. T h e o r e m 4.4. Let M be an interval [P, Q] for an absorbing Markov set-chain. Then lim M k exists. (This limit, for 2 or more absorbing states, is not M ~176 k---+ o o
96
C H A P T E R 4. B E H A V I O R I N M A R K O V S E T - C H A I N S
Proof. Let P, Q be the submatrices of P, Q respectively that correspond precisely to the transient states of the Markov set-chain. Then by Corollary 4.1, for all positive integers h, d([P, Q-]h, {0}) < K/3 h
(4.2)
where K and/3 are positive constants with/~ < 1. To show that lim M k exists we show that {Mk}k>_l is Cauchy. For this, k---~ cx)
let e be a positive constant and let N be a positive integer such that K/3N <-- 5e
and
g 2 /~N s -1--- ~ -< -3"
(4.3)
Now let u and v be positive integers where u, v > N. We assume without loss of generality that u < v. Let A1 . . . A ~ E M u. Choose any A ~ + I , . . . ,A~ E M. Then A 1 . . . A ~ E M ". For all k, partition each Ak according to its absorbing states and its transient states, so Ak =
[i o] Nk
Qk"
Thus, for any positive integer t, t _< v, 0 where Rt = N1 + Q1N2 + QIQ2N3 + "'" + QI ... Q t - l N t . t = v we see that
Taking t = u and
HAI...Av - A1...Aul[ =
[o
Rv-R~
o Q~...Q~-Q1...Qu
] <-
IIR. -R~,[I + IIQI . . . Q , - Q1 ... Q~II -< []Q1 . . . Q , N , + I
+ ... + Q 1 . . . Q ~ - ~ N v l l + [IQ1 ... Q~,l[ + IIQ~ ...Q.II -<
and by factoring and using (4.2) IIQ, ... Q.II [[Nu+l + . . . + Q u + l . . . Qv-lNv[[ + K 3 u + K/3 v Using (4.2) again, K < K /3u ~ _ 3 + K /3" + K /3V. And, using (4.3),
_<e.
4.1. CLASSIFICATION AND CONVERGENCE
97
Thus, M ~ C_ M v + ~. To show M v _C M ~ + e is as above except the matrix in M ~ is truncated to obtain the matrix in M ~. Thus, d(M u, M v) <_ e for all u, v _> N which assures that {Mk}k>_l is Cauchy. Thus, lim M k exists. [] k--+(x~
C o r o l l a r y 4.3. Using the hypothesis of the theorem and that L =
lim M k, k--~ c ~
there are constants K and/3, 0 u, K
d(M ~, M ~) < K ~ 3 ~ _ ~ + K~3~ + g~3 ~ K2 _ 1_ ~u
<_
+ K~
+ K~ ~
+K+K
~'~
< K ~ '~ --
K 2
where K = ~
+ 2K. Now, letting v --+ c~ yields
d(M", L) <_ K/3", the result of the corollary.
[]
E x a m p l e 4.1. Let M be an interval [P, Q] where
p=
0
1 0 .3
0 .2 .2
and
Q=
0
1 0 .4
0 .3 .3
"
Thus, M has two absorbing states and one open class which is transient. Hence, by Theorem 4.4, lim M k exists. Below we compute bounds on its limit set, k--+oo
say L. Since the last two columns of any matrix in L are composed of O's, we need only compute bounds on the first two columns. After thirty-nine iterations, remaining iterations repeated the previous calculation. We found the bounds on the first two columns of matrices in L to be
L~ =
1 0 .714285714 .238095238
0 1 .142857143 .571428571
'
F 1 H~ = / 0 .857142857 L.428571428
0 1 .28571428( .761904762
98
C H A P T E R 4. B E H A V I O R IN M A R K O V S E T - C H A I N S
In viewing the componentwise difference in these bounds, IIQ - PII = .3.
note that
We conclude the section with a result, needed later, that concerns a Markov set-chain that converges even after certain row changes in its matrices. For this, we need a few preliminaries. D e f i n i t i o n 4.3. Let M be the transition set for a Markov set-chain and let A C M. If the i-th row of A is replaced by e~, the resulting matrix is denoted by A. Define Me, = {A: A e M } . Note that Me, is a transition set for a Markov set-chain. L e m m a 4.1. Let M be the transition set for an ergodic Markov set-chain. Then, for any i, Me, is product scrambling. Thus, lim M~ = M ~ k --~ oo
*
e i
"
Proof. Since the Markov set-chain is ergodic, lim M ~ = Moo where M consists k--+oo
of positive rank one matrices. Thus, since Moo is compact, there is a positive matrix E such that E < B for any B E Moo. Since lim M k = M o o , there is a --
k--+oo
positive integer N such that
1-E < A 1 . . . A N 2 for any A 1 , . . . , AN E M. Written in terms of a column we have
1 E < (A1 AN)i < (A1 . A g ) i 2 ~" " where the subscripts indicate the i-th columns of the corresponding matrices. Hence T(A1... AN) < 1 and since Me, is compact, T ( M ~ ) < 1. Thus, Me, is product scrambling which proves the lemma. [] For the desired result we use the following definition. D e f i n i t i o n 4.4. Let M be the transition set for a Markov set-chain. For any A C M, replace row i in A by the 0 vector, obtaining A. Define
Mo, = { A :
AeM}.
Of course, Mo, is not a transition set. T h e o r e m 4.5. Let M be the transition set for an ergodic Markov set-chain.
Then, there are constants K and ~, 0 < fl < 1, such that d ( { O } , M h) <_ K ~ h for any positive integer h.
4.1. C L A S S I F I C A T I O N A N D C O N V E R G E N C E
99
Proof. For notational simplicity, and without loss of generality, we will suppose i=l. For any A E M, partition A C Mel as 1
0
Then A E Mo~, in partitioned form, is
[
],
By Lemma 4.1, Me 1 is product scrambling. Thus, M ~ is absorbing, with precisely one absorbing state. Prom this it follows that the Markov set-chain, with transition set M ~ , is regular. Thus, by Corollary 4.1, there are constants K and ~, 0 < ~ < 1, such that
IIQ1 ...Qhll _< K~ h
(4.5)
for any Q 1 , . . . , Qh corresponding, by (4.4), to A 1 , . . . Ah E Mo~. Now, let N be such that 1 K~ g < 2 and B, C E (Mol)N. Then BCe <
(4.6)
o(0)
where f is the (n - 1) x 1 vector of l's, <_ K ~ N e 1 < -e -2 1
by (4.5) and
by (4.6). Thus,
IIBCII < ~.
(4.7)
Now, for -A1,. 99 ,-Ah E Mol, write h = 2Nq + r where 0 < r < 2N. Then, using (4.7) we have IIA1...AhI] <_
< KZ h whereK--2and~=
(!~ 2-~ < 1. This gives the result. ~2j
[]
C H A P T E R 4. B E H A V I O R IN M A R K O V S E T - C H A I N S
100
4.2
Weak
law
of large
numbers
T h r o u g h o u t this section we let M be an interval for a regular Markov set-chain. From T h e o r e m 4.3 we know t h a t lim M k : M cr a set of rank one matrices. k--+oo
Let { X k } k > _ O be a nonhomogeneous Markov chain with transition m a t r i x Ak at step k and initial distribution vector y. T h e purpose of this section is to describe a weak law of large numbers (WLLN) for the n o n h o m o g e n e o u s Markov chain in a Markov set-chain setting. To obtain this result, we need a few preliminaries. For this, let f be a real valued function defined on {81,... , s,~}. Setting fi = f(si) we can denote this function by f = ( f l , . - - , fn) t. Now define, for any stochastic vector x,
L={xAf:
ACM ~
C_R.
Since M ~ is a set of rank 1 matrices L does not depend on the choice of x. Further, since M ~ is c o m p a c t and convex, so is L. Thus, L is a closed interval of R, the set of real numbers. D e f i n i t i o n 4.5. Let a E R and C a c o m p a c t set in R. Define ~(a,C)
= m i n [a - c I cCC
the distance between a and C. Lemma
4.2. Let A 1 , A 2 , . . . E M. Then lim g(xA1 . . . A k f , L) = O. k--+ oo
Proof. For fixed k, let B E M ~ such t h a t IIAx... Ak -
Bll
--
min
CEM ~
IIA1... Ak - VII.
(4.8)
Then
5(xA1. . . A k f , L) = min IxA1. . . A k f - II IEL
<_ ]xA1 ... A k f - xBfl <_ Ix(al . . . A k -- B ) f l _< [Ix(A1 ... Ak - B)II Ilfll
_< Ilxll [IA1 .., Ak - ell Ilfll __ I I A 1 . . . A k - BII Ilfll and by (4.8) < d ( M k, M ~ ) ] i f [ [ . Since M is regular, lim d ( M k M ~ ) = 0. T h e result follows. k--+a~
Lemma4.3.
lim ~(~=lEI(xl) k-~o~ i u , L ) = 0.
[]
4.2. WEAK LAW OF LARGE NUMBERS
101
Pro@ For each i, define li such t h a t
IE f (XD - ld = min IE f (X d - II tEL
= 5(Ef(Xi), L).
k
Define l (k) - l l + . .k. + z ~ C L. T h e n
(
~ Ef(Xd
5
) ,L
i=1
E ~/(xd <
l(k)
i=1
k
k
<
~
EY(Xd - l~ k
i:1
1
k
<_ ~
[Ef(Xi) -lil
i=I k
< i=l
<_
1
k
Z 5(xAI... Air, L). i=1
Now by L e m m a 4.2, lim (~(xA1 ... Akf, L ) = 0 and so by C a u c h y ' s T h e o r e m , k-+oo
k
. . . A J , L) = O.
lira 1 E S ( x A 1
k-~oo R
i=1
[] Using this lemma, we can obtain our version of the W L L N . 4.6. (WLLN). Let {Xk}k>_0 be a nonhomogeneous Markov chain with transition matrices in M. Let f be a real valued function defined on { s l , . . . , Sn}. Then, for any given constant ~,
Theorem
Pr
~
i=1 k
,L
>e
--+0 as k --~ c~.
Proof First observe t h a t if a, b E R then (f(a, L) = rain la - II <_ ~ i ~ ( l a - b[ + lb - II) lEL
= l a - bl + 6(b,L).
C H A P T E R 4. B E H A V I O R IN M A R K O V S E T - C H A I N S
102 k
k
( )
Thus, setting a = ~ f ( X i ) / k and b = ~ E f ( X i ) / k we have i=1
i=1
El(X,)
~=Ei(/(xd; E l ( X d ) 6
k
,L
i=1 k
+5
_<
,L
.
And,
E :(xd k ,L
>e
.~ ( f ( X i )
-
-
~
-{
5
i=l
E f (Xi) )
k
+
>
'
L
>
.
By L e m m a 4.3, the second t e r m on the right hand side of the inequality, is 0 for sufficiently large k. To show t h a t the first term on the right side also tends to 0 as k increases, by using Chebyshev's Inequality, we need only show t h a t
f(Xi)
k--~ Var
~ 0
as
k--+ oo.
i=1
As the computations for this are notationally rather intricate, we simplify notation by setting e(i) : E f ( X i ) and F : m a x { I f l l , . . . If,~l}- Recall t h a t
Var
f(xd = ~ Vat I ( X d i=1
+ 2 ~_,
Cov(I(X~),f(X~)).
i<j
i=1
We now find bounds on the two terms on the right side of this equation. k
(a) Bound on ~
Var f ( X i ) : For this, note t h a t
i=1
g(f(xd
- ~(i)) 2 = E f ~ ( X d - ~(i) ~ <_2 : .
Thus, k
k
} 2 Vat f ( x d : ~ i=1
(b) Bound on 2 ~
E ( : ( X d - 4i)) 2 < 2kF ~
i=1
C o v ( f ( X i ) , f ( X j ) ) : We first bound
i<j
E((f(Xi)
- e(i))(y(xi+s)
- e(i + s)))
(4.9)
4.2. WEAK LAW OF LARGE NUMBERS where 1 < i < k -
103
1 and 1 < s < k - i. For this, recall that Fr,s = A r + l A r + 2 . . . A r + s
so t h a t (4.9) becomes
EE
x--" ,(0,i),(i,~) 2__.yd~ Jh~ ( A - 4 i ) ) ( / j - ~ ( i + s ) ) =
E(sJ
_
h
j
s
n d~
+ s)) E
j
h
(o i) Y~f;h' (fh -
Now set 5h = ~
(sh
(4.10)
)
s
e(i)). Note that ~ ~h = 0. Thus, the expression
s
h
(4.10), and thus (4.9), is bounded by
2FT(Fi,s) E 15hi
4F2T(Fi,~) which, by using Corollary 4.2, is no larger than
4F2K~3~
(4.11)
for some constants K and t3 with 0 < fl < 1. Thus, since
~<J C o v ( / ( x d , / ( x j ) ) = 2 k-~ ~-i E(f(x~) 2Z Z Z
~(i))(f(X~+,)
- ~(i + s)) <
i=1 s=l
by (4.11)
k-1 k-i 8F2K k 2 E E 4 F 2 K ~ 3 ~ <- 1~-~ " i=l
s=l
Now, usingtheboundsfoundin(a) and(b)weseethat-~ Var(~f(Xi))i=x --* 0 as k --+ oc. This yields the theorem.
[]
In terms of the theorem we see that as the number of steps in a chain increase, k
f(Xi)
the average ~ ~
converges to L. For example, if f is the identity on
i=l
{sl,...,sn}then{~-~Xi} i=1 that
-~ ~ Xi i=1
converges to L. This, of course does not mean k>_0
converges. k>0
We can also convert Poisson's WLLN into a set-theoretic format.
C H A P T E R 4. B E H A V I O R I N M A R K O V S E T - C H A I N S
104 Theorem
4.7. Let {Xi}i>o be a sequence o/independent random variables with k
P r { X i = 1} = Pi and Pr{X~ = 0} = qi where Pi + qi = 1. Let X k = E X i / k , i=1 k
Pk = ~ p i / k and suppose a < Pi <_ b / o r all i. Then for any e > O, i--=1
Pr{a-e
< Xk < b+c}-+ l
as k--~ oc. Proof. Applying Poisson's WLLN, given any ( > 0, P r { f k -- e <_ X k < pk + e} -~ l as k ~ oo. Since a <_Pi <_ b for each i, it follows that a < Pk <-- b. Thus,
Pr{a-e
< Xk < b+e}-+ 1
as k -+ co.
[]
An example demonstrating Poisson's WLLN follows. E x a m p l e 4.2. Given a table covered with coins, a coin is selected and flipped. The probability of a head occurring no doubt depends on the coin selected. Suppose t h a t the probability of a head occurring ranges from .49 to .51. Let
Xa =
1 0
if the outcome of the k-th experiment is a head, and otherwise.
Then, for any positive constant e, P r { . 4 9 - e < Xk < . 5 1 + e} --+ 1 as k --+ oo. So, in the above sense, the average of the outcomes of the sequence of trials -~ [.49, .51] as k --+ oc. As a Markov set-chain use of Poisson's WLLN, suppose initially each nonhomogeneous Markov chain, with transition matrices in M, is in si. Now choose a sequence of the chains and a positive integer K . Define
Xk = ~ 1 (0
if the k-th chain in the sequence is in sj after K steps, and otherwise.
If LK = (l}K)) and HK = (hl K)) are the lower and upper bounds respectively, on M K, computed by the Hi-Lo method, then, for any positive constant e,
Pr{l}K) - e < X k < hl K) + e} --~ 1 as k -~ oo. So, in this sense, the average of the outcomes, at the K - t h step, of possibly different nonhomogeneous Markov chains, tends to the interval [lij (K) ,hij(g) ] a s k increases.
4.29 W E A K L A W OF L A R G E NUMBERS
105
E x a m p l e 4.3. A junior college wants to study its graduation rates 9 The college lists the state of a student as F:
Freshman
S:
Sophomore
G:
Graduate.
Transition matrices, for yearly steps, are determined with P and Q given as
G
S
= S F
F
.3 .4
Q =
.4 .5
Bounds for the first five years can be found in Table 4.1.
T a b l e 4.1. L i s t e d b e l o w a r e b o u n d s o n A1 . . . Ah f o r v a r i o u s c h o i c e s for k Lower bound Lk
Step k
[100] .84 .24
k=2
k=3
[ i9~ 6 9
k=4
k--5
Upper bound Hk
[1
99744 96624
.09 .35
.25
90 .22
00 ' .125
0 00]
.0081 .1235
.0625
1
0
0
.98976 .7872
9 .0658
0 .0312}
[10 ] .91 .35
9 9
[1
.16 .46
.36
9 .34
9
0
.9919 [.8015
.0256 .2296
9
1 .99757 [ .8967
0 .01024 .148
0 0 .07776
Interpreting the 3,3 entry for step 5 we see t h a t there is a small probability, between .03 and .08 (rounding to 2 digits), of a student still being classified as a freshman five years after entering the school. And, interpreting in terms of Poisson's WLLN, if different runs, with different nonhomogeneous Markov chains, are made, averaging the outcomes after 5 steps, the average tends to
[.03, .0s].
CHAPTER 4. BEHAVIOR IN MARKOV SET-CHAINS
106
4.3
B e h a v i o r in M a r k o v s e t - c h a i n s
Throughout this section we let M be an interval [P, Q] for a regular Markov set-chain. Let {Xk}n>0 be a nonhomogeneous Markov chain with transition matrix An in M at each step k. We partition each An according to the ergodic and transient states, An =
0 ]"
Ark
Qn
Finally, we use that Fo,n = AI 9.. Ak for all positive integers k. The behavior in the Markov set-chain is the movement of the nonhomogeneous Markov chain among the states, as the steps increase. In this section, we describe three kinds of movement: movement within the transient states, movement from the transient states to the ergodic states, and movement within the ergodic states. I
Movement
within
the
transient
states
We assume the nonhomogeneous Markov chain is initially in a transient state si. Let sj be another transient state. We intend to find the expected number of visits the chain makes to sj as the number of steps increase. For this, let
u(n)
if the chain is in sj at step k,
~1
ij = [ 0
otherwise.
Further define t
(i)
_(t) 7~iJ
:
. (k) Z aiJ and k=O O0
( i i ) - ( ILij ~)
:
~ _ ( kl~ij) k=O
which represent the number of visits of the chain to sj in t steps and for all steps, respectively. We compute the expected values as follows. For (i), we have t
k=O t
k=0
n)
4.3. B E H A V I O R I N M A R K O V S E T - C H A I N S
107
where f}o,o) = {10 i f i = j otherwise. For (ii), by Fubini's Theorem (x)
n (~) x--" ,~ (4) l:.,nij = ~.~ E'nij k----O oo
V" :!0 ,4) " ~ J~3 k=0
In matrix
form we have
(or [Eni i ] = (I + QI + Q1Q2 + .. . )ij. Corollary 4.1 can be used to show this sum converges. To compute tight bounds on I + Q1 + Q~Q2 + "'" we compute bounds on the last n - r columns of I + A1 + A1A2 + . " and delete the first r components in these bounds. To compute bounds for column j, begin by choosing a positive integer s. Then the j - t h column of P and the j - t h column of Q bound that of As. We write 11 <_ [As]j <_ hi where 11 and hi are the j - t h columns in P and Q and [As]j denotes the j - t h column of As. Thus, ej + ll <_ ej + [As]j ~ ej + h i . Now, using [P, Q], apply the Hi-Lo method to this interval of column vectors obtaining 12 <_ A~-l(ej + [As]j) <_ h2
or
12 <_ [A~-I]j + [As-lAs]~ <_ he. Again ej +12 < ej + [As-1]j + [As-lAs]j <_ ej + h2. Continuing, we have ej +ls <_ ej + [A1]j + . . . + [A1...A~]j <_ ej + h~. If at this point we find that our choice of s was too small, set s -- s + 1 and compute the next bounds. And, of course, this can be continued. E x a m p l e 4.4, We continue Example 4.3 of studying graduation rates of a junior college. Here, we add to that study the expected number of visits to each class. Bounds on this expected number are given in Table 4.2.
CHAPTER 4. BEHAVIOR IN M A R K O V SET-CHAINS
108
Table 4.2. B o u n d s o n t h e e x p e c t e d n u m b e r of v i s i t s i n e a c h c l a s s Step k
Lower bound Lk
k---1
[173 :.
1.075]
k=2
[1.417 [1.012
0 ] 1.875
k: 3
k=4 k=5
Upper bound Hk
[195 :.
1.096]
[1.624 0 ] [1.255 2.176
[1141275: .0 ] . 1.9375 0] [1.27444 1.96875 0 I [1.335676 1.984375
rl[1.4395 .6496 2.3056 o] 0] [1.54455 2.38336 r160 90 o6] [1.602195 2.43001
We interpret the result of step 5. Here 1.43 < End51) < 1.66 1.34 _< En~ ) <_ 1.60 1.98 _< E n ~ ) <_ 2.43
(rounded to 3 digits).
Of course, the initial visit (beginning freshman) counts in these values. For a large number of steps, to 3 digits we have 1.43 _< E n ~ ) < 1.67 1.43 ~ En(T ) <_ 1.67
2.00 < E n ~ ) <_ 2.50. II
Movement
from a transient
state to an absorbing
state
In this study we assume that the regular Markov set-chain has only one ergodic state, namely sl. Thus, this state is absorbing. We assume the nonhomogeneous Markov chain is initially in a transient state si and we find the expected number of steps the chain takes in order to reach the absorbing state Sl. Using the work in part I, we define ~
= E , nl~ ) jcT
4.3. BEHAVIOR IN M A R K O V SET-CHAINS
109
where T = { 2 , . . . , n}. Thus ti sums the number of visits of the chain to each transient state sj and so t~ is the number of visits to transients states before absorption. The expected value of ti is
Eti = E
" (~) l~nij
sjET O0
= K-,~dO,k) ... f(0,k)~ /__~wi,2 + f}o,3'k) + +-i,n , k=O
and in matrix form
= e i ( I + Q1 + Q1Q2 + ' " ) e . To compute tight bounds on
( I + Q1 + " " + Q 1 . . . Q s ) e we need to proceed as in To begin, we need to with its first component using [P, Q] to apply the that
part I, with a slight adjustment. find column tight bounds on A s f where f is a vector 0 and all other components 1. This can be done by Hi-Lo method to f . This gives bounds ll and hi such
ll <_A s f <_ hl. Now, we can proceed as in part I. E x a m p l e 4.5. This example continues the study of the flow of students through the states (freshman, sophomore, graduate) for a junior college. (See E x a m ple 4.3 and Example 4.4.) Here we continue to add information by computing the expected number of years it takes to graduate. We compute this number by finding bounds on
ei(I + Q1 + Q1 + Q2 + " " )e for i = 2 (sophomore state) and i = 3 (freshman state) for the regular Markov set-chain with
P =
.3 .4
,
These bounds are recorded in Table 4.3.
Q =
.4 .5
.
CHAPTER 4. BEHAVIOR IN M A R K O V SET-CHAINS
110
Table 4.3. B o u n d s o n (I + Q1 + " " + Q . . . Qk)e for
several choices of k Lower bound lk
Upper bound hk
/139
(156
(1:o:)
(1:::)
k= 4
(1.4251"~ [,3.2185]
/1.6496"~ ~,3.6176]
k = 100
/'1.42857143"~ ~3.42857143]
/1.66666667'~ \4.16666667]
Step k
k= 2
~,2.65]
\2.77]
Thus from Table 4.3, at the 100-th step, 1.43 _< Etl <_ 1.67 3.43 < Et2 < 4.17
(rounded to 3 digits).
So, seniors require between 1.43 and 1.67 years to graduate while freshmen require between 3.43 and 4.17 years to graduate.
III
Movement
within an ergodic class
We suppose that the Markov set-chain has precisely one class and that class is ergodic. Let si and sj be states in this class and suppose the nonhomogeneous Markov chain is initially in s/. We find the expected number of steps before the chain enters sj for the first time. We define the needed random variables as
p(k)
~1 ij -- 1,0
if the process is in sj at step k, for the first time, otherwise.
Then O0
, (k) Pij = 2.~ tcPiJ k=0
is called the first passage time from si to sj.
4.3. BEHAVIOR IN M A R K O V SET-CHAINS
111
Thus, OG
~-~ .,~ (k)
Epid : ~ tgs k=0
= (A1 + 2A1A2 + " - + kAI-A2...Ak + " ' ) i d
(4.12)
where Ak is the matrix Ak with j - t h row replaced by a row of O's. By Theorem 4.5, this sum converges. To compute bounds on Epij we proceed as follows. First note that the Hi-Lo method, using the i-th row of [P, Q], uses a bounded set of stochastic row vectors, say [Pi, qi], to find the i-th component bound on a bounded set of column vectors, say [/, h], and computes bounds on [Pi, qi][1, hi. Thus, using the Hi-Lo method on the nonzero rows of [P, Q], and simply recording the 0 row bound as 0, we can sequentially compute the k-th column bounds on the expression in (4.12). We begin noting that
l < [Ar]j ~_ h where I and h are the j - t h columns of P and Q respectively while [Ar]j denotes the j - t h column of At. Hence
rl ~ r[Ar]j __~rh
and
11 = (r - 1)ej + rl ~ [(r - 1)ej + r[Ar]j ~ (r - 1)ed + rh = hi. We can continue this technique to get 1~-1 _< ej + 2[A2]j + . . . + r [ A 2 . . . A ~ ] j < hr-1. Finally, using [P, Q], we can apply the Hi-Lo technique on this bounded set of column vectors to get l~ _< ey + [A1]j + 2[A1A2]j + " - +
r[AIA2 . . . A r ] j -~ hr-
E x a m p l e 4.6. In the study of occupational mobility, occupations are classified as upper, middle, and lower. The study seeks information on movement between these classes. This is done, at least in the study of Glass and Hall (1954) and Prais (1955), by seeing if the first sons occupation is different from that of his father. The transition matrix used in that study, using approximates for simplicity, was Upper Middle Lower Middle Lower
.06 .02
4~ 00]
.69 .50
.25 .48
.
112
C H A P T E R 4. BEHAVIOR IN M A R K O V SET-CHAINS
We will assume there is some fluctuation and that transition matrices are in the interval determined by
P =
.04 .01
.67 .48
.23 , .46
Q =
.08 .03
.71 .52
.27 . .50
Computing upper and lower bounds on A1A2... Ak, as k increases, we have
L~ =
.05 .05
.59 .59
.27 .27
H~ =
.11 .11
.64 .64
.34 .34
(rounding to 2 digits). Thus, if Xk denotes the vector of upper, middle, and lower percentages of population at time k, then xk -~ [/~, h~] as k --+ ~ where loo -- (.05, .59, .27) and hoo = (.11, .64, .34). Thus, under the assumptions given, between 5% and 11% of the population will be in the upper class, between 59% and 64% in the middle class, and between 27% and 34% in the low class. Of course, there may be fluctuations, with steps, within those classes. We now calculate the mean first passage times, by the method described in this part, we get
15 16
1.5 1.9
3.9 3.0
<_ [E(pij)] _< 34 35
1.7 2.1
4.9 . 3.7
Thus, interpreting the 3,1-entries, it is expected to take between 16 and 35 generations for some family in the lower occupation classification to move into the higher occupational classification, according to the data we have. Related
research
notes
The basic work of this chapter, including the WLLNs, was taken from Hartfiel and Seneta (1994). Additional material for this chapter is given below. (a) H i s t o r y . Seneta (1996) gave a historical review of WLLN and CLT (Central Limit Theorem) for Markov chains and nonhomogeneous Markov chains. References to additional work is also given there. Also see Seneta (1973). (b) A p p l i c a t i o n s . Markov set-chains have been used in ways other than those shown in this book. Diamond et al. (1990 and 1995) use interval stochastic matrices [P, Q] to investigate some strategies to suppress collapsing effects when chaotic dynamical systems are approximated by spatial discretization. Masami et al. (1997 and 1998) use Markov set-chains to develop controlled Markov set-chains with discounting. Some computational work is included. In his book, Paz (1971) studies probabilistic automata by considering Markov systems. A Markov system is basically a finite set M of stochastic matrices. The
4.3. BEHAVI OR IN M A R K O V SET-CHAINS
113
important part of this work concerns products of matrices from M. Some of our theory of Markov set-chains can be used in that setting and, by bounding the matrices in M by P and Q, our computational work can also be used.
Appendix T h i s a p p e n d i x gives a brief s u r v e y of several topics of m a t h e m a t i c s used w i t h i n t h i s m o n o g r a p h . References to full d e s c r i p t i o n s of these topics are p r o v i d e d . T h r o u g h o u t this a p p e n d i x we let V b e a v e c t o r space. F o r o u r work, t h e d o m a i n of V will b e t h e v e c t o r spaces R n a n d t h e v e c t o r spaces of n • n m a t r i c e s w i t h real entries.
A.1
Norms
W e d e s c r i b e t h e n o r m used in this m o n o g r a p h . T h e v e c t o r n o r m we use on row v e c t o r s is defined as n
Ilxll = Z IxL k=l
w h e r e x = ( x l , . . . , x,~). T h i s is t h e s t a n d a r d 1-norm. F o r t h e r e l a t e d m a t r i x n o r m we use i]AII = m a x
ILxAII
Ilxll
w h e r e A is a n n • n real m a t r i x . T h i s m a t r i x n o r m is n o t s t a n d a r d since we c o n s i d e r left m u l t i p l i c a t i o n b y vectors r a t h e r t h a n t h e u s u a l right m u l t i p l i c a t i o n . U s i n g t h i s definition it can b e shown, using precisely t h e s t a n d a r d techniques, that n
IIAII = m ax~-~, laikl. k=l
F r o m this it is clear t h a t if A is s t o c h a s t i c , IIAGI= 1. F o r a m o r e full discussion on n o r m s see F r a n k l i n (1968) or, for a m o r e recent b o o k , see D a t t a (1995).
A.2
Operations
on compact
sets
T h a t t h e infinite i n t e r s e c t i o n a n d t h e finite union of c o m p a c t sets is c o m p a c t is well known. W h a t we discuss here are t h e results of a r i t h m e t i c o p e r a t i o n s on c o m p a c t sets.
116
APPENDIX
D e f i n i t i o n A . 1 . If C and K are subsets of V, then (i) C + K = { c + k :
cECandkEK}.
For any scalar c~, (ii) c ~ C = { a c :
cEC}.
A n d for the n x n matrices, (iii) C K = {ck: c E C and k E K } . T h e following result is easily shown. T h e o r e m A . 1 . Let V be a normed vector space. If C and K are compact sets then so are C + K , a C , and C K .
A.3
Convex sets, polytopes, and vertices
Studies of convex sets, polytopes, and vertices are included in m a n y books 9 W h a t we are interested in here is to put together t h a t work which pertains to m a t r i x theory, and, in particular, supports the work in this monograph 9 We divide this p a r t into general results and p o l y t o p e results. T h e general results are covered first9 D e f i n i t i o n A . 2 . A subset C of V is convex if whenever x, y E C then c~x + (1 - a ) y E C for any scalar ~, 0 < a < 1. T h e o r e m A . 2 . The s u m of convex sets and the product of a scalar and a convex set are convex. In addition, the closure of a convex set is convex and the intersection of infinitely m a n y convex sets in V is convex. ( T h e first two results are easily shown. The latter two results can be f o u n d in Eggleston, p. 8-9). A vector v E V is a convex combination of vectors V l , . . . ,vr E V if there are nonnegative scalars ~ 1 , . . . , ~ r such t h a t c~1 + .-- + ~r = 1 and v = ~1Vl + 9 ..
~- OlrV r.
D e f i n i t i o n A . 3 . Let K be a n o n e m p t y set in V. (i) T h e set which is the intersection of all convex sets containing K is called the convex hull of K , written conv K . (ii) T h e set of all convex combinations of all finite subsets of K is called the convex span of K , written convex span K . It is easily shown t h a t conv K = convex span K and t h a t this set is convex 9 A simple description of a c o m p a c t convex set can be achieved by using the following special points.
A.3.
C O N V E X SETS, P O L Y T O P E S , A N D V E R T I C E S
117
D e f i n i t i o n A . 4 . A p o i n t p in a convex set C is an e x t r e m e p o i n t of C if w h e n ever p is a convex c o m b i n a t i o n of x, y E C t h e n p = x or p = y. C o m p a c t convex sets can b e d e s c r i b e d , in t e r m s of e x t r e m e points, as follows. Krein-Milman Theorem. A c o m p a c t convex set C is t h e convex hull of its e x t r e m e points. ( K e l l y a n d Weiss, p. 205) Before l e a v i n g t h e g e n e r a l results of this p a r t we a d d one a d d i t i o n a l r e s u l t which is s o m e t i m e s useful. Caratheodory Theorem. L e t S C_ V. If y E conv S t h e n t h e r e is a set of v e c t o r s x l , . . . , x8 in S, w h e r e s <_ d i m V, such t h a t y is a convex c o m b i n a t i o n of x l , . . . , xs. (Eggleston, p. 35) W e now give t h e p o l y t o p e results. D e f i n i t i o n A . 5 . A convex set P is called a convex p o l y t o p e if t h e r e is a finite set K such t h a t P = cony K . If no v e c t o r in K is a convex c o m b i n a t i o n of t h e r e m a i n i n g v e c t o r s in K , t h e n K is convexly i n d e p e n d e n t . It is easily shown t h a t if P is a convex p o l y t o p e a n d P = c o n v K t h e n t h e r e is a s u b s e t K ' of K which is convexly i n d e p e n d e n t a n d cony K = c o n v K ' . Theorem
A . 3 . Let K - - { v l , . . . , v r } C_ V. Then, cony K is compact.
Proof. Let M = m a x { l [ v l l l , . . . , I]v~l[}. If v E conv K we can w r i t e v = a l V l + 9. " + a r v ~ , a convex sum. T h e n I[vl[ _< a l [ I v l l [ + " - + a ~ IIv~[I _< a i M + . . . + a ~ M = M . T h u s , conv K is b o u n d e d b y M . W e now n e e d t o show t h a t conv K is closed. F o r this, let w b e a l i m i t p o i n t of conv K . T h e n , t h e r e is a sequence Wl, w 2 , . . , of vectors in conv K t h a t converges to w. Since w l , w 2 , . . , a r e in cony K , we can w r i t e t h e m as convex c o m b i n a t i o n s , Wk :
O Z k l V 1 + " "" + OLkrV r
for
each
k.
Since ( a 1 1 , . . . , (~ir), ( a 2 1 , . . . , a 2 ~ ) , . . , are in R ~ a n d this sequence is b o u n d e d it follows t h a t this sequence has a convergent subsequence, say (akl x , . . . , akin), ( a k 2 1 , . . . , a k 2 r ) , - - - 9 S u p p o s e this sequence converges t o ( a 0 1 , . . . , a0~). Since a k l + " 9+ ak~ = 1, for all k, it follows, by t a k i n g t h e limit, t h a t a01 + - + a 0 ~ = 1. A n d , b y a limit a r g u m e n t it also follows t h a t a o l >_ 0 , . . . , ao~ _> 0. T h u s , a01Vl + " 9 " - ~ - O l o r V r i s in convex s p a n K . Since wk~ = O ~ k i l V l + " 9 " + O l k l r V r , b y c o m p u t i n g t h e limit we have t h a t w = a01vl + " . + a 0 ~ v ~ . T h u s w E conv K a n d it follows t h a t conv K is closed 9 [] 9
-
U s i n g this t h e o r e m a n d t h e K r e i n - M i l m a n T h e o r e m we know t h a t a p o l y t o p e is t h e convex hull of its e x t r e m e points. A c t u a l l y , we can show t h a t t h e e x t r e m e p o i n t s are all in K . A . 1 . Let K = { v l , . . . ,vr} C_ V and convexly independent. is the set of all extreme points o] cony K .
Lemma
Then K
118
APPENDIX
Proof. Let v E conv K a n d v ~ K . We need to show t h a t v is n o t a n e x t r e m e p o i n t of conv K . Since v ~ conv K we can write v = c~lvl + . . . + c~rvr, a convex c o m b i n a t i o n . Since v ~ K there are at least two a i ' s t h a t are not 0. W i t h o u t loss of generality, suppose c~l # 0 a n d c~r # 0. Set p = vl a n d q - - ~1-~1 1-~1 --~v2+"-+ c~ v r so p,q E conv K . T h e n , v = c ~ l p + (1 - c~l)q. Since v r K , p # v a n d as a consequence, q # v. T h u s , v is n o t a n e x t r e m e p o i n t of conv K . Now, we need to show t h a t every vector in K is a n e x t r e m e p o i n t of conv K . W i t h o u t loss of generality, suppose vl = a v + ~w a convex c o m b i n a t i o n where v, w E c o n v K a n d 0 < c ~ < 1. Write v - - ~ c~vi a n d w = ~ ~ivi, convex c o m b i n a t i o n s . T h e n i=1
i=1
; (~c~1 + ~1)v1 + - . . + ( c ~ + r162 a convex c o m b i n a t i o n . Now, if c~ctl + ~ 1 < 1 we can show t h a t Vl can be w r i t t e n as a convex c o m b i n a t i o n of v2, 9 9 , v~ which denies t h a t K is convexly i n d e p e n d e n t . Thus, c~c~l + BB1 = 1 a n d so, c~1 = 81 = 1. T h u s , v = vl a n d w = Vl from which it follows t h a t vl is an e x t r e m e point. [] We should add t h a t the extreme points in a convex p o l y t o p e are u s u a l l y called vertices. Some of the work, in this m o n o g r a p h , concerns showing t h a t a convex set is in fact a polytope. W h e n this is done, the following t h e o r e m is useful. Theorem
A . 4 . Let C be a convex set. If
(i) C is compact and (ii) C has finitely m a n y vertices then C is a convex polytope. Most of the m a t e r i a l in this part was taken from Eggleston (1969) as well as Kelly a n d Weiss (1979).
A.4
Distance
on
compact
sets
In this p a r t of the appendix, we review two distance calculations on c o m p a c t sets: d i a m e t e r of a set a n d Hausdorff metric, For the Hausdorff metric, we let
H(V) ={W:
W is a c o m p a c t set in V}.
Using this set, we define the Hausdorff metric.
A.4. DISTANCE ON COMPACT SETS
119
D e f i n i t i o n A . 6 . For any X, Y E H(V) define
6 ( X , Y ) = max(min [Ix - Y]I) and zEX yEY
d(X, Y) = max{6(X, }'), 6(Y, X)}. The function d is called the Hausdorff metric on H ( V ) . Theorem
A . 5 . The Hausdorff metric is itself a metric. (Barnsley, p. 34)
As expected, if X1, X 2 , . . . is a sequence from H ( V ) , then lim Xk = X
means
k---~ oo
lim d(Xk, X) = O. k--4 oo
From this, Cauchy sequences can be defined and the following can be shown. Theorem
A . 6 . H(V) is a complete metric space. (Barnsley, p. 37)
A set theoretic description, often useful as well as geometrically appealing, of the Hausdorff metric follows. D e f i n i t i o n A . 7 . Let X be a compact set of V and e > 0. Then X+e={y:
]lx-yH <e
for some
x6X}.
A . 7 . Let X and Y be compact subsets of V. Then ~ ( X , Y ) <_ e if] X C Y +e. Thus, d ( X , Y ) < e if[ X q Y +e a n d Y C_ X +e. (Barnsley, p. 35)
Theorem
In the monograph, we refer to d being continuous. To make this clear, we include a theorem. For it, we need a lemma. L e m m a A . 2 . Let X, X, Y, Y be compact sets in V. Then
Id(X,Y) - d(X, Y)I < d(X, X) + d(Y,~'). Proof. By the triangle inequality, d ( X , Y ) <_d ( X , X ) + d(X,~')
so
d(X,Y) - d(X,Y) < d(X,X).
(1)
Also, m
d(X,Y) < d(X,X) + d(X,Y)
so
d(X, Y) - d(X, Y) < d(X, X).
(2)
Using (1) and (2),
I d( X , Y) - d(X, Y)I _< d ( X , X ) .
(3)
APPENDIX
120 Now, using (3),
[d(X, Y ) - d( X , Y)[ <_ [ d ( X , Y ) - d ( X , Y ) + d(X, Y ) - d( X , Y)[ <_ Id(X, Y ) - d ( X , Y)l + ]d(X, Y) - d(X, Y)l <_ d(X, X ) + d(Y, Y ) [] As a consequence, we have the following. T h e o r e m A.8. Let {Xk }k>_o be a sequence of compact sets and suppose lira Xk = k -~ oo
X , a compact set. Then, for any compact set Y lim d(Xk, Y ) = d(X, Y). k--+ o ~
Another result, easily shown, that we use follows. T h e o r e m A.9. Let {Xk}k_0 be a sequence of compact sets and suppose lira Xk = X , a compact set. If F is an n • n matrix then l i m ( X k F ) = X F . k ---~o o
x -+ oo
(Here, for any set Y, Y F = {yF: y C Y } . ) An interesting result links compactness of a metric space to that of the defining space. T h e o r e m A . 1 0 . Let X C_ V be compact. Then ( H ( X ) , d ) is a compact metric space. (Barnsley, p. 34) The diameter of a set is given below. D e f i n i t i o n A.8. Let X be a compact set in V. The diameter of X is defined as
A(X)--max{llx-y[l:
x,y e X}.
(Kelly and Weiss, p. 54 or Eggleston, p. 23) A final result describes the continuity of A. T h e o r e m A.11. If X and Y are compact sets in V and d ( X , Y ) <_ e then IA(X) - A(Y)I _< 2e.
Proof. Since d ( X , Y ) <_ e it follows by Theorem A.7 that X _C Y + e and Y C X + e. Thus, A ( X ) < A(Y) + 2e and A(Y) < A ( X ) + 2e. From this we have I A ( X ) - A(Y)[ < 2e. [] From this theorem it follows that if X1, X 2 , . . . is a sequence of compact sets in V and lira Xk = X, a compact set in V, then lira A(Xk) = A ( X ) . k--+oo
x-~oo
For additional material in this area see Berge (1963), Eggleston (1969), Kelly and Weise (1979), and Barnsley (1988).
A.5. PROBABILITY RESULTS
A.5
121
Probability results
In this part we list several probability results used in Chapter 4. Since these results are somewhat scattered, we organize them here. C a u c h y ' s T h e o r e m . Let sl, s 2 , . . , be a sequence of numbers. Define
sl + ... + Sn t n
-n
for all n > 0. If {Sk}k>_l converges to s then Snell, and Knapp, p. 36) Fubini's Theorem. then
If
{tk}k>_, converges to s. (Kemeny,
{Xk} is a sequence of nonnegative random variables, E
Xk
E EXk.
k=0
k:0
(Kemeny, Snell, and Knapp, p. 53 or Loeve, p. 125) C h e b y s h e v ' s I n e q u a l i t y . Let, X be a random variable having mean # and let t be a positive number. Then
Pr{IX
-
1 Var(X)2. #l >_t} ~_ -~
(Clark and Disney, p. 147) P o i s s o n W L L N . If in a sequence of independent trials, the probability of occurrence of an event A in the k-th trial is equal to Pk, then lim n--+ c~
Pr{l# ?2
Pl+'"+Pnt
<e} = 1
n
where, as usual, it denotes the number of occurrences of A in the first n trials. (Gnedenko, p. 201)
Bibliography Alefeld, G., Herzberger, J. (1983): Introduction to interval computations. Academic Press, New York Alefeld, G., Kreinovich, V., Mayer, G. (1997): On the shape of the symmetric, persymmetric, and skew-symmetric solution set. SIAM J. Matrix Anal. Appl. 18, 693-705 Altham, P.M.E. (1970): The measurement of association of rows and columns for the rxs contingency table. J. Roy. Statist. Soc. Set B 32, 63-73 Anthonisse, Jac.M., Tijms, H. (1977): Exponential convergence of products of stochastic matrices. J. Math. Anal. Appl. 59, 360-364 Artzrouni, M. (1983): A theorem on products of matrices. Linear Algebra Appl. 49, 153-159 Artzrouni, M. (1986): On the convergence of infinite products of matrices. Linear Algebra Appl. 74, 11-21 Artzrouni, M. (1991): On the growth of infinite products of slowly varying primitive matrices. Linear Algebra Appl. 145, 33-57 Artzrouni, M., Li, X. (1995): A note on the coefficient of ergodicity of a columnallowable nonnegative matrix. Linear Algebra Appl. 214, 93-101 Barmish, B.R., Hollot, C.V. (1984): Counter-examples to a recent result on the stability interval matrices by S. Bialas. Int. J. Control 39, 1103 1104 Barnsley, M. (1988): Fractals everywhere. Academic Press, New York Bauer, F.L., Deutsch, E., Stoer, J. (1969): Absch/izungen ffir die Eigenwerte positiver linearer operatoren. Linear Algebra Appl. 2, 275-301 Ben-Haim, Y., Elishakoff, I. (1990): Convex models of uncertainty in applied mathematics, Elsevier, New York Berge, C. (1963): Topological spaces. Oliver and Boyd, Edinburgh Berman, A., Plemmons, R. (1979): Nonnegative matrices in the mathematical sciences. Academic Press, New York Bialas, S. (1983): A necessary and sufficient condition for the stability of interval matrices. Int. J. Control 37, 717-722 Birkhoff, G. (1967): Lattice theory, 3rd edn. American Mathematical Society Colloquium Publications XXV, Providence, Rhode Island Bone, T., Jeffries, C, Klee, V. (1988): A qualitative analysis of x ~ = A x + b. Disc. Appl. Math. 20, 9-30
124
BIBLIOGRAPHY
Bowerman, B., David, H.T., Isaacson, D. (1977): The convergence of Cesaro averages for certain non-stationary Markov chains. Stoch. Proc. Appl. 5, 221-230 Brualdi, R.A., Shader, B.L. (1995): Matrices of sign-solvable linear systems. Cambridge University Press, Cambridge Bushell, P. (1973): Hilberts metric and positive contraction in Banach space. Arch. Rational Mech. Anal. 52, 330-338 Carmeli, M. (1983): Statistical theory and random matrices. M. Dekker, New York Chatterjee S., Seneta, E. (1977): Towards consensus: some convergence theorems on repeated averaging. J. Appl. Prob. 14, 89-97 Christian, Jr., F.L. (1979): A K-measure of irreducibility and doubly stochastic matrices. Linear Algebra Appl. 24, 225-237 Clarke, B.L. (1975): Theorems on chemical network stability. J. Chem. Phys. 62, 773-775 Clarke, B.L., Disney, R.L. (1970): Probability and random processes for engineers and scientists. John Wiley, New York Cohen, J.E. (1979): Contractive inhomogeneous products of non-negative matrices. Math. Proc. Camb. Phil. Soc. 86, 351-364 Cohen, J.E., Sellers, P.H. (1982): Sets of nonnegative matrices with positive inhomogeneous products. Linear Algebra Appl. 47, 185-192 Cohen, J.E., Kesten, H., Newman, C.M. (Editors) (1986): Random matrices and their applications. Contemporary Mathematics 50, Amer. Math. Soc., Providence Courtois, P.J., Semal, P. (1984): Error bounds for analysis by decomposition of nonnegative matrices. Mathematical Computer Performance and Reliability. Elsevier Science Publishers, North Holland, New York, 209-224 Crisanti, A., Paladin, G., Vulpiani, A. (1993): Products of random matrices in statistical physics. Springer-Verlag, Berlin-Heidelberg-New York Cull, P., Vogt, A. (1973): Mathematical analysis of the asymptotic behavior of the Leslie population matrix model. Bull. Math. Bio. 35, 645-661 Datta, B.N. (1995): Numerical linear algebra and applications. Brooks/Cole Publishing Company, Pacific Grove, California Daubechies, I., Langarias, J.C. (1992): Sets of matrices all infinite products of which converge. Linear Algebra Appl. 161,227-263 Deutsch, E., Zenger, C. (1971): Inclusion domains for the eigenvalues of stochastic matrices. Numer. Math. 18, 182-192 Diamond, P., Kloeden, P., Pokrouskii, A. (1994): Interval stochastic matrices and simulation of chaotic dynamics. Contemporary Mathematics 172, Amer. Math. Soc., Providence, 203-215 Diamond, P., Kloeden, P., Pokrouskii, A. (1995): Interval stochastic matrices, a combinatorial lemma and the computation of invarient measures of dynamicals systems. J. Dynam. Diff. Eq. 7, 341-364.
MARKOV-SET CHAINS
125
Dobrushin, R.L. (1956): Central limit theorem for non-stationary Markov chains, I, II. Theor. Prob. Appl. 1, 63-80, 329-383 Doeblin, W. (1938): Expos@ dela th~orie das chaines simples constantes de Markoff s un hombre fini d'etates. Reune Math@matiqde (Union Interbolk amique) 2, 77-105 Eggleston, H.G. (1969): Convexity. Cambridge University Press, Cambridge Elsner, L. Koltracht, I., Neuman, M. (1990): On the convergence of asynchromous paracontractions with applications to tomographic reconstructions from incomplete data. Linear Algebra Appl. 130, 65-82 Eschenbach, C.A. (1993): Sign patterns that require exactly one real eigenvalue and patterns that require n - 1 non real eigenvalues. Linear and Multilinear Algebra 35, 213-223 Eschenbach, C.A., Johnson, C.R. (1991): Sign patterns that require real, non real, and pure imaginary eigenvalues. Linear and Multilinear Algebra 29, 299-311 Eschenbach, C.A., Johnson C.R. (1993): Sign patterns that require repeated eigenvalues. Linear Algebra Applic. 190, 169-179 Faedo, S. (1953): Un nuovo problema di stabilit/~ per le equazioni algebriche a coefficienti reali. Ann. Scuola Norm. Super. Piza 3, 53-63 Fenner, T.I., Loizou, G. (1971): On fully indecomposable matrices, J. of Computer and System Sciences 5,607-622 Fiedler, M. (1972): Bounds for eigenvalues of doubly stochastic matrices. Linear Algebra Appl. 5, 299-310 Fiedler, M. (1995): An estimate for the nonstochastic eigenvalues of doubly stochastic matrices. Linear Algebra Appl. 214, 133-143 Franklin, J. (1968): Matrix theory. Prentice-Hall, Englewood Cliffs, New Jersey Freese, R., Johnson, C.R. (1974): Comments on the discrete matrix model of population dynamics. J. of Research of the National Bureau of Standards B. Mathematical Sciences 788, No. 2, 73-78 Friedland, S., Schneider, H. (1980): The growth of powers of a nonnegative matrix. SIAM J. Alg. Disc. Meth. 1, 185-200 Funderlic, R.E., Meyer, C.D. (1985): Sensitivity of the stationary distribution vector of an ergodic Markov chain. ORNL-6098, Oak Ridge National Laboratory, Oak Ridge, Tennessee Funderlic, R.E., Meyer, C.D. (1986): Sensitivity of the stationary distribution vector of an ergodic Markov chain. Linear Algebra Appl. 76, 1-17 Gantmacher, F.F. (1964): The theory of matrices. (vol. 1 and vol. 2). Chelsea Publishing Co., New York Garloff, J., Schwierz, K-P. (1980): A bibliography on interval mathematics II. J. Comput. Appl. Math. 6, 67-79 Geramita, J.M., Pullman, N.J. (1984): Classifying the asymptotic behavior of some linear models. Math. Bio. 69, 189-198. Glass, D.V., Hall, J.R. (1954): Social mobility in Great Britain: A study of intergeneration changes in status. Social Mobility in Great Britain. Routledge
126
BIBLIOGRAPHY
and Kegan Paul, London Gnedenko, B.V. (1982): The theory of probability. (translated by George Yankovsky), Mir Publishers, Moscow Golubitsky, M., Keeler, E.B., Rothschild, M. (1975): Convergence of age structure: applications of the projective metric. Theor. Pop. Bio. 7, 84-93 Gorman, W.M. (1964): More scope for qualitative economics. R. Econ. Studies 31, 65-68 Gregory, D.A., Kirktand, S.J., Pullman, N.J. (1992): Row stochastic matrices with common left fixed-vector. Linear Algebra Appl. 169, 131-149 Hajnal, J. (1976): On products of nonnegative matrices. Math. Proc. Cambridge Phil. Soc. 79, 521-530 Harary, F., Lipstein, B., Styan, G. (1979): A matrix approach to nonstationary chains. Oper. Res. 18, 1168-1181 Hartfiel, D.J. (1973): Bounds on eigenvalues and eigenvectors of a nonnegative matrix which involve a measure of irreducibility, SIAM J. Appl. Math. 24, 83-85 Hartfiel, D.J. (1974a): On infinite products of nonnegative matrices. SIAM J. Appl. Math. 26,297-301 Hartfiel, D.J. (1974b): A study of convex sets of stochastic matrices induced by probability vectors. Pacific J. of Math. 52,405-418 Hartfiel, D.J. (1975a): Results on measures of irreducibility and full indecomposibility. Trans. Amer. Math. Soc. 202, 357-368 Hartfiel, D.J. (1975b): Two theorems generalizing the mean transition probability results in the theory of Markov chains. Linear Algebra Appl. 11, 181-187 Hartfiel, D.J. (1980): Concerning the solution set to A x = b where P <_ A < Q and p ~ b _< q. Numer. Math. 35,355-359 Hartfiel, D.J. (1981a): On the limit set of stochastic products xA1 ... Ak. Proc. Amer. Math. Soc. 81,201-206 Hartfiel, D.J. (1981b): A general theory of measures for nonnegative matrices. Linear Algebra Appl. 35, 21 35 Hartfiel, D.J. (1983): Stochastic eigenvectors for qualitative stochastic matrices. Disc. Math. 43, 191-197 Hartfiel, D.J. (1984): An ergodic result for the limit of a sequence of substochastic products xA1 . . . A t . Linear and Multilinear Algebra 15, 193-205 Hartfiel, D.J. (1985): On the solution to x'(t) = A ( t ) x ( t ) over all A ( t ) where P < A ( t ) <_ Q. J. Math. Anal. Appl. 108, 230-240 Hartfiel, D.J. (1987): Computing limits of convex sets of distribution vectors x A 1 . . . A~. J. Statist. Comput. Simul. 38, 1-15 Hartfiel, D.J. (1991a): Component bounds on Markov set-chain limiting sets. J. Statist. Comput. Simul. 38, 15-24 Hartfiel, D.J. (1991b): Sequential limits in Markov set-chains. J. Appl. Prob. 28, 910-913
MARKOV-SET CHAINS
127
Hartfiel, D.J. (1993a): Results on limiting sets of Markov set-chains. Linear Algebra Apph 195, 155-163 Hartfiel, D.J. (1993b): Cyclic Markov set-chains. J. Statist. Comput. Simul. 46, 145-167 Hartfiel, D.J. (1994a): Homogeneous Markov chains with bounded transition matrix. J. Appl. Prob. 31,362-372 Hartfiel, D.J. (1994b): Lumping Markov set-chains. Stoch. Proc. Appl. 50, 275-279 Hartfiel, D.J. (1995): Indeterminate Markov systems. Appl. Math. Comput. 68, 1-9 Hartfiel, D.J., Seneta, E. (1994): On the theory of Markov set-chains. Advances in Applied Probability 26, 947-964 Iosifescu, M. (1980): Finite Markov processes and their applications. John Wiley, New York Isaacson, D., Madsen, R., (1976): Markov chains: theory and applications. John Wiley, New York Isaacson, D., Luecke, G.R. (1978): Strongly ergodic Markov chains and rates of convergence using spectral conditions. Stoch. Proc. Apph 7, 113-121 Jeffries, C. (1974): Qualitative stability and digraphs in model ecosystem. Ecology 55, 1415-1419 Jeffries, C., Van den Driessche, P. (1991): Qualitative stability and solvability of difference equations. Linear and MuItilinear Algebra 30, 275-282. Johnson, C.R. (ed.) (1990): Matrix theory and applications. Amer. Math. Soc., Providence, Rhode Island Johnson, C., Bru, R. (1990): The spectral radius of a product of nonnegative matrices. Linear Algebra Appl. 141,227-240 Karl, W.C. (1984): S.M. Thesis. Department of Electrical Engineering, Massachusetts Institute of Technology Karl, W.C., Greschak, J.P., Verghese, G.C. (1984): Comments on a necessary and sufficient condition for the stability of interval matrices. Int. J. Control 39, 849-851 Kaszkurewicz, E., Bhaga, A. (1989): Qualitative stability of discrete-time systems. Linear Algebra Appl. 117, 65-71 Kelly, P.J., Weiss, M.L. (1979): Geometry and convexity. John Wiley, New York Kemeny, J.G., Snell, J.S., Knapp, A.W. (1966): Denumerable Markov chains. D. Van Nostrand, Princeton, New Jersey Kharitonov, V.L. (1978): Asymptotic stability of an equilibrium position of a family of systems of linear differential equations. Differenejalnyje Uravnenija 14, 2086-2088 Lancaster, K. (1962): The scope of qualitative economics. R. Econ. Studies 29, 99-123 Lancaster, K. (1964): Partitionable systems and qualitative economics. R. Econ. Studies 31, 69-72
128
BIBLIOGRAPHY
Lancaster, K. (1965): The theory of qualitative linear systems. Econometrica 33, 395-408 Leizarowitz, A. (1992): On infinite products of stochastic matrices. Linear Algebra Appl. 168, 189-219 Levins, R. (1974): Problems of signed digraphs in ecological theory. Ecosystem Analysis and Prediction. SIAM. 264-377 Lewin, M. (1971): On nonnegative matrices. Pacific J. of Math. 36, 753-759 Loeve, M. (1963): Probability theory, 3rd ed. D. Van Nostrand, Princeton, New Jersey Loewy, R., Shiev, D.R., Johnson, C.R. (1991): Perron eigenvectors and the symmetric transportation polytope. Linear Algebra Appl. 150, 139-155 Logofet, D. (1992): Matrices and graphs: stability problems in mathematical ecology. CRC Press, Boca Raton, Florida Marcus, M., Minc, H., (1964): A survey of matrix theory and matrix inequalities. Allyn and Bacon Inc., Boston Markov, A.A. (1906): Extensions of the law of large numbers to dependent quantities [in Russian]. Izn. Fiz.-Matern. Obsch. Kazan University, (2nd ser) 15, 135-156 Masami, K., Sun, J., Hasaka, M., Huang, Y. (1977): Controlled Markov setchains with discounting. Optimization methods for mathematical systems with uncertainty. Sfirikaisekikemky~ho KSkyfiroka 978, 136-146 (Japanese (Kyoto, 1996)) Masami, K., Sun, J., Hasaka, M., Huang, Y. (1998): Controlled Markov set chains with discounting. J. Appl. Prob., to appear Maybee, J., Quirk, J. (1969): Qualitative problems in matrix theory. SIAM Review 11, 30-51 Mehta, M.L. (1991): Random matrices, 2nd ed. Academic Press, Boston Meyer, C.D., Plemmons, R.J. (1977): Convergent powers of a matrix with applications to iterative methods for singular systems. SIAM J. Numer. Anal. 14, 699-705 Minc, H. (1988): Nonnegative matrices. John Wiley, New York Mukherjea, A. (1979): Limit theorems: stochastic matrices, ergodic Markov chains, and measures on semigroups. Probabilistic Analysis and Related Topics, vol. 2. Academic Press, New York, pp. 143-203 Mukherjea, A., Chaudhuri, R. (1981): Convergence of nonhomogeneous stochastic chains II. Math. Proc. Phil. Soc. 90, 167-182 Neumaier, A. (1990): Interval methods for systems of equations. Cambridge University Press, Cambridge Ostrowski, A. (1973): Solutions of equations in Euclidean and Banach spaces. Academic Press, New York Paz, A. (1965): Definite and quasidefinite sets of stochastic matrices. Proc. Amer. Math. Soc. 16, 634-641 Paz, A. (1971): Introduction to probabilistic automata. Academic Press, New York
MARKO V-SET CHAINS
129
Prais, S.J. (1955): Measuring social mobility. J. Roy. Statist. Soc. 118, 56-66 Preparata, F.P., Shamos, M.I. (1985): Computational geometry, an introduction. Springer-Verlag, Berlin-Heidelberg-New York Pullman, N.J. (1966): Infinite products of substochastic matrices. Pacific J. 16, 537-544 Pullman, N.J., Styan, G.P.H. (1973): The convergence of Markov chains with nonstationary transition probabilities and constant causative matrix. Stoch. Proc. Appl. 1,279-285 Quirk, J., Ruppert, R. (1965): Qualitative economics and the stability of equilibrium. R. Econ. Studies 32,311-326 Redheffer, R., Walter, W. (1984): Solution of the stability problem for a class of generalized prey-predator systems. J. Diff. Eq. 52, 245-263 Rhodius, A. (1989): About almost scrambling stochastic matrices. Linear Algebra Appl. 126, 79-86 Rhodius, A. (1997): On the maximum of ergodic coefficients, the Dobrushin ergodicity coefficients, and products of stochastic matrices. Linear Algebra Appl. 253, 141-154 Rota, G.C., Strang, W.G. (1960): A note on the joint spectral radii. Indag. Math. 22, 379-381 Rothblum, U.G. (1981): Sensitivity growth analysis and multiplicative systems. I. The dynamic approach. SIAM J. Alg. Disc. Meth. 2, 25-34 Rothblum, U.G., Tan, C-P. (1985): Upper bounds on the maximum modules of subdominant eigenvalues of nonnegative matrices. Linear Algebra Appl. 66, 45-86 Samuelson, P.A. (1955): Foundations of economic analysis. Harvard Univ. Press, Cambridge, Massachusetts Schneider, H. (1977): The concepts of irreducibility and full indecomposability of a matrix in the works of Frobenious, KSnig, and Markov. Linear Algebra Appl. 18, 139-162 Schwarz, S. (1964): On the structure of the semigroup of stochastic matrices. A Magyar Tudomanyos Akdemia Mathematilmi Kutato Intelzetenek Kozlemenyei IX, 297-311 Schwartz, S. (1973): The semigroup of full indecomposable relations and Hall relations. Czech. Math. 23, 151-163 Seneta, E. (1973): On this historical development of the theory of finite inhomogeneous Markov chains. Proc. Cambridge Phil. Soc. 74, 507-513 Seneta, E. (1979): Coefficients of ergodicity: structure and applications. Adv. Appl. Probab. 11,576-590 Seneta, E. (1981): Non-negative matrices and Markov chains, 2nd ed. SpringerVerlag, Berlin-Heidelberg-New York Seneta, E. (1983): Spectrum localization by ergodicity coefficients for stochastic matrices. Linear and Multilinear Algebra 14, 343-347 Seneta, E. (1984a): Explicit forms of ergodicity coefficients and spectral localization. Linear Algebra Appl. 60, 187-197
130
BIBLIOGRAPHY
Seneta, E. (1984b): On the limiting set of non-negative matrix products. Statist. Prob. Letters 2, 159-163 Seneta, E. (1988a): Sensitivity to perturbation of the stationary distribution: some refinements. Linear Algebra Appl. 108, 121-126 Seneta, E. (1988b): Perturbation of the stationary distribution measured by ergodic coefficient. Advances in Appl. Prob. 20, 228-230 Seneta, E. (1993a): Application of ergodicity coefficients to homogeneous Markov chains. Contemporary Math. 149, 189-199 Seneta, E. (1993b): Explicit forms for ergodicity coefficients of stochastic matrices. Linear Algebra Appl. 191,245-252 Seneta, E. (1993c): Sensitivity of finite Markov chains under perturbation. Statist. Prob. Letters 17, 163-168 Seneta, E. (1996): Markov and the birth of chain dependence. International Statistical Review (3)64, 255-263 Seneta, E., Tan, C.P. (1984): The Euclidean and Frobenious ergodicity coefficients and spectrum localization. Bull. Malaysian Math Soc. 7, 1-7 Smith, R.A. (1966): Sufficient conditions for stability of a solution of difference equations. Duke Math. J. 33, 725-734 Tan, C-P. (1982): A functional form for a particular coefficient of ergodicity. J. Appl. Prob. 19, 858-863 Tan, C-P. (1983): Coefficients of ergodicity with respect to vector norms. J. Appl. Prob. 20, 277-387 Trench, W.F. (1995): Invertibility convergent infinite products of matrices, with applications to difference equations. Comput. Math. Appl. 30, 39-46 Tsaklidis, G., Vassilisiou, P.-C.C. (1990): Infinite products of matrices with some negative elements and row sums equal to one. Linear Algebra Appl. 127, 41-58 Tyson, J. (1975): Classification of instabilities in chemical reaction systems. J. Chem. Phys. 62, 1010-1015 Wesselkamper, T.C. (1982): Computer program schemata and the processes they generate. IEEE Trans. on Software Engineering Se-8, 412-419 Wolfowitz, J. (1963): Products of indecomposable, aperiodic, stochastic matrices. Proc. Amer. Soc. 14, 733-737 Zenger, C. (1972): A comparison of some bounds for the non-trivial eigenvalues of stochastic matrices. Numer. Math. 19, 209-211
Index backward product, Bpr 21 canonical form 12, 91 Cauchy's theorem 121 Cesaro set sum 75 Chebyshev's Inequality 121 classification of states ergodic 92 transient 92 coefficient of ergodicity definition 7- 4 properties 5 uniform 60 compact sets 115 component bounds 50
H 5O Lk 52 Hk 52 L ~ 65 Hoo 65 convex sets 116 distance 5(F, ~1) 20
5(a, C)
100
5(X,Y) 119 d(X, Y) 119 forward product, Fp,r 19 Fubini's theorem 121 graph of T, G(T) 8 Hausdorff metric 119 Hi-Lo method 48 initial distribution set, So 35 intervals [p,q] 28 [P, Q] 34 tight 30 column tight 35, 66
irreducible matrix 13 lumping 84 Markov chains 14 Markov set chain definition 35 cyclic 72 types 93 nonhomogeneous Markov chains 14 norm 115 Poisson WLLN 121 polytope 117 primitive matrix 13 regular matrix 16 scrambling definition 4 product 63 integer 63 spread, S(w) 5, 7 stochastic matrix 3 stochastic matrix sets 121 20 ~t~ 34
M k 35 M ~ 64 ~ 82 stochastic vector sets A,~ 28 Sk 36 S~ 62 Ck 75 C~ 78 transition set 35 WLLN 121
Printing: Weihert-Druck GmbH, Darmstadt Binding: Buchbinderei SchLffer, Griinstadt
