# 2.3 Variances of sums

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.

###### Theorem 2.17

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