2 General Markov Chains (September 10, 1999)

2.3 Variances of sums

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

EπNi(t)=tπi.E_{\pi}N_{i}(t)=t\pi_{i}.

It’s not hard to calculate the variance:

varπNi(t)\displaystyle{\rm var}\ _{\pi}N_{i}(t) =\displaystyle= r=0t-1s=0t-1(Pπ(Xr=i,Xs=i)-πi2)\displaystyle\sum_{r=0}^{t-1}\sum_{s=0}^{t-1}(P_{\pi}(X_{r}=i,X_{s}=i)-\pi^{2}% _{i})
=\displaystyle= πi(u=0t-12(t-u)(pii(u)-πi)-t(1-πi))\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|u=|s-r|. This leads to the asymptotic result

varπNi(t)tπi(2Zii-1+πi).\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:IRf:I\rightarrow R and g:IRg:I\rightarrow R and center so that Eπf(X0):=iπif(i)=0E_{\pi}f(X_{0}):=\sum_{i}\pi_{i}f(i)=0 and Eπg(X0)=0E_{\pi}g(X_{0})=0. Write

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

and similarly for StgS^{g}_{t}. Then

EπStfStg=ijf(i)g(j)r=0t-1s=0t-1(Pπ(Xr=i,Xs=j)-πiπj).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 rsr\leq s equals, putting u=s-ru=s-r,

πiu=0t-1(t-u)(pij(u)-πj)tπiZi,j.\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.

EπStfStgtfΓg:=ijf(i)Γijg(j)\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

Γij:=πiZij+πjZji+πiπj-πiδij.\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

varπNi(t)t2πiZii\frac{{\rm var}\ _{\pi}N_{i}(t)}{t}\rightarrow 2\pi_{i}Z_{ii}

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

Γij:=πiZij+πjZji.\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 ff,

t-1/2StfdNormal(0,fΓf) as t.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 Ni(t)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 vari(Ti+){\rm var}\ _{i}(T^{+}_{i}) of the inter-renewal time, and by (2.22) below this in turn relates to EπTiE_{\pi}T_{i}.