2 General Markov Chains (September 10, 1999)

2.8 Miscellaneous methods

2.8.1 Martingale methods

Modern probabilists regard the martingale optional stopping theorem as one of the most important results in their subject. As propaganda for martingales we give below four quick applications of that theorem, and a few more will appear later. All of these results could be proved in alternative, elementary ways. For the reader unfamiliar with martingales, Durrett [133] Chapter 4 contains much more than you need to know: Karlin and Taylor [208] Chapter 6 is a gentler introduction.

Lemma 2.27

Given a non-empty subset AIA\subset I and a function f(i)f(i) defined for iAi\in A, there exists a unique extension of ff to all II satisfying

f(i)=jpijf(j),  iA.f(i)=\sum_{j}p_{ij}f(j),\ i\not\in A.

Proof. If ff satisfies the equations above then for any initial distribution the process Mt:=f(Xmin(t,TA))M_{t}:=f(X_{\min(t,T_{A})}) is a martingale. So by the optional stopping theorem

f(i)=Eif(XTA) for all i.f(i)=E_{i}f(X_{T_{A}})\mbox{ for all }i. (2.28)

This establishes uniqueness. Conversely, if we define ff by (2.28) then the desired equations hold by conditioning on the first step.

Corollary 2.28

If hh is harmonic, i.e. if

h(i)=jpijh(j) for all ih(i)=\sum_{j}p_{ij}h(j)\mbox{ for all }i

then hh is constant.

Proof. Clearly a constant function is harmonic. So the Corollary follows from the uniqueness assertion of Lemma 2.27, taking AA to be some singleton.

Lemma 2.29 (The random target lemma)

The sum jEiTjπj\sum_{j}E_{i}T_{j}\pi_{j} does not depend on ii.

Proof. This repeats Corollary 2.14 with a different argument. The first-step recurrence for gj(i):=EiTjg_{j}(i):=E_{i}T_{j} is

gj(i)=1(ij)+1(ij)kpikgj(k).g_{j}(i)=1_{(i\neq j)}+1_{(i\neq j)}\sum_{k}p_{ik}g_{j}(k).

By Corollary 2.28 it is enough to show that h(i):=jπjgj(i)h(i):=\sum_{j}\pi_{j}g_{j}(i) is a harmonic function. We calculate

h(i)\displaystyle h(i) =\displaystyle= 1-πi+j,kπjpikgj(k)1(ij)\displaystyle 1-\pi_{i}+\sum_{j,k}\pi_{j}p_{ik}g_{j}(k)1_{(i\neq j)}
=\displaystyle= 1-πi+kpik(h(k)-πigi(k)) by definition of h(k)\displaystyle 1-\pi_{i}+\sum_{k}p_{ik}(h(k)-\pi_{i}g_{i}(k))\mbox{ by % definition of }h(k)
=\displaystyle= kpikh(k)+1-πi(1+kpikgi(k)).\displaystyle\sum_{k}p_{ik}h(k)\ \ +1-\pi_{i}\left(1+\sum_{k}p_{ik}g_{i}(k)% \right).

But 1/πi=EiTi+=1+kpikgi(k)1/\pi_{i}=E_{i}T^{+}_{i}=1+\sum_{k}p_{ik}g_{i}(k), so hh is indeed harmonic.

Lemma 2.30

For any stopping time SS and any states i,j,ki,j,k,

Ei(number of transitions jkj\rightarrow k starting before time SS)E_{i}(\mbox{number of transitions $j\rightarrow k$ starting before time $S$})
=pjkEi(number of visits to jj before time SS).=p_{jk}E_{i}(\mbox{number of visits to $j$ before time $S$}).

Proof. Recall that “before” means strictly before. The assertion of the lemma is intuitively obvious, because each time the chain visits jj it has chance pjkp_{jk} to make a transition jkj\rightarrow k, and one can formalize this as in the proof of Proposition 2.4. A more sophisticated proof is to observe that M(t)M(t) is a martingale, where

M(t):=Njk(t)-pjkNj(t).M(t):=N_{jk}(t)-p_{jk}N_{j}(t).
Nj(t):= number of visits to jj before time tt N_{j}(t):=\mbox{ number of visits to $j$ before time $t$ }
Njk(t):= number of transitions jkj\rightarrow k starting before time tt .N_{jk}(t):=\mbox{ number of transitions $j\rightarrow k$ starting before time % $t$ }.

And the assertion of the lemma is just the optional stopping theorem applied to the martingale MM and the stopping time SS.

Lemma 2.31

Let AA be a non-empty subset of II and let h:IRh:I\rightarrow R satisfy

(i) h(i)0,  iAh(i)\geq 0,\ i\in A

(ii) h(i)1+jpijh(j),  iAch(i)\geq 1+\sum_{j}p_{ij}h(j),\ i\in A^{c}.

Then EiTAh(i),  iIE_{i}T_{A}\leq h(i),\ i\in I.

Proof. For arbitrary hh, define gg by

h(i)=1+jpijh(j)+g(i)h(i)=1+\sum_{j}p_{ij}h(j)+g(i)

and then define

Mt=t+h(Xt)+s=0t-1g(Xs).M_{t}=t+h(X_{t})+\sum_{s=0}^{t-1}g(X_{s}).

Then Mmin(t,TA)M_{\min(t,T_{A})} is a martingale, so the optional sampling theorem says

EiMTA=EiM0=h(i).E_{i}M_{T_{A}}=E_{i}M_{0}=h(i).

But the hypotheses on hh imply MTATAM_{T_{A}}\geq T_{A}.

2.8.2 A comparison argument

A theme running throughout the book is the idea of getting inequalities for a “hard” chain by making a comparison with some “easier” chain for which we can do exact calculations. Here is a simple example.

Lemma 2.32

Let XX be a discrete-time chain on states {0,1,2,,n}\{0,1,2,\ldots,n\} such that pij=0p_{ij}=0 whenever j>ij>i. Write m(i)=i-EiX1m(i)=i-E_{i}X_{1}, and suppose 0<m(1)m(2)m(n)0<m(1)\leq m(2)\leq\ldots\leq m(n). Then EnT0j=1n1m(j)E_{n}T_{0}\leq\sum_{j=1}^{n}\frac{1}{m(j)}.

Proof. The proof implicitly compares the given chain to the continuous-time chain with qi,i-1=m(i)q_{i,i-1}=m(i). Write h(i)=j=1i1/m(j)h(i)=\sum_{j=1}^{i}1/m(j), and extend hh by linear interpolation to real 0xn0\leq x\leq n. Then hh is concave and for i1i\geq 1

Eih(X1)\displaystyle E_{i}h(X_{1}) \displaystyle\leq h(EiX1) by concavity\displaystyle h(E_{i}X_{1})\mbox{ by concavity }
=\displaystyle= h(i-m(i))\displaystyle h(i-m(i))
\displaystyle\leq h(i)-m(i)h(i) by concavity\displaystyle h(i)-m(i)h^{\prime}(i)\mbox{ by concavity }
=\displaystyle= h(i)-1\displaystyle h(i)-1

where hh^{\prime} is the left derivative. The result now follows from Lemma 2.31.

2.8.3 Wald equations

As mentioned previously, the results above don’t really require martingales. Next we record a genuine martingale result, not directly involving Markov chains but ultimately useful in their analysis. Part (c) is Wald’s equation and part (b) is Wald’s equation for martingales. The result is a standard consequence of the optional sampling theorem: see [133] (3.1.6) for (c) and [133] Theorem 4.7.5 for (a).

Lemma 2.33

(a) Let 0=Y0Y1Y20=Y_{0}\leq Y_{1}\leq Y_{2}\ldots be such that

E(Yi+1-Yi|Yj,ji)c,i0E(Y_{i+1}-Y_{i}|Y_{j},j\leq i)\leq c,\ i\geq 0

for a constant cc. Then for any stopping time TT,

EYTcET.EY_{T}\leq cET.

(b) If in the hypothesis we replace “c\leq c” by “=c=c”, then EYT=cETEY_{T}=cET.

(c) In particular, if Yn=i=1nξiY_{n}=\sum_{i=1}^{n}\xi_{i} for i.i.d. nonnegative (ξi)(\xi_{i}) then EYT=(Eξi)(ET)EY_{T}=(E\xi_{i})(ET).