4.4 The relaxation time $\tau_{2}$

Perhaps the most natural probabilistic interpretation of $\tau_{2}$ is as follows. Recall that the correlation between random variables $Y,Z$ is

For a stationary Markov chain define the maximal correlation function

This makes sense for general chains (see Notes for further comments), but under our standing assumption of reversibility we have

This is a translation of the Rayleigh-Ritz characterization of eigenvalues (Chapter 3 yyy) – we leave the details to the reader.

Now consider a function $g$ with $E_{\pi}g(X_{0})=0$ and $||g||_{2}^{2}\equiv E_{\pi}g^{2}(X_{0})>0$. Write

Recall from Chapter 2 yyy that for general chains there is a limit variance $\sigma^{2}=\lim_{t\rightarrow\infty}t^{-1}{\rm var}\ S_{t}$. Reversibility gives extra qualitative and quantitative information. The first result refers to the stationary chain.

Proof. Consider first the continuous time case. A brief calculation using the spectral representation (Chapter 3 yyy) gives

where $g_{m}=\sum_{i}\pi^{1/2}_{i}u_{im}g(i)$. So

by change of variables in the integral defining $A(u)$. The right side increases with $t$ to

and the sum here is at most $\sum_{m\geq 2}g^{2}_{m}/\lambda_{2}=||g||_{2}^{2}\tau_{2}$. On the other hand, $A(\cdot)$ is increasing, so

In discrete time the arguments are messier, and we will omit details of calculations. The analog of (4.26) becomes

In place of the change of variables argument for (4.27), one needs an elementary calculation to get

This shows

and the sum is bounded above by

Next, rewrite (4.29) as

Then the upper bound for ${\rm var}\ _{\pi}S_{t}$ follows by checking

For the lower bound, one has to verify

where in the sequel we may assume $\lambda_{2}>0$. Then

and so

But

giving the lower bound. $\Box$

Note that even in discrete time it is $\tau_{2}$ that matters in Proposition 4.29. Eigenvalues near $-1$ are irrelevant, except that for a periodic chain we have $\sigma=0$ for one particular function $g$ (which?).

Continuing the study of $S_{t}\equiv\int_{0}^{t}g(X_{s})ds$ or its discrete analog for a stationary chain, standardize to the case where $E_{\pi}g(X_{0})=0,E_{\pi}g^{2}(X_{0})=1$. Proposition 4.29 provides finite-time bounds for the asymptotic approximation of variance. One would like a similar finite-time bound for the asymptotic Normal approximation of the distribution of $S_{t}$.

See the Notes for further comments. For the analogous result about large deviations see Chapter yyy.

Suppose we want to estimate the average $\bar{g}\equiv\sum_{i}\pi_{i}g(i)$ of a function $g$ defined on state space. If we could sample i.i.d. from $\pi$ we would need order $\varepsilon^{-2}$ samples to get an estimator with error about $\varepsilon\sqrt{{\rm var}\ _{\pi}g}$. Now consider the setting where we cannot directly sample from $\pi$ but instead use the “Markov Chain Monte Carlo” method of setting up a reversible chain with stationary distribution $\pi$. How many steps of the chain do we need to get the same accuracy? As in section 4.3.3, because we typically can’t quantify the closeness to $\pi$ of a feasible initial distribution, we consider bounds which hold for arbitrary initial states. In assessing the number of steps required, there are two opposite traps to avoid. The first is to say (cf. Proposition 4.29) that $\varepsilon^{-2}\tau_{2}$ steps suffice. This is wrong because the relaxation time bounds apply to the stationary chain and cannot be directly applied to a non-stationary chain. The second trap is to say that because it take $\Theta(\tau_{1})$ steps to obtain one sample from the stationary distribution, we therefore need order $\varepsilon^{-2}\tau_{1}$ steps in order to get $\varepsilon^{-2}$ independent samples. This is wrong because we don’t need independent samples. The correct answer is order $(\tau_{1}+\varepsilon^{-2}\tau_{2})$ steps. The conceptual idea (cf. the definition of $\tau_{1}^{(2)}$) is to find a stopping time achieving distribution $\pi$ and use it as an initial state for simulating the stationary chain. More feasible to implement is the following algorithm.

Algorithm. For a specified real number $t_{1}>0$ and an integer $m_{2}\geq 1$, generate $M(t_{1})$ with Poisson$(t_{1})$ distribution. Simulate the chain $X_{t}$ from arbitrary initial distribution for $M(t_{1})+m_{2}-1$ steps and calculate

To make the right side approximately $\delta$ we may take

Since the mean number of steps is $t_{1}+m_{2}-1$, this formalizes the idea that we can estimate $\bar{g}$ to within $\varepsilon||g||_{2}$ in order $(\tau_{1}+\varepsilon^{-2}\tau_{2})$ steps.

xxx if don’t know tau‘s

Proof. We may suppose $\bar{g}=0$. Since $X_{M(t_{1})}$ has the distribution of the continuized chain at time $t_{1}$, we may use the definition of $s(t_{1})$ to write

for some probability distribution $\rho$. It follows that

Apply (4.24).

The extremal characterization (4.22) can be used to get lower bounds on $\tau_{2}$ by considering a tractable test function $g$. (xxx list examples). As mentioned in Chapter 3, it is an open problem to give an extremal characterization of $\tau_{2}$ as exactly an inf over flows or similar constructs. As an alternative, Theorem 4.32 gives a non-exact upper bound on $\tau_{2}$ involving quantities derived from arbitrary choices of paths between states. An elegant exposition of this idea, expressed by the first inequality in Theorem 4.32, was given by Diaconis and Stroock [122], and Sinclair [307] noted the second inequality. We copy their proofs.

We first state the result in the setting of random walk on a weighted graph. As in section 4.1, consider a path $x=i_{0},i_{1},\ldots,i_{m}=y$, and call this path $\gamma_{xy}$. This path has length $|\gamma_{xy}|=m$ and has “resistance”

where here and below $e$ denotes a directed edge.

Note that the two inequalities coincide on an unweighted graph.

Proof. For an edge $e=(i,j)$ write $\Delta g(e)=g(j)-g(i)$. The first equality below is the fact $2\ {\rm var}\ (Y_{1})=E(Y_{1}-Y_{2})^{2}$ for i.i.d. $Y$’s, and the first inequality is Cauchy-Schwarz.

where $\kappa$ is the max in the first inequality in the statement of the Theorem. The first inequality now follows from the extremal characterization (4.22). The second inequality makes a simpler use of the Cauchy-Schwarz inequality, in which we replace (4.30,4.31,4.32) by

where $\kappa^{\prime}$ is the max in the second inequality in the statement of the Theorem.

Remarks. (a) Theorem 4.32 applies to continuous-time (reversible) chains by setting $w_{ij}=\pi_{i}q_{ij}$.

(b) One can replace the deterministic choice of paths $\gamma_{xy}$ by random paths $\Gamma_{xy}$ of the form $x=V_{0},V_{1},\ldots,V_{M}=y$ of random length $M=|\Gamma_{xy}|$. The second inequality extends in the natural way, by taking expectations in (4.33) to give

and the conclusion is

(c) Inequalities in the style of Theorem 4.32 are often called Poincaré inequalities because, to quote [122], they are “the discrete analog of the classical method of Poincaré for estimating the spectral gap of the Laplacian on a domain (see e.g. Bandle [39])”. I prefer the descriptive name the distinguished path method. This method has the same spirit as the coupling method for bounding $\tau_{1}$ (see Chapter yyy), in that we get to use our skill and judgement in making wise choices of paths in specific examples. xxx list examples. Though its main utility is in studying hard examples, we give some simple illustrations of its use below.

Write the conclusion of Corollary 4.33 as $\tau_{2}\leq w\max_{e}\frac{1}{w_{e}}\ F(e)$. Consider a regular unweighted graph, and let $\Gamma_{x,y}$ be chosen uniformly from the set of minimum-length paths from $x$ to $y$. Suppose that $F(e)$ takes the same value $F$ for every directed edge $e$. A sufficient condition for this is that the graph be arc-transitive (see Chapter 8 yyy). Then, summing over edges in Corollary 4.33,

where $|\stackrel{\rightarrow}{{\cal E}}|$ is the number of directed edges. Now $w=|\stackrel{\rightarrow}{{\cal E}}|$, so we may reinterpret this inequality as follows.

In the context of the $d$-dimensional torus $Z^{d}_{N}$, the upper bound is asymptotic (as $N\rightarrow\infty$) to $N^{2}E\left(\sum_{i=1}^{d}U_{i}\right)^{2}$ where the $U_{i}$ are independent uniform $[0,1/2]$, This bound is asymptotic to $d(d+1/3)N^{2}/16$. Here (Chapter 5 Example yyy) in fact $\tau_{2}\sim dN^{2}/(2\pi^{2})$, so for fixed $d$ the bound is off by only a constant. On the $d$-cube (Chapter 5 Example yyy), $D$ has Binomial$(d,1/2)$ distribution and so the bound is $ED^{2}=(d^{2}+d)/4$, while in fact $\tau_{2}=d/2$.

Intuitively one feels that the bound in Corollary 4.34 should hold for more general graphs, but the following example illustrates a difficulty.

Here a straightforward implementation of Theorem 4.32 gives an upper bound of $2m$, while in fact $\tau_{2}=m/2$. On the other hand the conclusion of Corollary 4.34 would give an $O(1)$ bound. Thus even though this example has a strong symmetry property (vertex-transitivity: Chapter 8 yyy) no bound like Corollary 4.34 can hold.