2 General Markov Chains (September 10, 1999)

2.2 Identities for mean hitting times and occupation times

2.2.1 Occupation measures and stopping times

The purpose of this section is to give a systematic “probabilistic” treatment of a collection of general identities by deriving them from a single result, Proposition 2.3. We work in discrete time, but give the corresponding continuous-time results in section 2.2.3. Intuitively, a stopping time is a random time which can be specified by some on-line algorithm, together (perhaps) with external randomization.

Proposition 2.3

Consider the chain started at state ii. Let 0<S<0<S<\infty be a stopping time such that XS=iX_{S}=i and EiS<E_{i}S<\infty. Let jj be an arbitrary state. Then

Ei(number of visits to jj before time SS)=πjEiS.E_{i}(\mbox{number of visits to $j$ before time $S$})=\pi_{j}E_{i}S.

In the phrase “number of …before time tt”, our convention is to include time 00 but exclude time tt.

We shall give two different proofs. The first requires a widely-useful general theorem in stochastic processes.

Proof. Consider the renewal process whose inter-renewal time is distributed as SS. The reward-renewal theorem (e.g. Ross [300] Thm. 3.6.1) says that the asymptotic proportion of time spent in state jj equals

Ei(number of visits to jj before time SS)/EiS.E_{i}(\mbox{number of visits to $j$ before time $S$})/E_{i}S.

But this asymptotic average also equals πj\pi_{j}, by the ergodic theorem. \Box

We like that proof for philosophical reasons: a good way to think about general identities is that they show one quantity calculated in two different ways. Here is an alternative proof of a slightly more general assertion. We refer to Propositions 2.3 and 2.4 as occupation measure identities.

Proposition 2.4

Let θ\theta be a probability distribution on II. Let 0<S<0<S<\infty be a stopping time such that Pθ(XS)=θ()P_{\theta}(X_{S}\in\cdot)=\theta(\cdot) and EθS<E_{\theta}S<\infty. Let jj be an arbitrary state. Then

Eθ(number of visits to jj before time SS)=πjEθS.E_{\theta}(\mbox{number of visits to $j$ before time $S$})=\pi_{j}E_{\theta}S.

Proof. Write ρj=Eθ(number of visits to jj before time SS)\rho_{j}=E_{\theta}(\mbox{number of visits to $j$ before time $S$}). We will show

jρjpjk=ρkk.\sum_{j}\rho_{j}p_{jk}=\rho_{k}\ \forall k. (2.5)

Then by uniqueness of the stationary distribution, ρ()=cπ()\rho(\cdot)=c\pi(\cdot) for c=kρk=EθSc=\sum_{k}\rho_{k}=E_{\theta}S.

Checking (2.5) is just a matter of careful notation.

ρk\displaystyle\rho_{k} =\displaystyle= t=0Pθ(Xt=k,S>t)\displaystyle\sum_{t=0}^{\infty}P_{\theta}(X_{t}=k,S>t)
=\displaystyle= t=0Pθ(Xt+1=k,S>t) because Pθ(XS=k)=Pθ(X0=k)\displaystyle\sum_{t=0}^{\infty}P_{\theta}(X_{t+1}=k,S>t)\mbox{ because }P_{% \theta}(X_{S}=k)=P_{\theta}(X_{0}=k)
=\displaystyle= t=0jPθ(Xt=j,S>t,Xt+1=k)\displaystyle\sum_{t=0}^{\infty}\sum_{j}P_{\theta}(X_{t}=j,S>t,X_{t+1}=k)
=\displaystyle= t=0jPθ(Xt=j,S>t)pjk by the Markov property\displaystyle\sum_{t=0}^{\infty}\sum_{j}P_{\theta}(X_{t}=j,S>t)\ p_{jk}\mbox{ % by the Markov property}
=\displaystyle= jρjpjk.\displaystyle\sum_{j}\rho_{j}p_{jk}.


2.2.2 Mean hitting time and related formulas

The following series of formulas arise from particular choices of jj and SS in Proposition 2.3. For ease of later reference, we state them all together before starting the proofs. Some involve the quantity

Zij=t=0(pij(t)-πj)Z_{ij}=\sum_{t=0}^{\infty}\left(p^{(t)}_{ij}-\pi_{j}\right) (2.6)

In the periodic case the sum may oscillate, so we use the Cesaro limit or (equivalently, but more simply) the continuous-time limit (2.9). The matrix 𝐙{\bf Z} is called the fundamental matrix (see Notes for alternate standardizations). Note that from the definition

jZij=0 for all i.\sum_{j}Z_{ij}=0\mbox{ for all }i. (2.7)
Lemma 2.5


Lemma 2.6
Ei(number of visits to jj before time Ti+T^{+}_{i})=πj/πi.E_{i}(\mbox{number of visits to $j$ before time $T^{+}_{i}$})=\pi_{j}/\pi_{i}.
Lemma 2.7

For jij\neq i,

Ej(number of visits to jj before time TiT_{i})=πj(EjTi+EiTj).E_{j}(\mbox{number of visits to $j$ before time $T_{i}$})=\pi_{j}(E_{j}T_{i}+E% _{i}T_{j}).
Corollary 2.8

For jij\neq i,

Lemma 2.9

For ili\neq l and arbitrary jj,

Ei(number of visits to jj before time TlT_{l})=πj(EiTl+ElTj-EiTj).E_{i}(\mbox{number of visits to $j$ before time $T_{l}$})=\pi_{j}(E_{i}T_{l}+E% _{l}T_{j}-E_{i}T_{j}).
Corollary 2.10

For ili\neq l and jlj\neq l,

Pi(Tj<Tl)=EiTl+ElTj-EiTjEjTl+ElTj.P_{i}(T_{j}<T_{l})=\frac{E_{i}T_{l}+E_{l}T_{j}-E_{i}T_{j}}{E_{j}T_{l}+E_{l}T_{% j}}.
Lemma 2.11


Lemma 2.12


Corollary 2.13

jπjEiTj=jZjj\sum_{j}\pi_{j}E_{i}T_{j}=\sum_{j}Z_{jj} for each ii.

Corollary 2.14 (The random target lemma)

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

Lemma 2.15
Eπ(number of visits to jj before time TiT_{i})=πjπiZii-Zij.E_{\pi}(\mbox{number of visits to $j$ before time $T_{i}$})=\frac{\pi_{j}}{\pi% _{i}}Z_{ii}-Z_{ij}.

Lemmas 2.11 and 2.12, which will be used frequently throughout the book, will both be referred to as the mean hitting time formula. See the Remark following the proofs for a two-line heuristic derivation of Lemma 2.12. A consequence of the mean hitting time formula is that knowing the matrix 𝐙{\bf Z} is equivalent to knowing the matrix (EiTj)(E_{i}T_{j}), since we can recover ZijZ_{ij} as πj(EπTj-EiTj)\pi_{j}(E_{\pi}T_{j}-E_{i}T_{j}).

Proofs. The simplest choice of SS in Proposition 2.3 is of course the first return time Ti+T^{+}_{i}. With this choice, the Proposition says

Ei(number of visits to jj before time Ti+T^{+}_{i})=πjEiTi+.E_{i}(\mbox{number of visits to $j$ before time $T^{+}_{i}$})=\pi_{j}E_{i}T^{+% }_{i}.

Setting j=ij=i gives 1=πiEiTi+1=\pi_{i}E_{i}T^{+}_{i}, which is Lemma 2.5, and then the case of general jj gives Lemma 2.6.

Another choice of SS is “the first return to ii after the first visit to jj”. Then EiS=EiTj+EjTiE_{i}S=E_{i}T_{j}+E_{j}T_{i} and the Proposition becomes Lemma 2.7, because there are no visits to jj before time TjT_{j}. For the chain started at ii, the number of visits to ii (including time 00) before hitting jj has geometric distribution, and so

Ei(number of visits to ii before time TjT_{j})=1/Pi(Tj<Ti+).E_{i}(\mbox{number of visits to $i$ before time $T_{j}$})=1/P_{i}(T_{j}<T^{+}_% {i}).

So Corollary 2.8 follows from Lemma 2.7 (with ii and jj interchanged).

Another choice of SS is “the first return to ii after the first visit to jj after the first visit to ll”, where i,j,li,j,l are distinct. The Proposition says

πj(EiTl+ElTj+EjTi)=Ei(number of visits to jj before time TlT_{l})\pi_{j}(E_{i}T_{l}+E_{l}T_{j}+E_{j}T_{i})=E_{i}(\mbox{number of visits to $j$ % before time $T_{l}$})
+Ej(number of visits to jj before time TiT_{i}).+E_{j}(\mbox{number of visits to $j$ before time $T_{i}$}).

Lemma 2.7 gives an expression for the final expectation, and we deduce that (for distinct i,j,li,j,l)

Ei(number of visits to jj before time TlT_{l})=πj(EiTl+ElTj-EiTj).E_{i}(\mbox{number of visits to $j$ before time $T_{l}$})=\pi_{j}(E_{i}T_{l}+E% _{l}T_{j}-E_{i}T_{j}).

This is the assertion of Lemma 2.9, and the identity remains true if j=ij=i (where it becomes Lemma 2.7) or if j=lj=l (where it reduces to 0=00=0). We deduce Corollary 2.10 by writing

Ei(number of visits to jj before time TlT_{l})=E_{i}(\mbox{number of visits to $j$ before time $T_{l}$})=
Pi(Tj<Tl)Ej(number of visits to jj before time TlT_{l})P_{i}(T_{j}<T_{l})E_{j}(\mbox{number of visits to $j$ before time $T_{l}$})

and using Lemma 2.7 to evaluate the final expectation.

We now get slightly more ingenious. Fix a time t01t_{0}\geq 1 and define SS as the time taken by the following 22-stage procedure (for the chain started at ii).

(i) wait time t0t_{0}

(ii) then wait (if necessary) until the chain next hits ii.

Then the Proposition (with j=ij=i) says

t=0t0-1pii(t)=πi(t0+EρTi)\sum_{t=0}^{t_{0}-1}p^{(t)}_{ii}=\pi_{i}(t_{0}+E_{\rho}T_{i}) (2.8)

where ρ()=Pi(Xt0=)\rho(\cdot)=P_{i}(X_{t_{0}}=\cdot). Rearranging,


Letting t0t_{0}\rightarrow\infty we have ρπ\rho\rightarrow\pi by the convergence theorem (strictly, we should give a separate argument for the periodic case, but it’s simpler to translate the argument to continuous time where the periodicity issue doesn’t arise) and we obtain Lemma 2.11.

For Lemma 2.12, where we may take jij\neq i, we combine the previous ideas. Again fix t0t_{0} and define SS as the time taken by the following 33-stage procedure (for the chain started at ii).

(i) wait until the chain hits kk.

(ii) then wait a further time t0t_{0}.

(iii) then wait (if necessary) until the chain next hits ii.

Applying Proposition 2.3 with this SS and with j=ij=i gives

Ei(number of visits to ii before time TkT_{k})+t=0t0-1pki(t)=πi(EiTk+t0+EρTi),E_{i}(\mbox{number of visits to $i$ before time $T_{k}$})+\sum_{t=0}^{t_{0}-1}% p^{(t)}_{ki}=\pi_{i}(E_{i}T_{k}+t_{0}+E_{\rho}T_{i}),

where ρ()=Pk(Xt0=)\rho(\cdot)=P_{k}(X_{t_{0}}=\cdot). Subtracting the equality of Lemma 2.7 and rearranging, we get


Letting t0t_{0}\rightarrow\infty, we have (as above) ρπ\rho\rightarrow\pi, giving


Appealing to Lemma 2.11 we get Lemma 2.12. Corollary 2.13 follows from Lemma 2.12 by using (2.7).

To prove Lemma 2.15, consider again the argument for (2.8), but now apply the Proposition with jij\neq i. This gives

t=0t0-1pij(t)+Eρ(number of visits to jj before time TiT_{i})=πj(t0+EρTi)\sum_{t=0}^{t_{0}-1}p^{(t)}_{ij}+E_{\rho}(\mbox{number of visits to $j$ before% time $T_{i}$})=\pi_{j}(t_{0}+E_{\rho}T_{i})

where ρ()=Pi(Xt0=)\rho(\cdot)=P_{i}(X_{t_{0}}=\cdot). Rearranging,

t=0t0-1(pij(t)-πj)+Eρ(number of visits to jj before time TiT_{i})=πjEρTi.\sum_{t=0}^{t_{0}-1}(p^{(t)}_{ij}-\pi_{j})+E_{\rho}(\mbox{number of visits to % $j$ before time $T_{i}$})=\pi_{j}E_{\rho}T_{i}.

Letting t0t_{0}\rightarrow\infty gives

Zij+Eπ(number of visits to jj before time TiT_{i})=πjEπTi.Z_{ij}+E_{\pi}(\mbox{number of visits to $j$ before time $T_{i}$})=\pi_{j}E_{% \pi}T_{i}.

Applying Lemma 2.11 gives Lemma 2.15.

Remark. We promised a two-line heuristic derivation of the mean hitting time formula, and here it is. Write

t=0(1(Xt=j)-πj)=t=0Tj-1(1(Xt=j)-πj)+t=Tj(1(Xt=j)-πj).\sum_{t=0}^{\infty}\left(1_{(X_{t}=j)}-\pi_{j}\right)=\sum_{t=0}^{T_{j}-1}% \left(1_{(X_{t}=j)}-\pi_{j}\right)+\sum_{t=T_{j}}^{\infty}\left(1_{(X_{t}=j)}-% \pi_{j}\right).

Take Ei()E_{i}(\cdot) of each term to get Zij=-πjEiTj+ZjjZ_{ij}=-\pi_{j}E_{i}T_{j}+Z_{jj}. Of course this argument doesn’t make sense because the sums do not converge. Implicit in our (honest) proof is a justification of this argument by a limiting procedure.

Example 2.16

Patterns in coin-tossing.

This is a classical example for which 𝐙{\bf Z} is easy to calculate. Fix nn. Toss a fair coin repeatedly, and let X0,X1,X2,X_{0},X_{1},X_{2},\ldots be the successive overlapping nn-tuples. For example (with n=4n=4)

tossesHTHHTTX0=HTHHX1=THHTX2=HHTT\begin{array}[]{ccccccc}\mbox{tosses}&H&T&H&H&T&T\\ X_{0}=&H&T&H&H&&\\ X_{1}=&&T&H&H&T&\\ X_{2}=&&&H&H&T&T\\ \end{array}

So 𝐗{\bf X} is a Markov chain on the set I={H,T}nI=\{H,T\}^{n} of nn-tuples i=(i1,,in)i=(i_{1},\ldots,i_{n}), and the stationary distribution π\pi is uniform on II. For 0dn-10\leq d\leq n-1 write I(i,j,d)I(i,j,d) for the indicator of the set “pattern jj, shifted right by dd places, agrees with pattern ii where they overlap”: formally, of the set

ju=iu+d, 1un-d.j_{u}=i_{u+d},\ 1\leq u\leq n-d.

For example, with n=4n=4, i=HHTHi=HHTH and j=HTHHj=HTHH,

d0123I(i,j,d)0101\begin{array}[]{ccccc}d&0&1&2&3\\ I(i,j,d)&0&1&0&1\end{array}

Then write


From the definition of 𝐙{\bf Z}, and the fact that X0X_{0} and XtX_{t} are independent for tnt\geq n,


So we can read off many facts about patterns in coin-tossing from the general results of this section. For instance, the mean hitting time formula ( Lemma 2.11) says EπTi=2nc(i,i)-nE_{\pi}T_{i}=2^{n}c(i,i)\ -n. Note that “time 0” for the chain is the nn’th toss, at which point the chain is in its stationary distribution. So the mean number of tosses until first seeing pattern ii equals 2nc(i,i)2^{n}c(i,i). For n=5n=5 and i=HHTHHi=HHTHH, the reader may check this mean number is 3838. We leave the interested reader to explore further — in particular, find three patterns i,j,ki,j,k such that

P(pattern ii occurs before pattern jj)>1/2P(\mbox{pattern $i$ occurs before pattern $j$})>1/2
P(pattern jj occurs before pattern kk)>1/2P(\mbox{pattern $j$ occurs before pattern $k$})>1/2
P(pattern kk occurs before pattern ii)>1/2.P(\mbox{pattern $k$ occurs before pattern $i$})>1/2.

Further results. One can of course obtain expressions in the spirit of Lemmas 2.52.15 for more complicated quantities. The reader may care to find expressions for

Ei(number of visits to jj before time min(Tk,Tl)\min(T_{k},T_{l}))E_{i}(\mbox{number of visits to $j$ before time $\min(T_{k},T_{l})$})
Pi(hit jj before time min(Tk,Tl)\min(T_{k},T_{l})).P_{i}(\mbox{hit $j$ before time $\min(T_{k},T_{l})$}).

Warning. Hitting times TAT_{A} on subsets will be studied later (e.g. Chapter 3 section 5.3) (yyy 9/2/94 version) in the reversible setting. It is important to note that results often do not extend simply from singletons to subsets. For instance, one might guess that Lemma 2.11 could be extended to

EπTA=ZAAπ(A),ZAA:=t=0(Pπ(XtA|X0A)-π(A)),E_{\pi}T_{A}=\frac{Z_{AA}}{\pi(A)},\ \ Z_{AA}:=\sum_{t=0}^{\infty}(P_{\pi}(X_{% t}\in A|X_{0}\in A)-\pi(A)),

but it is easy to make examples where this is false.

2.2.3 Continuous-time versions

Here we record the continuous-time versions of the results of the previous section. Write

Zij=0(Pi(Xt=j)-πj)dtZ_{ij}=\int_{0}^{\infty}(P_{i}(X_{t}=j)-\pi_{j})dt (2.9)

This is consistent with (2.6) in that 𝐙{\bf Z} is the same for a discrete-time chain and its continuized chain. Recall from section 2.1.2 the redefinition (b) of Ti+T^{+}_{i} in continuous time. In place of “number of visits to ii” we use “total duration of time spent in ii”. With this substitution, Proposition 2.3 and the other results of the previous section extend to continuous time with only the following changes, which occur because the mean sojourn time in a state ii is 1/qi1/q_{i} in continuous time, rather than 11 as in discrete time.

Lemma 2.5.EiTi+=1qiπiE_{i}T^{+}_{i}=\frac{1}{q_{i}\pi_{i}}.

Lemma 2.6.

Ei(duration of time spent in jj before time Ti+T^{+}_{i})=πjqiπi.E_{i}(\mbox{duration of time spent in $j$ before time $T^{+}_{i}$})=\frac{\pi_% {j}}{q_{i}\pi_{i}}.

Corollary 2.8. For jij\neq i,