# Time changes of Markov chains

## Time changes of Markov chains

Stochastic Processes and their Applications North-Holland Publishing Company TIME CHANGES OF 13 (1982) 189-199 ARKOV 189 CHAINS A.O. PITTENGER ...
Stochastic Processes and their Applications North-Holland Publishing Company

TIME CHANGES

OF

13 (1982) 189-199

ARKOV

189

CHAINS

A.O. PITTENGER Department of Mathematics, University of Maryland-Baltimore County, Catonsville, MD 21228, U.S.A.

Received 10 April 1980 Revised 9 March 198 1

An increasing sequence of random times {T,, TV2 0) is called a Markov time change if {X( T,,)} is a new Markov chain. If the {T,} satisfy certain ‘operational’ requirements such as conditional independence of the T,-past and T,-future given X(T,), then there is an equivalent, algebraic description of the {T,) in terms of a triple (To, S, r), where To and S are splitting times with respect to a set C A further assumption on r makes it easy to check that a triple will generate a Markov time change, and it is shown that processes such as last exit processes and excision processer satisfy this assumption.

AMS (MOS) 1970 Subj. Class.: Primary 6Ob 10, Secondary 1 \$u:; ;EE Markov time changes conditional independence times

60G40

1. Introduction In recent years a great deal of attention has been given to qualitatively different descriptions of random times. For example, in a Markov chain a stopprng time 7’ is defined algebraically by {T = n} E S”, using the usual notation, while a different sort of property is: the process evolves from T in accordance with the original semigroup. An example of the equivalence of different types of definitions is contained in Lemma 2.8 below, where the concept of conditional independence is shown equivalent to the algebraic concept of splitting. We should note here that Lemma 2.8 is due to Jacobsen and Pitman [4] and that Jacobsen has a nice discussion of algebraic versus what he calls operational definitions in his recent preprint [5]. We follow his lead and henceforth classify properties as algebraic or operational, although the distinction is sometimes a bit subtle. These investigations have not been limited to the case of Markov chains. For example, Getoor and Sharpe have actively pursued this theme (see [l], for example) and in [7] concepts developed in [4] were extended to the context of general Markov processes. 0304-4149/82/0000-0000/\$02.75

@ “,982 North-Holland

A.O. Pittenger / Time changes of Markov chains

190

The purpose of this note is to consider algebraic versus operational definitions of Markov time changes, that is increasing randolm times which transform the given Markov chain into another Markov chain. (The analogous problem for Markov processes has been studied recently by Glover in [2,3].) One difficulty we encounter is defining the operational requirements precisely. If the requirements are too weak, there is toi3 much freedom and general characterizations seem impossible. In Section 3 we make 2 case for a balanced set of requirements and obtain in Theorem 3.6 a nice, equivalent algebraic definition. The effect of weakening the requirements is illustrated in Section 5. In Section 4 we show, in Theorem 4.4, how an additional restriction, expressed algebraically or operationally, provides a rather general criterion for the conditions of Theorem 3.6.

2. Notation Before doing any of this let us first define the context. E denotes a tour table, discrete state space and a the set of infinite sequences (paths) of elements of E. As usual Xn (0) means ti (12). @ is the g-algebra generated by (xk, 0 d k < oo), and 9: is the m-algebra generated by {XL,0 c k s n}. If P = (pal,) is a given transition matrix, then 9 and 9,, denote thfe usual completions using the usual measures P&, p an initial distribution. Since E is countable, we can alssume an initial measure ~0 with positive weight at all points, and In the discussions below it sul%ces to make our arguments with respect to P”“, denoted henceforth as P. We also express expectation and probability with the same symti~l: P”(f, Al, AZ) means E”(f(w); Ai n&). Let R be a random time - an extended, non-neg,ative, integer-valued, s-measurable function. P(N), the R-past, is the a-algebra generated by (9k ~I{R = k}, 0 s k}, and 9?(R) = Si’9, the R-future, is the completion of a{X(R + k), 0 s k) (@k represents the usual shift: X,(&o) ‘--X:+&U)). Note that for any _K S-=S(R)v%(R).

(2.1)

We now introduce specific types of random times. 2.2.

efinition. R is a conditiotial independence time if for A. E S(R) and B E \$F P(A, 9;‘BIX(R))

=

(2.3

(9’;‘BI X(R)) = QXIRi(B),

(2.4)

Equivalently (6,‘B19(R))

=

where Q”( 9) is a probability on (i2, 9) depending only on a. Using the ideas of [4] we introduce the following.

A.O. Pittenger / Time changes

sf Ma:-kov chains

191

2.5. Definition. R is a splitting time if for all 0 s n =C00 (R =n]=F,nB,‘G,,,

(2.6)

for some F, E 9\$ and G, E 9. We will call R a stationary splitting time (with respect to G) if {R =n)=F,,[email protected],‘G,

(2.7)

for some F,.,E 9 and G E 5 In the discussion below we only need (2.7), and henceforth, when splitting is mentioned, stationary splitting is intended. As mentioned in the introduction, a basic example of the equivalence between an operational definition and an algebraic definition is that between (2.4) and (2.7). Since we use this result extensively, we include a quick proof. 2.8. Lemma (141). R is a stationary splitting time with respect to G (briefly, a G splitting time) i/f R is a conditional independence time with Q” (A) = Pa (A 1G).

Proof, The proof that splitting implies conditional independence is easy and is left to the reader. For the converse let a’ be an (n + l)-tuple (ao, al, . . . , a,) and define A(6) = {Xk = ak, 0 s k s n}. Since IQ is s-measurable, we can find 9O-measurable, (0,1}-valued functionsfn =fn(XO, X1, . . .) such that, for n Z m,f, fm = 0 and P-as., R(o)=n iff f,, = 1. For a given n and a, = a define l

GM)=G(d,a,n)={o:f,(aO,.

..

,a,,Xl,.

Then if 1(~, n) = {a: a,, =a and P(A(a’), R =n)>O},

. .)= l,Xo=a,

=a}.

we have

(x n ==a,R=n}=U{A(d)n8,‘G(d),dEI(a,n)}

PCS.

(2.9)

Let li E I(a, n) and &E I(a, m). It follows that 0 = P(A(a’), R = n, Xn = a, 6,’ (G(6) - G(d))) = P(A(a’), R = n, Xn = a, Q”(G(6) - G(B))),

or Q”(G(@-G(a’))

= 0. By symmetry Q”(G(&LJG(~‘))

{X,l=a,R=n}=U{A(~)n8~1G(a),~~I(a,n)}

= 0, and thus -a.s.

where G(a)=UU{G(6),~d(a,m),msO~. Defining G=UG,!a) IJ CJ {[email protected];, a’ E I(a, n), a E El gives (2.7) and complete: the proof.

and F,=

Nlate that the property of being a splitting time depends on the semigroup. For example, let the process flow from left to right, as indicated schematically below: Gl

--+

bl --+

cl

-

al ==3

a2

------b

b2

-

c2

-

a2

etc.

(2.10)

182

A.O. Pittenger / Time changes of Markov chains

Define R = inf{k > 1, (Xk-1, Xk+l) = (ai, ci), i = 1 or i = 2). Then, since transitions from ai to bj, i # j, are prohibited, J? will be a splitting time with G = ((,.%V~~, Xl) = (bi, ci), i = 1 or i = 2). The construction of G in Lemma 2.8 excludes addling~into G any paths with initial transitions from bi to Cj, i 7”j, on the grounds that tr,ansi+ions from aj to bi, i # j, have zero probability. If the transition matrix allowed such transitions, ,R would cease to be splitting. 0ne final fact is worth noting: Any G in 9 can be a splitting set.

(2.11)

For example, let T he any stopping time and define a G-splitting time by {R = m} = {T =m}nB;‘G.

3. Time changes

Let {T,, n 2 0) be a sequence of strictly increasing random times. We wish to investigate conditions on the {Tfi} which make {X( T,,)} a (stationary) Markov chain. Before plunging into technicalities, let us consider two examples. The first is thll: last exit process constructed from To = L = sup{k 2 0: Xk E B}, where B is a fixed set, itransient for the original process. Tn is defined as L + n, and it is well known [6] that {X( T,), 9( T,)} is a Markov chain with transition matrix P’”(X1 = bl H = ooj, where H is the hitting time of B: (3.1) The second example is the so-called excision process. Two disjoint sets B1 and B2 are defined with hitting times Hi and penetration times Di: Di - inf{k 20: Xk E Bi},

i = I, 2.

(3.2)

Define two sequences of times {Sn) and {Ln) by So = Dr and the others recursively:

Ll =infi[k s&-r:

E_12dk
S;; = inf{k :> L, : Xk E Bl}. Thus the L, are, sequentially, last hits of B1 prior to Bz, and the S, are the subsequent times of return to B1. The excision process is defined by removing times in (L,, Sn) from the time scale and defining a new time scale. We omit a formal de!mition of the resulting T,, since an alternative description is given below. There are several features common to both examples. First, information increases as n increases, i.p., S(T,) c 2F(T,+1). Second, it turns out that all of the T,, are conditional indeperrdence times with the same Q’. Third, given the value of Tn the depends only on post-Tn information, and the method of dependent of n. Finally, as we will see, it follows from these ), 9(Tn)} is a Markov chain.

A.O. Pittenger / Time changes

gf Markov chains

193

It is possible to weaken some of those features atnd still produce examples of time changes which also produce Markov chains. The disadvantages are that interconnections between T,, and T,,+I may be lost or the constructed process may have little or no relationship to the original process. As a rather extreme example, suppose that the T,, are strictly increasing, finite, and defined so that %( T,) c 9( r. 1) and X( T,,) = a for all IL Then we obtain a trivial Markov chain with a one by one transition matrix. Obviously, the new chain has little to do with the original process, and the restrictions on the 7” are too slight to provide structure. More modest adjustments of the properties discussed above are possible, and some examples are given in Section 5. These examples show that even slight relaxations of the imposed conditions can unlink the T, and enormously complicate any algebraic description of the random times. Consequently, WC confine ourselves to the following ‘operational’ properties suggested by the examples: .fF(T,) c 9(T,+1)

for all n 20,

P(B~~CI9~~T,)) = QXtTn’(C)

W’~+I = T, tklS(T,))

(3.3a) for all n 20,

= QXITn’(S = k),

(3.3b) y&20,

where S is a fixed random time and Q”( l) is a probability on (0,s). Markov property is

WU’A I)

is a Markov chain,

(3.3c) The resulting (3 l 4)

where the transition matrix is left unspecified. Now return to the last exit process and the excision process. Both of these examples have a common algebraic description based upon a triple (To, S, r) satisfying 0 G To and

0< \$

T,,=Tn_l+Sot9~,,_,,

r

E

S(S).

are r splitting times, nd,

(3Sa) (3Sb) (3Sc)

For the last exit process it is easy to check that AT= {W: Xk & B, k 2 1}, To = L and

will generate the {T,) via (3.5b). The excisic)r: process is more involved. Here r = {L)l
A.O. Pitterzger/ Time changes of Markov chains

194

where the Hi are defined as in (3.1). Note that, r E 9(S), = 1}, k = 1,

{X&&}n{S

rn’s=k’~(~X~~B~~n~S=k~, k>P.

Using (3.5b) to define the T, it is easy to trace out the evolution of X(T,) and see that the foregoing is consist~_it wi*:bthe earlier description of the excision process. We are now ready for the following. 3.6. Theorem. Let (T,,, n 3 0) be a sequence

of st’rictlyincreasing

random times. Then (T,,,n 30) satisfies (3.5) iff it satisfies (3.3). In either case (3.4) holds with transition matrix Pa (X(S) = b 1r).

Proof. Assume (3.5). We show by induction that the T, are all splitting times with respect to r. Let {T, =k}==Ak(n)nOklf’,

Ak(n)Egk,

and use (3.5a) and (3.5~) to obtain

r,l(s=/)=Bi~~s=j~=BinCine~~r, with Bj and Ci in 9j= Then m-l {T n+l

=m}=

u

{T,=k}n{So&=m-k)

k=n m-l =

0 A&(n) n 6,’ (Bm-k n Cm-k n

eikkAr)

k=n

=_qm(n + I)n&T, A,,%(n+ 1) E Pm. This shows that T,+l is a r splitting time and, buried in the proof, that T,., is 9(T,+r)-measurable. That last result is equivalent to (3.3a). Note that V n+ I- T, = k} equals OFi (S = k), so that (3.3~) is immediate.

Here the essential step in verifying (3.4) is (X(T,+1)=b,X(T,+2)=~~j~(T,))=Px’Tn’(X(S)=b,lly(S2)=c~r) =P x’Tn’(X(S) = blr)Pb(X(S)

= clr),

where S2 = S + S 0 OS.The first equa!.ity is from (3.3b) and splitting, while the second follows from P”(r, X(S) = 15,X( ;G =

m=l

=

f m= 1

pv,

(m)=b,:F=m&,*(

p”(~~,,X(m)=li,C,,e~‘(r,X(S)=c))

A.O. Pittenger / Time changes of Markou chains

=

f m= 1

P”(B,,

X(m)

= 6,

Cm,

&,‘f,

P'(X(S)

195

= clr))

=Pa(r,X(S)=b)Pb(X(S)=c(r). For the converse, assume (3.3). It is immediate from (3.3a), (3.34 and an induction proof that (7’0, T1, . . . ,7’,,) has the same distribution as (To, f1, . . . , F,J, where Pn = ‘1=,-l+s O19fn_1.Hence we can replace the T,, by F,, and then drop the tilde. This gives (3Sb) and identifies 7’0and S. Now each T,, is a splitting time with the same law QX(Tn) on the T, future. An examination of the proof of Lemma 2.8 shows that a common r clin be defined for all the T,. It is also easy to see that the S of (3.3~) is really only used on r; that is we can define S to be infinite on gc and all of (3.3) will still hold. Note that P”(r) > 0 only if a is realized with positive probability as X( T,.J for some n. Assume then that P(A(a'), T,, = k, X(T,) = a) is positive, where we use the notation introduced in the proof of Lemma 2.8. Let B E P(S) and compute P(A(a’), T, =k,X(T,)=a,

9&B,

S
t9&C)

in two different ways to obtain P”(I’, B, S ~00, &‘C) = P”(r, B, S -==q Px’s’(C(I-)).

(3.7)

Since S is infinite on r’, we may remove the first r from both expressions for all such initial states a, finally obtaining the fact that S is a conditional independence time with P(BS*C 19(S)) = Pxts’ (Cl r). This shows that S is a splitting time with respect to K Finally, since r 1 {S < OO},it easily follows that r E g(S), completing the verification of conditions (3.5). Note that in the proof above, we have shown S not tb oe unique. The reader may confirm this ambiguity with the excision process by defining S to be infinite on P.

0

Variations on the theme of r

In (2.11) we observed that any set could serve as a splitting set. However, the results of Theorem 3.6 show that for F to serve in the construction of a Markov time change via (3.5), there is an interplay between r and a positive, r splitting time. Not every set sazisfies these requirements. For example, suppose the state space is {a, 6, c, d, A} with A absorbing and all transitions possible except those out of A. Let r be defined as 2m

E {Q,6, Al

*

X2m+t E h 6) *

X2m+2

c {b,C, A),

X2m+3E{a

4,

X2?,, E {c, 4

*

Xzm+l E (CTd} *

X2m+2 E b, 4, X2m+3 E {bv CIv (U

:uoynpu! liq si 3sa.l ay,L ‘J = w 103 splay (q) wyi 0s J, _ 0 u .J = {1 = CI) uay~, ‘(t?) aumss~ MON *(a) pue (q) 30 a2uaIeA!nba ay: %yysgqe~sa

‘tu

~J,“@~rn

‘00

l3S!MK3~,0

1=s

auyap put2 (a) aurnsse %Iasrafwo3 l sp[oy Pi

Pug

‘{ZU~~)V~~~Jr~~V~~V~~=Jr~~u~~uJ={2U=S)uJ uayL lau.u) %uy~yds J e si s PUBsplay (q) asoddns

'JOOld

l ( s*c) u! SEaidy a%uey:, awl e 30 )lad st! pasn aq JOUUBSJ away ptw %)s!xa s yans ou ley) s~ol103 11 l ‘-uzx 30 sanpw 3aylo aql 103 [email protected]~e .yy~s v l yal ay, uo IOU Jnq ‘(z*p) 30 ap!s [email protected]!.1 aq, uo alq!ssod s! 4 = I+ “zx pun v = I- “ZX ‘{uz = s} u J u! alqTscod s? v = 1-“zx 3! %ailA

asoddns l g = {I+ z.uz= s}u J AI.reaI3 l (s)g 3 J pw ‘v 30 ly WI.J ayl 2 ‘1)< (2 > s ‘,,[)a ~J!M s auy %u!ggds J ‘aigsod t! s)s!xa alay asoddns uue

A.O. Pittenger / Time changes of Markov chains

197

where B, E S,,,. The converse is equally straightforward: n-l

(D=n)=

n 8~11%8~‘~=l?v9-1{D=n-l} in=0 =

r’n

8-‘Fn_1 n B,‘r = B’, n 8-‘F,--1 n t9,‘K

4.5. Remark.. The requirements of (3.5) include a positive r splitting :ime. Note that if D(r) is a r splitting time, then so is H = H(r) = inf{k > 1, w E &‘k’r),

since {H=n~}=8-‘{D=m-1}=8-‘F,_ln8~1r. S in (3.5) (see Example 5.2 below).

(4.6) Hence H can play the role of

The last variation on the theme is that there are sets between the extremes of (4.1) and Threorem 4.4, i.e., D(r) is not a r splitting time but positive r splitting times S exist with r E 9(S). Thus, even as operational properties were restricted to obtain Theorem 3.6, so the choice of r is strictly narrowed by Theorem 4.4. Let the state space be (0, 1, A}, again with all transitions from (0, 1) possible. Let a block of zeros in o mean a maximal string appearing in o in the form (0, . . . , 0, x, . . .) or (. . . , x, 0, . . . , 0, y, . . .) with x and y non-zero. 0 is path space, and r = {w: all blocks of zero in w have prime cardinality}.

(4.7)

Then D(r) is not a r splitting time. For example, w starting (1, 0, 0. 0, 0, 0, 0, 0, 0, 0, x # 0, . . .) will be in {D = 3}, assuming only prime blocks occur after x # 0. But {X0 = 1, X1 = X2 =X3 = 0) n t3i1r contains o beginning (1, 0, 0, 0, 0, 0, 0, 0, ) which are in {D = 0}, again assuming only prime blocks after x \$0. xzo,... However, if we define S = 1+ inf{k 2 0: .,Yk# 0, (L)E e;‘r}, it is easy to check that r E 9(S) and S is splitting with respect to I’. We leave the details to the reader? noting only the key fact that at time S either X(S) it 0 or X(S) = 0 andX(S -- 1) # 0, thus effectively splitting both r and the S past and future.

We further illustrate the results and restrictions of Sections 3 and 4. The assertion of Theorem 3.6 depends on the semigroup I? ed after (2.10), and r is the set G this, note that if To = S = R, the time in the same paragraph, then (To, S, r) satisfies (3.5) and thus defines a Markov time change. Again, if transitions qi to bj, i # j, were allowed, the construct:ion would fail.

lpUOyn~ JO pua aq, 1x2 aIduIexa Snoa~E~~no palsa%%ns oyih ‘Inod: Iaeyai qp~ pua ‘cj*s tuaJoay& 30 3oold ay, u! uo!\$e=, ueIv Y)!Mauoglesaailuo:, In3asn a~paIMou~~~ 0) a

aLp

l (p*c) pm (3g.c) ‘(ec*c) se IIaM SEamapuadapul Ieuo~~~puoc~ 30 ~03 pauaqaaM t! ICjs9es 11~~s 111~ saw) ayl )nq 6pavmIdtuoa AIsnowoua aplzw aq uw am)n3- pm md- uJ uaaMlaq d!ysuo!leIa.walu! aq\$ ‘amds Arabsaylop pappE am ssu!od a~ow 31

~3~3UI l (s*f) 30 )saJ ay, put? amapuadapu! Ieuog~puos sg~ Li3s9esaAoqe pauyap (‘# ayl uayl ‘(c e y ‘(>I+ u~)x}~ 6awn3-uL.Lay’, 30 wd Quo pua (u~)g 30 amapuadapu! I~uo~~!puo:, a+baJ 03 pauaqeah SF(qc*Q 31 I-Q .talje (23 613)30 ~!y JSJYaq, 6”~ %u!sn uo~lma~~.rlqpauyap am Q 8utu!ecual ayL l

‘(‘3 = (oH,X 31!‘p = (f+>X ‘z+yX “+3X ‘VX):oH< y}3u!

i

SBpauyap aq s = 0~ ,a1 pue 62 61= / 6(!v %f% 6%) = &J putz (b % “Q %I) = i1g16q .QpsaIdn\$-p %uiuyaa “(236’3) 30 my %uu~q aq3 aq 0~ Ia? l alqtssod SUO~J~SUEJJ IIle qq~ (23 613 ‘Zq ‘1 q ‘Zv 61?P} aq amds al’lels ay;lrla? l AIsnowloua sJa)leuu a\$mIduIo:, UB~(qg*E) 30 %u!uayeaM [email protected] e uahz lc*s agdumxa

l (s*E) e!h a8uaq3 am!) ~oy.ieyya sauyap (J OH ‘(~):a) sny) pug ‘awt\$ %u!w!;ds J B si (~)a uay& ‘(“0 > IQ} = J Y)!M saw!) Ieuitulal he aq Za pun IQ VI um aM ‘ssa3old uoFs!Dxaayl 30 uoIlezge:aua% E sv lz’s qduusx

A.O. Pittenger / Time changes of Markov chains

199

eferences [l] R.K. Getoor and M,.T. Sharpe, The Markov property at co-optional times, Z. Wahrsch. Verw. Gebiete 48 (1979) 201-211. [2] J. Glover, Raw time changes of Markov processes, Ann. Probab. 9 (1981) 90-102. [3] J. Glover, Applications of raw time-chacges to Markov processes, Ann. Probab. 9 (198 1) 10 19-l 029. [4] M. Jacobsen and J.W. Pitman, Birth, death and conditioning of Markov chains, Ann. Probab. 5 (1977) 430-450. [S] M. Jacobsen, Markov chains: birth and death times with conditional independence, preprint #7, Inst. Math. Stat., University of Copenhagen, 1979. [6] P.A. Meyer, R.T. Smythe and JB. Walsh, Birth and death of .Markav processes, Proc. 6th Berkeley Symp. Stat. Prob., Vol. 3 (1972) 245-305. [7] A.O. Pittenger, Regular birth times foi Markov processes, Ann. Probab. 9 (198 1) 769-780.