CHAPTER 1
TRANSITION PROBABILITIES. MARKOV CHAINS
In this chapter we introduce the basic data of our study. Throughout the sequel a measurable space ( E ,8)is assumed given.
1. liernels. Transition probabilities
+
Definition 1.1. A kernel on E is a mapping N from E x 8 into  a, I.. such that: (i) for every x in E , the mapping A t N ( x , A ) is a measure on 8 which will often be denoted by N ( x , * ) ; (ii) for every A in &, the mapping x N ( x , A ) is a measura.ble function with respect to 8 which will often be denoted by N (  ,A ) . f
+
The kernel N is said to be positive if its range is in [0, a].It is said to be afiizite if all the measures N ( x , ) are afinite; it is said to be proper if E is the union of an increasing sequence of subsets of E such that the functions N ( , E n ) are bounded. The kernel N is said to be b,ounded if its range is bounded, or in other words, if there is a finite number M such that IN(x, A )I M < co for every x in E and A in 8.A bounded kern'el is a proper kernel and a proper kernel is afinite, the converse statements being obviously wrong. If N is positive, then N is bounded if and only if the function N(* , E ) is bounded.
<
Definition 1.2. In the sequel we shall deal mainly with positive kernels. If f is in b,, it is then easily seen b y approximating f with simple functions that one defines a function in 8, denoted N / or N ( / )by setting
By defining Nf = Nf+  Nf, we may extend this t o every function in 8 such that N f + and N f  are not both infinite. We sometimes write N ( x , f ) for N f ( x ) ;in particular N ( x , A ) = Nl,(x). 8
CH. 1, $1
KERNELS. TRANSITION PROBABILITIES
9
In the same way, let m be a positive measure on 6, and define for AEB,
mN(A) =
5.
m(dx) N ( x , A ) = ( m , N ( * , A ) ) ;
it is easily seen that mN is a positive measure on 6,and as above this may be extended to signed measures. The two mappings thus defined are linear and, whenever the two members are meaningful, we have
Notice further that if we call E, the Dirac measure of the point x , we have E,N( * ) = N ( x , * ). The mappings of b, into itself defined by positive kernels are characterized by the following property.
Proposition 1.3. A n additive and homogeneous ma#$ing V of 8, into itself i s associated with a positive kernel if and only if for every increasing sequence {f,} of functions in 6, one has
Proof. Easy and left to the reader as Exercise 1.9. We proceed to a few examples of kernels.
Examples 1.4. (i) Let A be a positive afinite measure on 8 and n a positive realvalued function defined on E x E and measurable with respect t o the product aalgebra 6 @ 6. One may then define a kernel N on E by setting
Such a kernel is called an integral kernel with basis A. When E = Rd, d 2 3, = ( x  yI d+2, we thus get the kernel of newtonian potential theory. The kernel N is positive and for f E b,,
A is the Lehesgue measure, and n ( x , y )
10
TRANSITION PROBABILITIES. MARKOV CHAINS
CH. 1, $1
If n(x, y ) = u ( x ) b ( y ) , where u, b are two measurable functions on E , then
i
N f ( 4 = a ( x ) QY) !(Y)
WY)
= (fb,A)
44.
In that case we write N = a @ b l , and simply N = a @ 1if b = 1. A case which has been extensively studied is the case where E is countable and d the discrete aalgebra on E. The measure may be taken equal to the counting measure of E (A({%}) = 1 for every x in E ) and the integrals then reduce to sums, that is Nf(4= n(x. Y) f(Y).
2
YEE
But since in that case N ( x , {y}) = n(x, y ) , we shall mix the two notational devices and write more simply
It thus suffices to give the numbers N ( x ,y) to define on E a kernel, which may then be viewed as an infinite square matrix indexed by the elements of E . The measures (functions) will be “row” (“column”) vectors and the operators of Definition 1.2 are just the usual operators on vectors defined by square matrices. (ii) Let G be a multiplicative locally compact semigroup and p a positive Radon measure on the Borel sets of G ; one defines a positive kernel N on G by setting N ( x , A ) = (,u * 4 (4, where
* denotes the convolution in G . For a Borel function f
and for a positive measure m on G , mN = p * m. Such a kernel is called a convolution kernel. The newtonian kernel of (i) is a convolution kernel. The case where G is a group will of course be of special interest in the sequel. We remark that it is not true that Nf = ,u * f since (whenever it makes sense) (P * f )
(4 =
1 f(P4 G
If we call i; the image of p by the mapping x
P(dY). + xl,
then Nf
=
,& * f .
CH. 1. $1
KERNELS. TRANSITION PROBABILITIES
11
This may be put in the following more general setting. We say that G (the elements of which are henceforth written g, g', h,. . .) operates on the topological space M , or that M is a Gspace, if there is a continuous mapping g x x +gx from G x M to M such that (glgz)x = g,(g,x). With a positive measure u , on G we associate a kernel N on M , by setting, for a Bore1 function f on M ,
if m is a positive measure on M then mN = ,u * m, where the convolution is defined by the formula (P
* m, f )
=
5
GxM
*
f k x ) ,u(dd m(dx).
By letting G operate to the left on itself, we see that the former example is a special case of the latter. (iii) A measurable mapping 6 of E into itself ( 6 ~ B / bis) called a point transformation of E . With such a mapping we may associate a kernel by setting ~ ( xA ,) = 1,(e(x)) = ~ o  I ( A ) ( ~ ) *
Definition 1.5. The com9osition or prodzlct of two positive kernels M and N is defined by
MN(x,A ) =
5.
M ( x , dy) N ( Y ,A ) .
It is easily seen that M N is a kernel and we have
Proposition 1.6. The comfiosition of positive kernels i s a n associative operation. Proof. By approximating f E 8, by simple functions, it is easily checked that ( ( L M ) N f) = ( L M )( , N f ) = L( * , ( M N f ) )= ( L ( M N ) f) , which is the desired conclusion. From now on, unless the contrary i s stated, we deal only with positive kernels. By virtue of the preceding proposition we may therefore define the powers N n of a positive kernel N ; they are the kernels defined inductively by the formula N"(x, f ) = N ( x , N"'f) = N"'(x, N f ) .
12
TRANSITION PROBABILITIES. MARKOV CHAINS
CH. I, $1
For I J = 0, we set N o = I, where I(%, ) = E,( * ). The convolution powers of a positive probability measure p on a group will be denoted ,u* or more simply p”. Let us give yet another definition that we shall need in the sequel.
Definition1.7. Let M and N be two kernels; we say that kl is smaller than N and write M N if, for every f E b,, we have Mf N f . We write M < N if in addition there exists an f E 8, such that Mf < N f .
<
<
The following definitions are basic.
<
Definition 1.8. A kernel N such that N ( x , E ) 1 for all x in E is called a transition Probability or a submarkovian kernel. I t is said to be markovian if N ( x , E ) = 1 for all x in E. In the sequel we shall often write T.P. instead of writing in full the words “transition probability.” Throughout almost all the sequel our basic datum will be a transition probability, denoted by the letter P , the properties of which we shall study from the probabilistic point of view as well as from the potential or ergodic theoretical points of view. The powers of P will be denoted P , rather than Pn;this integer n will appear as a “time” in the sequel. We close this section with a few useful remarks. If P is a T.P., the operators associated with P according to Definition 1.2 will also be denoted by P. They are $ositive operators, that is, they map positive functions (measures) into positive functions (measures). Moreover, they are linear and continuous operators on the Banach spaces bb and bA(b), and their norm is less than or equal to 1. This may be stated: P is a positive contractiolz of these Banach spaces. Finally notice that the product of two T.P’s is itself a T.P.
Exercise 1.9. Prove Proposition 1.3. [Hint. Define the kernel N by setting N ( x , A ) = V l , ( x ) . ] Exercise 1.10. By using the convolution kernels associated with the three following measures on R, prove that Proposition 1.6 may fail to be true if the kernels are not positive: (i) the Lebesgue measure, (ii)  E ~ (iii) , the restriction of the Lebesgue measure to R,. Exercise 1.11. Compute the powers of the kernels defined in Example 1.4 (ii).
CH. 1, 52
HOMOGENEOUS MARKOV CHAINS
13
Exercise 1.12. If N = a @ 3, compute M N and N M for an arbitrary positive kernel M .
Exercise 1.13. If N is the kernel of Example 1.4(iii),prove that Nf WZN= ~ ( w z ) .
=f
0
8 and
Exercise 1.14. If E is countable and Pis a T.P. on E written as a matrix, then Pn can be written as the nthpower of this matrix. Exercise 1.15. For any Bore1 function on a group G , define T,f by T,f(x) = f ( x g ) . Prove that a kernel N on G is a convolution kernel as defined in 1.4(ii) if and only if T E N = NT,. Exercise 1.16. Let M and N be two kernels and suppose that N is an integral kernel; prove then that M N is an integral kernel. Exercise 1.17. Let P be a T.P. on ( E , 8). A subaalgebra B of B is said t o be admissible for P i f : (i) it is countably generated; (ii) for any A E 99 the function P ( * , A ) is @measurable (in other words P is a T.P. on ( E ,B ) ) . Prove that any countable collection of sets in d is contained in an admissible aalgebra. [Hint: The smallest algebra go containing the given collection and all the sets { x : P(x, A ) I } for rational I and A in go is countable. The aalgebra is generated by BO.]
<
Exercise 1.18. Let N and A be two positive kernels on ( E , 8).Prove that ( N A ) "N satisfies the relation the kernel S =
znaO S
=
N
+ NAS
=
N
+ SAN.
If B is another positive kernel, then
C (SB)"S = C ( N ( A + B))"N.
n>O
n>O
2. Homogeneous Markov chains Let (Q, 9, Po) be a probability space and X = {X,},,, a sequence of = a(X,, m n) random variables defined on Q with their range in E. Let 9, and 9, be an increasing sequence of aalgebras such that g , , D . F , , f o r every n.
<
14
T R A N S I T I O N PROBABILITIES. MARKOV C H A I N S
CH. 1, $2
Definition 2.1. The sequence X = {X,},,, is said to be a Markov chain with respect to the aalgebras 9, if, for every n, the aalgebras 9, and a(Xm,m n) are conditionally independent with respect to X,; in other words, if for every A E 9,, and B E a(X,, m n)
>
I
I
I
P,[A n B X,] = P,[A X,] P,[B X,]
as.
<
If 9, = 9,, we say simply that X , is a Markov chain; the “past”a(X,, m n) and the “future” a(X,, m 2 n) then play totally symmetric roles in this definition, the intuitive meaning of which is clear: given the present X,, the past and the future are independent. Notice that if the above property is true with the aalgebras 9,, it is a fortiori true with the aalgebras 9,Finally . we emphasize the importance of Po in this definition; if we change the probability measure Po there is no reason why X should remain a Markov chain. Pro osition 2.2. T h e sequence X i s a Markov chain with respect to the aalgebras 9$f and only if, for every random variable Y Eba(X,, m 3 n), Eo[Y I 9,,] = Eo[Y I X,]
Poas.,
where E , dsnotes the mathematical expectation operator with respect to Po. Proof. Pick A in gnand B in a(X,, m 2 n ) ;then since gn3 a(Xn)
I
E O [ ~7 A B Xnl = E O [ l A
I 1 y n
xnl
= EO[’A E [ 7 B
I ’n] I xnl#
and if the property in the statement is true, this is equal to
which proves that {X,},,, is a Markov chain. Conversely it suffices to show the above property when Y = 1, with B in a(X,, m 2 n), and this amounts to showing that for every A in Yn, IBI
=
EOVA E O V ~
I X~II.
But since {X,} is a Markov chain, the right member is equal to EO[EO[~AE [ I B
1 xnl I X ~ I =I
which completes the proof.
EO[EO[~A
= E,[E,[I,
I Xnl 7B
I Xn11
IX~II =
EOP,
7 B l ~
CH. 1, $2
HOMOGENEOUS MARKOV CHAINS
15
The following definition is basic.
Definition 2.3. The sequence X = {X,},,, of random variables is called a homogeneous Markov chain with respect to the aalgebras 9, with transition Probability P if, for any integers m, n with m < n and any function f E bb, we have EoV(Xm) 3 n 1 = P n  m f ( X m ) P0a.s.
1
The probability measure v defined by v ( A ) = P o [ X oA~] is called the starting measure. If 9, = F,, we say more simply that X is a homogeneous Markov chain with transition probability P. We leave t o the reader as an exercise the task of showing that a Markov chain in the sense of Definition 2.3 is a Markov chain in the sense of Definition 2.1. To this end the following proposition comes in useful.
Proposition 2.4. The sequence {X,],,, i s a Markov chain with transition probability P if and only if for every finite collection of integers to = 0 < tl * * * < t , and functions f o , . . ., f , in b b one has
Proof. If n = 1, the above formula follows a t once from Definition 2.3. Now, applying Definition 2.3, we get
Since f n P 1 Pt,t,l f , is still a function of bb, the “only if” part follows by induction. To obtain the “if” part, it suffices by the monotone class theorem, t o prove that for every integer to = 0 < ti < < tk m < n and functions f o , f l , . . ., f k , f in b b one has 1 . 
<
16
TRANSITION PROBABILITIES. MARKOV CHAINS
CH. 1, $2
but this is an immediate consequence of the above formula.
Remark 2.5. I t is easily seen that the condition in Definition 2.3 is satisfied’ provided it is satisfied for every pair of consecutive integers. The main goal of this section is to show that with every transition probability we may associate a homogeneous Markov chain, which will be one of the main objects of our study. We begin with a few preliminaries. Let P be a T.P. on E . Let A be a point not in E and write E,j = E U { A } and 8, = a(&, { A } ) .We extend P to (Ed,8,)by setting
P(x,{ A } ) = 1  P(x, E ) if x # A ,
P(A,,{ A } ) = 1.
If E is locally compact we choose as A the point at infinity in the Alexandrov’s compactification of E . We introduce the following convention : any numerical function f on E will automatically be extended to E , by setting / ( A ) = 0. Heuristically speaking, P is the tool which permits us t o describe the random path of a “particle” in E. Starting a t x a t (ime 0, the particle hits a random point x1 at time 1 according to the probability measure P(x, * ), then a random point x g a t time 2 according to P ( x l ; ) and so forth. If P(x, E ) < 1, that means that the particle may disappear or “die” with positive probability; by convention it then arrives at the “fictitious” point A , where it stays for ever after. We ‘assume however that P ( x , E ) > 0 for every x in E ; that is, the particle does not die at once with probability one. Definition 2.6. The point A is called the cemetery. We shall rather say “point a t infinity” when E is locally compact. The space ( E , 6‘) is called the state space. We are now going to give a mathematical formulation of the above description. For every integer n 3 0, let (I?:, 8;)be a copy of (Ed,gd);we call (Q, 9) their product space, namely 0 = ES, and F is the aalgebra generated by the semialgebra Y of measurable rectangles of Q. We recall that a measurable rectangle is a set of the form
n:=o
fiAn,
n=O
An€&:,
where it is assumed that A , is different from EZ for only finitely many n.
Definition 2.7. The space 52 is called the canonical #robability space. We call X,, n 3 0, the coordinate mappings of 0.Let w = {x,, n 0) be a point
CII. 1, $2
HOMOGENEOUS MARKOV CHAINS
17
in Q, then X , ( o ) = x , ; we also set X,(o) = d for every o in Q. These mappings X , are random variables defined on 9 with range in E , and are clearly measurable with respect to the oalgebras 9, = cr(Xm,m n). A point o in 9 is referred to as a trajectory or a path.
<
We come to our main result.
Theorem 2.8. For every x in E there exists a unique probability measure P, on (9,9) such that for any finite collection no = 0 < nl < n2 < < n, of integers and every rectangle k
Furthermore for every set A
E
3,the map x
+
Px[A]as &,measurable.
Proof. Equation (2.1) defines clearly an additive set function on 9'which has a unique extension to an additive function on the Boolean algebra d= and the restriction of this set function to each of thenalgebras 9,is probability measure. We still call P, the extended set function. ; this is true for The map x + PJA] is then in & for every A ~ dindeed measurable rectangles and the class of sets B E 9, for which it is true is, for every n, a monotone class. E)L;,and for A ~d To prove the first half of the theorem, we
[email protected] = and (xo, x l , . . . , X,) a finite collection of points in E , we write A ( x o ,x,, . . ., x,) for the set of points on+lin Qn+lsuch that ( x o , x,,.. . , x,, on+l)is in A . The space 9" being isomorphic to 9, we may define a set function on the algebra generated by the rectangles of Qn in the same way as we have defined Y,.This set function will be denoted by Pz.Again we observe that the map x + P=[A]is &measurable for A ~ dMoreover . using the same argument as to prove Fubini's theorem, we can see that for A E & we have
u:==,9,,
n;=,
c
To prove that P , can be extended to a probability measure on 9we have
TRANSITION PROBABILITIES, MARKOV CHAINS
18
CH. 1, 92
to show that it is aadditive on &’. Let { A j } be a sequence in d decreasing to 0 and let us suppose that limj P,[Af] > 0 . By the last displayed formula applied to A’ we see that this implies, since P(x,* ) is a probability measure, that there exists a point f l E E such that lim, P:,[Aj(x)]> 0. As a result A j ( x ) is nonempty for every j ; moreover reasoning with Pi, and { A j ( x ) }as we did with P , and A f we find that there exists a point Z2 E E such that lim ~ i , [ ~ f a,)] ( x , > 0. i
Proceeding inductively, we find that for every n there is a point I n such that A+, Zl,X2,. . ., 2,) is nonempty for every 1. But since each A j depends on only finitely many coordinates it follows that the point w = ( x , Zl,Z,, . . . , Z n , . . .) belongs to every A f which is a contradiction. To prove the second half of the statement, we observe that the class of sets R such that x + P,[B] is measurable is a monotone class which includesd. Definition 2.9. For every probability measure v on ( E ,b),we define a new probability measure P , on (Q, 9) by setting
ttrdwit, tho tnr*nurt+bllltjy Lit ttw p~irr~bltt~ the~trclcrrHlVra (IPIONII $13 Cilr above formula, which clearly defines a probability measure. For Y sx E, we have P , = P,, and if A is the rectangle in Theorem 2.8, then since A = we have
PJAI =
By comparing this relation with that of Proposition 2.4,we can state:
Proposition 2.10. For every Probability measure P, the sequence X
=
{X,),,,
CH. 1, 52
HOMOGENEOUS MARKOV CHAINS
19
i s a homogeneous Markov chain with transition $robability P and starting measure v. It is called the canonical Markov chain with transition Probability P.
Proof. By the usual argument we may replace the sets Ani in the above relation by functions fni, so that X satisfies the condition of Proposition 2.4. Definition 2.11. Let q(o)be a property of w ; then q is said to hold almost surely (a.s.) on A E 3,if the set of o ' s in A for which q(o)fails to hold is contained in a set A , E 9 such that for every x E E , P,(Ao) = 0. If A = Q we simply say "almost surely". We proceed with some more definitions and notation. Let Z be a positive numerical random variable on (52,s). Its mathematical expectation taken with respect to P , will be denoted E,[Z]; if Y = E,, then we write simply E,[Z]. I t is easily seen that the map x E,[Z] is in Q and that +
E,[Z] = Furthermore if f have
E b,,
5.
v(dX) E,[Z].
then f ( X , ) is a random variable on (in,9) and we
Indeed, for f = 7, this'formula is a special case of eq. (2.1), and it may be extended to Q, by the usual argument.
Definit,ion 2.12. The shift operator 8 is the point transformation on n defined bY e({x,, X I , . . ., xn,. . .>) = (xi, ~ 2 , .. ., %,+I,. . .>. It is obvious that 8 E F / F and that X , ( ~ ( W )=) Xn+l(o).We write 8, for the fithpower of 8: 8, = B o 8 * o 8 p times. Clearly X,(e,(w)) = Xn+P(w), which will also be written X , o 8, = X,,,. Since

Or'{X,
EA
}
= {Xn+, E A ) ,
it is easily seen that 8, E cr(Xn,n 2 $)IS. The following proposition gives the handy form of the Markov property and will frequently be used in the sequel.
20
TRANSITION PKOBABILITlES. MARKOV CHAINS
CH. I , $2
Proposition 2.13 (Markov property). For every fiositive random variable 2 on (Q, F), every starting measure v and integer n,
E,[Z
I
P,u.s.
0 , F,] = E,,[Z]
o
on the set { X , # A } . The last phrase is necessary to be consistent with the convention that functions on E , in particular the function E.[Z],are extended to E by making them vanish at d ; and there is no reason why the first member should vanish on { X , = A } . In the most frequent case however, where P is markovian, the event {X,, = A } has zero P,probability for every Y and the above qualification may, and often will, be forgotten in the sequel. Before we proceed to the proof let us also remark that the righthand side of the above relation is indeed a random variable because it is the composite mapping of the two measurable mappings w + X , ( o ) and x + E,[Z]. We also notice that if Z = l(xmsA), A E 8, the above formula becomes
P,CX,+,
EA
1 9,1= P,,,[x,~
E
AI P,a.s.,
which is the formula of Definition 2.3,
Proof of 2.13. We must prove that for any B E F,, JB
z
0
e n l{XneE)dpv =
5.
E,,LZI u v ;
and by the usual extension argument it suffices to prove this relation for the case in which B is a rectangle, namely B = {X,,, E B,, . . . , X , E Bk} with B i e 8,and in which 2 = 1 A , where A is the rectangle used in Theorem 2.8. The result then follows immediately from eq. (2.2). As much as P , our basic datum will henceforth be the canonical chain X associated with P. We shall be concerned with all probability measures P,, and shall use freely the Markov property of Proposition 2.13. Indeed, although the canonical chain is not the only chain with transition probability P , it has the following universal property which allows one to translate any problem on a chain Y to the analogous problem on the canonical chain X .
Proposition 2.14. Let Y be a homogeneous Markov chain defined on the 9robabil
CH. 1, $ 2
HOMOGENEOUS MARKOV CHAINS
21

ity s*ace ( W ,a, Q ) with transition probability P and starting measure v ( ) = Q[Y,E. 1. T h e n the canonical Markov chain associated with P i s the image of Y by the rna$$ing q which sends w E W to the 9oint 0
of SZ
=
=
~ ( w=) (yo(w), Y l ( w ) , **
9
,
Yn(w),. . .)
E:. T h e image of Q by q i s equal to P,.
Proof. The mapping
is measurable because the composite mappings of with the coordinate mappings X , are equal to the random variables Y,. I t is then easily verified that p(Q) = P,.
Exercise 2.15. Prove that a real random variable 2 is u(X,, m urable if and only if Z = 2' o 0, where 2' E 9.
3 n)meas
Exerciso 2.16. A sequence {X,},,, of random variables defined on (Q, 9, P) is a Markov chain of order r if for every B E d and integer n, PIX,+I
E
I
B u(Xm,m
< n)] = P[X,+,E B 1 o(Xm,n  r + 1 < m < n ) ] .
Prove that the sequence of random variables Y, = ( X , + l , . . . , Xn+rl)with range in Eris a Markov chain in the ordinary sense.
<
Exercise 2.17. (1) Suppose that for every pair m n of integers there is a T.P. called P m , , such that Pl,,P,,., = Pl,,. Prove that one can associate with these T.P.'s a nonhomogeneous Markov chain, that is, a sequence of random variables X , defined on a space (SZ,9,P) and such that for f E b b
EV(Xn)I ~(x,, k
Exercise 2.18. Let X be a homogeneous canonical Markov chain and ( W ,d ,Q) a probability space. Let U be a random variable defined on W and endow the space 0 = 9 x W with the aalgebras 3, = u(X,, X I , . . ., x,,U ) , and the probability measures
P
=
9=u
u 59,
(n10
)
P @ Q. Prove that the sequence
{x,}
22
TRANSITION PROBABILITIES. MARKOV CHAINS
CH. I, $2
x,(w,
defined by to) = X,(w), is still a homogeneous Markov chain with the same T.P. with respect to the aalgebras 9,.
Exercise 2.19. If {X,,] is a homogeneous Markov chain, then E[f(X,,) 1 XJ = P,,,,, f(X,) as., but the converse is false as the following example shows. Set E = {1,2,. . ., N } and define B = 52, U Bz where sZ1 = E and Q2 is the set of permutations of E . Define a probability measure P on 52 by setting with (obvious notation) P(W1) =
N2,
P(o~= ) (1  N’) (A’!)’.
< <
Define further random variables X,, 1 n N , with values in E by X,,(wl) = w,, X,(w2) = i if i is the tzth number in the permutation w2. If we define a T.P. on E by P(i,j ) = N  l , prove that
P[X,
=
i I Xn, = i] = P(i,j ) ,
n
2,
although for N 2 3, the sequence {X,} is not a Markov chain. By using the space B x B x B * build an example where {X,} is indexed by K.

Exercise 2.20. The following chain may be seen as describing the evolution of the size of a population where, at each generation, the random number of offsprings of the individuals are independent and equally distributed. I t is called the GaltonWatson chain. The state space is the set N and the conditional probability P[X,+, = x 1 S,] is equal to the law of the sum of X, independent equidistributed random variables of law fi = (#(x), x E N).The T.P. is thus given by P(x,y ) = #*“(y). (1) Prove that for every n there exists a probability measure 9, on E such that P n ( x , Y) = p , * z ( ~ ) . [Hint: Begin by proving that the mapping from Ox into B defined by Xn(p(w1*** *
t
0s)) =
Xn(wJ
+ . + Xn(wz) *
*
sends the product measure P , @ P , @ ... @ P , to P,. This is the mathematical formulation of the following intuitive fact: the chain starting at x behaves as the sum of x independent chains starting at I.] (2) Prove that the generating functions g,,(l) = tX#,(x) are given by the recurrence formula gn+l(t) = g n ( g ( t ) ) = g(gn(t))p
zxsE
where g is the generating function of the measure #. Compute for P1 the
CH. 1, $3
STRONG MARKOV PROPERTY
mean value and variance of to exist.
23
X, as functions of those of X , which are assumed
3. Stopping times. Strong Markov property
Definition 3.1. A stopping time of the canonical Markov chain X is a random variable defined on (52,s) with range in N U ( 0 0 ) and such that for every integer n the event {T = n } is in 9,The . family STof events A E 9 such that for every n, {T = n} n A E 9, is called the aalgebra associated with T . I t is easily verified that F Tis indeed a subaalgebra of 9. The constant random variables are stopping times, and if T ( w ) = 72 for every w E 52, then F T = Fn. The stopping times thus appear as generalizations of the ordinary times. The following examples of stopping times are basic.
Definition 3.2. For A E 8, we call first hitting time of A and first return time of A the random variables defined by T A ( w )= inf{n S,(w)
=
inf{n
0 : X,(w) E A } ,
> 0 : X,(o)
EA},
where in both cases the infimum of the empty set is understood to be
+
00.
I t is readily checked that both variables are stopping times. For example n1
{T,
=
n} =
n {x,E A"} n {x,E A } E 9,.
m=O
In the same way the random variable c ( w ) = inf{n
2 0: X,(o)
= d}
is a stopping time called the deathtime of X . If P is markovian, to m.
+
5 is a.s. equal
Definition 3.3. With each stopping time T we associate the following objects: (i) The random variable X, is defined by setting
X , ( o ) = X,(w)
if T ( w ) = n,
X T ( w )= d if T ( w ) =
+
00.
I t gives the position of the chain at time T , and the reader will easily check that X T E % T / 8 d .
CH. 1. 53
TRANSITION PROBABILITIES. MARKOV CHAINS
24
(ii) The point transformation O,(w) = O,(w)
8T
on 9 is defined by setting
if T ( w ) = n,
8T(o) =
if T ( w ) =
w,,
where w,, is the trajectory { A , A , . . . , A , . . .} of eT E9 19 and that
+
00,
SZ. It is easily seen that
Proposition 3.4. Let S and T be two stopping times; then the mapping S T o Os : w + S ( w ) T(Os(w))i s a stopping time.
+
+
Proof. We have {S
+ Toes
=
n}
=
u {S = p } n { T
0Os
= n $}.
P
The event {S = p } is in 9, c 9,and on {S = p } we have Os
{ T o e s = n  p ) = { T o o , = rt
p}
=
=
8,; hence
q l ( { T = 12  ~ } ) E F ,
since {T = n  $} E .F,,,. Intuitively one should think of stopping times as the first time some physical event occurs and of P Tas containing the information,on the chain up t o time T when this event occurs. The time S T o Os is the first time where the “event T” occurs after the “event S” has occurred. For instance if A E b, n + T , o 8, is the first hitting time of A after time n ; in particular S,’ = 1 T , o el. If A , B E 6, then T , T , 0 8, is the first time the chain hits B after having hit A . Despite its simplicity the following result is basic. It implies in particular that if one starts to observe the chain at a stopping time, the ensuing process is still a homogeneous Markov chain with the same T.P. (cf. Exercise 3.14).
+
+
+
Theorem 3.6 (Strong Markov property). For every real positive random variable Z on (SZ, 9), starting measure v and stopping time T ,
By convention the two members vanish on { X ,
= A}.
The right member is the composite mapping of w
X , ( w ) and x
+
+
E,[Z].
26
STRONGMARKOVPROPERTY
CH. 1, 53
Proof. We have to show that for A
E
F,,
or equivalently
I t suffices therefore to prove that for every n
0 and B
E Fn,
but this is precisely the Markov property of Proposition 2.13.
Definition 3.6. With each stopping time T we associate a new T.P., denoted
PT,by setting for B E 8, PT(%,B ) It is easily seen that if f
E b,,
= J?,[XTEB].
then
PTf(x)
= Ez[f(XT)l.
We recall that by our conventions f ( X T )= 0 on { X , = A } . We further notice that if T = n as., then P, = P,. Finally if A E 8, we write P A instead of P,; this T.P. is called the balayage operator associated with A . Before we state our next result, we introduce the following notation. Let E 8 ;define I , to be the operator of multiplication by l , , I , f ( x ) = f ( x ) if x E A , I , f ( x ) = 0 if x $ A . We may now give for PAthe following analytical expression.
A
Proposition 3.7. For A
E
8, PA
=
2 (IACP)"I,.
n2.O
Proof. Let B
E 8; using
eq. (2.2), we have
26
TRANSITION PROBABILITIES. MARKOV CHAINS
P ( x n  l ? dxn)
CH. 1, 83
IBnA(%n),
which is the desired result. Clearly the measures PA(%,) vanish outside A . Furthermore if x E A , then PA(x, ) = E,; indeed x E A implies P z [ X o= x ] = 1, hence TA = 0 P,as. and consequently X T A= x P,a.s. In the same way, if x $ A , then TA = S A P,as. and P,(x, * ) = PSA(x, * ). We close this section by applying the strong Markov property to compute the products of operators P T . We first notice that if S and T are two stopping times then XT(Os(0))= X s + T o e s ( W ) , which we write simply X T 0 Bs

=
1
xS+ToOs
Proposition 3.8. Let S , T be two stopping times; then PsPT = PS+ToBS. Proof. Let f E bb,. We have, applying Definition 3.6,
We set ITA
=
I, PsA = I, P
The interpretation of the kernel ITA is given in Exercise 3.13.
Exercise 3.9. Let A , B E 8 ;can TAue and TAnB be expressed as functions of TA and TB ? Given A c B , compare TA and T , and prove that PBPA= PA. Exercise 3.10. Let S and T be two stopping times. (1) Prove that inf(S, T ) and sup(S, T ) are stopping times. In particular S A ~tis a stopping time for every n. Moreover Finf(S,T) = 9 s nF T .
27
STRONG MARKOV PROPERTY
CH. 1, 53
(2) I f r E 2 F t s , t h e n r n { S ~ T } € 2 F T . I f S ~ T , t h e n . F t s c ~ 6 , . (3) Prove that the event { S T } is in .Fs n .FT; (4) Prove that the conditional expectations E[ .Fs] and E [ I .FT]commute and that their product is E [ )2Finr(s,T)].
<
I
Exercise 3.11. Let p be a function mapping N into itself. The random variable p ( T ) is a stopping time for every stopping time T , if and only if p enjoys the following property: there is an integer k, which may be co, such that
+
p ( n ) 3 n for n
< k,
~ ( n= )
k for n > k .
If p is now a function mapping Nd into N,then p(T1,T,, . . ., T d )is a stopping time for any duple of stopping times T i if and only if the functions obtained from p by fixing d  1 variables enjoy the above property.
+
Exercise 3.12. (1) Let A E B; prove that T , = n TA 0 8 , on { T , 2 n } . Let A , B E 8 ;has TA T Bo 8 T A the same property as TA? (2) Let T be a stopping time such that T = n T o 8 , on { T > n } . Prove that
+
+
ICT>nl
=
l I T > n  l l * IIT>11
enl.
(3) Let Y be the sequence of random variables defined by
Y,(w) = X,(o)
if T ( w ) > n ,
<
Y,(w) = d if T(o) n.
Prove that Y is a homogeneous Markov chain with respect to the aalgebras P, on (Q, F). When T = T , we can take A" as its state space; prove then that its T.P. is equal to IAcPIAc.The chain Y is said to be obtained by killing X at time TA.
S T Afor n every probability measure
Exercise 3.13. Let A
T I = SA, T ,
=
E
d and define inductively the times
T1
+ SA
0
OF,,.
. ,, Tn = Tn1 + S A
0
8Tnlp..
.
(1) Prove that the times T , are the successive times at which the chain returns in A . (2) Prove that the sequence {Y,= XT,} is a homogeneous Markov chain with respect to the aalgebras 2FT, with T.P. This chain is called the chain induced on A or the trace chain on A .
n,.
Exercise 3.14. Let T be a finite stopping time. Prove that the sequence Y = {XT+n}n>Ois a homogeneous Markov chain with transition probability
28
TRANSITION PROBABILITIES. MARKOV CHAINS
CH. I, 54
P with respect to the aalgebras .FT+n.What can be said if T is not finite ? Exercise 3.16. Stopped chains. If T is a stopping time of X prove that the sequence Y = {XTAn}n>Ois a homogeneous Markov chain if and only if T = T A for a set A E 8.In that case write down the T.P. of the chain Y . Exercise 3.16. Let T be a stopping time and G a real function on SZ x 52 measurable with respect to Sr @ 9. Prove that for any v, f
for w, w' E 52. [Hint: Begin with G ( w , 0 ' ) = ~ ( w $(w'), ) where T E S,.]
Exorcise 3.17. Let T be a stopping time and S a random variable *",measurable and 2 T a.s. Prove that, for f E b+, Ev[f
xS
I FTl
(w)= P S ( ~ I )  T ( ~ ) f( )~ T ,
[Hint: Use the preceding exercise with G(w, w') = f(Xs(aIl(w')).]
(a, F), with range in N u {a},
Exercise 3.18. A random variable L defined on is called a death time if L o 0 = ( L  l)+,that is, L08=Ll (1) Let A
E 6'; prove
ifL21,
L 0 8 = 0 ifL=O.
that the last hitting time of A , namely
>
L A = SUP{% 0, X ,
E
A},
where the supremum of the empjy set is taken equal to zero, is a death time. The death time of the chain is a death time. (2) Prove that X L o 8 = X , on (0 < L} if L is a death time. (3) If L and L' are death times, then L v L' and L A L' are death times; ( L  n)+ is a death time for every n.
4. Random walks on groups and homogeneous spaces In this section we define an important family of Markov chains, which will occur frequently in the sequel both for their intrinsic interest and to provide examples about general results. In the sequel G is an LCCB group and we call 9 the aalgebra of its Bore1 sets. The elements of G will be denoted g, g', h,. . . and the inverse of g by gl. The unit element is denoted e.
RANDOM WALKS
CH. 1, $4
29
Definition 4.1. A right (left) random walk on G is a Markov chain with state space (G, 9)and transition probability E~ * p ( p * EJ, where p is a probability measure on (G, 9 ) which is called the law of the random walk. For the right random walk we have therefore P(g, A ) = .sK * p ( A ) . For h E G we set hA = fhg: g E A } ; we then have P(hg, hA) = P(g, A ) . The right random walk is invariant under left translations (see Exercise 1.15). Of course on an abelian group there is only one random walk of law p.
Proposition 4.2. Let X be the right random walk of law p ; then for every P , the random variables 2, = X;JIX,, n 2 1, are indefiendent and equidistributed with law p. Proof. Let f i , i We have
=
1, 2 , . . ., # be a finite collection of bounded Borel functions.
For every g in G we have E,[f(XG'X,)] = p ( f ) , so that we get inductively P = nEv[fi(zi)I, i=l
which is the desired result.
Remarks 4.3. The random variable X , is thus a s . equal to the product X , Z1 * * Z,, where the Ziare independent with law p. In particular X , is P,as. equal to the product of n independent equidistributed random var

iables. Of course there is a lefthanded version of these results and the left random walk may be written Z , Z,l * * Z, X,. The invariance by translation is also obvious from this relation. We assume now that G operates on the left on an LCCB space M ; let A be the ualgebra of Borel subsets of M . We may associate with p a T.P. on ( M , .A) by setting (cf. Example 1.4 (ii)), for x E M , A E A,

We are going to show an interesting way of constructing a Markov chain with transition probability P.
TRANSITION PROBABILITIES. MARKOV CHAINS
CH. 1, $4
Let X be the left canonical random walk of law p on G . We set
a = M x Q,
30
g,,
= 4 @ 3, = 4 @ S,,, and if v is a probability  measure on ( M , 4 ) we call P , the probability measure v @ P, on (0, F). Next, for 6 = ( x , w ) we set Yo(&)= x and
Y,(&) = X,(O) Yo(&)= X , ( w ) x . Proposition 4.4. The sequence {Yn}n>ois a homogeneous Markov chain with respect to the aalgebras .Fnfor any probability measure P,. Its transition probability is equal to P . Proof. The aalgebra %, is generated by the rectangles and I' E 3,,. For A in 4 we have
I
AXr
where
A
=
7A(ym+n)
dPv
=
y(dx)
5
r
7A(Xm+n(w)
(1 x
I' where (1E
dpe(w)
{g: gx E A } ; but (pm * ex,,) (A)= (pm* E ~ , , X ) ( A ) , so that finally
which is the desired conclusion.
Remark 4.5. The chain Y thus constructed is not the canonical chain associated with P, but it is sometimes useful to know that one can construct a chain associated with P in the above way, for instance when one must deal simultaneously with the random walks on G and on M . In the preceding discussion one could not use the right random walk instead of the left random walk unless G operates on M on the right. We shall, however, show that under an additional hypothesis one may associate with right random walks some interesting random walks on (left) homogeneous spaces of G. We begin with a result of more general scope. Let X be a Markov chain on ( E , 6 ) and a a measurable mapping from ( E , 6 )onto a space (E', 8')such that, for every A' E b',
CH. 1, $4
RANDOM WALKS
31
P ( x,csl(A’)) = P(x‘,al(A’) if a ) . ( and moreover such that for A
E
x:,= a(X,),
= u(x’),
(4.1)
8,a(A) E 8‘. We set
P‘(x‘, A )
=
P(ul(x‘),u  l ( A ) ) ,
where al(x’) is any point in ul({z’}).Thanks to the second property of u, it may be checked that P‘ is a T.P. on E‘, and we have Proposition 4.6. T h e sequence {X:},,, (E’, 8’) with transition Probability P’.
i s a homogeneous Markov chain on
Proof. Let A’ E 8’and P v be a probability measure on the space 0 of the chain X ; we have
pv[x:+, E A‘
19n1
= Pv[c(Xrn+n)
13n1 =
= P,[X,,
=
ul(A‘)]
Pv[Xrn+nEOYA’)
P:[x:, A’],
since it is easily seen from eq. (4.1) that
Pi(%’,A’)
=
P,(csl(x’), al(A’)).
Remark and Examples 4.7. Here also the chain X : is not the canonical chain associated with P’, since the random variables X : are defined on the space D of the chain X . This proposition allows us to construct new chains from already known ones. Let us call symmetric a random walk such that p = 1; where fi is the image of ,u by the mapping x xl. Let X be a symmetric random walk on R or Z. Then we may apply the above result with the map u :x 1x1. We then say that X‘ is obtained from X by reflection at the point 0 . Now let G be a group and K a compact subgroup of G ; let cs denote the canonical, continuous and open mapping G + G/K. If x E G / K , d ( x ) is of the form g K and the T.P. of the right random walk of law p on G satisfies the conditions of Proposition 4.6 if ,u is Kinvariant, that is to say that sk * ,u = ,u for every k E K or equivalently that ,u = mK * p‘, where m K is the normalized Haar measure for K and p’ any probability measure on G. The image of the right random walk on G by u is then a homogeneous Markov chain on G / K .When G is a semisimple Lie group with finite centre and K a maximal compact subgroup, we thus obtain random walks on the Riemannian symmetric space C / K . +
+
32
CH.1, $4
TRANSITION PROBABILITIES. MARKOV CHAINS
We could have taken the image of the left random walk by wellknown equivariance properties of u would then imply that U(2,
z,1*  2, X,) *
= 2, 2,1

U,
but the
21 U ( X 0 )
and we would be in the general situation of Proposition 4.4.
Exercise 4.8. A subrandom walk is a Markov chain on a group G with T.P. * p (or p * E ~ but ) with p(G) < 1. Prove, using the same notation as in Proposition 4.2, that the random variables of any finite collection Z,,,. . ., Z,, are independent on the set {t> nJ. E,
Exercise 4.9. (1) Let X be a right random walk of law p and T a stopping time. Prove, after restricting the probability space to Q, = {T < a},that the variables X,'X,+, are independent of 9,and that Y = X,,, is still a right random walk of law p. [Hint: See Exercise 3.14.1 (2) We assume that the underlying group is R or Z and we define inductively the following sequence of random variables T,(w) = 0, ~ ~ ( =winf{n ) 2 1: X,(o)
> Xo(o)),
T,(w) = inf(n > T,1: X,(w)
> XTfi,(w)},
+
where the infinum of the empty set is taken equal to 03. Prove that the variables T , are stopping times and that the sequences {T,} and {X,,,} are subrandom walks. Under which condition are they true random walks?
Exercise 4.10. Let X be a random walk of law p on G and T , the nthreturn time (cf. Exercise 3.13) to a closed subgroup H . Prove that Y = { X T n } is a subrandom walk on H . Give its law as a function of p and .,I Under which condition is it a true random walk? Exercise 4.11. Let G be a LCCB group which is the semidirect product of two groups H and K.Every element g in G may be written uniquely as a pair (h,k ) , and using the additive notation in K we have (h,k) (h',k') = (hh',hk' k ) . (Example: G is the group of rigid motions of the euclidean plane, H is the group of rotations and K the group of translations.) Let X , = (H,, K,) be a
+
PROPERTIES O F INTEGRAL KERNELS
CH. 1, 55
33
left random walk on G ; then H , is a random walk on H and K , the Markov chain induced (cf. Proposition 4.4) by X , on K . (We recall that K is an invariant subgroup of G and therefore that G operates on K in a natural way.)
Exercise 4.12. One can study the random walks on the spaces ( W , d ,P ) equal to the infinite product (G, 99, P ) ~We . let {Z,},,, be the coordinate mappings, which are clearly independent and equidistributed. (1) The probability measure Pg on (9,9) is the image of P by the mapping from W to 9
(2) Prove that P is invariant under finite permutations of the coordinates in W . (3) An event A E&’ is said to be symmetric if it is invariant under finite permutations of coordinates. Prove that the family of symmetric events is a aalgebra and that if A is symmetric then either P ( A ) = 0 or P ( A ) = 1. This is the socalled zeroorone law for symmetric events. Finally prove that the events in u(Zm,m 2 n) are symmetric. [Hint: To prove the zeroorone law, approximate sets in d by rectangles C depending on the first n coordinates and use the permutation a exchanging 1 a n d n 1,2 andn 2 , . . ., n and 2n.
n;=,
+
+
6. Analytical properties of integral kernels This section should be omitted at first reading. Its purpose is to collect some results which will be useful later and which will then be referred to. Since these results deal mainly with compactness, we recall:
Dcfinition 6.1. A linear and continuous operator from a Banach space into another Banach space is said to be compact if it maps bounded sets onto relatively compact ones. A kernel on ( E , 8 ) is said to be compact if it maps the unit ball 92 of b b into a relatively compact set in bb. A compact kernel is thus a bounded kernel. Let us also recall that an operator with finitedimensional range is compact and that every compact operator is the uniform limit (cf. ch. 6, Definition 3.1) of operators with finite dimensional range. Finally the adjoint of a compact operator is itself compact. We characterize below the compact kernels.
34
TRANSITION PROBABILITIES. MARKOV CHAINS
CH. 1. $5
Proposition 6.2. I f ( E , 8)i s separable, a compact kernel i s a n integral kernel. Proof. Let N be a compact kernel; its adjoint N* is a compact endomorphism of bB*. But since b d ( B ) is closed in bC"* and invariant by N , the operator N * , which is equal to N operating on the left, is a compact endomorphism of b.A(B).AS a result the set { N ( x , * ) : x E E } is relatively compact in b d ( B ) , and consequently there is a probability measure A on 8 such that for every x in E one has N ( x , ) << A. The proposition then follows from the following lemma.

Lemma 5.3. If ( E , 8)is separable, for every probability measure A on d and every proper kernel N on ( E , 8)there exists a function (x, y ) + n(x,y ) which i s B @ &measurable and such that N i s the s u m of the integral kernel with basis A associated with n and of a kernel N 1 such that all measures "(x, ) are singular with res$ect to A.

The function n is called a density of N with respect to A. I t is unique in the sense that if n' is another function with the same properties, then for every x , we have n ( x ; ) = n ' ( x ; ) Aas. Actually, what the lemma says is that one can choose n ( x ; ) within the equivalence class of the RadonNikodym derivative dN(x, * ) / d l in such a way that the resulting bivariate function n is d @ &measurable.
Proof. By hypothesis there exists a sequence of finite partitions Yn of E such that Pn+lis a refinement of Bnand that 8 is generated by 8". A point y in E belongs to one and only one set in Pn,which we call EJ. Our notation will not distinguish between 8" and a ( P ) . Let v be a probability measure on B ; the functions f, defined by setting
u:
fn(Y) fnb)
v(EJ)/A(EJ) if A(EJ)> 0, if A(E3) = 0,
=0
form a positive martingale relative to the aalgebras 8" and the probability measure 1,hence converge Aas. to a limit f , as n tends to 00. For every AE Bnwe have by Fatou's lemma
+
u:
j"
< lim
1 ! *
fn
dA
Pn,this inequality
CH. 1, $5
PROPERTIES O F INTEGRAL KERNELS
36
holds for all sets in 8.Let f be a function such that
<
then, as is easily seen, E[f I Yn] f , Ia.s. and therefore by passing to the f , Ia.s. The function f , being thus the largest (up to limit we get f equivalence) function with this property, is equal to the RadonNikodym derivative of v with respect to 1. Let now N be a bounded kernel; we apply the above discussion to the probability measure P ( x , ) = N ( x , ) / N ( x ,E ) . The functions f , defined by setting
<

f n ( x ,y )
=

P ( x, E;)/I(E;) if R(EY) > 0,
f,(x, y ) = 0
if I(E!)
=
0,
are Q @ &measurable; their superior limit as n goes to infinity is & @ 6measurable and provides the desired function n. I f N is merely proper, we begin by multiplying it on the right by a strictly positive function h such that N h is bounded (see ch. 2, Proposition 1.14). The property may still be extended to some nonpositive kernels.
Corollary 6.4. If ( E , 8)i s separable, then every proper kernel N such that N ( x , ) << I for every x in E is an integral kernel.

The following results will go in the converse direction. We start with a preliminary result which is a generalization of Egoroff's theorem.
Proposition 6.6. Let H be a set of finite functions in 8, compact and metrizable for the topology of pointwise convergence; for every E > 0 there exists a set F E 8 such that R(E)< E and I,(H) is com#act for the to$ology of uniform convergence. Proof. By hypothesis there exists a sequence {x,},,o of points in E which separates H and a countable subset H , of H which is dense in H for the topology of pointwise convergence. We set h, = sup{(/
 g ) : f , g E H and If(xk)  g(xk)l < 2" for k
< n}.
Since H I is dense in H , the supremum may be obtained by considering only the functions of H I ; as a result h, is in 8.Each function h, is finite and moreover h,+, h, and inf, h, = 0. For every sequence {g,} C H which converges pointwise to g E H , we have
<
TRANSITION PROBABILITIES. MARKOV CHAINS
36
CH. 1, $5
the following property: for every n there exists a Po such that $ 2 f i 0 implies (g  g,l 12,. I t follows that for a set F E I,such that {IF h,} converges uniformly to zero, the set 1 , H is compact for the topology of uniform convergence. The desired result then follows from Egoroff's theorem.
<
Theorem 5.6. Let N be a n integral kernel with basis A on ( E , 8)and such that NI is finite; then there exists a n increasing sequence of sets A , in Q szcch that: (i) for every E > 0 there is a n integer n such that A(Ai) < E ; (ii) the kernels I,,, N are comfiact.
Proof. The image N ( 4 ) is equal to the image by N of the unit ball in [email protected]), which is compact and metrizable for the weak* topology a(Lm(A), L1(A)). Since N is a continuous operator with respect to this topology and the topology of pointwise convergence, the set N ( 4 ) is compact and metrizable for the topology of pointwise convergence. By Proposition 5.5 there exists a sequence {A,,} of sets in d with the required properties and such that the sets I,, N(%) are compact for the topology of uniform convergence hence such that the operators I,, N are compact. The preceding results are useful in many situations. In this book we shall use them to prove quasicompactness properties. We are now going to state in a topological setting some properties which may be used to the same end. We assume below that E is an LCCB space and I the aalgebra of Bore1 sets.
Definition 5.7. A submarkovian kernel N on ( E , 8)is said to be (i) Feller if the map x E,N from E to b d ( Q ) is continuous for the strict topology on b d ( B ) , in other words if N f E C ( E )whenever f E C ( E ); (ii) strong Feller if the same map is continuous for the weakstar topology a ( b A ( I ) , b6), in other words if NfE C ( E )whenever f E b b ; (iii) strong Feller in the strict sense if the same map is continuous for the norm topology on bA(b). +
Plainly each of these conditions is more stringent than the previous one. The convolution kernels provide examples of Feller kernels, and even of strong Feller kernels, whenever the relevant measure is absolutely continuous. Examples of kernels strongly Feller in the strict sense will be obtained as byproducts of the following results.
CH. 1, 55
PROPERTIES OF INTEGRAL KERNELS
37
Proposition 6.8. The following two conditions are equivalent : (i) the kernel N i s strong Feller in the strict sense; (ii) the image by N of bounded sets of C ( E ) are compact for the topology of uniform convergence on compact sets. Proof. If f is in the unit ball of C(E) then for every pair (x, y ) in E x E ,
thus functions N f , f in the unit ball of C ( E ) ,are equiuniformly continuous on compact sets and (ii) follows from (i). The converse follows a t once from the relation

11N(x9 )  N ( Y , * )I1 =
SUP(lNf(X)
 N f M l : f E C ( E ) , llfll d 11
and the equicontinuity on compact sets of the functions Nf(f E C ( E ) ,llfll
< 1).
R'emark. The image by N of the bounded sets of b b are also compact for the topology of uniform convergence on compact sets. Theorem 6.9. T h e product of two strong Feller kernels i s strong Feller in the strict sense.
Proof. The theorem follows immediately from the preceding proposition and the next two lemmas, in which N is a strong Feller kernel. Lemma 6.10. From every sequence {g,} of functions in the unit ball 4 of bb, one can extract a subsequence {gi} such that {Ng:) i s pointwise convergent. Proof. Let (x,} be a countable dense subset of E , and set I = 2,2"N(x,, * ). The measures N ( x , * ) are all absolutely continuous with respect t o I. Indeed if f is Inegligible, the continuous function Nf vanishes a t all points x,, hence everywhere. Let now {g:} be a subsequence of {g,} convergent in the sense of a(Lm(A).L1(I)). (We indulge in the usual confusion between functions and their equivalence classes.) Then the sequence ( N g l } converges pointwise. Lemma 6.1 1. Let {g,) be a sequence of functions in % converging pointwise to a function g ; then the sequence {Ng,} converges to N g uniformly on every compact set.
TRANSITION PROBABILITIES. MARKOV CHAINS
38
CH. 1, $5
Proof. It suffices to prove the lemma for the case g = 0. Set h, = supm>,lgnl ; as lNg,l Nh, it suffices to show that {Nh,} converges to zero uniformly on compact sets. Since the functions Nh, are continuous and decrease to zero we conclude the proof by applying Dini's lemma.
<
As an application, let us give the following result. The reader may refer to ch. 2 9 6 for the definition of a resolvent. Proposition 6.12. If the kernels {Va}a,oof a submarkovian resolvent are strong Feller, then they are strong Feller i n the strict sense.
.
Proof. Let p > u ; the map x + E,V,V, is continuous for the norm topology by Theorem 5.9, and the maps x &,Vbconverge uniformly to zero whenever p + m , since IIc,VBI(< pl. The result thus follows from the relation Va = (P  a)Va
J',+
J'b.
Exercise 6.13. If E is an LCCB space, NI is continuous, and N(C,(E)) c C(E), then N is Feller. Exercise 6.14. If G is a group, prove that the convolution kernels E , * ,u on G are Feller. If ,u is absolutely continuous with respect to the Haar measure, then E, * ,u is strong Feller. Prove by an example that it is not always strong Feller in the strict sense. Exercise 6.16. Let M and N be two kernels on the separable space ( E , 8); prove that there exists an & @I &measurable function f and a kernel "such that for every x in E , the measure N1(x, * ) is singular with respect t o M ( x , * ) and
Exercise 6.16. Let N be a bounded kernel taking both positive and negative values. Prove that the map N+ defined by N+(x, ) = ( N ( x , ))+, is also a kernel. As a result, if we set a(.) = IIN(x, the function cc is &measurable. [Hint: See ch. 6 32.1
)\I

Exercise 6.17. Prove the following extension to Lemma 5.3. If there is a probability measure Y and a family of sets E n increasing to E , such that
CH. 1. 56
PROPERTIES O F INTEGRAL KERNELS

39
N ( , En)< a, vas. for every n, then there exist a function n and a kernel N 1 such that
for valmost every x .