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.

Consider the chain started at state $i$. Let $0<S<\infty$ be a stopping time such that $X_{S}=i$ and $E_{i}S<\infty$. Let $j$ be an arbitrary state. Then

$j$ |

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

$j$ |

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.

Let $\theta$ be a probability distribution on $I$. Let $0<S<\infty$ be a stopping time such that $P_{\theta}(X_{S}\in\cdot)=\theta(\cdot)$ and $E_{\theta}S<\infty$. Let $j$ be an arbitrary state. Then

$j$ |

Proof. Write $j$. We will show

$\sum_{j}\rho_{j}p_{jk}=\rho_{k}\ \forall k.$ | (2.5) |

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.

$\displaystyle\rho_{k}$ | $\displaystyle=$ | $\displaystyle\sum_{t=0}^{\infty}P_{\theta}(X_{t}=k,S>t)$ | ||

$\displaystyle=$ | $\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=$ | $\displaystyle\sum_{t=0}^{\infty}\sum_{j}P_{\theta}(X_{t}=j,S>t,X_{t+1}=k)$ | |||

$\displaystyle=$ | $\displaystyle\sum_{t=0}^{\infty}\sum_{j}P_{\theta}(X_{t}=j,S>t)\ p_{jk}\mbox{ % by the Markov property}$ | |||

$\displaystyle=$ | $\displaystyle\sum_{j}\rho_{j}p_{jk}.$ |

$\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

$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

$\sum_{j}Z_{ij}=0\mbox{ for all }i.$ | (2.7) |

$E_{i}T^{+}_{i}=1/\pi_{i}$.

$j$ |

For $j\neq i$,

$j$ |

For $j\neq i$,

$P_{i}(T_{j}<T^{+}_{i})=\frac{1}{\pi_{i}(E_{i}T_{j}+E_{j}T_{i})}.$ |

For $i\neq l$ and arbitrary $j$,

$j$ |

For $i\neq l$ and $j\neq l$,

$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}}.$ |

$\pi_{i}E_{\pi}T_{i}=Z_{ii}$.

$\pi_{j}E_{i}T_{j}=Z_{jj}-Z_{ij}$.

$\sum_{j}\pi_{j}E_{i}T_{j}=\sum_{j}Z_{jj}$ for each $i$.

$\sum_{j}\pi_{j}E_{i}T_{j}$ does not depend on $i$.

$j$ |

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

$j$ |

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

$i$ |

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

$j$ |

$j$ |

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

$j$ |

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

$j$ |

$j$ |

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

$\sum_{t=0}^{t_{0}-1}p^{(t)}_{ii}=\pi_{i}(t_{0}+E_{\rho}T_{i})$ | (2.8) |

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

$\sum_{t=0}^{t_{0}-1}(p^{(t)}_{ii}-\pi_{i})=\pi_{i}E_{\rho}T_{i}.$ |

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

$i$ |

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

$\sum_{t=0}^{t_{0}-1}(p^{(t)}_{ki}-\pi_{i})=\pi_{i}(E_{\rho}T_{i}-E_{k}T_{i}).$ |

Letting $t_{0}\rightarrow\infty$, we have (as above) $\rho\rightarrow\pi$, giving

$Z_{ki}=\pi_{i}(E_{\pi}T_{i}-E_{k}T_{i}).$ |

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

$j$ |

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

$j$ |

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

$j$ |

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

$\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 $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.

Patterns in coin-tossing.

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

$j_{u}=i_{u+d},\ 1\leq u\leq n-d.$ |

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

$c(i,j)=\sum_{d=0}^{n-1}2^{-d}I(i,j,d).$ |

From the definition of ${\bf Z}$, and the fact that $X_{0}$ and $X_{t}$ are independent for $t\geq n$,

$Z_{ij}=c(i,j)-n2^{-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

$i$ |

$j$ |

$k$ |

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

$E_{i}\min(T_{k},T_{l})$ |

$j$ |

$j$ |

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

$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.

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

$Z_{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 $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.

$j$ |

Corollary 2.8. For $j\neq i$,

$P_{i}(T_{j}<T^{+}_{i})=\frac{1}{q_{i}\pi_{i}(E_{i}T_{j}+E_{j}T_{i})}.$ |

Generated on Mon Jun 2 14:23:48 2014 by LaTeXML