This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
f strongly" means f I -› 0. In this case, we write f = s-lim fn . For operators on X, strong convergence T := s-limT„ means T f = s-urn T„ f for all f E X. We shall assume that the t.p.f. P defines a linear operator on X into itself given by
Ilf, -
(P f)(x) := f P(x,dy)f(y) Vf E X, x E X. x As usual, Pn denotes the n-step transition function, which is given recursively by Pn(x, B) = f P x
1 (x, dy)P(y, B),
n = 1, 2, .. . ,
where P°(x, •) is the Dirac measure at x; we also write P° := I, the identity operator. For n = 1, 2, ... , let
sn := I ± p + . . . ± P 1 ,
(8.3.1)
so that we can write (8.2.2) as P( n ) = n —l Sn . The following definition is an adaptation of the concept of canonical triplet introduced by Yushkevich [136] (see also [35] or [58]) for Markov control processes.
Definition 8.3.1. Let f be a given function in X. A pair (g, h) of functions g and h in X is said to be an f-canonical pair if S„ f + Pnh = ng + h
Vn = 1, 2, • • • •
(8.3.2)
106
Chapter 8. The Poisson Equation
It turns out that (8.3.2) is equivalent to the multichain P.E. (8.2.1) in the following sense.
Theorem 8.3.2. (g, h) is an f -canonical pair if and only if (g, h) is a solution to the multichain P.E. with charge f. Proof. (-) Let (g, h) be an f-canonical pair. Then, with n = 1, (8.3.2) yields (8.2.1)(b). Now, to obtain (8.2.1)(a), apply P to both sides of (8.2.1)(b) to get P2 h = Pg + Ph— Pf, and, on the other hand, note that (8.3.2) with n = 2 yields P2 h = 2g -Fh—f—Pf. The last two equations give (8.2.1)(a) since they imply Pg—g=g+h—Ph—f= 0, where the latter equality comes from (8.2.1)(b). (-) Conversely, suppose that (g, h) satisfies (8.2.1). Then g = P g implies g = Pk g for all k = 0, 1, ... , and, therefore, n-1 pk g
ng =-
_ sng
Vn = 1,2,... .
(8.3.3)
k=0
Now write (8.2.1)(b) as h = (f — g)+ Ph and iterate to obtain h = Sn ( f — g) + Ph = Sn f — ng + Ph
[by (8.3.3)],
which is the same as (8.3.2).
El
Although Theorem 8.3.2 is quite straightforward, it has important consequences. In particular, we will derive from it additional necessary and/or sufficient conditions for the existence of solutions to the multichain P.E. Recall that the norm of an operator T from X into itself is defined as
IITII := sup IIIT f II I f c x,11/11
1 1,
and that T is said to be power-bounded if there is a constant Al > 0 such that IIT1 < M for all n = 0, 1, ... .
Corollary 8.3.3. Let (g, h) be an f -canonical pair. Then: (a) g = s-lim P(n) g n
(b) If Pm hln —> 0 (poin,twise or strongly), then limP (n) f =limP(n) g = g (pointwise or strongly, respectively). (c) If P is power-bounded, then supn llSn(f — 9)11 <00.
8.3. Canonical Pairs
107
Proof. Part (a) follows from (8.3.3). Moreover, from (8.3.3) and (8.3.2) we get Sn (f — g) = h — Pnh.
(8.3.4)
This yields (b) [using (a)], and also (c) since 1lS ri (f — g)11 5_ (1+ M)111111, where M is such that 11P n ii < M for all n = 0, 1, ... . Ill Remark 8.3.4. (a) Observe that if (8.2.1)(b) holds, so that f — g = (I — P)h, then we can also obtain (8.3.4) from the general expression:
Pk (I — P) = I — P n Vn = 1,2 . .. .
Sn (I — P)
(8.3.5)
k=0
(b) The hypotheses in parts (b) and (c) of Corollary 8.3.3 obviously hold if P is a contraction operator, i.e., IIPII < 1. This is the case if, for instance, X = B(X) is the Banach space of bounded measurable functions on (X, B) with the sup norm, or if X = L p (p) with 1 < p < oo and it a P-invariant p.m., i.e., it is a (not necessarily unique) p.m. such that it(B) = f it(dx)P(x, B) x
VB E B.
(8.3.6)
(Recall (2.2.12).) The following theorem gives another characterization of a solution to (8.2.1).
Theorem 8.3.5. Let f,g and h be functions in X, and suppose that: (a) P is bounded (i.e., 11-13 11 < M for some constant M), and (b) Pa /n —* 0 strongly. Then the two following assertions are equivalent. (i) (g, h) is the unique solution of the P.E. (8.2.1) for which s-lim P (n) h = 0.
(8.3.7)
(ii) g = s-lim P(n) g = s-lim P(n) f , and N n-1
h = s-lim Tv-
E E Pk (f — g) = s-lim n=1 k=0
N
Sn(f
—
g).
(8.3.8)
n=1
Proof. (i) = (ii). If (i) holds, then the first condition in (ii) follows from Corollary 8.3.3(b). On the other hand, by (8.3.4), 1
N n=1
1
N
VN = 1,2,.... n=1
Hence, (8.3.8) follows from (8.3.9) and (8.3.7).
(8.3.9)
Chapter 8. The Poisson Equation
108
(ii) = (i). If g = s-lim P(n) g = s-lim P(n) f , then (8.2.1)(a) holds [since, by assumption (a), we can interchange P and s-lim], and also s-lim P(n ) (f - g) = 0.
(8.3.10)
To prove (8.2.1)(b) first note that, by (8.3.5), n-1
(I - P)
E Pk (f - g) = (I -
Pn )( f
- g).
(8.3.11)
k=0
Therefore, applying (I - P) to both sides of (8.3.8) and using assumption (a) again, we get (I - P)h =
n-1
1 S-111-11 —
N
(I -
P)
n=1
E pk (f - g) k=0
( f - g) - s- lim —
N
N ‘-d n=1
Pn (f - g)
[by (8.3.10)],
= f - g
i.e., (8.2.1)(b) holds. Hence, the pair (g, h) is a solution to (8.2.1); it only remains to show that it is unique. Before doing this, let us note that (8.3.8) and (8.3.9) together imply (8.3.7). Now let (gi, h1) and (g2, h2) be two f-canonical pairs satisfying the conditions in (ii). Then gi = s-lim P(n) f = g2 ,
i.e., gi = g2 =: g.
(8.3.12)
Furthermore, since (I - P)h, = f -g for i = 1, 2, the function u = h i - h2 satisfies (I - P)u = 0, and, therefore, u = Pk u for all k = 0, 1,..., which implies u = s-lim P(n) u = s-lim P(n ) hi - s-lim P( n) h2 = 0 [by ( 8 . 3 . 7)], LI
i.e., hi = h2. This completes the proof.
In the following section we show that the results in Theorem 8.3.5, as well as those mentioned in the following Remark 8.3.6 are valid in a more general context. Remark 8.3.6. If the state space X is a finite set, in which case the t.p.f. P is a square matrix, it is well-known [11, 35, 73, 101, 111] that the limiting matrix n-1
iim P(n) = 11111n-
E
Pk (componentwise)
(8.3.13)
k=0
exists (compare (8.3.13) with (2.3.7), (2.3.8), and (5.2.3), for instance), and that / - P + H is nonsingular; its inverse Z := (I - P +11) -1
(8.3.14)
8.3. Canonical Pairs
109
is called the fundamental matrix associated to P. Moreover, the matrix
(P — 11) k (I — H)
(8.3.15)
H = (I — P + 11)-1 (I — H) = Z(/ — H)
(8.3.16)
satisfies and is called the deviation matrix associated to P (or the Drazin inverse of ./— P); P — II is sometimes called the approach matrix [127]. The above facts are also true if X is a countable set. What we wish to remark is that the solution pair (g, h) in Theorem 8.3.5(i), (ii) is precisely
g =11f,
and
h = H f.
(8.3.17)
In Theorem 8.4.7 we show that (8.3.16) and (8.3.17) hold in a much more general setting.
Remark 8.3.7. The choice of the underlying space X is important. For instance, consider the countable set X = {1, 2, ... } with the discrete topology, and let X be the Banach space of bounded functions on X with the supremum norm 7.4 := sup x 1u(x)j. Further, let {g(x), x E X}, be a probability distribution on X, that is, q(x) > 0 for all x and Ex q(x) = 1, which is assumed to have a finite "mean value" q := x q(x) < Do, x
E
and let P(x, y) __ P(x, {y}) be the t.p.f. given by
P(x,x — 1) := 1 Vx > 2, and P(1, y) := q(y) Vy > 1. Finally, consider the Poisson Equation (8.2.1) with charge f E X defined by f(1) := 1-4, and f(x) := 1 Vx > 2. Then one can easily check that (8.2.1) has a solution (h, g) with g(.) -_T., 0 and
h(x) = f(1) + x — 1 Vx E X.
(8.3.18)
In fact, except for an additive constant, any solution h to (8.2.1) is of the form (8.3.18), which is not a bounded function. In other words, the charge f is in X and the P.E. is "solvable", but the solution is not in X. This kind of situation can often be remedied by suitably enlarging the space X. For example, consider the weighted norm Ilul w := Ilu/w = suplu(x)lw(x) -1 , x where w(x) = x for all x E X, and let Xw be the Banach space of functions u on X with finite w-norm, i.e., Iluilw < oo. It is clear that Xw contains X (in fact,
110
Chapter 8. The Poisson Equation
since w > 1, we have IluIl u, < Hull < co if u is bounded) and, moreover, the function h in (8.3.18) belongs to Xli, That is, the P.E. does not have a solution in X, but it does in XiD . Moreover, it is straighforward to check that P is still a bounded linear operator on X„) . Under some additional assumption on the distribution q (for instance, if q has a finite "moment generating function"), one may show that P is in fact power-bounded.
8.4 The Cesaro-Averages Approach It follows from the results in §8.3 that the existence of solutions to the multichain P.E. (or, equivalently, the existence of canonical pairs) is closely connected with the limiting behavior of the Cesar° averages P(') := n -1 ,572 . In this section we obtain necessary and/or sufficient conditions for the existence of such solutions by identifying the limits of P(n). To do this we shall use the mean ergodic theorem of Yosida and Kakutani [135] (see also [133] or [34]), which requires the following assumption.
Assumption 8.4.1. X is a Banach space and P maps X into itself. Moreover, (a) Pr' In -- 0 strongly, and (b) sup.11P (n) i <00. Note that (a) and (b) trivially hold if P is power-bounded, in particular, if P is a contraction [see Remark 8.3.4(b)]. Now let A(P) be the set of functions whose Cesar° averages converge, i.e., A(P) := {f E XI P ( n) f
converges strongly as n -4
The set A(P) is nonempty [it contains (at least) the constant functions] and the following mean ergodic theorem (for a proof see the above-mentioned references) provides a description of it. We use the notation Ker := kernel (or null) space and Ran := range. Moreover, Y denotes the closure of a set Y.
Theorem 8.4.2. Suppose that Assumption 8.4.1 holds. Then A(P) is the closed linear manifold given by A(P) = Ker(/ - P) @ Ran(/ - P).
(8.4.1)
Furthermore, the operator H that maps f 1--> fif := s-lim P ( h') f is a projection on A(P) (i.e., ii 2 = H) with range and kernel Ran(II) = Ker(/ - P), and
Ker(II) = Ran(/ - P),
(8.4.2)
and satisfies HP = PH = 112 = H. If, in addition, X is reflexive, then P is mean ergodic, i.e., A(P) = X.
(8.4.3)
8.4. The Cesaro-Averages Approach
111
Remark 8.4.3. We have already seen special cases of Theorem 8.4.2. For instance, if we take the "projection" (or idempotent) operator H as the linear mapping H in Lemma 5.2.4, where X = Li (p), then (5.2.5) follows from (8.4.3). See also Theorem 5.2.2(c),(d), and Theorem 2.3.5. On the other hand, concerning the last statement in Theorem 8.4.2, the condition that X be reflexive is sufficient but not necessary for P to be mean ergodic. For instance, suppose that p, is a P-invariant p.m., and let X = L i (p). Then X is not reflexive, but as shown by the MET, Theorem 2.3.5, A(P) = X. We shall now derive necessary conditions for the existence of solutions to (8.2.1); sufficient conditions are considered in the second half of this section. Let (g, h) be a solution of the multichain P.E. with charge f, and suppose that Assumption 8.4.1 holds. Then, by (8.4.1) and (8.2.1), g and f are both in A(P), and in fact, by Corollary 8.3.3(a), (b),
g = II f .
(8.4.4)
Hence, in particular, we may rewrite (8.2.1)(b) as (/ — P)h = (/ — II)f.
(8.4.5)
On the other hand, by (8.4.4), g is necessarily unique but this needs not be the case for h because (g,h+ Hit') is also a solution of the multichain P.E. for any h' in A(P); indeed, by (8.4.3), we have (I — P)1111' = 0, and so
(I — P)(h + IIh') = (I — P)h = (I — H)/ . For h to be unique it suffices, for instance, to add the constraint IIh = 0.
(8.4.6)
In other words, as in the last part of the proof of Theorem 8.3.5, we have:
Proposition 8.4.4. If (g, h 1 ) and (g, h2) are two solutions of the multichain P.E. and h1 , h2 satisfy (8.4.6), then h1 = h2. Proof. From (8.4.5), (/ — P)(hi — h2) = 0, i.e. u := h1 — h2 is in Ker(/ — P) = Ran(H) [by (8.4.2)]. This implies u = Hu, so that, by (8.4.6), u = h1 — h2 = 0. 0 Finally, we shall use (8.3.5) to re-state Corollary 8.3.3 in the context of this section. Actually, the following proposition almost amounts to a trivial remark but it is important because it gives an idea of the rate of convergence of P(n) f to IIf .
Proposition 8.4.5. Suppose that Assumption 8.4.1 holds. If f and h satisfy (8.4.5), with f in A(P), then P(n) f — Ilf = —1 (I — Pn)h --4 0
strongly.
(8.4.7)
112
Chapter 8. The Poisson Equation
If in addition P is power-bounded, then 1P(n) .f – [If II
(8.4.8)
MIlhIl/n
for some constant M. Proof. From (8.4.5) and (8.3.5), S1 n (I – II) f = Sn (I – P)h = (I – Pn)h.
Since S, (/ – H) = Sn – nil, (8.4.7) — hence (8.4.8)
follows.
111
Remark 8.4.6. The convergence in (8.4.8) can be greatly improved by imposing suitable assumptions on the t.p.f. P. In particular, there is a large variety of
conditions ensuring a geometric rate of convergence (see §4.3.3), that is, there exists a constant 0 <8 < 1 such that Pri i – it(i)1 < cfin V f E X, and n = 0, 1, . . . ,
(8.4.9)
where j( f)) :=ff dp = II f for some P-invariant probability measure it, and c is a constant (that may depend on f). See [22, 46, 51, 64, 70, 103]. Note that if (8.4.9) holds, then the operator H o introduced below is defined for all f E X. To state sufficient conditions for the existence of solutions to the multichain P.E., let us consider two operators H o and H defined as Hof := s-
lim
7j -4
n-1
y-: ( p k - IT) f =
Do
E(Pk - 11 )f,
k=0
k=0
00
and
N n-1
1 H f := s-I\Ern Kr E cx)
(pk
_ ii)f.
(8.4.10)
n=1 k=0
The domain of H is Dom(H) := { f E A(P)I the limit in (8.4 .10) exists}, and similarly for Ho . If a sequence {hn } in X converges strongly to h then so does the sequence of averages n -1 E nk=01 hk. Thus, taking ,
n-1
hn :=
E(pk
_ II)f,
k=0
we see that H is an extension of Ho , that is, Dom(H0 ) c Dom(H) and H f = Ho f
V f E Dom(1/0 ).
In fact, these remarks were intended mainly to illustrate the relation between (8.4.9) and Ho , whence between (8.4.9) and H. But what we are really interested in is the following result, which in particular gives the precise domain and range of H. [Compare Theorem 8.4.7 and Remark 8.3.6, noting that (P – II) k (I – II) = Pk – H for all k = 0, 1, ... , by (8.4.3).]
113
8.4. The Cesaro-Averages Approach
Theorem 8.4.7. Under Assumption 8.4.1 we have: (a) f is in Dom(H) if and only if the pair (g, h) given by g = II/ and N E E( pk _ ri) f h :-= H f = s- lim N-1 n-1
N —,oc
(8.4.11)
n=1 k=0
is the unique solution of (8.4.4)-(8.4.6). (b) Dom(H) = Ran(H) e (I - P) Ker(II) [= Ker(/ - P) ED (I - P)Ran(/ - P), by
(8.4.2)]. (c) Ran(H) = Ker(II) [= Ran(/ - P), by (8.4.2)]. (d) The restriction of H to Ran(H) = Ker(II), call it Z, is the inverse of I-P+II, i.e., Z f = (I - P + II) -l f
Vf E Ran(H) 1= Ker(II) by (c)j;
(8.4.12)
hence, the function h in (8.4.11) can be written as h = H f = Z(I - II)f V f E Dom(H).
(8.4.13)
(a) (). Suppose that f is in Dom(H), and let g := II f and h := H f. Then observing that [by (8.4.3)] Proof.
pk (1- ____ ll) f
( 1-' 7-4
ii) f Vk = 0,1,...,
we see that the function h = H f in (8.4.11) is the same as the function h in (8.3.8) with g = Ilf. Hence the implication "" in (a) follows from the implication "(ii)(i)" in Theorem 8.3.5. Similarly, the converse follows from "(i)(ii)" in Theorem 8.3.5. (b) Let f be in Dom(H) and let g := II f and h := H f. Then, by part (a), (8.4.5) and (8.4.6) yield f = II f + (I - P)h,
with h
E
Ker(II);
hence f
is in Ran(H) e (i- - P) Ker(II).
(8.4.14)
Now suppose that f satisfies (8.4.14). Then there are functions f i in A(P) and f2 in Ker(H) such that f =I-Ifi+ (I - P)f2. Obviously [by (8.4.3)], Hfi is in Dom(H) and HIIf i = 0. Moreover [by (8.4.3) again] (p k
_ "i)(I _ p) _
pk ____ pk-1-1 ,
and so H(I - P)f2 -= f2. Summarizing, if f satisfies (8.4.14), then f is in Dom(H) and H f = f2.
114
Chapter 8. The Poisson Equation
(c) Suppose h = H f is in Ran(H). Then since H is bounded (by Assumption 8.4.1), we can interchange H and s-urn in (8.4.10), which combined with (8.4.3) yields 1-11/ = IIHf = 0, i.e., h E Ker(H), (8.4.15) so that Ran(H) c Ker(II). Now to prove that Ker(H) c Ran(H), let h be in Ker(II) and let f := (I - P)h. Then, by (8.4.3) and (8.3.5), n-1
n-1
E(pk _ {)f k=0
.
E (pk _ 11) (I — P)h = (I - Pn)h.
(8.4.16)
k=0
Thus, (8.4.10) yields H f = h - Ilh = h, i.e., h is in Ran(H). (d) Suppose that f is in Ran(H) = Ker(II) and let h =- H f . Then, by (a), from (8.4.5)-(8.4.6) we get (I - P)h = (I - II) f = f and Hh = 0, so that (I - P + II)h = (I - P)h + Hit = f,
i.e., (I - P +II)H = I on Ker(I1). A similar argument shows that H(/-P+II) = I on Ker(H). Finally, to prove (8.4.13), let f be any function in Dom(H). Then part (a) yields that h = H f satisfies (8.4.5)-(8.4.6), so that (I - P + II)Hf = (I - P)h +Hh = (I - II) f ,
and (8.4.13) follows.
n
Remark 8.4.8. (a) Arguing as in (8.4.16) it can be shown that H(I - P)f = (I - II) f
Vf E Dom(H),
so that in addition to (8.4.13) we have H (I - P + II) f = H (I - P) f = (I - II) f .
(b) The operator Ho defined above is sometimes called the ergodic potential of P, and H1 := Ez° 0 Pk is called the potential [108, 112, 127]. In the following section we study the a-potential (or resolvent) R,„ in (8.5.1).
8.5 The Abelian Approach For every 0
Ra := (1. — aP)
—
E akpk k=0
.
(8.5.1)
8.5. The Abelian Approach
115
The close connection between the limits of the Cesar() averages P(n ) [see (8.3.1)] as n -- oo and the limits of the "Abelian means" (1 — as aI 1 has been widely exploited in a variety of contexts. In this section we use that connection to study the multichain P.E. (8.2.1). First, to ensure that, among other things, R, is well defined we let X be as in §8.4 [i.e., X is a Banach space] and suppose:
Assumption 8.5.1. P is power-bounded, i.e., there is a constant M such that liPnii < M for all n = 0,1, .... Assumption 8.5.1 obviously holds, in particular, if P is a contraction [see Remark 8.3.4(b)]. On the other hand, note that Assumption 8.5.1 implies Assumption 8.4.1 and, therefore, all the results of §8.4 are valid. Moreover, (8.5.2)
sup 11( 1 — a)R, 11 5_ M (< oo),
0
which, since P is positive (f > 0 = P f > 0), is in fact equivalent to the condition supn IIP (n)Il < oo in Assumption 8.4.1(b) (see, for instance, [36]). In addition, a well known result [19, 117] yields that, under Assumption 8.5.1, the set A(P) in (8.4.1) is the same as the set of all f E X for which the strong limit s-lim„-ti (1 — ce)R,f exists, and in fact coincides with TIf:
s- lim P (n ) f = IV = s-lim(1 — a).1=1„f n—too
at1
V f E A(P).
(8.5.3)
(See Remark 8.5.4, below.) We next extend to our present context a result in [20], which turns out to be related to Proposition 8.4.5.
Proposition 8.5.2. Suppose that Assumption 8.5.1 holds, and let f be a function in X . Then n-1
n-1
(a) an(Pn—/)Rf =
Ea k )
(1—a)R,f
( k =0 (b) For every n = 1, 2, . . . , the limit
—
E
a
k pk r J
Va E (0, 1), n= 1, 2, . . .
k=0
G n f := s-lim(Pn — .1)Ra f all
(8.5.4)
exists if and only if f is in A(P), in which case [by (a) and (8.5.3)] Gnf = n • IV
—
Snf
Vn = 1, 2 , • " ,
(8.5.5)
so that s- lim G n f In = 0; Ti —+00
(c) Given f in A(P), a function h satisfies the P.E. (8.4.5) if and only if Gn f = Pnh — h
Vn = 1,2,... .
(8.5.6)
Chapter 8. The Poisson Equation
116
Proof. (a) From (8.5.1), we get R, = I + aPR,, which iterated yields n-1
R, =
E
Vn = 1,2,..., 0 < a < 1.
a k Pk ± an Pn Ra k=0
Substracting an Ra to both sides of this equation and recalling that n-1 1 — an = (1 k=0
we obtain (a). (b) In (a) take both lim inf and lirn sup as a i 1 to get s-lim inf (Pn — I)R, f = n • s-lim inf (1 - a)R, f - S n f all
all
< n • s-lim sup(1 - a)R, f - Sn f all
=
s-lim sup(Pn - I)R, f . all
Thus, in view of (8.5.3), we conclude that (8.5.4)-(8.5.5) hold if and only if f is in A(P). Finally, (c) follows from (8.5.5) and the equality (8.4.7) [or (8.3.2) with g = 0 HP. With n = 1, Proposition 8.5.2(a) gives the following expression for (/ - P)Ra = R,(I - P):
a R,(I - P) f = f - (1 - a)R, f
Vf E X.
(8.5.7)
f E A(P).
(8.5.8)
Therefore, from (8.5.3) [or from (8.5.5) with Ti = 1], s-lim R,(I - P) f = (I - II) f all
if
We will now use (8.5.7) and (8.5.8) to obtain a result similar to Theorem 8.4.7 but using R, instead of P(n) . First, following [19] (see also [118]) let Po denote the restriction of P to A(P) and define J f := s-lim R, f , all
whenever the limit exists.
117
8.5. The Abelian Approach
Theorem 8.5.3. Under Assumption 8.5.1:
(a) Dom(J) = Ran(/ — Po ), and Ran(J) = Ker(II). (b) f is in Dom(J) if and only if (8.5.9)
h = s-lim Ra f [= J f] all
is the unique solution of the Poisson equation (g = 0 and) (I — P)h = f
IIh ----- O.
with
(8.5.10)
(c) f is in Dom(J) if and only if the pair (g, h) with g = IIf and h as in (8.5.9) is the unique solution of the multichain P.E. (8.2.1) satisfying IIh = 0. (d) The restriction of J to Ran(J) = Ker(II) is the inverse of (I — P o ), i.e.,
Vf E Ker(H). (8.5.11)
(I — P)J f = f = J(I — P)f
Proof. (a) To show that Ran(/—Po) c Dom(J), let f be a function in Ran(/ — Po). Then there is a function h in A(P) such that f = (I — P)h, and (8.5.8) gives that f is Dom(J) and J f = s-lim Ra (I — P)h = (I — II)h. (8.5.12)
Suppose now that f is in Dom(J), and let J f = h, i.e., s-lim R a f = h.
(8.5.13)
all
Then multiplying the latter equality by (1 — a) we obtain, by (8.5.3), II f = s-lim(1 — a) R a f = s-lim(1 — a) • h = all
all
0.
This in turn yields [by (8.5.8) — also recall that P is bounded] f = s-lim R a j — P)f = (I — P) - J f = (I — P)h.
(8.5.14)
all
Finally, by (8.5.13), h = s-urn R, f all
= s-iiM R a j — P)h all
[by (8.5.14)],
which, by (8.5.12), yields h = h — IIh; hence, IIh = 0.
(8.5.15)
Thus, from (8.5.14) and (8.5.15) we conclude that f is in Ran(/ — P0 ). This completes the proof of Dom(J) = Ran(/ — 130).
Chapter 8. The Poisson Equation
118
On the other hand, note that (8.5.13) and (8.5.15) imply Ran(J) c Ker(II). Now let h be in Ker(H), and let f := (I — P)h. Then (8.5.8) yields J f = s-lim Ra (I — P)h = (I — II)h = h, ail
i.e., h is in Ran(J). In other words, Ker(H) c Ran(J). (b) This follows from (a). Namely, the implication "" follows from (8.5.14) follows from (8.5.12). The uniqueness comes and (8.5.15), and the converse from Proposition 8.4.4. (c) () If f is in Dom(J), it follows from (8.5.5)—(8.5.6) and (8.3.2) that (IIf, h) is an f-canonical pair. Thus, by Theorem 8.3.2 and Proposition 8.4.4, is the unique solution of (8.2.1) satisfying (8.4.6). (IIf, , () The converse follows from part (b): In (8.5.9) and (8.5.10), replace f by f - Ilf• (d) The first equality in (8.5.11) follows from (8.5.9)—(8.5.10), and the second follows from (8.5.8) [or (8.5.12)]. Remark 8.5.4. An informal way of arriving at the second equality in (8.5.3) as well as at (8.5.16) J f = s-lim Ra f ail
in (8.5.9) is as follows. In (8.5.1) replace Pk by H + (Pk — H) to get 00
Ra =
k (pk H) 1—
a
(8.5.17)
k=0
This immediately suggest the second equality in (8.5.3) if Pk — H converges to zero sufficiently fast, for example, as in (8.4.9). In particular, using k-1
for k = 1, 2, . . j=o elementary calculations on (8.5.17) give H
Ra =
+
1/0 — (1 —
1— a
a)
00
00
E
E
k=0
n=-k+1
_
(8.5.18)
E(Pk _ n).
(8.5.19)
where, as in §8.4, n-1
OC
Ho
(pk k=0
- n) =
s- lirn
n—>oo
k=0
Thus, if the sequence in (8.5.19) converges, (8.5.18) yields the second equality in (8.5.3) as well as (8.5.16) with J f = Ho f for f in Ker(II). These calculations can be made precise even in the uniform (instead of the strong) operator topology; see e.g. [77, 95, 100, 118]. Finally, note that expressions such as (8.5.18) can be used to obtain, for instance, rates of convergence of (1 — a)Ra to H as a T 1.
119
8.6. Notes
8.6 Notes We have presented a detailed analysis of the problem of existence of solutions to the multichain P.E. (8.2.1) in a very general context, using the concept of canonical pairs (§8.3), Cesar° averages P( n) (§8.4), and a-potentials R, (§8.5). There remains, however, a lot to be done. In particular, some important open problems are the following. 1. To develop approximation schemes to solve (8.2.1), perhaps iteratively. If the state space X is finite, there are available some computational algorithms — see the references in Remark 8.3.6. For the case of general X, some of the techniques in [19, 97, 118, 120] and their references might be useful. 2. Theorem 8.4.2 provides an "ergodic decomposition" of the domain X of P, expressing X as the (disjoint) union of A(P) and its complement X\A(P). This, in turn, is used to obtain the domain and range of the operators H, H, J, and so on. It would be interesting to obtain a more precise form of these sets for the particular classes of Banach spaces X (for instance, X an L p space) used in probability applications. On the other hand, as shown in §4.5 and §5.3, for instance, there are well-known ergodic decompositions of the MC's state space X. These typically give more information on the MC's probabilistic behaviour and, therefore, it would be important to relate them to the different sets appearing in Theorems 8.4.2, 8.4.7 and 8.5.3. In other words, the basic question is to find the relation (if any) between an ergodic decomposition of X and one of X. 3. An important issue in some Markovian control problems is to determine the validity of a Laurent expansion of the form [cf. (8.5.18)] 00
/7„, = 111(1 — a) + E(—arHn,
(8.6.1)
n=0
where H is the "deviation operator" in (8.4.10) [see also (8.4.13) and (8.3.15)]. To our knowledge, (8.6.1) has only been studied under very strong assumptions [111, 129, 137], and it turns out to be related to a sequence of "nested" Poisson equations. 4. From Theorem 5.2.2 we know that, under appropriate hypotheses, the projection operator H in Theorem 8.4.2 is determined by a t.p.f. I1(x, B), which has nice implications. It would be useful to obtain a similar result for (1 — a)R, [see (8.5.3)]. 5. In the unichain case, there is a well-known relation between the existence of solutions to the Poisson equation and probabilistic conditions such as the Doeblin and Harris conditions [96, 112]. What can be said about this relation in the multichain case?
120
Chapter 8. The Poisson Equation
6. The results in this paper are for the "discrete-time" Poisson equation (8.2.1), in the strong topology. What are the corresponding results for the continuous-time case (when P — I is replaced by the generator of a continuous-time Markov semigroup Pt , t > 0) and/or in the uniform or weak (operator) topologies? What can be said about the "adjoint" Poisson equation v = vP, it(I — P) = 0— v, for a given "charge" 0 in X*? (See [19, 95, 97, 108, 117, 118, 119, 120, 100].) Most of the results in this chapter are fom Hernandez-Lerma and Lasserre [68].
Chapter 9
Strong and Uniform Ergodicity 9.1 Introduction In this chapter we introduce the notions of strong ergodicity and uniform ergodicity of MCs. We study how these notions relate to the concept of "stability" of a transition kernel and to the solvability of the Poisson equation (8.2.1). For a MC with a t.p.f. P that admits an invariant p.m. ii, the original notion of ergodicity refers to the property (2.4.5). This property occurs if ii is ergodic (Definition 2.4.1) and states a memoryless property of the MC in the long-run, in the sense that the limit of P(n) does not depend on the initial state x, for p-a.a. x E X. However, this memoryless property is true only in a proper subset of X. For the strong and the uniform ergodicity studied in this chapter, the memoryless property holds for any initial state x E X. Moreover, uniformly ergodic MCs have an interesting "stability" property under sufficiently small perturbations of the t.p.f. P. We will see that the strong ergodicity and the uniform ergodicity properties are indeed very strong. For instance, strong ergodicity implies (and in fact is equivalent to saying) that the MC is positive Harris recurrent. Some authors state strong and uniform ergodicity in terms of the asymptotic property of the sequence {Pm } of n-step transition probabilities (see, e.g., Meyn and Tweedie [103], Nummelin [1081), whereas some others (e.g., Kartashov [78], or Revuz [112]) use the same definition but in terms of the sequence of Cesaro averages {PM} rather than {Pn}. We choose the latter definition mainly because the former, in terms of {Pn}, implicitly assumes an additional "aperiodicity" property of the MC, not easy to check in general, whereas the strong ergodicity property does not require this aperiodicity assumption. Moreover, the definition of uniform ergodicity in terms of {Pri} is not really appropriate because, with this definition, it turns out that a uniformly ergodic MC in fact inherits (with no further assumption) the stronger geometric ergodicity property introduced in Definition 4.3.5.
122
Chapter 9. Strong and Uniform Ergodicity
Also in this chapter we introduce the notions of weak ergodicity and weak uniform ergodicity for a MC on a LCS metric space. These definitions are essentially the same as those of strong and uniform ergodicity, except that we look at the t.p.f. P as a linear operator acting on Cb(X) only (rather than on B(X)). The conditions for weak and weak uniform ergodicity are, of course, easier to verify. It turns out, however, that the latter weaker notions yield basically the same properties. For instance, compare Propositions 9.2.4 and 9.3.4, and Theorems 9.2.7 and 9.3.5.
9.2 Strong and Uniform Ergodicity 9.2.1 Notation Given a Banach space (X, I1.11), we denote by L(X) the Banach space of bounded linear operators on X into itself with the induced operator norm 11.11, which is defined as for Q E L(X). (9.2.1) IIQII := sup 11Qx11 11x115_1 We shall consider, in particular, the following two cases, in which (X, B) is a given measurable space: • X = M(X), the Banach space of finite signed measures on (X, B), with the total variation norm (1.4.3). Moreover, we shall denote by 11.11 the total variation norm or any norm equivalent to it, as in (1.4.4), for instance. • X --= B(X) the Banach space of bounded measurable functions on X, with the supremum (or sup) norm VII = supx If(x)1. In these cases, it will be clear from the context whether 11.11 refers to the total variation norm or to the sup norm. Consider now a MC „ = { t } on a measurable space (X, B) with t.p.f. P. We may look at P as a linear operator on M(X), that is P E L(M(X)), defining v '—f vP as in (2.2.12), i.e., v P (B) = f P(x, B) v(dx)
VI/
E M(X).
(9.2.2)
Similarly, defining f i— P f as in (2.3.6), i.e., P f (x) = f f (y)P(x, dy)
V f E B(X),
(9.2.3)
we may view P as a linear operator in L(B(X)). For notational ease, we write P for both the operator P E L(M(X)) in (9.2.2) and P E L(B(X)) in (9.2.3). Hence, by (9.2.1),
IIPII = sup{Ilv-P11 114 = supaPP1111/11
1 , v E M(X)} 1, f E B(X)I-
(9.2.4)
9.2. Strong and Uniform Ergodicity
123
From (9.2.2) we have IvP(B)I
VB E B,
f P(x,B) Iv
which yields that 11vPii operator. Similarly, by (9.2.3),
or IIP _< 1. Thus P E L(M(X)) is a contraction
IPi(x)I
11f1
f li(Y)i P(x,dY)
and so P E L(B(X)) is a contraction operator, i.e., 11PM< 1. Hence, by the recursive definition of the n-step transition probabilities Pn (see §2.2), we can see that < 1 Vn > 0. (9.2.5) This means that in either case (9.2.2) or (9.2.3), P is power-bounded, and so the techniques used in Chapter 8 are applicable in our present context. Also note that Assumption 8.4.1 holds for both X = M(X) and X = B(X).
9.2.2 Ergodicity Throughout this chapter we assume that (X, 13) is a separable measurable space and that P has an invariant p.m. tt (that is, p = AP). As usual, P(n) denotes the n-step expected occupation measures in (2.3.6).
Definition 9.2.1. Let
be a MC on X with t.p.f. P, and assume that P has an invariant p.m. p. The MC e. is said to be (a) strongly ergodic if ex E X;
11 P(n) (X1')
(9.2.6)
(b) uniformly ergodic if sup 11P ( n ) (x, .) —M TEx
0.
(9.2.7)
Let H := 1 0 p, be the linear operator on M(X) defined by v
v11 = v(1 0 tt) := v(X) 1u V v E M(X),
so that H E L(M(X)). We also define H := 1 0 tt on B(X) as f
Hf = (1
it)f(x) := f fd,u Vx E X,
so that H E L(B(X)). Hence, as for P, we shall use the same notation for H as an operator in L(M(X)) and in L(B(X)).
124
Chapter 9. Strong and Uniform Ergodicity
In either case, that is, viewing H as an operator in L(M(X)) or in L(B(X)), (9.2.7) is equivalent to (9.2.8) lirn 11 P(n) - rut = 0 7/ -p00
for the corresponding operator norm on B(X) or on M(X). Note that if . is strongly ergodic, then p, is necessarily the unique invariant p.m. for P. Therefore, by Proposition 2.4.3, p is ergodic (Definition 2.4.1), and so Proposition 2.4.2 yields the p-a.e. ergodicity property (2.4.5). However, (9.2.6) (and a fortiori (9.2.7) and (9.2.8)) is stronger than (2.4.5) in the sense that it yields
P(n) f (x) - f f dp
for all x E X and f E B(X).
(9.2.9)
We also have the following
Proposition 9.2.2. A MC is strongly ergodic if and only if it is P.H.R. Proof. The proof is a direct consequence of Theorem 4.3.2.
0
On the other hand, we have the following characterization of uniform ergodicity.
Proposition 9.2.3. (Kartashov [78, Theor. 1.3]). The MC , is uniformly ergodic if and only if the operator (I - P + H) E L(M(X)) has a bounded inverse in L(M(X)), where I E L(M(X)) is the identity operator. Moreover, in Proposition 9.2.3 we may replace M(X) with B(X), which yields the following.
Proposition 9.2.4. The MC „ is uniformly ergodic if and only if the operator (I - P + H) E L(B(X)) has a bounded inverse in L(B(X)). Proof. We proceed as in Kartashov [78, p. 8]. For each n > 1, the bounded linear operator Qn : B(X) -> B(X) defined by n
Q n := H + n -1 E(k(P (k) - H)) lc=-1
satisfies
Qn(i - P -EH) = (I - P ±H)Qn
I _ p(n+1) ± H ± n -i i.
(9.2.10)
9.2. Strong and Uniform Ergodicity
125
Therefore, if . is uniformly ergodic, choosing n such that 1 P(n+ 1) - Hil < 1 ensures that the operator (/ - P ( n+ 1) + H + n -1 /) has a bounded inverse and commutes with Q„ and (/ - P + H). Multiplying both sides of (9.2.10) by Zn := (/ - P(n+1) ± H + n -11) -1 yields that the linear operator Z E L(B(X)), defined by Z := (I - P +11)-1 = Z„Q„ = is well-defined and bounded. Conversely, let (/ - P + H) : B(X) -+ B(X) have a bounded inverse Z E L(B(X)). Observe that for all n = 1, 2, ... , (I _ p ± ri) (p(n) — H)
Hence, by (9.2.5), 11(/ - P + II)(P (n) — 11)11 follows that
< 2n -1 for all n = 1, 2, ... , and so it
11P (n) — 11 11 = 11Z (I — P + II) (P (n) - 11 )11
—11)11 2 n -1
1141.
Thus 11 P(n) — fill —÷ 0 as n -4 oo. By Definition 9.2.1(b), t. is uniformly ergodic. 0
9.2.3 Strong Stability Now consider Kartashov's [78] notion of a strongly stable MC.
Definition 9.2.5. A MC . with t.p.f. P is said to be strongly stable in the norm M.M if there is some € > 0 and a neighborhood N(P,€) := {(2 I IIQ — PM < €} of P in L(M(X)) such that (a) Every stochastic kernel Q E N(P, c) has a unique invariant p.m. v = vQ. (b) For every sequence {Qn } of stochastic kernels in N(P, e) for which MQ n — PH ---* 0, one has Ilv, - liM -4 0, where lin is the invariant p.m. for Q„, and p, is the invariant p.m. for P. In fact, this definition is also valid for other norms than (1.4.3), provided that they satisfy some conditions (see Kartashov [78, page 5]). It turns out that the uniformly ergodic MCs satisfy the strong stability property, and conversely.
Theorem 9.2.6. (Kartashov [78, Theor. 1.6]). A MC is strongly stable in the norm 11.11 if and only if it is uniformly ergodic. Thus, uniform ergodicity is equivalent to a strong form of stability, that is, under a sufficiently small perturbation of its t.p.f., a uniformly ergodic MC preserves its "ergodic" properties.
126
Chapter 9. Strong and Uniform Ergodicity
9.2.4 The Link with the Poisson Equation We may use Theorem 9.2.6 to relate strong and uniform ergodicity to the solvability of the Poisson Equation (P.E.) in (8.2.1) with ga- constant, i.e., (9.2.11)
g (I — P)h = f. Indeed, we have the following.
Theorem 9.2.7. (a) The MC e, is strongly ergodic if for every B
E B, there exist
a scalar gB and a measurable function hB that solve the P.E. (9.2.11) with charge i.e., f (9.2.12) g (I — P)h = 11B, and such that PnhB/n ---+ 0 pointwise. (b) The MC e, is uniformly ergodic if and only if for every "charge" f B(X), the P.E. (9.2.11) has a solution (gf,hf) ER x B(X).
E
Proof. (a) Choose an arbitrary B c B, and let (gB , h B) be a solution of the P.E. (9.2.12) such that PnhB/n —+ 0 pointwise as n —+ oo. From (8.3.2) with f = "LB we obtain gB + PnhB (x)In = hB(x)/n+ P(n) (X, B) Taking limit in (9.2.13) as n
(9.2.13)
co yields
P( n ) (x,B)
gB
From Theorem 4.3.1 it follows that
II P(n) (X1
Vx E X.
A(*)
V x E X.
is P.H.R., and thus, by Theorem 4.3.2, —+0
Vx E
X,
where p, is the unique invariant p.m. for P. This proves (9.2.6), and so is strongly ergodic. (b) The only if part. From Proposition 9.2.4 the operator I— P +II : B(X) B(X) has a bounded inverse Z E L(B(X)). It is easy to check that for any given f E B(X), the pair (gf,hf) E R x B(X) with gf := f fdp, and hf := Zf solves the P.E. (9.2.11). The if part. Choose an arbitrary charge f e B(X), and assume that the P.E. (9.2.11) has a solution (gf ,hf ) E R X B(X). As in the proof of (a), it follows that is P.H.R. with a unique invariant p.m. p. Next, the solution hf is unique in B(X) up to a constant because if h'f is another solution in B(X), then (I — P)(h f — hif ) = 0. Therefore, by Theorem 4.2.14, the bounded P-harmonic function hf — hif is constant. Let Bo(X) := {f E B(X)I f fdp, = 0} c B(X).
9.3. Weak and Weak Uniform Ergodicity
127
We thus have (I - P)B(X) = Bo(X) and I - P: Bo(X) -> Bo(X) is one-to-one and onto. By the Banach Theorem (see e.g. [34, Theor. 2, §II 2.1.2]), I - P has a bounded inverse Q: Bo(X) Bo(X). Proceeding as in Revuz [112, P. 204], n-1
n-1
pifflfII
11nl
= 11 71-1
i=0
E Piu - rif)11 i=0 n-1
= lin - 1 E PT/ - P)Q(f
11 /)
i=0
<
4n' 1Q11
Hence sup IIP (n) / Tin -3 0 or, equivalently, II P(n)
-4 0 1
which is also equivalent to uniform ergodicity (see (9.2.8)).
El
Remark 9.2.8. (a) Theorem 9.2.7(b) is slightly different from Theorem 3.5(ii) in Revuz [112] where it is stated that uniform ergodicity is equivalent to : (al) there is an invariant p.m. u, (a2) the bounded harmonic functions are constant, and (a3) (I - P)B(X) = B o (X). (b) Given a weight function w : X -> [1, oo), one can also get a weighted version of Theorem 9.2.7 with the spaces B„(X), M ill (X) defined as B(X) = {f
sup IA4
xEX
in lieu of B(X), M(X), with
Mph,
as in (4.3.6).
9.3 Weak and Weak Uniform Ergodicity Strong ergodicity is indeed a strong property because, as we already noted in Proposition 9.2.2, it is equivalent to P.H.R. Of course, uniform ergodicity is an even stronger property. However, as many MCs with a unique invariant p.m. are not P.H.R., one may wonder whether there exists a notion weaker than strong ergodicity. It turns out that when X is a LCS metric space, replacing the convergence in total variation norm in (9.2.6) with weak convergence leads to the following concept.
128
Chapter 9. Strong and Uniform Ergodicity
9.3.1 Weak Ergodicity Definition 9.3.1. Let , be a MC on a LCS metric space X, with t.p.f. P. Assume that P has an invariant p.m. it. Then e. is said to be weakly ergodic if Vx E X, where "" denotes the weak convergence of p.m. 's (see Definition
(9.3.1) 1.4.10).
Clearly, (9.3.1) is a lot weaker than (9.2.6). (See (1.4.10).) Of course, if (9.3.1) holds, the "time average = space average" ergodicity property (2.4.5) is still true for arbitrary f E Li (p), since it is the unique invariant p.m. (Recall that a weakly convergent sequence of p.m.'s has a unique limiting measure.) However, instead of the p-a.e. convergence in (2.4.5), under (9.3.1) we have for all x E X, and f E Cb(X).
Pen) f(x) --4 f f dp
(9.3.2)
We have seen in §5.2 and §5.3 that for a MC . on a LCS metric space, with a t.p.f. P that admits an invariant p.m., there is a Yosida decomposition of X into ergodic classes such that in each ergodic class E there is a unique (ergodic) invariant p.m. co and a set A c E of full cp-measure, such that p(n)( x,
.)
ep
Vx E A.
In other words, in a LCS metric space, the restriction of a MC to its ergodic classes is weakly ergodic, with no further assumption than the existence of an invariant p.m. The next result provides a sufficient condition for weak ergodicity.
Proposition 9.3.2. Let e. be a MC on a LCS metric space X, with t.p.f. P. Assume that (a) P is weak-Feller. (b) P admits a unique invariant p.m. p. (c) There exist a measurable function V : X ---4 IR+ and a moment function f : X —> 111 + (Definition 1.4.14) such that PV (x) < V (x) — f (x) -I- 1 Then . is weakly ergodic.
Vx E X.
(9.3.3)
9.3. Weak and Weak Uniform Ergodicity
129
Proof. Iterating (9.3.3) we obtain
n-1
> pnv +
Pk
f — n,
k=0
which gives
n-1 V>
E Pk f —
n Vn > 1,
k=0
because V is nonnegative. Hence, sup f P (n ) (x, dy) f (y) < 1 + V(x)
Vx E X.
As f is a moment, from Proposition 1.4.15 we have that the sequence IP(n ) (x,.)} is tight for every x E X [see Definition 1.4.14 Now choose an arbitrary x E X. By Prohorov's Theorem 1.4.12, there is a p.m. px E M(X)+ and a subsequence {nk} of {n}, such that /3(71 )(x, .) = ,a x. The latter convergence and (a), together with Proposition 7.2.2, yield that fix P = lix. Thus, by the uniqueness of the invariant p.m. p in (b), px = p for all x E X. Therefore, as x E X was arbitrary, the whole sequence {PM (x, .)} converges to p, that is, (9.3.1) holds. 0 We next introduce the notion of weak uniform ergodicity.
9.3.2 Weak Uniform Ergodicity Definition 9.3.3. Let e. be a MC on a LCS metric space X, with a weak-Feller t.p.f. P. Assume that P has an invariant p.m. p. Then e. is said to be weakly uniformly ergodic if sup
sup I P( n ) f(x) —
0
as n
oo.
(9.3.4)
fEcb(x);11f11<1 xEx
In other words, for a weakly uniformly ergodic MC, the weak convergence in (9.3.1) is uniform in x E X and f in the unit ball of Cb(X). Recall that Cb (X) equipped with the sup norm is a Banach space. Thus, as P is weak-Feller, we can consider P and H = 1 0 p as linear operators on Ch(X) (that is, P and H are in L(Cb (X))) with the corresponding operator norm 11.11b on L(Cb(X)), 11 (211b :=
sup
sup
{fEcb(x)difil
Kg(x)1
for Q E L(Cb(X)).
This norm is denoted by111Q1 b to avoid confusion with the norm Then (9.3.4) is equivalent to
11 -P(n)
rqb —>
0
as n
oo.
We have the following analogue of Proposition 9.2.4
1Q11
in (9.2.4). (9.3.5)
Chapter 9. Strong and Uniform Ergodicity
130
Proposition 9.3.4. The MC . is weakly uniformly ergodic if and only if the operator (I P + H) E L(Cb(X)) has a bounded inverse. —
Proof. The proof is a verbatim copy of the proof of Proposition 9.2.4 with the 0 norm 11.11b in lieu of 11.11. We also have an analogue of Theorem 9.2.7.
Theorem 9.3.5. Let e. be a MC on a LCS metric space, with a weak-Feller t.p.f. P. Assume that P has a unique invariant p.m. p. (a) e, is weakly ergodic if for every f E Cb(X), there is a scalar g f and a measurable function hf such that (g f, h f) solves the P.E. (9.2.11), and in addition Pnh f In —> 0 pointwise as n —+ oo. (b) e, is weakly uniformly ergodic if and only if for every f E Cb (X), the P.E. (9.2.11) has a solution (g f, h f) in R X Cb(X). Proof. (a) The proof is similar to that of Proposition 9.2.7(a). Fix an arbitrary f E Cb(X). Iterating (9.2.11) yields PO') f (x) —* g1
Vx E
X.
(9.3.6)
As f E Cb(X) was arbitrary, it follows that P(n) (x, .) = v for some v E M(X). Hence, as P is weak-Feller, by Proposition 7.2.2 it follows that v is an invariant p.m. for P. Moreover, from the uniqueness of p,, we have v = p. Thus, P(n ) (x, .) = p for p all x E X, that is, e, is weakly ergodic. Moreover, from (9.3.6) and P(n) (x, .) for all x E X, it follows that gf = f fdp= fIf. (b) Only if part. From Proposition 9.3.4, the operator I—P+II has a bounded inverse Z E L(Cb(X)). Given f E Cb(X), the pair (gf,hf) with gf := Hf and h f := Z f E L(Cb(X)) solves the P.E. (9.2.11). If part. Choose an arbitrary f E Cb(X) and let (g f,h f) E R x Cb(X) be a solution to (9.2.11). By (a), e, is weakly ergodic and g f = fIf . It also follows that the continuous bounded harmonic functions are constant. Indeed, let fo E Cb(X) be such that Pfo = fo (and hence, P(n)f0 = fo for all n > 0). As , is weakly ergodic, we have fo(X) = nlinI Pen) fo (x) = fdp, fo
Vx E X.
Thus, let (g f , h f) and (g"f , W.f.) be two solutions of the Poisson equation, h'f ) = 0, that is, the function with h f, lef E Cb(X). It follows that (I P)(h f (h f — h'f ) E Cb(X) is harmonic, hence constant. Let Coo (X) C Cb(X) be the subspace of Ch(X) defined by —
—
Coo (X) := If E Cb(X) I Ilf = 01. Then, using the weak-Feller property, we have (I — P)Cb(X) = Coo (X), and the linear operator (I P) E L(Cb(X)) is one-to-one and onto from Coo (X) into —
9.4. Notes
131
Coo (X). By the Banach Theorem (see, e.g., [34, Theor. 2, §11.2.1.2]), / — P has a bounded inverse Q : Coo (X) —) Coo(X). The rest of the proof mimics that of the if part of Proposition 9.2.7, with the norm M.Mb in lieu of 11.11. LII
Example 9.3.6. Consider the following example from Borovkov [15]. Let X := [0, 1] and let e. be the MC
=
+ 'I't
(mod 1),
t = 0, 1,
,
(9.3.7)
where {V} is a sequence of i.i.d. random variables with Prob(O t = a) = p =1 — Prob(6 = 0), with a > 0 irrational, say a = -VI This MC can be interpreted as a summation process on a circle of unit length, and we have P(x,.)
ji
Vx E X,
(9.3.8)
where i is the Lebesgue measure on [0,1], and it is the unique invariant p.m. for P (see Borovkov [15, Example 1, p. 544]). Of course, (9.3.8) yields that
P(n) (x,.) =
Vx E X,
(9.3.9)
that is, the MC is weakly ergodic (see Definition 9.3.1). In addition, the support of P( ') (x,.) is finite for every n > 0 and x E X. Hence, as in (6.2.4)—(6.2.7), the convergence in (9.3.9) can only be weak and not in total variation, which implies that the MC is not strongly ergodic.
9.4 Notes Some definitions and results of this chapter are from Kartashov [78]. On the other hand, the link with the Poisson equation and the notions of weak ergodicity and weak uniform ergodicity are from the authors. As already mentioned, several authors (see, e.g., Meyn and Tweedie [103], Nummelin [108]) define the strong ergodicity and the uniform ergodicity of a MC, using the convergence in the total variation norm of the n-step probabilities /31 (x,.) (rather than the Cesar° averages P(n)(x,.)) to /..t. Revuz [112] considers both definitions with Pn and P("), respectively. For the former, with Pm, he requires P to be Harris recurrent, aperiodic and quasi-compact, and the latter P is Harris recurrent and quasi-compact (see [112, Theor. 3.4, 3.5, pp. 203-204]), where P is said to be quasi-compact if there exists a sequence {U n } of compact operators on B(X) such that —+ 0 as n oo. Moreover, P is quasicompact if and only if there exists a compact operator U and an integer n o such that Pn° — U M < 1 (see Revuz [112, Prop. 3.3, p. 202]).
Part III
Existence and Approximation of Invariant Probability Measures
Chapter 10
Existence and Uniqueness of Invariant Probability Measures 10.1 Introduction and Statement of the Problems A critical assumption for many results of previous chapters is that a MC admits at least one invariant p.m. In this chapter we investigate the issue of existence of those invariant p.m.'s. Namely, we consider a MC on a measurable space (X, B), with t.p.f. P and we present necessary and sufficient conditions for •
P. Existence of invariant p.m.'s for P;
•
P;. Existence of strictly positive invariant p.m.'s; and
•
P. Existence and uniqueness of strictly positive invariant p.m.'s.
By a strictly positive invariant p.m. in problems 13'; and P;, we mean an invariant p.m. it on B such that p(G) > 0 for any open set G E B, and, therefore, we shall consider PI and 7-31; in the case in which X is a topological space with Borel a-algebra B. In fact, some of our results require X to be a metric space. Finding an invariant p.m. for P is essentially equivalent to finding a solution it to the linear system
1.113 = it with
1i(X) = 1 and tt E M(X) +
in the Banach space M(X) of finite signed measures on X (see §1.2.1).
(10.1.1)
Chapter 10. Existence of Invariant Probability Measures
136
In addition to (10.1.1) we also consider the constraint ii
^ (Po
(10.1.2)
5_ IN,
(10.1.3)
and/or
where (po , /Po are nontrivial measures in M(X)±. When v;i 0 in (10.1.2) is strictly positive, that is, p0 (G) > 0 for every open set G E B, we obtain conditions for problems 71); and P. On the other hand, finding conditions for existence of an invariant p.m. that satisfies (10.1.3) might be useful to determine the existence of a suitably majorized invariant p.m., for instance, with a "tail" property. Finally, we also consider the problems Pi* for MCs in a restricted setting, namely when X is a LCS metric space and the t.p.f. P satisfies the weak-Feller property (see Definition 4.4.2). In this case, we can derive existence conditions without invoking constraints of the form (10.1.2), as we do in the general case. These results are presented in §10.4. The approach. Our approach to problems P7 is in fact very straightforward. The main idea is to write the problems P: as "linear equations" in appropriate Banach spaces, and then use a Generalized Farkas Theorem of Craven and Koliha [25, Theor. 2] to obtain necessary and sufficient conditions for the corresponding linear equations to have a solution. The main technical difficulty is to check whether a certain set is weakly closed, for which we use the Alaoglu (or Banach-Alaoglu-Bourbaki) theorem (see Lemma 1.3.2). We could in principle use alternative approaches to linear equations (see [25, 56]), but the present approach has the advantage that the resulting existence and uniqueness criteria resemble Lyapunov (or Foster-Lyapunov) criteria, usually found in related results. The results for problems P i* are presented in §10.3, §10.4 and §10.5. As some of the proofs are rather technical, for ease of exposition they are postponed to §10.7, after some technical preliminaries in §10.6.
10.2 Notation and Definitions Let (X, B) be a measurable space, and e, a MC on X with t.p.f. P. Let B(X) be the Banach space of real-valued bounded measurable functions on X, with the supremum norm f II = supx 1 f (x) I. As was already noted in §1.3, the spaces M(X) and B(X) form a dual pair (M(X), B(X)) of vector spaces with the bilinear form (IL u):= f u dL
V,u, E M(X), u E B(X).
(10.2.1)
10.2. Notation and Definitions
137
As in §9.2, we use the same "P" to denote the mapping f 1-> P f on B(X) defined by (9.2.3) (or (2.3.6)) and the mapping v i- vP on M(X) defined by (9.2.2) (or (2.2.12)). From Remark 2.3.7(13) (see also §9.2), P is a positive contraction and also a Markov operator. A signed measure p, in M(X) is said to be a fixed point of P if it is Pinvariant, i.e., ,u,P = p. The problem of finding an invariant p.m. for P is basically equivalent to that of finding a nontrivial fixed point of P. Indeed, let p E M(X) be a fixed point of P, and let {D, DC} be the Hahn-Jordan decomposition of p. Denote by p+ (B) := p,(B n D) and p - (B) := p(B n Dc) the positive and negative parts of ,u,, respectively. It is then clear that p, = p+ + p,- is a fixed point of P if and only if p+ and p- are invariant p.m.'s for P (after renormalisation to a p.m. if necessary). Let ba(X) be the Banach space of finitely-additive measures on B, equipped with the total variation norm. Then, ba(X):-_- B(X)* [see (1.2.4) or [34, Theor. IV.5.1]]. Let P* : ba(X) --4 ba(X) be the adjoint (or dual) of the operator P : B(X) -> B(X), that is, P* is such that: u) = (p, Pu),
Vic E ba(X), u E B(X).
(10.2.2)
As M(X) c ba(X), and in view of (2.2.12), when restricted to M(X), P* coincides with P, that is, P* p(B) = pP(B) = f p(dx) P(x, B) x
VB E B, eu, E M(X),
(10.2.3)
so that P* maps M(X) into itself, that is, P*(M(X)) c M(X). If p and v are in M(X), we denote by p, V v (resp. p, A v) the maximum (resp. minimum) of p, and v. That is, p,V v := and
1
1
2 A family K C M(X) is order-bounded from above (resp. from below) if there is some v E M(X) with p, < II (resp. v < p) for all p E K. (See [44, 69, 70, 71] for results, examples and applications of order-boundedness of measures). Now let fp, I be a bounded sequence in M(X)+, and define the order lim inf of {11,} as -
0 - lim inf pr, := n —■ DO
VA m>1 n>m
in 1
(10.2.4)
which is a (possibly trivial or unbounded) measure. Indeed, for every m > 1, the sequence {A n , n > ml C M(X) + is order-bounded from below by the trivial measure 0. The measures 71m := An>m An are well-defined, and {wi } is a nondecreasing sequence as m -> oo. Therefore, by the Vitali-Hahn-Saks theorem [see
Chapter 10. Existence of Invariant Probability Measures
138
Proposition 1.4.21, rini I (p for some, not necessarily finite, measure (p. Similarly, the order-lim sup of bin } is defined as 0 — lim sup it, := n co
A V An , m>1 n>m
(10.2.5)
which is a possibly unbounded measure, that is, not necessarily in M(X)+.
10.3 Existence Results We first consider results for problem Pr in a general measurable space (X, B) , and for problems '1::' and P;, X is a metric space. Let {P() (x, .)} be the sequence of expected occupation measures with initial state x e X, defined in (2.3.4).
10.3.1 Problem Theorem 10.3.1. Let . be a MC on X with t.p.f. P. Then the following statements are equivalent: (a) There is a measure ft E M (X) that satisfies (10.1.1) and (10.1.2) for some measure cp o E M(X)+. (b) The condition
(P — I)u < —v + s with u,v E B(X) + and s E R+
(10.3.1)
implies —
(40 o, v) + s > 0
(10.3.2)
for some measure (po e M(X)+. (c) There is a measure 7 in M(X) ± such that "ii := 0 — lim inf -yP (n) is in rt -■ 00
M(X)± , and it is nontrivial. We also have the following "majorization" version of Theorem 10.3.1.
Theorem 10.3.2. Let „ be a MC on X with t.p.f. P. Then the following statements are equivalent: (a) There is a measure au, E M (X) that satisfies (10.1.1) and (10.1.3) for some measure 00 c m(x)±. (b) The condition
(P — I)u
(10.3.3)
implies (00, v) — s > 0
(10.3.4)
for some measure O o E M(X) +. (c) There is a measure 7 in M(X) + such that -3 := 0 — iirnsup7P(n) is in M(X)+.
10.3. Existence Results
139
For a proof of Theorem 10.3.1 and Theorem 10.3.2 see §10.7 Remark 10.3.3. (a) Theorem 10.3.1 improves many previous results in that it gives necessary and sufficient conditions for the existence of invariant p.m.'s for P under no hypotheses; most of the results in the literature give only sufficient conditions for the existence of an invariant p.m. or require additional hypotheses. For instance, one usually assumes that X is a LCS metric space, and that P satisfies the weak-Feller property (see Definition 4.4.2), or even, instead of the Feller property, quite often it is required the stronger hypothesis P maps Co (X) into itself,
(10.3.5)
where Co (X) is the Banach space of bounded continuous functions that vanish at infinity, equipped with the sup-norm. [See, for instance, [7, 85, 87, 99, 103] and their references.] Some authors write (10.3.5) in the equivalent form: P satisfies the Feller property and, in addition, for every compact K C X, the function x 1-4 P(x, K) vanishes at infinity. (b) The references mentioned in (a) can be related to Theorem 10.3.1 by noting the similarity between (10.3.1) and the Lyapunov (or Foster-Lyapunov) criteria in the literature; see also (10.4.4) below. In particular, the above two theorems permit to derive a simple sufficient condition for existence of an invariant p.m. (For examples of MCs that satisfy the hypotheses in parts (a) and (b) of the following corollary, see, e.g., [70, 71] and the references therein.) Corollary 10.3.4. Let l. be a MC on X with t.p.f. P. (a) If P (n) (x, .) > coo for some x E X, some nontrivial measure (po E M(X)+ , and all n = 1, 2, . . . , then P admits an invariant p.m. (b) If P(n)(x,.) < 00 for some x E X, some measure 00 E M(X)± , and all n = 1, 2, ... , then P admits an invariant p.m. Proof. (a) We will show that the condition (10.3.1) implies (10.3.2) for the measure co o , which by Theorem 10.3.1 yields the desired conclusion. Rewrite (10.3.1) as u > Pu + v - s and iterate n times to get n-1
u > Pn u ±
E Pt v - ns. t=0
Therefore, rearranging terms and multiplying by n -1 , we obtain, for all x E X, n-i r1,-1 (Pn - pu(x) <
- n -1
E Pt v (x) + s
t=0
=
- (P(n) (x , .), v) + s,
so that with x and coo as in (a) we obtain n -l (Pn - /)u(x) < -((po,v) +
S.
140
Chapter 10. Existence of Invariant Probability Measures
Taking limit as n -4 oo and using the boundedness of u we get ((po, v) < s, that is, (10.3.2) holds. Thus the conclusion in (a) follows from Theorem 10.3.1. (b) Rewriting (10.3.3) as u > Pu — v ± s and arguing as in the proof of (a) we obtain that for all x E X n-1
n -1 (Pn — I)u(x) <
_i E pt, (x) _ s n t=0
,
(p(n)(x,
.), v) —
s.
Hence, with x and 00 as in (b), we get n -1 (Pn I)u(x) 5_ (00 ,v) — s. Taking limit as n —> oo yields (0 0 , v) — s > 0, and so (10.3.3) implies (10.3.4). Thus, the desired conclusion follows from Theorem 10.3.2. CI
10.3.2 Problem pI We now turn our attention to the existence of strictly positive invariant p.m.'s, assuming that X is a metric space. In fact, as an immediate consequence of Theorem 10.3.1 we obtain the following.
Corollary 10.3.5. Assume that X is a metric space with Borel a-algebra B, and let . be a MC with t.p.f. P. Then the following conditions are equivalent: (a) There is an invariant p.m. which is strictly positive; that is, there is a measure p E M(X) that satisfies (10.1.1) and (10.1.2) for some strictly positive measure (Po. (b) The condition (10.3.1) implies (10.3.2) for some strictly positive measure o. (c) There is a measure 7 in M(X) such that '')-, := 0— lim inf ,.),p(n) is in TI -4 00
M(X)+ , and it is strictly positive. (d) There is a measure -y in M(X) ± such that 7P(n) (B) -- aB V B E B, as n —> oo, with sup BEB aB < oo, and lim -yP( n ) (G) > 0 for every open set C E B. n-+(x)
Proof. The equivalence of (a), (b) and (c) follows directly from the proof of Theorem 10.3.1 (see §10.7.1). On the other hand, to get that (a) = (d) it suffices to take 7 := p, and aB := ,u,(B). Finally, to prove that (d) = (a), let -y, be the measure defined by 7n (B) := 7P(B)
VB E B, n = 1, 2, .. . .
10.3. Existence Results
141
If (d) holds, i.e., -y(B) aB for every B E B, by the Vitali-Hahn-Saks theorem (Proposition 1.4.2) there is some measure it E M(X)+ such that 'y71 (B)
,a(B)
VB E B,
(10.3.6)
that is, 'Yn —>u setwise, and p, is strictly positive. In addition, 'Yn/3 = 'Yn + n -1 [21 /3n -Y] •
(10.3.7)
Therefore, as P maps B(X) into itself, for every B E B we have ,a(B) = lim y(B) = n oo
lim00(7?-1, P1B) [by (10.3.7)]
fl
=
(P,P1B) [by (10.3.6)]
= so that ,aP = it, that is, it is a strictly positive invariant p.m.
El
10.3.3 Problem P1' We now turn our attention to problem 'P:3", that is, the existence of a unique strictly positive invariant p.m. We first use Theorem 10.3.1 to obtain the existence of an invariant p.m. it which is not strictly positive, that is, p,(G) = 0 for some given (fixed) open set G c B.
Corollary 10.3.6. Assume that X is a metric space with Borel o - -algebra B, and let G X be a nonempty open set. Then the following conditions are equivalent: (a) There is an invariant p.m. ,u, with p(G) = 0. (b) The condition (10.3.3) implies (10.3.4) for some measure '00 E M(X)+ such that 00(G) = 0. (c) There is a measure -y in M(X) + such that 5% := 0 — lirn sup -yP ( n) is in M(X)+ , and 5%(G) = 0. (d) There is a nontrivial measure -y in M(X) ± such that lim 7P(B) = aB V B E B, 71,-)• 00
with sup BEB aB <00, and -yP( n) (G)
0 as n
oo.
Proof. To prove the equivalence of (a), (b) and (c), it suffices to observe that the existence of an invariant p.m. ji with p,(G) = 0 is equivalent to the problem of existence of an invariant p.m. it majorized by some measure zi)c, E M(X) + with Oo(G) = 0. Then apply Theorem 10.3.2. The proof of (a) <=> (d) mimics the proof of the equivalence of (a) and (d) in Corollary 10.3.5. LI We now consider problem 1:%'; again but assuming that P satisfies the strongFeller property (Definition 4.4.2), that is, P(B(X)) c
cb (x).
(10.3.8)
(In the following two sections we replace (10.3.8) with the weak-Feller property.)
142
Chapter 10. Existence of Invariant Probability Measures
Theorem 10.3.7. Assume that X is a metric space with Borel a-algebra B, and P is strong-Feller. Then the following conditions are equivalent: (a) P has a unique invariant p.m. and it is strictly positive, or P does not have an invariant p.m. (b) For every nonempty open set G X and for every Oci E M(X) + such that Oo(G) = 0, there are functions G, VG E B(X)+ , and a scalar SG such that (P - I))11c < VG - sG and (00 ,vG )— s G <0. (c) For every nonempty open set G X and every measure -y E M(X)+, the measure 5% := 0- lim sup -yP ( n) is either unbounded or such that "y'(G) > 0. n —>
Proof. (b) (c) follows from the equivalence of (b) and (c) in Corollary 10.3.6. Moreover, from Corollary 10.3.6 again, (b) is equivalent to saying that for every open set G X, there is no invariant p.m. with u(C) = 0. Equivalently, either there is a strictly positive invariant p.m. or there is no invariant p.m.. Hence (a) (b). To complete the proof let us suppose that (b) holds. Now if (a) does not hold, then P has an invariant p.m. which is not strictly positive, which contradicts (b), or P has more than one invariant p.m. Let 4a 1 and 112 be two invariant p.m.'s with p2. Then the finite signed measure v := pi - /12 is a fixed point of P, and so are the nonnegative measures v+ and v - [see Lemma 2.2.3 or the paragraph following (10.2.1)]. Moreover, v+ and v - are both nontrivial fixed points of P. To see this, suppose, for instance, that v+ (X) = 0. Then < ,a2 , and so Remark 2.2.4 yields ,u,i = p2, which contradicts our assumption p i ,a2 . A similar argument shows that v - (X) > 0. Now, as v+ and v - are nontrivial, we may assume that they are invariant p.m.'s for P. Let {D, DC} be the Hahn-Jordan decomposition of v = v+ - v - , so that, in particular, v+(D) =1 and v - (D) = 0. Then (i) P(x,D) = 1 v+-a.e.,
and (ii) P(x,D) = 0 v - -a.e.
(10.3.9)
Indeed, by the invariance of v+ , v+(D) = f v+(dx)P(x,D), ,c which combined with v+(D) = v+(X) = 1 yields (10.3.9)(i); a similar argument gives (10.3.9)(ii). Furthermore, by (10.3.9)(i), D is v+-invariant, and thus (as in (2.4.1)), there exists an invariant set B C D such that v+ (B) = 1 and P(x, B) = 1 for all x E B; in fact, by the strong-Feller property, P(x, D) = 1 for all x in the closure B of B. Note that the complement BC of B is nonempty because otherwise B = X would imply P(x,D) =1 for all x in X, contradicting (10.3.9)(ii). Finally, we observe that v+(B c ) = 0 since BC is contained in BC and v +(BC) = 0. In other words, assuming that (a) does not hold, we have found that v+ is an invariant p.m. that vanishes on the nonempty open set BC X, which contradicts (b). Hence (b) implies (a).
10.4. Markov Chains in Locally Compact Separable Metric Spaces
143
10.4 Markov Chains in Locally Compact Separable Metric Spaces Some results in this section require Assumption 10.4.1, below, in which we use the weak-Feller property (see Definition 4.4.2).
Assumption 10.4.1. (a) X is a LCS metric space; (b) P is weak-Feller. We first state an analogue of Theorem 10.3.1(a),(b) in the present context of Assumption 10.4.1. In fact, the only thing we do is that we replace B(X) + in (10.3.1) with Cb(X) +, see (10.4.1).
Theorem 10.4.2. Let . be a MC on X with t.p.f. P. Under Assumption 10.4.1, the following statements are equivalent: (a) There is a measure it E M(X) that satisfies (10.1.1) and (10.1.2) for some measure (po E M(X)+ . (b) The condition (P — I)u < —v + s with u,v E Cb(X) + and s E111+
(10.4.1)
implies —
((P o, v ) + s > 0
(10.4.2)
for some measure (p o E M(X) + . We shall now present specialized versions of Corollary 10.3.6 and Theorem 10.3.7 for strictly positive invariant p.m.'s. As in §10.3.3, we first consider an invariant p.m. which is not strictly positive. That is, there is a measure iu, and a nonempty open set G X such that (i) p, (/ — P) = 0,
(ii) (p, 1) < 1,
(iv) (ii, fo) ?
E,
(iii) (p, 1lG) < 0, and
with it in M(X)+,
(10.4.3)
for some number E > 0 and some strictly positive function fo in Co (X)+. The reason for stating the existence of such an invariant p.m. in the form (10.4.3) will be apparent from the proof of Theorem 10.4.3. In particular, (10.4.3)(iv) ensures that p is nontrivial, that is, p(X) > 0, which combined with (10.4.3)(i)—(iii) yields that it [multiplied by 11 p(X) if necessary] is an invariant p.m. that vanishes on G. The following theorem gives necessary and sufficient conditions for the existence of a solution it in M(X) + to (10.4.3).
X be a Theorem 10.4.3. Suppose that Assumption 10.4.1 holds, and let G nonempty open set. Then the following conditions are equivalent: (a) There is a measure it E M(X) ± that satisfies (10.4.3) for some € > 0.
144
Chapter 10. Existence of Invariant Probability Measures (b) There exists some E > 0 such that the condition (P — I)u < a + (31G — -y fo , with u E Cb(X)+ and a,I3,-y > 0,
(10.4.4)
implies a > E-y.
(10.4.5)
(c) There exists x E X such that lim inf P(n) (x , G) = 0 n— ■ oo
and
lim inf P( n) fo(x) > 0. n.— oo
For a proof of Theorem 10.4.3 see §10.7. Moreover, from Theorem 10.4.3 we get the following criterion for the existence of a unique strictly positive invariant p.m.. Corollary 10.4.4. Suppose that Assumption 10.4.1 holds. Let „ be a MC on X with t.p.f. P and let f o be a strictly positive function in C o (X). If X is a LCS metric space and P is strong-Feller, the following conditions are equivalent: (a) There is no p, E M(X) ± that satisfies (10.4.3); that is, either P does not admit an invariant p.m. or, if it does, it is (unique and) strictly positive. (b) For every nonempty open set G X and every E > 0, there is a function u E Cb(X)+ and constants a,13,-y > 0 such that (P — I)u < a + 01G — -yfo
and a < E7,
(10.4.6)
or, equivalently, (P — I)u < a + 01G — fo and a < E.
(10.4.7)
(c) For every nonempty open set G X and every x E X lim inf P(n) (x , G) > 0 n--c>o
or
lim inf P(n) MX) = 0. n--4co
(10.4.8)
Proof. To obtain (10.4.7) from (10.4.6) it suffices to multiply the inequalities in (10.4.6) by 1/-y and relabel u/-y, a/-y, and 131-y as u, a and 0, respectively. The relations (a) = (b) <=> (c) follow from Theorem 10.4.3. To complete the proof let us suppose that (b) holds. Now if (a) does not hold, then either P has an invariant p.m. which is not strictly positive, which contradicts (b), or P has more than one invariant p.m.. As in the proof of Corollary 10.3.7, one uses the strong-Feller property to prove that P cannot admit two distinct invariant p.m.'s. El Remark 10.4.5. Uniqueness of invariant p.m.'s, strictly positive or not, is a tough question and, in particular, the strong-Feller property required in Corollary 10.4.4 seems to be unavoidable in our present context: Skorokhod [122] gives an example of a MC in which X is compact, P satisfies the weak-Feller property and it is topologically connected [meaning that EkP k (x, G) > 0 for any x E X and any nonempty open set G], and still it does not have a unique invariant p.m. He does obtain uniqueness results (see, for instance, [122, Theorem 2]), but under hypotheses much more restrictive than those of Corollary 10.4.4.
10.5. Other Existence Results in Locally Compact Separable Metric Spaces 145 For examples of MCs that satisfy the strong-Feller property see after Definition 4.4.2.
10.5 Other Existence Results in Locally Compact Separable Metric Spaces The existence results in §10.3 and §10.4 are stated in terms of minorizing or majorizing measures as in (10.1.2) and (10.1.3). In this section we consider a different type of existence results, using a moment function (Definition 1.4.14) and the Banach space Co(X) of bounded continuous functions on X that vanish at infinity.
10.5.1 Necessary and Sufficient Conditions We first present a set of necessary and sufficient conditions.
Theorem 10.5.1. Let be a MC on X with t.p.f. P. Let Assumption 10.4.1 hold and let fo be a fixed, strictly positive function in C o (X). Then the following four statements are equivalent: (a) P admits an invariant p.m. p E M(X). (b) For some initial distribution v E M(X) ± and some moment function f, 0 < liminf n -1 EEf(et) n—*oo
<
00.
(10.5.1)
t =o
(c) For some initial state x E X, lim inf P(n ) fo (x) > 0.
(10.5.2)
11-> (DO
(d) For some initial state x E X and some compact set K E B, lim sup P(n ) (x, K) > 0.
(10.5.3)
n oo
Theorem 10.5.1 is proved in §10.7.3. Observe that, in contrast to the moment function f in (b), the function fo in (c) is arbitrarily fixed.
10.5.2 Lyapunov Sufficient Conditions The conditions in Theorem 10.5.1 are necessary and sufficient, but they are all stated in terms of asymptotic properties of P(n) . However, we have seen in §7 a sufficient condition for existence of an invariant p.m. for a weak-Feller MC (see Theorem 7.2.4). This condition is only sufficient, but it involves only the one-step t.p.f. P and a Lyapunov function V to guess in (7.2.5).
Existence of Invariant Probability Measures
146
Namely, given an arbitrarily fixed strictly positive function fo E Co(X), one has to guess a measurable function V : X --4 R+ (not identically zero) and a scalar b> 0 such that PV (x) < V(x) - 1 + bf o (x)
Vx E X.
(10.5.4)
The Lyapunov condition (10.5.4) can also be used for other purposes. For instance, consider a MC on the real line X := R. Suppose we want to check whether there exists an invariant p.m. with an exponential tail, that is, an invariant p.m. such that
L for some positive scalar such an invariant p.m.
T.
erixi,a(dx) < oo,
The following Lyapunov condition permits to detect
Corollary 10.5.2. Let . be a weak-Feller MC on X = R. Assume that there exist positive scalars b, T and a nonn,egative measurable function V: X -- R+ such that PV(x) < V (x) - eTlxl + b Vx E X.
(10.5.5)
Then there exists an invariant p.m., and every invariant p.m. has an exponential tail. Proof. The proof mimics that of Theorem 7.2.4. Iterate (10.5.5) n times and multiply by n -1 to obtain
ro L. p(n)( x, dy ) e r1Y1 _< b + [V(x) - PnV(x)]/n,
(10.5.6)
for all x E X and n = 1, 2, .... The function x '-f eTlx 1 is a moment and, therefore, (10.5.6) and Proposition 1.4.15 yield that the sequence {P(n)(x, is tight for every x E X. Fix an arbitrary x E X. By Prohorov's Theorem 1.4.12, there is a subsequence nk and a p.m. px such that P(n ) (x, .) = ,ux and, by Proposition 7.2.2, px P = px . In addition, as x 1-4 erlxl is continuous and nonnegative, letting k -p oo, Proposition 1.5.6(a) yields f 00 00 f p(n x, dy ) elm < b, Loo e TIYI ttx(dy) < liminf k)( k-000 -00 .)}
which proves that ,u,x is an invariant p.m. with an exponential tail. Let us now consider an arbitrary invariant p.m. it for P. By Lemma 5.2.4(a), p, can be written as p(B) = f aux (B) p(dx),
B E 8,
(10.5.7)
147
10.6. Technical Preliminaries whereas, by Theorem 5.2.2(a),(b), there is a t.p.f. H such that it' = II(x,.) f elY1 p,x id-y\) and f II(x, dy)erlYI are equal Therefore, the functions x and so, by (10.5.7), f
erlYI ic(dy)
=
[f cc II(x, dy) eTlY] ,u(dx) f—00 — 00 itx (do] p(dx)
f[f 00
f
oo
bdit = b,
and it follows that has an exponential tail.
LI
Of course, Corollary 10.5.2 can be translated to MCs on a "one-dimensional" countable space, that is, X := l• • • — 2, —1, 0, 1, 2, . . . 1.
10.6 Technical Preliminaries 10.6.1 On Finitely Additive Measures We first recall some notation. Let (X, 8) be a measurable space. Let B(X) be the Banach space of bounded measurable functions on X, equipped with the sup-norm whose topological dual B(X)* ba(X) is the Banach space of finitely additive measures on B (called charges in Rao and Rao [13] and means in Revuz [112]), equipped with the total variation norm. The space M(X) of finite signed measures on X is a subspace of ba(X), which is also a Banach space with the total variation norm. A pure finitely additive measure (or a pure charge) ,u E ba(X) is an element of the space M(X) -- defined as
MPO-L :=
{A E ba(X)1A I ea
for every
E M(X)},
(10.6.1)
where A 1,u if and only if 1A1 A ji = 0 (see, e.g., Rao and Rao [13, Theor. 10.1.2, p. 240]). Moreover, every i E ba(X)+ can be decomposed as with cp E M(X) + and
E ba(X)±
n m(x)±.
(10.6.2)
(See Rao and Rao [13, Theor. 10.2.1, p. 241] .) Let P be the t.p.f. of a MC on X, viewed as an operator f Pf on B(X) (see (2.3.6)) with dual (or adjoint operator) P* : ba(X) ba(X) whose restriction to M(X) coincides with the operator v vP on M(X) defined in (2.2.12) [see (10.2.2)—(10.2.3)].
148
Existence of Invariant Probability Measures
Lemma 10.6.1. Let . be a MC on X with t.p.f. P. Let (i00,00 be nontrivial measures in M(X)+ , and let ea E ba(X)+ . (a) If it < 00, then ii is countably additive, that is, ii, is in M(X)+ . (b) If it > (po , then il is not purely finitely-additive, and pt = cp + IP with cp E M(X) + and 0 a pure nonnegative finitely-additive measure. In addition, if P* ea = iu, then c,oP = (p. Proof. (a) Let {B n } be a sequence in B such that Bn j 0. As tt(Bn) < 00(B n ) for all n = 1, 2, ... , and 00 is countably additive, it follows that ,a(B7 ) 1 0, and thus p is countably additive. (b) Let F(p) := Iv E M(X) + I v < O. Then F(p) is nonempty since (Po E 1704. From Yosida and Hewitt [134, Theor 1.23], F(p) contains a maximal element (to E M(X)+. Moreover, from (10.6.2), iu can be written as
for some nonnegative and pure finitely-additive measure V) and a maximal element (p E M(X)± of ['(p). As co is a maximal element of F(p,) it follows that co o < co. This gives the first statement in (b). Suppose now that P* it = it. Hence, as P* is a positive operator, we get Ii = P* A > P* (P = co-P. Hence, we conclude that (pP E F(p) and thus (pP < cp. The latter fact and the CI boundedness of (p imply that (pP = (p (see Remark 2.2.4).
10.6.2 A Generalized Farkas Lemma Let (X, Y) and (2, W) be two dual pairs of vector spaces (see §1.3), and A a linear map from X to Z. The adjoint of A, written A*, is defined by the relation (Ax, w) = (x, A* w) for each x E X and w E W. Further, A* maps W into 3) [i.e., A*(W) C Y] if and only if A is weakly continuous, (10.6.3) [i.e., continuous with respect to the weak topologies o- (X, y) and o- (Z, W)]; see, for instance, [25, p.984]. Lemma 10.6.2. (Craven and Koliha [25, Theor. 2]). Let (X , y) and (2,1N) be two dual pairs of (real) vector spaces, and let K be a convex cone in X with dual cone K* := {y c yl(x,y) > 0
Vx E K}
c Y.
Let A : X —> Z be a weakly continuous linear map with adjoint A* :1 / 1 1 —> y. If A(K) is weakly closed, then the following conditions are equivalent for b E Z: (a) The equation Ax = b has a solution x in K. (b) A*w E K* = (b,w) > 0.
10.7. Proofs
149
10.7 Proofs 10.7.1 Proof of Theorem 10.3.1 For technical reasons that will become apparent below, instead of trying to solve PI' in M(X) we will first consider Pi' in the larger space ba(X) D M(X) of finitely-additive measures. We begin by noting that, by (10.2.3), the condition (a) in Theorem 10.3.1 is equivalent to: There exists p E ba(X) such that (I — P*)p = 0,
u> wo ,
(it, 1) = 1,
and p E ba(X)+ .
(10.7.1)
Indeed, it is obvious that (10.1.1) and (10.1.2) imply (10.7.1) since P* ,u coincides with p,P whenever ti E M(X). Conversely, if (10.7.1) holds, then P* ,u, = p. In addition, p, can be decomposed as it = yo + 0 with yo E M(X) + and lp > 0 a pure nonnegative finitely-additive measure, that is, 7,b E M(X)' (see (10.6.2) and 10.6.1)). By Lemma 10.6.1(b), (pP = P*(p = cp and yo > yoo , so that co is a nontrivial invariant measure in M(X)+. Therefore, the p.m. (p(.)1(p(X) satisfies (10.1.1) and (10.1.2). On the other hand, introducing the "slack variable" v in M(X)+, we can see that the existence of a solution ,u to (10.7.1) is equivalent to: There is a solution (p,, v) in the convex cone K := ba(X)+ x ba(X)+ to
( i ) ( I — P* )/-1 = 0 ,
and (iii) (ii, 1) = 1.
(ii) A — v = (po,
(10.7.2)
In view of this remark, we will prove Theorem 10.3.1 by showing that (10.7.2) has a solution in K if and only if part (b) in Theorem 10.3.1 is true. To do this, we use Lemma 10.6.2 as follows. To put (10.7.2) in the context of Lemma 10.6.2 consider the dual pairs (X ,Y) and (Z, IN) with X := ba(X) x ba(X),
Y := B(X) x B(X),
Z := ba(X) x ba(X) x R,
W := B(X) x B(X)
x R.
Let A : X —> Z be the linear map A(p, v) := ((I — P*),u,, p — v, (p, 1)), and let K be the positive cone in X, i.e., K := (ba(X) x ba(X))+ = ba(X)+ x ba(X)+ . Thus, we can rewrite (10.7.2) as in part (a) of Lemma 10.6.2, i.e., A(p,v) = (0,(P0, 1) has a solution
(p, v) in
K.
(10.7.3)
Existence of Invariant Probability Measures
150
Now note that by (10.2.2), the adjoint A* of A is A* (u, v, s) = ((/ — P)u + v + s,—v), and that A* maps W into 3); hence A is weakly continuous [see (10.6.3)]. Thus, since the dual cone of K is K* = (B(X) x B(X))+ = B(X) + x B(X)+, in the present context we can write (b) in Lemma 10.6.2 as A*(u, v, s)
in
K* = ((0, (Po , 1) , (u, v, s)) = ((Po, v) + s ? 0.
(10.7.4)
Finally, replacing v by —v in (10.7.4), we see that (10.7.4) is precisely the statement "(10.3.1) implies (10.3.2)" in part (b) of Theorem 10.3.1 (when s is negative, the statement is automatically satisfied). Therefore, since we already know that A is weakly continuous, the proof of Theorem 10.3.1 will follow from Lemma 10.6.2 if we show that A(K) is weakly closed.
(10.7.5)
To prove (10.7.5), let (D,>) be a directed set, and let {(p,, v,), a E D} be a net in K such that A(u,, v,) converges to (a, b, c) E Z in the weak topology o- (Z, W), i.e.,
(i) (I _ P*) tta setwise
a,
(ii) tic, _ va set,4se b,
(10.7.6) and (iii) (L c , 1) —> C. We wish to show that (a, b, c) is in A(K), that is, there exists a pair (p , 0) in K such that (i) (/ — P* ) IP = a,
( ii ) isio _ 110
b, (10.7.7)
and (iii) (it ° , 1) = c. To prove (10.7.7), first note that the real number c in (10.7.6)(iii) is nonnegative since so is (p,, 1) = t(X) , IlI1 c,11 Tv . We shall consider two cases, c = 0 and c > 0. If c = 0, then (I-La, 1 ) = 1112 0 Iliv
0,
and so
I P*Pa 1 1T v =
Thus, (10.7.6) yields that (110,110) = ( 0, _ b) satisfies (10.7.7). Let us now consider the case c> 0.
I I[ta IIT v --+ O.
10.7. Proofs
151
If c > 0, the condition (10.7.6)(iii) implies the existence of a' E D and m' > 0 such that (p,,„, 1) = 1,1 1.14Tv < m' for all a > a', and the same holds for IIP * Pa 11Tv = iitia 11Tv. Combining this fact with (10.7.6)(i) and (ii) we see that there exists ao E D and mo > 0 such that illiallTv, IlvallTv < mo Va > ao. Therefore, as ba(X) f_`-_-' B(X)* (see (1.2.4)), the weak topology o- (ba(X), B (X)) is the weak* topology of ba(X). It follows from the Banach-Alaoglu theorem (Lemma 1.3.2), that the unit ball of ba(X) is weak* compact, so that, by the boundedness of the net {} , there is a subnet {AA in K and an element it ° E ba(X) such that ,u,(3 -- it° setwise. From this and (10.7.6)(ii) we deduce that vo -- v° setwise for some v ° E ba(X) and p° — v° = b. As K is weak* closed, it follows that 40 , v° E K. Moreover, as P* is weakly continuous, it also follows that (I — P* )1.10 —> (I — P*)tt ° = a. Hence, ( tto , vo )\ E K satisfies (10.7.7), which implies that (a, b, c) is in A(K). This completes the proof of (10.7.5), and so the equivalence of (a) and (b) in Theorem 10.3.1. To prove that (a) = (c), it suffices to take -y := ,u because then (c) follows from the invariance of ea. To prove the reverse implication, we will show that (c) implies (b). To see this, let -y be as in (c), and suppose that (10.3.1) holds; we will next show that (10.3.2) is satisfied with c,0 0 (•) := 5%(-)/-y(X), which [by (c)] is a nontrivial measure in M(X)+. Now, let us write the inequality in (10.3.1) as
u > Pu + v — s and iterate. This gives n-1
u> pnu+ E pkv_ns
Vn > 1,
k=0
and integration with respect to y [noting that (-yP k ,u) = (y,P k u)] yields n-1 (7, IL) >
(713n , u) + (E -y Pk , v) — ns-y(X), k=0
or, dividing both sides by rry(X),
s + (-y, u)/n-y(X) ..> (713n , u)/n-y(X) + eyn, v)/y(X), where
n-1 1 V 7pk = 7 ,s(n) ,yn := _ /-' n z—i k=0
/
Observe that 0 < (7 P7 1 ) U) and that (7(),v)
n = 1,2, ... .
1147 Pn (X) = 1147 (X) < 00 for all n = 0,1, ... ,
?_ ( A 7 k, v) k> m
(10.7.8)
Vn > m
(m = 1, 2, ... ).
Existence of Invariant Probability Measures
152
Thus, since Ak>,n 71 (m = 1,2, ... ) is a monotone nondecreasing sequence of measures that converges setwise to ;1, (see (10.2.4)), taking the liminf r, in (10.7.8), we get s > ( , v)/-y(X), which is the same as (10.3.2) with (p o := -3/-y(X). El The proof of Theorem 10.3.2 and of Theorem 10.4.2 is the same as that of Theorem 10.3.1 with obvious changes.
10.7.2 Proof of Theorem 10.4.3 (a) <#. (b). We may replace (10.4.3)(i) by p,(I — P) < 0 with tt in M(X)+. Taking this into account, we introduce "slack variables" I/ in M(X)+ and r, s, and t in R± to rewrite (10.4.3) as
(i) it(I — P) +v = 0, (ii) (p, 1) +r = 1, (iii) (,a, 1G) +8 = 0, and (iv) (A, fo ) — t = s,
with (p, v, r, s, t) E K,
(10.7.9)
where K is the convex cone
K := (M(X)+) 2 x (R +) 3 . Having (10.4.3) in the form (10.7.9), we may prove Theorem 10.4.3 using Lemma 10.6.2 again, as follows. Let (X, y) and (Z, W) be the dual pairs of vector spaces with X := M(X) 2 x R3 ,
Y := B(X) 2 x R3
Z := M(X) x R3 ,
W := Cb(X) x R3 .
Then defining a linear map A : X —> Z as A(p, v, r, s, t) := (p,(/ — P) + v, (ii, 1 ) + r, (I-t, 1G) + s, (II, f0) — t), (10.7.9) becomes A(p, v, r, s, t) = (0, 1, 0, E)
with
(p, v, r, s, t) E K,
(10.7.10)
which corresponds to part (a) in Lemma 10.6.2. On the other hand, the adjoint A*:W-->YofAis
A * (u,a,0, -Y) = ((/ — P)u + a + 01G + 7,io,u,oe,i3 , -1'), which indeed maps W into
y, and so A is weakly continuous (see (10.6.3)). Then
10.7. Proofs
153
part (b) in Lemma 10.6.2 can be written as:
A*(u, a„ (3,-y) E K* = (B(X)+) 2 x (11k +) 3 implies ((0, 1, 0, E), (u, a, 0,-y)) = a + E'y > 0; that is,
(P - I)u < a + MG + Vo, with u E Cb(X)+ , a > 0,
0 > 0, and - -y > 0,
implies a+ E-y > 0. Finally, replacing -y by -y, we see that the latter statement is precisely part (b) in Theorem 10.4.3. Therefore, by Lemma 10.6.2, the proof of Theorem 10.4.3 will be complete if we show that A(K) is weakly closed. (10.7.11) We shall omit, however, the proof of (10.7.11) because it is essentially the same as the proof of (10.7.5), using the Banach-Alaoglu theorem and the fact that if {an} C M(X) is a sequence that converges to it E M(X) in the weak* topology o- (M(X), C o (X)) for M(X), then for every nonnegative 1.s.c. function f on X,
liminff f n—■ ao
ffd dpn >. p,
(see Proposition 1.4.18). In particular, for an open set G we obtain lim inf itn (G) > p(G). n—■ oo
(a) = (c). Suppose that fi satisfies (10.4.3) so that, in particular, p is an invariant p.m.. Then, by the Individual Ergodic Theorem 2.3.4, for every f in L i (p,), there is a function f* in L1(1) such that
1 nx -1 ---. f*(x) = lim - 2 Pk f (x) n-,3o n
p,-a.e.,
(10.7.12)
k=0
and
Ix f dp, = I r dp. (10.7.13) x and f = fo we see that (c) follows from (10.7.12) and
In particular, taking f = 1G (10.7.13). (c) = (b) [<=>. (a)]. Suppose that (c) holds and let u, a, 0, and -y be as (10.4.4), so that u > Pu + 7 fo - 01G — a. Iterate this inequality and rearrange terms to obtain, for n = 1, 2, ... , U 4-
na + 0
n-1
n-1
k=0
k=0
E pki G > Pnu + 7E pkfo.
154
Existence of Invariant Probability Measures
Finally, divide by n and take lim inf as n -- oo to get (10.4.5) with E := lim inf n—>oo
i n— —
n
Pk fo ( x )•
k=0
That is, (c) implies (b), which completes the proof of Theorem 10.4.3.
El
10.7.3 Proof of Theorem 10.5.1 The proof of (a) implies both (c) and (d) follows from the Birkhoff Individual Ergodic Theorem 2.3.4. Indeed, let p be a invariant p.m. for P. As both g := fo and g := 1K belong to Li(p), by Theorem 2.3.4 we get
n-1 lim inf P(n)g(x) = lirn n -1 EEx g (6) = g*(x) n—*oo
p-a.e.
t=0
for some measurable function g* E Li (,u), and, in addition, f g dp = f g*dp. With g := fo and using that f fo du > 0, it follows that g*(x) > 0 on some set B with p(B) > 0. On the other hand, with g := 1K we have f g*(x)dp, = p(K) > 0 for some K E B. Summarizing, (a) = (c) and (a) = (d). (c) (a). Assume (c) is true for some x E X, and write (10.5.2) as lim inf f P n—■ ao
(n) (X, dy) fo (y) > 0.
Recall that 113(n) (X, .)} is in the unit ball of M(X), which is sequentially compact in the weak* topology a(M(X), Co(X)) of M(X) (see Lemma 1.3.2(b)). Now, let px be a weak* accumulation point of the sequence {P(n)(x,.)}, hence a limit point for some subsequence {P (nk ) (x,.)}. By Proposition 7.2.2, p x is an invariant measure for P. Moreover, as fo E Co(X) satisfies (10.5.2) we have 0 < lim inf P(n) MX) < liM P (nk) MX) n—*oo
k—*co
=
f
fo dllx
which proves that px is a nontrivial invariant measure for P, hence an invariant p.m. for P (after normalization if necessary). (d) = (a). Consider a subsequence {nk} of {n} for which 0 < lim sup P(n) (x,K) = lim P (nk ) (x, K),
(10.7.14)
k—>oo
with x and K as in (d). As in the proof of (c) = (a), there is an invariant measure px E M(X)± and a subsequence (again denoted {n k } for convenience) such that
155
10.8. Notes
[ix is a weak* accumulation point of the subsequence {P ( nk ) (x, .)}. To prove that px is nontrivial, simply use the fact that, by Theorem 1.4.9(a) and (10.7.14), p(K) > limsupP (nk ) (x,K) > 0. k—■ oo
(b) .;=> (a). Suppose that (b) holds, and let {nk} c {n} be the subsequence for which the "lim inf" in (10.5.1) is attained, that is, 0 < lirn f f(y)(vP (nk ) )(dy) < oo. k— ■ oo
From this, we conclude that sup f f(y)(vP ( nk ) )(dy) < oo, k
which in turn, by Proposition 1.4.15 (as f is a moment), implies that the sequence v { p(nk)} is tight. Therefore, by Prohorov's Theorem 1.4.12, there is a measure and a subsequence (again denoted {nk}) such that vP ( nk )
pv .
Using that P is weak-Feller and it is a p.m., it follows from Proposition 7.2.2 that is an invariant p.m. (a) = (b). Conversely, let ii be an invariant p.m. Let Kn be a nondecreasing sequence of compact sets such that Kn I X, and p(Kn+i — Km ) < n -3 , n = 1,2, ... , where we have used that every p.m. on a o- -compact space is tight (see, e.g., [14]). Let v : X -- X be the measurable function such that v := n for every X E Kn+1 — K n , n> 1. Then, v is obviously a moment, and n-1
0 < lim sup n Ti
—>oo
00
Ei,f(W = f v dp, 5_
—
t=0
n=1
10.8 Notes Most of the results in this chapter are from [57]. There is an extensive literature on the problem Pi', e.g. [24, 29, 53, 70, 75, 85, 87, 88, 103, 94, 99, 105, 112, 122], ... , and the references therein. We know of no references for P; and 1- 7. . There are, of course, many previous works on existence and uniqueness of invariant p.m.'s, but not for strictly positive invariant p.m.'s. In addition, most results in the literature concern weak-Feller t.p.f.'s on a LCS metric space.
Chapter 11
Existence and Uniqueness of Fixed Points for Markov Operators 11.1 Introduction and Statement of the Problems In Chapter 10 we have considered the existence of invariant p.m.'s for a t.p.f. P, viewing P as a Markov operator on M(X) — see §10.2. Thus, an invariant p.m. p, turns out to be a fixed point of P, that is, p,P = p. In this section, we study essentially the same problem but from a very different perspective. To motivate the material in this chapter, consider the logistic map defined in (6.2.5) as x 1-> 8(x) = 4x(1 - x) for x E [0,1]. This gives a MC e, = with et+ i = S() for t = 0,1, ... , with some given initial distribution and the t.p.f. P(x, B) coincides with the Dirac measure concentrated at 8(x). Hence, as 8(x) = x if and only if x = 0 or x = 3/4, it follows that the Dirac measures 6 0 and 63/4 at the points 0 and 3/4 are "trivial" invariant p.m.'s, or fixed points of P. In fact, there are countably many other invariant p.m.'s of P associated with the cycles of all lengths j = 1,2, ... (see Holmgren [72] and the discussion in §6.3.2). However, one may wish to determine whether there exists an invariant p.m. that has a density w.r.t. the Lebesgue measure A on [0,1] (and, in fact, Ulam and von Neumann proved that there exists an invariant p.m. with density (7r,/x(1 - x)) -1 ). For the latter problem, the results of Chapter 10 are "useless", in the sense that they answer the question of existence of invariant p.m.'s but they do not give information about the existence of invariant p.m.'s with a density. When P maps the space of measures with a density w.r.t. A into itself, an alternative is then to consider the operator T in (2.3.10) defined on L 1 (A). Thus,
eo,
{et}
Markov Operators
158
T maps the density f E Li (A) of a measure vf < A to the density T f of (vfP) w.r.t. A. As noted in Remark 2.3.7(b), T is a Markov operator, and so, we are led to investigate the existence of nontrivial fixed points of T in L i (A). This is a topic of fundamental importance in many fields, including ergodic theory, probability, dynamical systems, and their applications, and there is, therefore, an extensive literature on the subject (some related references are given in the Notes section at the end of this chapter). Here we present necessary and sufficient conditions for the following problems to have a solution: • Pi . Existence of invariant probability densities (IPDs) for a Markov operator T on a space Li -a- Li (X, 13, A) (for a more precise statement see (11.2.3)); • P2. Existence of strictly positive IPDs; and • P3. Existence and uniqueness of strictly positive IPDs. The approach. The approach is similar in spirit to that in Chapter 10. Again, the main idea is to write the problems P i , i = 1, 2, 3, in terms of "linear equations" in appropriate Banach spaces, and then use a generalized Farkas theorem of Craven and Koliha [25, Theor. 2] (see Lemma 10.6.2), to obtain necessary and sufficient conditions for the linear equations to have a solution. The resulting existence and uniqueness criteria have a nice interpretation as Lyapunov (or Foster-Lyapunov) criteria, which, in some cases, allows us to compare our results with related works. After some preliminary material in §11.2, the existence results are presented in §11.3. For ease of exposition, all proofs are postponed to §11.4.
11.2 Notation and Definitions Let (X, B, A) be a a-finite measure space. We will assume that this space is complete, which means that B contains all the subsets of A-null sets (i.e., if B E B is such that A(B) = 0 and B' C B, then B' is in B). Let L i Li (X, 13, A) be the Banach space of A-integrable functions f on X with the Li norm
:= f IfIdA. We denote by Lt the "positive cone" in L i , i.e., LiF := If E Lil f > 01. In this chapter, A is a fixed measure, and "a.e." means "A-a.e.". As in Remark 2.3.7(b), a linear map T : L 1 L, is said to be a Markov operator if it is positive, that is,
Tf EL
if f E LiE ,
(11.2.1)
and, in addition, T is norm-preserving, that is,
ITf Iii
=
1111k if
f E L.
As T fl < TIf I it follows that T is also a contraction, i.e.,
f
1
IlfIli
Vf E
.
(11.2.2)
159
11.2. Notation and Definitions
A function f E Li is called a fixed point of T (or invariant w.r.t. T) if T f = f, and, on the other hand, f is called a probability density w.r.t. A if f > 0 and III f = 1. Thus, problem Pi addresses the question of finding functions f that satisfy T f = f and 11/111= 1, with f E Lt. (11.2.3) This is essentially equivalent to the problem of existence of nontrivial (IlfIli > 0) fixed points of T [see Remark 11.2.1(b)]. In fact, in addition to (11.2.3), we shall consider the condition (11.2.4) f fo where fo E LiE is a function which is positive on a set B e B of positive A-measure. Hence, specializing to the case B = X, so that (11.2.5)
fo > 0 a.e.,
we obtain conditions for P2 and 13, where strictly positive means f> 0 a.e. The results for Pi, P2, and P3 are presented in §11.3 and proved in §11.4. These results are applicable, for example, to the case in which the t.p.f. P is A-continuous, that is, P(x, B) is of the form P(x, B) = f p(x , y)A(dy),
(11.2.6)
where p(x, y) : X x X R+ is a given nonnegative, measurable function. Then, introducing the measures as in (2.3.9) and (2.2.12), that is, vf(B) := f f (x)A(dx)
for every
f E
(11.2.7)
and (v fP)(B) := f vf(dx)P(x, B),
(11.2.8)
the corresponding Markov operator T (2.3.10) maps f E Li into the RadonNikoqm derivative of v1/3 (which, of course, is absolutely continuous with respect to A), i.e., T f := d(vfP)/ dA,
or T f (y) = f vf(dx)p(x, y) a.e.
(11.2.9)
Thus, a function f that satisfies (11.2.3) is an 1PD for P in the usual sense, i.e., f (•) = I f (x)P(x, .)A(dx),
11/111= 1, f E Lt.
(11.2.10)
Moreover, the measure v1 in (11.2.7) is an invariant p.m. for P, i.e., vf P = vf .
(11.2.11)
160
Markov Operators
Another case of interest is when P corresponds to a "deterministic" (or "noiseless") MC as in (2.2.6), i.e., 6 = F(et-i) = Ft (G), t = 0, 1, .. . ,
(11.2.12)
where F : X -> X is a measurable function. The logistic MC et+ i = S(e t ) in the previous section is an example of such a MC. In this case, the t.p.f. P (x , B) is given by P(x, B) = 6 F(x) (B), which can be written as P(x, B) = 5x [F-1 (B)]
(with Sx := Dirac measure at x),
and all of the results for the operator T in (11.2.9) remain valid provided that F is A-nonsingular in the sense that A[F+ 1 (B)] = 0 if A(B) = 0. In this case, T is known as the Frobenius-Perron operatorcorresponding to F (see e.g. [85], p.40). Remark 11.2.1. (a) All sets and functions introduced below are supposed to be (B ) measurable. In §§11.3 and 11.4, we identify sets and functions which differ only on a A-null set. If X is a vector space, we denote by X+ := {x E Xlx> 0} the convex cone of nonnegative elements of X. The indicator function of a set B is denoted by 11B• (b) A function f E Li is a fixed point of T if and only if f+ := max( f, 0) and f - := - min(f, , 0) are both fixed points of T (see, for instance, [48] Lemma 2). Moreover, if f E Lt is a fixed point of T and III f Iii > 0, then fillf11, is an IPD for T. Thus, the problem of existence of nontrivial fixed points of T basically reduces to P. (c) Problem Pi is obviously equivalent to the problem of existence of functions that satisfy (11.2.3)-(11.2.4). In fact, we pose Ti in the form (11.2.3)-(11.2.4) because it naturally leads to the strictly positive case in which fo satisfies (11.2.5). However, if one is only interested in Ti, and not in P2 and P3, one can replace (11.2.4) with a "majorization" condition f < fo , which is useful to do in some applications, and our present approach is still applicable (as can be seen from the proofs in §11.4, and also in Remark 11.3.6). Several authors have studied the "majorization" problem but under very restrictive assumptions. For instance, [29] deals with a specific type of Markov chains in X = Rd ; [94] considers a Markov chain in X = {1, 2, ... }; and in [54] the underlying measure space (X, B, A) is as in the present paper, namely, -
(X, B, A)
is a a-finite complete measure space,
(11.2.13)
but it requires additional hypotheses that are not needed for our results in §11.3.
Incidentally, we need (11.2.13) because we wish to use the relation (11.3.3) below.
11.3 Existence Results In this section we first consider problem P i , in the form (11.2.3), (11.2.4); then P2, as in (11.2.3)-(11.2.5); and, finally, the uniqueness problem P3.
161
11.3. Existence Results
We begin by rewriting (11.2.3), (11.2.4) in an equivalent form, for which we need to introduce some notation.
11.3.1 The Space ba(X, A) Let M(X) be the Banach space of bounded signed measures on B with the total variation norm TV, and let MA (X) be the subspace of measures in M(X) which are absolutely continuous w.r.t. A, i.e., MA(X) :=
Itt c M(X) p, < AI.
(11.3.1)
By the Radon-NikoOm theorem, MA(X) is isometrically isomorphic to Li = Li(X,B, A), which we write as Li
(11.3.2)
MA(X).
Now let ba(X, A) _= ba(X, B, A) be the Banach space of bounded finitely-additive set functions it on B such that ,u(B) = 0 if A(B) = 0, with the total variation norm. Then ba(X, A) is isometrically isomorphic to the (topological) dual L of L,„ [34, Theor. IV.8.16], i.e., .14,0 c ba(X, A).
(11.3.3)
Hence, since LI L oo , the second dual LI* of Li is isometrically isomorphic to ba(X, A), that is, LI* ba(X, A), so we have L1 c ba(X, A)
L.
(11.3.4)
Finally, let T* : L c, —> L c, be the adjoint of the Markov operator T : L i —> Li in (11.2.1), (11.2.2). (In the "deterministic" case (11.2.12), the adjoint T* is called the Koopm,an operator with respect to F; see [85], p. 47. In the A-continuous case (11.2.6)–(11.2.9), T* g(x) = f p(x,y)g(y)A(dy).) Then T* is also a Markov operator (on L oc,), so that, in particular (by Lemma VI.2.2 in [34]),
1 7'11 =
T II = 1,
(11.3.5)
and the second adjoint T** : —> LI* of T is an extension of T [34, Lemma VI.2.6]. To simplify the notation we shall write T** as T and, in view of (11.3.4), we also write T: ba(X, A) —> ba(X, A). (11.3.6)
11.3.2 Problem Pi We now state our first result (proved in §11.4), where we use the notation (f, u) :=
f(
fu)dA for every f in Li and u in L.
162
Markov Operators
Theorem 11.3.1. The following statements are equivalent: (a) There is a function f E Li that satisfies (11.2.3), (11.2.4) for some fo E LiF . (b) There is a pair (p,,v) in ba(X, A) -1- x ba(X, A) -1- such that
(i)
(I — T)p, = 0,
(ii) it — v = (po ,
and
(iii)
p(X) = 1,
(11.3.7)
where c,00 E MA(X) ± is the measure defined by B E
Wo(B) = f fo dA,
B.
(11.3.8)
B
(c) The condition with u, v E L+ 0° and r E le
(T* — I)u < —v + r
(11.3.9)
implies (.f 0,v)
(11.3.10)
7''.
For a proof of Theorem 11.3.1 see §11.4. We can also derive a necessary and sufficient condition using asymptotic properties of the Cesaro sequence T(n) f o :
n-1 n _i E T k fo
for n = 1, 2, ...
(11.3.11)
k=0
(with T° := identity) for some fixed arbitrary strictly positive function fo E L. Theorem 11.3.2. Let fo E LiF be any fixed, strictly positive function. Then T admits a fixed point f* E Lif if and only if
lim inf n--- oo
T (n) fp
0.
(11.3.12)
For a proof of Theorem 11.3.2 see §11.4.
11.3.3 Problem P2 Theorem 11.3.1 refers to problem P1 in the form (11.2.3), (11.2.4), for a given function fo in L: t , which is positive on a set B E B with A(B) > 0. The following theorem, on the other hand, considers a function fo as in (11.2.5), so that a solution f E L1 to (11.2.3)—(11.2.5), if one exists, is a strictly positive IPD, as required in P2.
Theorem 11.3.3. The following statements are equivalent. (a) There is a function f E L i that satisfies (11.2.3) and (11.2.4) for some function fo as in (11.2.5).
163
11.3. Existence Results
(b) There is a pair (pc, v) in ba(X , A)+ x ba(X , ))± that satisfies (11.3.7), with cp o as in (11.3.8) for some function f o as in (11.2.5). (c) The condition (11.3.9) implies (11.3.10) for some function f o as in (11.2.5). (d) There is a function g o E Lt, with g o > 0 a.e., such that
lim inf Tn go > 0 a. e.
(11.3.13)
fl -*00
(e) There is a function g o e Lt, with go > 0 a.e., such that
lim inf T (n ) go > 0 a. e.,
(11.3.14)
with T (n) as in (11.3.11).
For a proof of Theorem 11.3.3 see §11.4. Remark 11.3.4. (a) As was already noted in §11.1, there are many previous works related to the problem of existence of an IPD, in particular, for strictly positive IPDs. For instance, for a general positive contration in L 1 , Neveu [105, Theor. 1] shows that part (a) in Theorem 11.3.3 is equivalent to: For any u E L, the equality lim infn (Tngo, u) = 0 implies that u = 0 a. e., where go is an arbitrary but fixed function in Lt with g o > 0 a.e.
(11.3.15)
Condition (11.3.15), which is written in still another equivalent form in [18], is, at least in appearance, more complicated that our condition (11.3.13) for Markov operators. On the other hand, by the general inequality h = ago + (h — ago ) > ago — (h — ag o ) , a E R,
arguments similar to those used by Neveu [105, p. 465] show that if (11.3.13) holds for a given strictly positive function g o in LiF , then it holds for every strictly positive function h in Li 1- .
(b) The existence of a strictly positive IPD does not imply, of course, that it is the unique IPD. For a simple counterexample take T as the 2 x 2 identity matrix on R 2 .
11.3.4 Problem P3 We now consider the question of uniqueness of strictly positive IPDs. To motivate our approach let us first consider the problem of finding an IPD which is not strictly positive. In other words, let G E B be a set such that G X and A(G) > 0, and consider the problem of finding an IPD f that vanishes on G. More explicitly, the problem is to find f in L -t such that (I — T) f = 0, III f Iii = 1, and
f = 0 a.e. on
C.
This is expressed in other equivalent forms in the following theorem.
(11.3.16)
164
Markov Operators
Theorem 11.3.5. Let G E B be a set such that G X and A(G) > 0. Then the following statements are equivalent: (a) (11.3.16) has a solution f in LiF . (b) There exists ,u in ba(X, A)± such that
(I — T)it = 0,
it < v., and (11,1) = 1,
(11.3.17)
for some nontrivial measure v. in M(X)± with v(G) = 0. (c) For any u, v in L+ and 13 E IR, the condition (I — T*)u + v + 0 > 0
(11.3.18)
(v., v) + 0 > 0,
(11.3.19)
implies for some nontrivial measure v. in M(X)± with v(C) = 0. (d) There exist go, h E 14- with Tr' go
lirn sup T ( n ) go 0 0 and lirn sup T (n) go = 0 a.e. on G. n ---*oo
(11.3.20)
n—oo
Remark 11.3.6. Observe that Theorem 11.3.5 also permits to derive a necessary and sufficient condition for the existence of a fixed point f of T, majorized by some given function fo E LI - , that is, the existence of a function f E Lil- that
satisfies (11.2.3) and the majorization condition f
(11.3.21)
fo
for some fo E L. As a consequence of Theorem 11.3.5 we obtain the following result on the uniqueness of a strictly positive IPD. Corollary 11.3.7. The following statements are equivalent: (a) Either T has a unique IPD which is strictly positive, or T does not have an IPD. (b) There is no set G E B with G X and A(G) > 0, for which (11.3.16) has a solution f in LiE . (c) For every set G E B with G L X and A(G) > 0, and every nontrivial measure v. in M(X)± with v(C) = 0, there exist u,v E LI, and 0 E R such that
(I — T* )u + v +13 > 0
and (v. , v) + 0 < 0.
(11.3.22)
(d) For every set G E B with G X and A(G) > 0, and for every go, h E LiF 0 withTngo
lim sup T ( n) go = 0 a. e. or lim sup Ten ) go n---oo
n--+ cc
0 on G.
(11.3.23)
165
11.3. Existence Results
Proof. It is clear that (a) implies (b). We next prove that (b) implies (a). Suppose that (b) holds. Now if (a) does not hold, then T has at least one
IPD which is not strictly positive, or it is not unique. As (b) holds, the former case is not possible. In the latter case, let fi f2 be two IPDs. Then f := fi — f2 is a nontrivial fixed point of T and so are f+ and f - [see Remark 11.2.1(b)]. Moreover, denoting by B E B the support of f+, there is a set G E B with A(G) > 0 such that G C B and f+ > 0 on G. Then f - = 0 on G and, therefore, f - illilli satisfies (11.3.16); hence, (b) does not hold. Thus, (b) implies (a). Finally, the equivalence of (a), (c) and (d) follows from Theorem 11.3.5. 1=1 Remark 11.3.8. If T* denotes the adjoint of a Markov operator T, then
is sometimes called the drift operator associated to T. In terms of A we may rewrite (11.3.18) in the form Au
< v +0,
which is of the same form as the Lyapunov (or Foster-Lyapunov) criteria that are widely used in studies on the "stability" of Markov processes and MCs; see, for instance, [7, 29, 53, 84, 103, 130].
11.3.5 Example Let P and T be as in (11.2.6) and (11.2.9), respectively. As an example of how one can derive conditions for the existence of IPDs, for f in LI- let us write Tn f = d(v fPn)I 0% as (11.3.24)
Tn f (y) = f vf(dx)pn(x,y), x
where IP (x, y) denotes the n-step transition density. Moreover, define p* (x, y) := lim inf pn (x, y), n
co
and f* (y) := f v f (dx)p* (x , y). X
Observe that f* is in L-IF since, by Fatou's lemma and (11.2.2), inf f (TThpdA Ilf*Ili = f f* clA < lim 7-1-400
IlfIli.
(11.3.25)
166
Markov Operators
Now, from (11.3.24) and using Fatou's lemma again, lim inf 7' f (y) > f* (y), so that a sufficient condition for (11.3.13) is: There is a function f e .14.- such that a.e.,
(11.3.26)
with f* as in (11.3.25). For instance, let A be the Lebesgue measure on R d , and let A be adxd matrix with spectral radius < 1. Moreover, let {o t ,t = 0,1, ... } be a sequence of i.i.d. (independent and identically distributed) Gaussian d-vectors with zero mean and a symmetric positive-definite covariance matrix. Then it is well known (and easy to show) that for the Gauss-Markov MC (2.2.11) = .24-t + Ot,
t = 0, 1, ...;
x o = x given,
the limiting density p* in (11.3.25) is again Gaussian. Therefore (11.3.26) always holds for any strictly positive function f in L 1 . Similarly, suppose that, for every y e X =R d , A y (B) := fB A(dx)p(x , y)
VB E B
defines a finite measure on B. Then
is also a finite measure on B, and if f E Lt is a convex function we obtain, by Jensen's inequality (see, e.g., Perlman [110, Prop. 1.1]), Tn f (y) ? f [fin (y)], where
11(y) := f xpn (x , y)A(dx). x
(11.3.27)
Hence if, in addition, f is strictly positive and if there is a constant M such that Illn( y ) 1 < Al
Vy E X, n = 1, 2, ... ,
(11.3.28)
then (11.3.27) yields lim inf Tn f (y) > 0
Vy E X.
71 ---+ 00
Thus, another sufficient condition for (11.3.13) is that every y and (11.3.28) holds.
Ay (*)
is a finite measure for
167
11.4. Proofs
11.4 Proofs Before proving Theorems 11.3.1, 11.3.2 and 11.3.3, we need the following auxiliary result. Let eu, be in ba(X, A))± [9 MA(X)+] and f in Lt. Then the notation f < p, (used in the following lemma) means that vf(B) < p,(B), where vf E MA(X)± is the measure defined in (11.2.7). Lemma 11.4.1. (See [39, p.34, Lemma A] or [105, Lemma 1]). Let p, be in ba(X, ))±. Then (a) The set P(jI) := If E 4 f < pl contains a maximal element f*; that f* is in r(p), and f* f for all f E r(p); (b) Let B := {xl f*(x) = 0. There exists a function u E Lto such that u > 0 on B and (p,u) = 0. (c) If, in addition, p, is a fixed point of a linear operator T : ba(X, )¼) —> ba(X, )) (i.e., T p = p), then so is f*.
11.4.1 Proof of Theorem 11.3.1 We shall prove that (a)-(b)(a) and (b).<=>(c). (a) = (b). Clearly, part (a) in Theorem 11.3.1 is equivalent to: There is pair of functions (f, g) in Lif x L -1- such that (I —T)f = 0,
f — g = fo ,
(f, 1) = 1.
(11.4.1)
To see the equivalence, simply take g := f — fo. Now, in turn, recalling that L 1 --' MA(X) and MA(X) c ba(X, A) [see (11.3.2) and (11.3.4)], we see that (11.4.1) implies part (b) in the theorem by identifying f and g in (11.4.1) with the measures p(B) := I fdA and v(B) := fB gc/A B
in MA(X) ± c ba(X, A)E. (b) = (a). Let (it, v) E ba(X, A)± x ba(X, A)± be a pair that satisfies (11.3.7). Then, by (11.3.7)(i) and Lemma 11.4.1, the set r(p) in Lemma 11.4.1(a) contains a maximal element f* e L, which is a fixed point of T. Moreover, by (11.3.8) and (11.3.7)(ii), fo is in r(t ) and, therefore, f* fo• Hence, f := f*/11f*Ili is an IPD with f > f* > fo, where the first inequality comes from
11/11 = I f*dA < (X) =1, x
and so the pair (f,g) c 1,1" x L -1- , with g := f — fo , satisfies (11.4.1). (b) .#› (c). We wish to use Lemma 10.6.2, for which we shall first rewrite (11.3.7) as a "linear equation".
168
Markov Operators
Consider the dual pairs (X, Y) and (Z, W), where X := ba(X, A) x ba(X, A),
y :=
L ao x 1,, Z := X x IR, W :=
y x IR.
A) and u E L oo , we write (it, u) := f u dit. In particular (tt, 1) = it(X). Now let A : X —> Z be the linear map For it
E ba(X,
A(1 1 , v) := ((I — niL, 1- 1 — v, (1- 1 , 1 )).
Furthermore, let K C X be the convex cone K := ba(X,A)+ x ba(X, A)+, for which the dual cone K* C 3) is K* := 40 x 40 , and let b E Z be the vector b := (0, (po , 1). Then we can write (11.3.7) as A(i,t, v) = b, so that part (b) in Theorem 11.3.1 [which corresponds to (a) in Lemma 10.6.2] becomes: the equation A(//, v) = (0, (Po, 1) has a solution (a, v) in
K.
(11.4.2)
Let us now consider the adjoint A* : W —> 3) of A, which is easily seen to be given as A* (u, v, r) = ((/ — T*)u + v + r, —v) V(u,v,r) E W. Thus, observing that ((0, (Po, 1), (u, v, r)) = (vo, v) + r, the statement corresponding to (b) in Lemma 10.6.2 is: (/ — T*)u + v + r > 0 and — v > 0
implies (vo, 0 + r > 0,
which, replacing v by —v and using (11.3.8), can be restated as (T* — I)u < —v + r and v E L±
implies (fo , v) < r.
(11.4.3)
Now note that if v E LI) , then for the inequality (fo , v) < r to be true we must necessarily have r > 0 (recall that f o is in Lt); thus, in (11.4.3) we may take r > 0. Moreover, without loss of generality, we may also take u > 0 because, for any u E L oo , the function u' := u+ Iluiloo is in 40 , and (T* — I)u = (T* — I)u'
(11.4.4)
(since T* c -2--- c • T*1 = c for any constant c). With these changes, (11.4.3) becomes exactly the same as statement (c) in Theorem 11.3.1. Therefore, as it is obvious that the map A in (11.4.2) is weakly continuous (see (10.6.3)) we can use Lemma 10.6.2 to conclude that (b) and (c) in Theorem 11.3.1 are equivalent provided that A(K) is weakly closed.
(11.4.5)
We shall now proceed to prove (11.4.5) using the fact that (ba(X, A), L oo ) is a dual pair of vector spaces, and that, by (11.3.3), the weak topology a(ba(X, A), L) on ba(X, A) is the weak* topology (see Remark 1.3.1). Convergence in this topology will be denoted by '''>.
169
11.4. Proofs
Let (D,>) be a directed set, and let {(p a , v,), a E DI be a net in K = ba(X , A)+ x ba(X , ))+ such that
A(, v) 14 (a, b, c) for some
(a, b, c) E W = L c, x L oo x IR;
that is (i) (I — T)p, 14 a,
(ii) p,, — I}, u-4 b,
and (iii) (p,a , 1) —4 c.
(11.4.6)
We wish to show that (a, b, c) is in A(K); that is, there is a pair (p, v) in K such that (i) (I — T)p, = a,
(ii) p, — v = b,
and (iii) (p, 1) = c.
(11.4.7)
By (11.4.6)(iii), we must have c > 0, so we shall consider two cases, c = 0 and c> 0. Case 1: c = 0. In this case, (11.4.6)(iii) implies that p, converges strongly to 0, since iii-tallTv = (Pa, 1) ---> 0, and so does T p c,. Hence, a = 0, and so (11.4.7) holds with (p, v) = (0, —b). Case 2: c> 0. By (11.4.6)(iii), there is a constant Mo (for instance, take Mo = 2c) and ao E D such that iiliallTv <M0 for all a > ao . This in turn, combined with (11.4.6)(ii), yields that there is ai E D and a constant M1 such that IlvallTv < Mi
for all a > a i . Therefore, the Banach-Alaoglu-Bourbaki theorem (see Lemma 1.3.2) implies the existence of finitely additive set functions p, v in ba(X , )YE' and a subnet {0} of {a} such that (i) PO 14 it,
and
w
(ii) vo —> v.
(11.4.8)
w* Moreover, (11.4.8)(i) yields that Tpo —> Tp, since (T,u,o, u) = (po,T* u) —) (p, T* u) = (T p, u)
Vu E L.
(11.4.9)
Finally, from (11.4.6), (11.4.8) and (11.4.9) it is easily deduced that the pair (p,, v) in (11.4.8) satisfies (11.4.7). This completes the proof of (11.4.5), and, therefore, the proof of Theorem 11.3.1.
11.4.2 Proof of Theorem 11.3.2 The "if" part. Let y(n)j0 be as in (11.3.11). Observe that supn
1 T(n) /0 1 < I fob.
By the Banach-Alaoglu theorem (see Lemma 1.3.2), the norm-bounded subsets of ba(X, A) are weak* compact (that is, in the weak* topology cr(ba(X , A), L) of ba(X, A)). Hence, there is a finitely additive measure p E ba(X , A)± and a subnet {n,} of the sequence {n}, such that (h,T (na ) fo ) —> (h, p)
Vh E L a c.
Markov Operators
170 It follows that T p = p, because T(T (na ) fo) = T (na ) fo + nV [Tna fo — fo]
Vn,,
and
(T* h, p,)
= lim (T* h, Ten' ) fo) a
= 1411 (h,T(T ( nce ) fo ))
a = (1.1„ u,) V h E L,,, where we have used that lirp ri 1 (h,Tn'io — fo)1
n ,---, 1 011. [ITn /011 + 11/01I]
27c i llhildifoll t O.
Hence, T ,u, = t. Now, let :I.; : = lim infn T (n) fo E LiE . By (11.3.12), addition, Fatou's lemma yields lim inf (h,T (n) fo) > (h, :10 )
10
0. In
Vh E 4;0 .
71,-- 00
Therefore, for every h E Lit,
( 11 , ii)
(h, T(na) f0) = liM a >
lim inf (h,T (n) fo) ri—oo
> (11 ,L), so that p, > fo . Invoking Lemma 11.4.1, we conclude that L E r(i,) :. If E Lill f
lirn
-1 n -1 \--01 L jk=0 T k fo
- 71 —1 k *. n—*(Do n _ i \-% Lik=0 T j
= lim
Snfo
Ti —+00 Sn f* '
with
n-1 Sn f :=
E Tk f
k=0
for f E Li.
(11.4.10)
171
11.4. Proofs
By Theorem 2.3.2, the limit in (11.4.10) is finite a.e. on C* := C n ff* > 01. Moreover, suppose for the moment that A is finite. Let C be the sub-a-algebra of A-invariant sets (where a A-invariant set A E 8 is a set such that TlIA = 11A). For any B E8 and f E Li we define (iBi)(x) := 11/3(x)f(x) for all x E X. Further, let D be the dissipative part of X in Hopf' s decomposition. Then, from Revuz [112, p. 150, Theor. 5.6], the limit in (11.4.10) can be written as fo E Vic fo IC] (f) * —1 lim T ( n) = lim Sri = n—■ oo Sn f* E [Hc f* IC]
*
with Plc :=Ic Eo°° (TID) n . Obviously, as Jo > 0, we have Hcfo > Ic Jo, and thus, from the strict positivity of fo, E[Hc folC] > E[IC folC] > 0. Moreover, writing f* = fr) and using f in lieu of f* in (11.4.11), we have Hcf =f so that the ratio in (11.4.11) is greater than E[ic folC]/E[Th` IC] on C*. This yields that (p.)-4 limn_>00 T () f0 > 0 on C. Finally, if A is not finite, as fo E 1,1- is strictly positive, let p, be the finite measure p(B) := fB fo dA equivalent to A. A function f is in L i (p,) if and only if fo f is in L i L i (A)). Therefore, we replace T with the new operator f f := fo-1 T(f 0 f). It turns out that T' is a positive contraction on L i (p) , and, in addition, L(t) = Loo (A), (T)* = T*, so that the a-algebra of invariant sets is the same (see Revuz [112, p. 133]). The ratio in (11.4.11) becomes ,
E[111 1C] E f f o lC]
and we conclude in the same manner as we did for the case A finite.
11.4.3 Proof of Theorem 11.3.3 The equivalence of (a), (b) and (c) follows, of course, from Theorem 11.3.1 applied to the particular case of a function f o > 0 a.e. To complete the proof of Theorem 11.3.3, we will show that (a)-(d)(e)(c). In fact, the first two implications are straightforward because if f E L 1 is as in (a), then go := f satisfies (d) (since T n f = f for all n, we get lim inf Tn f = f > 0), whereas (d)(e) follows from general properties of sequences. Hence, it only remains to prove that (e) implies (c). Let go E lit be as in (e), and suppose that (11.3.9) holds, that is, u > T*u
v — r, (11.4.12)
where u, v E Lto and r > 0. We will show that (11.4.12) implies (11.3.10) with fo given by inf fo := c • lim n—Kx)
where
c := 1/1Igoll i .
(11.4.13)
172
Markov Operators
To do this, observe first that fo indeed satisfies (11.2.5) [by (11.3.14)], and it belongs to LiE because [by (11.2.2)]
f
(T k go ) d A = 11 Tk g0 1 1
= 11.g o I I i
so that Fatou's lemma yields 11f0111 =
E f(T k go)c/A = c • b o b =1. f io ca < c • lim inf —n1 n-1 k=0
Now, to see that fo satisfies (11.3.10), iterate (11.4.12) to obtain (recalling that T*1 = 1) n-1 U > T*nu ±
E
vic, _
nr
Vn = 1, 2, . .. .
k=0
Then multiply by go and integrate with respect to A to see that n-1 (go , u) > (Tn go, u) + (E Tk go, v) — nrlig0111. k=0
Finally, in the latter inequality, multiply by (nlig o ll i ) -1 , and then take lim inf n to obtain (fo, v) < r from (11.4.13) and Fatou's lemma. Therefore, (e) implies (c), which completes the proof of Theorem 11.3.3. 0 Remark 11.4.2. In the proof of Theorem 11.3.5 we use the following fact, which is a restatement of Lemma 10.6.1(a) : If p, is in ba(X, A)+, v is in M(X) ± and p
11.4.4 Proof of Theorem 11.3.5 We shall prove first that (a) and (b) are equivalent. (a) (b). Let f be as in (a) and define vf(dx) := f(x)A(dx) as in (11.2.7). Then p, = v* := vf satisfy (b). (b) = (a). With p, and v * as in (b), Lemma 11.4.1 yields that the maximal element f* in F(p) is a fixed point of T such that f* = 0 a.e. on G. Moreover, by Remark 11.4.2, the condition p, < v* implies that in fact p, is a measure in M(X)+ and, therefore, f* is nontrivial [otherwise, the set B in Lemma 11.4.1(b) would be all of X, in which case p(X) = 0; a contradiction]. Hence f := f*/11f*Ili satisfies (11.3.16). (b) <=> (c). We shall use Lemma 10.6.2, for which we introduce the dual pairs (X, 32) and (2, W) of vector spaces X := ba(X, A) x ba(X, A), 3) := L oo x L oo , 2 := X X R, W := 3) X R.
173
11.4. Proofs
Let A: X -> Z and its adjoint A* : W -> Y be defined as A(p,, v) := ((I - T),u,, + v, (t.t, 1)),
and A* (u, v, 0) := ((/ - T*)u + v + 0,v). With this notation, part (b) in Theorem 11.3.5 is equivalent to: The linear equation A(ti, v) = (0, v * , 1) has a solution
v) in K,
(11.4.14)
where K := ba(X , ))± X ba(X, )¼)± is the positive cone in X. Similarly, part (c) in Theorem 11.3.5 can be written as: * = ((0 , v * , 1) , (u, v , 0)) = (v* , v) +3 > 0.
A* (u , v , ,3) E
(11.4.15)
Therefore, by Lemma 10.6.2, (11.4.14) and (11.4.15) are equivalent if (i) A is weakly continuous, and (ii) A(K) is weakly closed. The condition (i) is obvious (see (10.6.2)) and (ii) can be proved exactly as (11.4.5). (a) = (d). Choose h := go := f, where f is an IPD as in (a). (d) = (c). Consider u, v E L;c4,-0 and E R such that (11.3.18) holds. Rewrite (11.3.18) as u > T* u - v - 0. Then iterating n times and dividing by n one gets (after rearranging terms) n-1
71, -1
E T*kv + >
( T*11 —
Vn = 1,2,...
k=0
Hence, multiplying by g o and integrating w.r.t. A, n-1
E T k go , v) + 1311goll i
n -1 (go, (T " — Du)
(11.4.16)
k=0
for all n = 1, 2, .... Taking lim sup in (11.4.16) and invoking Fatou's lemma we obtain (lim sup n 71-■ CO
—1
n-1
T go, v) ± 011011
0
k=0
because the right-hand-side of (11.4.16) vanishes as n
Do. Therefore, letting
n-1 /1* (B) := I
Igo 11 -1 f (lim sup n -1 B
(11.3.19) follows.
n—>oo
E T k go ) dA for B E 8,
k=0
LI
174
Markov Operators
11.5 Notes Problems Pi and P2 have been studied by many authors. For instance, [80] and [124] deal with a problem of the form (11.2.3), (11.2.4), whereas [18, 39, 48, 75, 105, 112] study the strictly positive case P2. The latter references also show that if P2 has a solution, then T is a conservative operator, and, on the other hand, P2 turns out to be the same as the problem of existence of a probability measure 11, equivalent to A (in the usual sense that ii < A and A < //). In addition to these references, the case of a A-continuous Markov process, as in (11.2.6), is dealt with in [5, 85, 86], and the deterministic system (11.2.12) is studied in [4, 85, 126]. For most practical purposes, the problems Pi (i =-- 1, 2, 3) can be restricted to situations as in (11.2.6) or (11.2.12) because under mild assumptions on the measure space (X, B, A), every positive contraction T on Li is of the form (11.2.9) for at least one t.p.f. P (see [112], pp.120-121). Finally, we should remark that we know of no previous work on the uniqueness problem P3.
Chapter 12
Approximation Procedures for Invariant Probability Measures 12.1 Introduction In this chapter we consider a MC e. on a LCS metric space X with t.p.f. P. Suppose for the time being that A E M(X) is an ergodic invariant p.m. for P (see Definition 2.4.1). We address the following issue. Given f E Li(A), we want to evaluate f fdp, knowing only that the ergodic invariant p.m. A exists but p itself is not known. One way to proceed is to simulate the MC. This makes sense because, as A is ergodic, for all initial states x in a set Af of full A-measure we have
lim nri—■ cc
f(k) = f f diL
Px -a.s.
(12.1.1)
(see Corollary 2.5.2 and the comment after it). Hence, if we simulate the MC from an initial point eo E Af, that is, if we simulate a realization w E 52 to obtain a sample-path (eo (w), 6 (w), ... ) (with 6 e Af), then we obtain almost surely a good estimate of f f dp, for n sufficiently large. However, except for special cases, simulating a MC on a space X as, say 1 m , is not an easy task in general, even for small m. Moreover, even if we can simulate the MC e., what we obtain in (12.1.1) is only an estimate of f f dz. Instead of looking for an estimate of f f dp, an alternative approach is to approximate the numerical value f f dp, "directly". In fact, if X is finite and A is unique, then A can even be computed exactly by solving the finite-dimensional linear system p(I — P) = 0;
p(X) = 1; A > 0;
(12.1.2)
176
Chapter 12. Approximation Procedures for Invariant Probability Measures
see (10.1.1). However, solving (12.1.2) exactly becomes virtually impossible if X is countably-infinite or any other "large" set. One may thus try to "approximate" p (or f f dp) by solving finite-dimensional linear systems that approximate in some sense the original (large or infinite-dimensional) linear system (12.1.2). Note that in the latter approximation approach, one obtains a numerical approximation of the value f dp rather than a statistical estimate as in the former simulation approach. If the MC has several (unknown) invariant p.m.'s, one may wish to obtain upper and/or lower bounds on sup f dp, where the "sup" is taken over the set of all invariant p.m.'s for P. In this case, the simulation approach is not quite satisfactory because it only provides an estimate of f f dpo for some invariant p.m. po which depends on the initial state &) of the simulated sample-path. In contrast, we shall see that the proposed approximation schemes do provide such bounds. This chapter is organized as follows. In §12.2 we state the problem and provide some intermediate results needed in later sections. In §12.3 we propose a numerical approximation scheme based on a sequence of larger and larger finitedimensional linear programs. Under some conditions, the resulting sequence converges to the desired value. In §12.4 we provide an alternative approximation scheme for MCs with a weak-Feller t.p.f. P that maps polynomials into polynomials. This latter approach is based on the moments of the unknown p.m. p, and so, instead of a sequence of linear programs we obtain a sequence of semidefinite programs whose solution does not require discretizing the state space as in the former approach.
f
12.2 Statement of the Problem and Preliminaries Let X be a LCS metric space with Borel a-algebra B, and consider a MC on X with t.p.f. P. Let M(X), B(X), Cb(X), Co(X) be the Banach spaces defined in §§1.2.1 and 1.2.2. (In particular, recall (1.2.3).) Given a measurable function f : X —4 IR, suppose that we want to compute f f dp for some invariant p.m. p for P, with f E L 1 (p). Then we may first solve a linear system of the form (12.1.2), i.e., p (I — P) = 0, p(X) = 1,
p e M(X)±.
(12.2.1)
to obtain one invariant p.m. p, and then we compute, or at least approximate, the integral f f dp. In fact, one may wish to solve the following related optimization problem in which, as usual, (p, f) := f fdp, and we use the notation "s.t." for "subject to". P:
minimize s.t.
(P, p(I — P) = 0, p(X) = 1, p e M(X)+
(12.2.2)
12.2. Statement of the Problem and Preliminaries
177
This will provide : —the desired value inf P = (p, f) if p, is unique, —or infm (p, f), where the infimum is taken over all the invariant p.m.'s p, for P for which f is in L i (p) and (p, f) is bounded below. Note that P is an infinite-dimensional linear program; its optimal value is denoted inf P. A linear program is said to be solvable if there exists an optimal solution, say . In this case, P is said to be solvable and we write its value as inf P = min P =
f f d.
The underlying idea. To solve P the idea is to use an aggregation of constraints as well as an inner approximation of p e M(X) as follows.
12.2.1 Constraint-Aggregation When X is a LCS metric space, the Banach space Co (X) is separable, that is, it contains a countable dense subspace
H := {hi , h2 , . . .} c Co (X).
(12.2.3)
By the denseness of H in Co(X), for any two measures ,u, v in M(X) we have
P, = v <=> (1i, h) = (v, h) V h E Co(X) <=> (ii, h) = (v, h) Vh E H. Hence, solving (12.2.2) is equivalent to solving the linear program minimize s.t.
(ii, i)
(11(1- — P), h) = 0 Vh E H, (11,1) = 1, p, E M (X)± . (
12.2.4)
A key difference between (12.2.2) and (12.2.4) is that the latter is an optimization problem with countably many constraints. On the other hand, if in (12.2.4) we consider only a finite subset Hk C H in lieu of H, i.e., we only consider the constraints
(11, ( 1. — P), h) = 0 Vh E Hk C H, then we obtain a linear program with finitely many many constraints. This approximation to (12.2.4) is an aggregation scheme because we "aggregate" the infinitely many constraints ti(I — P) = 0 into finitely many of them. Further, one may even decide to relax the constraints (p,(/ — P), h) = 0 for h e Hk, to obtain the weaker constraints l(p(/ — P), NI < e Vh E Hk , (12.2.5) for some E > 0. To approximate (12.2.4) we will use the aggregation-relaxation scheme (12.2.5) together with (p, 1) = 1 and p, E M (X)± , which defines a linear program with finitely many constraints.
178
Chapter 12. Approximation Procedures for Invariant Probability Measures
12.2.2 Inner Approximation in M(X) The space M(X) has also an important, well-known property (see, e.g., Billingsley [14]). Namely, its subset P(X) of p.m.'s on X is such that every p.m. p, E P(X) can be "approximated" by p.m.'s with finite support in the following sense. As X is a LCS metric space, it contains a countable subset 5e (12.2.6)
:= {xi,x2,• • •}
dense in X. Proposition 12.2.1. Let p, E P(X) be an arbitrary, fixed, p.m. on X, and let X = {x i } be as in (12.2.6), i.e., a countable dense subset of X. Then there exists a sequence {p,} in P(X) such that:
has finite support (a) For every n = 2, of the form p n = Ein_ i Aril ax„ with Arii > 0 for all i = 1, . . .n, and (b) The sequence {li n } converges weakly to p, i.e., p n 1.4.10).
that is, p,,, is = 1.
>A
,u, (see Definition
We will also use this fact to build an inner approximation of (12.2.4) by approximating ,u, in (12.2.4) by a p.m. with finite support, which will yield another linear program with finitely many variables, the coefficients {A} in Proposition 12.2.1. Of course, the larger the support, the better the approximation. This is an inner approximation scheme (in M(X)) because we look for solutions p in a proper subset of the initial set of p.m.'s 'P(X). Finally, to approximate (12.2.4), we will combine the aggregation-relaxation scheme (12.2.5) with the just mentioned inner approximation scheme to finally obtain finite linear programs, i.e., linear programs with finitely many constraints and variables, that in principle are solvable even for a very large number of constraints and variables. We next show that under appropriate assumption on the function f, the above approximation scheme indeed works.
12.3 An Approximation Scheme Throughout this section, f : X R denotes a given nonnegative measurable function; additional assumptions on f are introduced below. We first examine an aggregation scheme which replaces the original infinitedimensional constraint p(/ — P) = 0 in (12.2.2) with finitely many constraints.
12.3. An Approximation Scheme
179
12.3.1 Aggregation Consider the following aggregation Pk of P. minimize (1--(I — P),
= 0 Vh E Hk, (i 1 , 1 ) = 1,
p > 0,
(12.3.1)
where Hk := h2,. . .,hk} C H and H C Co (X) is as in (12.2.3). From Definition 1.4.14(b), recall the following.
Definition 12.3.1. A function f : X
R is said to be inf-compact if the set
Kr :=
r}
E Xlf (x)
is compact for every scalar r. As noted after Definition 1.4.14, an inf-compact function is also a moment.
Proposition 12.3.2. Assume that f is inf-compact and nonnegative. Moreover, P is weak-Feller and admits art invariant p.m. ,u, with f f dp, < oo. Then (a) Pk is solvable for every k = 1, 2, . . . , and so is P. Further, inf Pk = min Pk
I
min P
as k
oo.
(12.3.2)
(b) Let p,k be art arbitrary optimal solution of Pk. Then every weak accumulation point of the sequence fp,k1 is an optimal solution of P. Proof. (a) Let us first note the following. By the assumption on p, the linear program P and its aggregation Pk each has at least one feasible solution, and 0 < inf Pk < inf P < (,u,, f) < Moreover, as Hk C Hk+i for all k, the values inf Pk form a nondecreasing sequence bounded above by inf P, and, therefore, there exists p* > 0 such that inf Pk I p < inf P.
(12.3.3)
We next prove (a). Fix an arbitrary k > 1. Let lin E P(X) be a minimizing sequence for Pk that is, pn is feasible and f fdp n j, inf Pk. By (12.3.3), there exist no, mo such that (An , f) < mo for all n > no. Hence, as f is a moment, from Proposition 1.4.15 it follows that the sequence {p m } is tight. Therefore, by Prohorov's Theorem 1.4.12, there is a p.m. p, and a subsequence In3 1 such that tin,= p. By the weak-Feller property, (I — Cb(X) as hEHC Co(X), so that for every h E Hk (ittri3
(I — P), h) = (pn, , (I — P)h) --> (, (I — P)h) = ((I — P), h),
which proves that p, is feasible for Pk. In addition, as f is 1.s.c. and nonnegative, from Proposition 1.4.18 we get inf Pk = lim inf (1413 1 f) 3
f).
180
Chapter 12. Approximation Procedures for Invariant Probability Measures
As p, is feasible, it follows that p, is an optimal solution for Pk. This proves the first statement in (a). To prove that P is solvable and (12.3.2), let pk be an arbitrary optimal solution of Pk and consider the sequence -tick 1. By (12.3.3), (p,k , f) < inf P for all k > 1, and so the sequence {AO is tight. Hence, by the same argument used in the p. previous paragraph, there is a subsequence {k 2 } and a p.m. p, such that ,u,k, Fix an arbitrary j > 1. Then there is some index i j such that hi E Hi for all i > ij . Therefore, by the weak-Feller property, as i oo we get (pkz (I — P), h .] ) = (pk „ (I — P)h3 )
(p, (I — P)h i ) = ([(1- — P), h i ).
As j > 1 was arbitrary, it follows that (p,(/ — P)p, h3 ) = 0 for every j, and thus, p, is feasible for P. Again, as f is nonnegative and 1.s.c., we have inf P > p* := lirn inf min Pk, = lirn inf (,u, ki , f) > (p, f). The latter inequality and the feasibility of p, yield (ii, f) = inf P = p", that is, tt is an optimal solution of P and, finally, (12.3.2) follows from (12.3.3). (b) That every weak accumulation point of {pk} is an optimal solution of P follows from the same arguments used in the proof of the second part of (a). The linear program Pk is still infinite-dimensional because the "decision variable" p is in M(X). To obtain a finite-dimensional linear program, we next combine the above aggegation scheme Pk with a "relaxation" and an "inner approximation" in M(X).
12.3.2 Aggregation-Relaxation-Inner Approximation Let X be as in (12.2.6). Instead of Pk, we next consider the optimization problem Pkn(Ek) (with Ek > 0) defined by: minimize Pkn(Ek) : s.t.
Aif (xi) E ni _ Ai [h(xi ) — Ph(x)11 < ek = 1, A i > 0 Vi, in,i
V h E Hk,
(12.3.4)
where xl, x2, , xn e X. Observe that this is a finite-dimensional linear program because there are finitely many constraints and decision variables A1, , An . We have the following. Proposition 12.3.3. Let f and P be as in Proposition 12.3.2, and let in addition f be continuous. Then : (a) For every c k > 0 there is an integer n(ck) such that Pk(k) is solvable, and min Pk n (Ek) < min P ek for all n > n(Ek)• (b) Suppose that E k ,I, 0, and let pk,n, be an optimal solution ofPkri(Ek) for each fixed n > n(ek). Then every weak accumulation point of the sequence {k n ,k = 1, 2, ... } is an optimal solution of P, and limk min Pim (fk) = min P for each n > n(ck).
181
12.3. An Approximation Scheme
Proof. (a) Let p* be an optimal solution of P so that (p*, f) = min P. Let Ki := {x E X f(x) < j}, which is a compact set as f is inf-compact. Moreover, as j —> oo, K3 I X, and so, p*(Kj ) > 0 for all j sufficiently large. In fact, to keep matters simple we shall assume that p* (KJ ) > 0 for all j > 1. The p.m. := p,*(B n Ki )/ au. (K3 ) for all B E B obviously converges weakly to p* (in fact, ,u,j even converges setwise to ,u,*). Hence (jig , f) —> (j*, f) and, in addition, (A3, f) < au* ( 1(3) -1 (A* , f) vi = 1 , 2 ,— .
(12.3.5)
Hence, given Ek > 0, there is some j(k) such that (pj, f) < min P + Ek/2 for all j > j(k). From the weak convergence of pj to p* and the continuity of the functions hi and Phi , i = 1, 2, ... , there is an index j i such that for all j > ji , l(, (I — P)h) — (p,* , (I — P)1)1 < Ek/2 Vh E Hk.
Fix jo > max[j(k), ji]. From Proposition 12.2.1, there is a sequence PO of p.m.'s with finite support in X 11 K30 , that converges weakly to pi o . As the restriction of f to Ki is continuous, and the hi are also continuous, it follows that there is some n(Ek, j o ) such that for all n > n(Ek, jo ), one has (vn , f) — (L 0 , f) and
I (v n, (I P) 11 )
Vh E Hk•
(11.7431( I P)h)I < Ek
Therefore, (v, f) < min + ek and i(vn, (/ — P)h)I < Ek
Vh E Hk,
which proves that vn is feasible for Pkn (f k), and min Pk(Ek) + E k• rz < (b) Choose an arbitrary n > n(ek, jo ), and let /L k be an optimal solution to Pk(€k). Since (jib, f) < min P + ck, we conclude that the sequence { pk} is tight. Consider an arbitrary converging subsequence pk, = p. Using again that f is continuous and nonnegative, from Proposition 1.4.18 it follows that f)
< lim inf
(pk„ f) < min P
i -400
because (Ilk, f) < min P + Ek for every k and e k 1 0. Now pick an arbitrary index j, and note that hj E Hk for all k> j. Therefore, 1(tql (I P)hj)1 <€k
j,
and so the convergence ,u,k, it yields (p, (I — P)h 3 ) = 0. As j was arbitrary, p is feasible for P. This fact and (,u,, f) < min P imply that p is an optimal solution for P. El
182 Chapter 12. Approximation Procedures for Invariant Probability Measures Remark 12.3.4. (a) A crucial hypothesis in Propositions 12.3.2 and 12.3.3 is the inf-compactness condition on f. It was used in combination with the fact that a set H of p.m.'s that satisfy sup per' f fdp, < co is relatively compact (see Proposition 1.4.15 and Theorem 1.4.12(a)). On the other hand, let f be a given inf-compact function, and suppose that P is weak-Feller. Assume that there exist a nonnegative scalar b and a measurable nonnegative function V : X R+ such that
PV (x) < V(x) — f (x) + b
Vx E X.
(12.3.6)
Then, by Proposition 9.3.2, every invariant p.m. ,u, satisfies (A, f) < b. Therefore, instead of the hypothesis (p, < oo in Proposition 12.3.2, one may try to find a suitable "Lyapunov function" V and a scalar b for which (12.3.6) holds. (b) For a given measurable function f on X, one may also wish to maximize (p, f) over the set of all invariant p.m.'s p, for P. The latter problem is, of course, equivalent to minimize —(p, f). In particular, we may wish to both maximize and minimize (p, f) over the set of invariant p.m.'s p, for P so as to obtain upper and lower bounds on (p, f). If f is continuous and X is compact, then, by Proposition 12.3.3, the approximation scheme permits to obtain sharp upper and lower bounds, as both max P and min P can be approximated as closely as desired.
Example 12.3.5. Consider the MC associated with the deterministic logistic map in (6.2.5); see also §11.1. Its t.p.f. is P(x, B) = 1B(4x(1 — x)) for x E X = [0,1] and B E B. Recall that P admits countably many invariant ergodic p.m.'s; see §6.3.2. Let us partition X into n subintervals of equal length. The dense subset H in (12.2.3) is taken to be the basis of the polynomials on [0, 1], that is H = {1,x,x 2 ,...}, so that the set Hk in (12.2.5) consists of the polynomials {1,x,x 2 ,...xk}. In (12.2.2) consider three functions, namely fi (x) := x 2 , 12(x) := x 8 and f3(x) := (x — 0.2)(x — 0.3)(x — 0.4). Notice that the Dirac p.m. 6 0 at x = 0 is an invariant p.m. for P, and, therefore, for the first two nonnegative functions fi and 12, we trivially have min P = 0. Hence, we have chosen to "maximize" (p, f) in the linear program PThk(Ek), and we have even taken ek = 0 for all k > 1. As X is compact and f is continuous, Proposition 12.2.4 is also valid replacing inf with sup and min with max, that is, when we wish to maximize (instead of minimize) (p, f). In this case, sup Pnk (ek) will provide an upper bound on supp (p, f), where the "sup" is taken over all the invariant p.m.'s p for P (see Remark 12.3.4(b)). The results are displayed in Table 12.1. From the results in table 12.1, one may observe that with a fine grid (say, n = 100 or n = 200) one obtains very good upper bounds on sup A (p, fi ) even with a small set H. For fi (x) := x 2 , the values show that the Dirac p.m. 6 3/ 4 at the point x := 3/4 is optimal, and is obtained exactly as it is a grid point when n = 100 or n = 200.
183
12.4. A Moment Approach for a Special Class of Markov Chains
Parameters n=50; k=5 n=50; k=10 11=50; k=20 n=100; k=5 n=100; k=10 n=100; k=20 n=200; k=5 n=200; k=10 n=200; k=20
fi(x)
f2(x)
f3(x)
0.5603 0.5548 0.5546 0.5625 0.5625 0.5625 0.5625 0.5625 0.5625
0.2600 0.2567 0.2566 0.2611 0.2610 0.2606 0.2612 0.2611 0.2611
0.1069 0.1066 0.1065 0.1071 0.1071 0.1070 0.1072 0.1072 0.1072
Table 12.1: Upper bounds on supm (p, f), i = 1, 2, 3
12.4 A Moment Approach for a Special Class of Markov Chains In this section we consider a special class of MCs on X = Rn whose t.p.f. P maps polynomials into polynomials. This class contains, for instance, the MCs associated with the deterministic systems (2.2.6) and the iterated function systems (2.2.7), for which the functions F in (2.2.6) and Fp in (2.2.7) are real-valued polynomials. We will see that in this case, for a given real-valued polynomial p : -> IR, we can obtain upper and lower bounds on (p,,p) by solving semidefinite programs, that is, convex optimization problems on the set of positive semidefinite matrices, for which efficient solution procedures are available (see, e.g., Vandenberghe and Boyd [132]). The polynomial p plays the role of the function f in (12.2.2).
12.4.1 Upper and Lower Bounds Let p : liin IR be a given polynomial, and suppose that one wishes to determine upper and lower bounds on (p, 7)) over the set P 11 (X) C P(X) of invariant p.m.'s for P that have all their moments finite, that is, p, E P 7 (X) if p(I - P) = 0; p(X) = 1; p E M(X) +, (t, x) <00 Va E
,
(12.4.1)
where N := {0, 1, ... }, and for a = (ai , • , an ) e N11 the notation x stands for • 4.. The integral (p, x") := f x' dp, in (12.4.1) is called a moment of p. Observe that when P maps polynomials into polynomials and p, satisfies (12.4.1), we have ,
(p,(/ - P),
Va
= (p, (I - P)x")
E N 11
.
(12.4.2)
Moreover, (12.4.2) defines linear constraints on the moments := (11 ,e)
a
E Nn.
(12.4.3)
184
Chapter 12. Approximation Procedures for Invariant Probability Measures
Let 1, xi, ... x n , xT,x i x2,
xrin xm i — 1 x2, . , x,rn
be a basis for the vector space A m of real-valued polynomials of degree at most m. The dimension of this basis is denoted by s(m). Let lal := Ei ai . A real-valued polynomial p E A m is written as
p(x) =
E lal
with {pc,} E Rs(m) its vector of coefficients. Let p be a real polynomial of degree s, that is, p E A,. Consider the optimization problems maximize {(i, p)i E Pinv(X)}1 minimize { ( au, , p) p , E
P: Q
(12.4.5) (12.4.6)
and, for fixed m E N with 2m > s, the corresponding approximations Pm : maximize
E
PaYa
(12.4.7)
lal<2m
s.t.
= (11 ,x') V lal 5_ 2m,
it E Pinv(X),
and Qm
minimize s.t.
E
pc yo
x c') ya=(it, lal<2m
(12.4.8) V< 2m, j E
(X).
We immediately have inf Qm < inf
< inf Q Vm = 1, 2, .
and SUP P m > sup TPrn+l > sup P Vm = 1, 2, .. . . Hence inf Qm < inf Q < sup P < sup Pm Vm = 1, 2, . . . .
(12.4.9)
Therefore, sup P m (resp. inf Q in ) provides monotonically improving upper (resp. lower) bounds for sup P (resp. inf Q) as m increases. However, the problems Pm and Qm are not directly solvable because of the constraints
= (,x)
Vce E Nn with c:E1 < m,
for some p, E Pinv (X).
(12.4.10)
We next see how to approximate P m and Q m by two related problems with explicit conditions on y that are necessary for (12.4.10) to hold.
12.4. A Moment Approach for a Special Class of Markov Chains
185
12.4.2 An Approximation Scheme As P maps polynomials into polynomials, let d( 13) be the degree of the polynomial Px13 for all 13 E Nn. Let y = {y a } E R 8(2m) , so that lal < 2m. Let 3 E Nn with d(0) < 2m. From (12.4.10) and (12.4.2), (p(I - P),x 13 ) = 0 =
Ay = bo,
for some scalar bo and some row vector Ao E Eks(2m) . Therefore, the constraint p, E Pinv (X) is replaced with the invariance condition
VO s.t. d(0) < 2m
Aoy = bo
on the moments. It remains to give necessary conditions for y to be the vector of moments up to order 2m of some p.m. p, E P(X). These conditions require the moment matrix defined below to be positive semidefinite. Moment matrix. Given a s(2m)-sequence {1, y a }, let Mm (y) be the moment matrix of dimension s(m) labelled by (12.4.4). For instance, for illustration purposes and clarity of exposition, consider the 2-dimensional case. The moment matrix Mm (y) is the block matrix {M,, i (y)} 0
111 ,3(y) =
Yi+j-1,1
Yi+j,o Yi+j-1,1
•
Yi,i
Yi±j —2,2 • • •
Yi
j
1
(12.4.11)
,
Yi+j-1,1
•
_
To fix ideas, with n = 2 and m = 2, one obtains 1
Y10 YO1
Yb M2 (y) =
I
Y20
Yll
YO2
Y20
Yll
Y30 Y21 Y12
YO1
Yll
Y02
Y21 Y12 YO3
Y20
Y30 Y21
Y40 Y31
Y1 1
Y21 Y12
Y31 Y22 Y13
Y12 YO3
Y22
I
Y02
I
Y22
Y13 YO4
Another, more intuitive, way of constructing M m (y) is as follows. If Mm (y)(1, i) ya and Mm (y)(j,1) = yo , then Min(Y)(i, i) = Ya+,3
with a+3 = (al + 131, • • • ,
+ On).
(12.4.12)
186
Chapter 12. Approximation Procedures for Invariant Probability Measures The moment matrix Mm (y) defines a bilinear form (.,
.)y
on A m , by
(q(x), y(x)) y := (q, Mm (y)v) , q(x), v(x) E A m , where the first scalar product (., .) y is for polynomials in A m whereas the second scalar product (., .) is the usual scalar product of vectors in Rem ) . Thus, if y is a sequence of moments of some measure m y , then (I7, Mm (y)q) = I q(s)2 py (dx) > 0,
(12.4.13)
so that Mm (y) is positive semidefinite, denoted Mm (y) >-- 0. Finally, P, is replaced with the semidefinite program IP, : maximize
Pa yo lal<2m
s.t.
Ay = bo V13 s.t. d(0) < 2m, Mm (y) 0,
(12.4.14)
whereas O m is replaced with the semidefinite program OC,11- 7n :
minimize
E
PaYa
ickl< 2m
Ay = bo V i3 s.t. d( 13) < 2m, Mm (y) > 0.
s.t.
(12.4.15)
The semidefinite program 'P m (resp. 4- 5m ) provides monotonically improving upper (resp. lower) bounds on P (resp. Q). Under some additional assumptions one may get sharp bounds.
12.4.3 Sharp Upper and Lower Bounds In this section we prove that for a certain class of MCs with weak-Feller t.p.f. P, the upper and lower bounds provided by sup 'Pm and inf Qm are "sharp" in the sense that inf inf Q and sup Pm ,I, sup P,
dm i
as m --- co. Let X = Rn, and suppose that we are interested in the invariant p.m.'s p, for P that have all their moments finite. For instance, consider the function f : IV —> IR+ defined by n
X I— f(x) :=
x i=1
e Rn,
(12.4.16)
12.4. A Moment Approach for a Special Class of Markov Chains
187
for some > 0. If (12.3.6) holds for the function f in (12.4.16) and for some Lyapunov function V : X le, then every invariant p.m. p for P satisfies
f f dp,
b
(12.4.17)
for some b > 0 (see Remark 12.3.4), and, therefore, every invariant p.m. for P has all its moments finite. Let p, be an arbitrary invariant p.m. for P, and let yi(2k) (j) := f x,?,k dp for all i = 1, ...n and k = 1,2, .... (12.4.17) imposes a restriction on the growth of the absolute moments of p; in particular, (12.4.17) implies
E co
[y1(, 2k)( ia) -1/2k
(12.4.18)
=00
k=1
for all i = 1, ...n, which is a multivariate analogue of Carleman's condition for univariate moment sequences (see Berg [9, p. 117]). We will use (12.4.18) in the proof of Theorem 12.4.1, below, because it implies, in particular, that the p.m. p is completely determined by its moments (see, e.g., Feller [38, pp. 514-515] and Berg [9, p. 117]).
4 1V
Let y,I 2k) be the variable y, corresponding to the monomial in the basis (12.4.4)). Then define the new version of the semidefinite programs (12.4.14) and (12.4.15) as P'm : maximize
E
PaYa
lal<2m
s.t.
= 10 0
VO S.t.
d(0)
< 2m,
(12.4.19)
Mm(Y) 0,
k=1722/0;.yi(2k) < b,
E1 Ern and Q'm
minimize s.t.
E
PaYct
Afly = bfi Vj S.t. d(0) < 2m, 0, Mm(Y) Ein=1 Em k=1 ( -y2 2:), ek) < b,
(12.4.20)
respectively.
Theorem 12.4.1. Let be a MC on X = le with a weak-Feller t.p.f. P that maps polynomials into polynomials. Let p: X —> R be a real-valued polynomial of degree s. Assume that the Lyapunov condition (12.3.6) holds with f as in (12.4.16), and let P'm and Q'm be as in (12.4.19) and (12.4.20), respectively. Then, (a) Pmand Q'm are solvable for all 2m> 8.
188
Chapter 12. Approximation Procedures for Invariant Probability Measures
(b) P and Q are solvable, and min Qin., min Q and max Pim, J. max P, as m oo.
(c) If P admits a unique invariant p.m., then min Q = max P min Qin '
p*
and max Irrn J p* , .
p* , and
as m oo.
Proof. (a) As P is weak-Feller, from the Lyapunov condition (12.3.6) it follows that all the invariant p.m.'s for P satisfy (12.4.17) (see Remark 12.3.4). and let To prove that P',.„ is feasible, take an arbitrary invariant p.m. y := { y,(p)} be the infinite vector of all its moments. From (12.4.17) we have 2k
Ii 00
ii
i=1 k=0
y(2k) (it) < b.
( 72 k )!
(12.4.21)
Therefore, the truncated vector of moments up to order 2m is feasible for both Pim, and qm . Next let y E 11 s(2m) be a feasible solution of P in ' . The set of feasible solutions of Pin, is compact because of the third constraint in (12.4.19) in Irrn , which implies that for every i = 1, ...n
yi(2k) < (2K).ory 2k 7 \
/
Vk= 1,2,....
(12.4.22)
From this fact together with M m (y) 0 and the definition of Mm (y), it follows that the whole diagonal of Mm (y) is nonnegative and bounded. By Mm (y) 0 again, we conclude that all the entries of M m (y) are bounded, and thus, the set of feasible solutions of P compact. Hence n i is solvable, and, with similar arguments, so is Q. This proves (a). ' , and (b) For each 2m > s, let ym E R s(2m) be an optimal solution of P m extend the vector ym- to an infinite vector ym = {yln} E by completing with zeros. Consider the sequence {ym} c 1R 00 In (12.4.22) we have already seen that all the entries of M m (y) are bounded. Fix an arbitrary q E N. As Mq (ym) is a submatrix of Mm (ym) for all m > q, it follows that the first s(2q) coordinates of ym are uniformly bounded in m. Hence, by a standard diagonal argument, there is a subsequence {mk} and a vector y* E 118' such that k
y7
Vi = 1,2,....
(12.4.23)
Let y*(m) E R s(2m) be the first s(2m) coordinates of y*. From (12.4.23) and Mm (ym) 0 it follows that
lum y*(m)) (
V2m > s.
(12.4.24)
12.4. A Moment Approach for a Special Class of Markov Chains
189
Moreover, (12.4.22) implies that Carleman's condition (12.4.18) holds for y* E which in turn implies that y* is the infinite vector of moments of a unique (or determinate) p.m. ,u on Rn (see Berg [9, Theor. 5, p. 117]). In addition, fix an arbitrary 0 E Nn. As ymk is an optimal solution of Irnik it follows that Aoymk = bo for k sufficiently large. Hence from (12.4.23) again, we obtain Aoy* = bo, that is (,u(I — P), x 13 ) = 0. (12.4.25) As 0 in (12.4.25) was arbitrary, it follows that ttP and ,u have the same moments. But from Carleman's condition (12.4.18), p (and hence btP) is completely determined by its moments (see again Berg [9, p. 117]), and thus, p,P = ,u, which proves that p is an invariant p.m for P. Finally, as p is a polynomial, by (12.4.23) we also have max P'nik
= E PaVank
= f P d/-1 =
PaY
P),
ial<s
IcIs
and thus, as max P m> sup P for all 2m > s and p is feasible for P, it follows that ( au, p) = sup P = max P. This proves that p is an optimal solution of P and that max Pin, 1 max P. The same arguments also apply to min Q'm with obvious changes. Finally, (c) follows from (b) when p is unique. Observe that the approximation scheme in this section requires —the function f in (12.2.2) to be a polynomial, and —the t.p.f. P to map polynomials into polynomials, whereas the approximation scheme in §12.3 can handle functions f in a larger class, and P is only assumed to be weak-Feller. However, for convergence of the latter approximation scheme one must impose restrictions on f (e.g., inf-compactness in Proposition 12.3.3 for the minimization case). On the other hand, for the moment approach, and under the assumptions of Theorem 12.4.1, one obtains sharp upper and lower bounds. Example 12.4.2. Consider the logistic map in Example 12.3.5. As X is the compact space [0, 1] c R, the semidefinite program rr,,, is the same as Pm in (12.4.14), i.e., y2k) we do not need to introduce the (additional) third constraint on the variables in (12.4.19). It suffices to impose that all the variables yi are in [0, 1]. In fact, one can instead impose the additional constraints Bm,(y) 0 and Mm _ 1 (y) — Bm,(y) 0, where the matrix B m is deduced from the moment matrix Mm by
Bm (y) :=
Y1
Y2
Y2
Y3
Yn
Yn+1
Yn •
• •
Yn+1 Y2n-1
(12.4.26)
190
Chapter 12. Approximation Procedures for Invariant Probability Measures
Indeed, (12.4.26) will ensure that { yi, y2,,_11 are the moments of a p.m. supported in [0, 1] (see, e.g., Curto and Fialkow [27, p. 622]). To compare with the methodology of §12.3, we consider the same functions (x) := x 2 , f2(x) = x 8 and f3(x) := (x — 0.2)(x — 0.3)(x — 0.4) for the criterion f fdp, to maximize in Pm . We may solve ir°,, for several values of the parameter m (that is, the number of moments considered is 2m) and several values of the number k of moment constraints iloy = too (or (p(I — P), x 3 ) = 0, j = 1, ... k). The results are displayed in Table 12.2. We can observe that we obtain very good bounds with few Parameters k=4; m=4 k=4; m=5 k=5; m=5
fi (x) 0.5625 0.5625 0.5625
f2(x)
h(x)
0.2613 0.2613 0.2612
0.10875 0.10875 0.10875
Table 12.2: Upper bounds for sup o (i f), i = 1,2,3
moment constraints (only 4 or 5). The results are consistent with those obtained for the linear programs in Example 12.3.5; see Table 12.1. For the function the invariant p.m. that maximizes ( au, fi ) is the Dirac measure .5 3/4 at the "fixed point" x = 3/4, and the exact value is obtained with k = 4 moment constraints, whereas this was not so for the linear programs even with n = 50 because the point x = 3/4 is not a grid point when n = 50 (see Table 12.1).
12.5 Notes The results in §12.3 are derived from the more general framework in [63], which deals with general linear programs in infinite-dimensional spaces (see also Hernandez-Lerma and Lasserre [64, 62] for approximation schemes for controlled Markov processes in metric spaces). The results in §12.4 are new. On the other hand, the moment approach in §12.4 was first developed for certain types of continuous time Markov control processes (controlled diffusions, exit time distribution, optimal stopping) on compact metric spaces by Helmes [49] and Helmes, Rohl and Stockbridge [50] but with different moment conditions. For instance, on X = [0,1] they use the so-called Hausdorff moment conditions that state that a sequence y = (yo , y,...) is a "moment sequence" of some measure on [0, 1] if and only if
j=0
3
0,
k = 0, 1, ...
(12.5.1)
(see, e.g., Feller [381), and analogue conditions for the multidimensional case. The resulting approximation scheme is a sequence of linear programs (LPs), whereas
12.5. Notes
191
in §12.4 we obtain a sequence of semidefinite programs. Both schemes have advantages and drawbacks. For instance, it is to be noted that the Hausdorff moment conditions (12.5.1) are numerically ill-conditioned because of the presence of binomial coefficients in (12.5.1). Moreover, the Hausdorff moment conditions are valid for measures on compact boxes [a, b]' (with generalizations to convex polytopes) only, whereas the semidefinite constraints are valid for arbitrary measures. On the other hand, many LP software packages can handle very large LPs which is not yet the case for semidefinite packages.
Bibliography [1] E. Akin, The General Topology of Dynamical Systems, Graduate Studies in Mathematics, American Mathematical Society, Providence, RI, 1993. [2] E.J. Anderson and P. Nash. Linear Programming in Infinite Dimensional Spaces, John Wiley & Sons, 1987. [3] R. Ash, Real Analysis and Probability, Academic Press, San Diego, 1972. [4] I. Assani and J. Wos, An equivalent measure for some nonsingular transformations and application, Studia Math. 97 (1990), 1-12. [5] K. Baron and A. Lasota, Asymptotic properties of Markov operators defined by Volterra type integrals, Ann. Polon. Math. 58 (1993), 161-175. [6] A. Barvinok, Convexity, Duality and Optimization, Lecture Notes, Department of Mathematics, University of Michigan, 1998. [7] V.E. Beneg, Finite regular invariant measures for Feller processes,J. Appl. Prob. 5 (1967), 203-209. [8] A. Ben Israel, Linear equalities and inequalities on finite dimensional, real or complex vector spaces: a unified theory, J. Math Anal. Appl. 27 (1969), 376-389. [9] C. Berg, The multidimensional moment problem and semigroups, Proc. of Symp. in Appl. Math. 37 (1987), 110-124. [10] A. Berman and A. Ben-Israel, More on linear inequalities with applications to matrix theory, J. Math. Anal. Appl. 33 (1971), 482-496. [11] D.P. Bertsekas, Dynamic Programming: Deterministic and Stochastic Models, Prentice-Hall, Englewood Cliffs, NJ, 1987. [12] D.P. Bertsekas and S.E. Shreve, Stochastic Optimal Control: The Discrete Time Case, Academic Press, New York, 1978.
194
Bibliography
[13] K.P.S. Bhaskara Rao and M. Bhaskara Rao, Theory of Charges: A Study of Finitely Additive Measures, Academic Press Inc., London, 1983. [14] P. Billingsley, Convergence of Probability Measures, Wiley, New York, 1968. [15] A.A. Borovkov, Conditions for ergodicity of Markov chains which are not associated with Harris irreducibility, Siberian Math. J. 32 (1992), 543-554. [16] J. Borwein, Weak tangent cones and optimization in a Banach space, SIAM J. Contr. Optim. 16 (1978), 512-522. [17] H. Brezis, Analyse Fonctionnelle: Theorie et Applications, 4eme tirage, Masson, Paris, 1993. [18] A. Brunel, New conditions for existence of invariant measures in ergodic theory, Lecture Notes Math. 160 (1970), 7-17. [19] P.L. Butzer and U. Westphal, The mean ergodic theorem and saturation, Indiana Univ. Math. J. 20 (1971), 1163-1174. [20] R. Cavazos-Cadena, A note on the vanishing interest rate approach in average Markov decision chains with continuous and bounded costs, Syst. Control Lett. 24 (1995), 373-383. [21] R.V. Chacon, Identification of the limit of operator averages, J. Math. Mech. 11 (1962), 961-968. [22] K.S. Chan, A review of some limit theorems of Markov chains and their applications, in: H. Tong, ed., Dimension, Estimation and Models (World Scientific Pub., Singapore, 1993), pp. 108-135. [23] K.L. Chung, Markov Chains with Stationary Transition Probabilities, 2nd ed., Springer-Verlag, Berlin, 1967. [24] O.L.V. Costa and F. Dufour, Invariant probability measures for a class of Feller Markov chains, Stat. Prob. Lett. 50 (2000), 13-21. [25] B.D. Craven and J.J. Koliha, Generalizations of Farkas' theorem, SIAM J. Math. Anal. 8 (1977), 983-997. [26] B.D. Craven, Mathematical Programming and Control Theory, Chapman Hall, London, 1978. [27] R.E. Curto and L.A. Fialkow, Recursiveness, positivity, and truncated moment problems, Houston J. Math. 17 (1991), 603-635. [28] R.E. Curto and L.A. Fialkow, Flat extensions of positive moment matrices: recursively generated relations, Memoirs of the Amer. Math. Soc. 136, no. 648, November 1998.
Bibliography
195
[29] J. Diebolt and D. Guegan, Probabilistic properties of the general nonlinear Markovian process of order one and applications to time series modelling, Rapport Technique #125, LSTA, CNRS-URA 1321, Universite Paris VI, 1990. [30] J. Dieudonne, Sur la convergence des suites de measures de Radon, An. Acad. Brasil. Ci. 23 (1951), 21-38. [31] J.L. Doob, Measure Theory, Springer-Verlag, New York, 1994. [32] M. Duflo, Methodes Recursives Aleatoires, Masson, Paris, 1990. [33] R.M. Dudley, Real Analysis and Probability, Chapman & Hall, New York, 1989. [34] N. Dunford and J.T. Schwartz, Linear Operators, Part I, Wiley, New York, 1957. [35] E.B. Dynkin and A.A. Yushkevich, Controlled Markov Processes, SpringerVerlag, New York, 1979. [36] R. Emilion, Mean-bounded operators and mean ergodic theorems, J. Funct. Anal. 61 (1985), 1-14. [37] G. Emmanuele, Existence of solutions to a functional-integral equation in infinite dimensional Banach spaces, Czech. Math. J. 44 (1994), 603-609. [38] W. Feller, An Introduction to Probability Theory and Its Applications, 2nd ed., John Wiley & Sons, 1966. [39] S.R. Foguel, The Ergodic Theory of Markov Processes, Van Nostrand, New York, 1969. [40] A.G. Gibson, A discrete Hille-Yosida-Phillips theorem, J. Math. Anal. Appl. 39 (1972), 761-770. [41] LI. Gihman and A.V. Skorohod, Controlled Stochastic Processes, SpringerVerlag, New York, 1979. [42] B.M. Glover, A generalized Farkas lemma with applications to quasidifferentiable programming, Zeit. Oper. Res. 26 (1982), 125-141. [43] B.M. Glover, Differentiable programming in Banach spaces, Optimization 14 (1983), 499-508. [44] J. Gonzalez-Hernandez and 0. Hernandez-Lerma, Envelopes of sets of measures, tightness, and Markov control processes, Appl. Math. Optim. 40 (1999), 377-392.
196
Bibliography
[45] P. Glynn, A GSMP formalism for discrete-event systems, Proc. of the IEEE 77 (1989), 14-23. [46] P. Glynn and S.P. Meyn, A Lyapunov bound for solutions of Poisson's equation, Ann. Probab. 24 (1996), 916-931. [47] S. Grigorescu, Ergodic decomposition for continuous Markov chains, Rev. Roum. Math. Pures Appl. XXI (1976), 683-698. [48] A.B. Hajian and Y. Ito, Conservative positive contractions in L 1 , Proc. 5th Berkeley Symp. on Math. Statist. and Prob., Vol. II, Part 2 (1967), 361-374. [49] K. HeImes, Numerical comparison of controls and verification of optimality for stochastic control problems, J. Optim. Theor. Appl. 106 (2000), 107-127. [50] K. Helmes, S. Rohl and R. Stockbridge, Computing moments of the exit time distribution for Markov processes by linear programming, J. Oper. Res. 49 (2001), No 4. [51] 0. Hernandez-Lerma, Adaptive Markov Control Processes, Springer-Verlag, New York, 1989. [52] 0. Hernandez-Lerma and J. Gonzalez-Hernandez, Infinite linear programming and multichain Markov control processes in uncountable spaces, SIAM J. Control Optim. 36 (1998), 313-335. [53] 0. Hernandez-Lerma and J.B. Lasserre, Invariant probabilites for FellerMarkov chains, J. Appl. Math. and Stoch. Anal. 8 (1995), 341-345. [54] 0. Hernandez-Lerma and J.B. Lasserre, Existence of bounded invariant probability densities for Markov chains, Statist. Probab. Lett. 28 (1997), 359366. [55] 0. Hernandez-Lerma and J.B. Lasserre, An extension of the Vitali-HahnSaks theorem, Proc. Amer. Math. Soc. 124 (1996), 3673-3676; correction ibid. 126 (1998), p. 849. [56] 0. Hernandez-Lerma and J.B. Lasserre, Cone-constrained linear equations in Banach spaces, J. Convex Anal. 4 (1996), 149-164. [57] 0. Hernandez-Lerma and J.B. Lasserre, Existence and uniqueness of fixed points for Markov operators and Markov processes, Proc. London. Math. Soc. (3) 76 (1998), 711-736. [58] 0. Hernandez-Lerma and J.B. Lasserre, Discrete-Time Markov Control Processes: Basic Optimality Criteria, Springer-Verlag, New York, 1996. [59] 0. Hernandez-Lerma and J.B. Lasserre, Ergodic theorems and ergodic decomposition for Markov chains, Acta. Appl. Math. 54 (1998), 99-119.
Bibliography
197
[60] 0. Hernandez-Lerma and J.B. Lasserre, Existence of solutions to the Poisson equation in L p spaces, Proceedings of the 35th IEEE CDC conference, Kobe (Japan) (1996). [61] 0. Hernandez-Lerma and J.B. Lasserre, Policy iteration for average-cost Markov control processes on Borel spaces, Acta. Appl. Math. 47 (1997), 125-154. [62] 0. Hernandez-Lerma and J.B. Lasserre, Linear programming approximations for Markov control processes in metric spaces, Acta Appl. Math. 51 (1998), 123-139. [63] 0. Hernandez-Lerma and J.B. Lasserre, Approximation schemes for infinite linear programs, SIAM J. Optim. 8 (1998), 973-988. [64] 0. Hernandez-Lerma and J.B. Lasserre, Further Topics on Discrete-Time Markov Control Processes, Springer-Verlag, New York, 1999. [65] 0. Hernandez-Lerma and J.B. Lasserre, Further criteria of positive Harris recurrence for Markov chains, Proc. Amer. Math. Soc. 129 (2000), 15211524. [66] 0. Hernandez-Lerma and J.B. Lasserre, Fatou's and Lebesgue's convergence theorems for measures, J. Appl. Math. Stoch. Anal. 13 (2000), 137-146. [67] 0. Hernandez-Lerma and J.B. Lasserre, On the classification of Markov chains via occupation measures, Appl. Math. (Warsaw) 27 (2000), 489-498. [68] 0. Hernandez-Lerma and J.B. Lasserre, On the probabilistic multichain Poisson equation, Appl. Math. (Warsaw) 28 (2001), 225-243. [69] 0. Hernandez-Lerma and J.B. Lasserre, Order-bounded sequences of measures, internal report, LAAS-CNRS, 1996 (unpublished). [70] 0. Hernandez, R. Montes-de-Oca and R. Cavazos-Cadena, Recurrence conditions for Markov decision processes with Borel state space: A survey, Ann. Oper. Res. 28 (1991), 29-46. [71] 0. Hernandez-Lerma and R. Romera, Limiting discounted-cost control of partially observable stochastic systems, SIAM J. Control Optim. 40 (2001), 348-369. [72] R.A. Holmgren, A First Course in Discrete Dynamical Systems, 2nd ed., Springer, New York, 1996. [73] A. Hordijk and F. Spieksma, A new formula for the deviation matrix, in: F.P. Kelly, ed., Probability, Statistics and Optimization (Wiley, New York, 1994), pp. 497-507.
198
Bibliography
[74] M. Iosifescu, A basic tool in mathematical chaos theory: Doeblin and Fortet's ergodic theorem and Ionescu Tulcea and Marinescu's generalization, Contemp. Math. 149 (1993), 111-124. [75] Y. Ito, Invariant measures for Markov processes, Trans. Amer. Math. Soc. 110 (1964), 152-184. [76] R.P. Kanwal, Linear Integral Equations: Theory and Techniques, Academic Press, San Diego, 1971. [77] S. Karlin, Positive operators, J. Math. Mech. 8 (1959), 907-937. [78] N.V. Kartashov, Strong Stable Markov Chains, VSP, Utrecht, The Netherlands, 1996. [79] J. Kemeny and L.J. Snell, Denumerable Markov Chains, Springer-Verlag, New York, 1966. [80] T. Komorowski, Asymptotic periodicity of stochastically perturbed dynamical systems, Ann. Inst. H. Poincare 28 (1992), 165-178. [81] S.G. Krein, Linear Equations in Banach Spaces, Birkhauser, Boston, 1982. [82] U. Krengel, Ergodic Theorems, Walter de Gruyter, Berlin, 1985. [83] N. Krylov and N. Bogolioubov, La theorie general de la m,esure dans son application a l' etude des sytemes de la mecanique non lineaires, Ann. Math. 38 (1937), 65-113. [84] H.J. Kushner, Stochastic Stability and Control, Academic Press, New York, 1967. [85] A. Lasota and M.C. Mackey, Chaos, Fractals, and Noise: Stochastic Aspects of Dynamics, 2nd ed., Springer-Verlag, New York, 1994. [86] A. Lasota and J.A. Yorke, Lower bound technique for Markov operators and iterated function systems, Random and Comput. Dynamics 2 (1994), 41-77. [87] J.B. Lasserre, Existence and uniqueness of an invariant probability measure for a class of Feller-Markov chains, J. Theoret. Prob. 9 (1996), 595-612. [88] J.B. Lasserre, Invariant probabilites for Markov chains on a metric space, Statist. Probab. Lett. 34 (1997), 259-265. [89] J.B. Lasserre, A new Farkas Lemma without a closure condition, SIAM J. Contr. Optim. 35 (1997), 265-272. [90] J.B. Lasserre, A new Farkas Lemma for positive semidefinite matrices, IEEE Trans. Aut. Contr. 40 (1995), 1131-1133 .
Bibliography
199
[91] J.B. Lasserre, A theorem of the alternative in Banach Lattices, Proc. Amer. Math. Soc. 126 (1998), 189-194. [92] J.B. Lasserre, Weak convergences of probability measures: a uniform principle, Proc. Amer. Math. Soc. 126 (1998), 3089-3096. [93] J.B. Lasserre, Quasi-Feller Markov chains, J. Appl. Math. Stoch. Anal. 13 (2000), 15-24. [94] J.B. Lasserre and H.C. Tijms, Invariant probabilities with geometric tail, Prob. Eng. Inform. Sci. 10 (1996), 213-221. [95] M. Lin, On the uniform ergodic theorem, II, Proc. Amer. Math. Soc. 46 (1974), 217-225. [96] M. Lin, Quasi-compactness and uniform ergodicity of Markov operators, Ann. Inst. H. Poincare, Sect. B, 11 (1975), 345-354. [97] M. Lin and R. Sine, Ergodic theory and the functional equation (I —T)x = y, J. Operator Theory 10 (1983), 153-166. [98] J. Lindenstrauss and L. Tzafriri, Classical Banach Spaces I and II, SpringerVerlag, Berlin, 1996. [99] G. Lu and A. Mukherjea, Invariant measures and Markov chains with random transition probabilities, Tech. Rept., Dept. of Mathematics, University of South Florida, 1994. [100] Y. Lyubich and J. Zemanek, Precompactness in the uniform ergodic theory, Studia Math. 112 (1994), 89-97. [101] A.M. Makowski and A. Shwartz, On the Poisson equation for countable Markov chains: existence of solutions and parameter dependence by probabilistic methods, Preprint: Electr. Eng. Dept., University of Maryland, College Park, 1994. [102] M. Metivier and P. Priouret, Theoremes de convergence presque sure pour une classe d'algorithmes stochastiques a pas decroissant, Probab. Th. Rel. Fields 74 (1987), 403-428. [103] S.P. Meyn and R.L. Tweedie, Markov Chains and Stochastic Stability, Springer-Verlag, London, 1993. [104] S.P. Meyn and R.L. Tweedie, The Doeblin decomposition, Contemporary Math. 149 (1993), 211-225. [105] J. Neveu, Existence of bounded invariant measures in ergodic theory, Proc. 5th Berkeley Symp. on Math. Stat. and Prob., Vol. II, Part 2, 1967, pp. 461-472.
200
Bibliography
[106] J. Neveu, Sur l'irreducibilite des chaines de Markov, Ann. Inst. Henri Poincare VIII (1972), 249-254. [107] J.R. Norris, Markov Chains, Cambridge University Press, Cambridge, 1997. [108] E. Nummelin, General Irreducible Markov Chains and Non-Negative Operators, Cambridge University Press, Cambridge, 1984. [109] T.V. Panchapagesan, Baire and a -Borel characterizations of weakly compact sets in M (T), Trans. Amer. Math. Soc. 350 (1998), 4839-4847. [110] M.D. Perlman, Jensen's inequality for a convex vector-valued function on an infinite-dimensional space, J. Multivar. Anal. 4 (1974), 52-65. [111] M.L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, Wiley, New York, 1994. [112] D. Revuz, Markov Chains, revised ed., North Holland, Amsterdam, 1984. [113] H.L. Royden, Real Analysis, Macmillan, New York, 1968.
[114] H.L. Royden, Real Analysis, 3rd Edition, Macmillan, New York, 1988. [115] W. Rudin, Real and Complex Analysis, 3rd edition, McGraw-Hill, New York, 1986. [116] R. Serfozo, Convergence of Lebesgue integrals with varying measures, Sankya: The Indian J. of Statist. 44 (1982), 380-402. [117] S.-Y. Shaw, Ergodic projections on continuous and discrete semigroups, Proc. Amer. Math. Soc. 78 (1980), 69-76. [118] S.-Y. Shaw, Mean ergodic theorems and linear functional equations, J. Funct. Anal. 87 (1989), 428-441. [119] S.-Y. Shaw, Uniform convergence of ergodic limits and approximate solutions, Proc. Amer. Math. Soc. 114 (1992), 405-411. [120] S.-Y. Shaw, Convergence rates of ergodic limits and approximate solutions, J. Approx. Theory 75 (1993), 157-166. [121] B. Simon, The classical moment problem as a self-adjoint finite difference operator, Adv. Math. 137 (1998), 82-203.
[122] A.V. Skorokhod, Topologically recurrent Markov chains: Ergodic properties, Theory Prob. App!. 31 (1986), 563-571. [123] A.V. Skorokhod, Lectures on the Theory of Stochastic Processes, VSP, Utrecht, The Netherlands, 1996.
Bibliography
201
[124] J. Socala, On the existence of invariant densities for Markov operators, Ann. Polon. Math. 48 (1988), 51-56. [125] L. Stettner, On the Poisson equation and optimal stopping of Ergodic Markov processes, Stochastics 18 (1986), 25-48. [126] E. Straube, On the existence of invariant, absolutely continuous measures, Comm. Math. Phys. 81 (1981), 27-30. [127] R. Syski, Ergodic potential, Stoch. Proc. Appl. 7 (1978), 311-336. [128] W. Szczechla, On ergodic averages and absorbing sets for positive contractions in L 1 , J. Math. Anal. Appl. 194 (1995), 560-568. [129] H.M. Taylor, A Laurent series for the resolvent of a strongly continuous stochastic semigroup, Math. Programm. Study 6 (1976), 258-263 [130] R.L. Tweedie, Invariant measures for Markov chains with no irreducibility assumptions, J. Appl. Prob. 25A (1988), 275-285. [131] R.L. Tweedie, Drift conditions and invariant measures for Markov chains, Stoch. Proc. and Appl. 92 (2001), 345-354.
[132] L. Vandenberghe and S. Boyd, Semidefinite programming, SIAM Review 38 (1996), pp. 49-95. [133] K. Yosida, Functional Analysis, 6th edition, Springer-Verlag, Berlin, 1980. [134] K. Yosida and E. Hewitt, Finitely additive measures, Trans. Amer. Math. Soc. [135] K. Yosida and S. Kakutani, Operator-theoretical treatment of Markoff processes and mean ergodic theorems, Ann. Math. 42 (1941), 188-228. [136] A.A. Yushkevich, On a class of strategies in general Markov decision models, Theory Prob. Appl. 18 (1973), 777-779. [137] A.A. Yushkevich, Blackwell optimal policies in Markov decision process with a Borel state space, Zeit. Oper. Res. 40 (1994), 253-288. [138] R. Zaharopol, Attractive probability measures and their supports, submitted. [139] C. Zalinescu, A generalization of Farkas lemma and applications to convex programming, J. Math. Anal. Appl. 66 (1978), 651-678. [140] C. Zalinescu, Solvability results for sublinear functions and operators, Zeit. Oper. Res. 31 (1987), 79-101. [141] X.-D. Zhang, On weak compactness in spaces of measures, J. Funct. Anal. 143 (1997), 1-9.
Index The numbers in this index refer to sections
absorbing set, 2.2, 2.3 additive-noise system, 2.2, 5.3 Akin, 5.6 Alaoglu Theorem, 1.3 aperiodic MC, 4.2 Ash, 1.4, 1.6
deterministic system, 2.2 Dieudonne, 1.5 Doeblin decomposition, 4.5 Doob, 1.3, 1.4., 1.6 dual ergodic theorem (DET), 2.3 dual pair of vector spaces, 1.3 Dunford, 1.4, 1.6
Banach-Alaoglu-Bourbaki theorem, see Alaoglu Theorem Berg, 12.4 Bertsekas, 1.4 Billingsley, 1.4, 12.2 Birkhoff IET, 2.3, 6.3 Bogoulioubov, 5.6, 9.3 Borel space, 1.5 Borovkov, 5.2, 7.4
ergodic measure, 2.4 ergodic theorem Chacon-Ornstein, 2.3 dual, 2.3 individual, 2.3 mean, 2.3, 8.2 pathwise, 2.5 ergodicity property, 2.4 expected occupation measure, 2.3
canonical pair, 8.3 Carleman's condition, 12.4 Cesaro sum, 2.3 Chung, 3.1, 3.6 convergence of functions dominated, 1.5 monotone, 1.5 convergence of measures setwise, 1.3, 1.4 vague, 1.4, 1.4 weak, 1.3, 1.4 countably generated a-algebra, 4.1 Craven, 10.1, 10.6, 11.1
Fatou's lemma, 1.5 Generalized, 1.5 Feller, 12.4, 12.5 Foguel, 2.3, 2.6, 6.3 fundamental matrix, 8.3 generalized Farkas theorem, 10.6 geometric ergodicity, 4.3 Gihman, 2.2 Glynn, 7.1 Grigorescu, 7.2 harmonic function, see invariant func tion Harris decomposition, 4.5
204 Harris recurrence, 4.2 null, 4.2 positive, 4.2 Hausdorff moment condition, 12.5 Hernandez-Lerma, 4.6, 5.6, 6.4, 8.6, 12.5 HeImes, 12.5 Hewitt, 10.6 Holmgren, 6.3, 11.1 Hopf's decomposition, 2.3 individual ergodic theorem (IET), 2.3 inf-compact function, 1.4 vs. tightness, 1.4 invariant function, 4.2 invariant probability measure, 2.2 approximation of, 12.3, 12.4 strictly positive, 10.1 invariant set, 2.2, 2.3 Ionescu-Tulcea, 2.2 iterated function system, 2.2, 6.2 Kakutani, 8.2, 8.4 Kartashov, 9.1, 9.2, 9.4 Kemeny, 3.1, 3.6 Krengel, 2.3, 2.6 Koliha, 10.1, 10.6, 11.1 Krylov, 5.6 Lasota, 2.2, 6.2, 7.2 Lasserre, 1.5, 1.6, 4.6, 5.6, 6.4, 7.4, 8.6, 12.5 Laurent expansion, 8.6 logistic map, 6.2, 6.3, 11.1 Mackey, 2.2, 6.2, 7.2 Markov chain (MC), 2.2 countable state, 3.1 indecomposable, 3.2 irreducible, 3.2 (p-irreducible, 4.2 (p-essentially irreducible, 4.2 periodic, 4.2 recurrent, 4.2 Harris, 4.2 positive Harris, 4.2 quasi Feller, 7.3
Index
strongly ergodic, 9.2 strong-Feller, 4.2, 7.2 strongly stable, 9.2 uniformly ergodic, 9.2 weakly, 9.3 weakly ergodic, 9.3 weak-Feller, 4.2, 7.2 mean ergodic theorem (MET), 2.3 Yosida and Kakutani, 8.4 measure, 1.2 ergodic, 2.4 finitely-additive, 1.2, 6.3, 10.6 signed, 1.3 support of, 5.3 total variation, 1.2 measure-preserving transformation, 2.3 Meyn, 2.6, 4.2, 4.3, 4.5, 4.6, 6.2, 9.1, 9.4 moment function, 1.4 vs tightness, 1.4 ,u-invariant set, 2.4 Neveu, 4.2, 6.2, 6.4, 11.3 Norris, 3.1, 3.6 Nummelin, 4.2, 4.6, 9.1, 9.4 occupation measure expected, 2.3 pathwise, 2.3 operator drift, 11.3 contraction, 2.3 Frobenius-Perron, 2.3, 11.2 Koopman, 11.3 Markov, 2.3 positive, 2.3 power-bounded, 8.3 shift, 2.5 order-boundedness of measures, 1.5 order-lim inf, 10.2 order-lim sup, 10.2 Panchapagesan, 1.4 pathwise ergodic theorem, 2.5 Perlman, 11.3 petite set, 4.3
Index Poisson equation (P.E.), 8.2, 9.2 unichain, 8.2 multichain, 8.2 Polish space, 1.4 Portmanteau theorem, 1.4 positive Harris recurrence (P.H.R.), 4.2 characterization of, 4.2, 4.3 probability density, 2.3 invariant, 11.1 strictly positive, 11.2 Prohorov's theorem, 1.4 Rao, 6.3, 10.6 relative compactness, 1.4 resolvent, 8.2, 8.4 Revuz, 2.3, 2.6, 4.2, 4.6, 6.3, 6.4, 9.1, 9.2, 9.4, 10.6, 11.4 Royden, 1.6, 6.3 Rohl, 12.5 Schwartz, 1.4, 1.6 separable measurable space, 4.1 Serfozo, 1.6 Shreve, 1.4 Skorohod, 2.2, 10.4 small set, 4.2 Snell, 3.1, 3.6 stochastic kernel, 2.2 Stockbridge, 12.5 strong law of large numbers, 2.5 tightness, 1.4 total variation norm, 1.4 transient set, 4.5 uniformly, 4.5 transition probability function (t.p.f.), 2.2 mean ergodic, 8.4 Tweedie, 2.6, 4.2, 4.3, 4.5, 4.6, 6.2, 9.1, 9.4 Vitali-Hahn-Saks theorem, 1.3 w-geometric ergodicity, 4.3 weak convergence, 1.3 of measures, 1.3, 1.4 weak topology, 1.3
205 weak* topology, 1.3 Yosida, 2.6, 5.2, 5.3, 5.6, 8.2, 8.4 Yosida's ergodic decomposition, 5.3 Yosida and Kakutani mean ergodic theorem, 8.4 Yushkevich, 8.3 Zaharopol, 4.6 Zhang, 1.4