4.3 The variation threshold $\tau_{1}$.

Recall from Chapter 2 yyy that $||\ \ \ \ ||$ denotes variation distance and

We define the parameter

The choice of constant $e^{-1}$, and of using $\bar{d}(t)$ instead of $d(t)$, are rather arbitrary, but this choice makes the numerical constants work out nicely (in particular, makes $\tau_{2}\leq\tau_{1}$ – see section 4.4). Submultiplicativity gives

The point of parameter $\tau_{1}$ is to formalize the idea of “time to approach stationarity, from worst starting-place”. The fact that variation distance is just one of several distances one could use may make $\tau_{1}$ seem a very arbitrary choice, but Theorem 4.6 below says that three other possible quantifications of this idea are equivalent. Here equivalent has a technical meaning: parameters $\tau_{a}$ and $\tau_{b}$ are equivalent if their ratio is bounded above and below by numerical constants not depending on the chain. (Thus (4.2) says $\tau^{*}$ and $\max_{j}E_{\pi}T_{j}$ are equivalent parameters). More surprisingly, $\tau_{1}$ is also equivalent to two more parameters involving mean hitting times. We now define all these parameters.

xxx Warning. Parameters $\tau_{1}^{(4)},\tau_{1}^{(5)}$ in this draft were parameters $\tau_{1}^{(3)},\tau_{1}^{(4)}$ in the previous draft.

The first idea is to measure distance from stationarity by using ratios of probabilities. Define separation from stationarity to be

Then $s(\cdot)$ is submultiplicative, so we naturally define the separation threshold time to be

The second idea is to consider minimal random times at which the chain has exactly the stationary distribution. Let

where the $min$ is over stopping times $U_{i}$ such that $P_{i}(X(U_{i})\in\cdot)=\pi(\cdot)$. As a variation on this idea, let us temporarily write, for a probability distribution $\mu$ on the state space,

where the $min$ is over stopping times $U_{i}$ such that $P_{i}(X(U_{i})\in\cdot)=\mu(\cdot)$. Then define

Turning to the parameters involving mean hitting times, we define

where the equality involves the fundamental matrix ${\bf Z}$ and holds by the mean hitting time formula. Parameter $\tau_{1}^{(4)}$ measures variability of mean hitting times as the starting place varies. The final parameter is

Here we can regard the right side as the ratio of $E_{i}T_{A}$, the Markov chain mean hitting time on $A$, to $1/\pi(A)$, the mean hitting time under independent sampling from the stationary distribution.

The definitions above make sense in either discrete or continuous time, but the following notational convention turns out to be convenient. For a discrete-time chain we define $\tau_{1}$ to be the value obtained by applying the definition (4.11) to the continuized chain, and write $\tau_{1}^{{\mbox{disc}}}$ for the value obtained for the discrete-time chain itself. Define similarly $\tau_{1}^{(1)}$ and $\tau_{1}^{1,{\mbox{disc}}}$. But the other parameters $\tau_{1}^{(2)}-\tau_{1}^{(5)}$ are defined directly in terms of the discrete-time chain. We now state the equivalence theorem, from Aldous [12].

This will be (partially) proved in section 4.3.2, but let us first give a few remarks and examples. The parameter $\tau_{1}$ and total variation distance are closely related to the notion of coupling of Markov chains, discussed in Chapter 14. Analogously (see the Notes), the separation $s(t)$ and the parameter $\tau_{1}^{(1)}$ are closely related to the notion of strong stationary times $V_{i}$ for which

Under our standing assumption of reversibility there is a close connection between separation and variation distance, indicated by the next lemma.

Proof. Part (a) is immediate from the definitions. For (b),

Note also that the definition of $s(t)$ involves lower bounds in the convergence $\frac{p_{ij}(t)}{\pi_{j}}\rightarrow 1$. One can make a definition involving upper bounds

where the equality (Chapter 3 Lemma yyy) requires in discrete time that $t$ be even. This yields the following one-sided inequalities, but Example 4.9 shows there can be no such reverse inequality.

Proof. Part (b) follows from part (a) and the definitions. Part (a) is essentially just the “$||\ \ ||_{1}\leq||\ \ ||_{2}$” inequality, but let’s write it out bare-hands.

Here $\pi_{a}=\frac{\varepsilon}{2+\varepsilon},\ \pi_{b}=\pi_{c}=\frac{1}{2+\varepsilon}$. It is easy to check that $\tau_{1}$ is bounded as $\varepsilon\rightarrow 0$. But $p_{aa}(t)\rightarrow e^{-t}$ as $\varepsilon\rightarrow 0$, and so by considering state $a$ we have $\hat{d}(t)\rightarrow\infty$ as $\varepsilon\rightarrow 0$ for any fixed $t$.

Remark. In the nice examples discussed in Chapter 5 we can usually find a pair of states $(i_{0},j_{0})$ such that

The next example shows this is false in general.

for suitably small $\varepsilon$. As $t\rightarrow 0$ we have $1-\bar{d}(t)\sim c_{\varepsilon}t^{2}$, the $max$ attained by pairs $(0,2)$ or $(1,3)$. But as $t\rightarrow\infty$ we have $\bar{d}(t)\sim a_{\varepsilon}\exp(-t/\tau_{2}(\varepsilon))$ where $\tau_{2}(\varepsilon)=\Theta(1/\varepsilon)$ and where the max is attained by pairs $(i,*)$. $\Box$

As a final comment, one might wonder whether the minimizing distribution $\mu$ in the definition of $\tau_{1}^{(3)}$ were always $\pi$, i.e. whether $\tau_{1}^{(3)}=\tau_{1}^{(2)}$ always. But a counter-example is provided by random walk on the $n$-star (Chapter 5 yyy) where $\tau_{1}^{(3)}=1$ (by taking $\mu$ to be concentrated on the center vertex) but $\tau_{1}^{(2)}\rightarrow 3/2$.

We will prove

These lemmas hold in discrete and continuous time, interpreting $tau_{1},\tau_{1}^{(1)}$ as $\tau_{1}^{{\mbox{disc}}},\tau_{1}^{1,{\mbox{disc}}}$ is discrete time. Incidentally, Lemmas 4.12, 4.13 and 4.14 do not depend on reversibility. To complete the proof of Theorem 4.6 in continuous time we would need to show

for some absolute constant $K$. The proof I know is too lengthy to repeat here – see [12]. Note that (from its definition) $\tau_{1}^{(2)}\leq\tau_{0}$, so that (4.15) and the lemmas above imply $\tau_{1}\leq 2K\tau_{0}$ in continuous time. We shall instead give a direct proof of a result weaker than (4.15):

Turning to the assertions of Theorem 4.6 is discrete time, (b) is given by the discrete-time versions of Lemmas 4.11 and 4.12. To prove (a), it is enough to show that the numerical values of the parameters $\tau_{1}^{(2)}--\tau_{1}^{(5)}$ are unchanged by continuizing the discrete-time chain. For $\tau_{1}^{(5)}$ and $\tau_{1}^{(4)}$ this is clear, because continuization doesn’t affect mean hitting times. For $\tau_{1}^{(3)}$ and $\tau_{1}^{(2)}$ it reduces to the following lemma.

Proof of Lemma 4.11. The left inequality is immediate from Lemma 4.7(a), and the right inequality holds because

Proof of Lemma 4.12. The left inequality is immediate from the definitions. For the right inequality, fix $i$. Write $u=\tau_{1}^{(1)}$, so that

We can construct a stopping time $U_{i}\in\{u,2u,3u,\ldots\}$ such that

and then by induction on $m$ such that

Then $P_{i}(X_{U_{i}}\in\cdot)=\pi(\cdot)$ and $E_{i}U_{i}=u(1-e^{-1})^{-1}$. So $\tau_{1}^{(2)}\leq(1-e^{-1})^{-1}\tau_{1}^{(1)}$.

Remark. What the argument shows is that we can construct a strong stationary time $V_{i}$ (in the sense of (4.13)) such that

Proof of Lemma 4.13. Consider the probability distribution $\mu$ attaining the min in the definition of $\tau_{1}^{(3)}$, and the associated stopping times $U_{i}$. Fix $i$. Since $P_{i}(X(U_{i})\in\cdot)=\mu(\cdot)$,

The random target lemma (4.7) says $\sum_{j}E_{i}T_{j}\pi_{j}=\sum_{j}E_{\mu}T_{j}\pi_{j}$ and so

Writing $b(i)$ for the left sum, the definition of $\tau_{1}^{(4)}$ and the triangle inequality give $\tau_{1}^{(4)}\leq\max_{i,k}(b(i)+b(k))$, and the Lemma follows.

Proof of Lemma 4.14. Fix a subset $A$ and a starting state $i\not\in A$. Then for any $j\in A$,

where $\rho$ is the hitting place distribution $P_{i}(X_{T_{A}}\in\cdot)$. So

Proof of Lemma 4.15. For small $\delta>0$ to be specified later, define

Note that Markov’s inequality and the definition of $\tau_{0}$ give

Next, for any $j$

by monotonicity of $p_{jj}(t)$. Thus for $j\in A$ we have

and applying Chapter 3 Lemma yyy (b)

Now let $i$ be arbitrary and let $k\in A$. For any $0\leq s\leq u$,

and so

Now

using Markov’s inequality and the definition of $\tau_{1}^{(5)}$. And $\tau_{1}^{(5)}\leq\tau_{1}^{(4)}\leq 2\tau_{0}$, the first inequality being Lemma 4.14 and the second being an easy consequence of the definitions. Combining (4.18) and the subsequent inequalities shows that, for $k\in A$ and arbitrary $i$

Applying this to arbitrary $i$ and $j$ we get

Putting $t=49\tau_{0},u=17\tau_{0},\delta=1/7$ makes the bound $=\frac{305}{833}<e^{-1}$.

Remark. The ingredients of the proof above are complete monotonicity and conditioning on carefully chosen hitting times. The proof of (4.15) in [12] uses these ingredients, plus the minimal hitting time construction in the recurrent balayage theorem (Chapter 2 yyy).

Outline proof of Lemma 4.16. The observant reader will have noticed (Chapter 2 yyy) that we avoided writing down a careful definition of stopping times in the continuous setting. The definition involves measure-theoretic issues which I don’t intend to engage, and giving a rigorous proof of the lemma is a challenging exercise in the measure-theoretic formulation of continuous-time chains. However, the underlying idea is very simple. Regard the chain $Y_{t}$ as constructed from the chain $(X_{0},X_{1},X_{2},\ldots)$ and exponential($1$) holds $(\xi_{i})$. Define $\hat{T}=N(T)$, where $N(t)$ is the Poisson counting process $N(t)=\max\{m:\xi_{1}+\ldots+\xi_{m}\leq t\}$. Then $X(\hat{T})=Y(T)$ by construction and $E\hat{T}=ET$ by the optional sampling theorem for the martingale $N(t)-t$. $\Box$

Of course for period-$2$ chains we don’t have convergence to stationarity in discrete time, so we regard $\tau_{1}^{{\mbox{disc}}}=\tau_{1}^{1,{\mbox{disc}}}=\infty$. Such chains – random walks on bipartite weighted graphs – include several simple examples of unweighted graphs we will discuss in Chapter 5 (e.g. the $n$-path and $n$-cycle for even $n$, and the $d$-cube) and Chapter 7 (e.g. card-shuffling by random transpositions, if we insist on transposing distinct cards).

As mentioned in Chapter 1 xxx, a topic of much recent interest has been “Markov Chain Monte Carlo”, where one constructs a discrete-time reversible chain with specified stationary distribution $\pi$ and we wish to use the chain to sample from $\pi$. We defer systematic discussion to xxx, but a few comments are appropriate here. We have to start a simulation somewhere. In practice one might use as initial distribution some distribution which is feasible to simulate and which looks intuitively “close” to $\pi$, but this idea is hard to formalize and so in theoretical analysis we seek results which hold regardless of the initial distribution, i.e. “worst-case start” results. In this setting $\tau_{1}^{(2)}$ is, by definition, the minimum expected time to generate a sample with distribution $\pi$. But the definition of $\tau_{1}^{(2)}$ merely says a stopping time exists, and doesn’t tell us how to implement it algorithmically. For algorithmic purposes we want rules which don’t involve detailed structure of the chain. The most natural idea – stopping at a deterministic time – requires one to worry unnecessarily about near-periodicity. One way to avoid this worry is to introduce holds into the discrete-time chain, i.e. simulate $({\bf P}+I)/2$ instead of ${\bf P}$. As an alternative, the distribution of the continuized chain at time $t$ can be obtained by simply running the discrete-time chain for a Poisson($t$) number of steps. “In practice” there is little difference between these alternatives. But the continuization method, as well as being mathematically less artificial, allows us to avoid the occasional messiness of discrete-time theory (see e.g. Proposition 4.29 below). In this sense our use of $\tau_{1}$ for discrete-time chains as the value for continuous-time chains is indeed sensible: it measures the accuracy of a natural algorithmic procedure applied to a discrete-time chain.

Returning to technical matters, the fact that a periodic (reversible, by our standing assumption) chain can only have period $2$ suggests that the discrete-time periodicity effect could be eliminated by averaging over times $t$ and $t+1$ only, as follows.

See the Notes for some comments on this problem.

If one does wish to study distributions of discrete-time chains at deterministic times, then in place of $\tau_{2}$ one needs to use

The spectral representation then implies

In general $\tau_{1}$ may be much smaller than $\tau^{*}$ or $\tau_{0}$. For instance, random walk on the complete graph has $\tau_{0}\sim n$ while $\tau_{1}\rightarrow 1$. So we cannot (without extra assumptions) hope to improve much on the following result.

Lemmas 4.24 and 4.25 later are essentially stronger, giving corresponding upper bounds in terms of $\tau_{2}$ instead of $\tau_{1}$. But a proof of Lemma 4.18 is interesting for comparison with the cat-and-mouse game below.

Proof of Lemma 4.18. By definition of $\tau^{(2)}_{1}$, for the chain started at $i_{0}$ we can find stopping times $U_{1},U_{2},\ldots$ such that

So $S_{j}\equiv\min\{s:X(U_{s})=j\}$ has $E_{i_{0}}S_{j}=1/\pi_{j}$, and so

where the second inequality is justified below. The second assertion of the lemma is now clear, and the first holds by averaging over $j$.

The second inequality is justified by the following martingale result, which is a simple application of the optional sampling theorem. The “equality” assertion is sometimes called Wald’s equation for martingales.

Cat-and-Mouse Game. Here is another variation on the type of game described in Chapter 3 section yyy. Fix a graph. The cat starts at some vertex $v_{c}$ and follows a continuous-time simple random walk. The mouse starts at some vertex $v_{m}$ and is allowed an arbitrary strategy. Recall the mouse can’t see the cat, so it must use a deterministic strategy, or a random strategy independent of the cat’s moves. The mouse seeks to maximize $EM$, the time until meeting. Write $m^{*}$ for the $sup$ of $EM$ over all starting positions $v_{c},v_{m}$ and all strategies for the mouse. So $m^{*}$ just depends on the graph. Clearly $m^{*}\geq\max_{i,j}E_{i}T_{j}$, since the mouse can just stand still.

Here’s a much weaker upper bound on $m^{*}$. Consider for simplicity a regular $n$-vertex graph. Then

Because as remarked at (4.16), we can construct a strong stationary time $V$ such that $EV=\frac{e\tau_{1}^{(1)}}{e-1}=c$, say. So we can construct $0=V_{0}<V_{1}<V_{2}\ldots$ such that

So regardless of the mouse’s strategy, the cat has chance $1/n$ to meet the mouse at time $V_{i}$, independently as $i$ varies, so the meeting time $M$ satisfies $M\leq V_{T}$ where $T$ is a stopping time with mean $n$, and (4.21) follows from Lemma 4.19. This topic will be pursued in Chapter 6 yyy.

Since discrete-time chains can be identified with random walks on weighted graphs, relating properties of the chain to properties of “flows” on the graph is a recurring theme. Thompson’s principle (Chapter 3 yyy) identified mean commute times and mean hitting times from stationarity as infs over flows of certain quantities. Sinclair [307] noticed that $\tau_{1}$ could be related to “multicommodity flow” issues, and we give a streamlined version of his result (essentially Corollary 4.22) here. Recall from Chapter 3 section yyy the general notation of a unit flow from $a$ to $\pi$, and the special flow ${\bf f}^{a\rightarrow\pi}$ induced by the Markov chain.

Proof. We work in discrete time (the continuous case is similar). By Chapter 3 yyy

and so

Thus

The result now follows because by (4.12)

where $i$ and $k$ are not required to be neighbors. $\Box$

Using Lemmas 4.11 - 4.13 to relate $\tau_{1}^{(4)}$ to $\tau_{1}$, we can deduce a lower bound on $\tau_{1}$ in terms of flows.

Unfortunately it seems hard to get analogous upper bounds. In particular, it is not true that

To see why, consider first random walk on the $n$-cycle (Chapter 5 Example yyy). Here $\tau_{1}=\Theta(n^{2})$ and $\psi({\bf f}^{a\rightarrow\pi})=\Theta(n)$, so the upper bound in Lemma 4.21 is the right order of magnitude, since $\Delta=\Theta(n)$. Now modify the chain by allowing transitions between arbitrary pairs $(i,j)$ with equal chance $o(n^{-3})$. The new chain will still have $\tau_{1}=\Theta(n^{2})$, and by considering the special flow in the original chain we have $\inf_{{\bf f}}\psi({\bf f})=O(n)$, but now the diameter $\Delta=1$.