2.2 Identities for mean hitting times and occupation 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.

In the phrase “number of …before time $t$”, our convention is to include time $0$ but exclude time $t$.

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 $S$. The reward-renewal theorem (e.g. Ross [300] Thm. 3.6.1) says that the asymptotic proportion of time spent in state $j$ equals

But this asymptotic average also equals $\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.

Proof. Write $j$. We will show

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

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

$\Box$

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

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

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 $(E_{i}T_{j})$, since we can recover $Z_{ij}$ as $\pi_{j}(E_{\pi}T_{j}-E_{i}T_{j})$.

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

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

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

So Corollary 2.8 follows from Lemma 2.7 (with $i$ and $j$ interchanged).

Another choice of $S$ is “the first return to $i$ after the first visit to $j$ after the first visit to $l$”, where $i,j,l$ are distinct. The Proposition says

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

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

and using Lemma 2.7 to evaluate the final expectation.

We now get slightly more ingenious. Fix a time $t_{0}\geq 1$ and define $S$ as the time taken by the following $2$-stage procedure (for the chain started at $i$).

(i) wait time $t_{0}$

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

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

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

Letting $t_{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 $j\neq i$, we combine the previous ideas. Again fix $t_{0}$ and define $S$ as the time taken by the following $3$-stage procedure (for the chain started at $i$).

(i) wait until the chain hits $k$.

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

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

Applying Proposition 2.3 with this $S$ and with $j=i$ gives

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

Letting $t_{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 $j\neq i$. This gives

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

Letting $t_{0}\rightarrow\infty$ gives

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

Take $E_{i}(\cdot)$ of each term to get $Z_{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.

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

$\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\}^{n}$ of $n$-tuples $i=(i_{1},\ldots,i_{n})$, and the stationary distribution $\pi$ is uniform on $I$. For $0\leq d\leq n-1$ write $I(i,j,d)$ for the indicator of the set “pattern $j$, shifted right by $d$ places, agrees with pattern $i$ where they overlap”: formally, of the set

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

$\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 $X_{0}$ and $X_{t}$ are independent for $t\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_{\pi}T_{i}=2^{n}c(i,i)\ -n$. Note that “time 0” for the chain is the $n$’th toss, at which point the chain is in its stationary distribution. So the mean number of tosses until first seeing pattern $i$ equals $2^{n}c(i,i)$. For $n=5$ and $i=HHTHH$, the reader may check this mean number is $38$. We leave the interested reader to explore further — in particular, find three patterns $i,j,k$ such that

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

Warning. Hitting times $T_{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

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

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

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 $T^{+}_{i}$ in continuous time. In place of “number of visits to $i$” we use “total duration of time spent in $i$”. 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 $i$ is $1/q_{i}$ in continuous time, rather than $1$ as in discrete time.

Lemma 2.5.$E_{i}T^{+}_{i}=\frac{1}{q_{i}\pi_{i}}$.

Lemma 2.6.

Corollary 2.8. For $j\neq i$,