In discrete time, consider the number $N_{i}(t)$ of visits to state $i$ before time $t$. (Recall our convention is to count a visit at time $0$ but not at time $t$.) For the stationary chain, we have (trivially)

$E_{\pi}N_{i}(t)=t\pi_{i}.$ |

It’s not hard to calculate the variance:

$\displaystyle{\rm var}\ _{\pi}N_{i}(t)$ | $\displaystyle=$ | $\displaystyle\sum_{r=0}^{t-1}\sum_{s=0}^{t-1}(P_{\pi}(X_{r}=i,X_{s}=i)-\pi^{2}% _{i})$ | ||

$\displaystyle=$ | $\displaystyle\pi_{i}\left(\sum_{u=0}^{t-1}2(t-u)(p^{(u)}_{ii}-\pi_{i})-t(1-\pi% _{i})\right)$ |

setting $u=|s-r|$. This leads to the asymptotic result

$\frac{{\rm var}\ _{\pi}N_{i}(t)}{t}\rightarrow\pi_{i}(2Z_{ii}-1+\pi_{i}).$ | (2.10) |

The fundamental matrix ${\bf Z}$ of (2.6) reappears in an apparently different context. Here is the more general result underlying (2.10). Take arbitrary functions $f:I\rightarrow R$ and $g:I\rightarrow R$ and center so that $E_{\pi}f(X_{0}):=\sum_{i}\pi_{i}f(i)=0$ and $E_{\pi}g(X_{0})=0$. Write

$S^{f}_{t}=\sum_{s=0}^{t-1}f(X_{s})$ |

and similarly for $S^{g}_{t}$. Then

$E_{\pi}S^{f}_{t}S^{g}_{t}=\sum_{i}\sum_{j}f(i)g(j)\sum_{r=0}^{t-1}\sum_{s=0}^{% t-1}(P_{\pi}(X_{r}=i,X_{s}=j)-\pi_{i}\pi_{j}).$ |

The contribution to the latter double sum from terms $r\leq s$ equals, putting $u=s-r$,

$\pi_{i}\sum_{u=0}^{t-1}(t-u)(p^{(u)}_{ij}-\pi_{j})\sim t\pi_{i}Z_{i,j}.$ |

Collecting the other term and subtracting the twice-counted diagonal leads to the following result.

$\frac{E_{\pi}S^{f}_{t}S^{g}_{t}}{t}\rightarrow f\Gamma g:=\sum_{i}\sum_{j}f(i)% \Gamma_{ij}g(j)$ | (2.11) |

where $\Gamma$ is the symmetric positive-definite matrix

$\Gamma_{ij}:=\pi_{i}Z_{ij}+\pi_{j}Z_{ji}+\pi_{i}\pi_{j}-\pi_{i}\delta_{ij}.$ | (2.12) |

As often happens, the formulas simplify in continuous time. The asymptotic result (2.10) becomes

$\frac{{\rm var}\ _{\pi}N_{i}(t)}{t}\rightarrow 2\pi_{i}Z_{ii}$ |

and the matrix $\Gamma$ occurring in (2.11) becomes

$\Gamma_{ij}:=\pi_{i}Z_{ij}+\pi_{j}Z_{ji}.$ |

Of course these asymptotic variances appear in the central limit theorem for Markov chains.

For centered $f$,

$t^{-1/2}S^{f}_{t}\ \ \stackrel{d}{\rightarrow}\ \ {\rm Normal}(0,f\Gamma f)% \mbox{ as }t\rightarrow\infty.$ |

The standard proofs (e.g. [133] p. 378) don’t yield any useful finite-time results, so we won’t present a proof. We return to this subject in Chapter 4 section 4.1 (yyy 10/11/94 version) in the context of reversible chains. In that context, getting finite-time bounds on the approximation (2.10) for variances is not hard, but getting informative finite-time bounds on the Normal approximation remains quite hard.

Remark. Here’s another way of seeing why asymptotic variances should relate (via ${\bf Z}$) to mean hitting times. Regard $N_{i}(t)$ as counts in a renewal process; in the central limit theorem for renewal counts ([133] Exercise 2.4.13) the variance involves the variance ${\rm var}\ _{i}(T^{+}_{i})$ of the inter-renewal time, and by (2.22) below this in turn relates to $E_{\pi}T_{i}$.

2.2 Identities for mean hitting times and occupation timesBibliography2.4 Two metrics on distributions

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