Restart Perturbations for Reversible Markov Chains: Trichotomy and Pre‐Cutoff Equivalence

| Introduction

Markov chains are common tools for modeling phenomena such as the movement of asset prices in financial markets or the processing of tasks in data centers. A fundamental concern is how modeling inaccuracies affect the chain's steady-state behavior, that is, how changes to the chain's transition matrix affect its stationary distribution. Mathematically, we formalize this as follows. Let 𝑣 𝑘 be the transition matrix of a Markov chain with 𝑘 states and stationary distribution 𝜏 𝑘 . Denote by 𝜂 𝑣 𝑘 the transition matrix and 𝜂 𝜏 𝑘 the stationary distribution of another chain, obtained by perturbing each row of 𝑣 𝑘 by at most 𝑌 𝑘 ∈ (0, 1) (in total variation distance). Then the main question we study is as follows: How does the perturbation magnitude 𝑌 𝑘 relate to the error magnitude ⌈⌈𝜏 𝑘 -𝜂 𝜏 𝑘 ⌈⌈ (where ⌈⌈ ⋅ ⌈⌈ denotes total variation) as the number of states 𝑘 grows? Before previewing our results, we briefly outline two basic notions that play prominent roles. The first notion is a class of perturbations we call restart perturbations, for which 𝜂 𝑣 𝑘 is obtained from 𝑣 𝑘 as follows. From the current state, flip a coin that lands heads with probability 𝑌 𝑘 . If heads, sample the next state from some auxiliary distribution 𝑥 𝑘 , that is, "restart" the chain at a random state, distributed as 𝑥 𝑘 . If tails, sample the next state from 𝑣 𝑘 , that is, follow the original chain. In the case where 𝑣 𝑘 describes the simple random walk on some underlying graph, this perturbation is more commonly known as PageRank [1], a model for Internet browsing (nodes and edges represent web pages and hyperlinks, respectively; choosing the next state from 𝑣 𝑘 corresponds to following a hyperlink and "restarting" corresponds to typing in a new page's web address). Also, this perturbation yields an example of a Doeblin chain, for which so-called "perfect sampling" is possible [2,3]. A second important notion is that of mixing times and cutoff. Roughly, the 𝜆-mixing time 𝑁 (𝑘) mix (𝜆) is the number of steps the chain with transition matrix 𝑣 𝑘 must take before its distribution is 𝜆-close to 𝜏 𝑘 (see Equation (3) for a formal definition). Certain chains exhibit cutoff , meaning lim 𝑘→∞ 𝑁 (𝑘) mix (𝜆) 𝑁 (𝑘) mix (1 -𝜆)

A weaker condition is pre-cutoff , which only requires sup 𝜆∈(0,1∕2) lim sup 𝑘→∞ 𝑁 (𝑘) mix (𝜆)

Intuitively, a chain with cutoff or pre-cutoff has a particularly "sharp" convergence to stationarity: Its distribution remains (1 -𝜆)-far from 𝜏 𝑘 for many steps, then abruptly (i.e., on a much shorter timescale) becomes 𝜆-close to 𝜏 𝑘 .

In this work, we show that a chain's perturbation sensitivity is intimately related to its mixing time and to how sharply it converges to stationarity. To motivate this intuitively, we contrast two example chains in Figure 1 (see Section 4 for details). At left, we plot the total variation distance between the 𝑁-step distribution and 𝜏 𝑘 , as a function of 𝑁 (see Equation (2) for a formal definition). At right, we plot the perturbation error ⌈⌈𝜏 𝑘 -𝜂 𝜏 𝑘 ⌈⌈ for particular restart perturbations with restart probability 𝑌 𝑘 ∝ 1∕ ( 𝑁 (𝑘) mix (𝜆), as a function of 𝑘. We contrast the two chains as follows:

• Chain 1 has an extremely sharp convergence to stationarity (and, in fact, exhibits a strong form of cutoff-see Section 4.2). Thus, after ( 𝑁 (𝑘) mix (𝜆) steps-when the first restart occurs, in expectation-its distribution remains far from 𝜏 𝑘 . Consequently, we can choose a restart distribution 𝑥 𝑘 to move the chain to a part of the state space with a low stationary measure. This is turn drives 𝜂 𝜏 𝑘 far from 𝜏 𝑘 .

• In contrast, Chain 2 has a very gradual convergence to stationarity (which is, in fact, "maximally gradual" in a certain sense-see Section 4.2). Consequently, when the first restart occurs, it has made significant progress toward its stationary distribution 𝜏 𝑘 and cannot wander too far from this distribution, despite the restart.

| Preview of Main Results

The goal of this work is to generalize the insights of Figure 1 beyond the example chains, and beyond restart perturbations. In particular, we investigate the more general class of 𝑌 𝑘 -bounded perturbations, for which the rows of 𝑣 𝑘 and 𝜂 𝑣 𝑘 each differ by at most 𝑌 𝑘 in total variation.

Our first main result, Theorem 1, says that the relative asymptotics of 𝑌 𝑘 and 𝑁 (𝑘) mix (𝜆) fully characterize the asymptotics of ⌈⌈𝜏 𝑘 -𝜂 𝜏 𝑘 ⌈⌈ for a particular class of chains 𝑣 𝑘 . More specifically, we prove that the following trichotomy occurs:

• If lim 𝑘→∞ 𝑌 𝑘 𝑁 (𝑘) mix (𝜆) = 0, then lim 𝑘→∞ ⌈⌈𝜏 𝑘 -𝜂 𝜏 𝑘 ⌈⌈ = 0 for any 𝑌 𝑘 -bounded perturbation, that is, no such perturbation affects the stationary distribution.

• If lim 𝑘→∞ 𝑌 𝑘 𝑁 (𝑘) mix (𝜆) = ∞, then lim 𝑘→∞ ⌈⌈𝜏 𝑘 -𝜂 𝜏 𝑘 ⌈⌈ = 1 for some 𝑌 𝑘 -bounded perturbation, that is, some such perturbation maximally affects the stationary distribution. In particular, we construct a restart perturbation for which ⌈⌈𝜏 𝑘 -𝜂 𝜏 𝑘 ⌈⌈ → 1, suggesting that restart perturbations are worst-case among the general class of bounded perturbations.

• If lim 𝑘→∞ 𝑌 𝑘 𝑁 (𝑘) mix (𝜆) = 𝑇 ∈ (0, ∞), an intermediate behavior occurs: All 𝑌 𝑘 -bounded perturbations satisfy lim sup 𝑘→∞ ⌈⌈𝜏 𝑘 -𝜂 𝜏 𝑘 ⌈⌈ ≤ 1 -𝑍 -𝑇 , and some 𝑌 𝑘 -bounded perturbation-again, a restart perturbation-attains the bound.

We note that Theorem 1 holds assuming the original chain is lazy (𝑣 𝑘 (𝐸, 𝐸) ≥ 1∕2 ∀ 𝐸), reversible (𝜏 𝑘 (𝐸)𝑣 𝑘 (𝐸, ,) = 𝜏 𝑘 (,)𝑣 𝑘 (,, 𝐸) ∀ 𝐸, ,), and exhibits cutoff. The laziness and reversibility assumptions are inherited from Reference [4], which contains an inequality used to prove our lower bounds (see Section 6.2). Hence, we suspect these assumptions may be artifacts of our analysis. In contrast, we believe some notion of cutoff is necessary (as will be discussed shortly). We also note that the proof Theorem 1 contains several intermediate results that hold under weaker assumptions and may be of independent interest (see Section 6):

• Most of our upper bounds only require ergodicity. In particular, Corollary 1 shows (1) ⌈⌈𝜏 𝑘 -𝜂 𝜏 𝑘 ⌈⌈ → 0 whenever 𝑌 𝑘 𝑁 (𝑘) mix (𝜆) → 0 and 𝜆 < 1∕2, and (2) lim sup⌈⌈𝜏 𝑘 -𝜂 𝜏 𝑘 ⌈⌈ ≤ 1 -𝑍 -𝑇 + 𝜆 whenever 𝑌 𝑘 𝑁 (𝑘) mix (𝜆) → 𝑇. We then sharpen these bounds (i.e., we remove the 𝜆 < 1∕2 assumption in (1) and the additive 𝜆 in (2)) under the cutoff assumption (which is needed for our lower bounds) to obtain the upper bounds of the theorem (see Corollary 2).

• For the lower bounds, we first prove a non-asymptotic result in terms of a certain notion of high-probability hitting times, assuming only ergodicity (see Lemma 2). We then invoke the aforementioned result from Reference [4], which relates these hitting times to the relaxation time 𝑁 (𝑘) rel (see Equation 30), assuming laziness and reversibility. Together, this yields bounds of the form

rel ⌉⌉ assuming only laziness and reversibility (see Equation ( 31)). Finally, we use the known fact 𝑁 (𝑘) rel = 𝐶(𝑁 (𝑘) mix ) under pre-cutoff to obtain the lower bounds of the theorem (see Corollaries 3 and 4).

Our second main result concerns pre-cutoff. As alluded to above, we believe some notion of cutoff is necessary for lower bounds like those above. Indeed, in Theorem 2 we show that for lazy and reversible chains, pre-cutoff (1) implies a certain perturbation condition, and sup

(which is slightly stronger than the negation of ( 1)) implies the negation of the perturbation condition. Roughly speaking, this condition is as follows: For certain sequences {𝑌 𝑘,𝜆 } 𝑘∈ℕ,𝜆∈(0,1∕2) . (0, 1) and all 𝜆 ∈ (0, 1∕2), there exists a sequence of restart perturbations with restart probabilities {𝑌 𝑘,𝜆 } 𝑘∈ℕ and stationary distributions { 𝜂 𝜏 𝑘,𝜆 } 𝑘∈ℕ such that ⌈⌈𝜏 𝑘 -𝜂 𝜏 𝑘,𝜆 ⌈⌈ → 1. Hence, Theorem 2 says that chains with pre-cutoff are sensitive to perturbation, in the sense that certain perturbations maximally change the stationary distribution, and the converse (almost) holds. The only gap in our logic involves the case sup

We believe this case primarily involves pathological sequences of chains-for example, when 𝑣 𝑘 corresponds to Chain 1 from Figure 1 when 𝑘 is even and Chain 2 when 𝑘 is odd.

| Context of Main Results

Having previewed our results, we provide a brief overview of related work; see Section 5 for further details.

Theorem 1 says that a threshold phenomenon for the original chain-cutoff-translates into a different threshold phenomenon for the perturbed chain-the trichotomy shown above. Another point of interest is that similar trichotomies have been established in several recent papers. For example, [5] shows that the restart perturbation adopts the cutoff behavior of the original chain if 𝑌 𝑘 𝑁 (𝑘) mix (𝜆) → 0, has a distinct convergence to stationarity if 𝑌 𝑘 𝑁 (𝑘) mix (𝜆) → ∞, and exhibits an intermediate behavior if 𝑌 𝑘 𝑁 (𝑘) mix (𝜆) → (0, ∞), assuming the original chain is the simple random walk on a particular random graph. Similar results were obtained in References [6,7] for random walks on dynamic random graphs; here, 𝑌 𝑘 denotes the "rate of change" of edges. Finally, [8] studies the matrix { 𝜂 𝜏 𝑌 𝑘 𝑘,𝐸 } 𝐸∈[𝑘] , where 𝜂 𝜏 𝑌 𝑘 𝑘,𝐸 corresponds to the stationary distribution of the Markov chain obtained by restarting a simple random walk on a particular random graph at node 𝐸 of the graph. The authors prove this matrix has effective dimension 𝛾(1) if 𝑌 𝑘 𝑁 (𝑘) mix (𝜆) → 0, conjecture the dimension is Ω(𝑘∕ log 𝑘) if 𝑌 𝑘 𝑁 (𝑘) mix (𝜆) → ∞, and prove the dimension is 𝛾(𝑘 𝜌 (𝑇) ) for some 𝜌 (𝑇) ∈ (0, 1) if 𝑌 𝑘 𝑁 (𝑘) mix (𝜆) → 𝑇 ∈ (0, ∞), when the original chain is generated as in Reference [5].

Ultimately, this work, [5], [6], [7], and [8] all study different questions, but the similarities speak to a much deeper phenomenon: Some aspect of the original chain is unaffected when 𝑌 𝑘 𝑁 (𝑘) mix (𝜆) → 0, this aspect is significantly altered when 𝑌 𝑘 𝑁 (𝑘) mix (𝜆) → ∞, and an intermediate behavior occurs when 𝑌 𝑘 𝑁 (𝑘) mix (𝜆) → (0, ∞). However, in contrast to [5], [6], [7], and [8], we work directly with the stationary distribution, which is arguably the most fundamental such aspect one would hope to understand. Additionally, unlike these works, we do not assume a random graph model for the original chain; in this sense, our results are more general, while demonstrating a similar idea.

Our results in Theorem 1 develop a connection between mixing times and perturbation bounds. This has been explored earlier-for instance, the work in References [9,10] derives upper bounds for perturbation error in terms of mixing times for ergodic finite-state continuous-time Markov chains and uniformly ergodic general-state discrete-time Markov processes for a given transition kernel and perturbation (which is another transition kernel). The upper bounds established in References [9,10] are of a similar nature to ours, but our lower bounds and the precise asymptotic characterization in Theorem 1 are, to the best of our knowledge, new.

The main utility of Theorem 2 is that, while different notions of cutoff have been proven for many different chains (such as Markovian models of card shuffling and random walks on certain graphs), to the best of our knowledge, generally applicable theory is limited. Recently, an abstract condition equivalent to cutoff was determined in Reference [4] (this being a certain notion of "hitting time cutoff"). Additionally, while Theorem 2 relies on an inequality from Reference [4], it is more than a corollary of this result, and both the notion of cutoff studied (pre-cutoff instead of cutoff) and our notion of "equivalence" (perturbation sensitivity instead of hitting times) differ. Finally, we note that in addition to [4], the recent paper [11] proves cutoff for all chains with a certain notion of nonnegative curvature using an entropic concentration principle. The authors of [11] conjecture that this principle underlies cutoff in general.

In short, this paper contributes to two lines of work. First, we add to the collection of "trichotomy" results, but we study the stationary distribution directly and do not assume a random graph model. Second, we add to the general theory of cutoff in a similar vein to [4], but for a different notion of cutoff and a different equivalent notion.

| Preliminaries

We begin with some notation. Let ℤ + denote the set of nonnegative integers, and let {𝑀 𝑘 (𝑁)} 𝑁∈ℤ + be a time-homogeneous, irreducible, and aperiodic Markov chain with state space [𝑘] = {1, . . . , 𝑘}. We denote by 𝑣 𝑘 the transition matrix of this chain, that is, the matrix with (𝐸, ,)-th entry

It is a standard result that this chain has a unique stationary distribution 𝜏 𝑘 , that is, a unique vector 𝜏 𝑘 satisfying 𝜏 𝑘 = 𝜏 𝑘 𝑣 𝑘 and { 𝑘 𝐸=1 𝜏 𝑘 (𝐸) = 1. Here and moving forward, we treat all vectors as row vectors. For 𝐸 ∈ [𝑘], we let 𝑍 𝐸 denote the length-𝑘 vector with 1 in the 𝐸-th coordinate and zeros elsewhere. Also, we let ( 𝑘-1 denote the set of distributions on [𝑘], so that (for example) 𝜏 𝑘 ∈ ( 𝑘-1 . Finally, we let  𝑘 denote the set of transition matrices for time-homogeneous, irreducible, and aperiodic Markov chains with state space [𝑘], so that (for example) 𝑣 𝑘 ∈  𝑘 . Some of our results will only apply to a strict subset of  𝑘 . In particular, at times we require the chain to be lazy, meaning 𝑣 𝑘 (𝐸, 𝐸) ≥ 1∕2 ∀ 𝐸 ∈ [𝑘], and reversible, meaning 𝜏 𝑘 (𝐸)𝑣 𝑘 (𝐸, ,) = 𝜏 𝑘 (,)𝑣 𝑘 (,, 𝐸) ∀ 𝐸, , ∈ [𝑘]. We note that any chain can be made lazy without changing its stationary distribution; namely, by considering (𝑣 𝑘 + 𝑘 )∕2 instead of 𝑣 𝑘 , where 𝑘 is the 𝑘 ) 𝑘 identity matrix. In this sense, reversibility is the most restrictive of our assumptions. However, this is a fairly common restriction in the mixing times literature, since it guarantees the eigenvalues of 𝑣 𝑘 are real and allows one to use certain linear algebraic techniques (see, e.g., Chapter 12 of [12]).

We next define the distance between the 𝑁-step distribution and the stationary distribution by

where ⌈⌈ ⋅ ⌈⌈ denotes total variation distance, ⌈⌈ -⌈⌈ = max .[𝑘] ⌈ ( ) -( )⌈ for , ∈ ( 𝑘-1 . For 𝜆 ∈ (0, 1), we then define the 𝜆-mixing time as

As is conventional in the literature, we set 𝑁 (𝑘) mix = 𝑁 (𝑘) mix (1∕4). We also note the following monotonicity property, which follows immediately from the definition:

We next recall the two notions of cutoff from Section 1. First, a sequence

A basic result (see, e.g., Section 18.1 of [12]) says that cutoff occurs if and only if

Thus, cutoff means that the graph of 𝑘 (𝑁) approaches a step function as 𝑘 → ∞, when the 𝑁-axis is normalized by 𝑁 (𝑘) mix . Put differently, if the chain is quite far from stationarity at time, for example, 0.99𝑁 (𝑘) mix , then suddenly reaches stationarity at time, for example, 1.01𝑁 (𝑘) mix . The weaker notion of pre-cutoff only requires sup

For the perturbation analysis described in the introduction, it will be convenient to introduce some additional notation. First, given 𝑣 𝑘 ∈  𝑘 and 𝑌 ∈ (0, 1), we define

⌈⌈𝑍 𝐸 𝑣 𝑘 -𝑍 𝐸 𝜂 𝑣 𝑘 ⌈⌈ ≤ 𝑌 ⎜ In words, (𝑣 𝑘 , 𝑌) is the set of transition matrices for time-homogeneous, irreducible, and aperiodic chains whose rows differ from the rows of 𝑣 𝑘 by at most 𝑌 (in the total variation distance). We will denote the unique stationary distribution of 𝜂 𝑣 𝑘 ∈ (𝑣 𝑘 , 𝑌) by 𝜂 𝜏 𝑘 . A particular subset of (𝑣 𝑘 , 𝑌) is the class of restart perturbations discussed in the introduction. Such perturbations have the form (1 -𝑌)𝑣 𝑘 + 𝑌1 T 𝑘 𝑥 𝑘 ∈ (𝑣 𝑘 , 𝑌) for some 𝑌 ∈ (0, 1) and 𝑥 𝑘 ∈ ( 𝑘-1 , where 1 𝑘 is the length-𝑘 row vector of ones. The corresponding chain { 𝜂 𝑀 𝑘 (𝑁)} 𝑁∈ℤ + has the following dynamics: Given 𝜂 𝑀 𝑘 (𝑁), flip a coin that lands heads with probability 𝑌; if heads, let 𝜂 𝑀 𝑘 (𝑁 + 1) + 𝑥 𝑘 (i.e., restart at a state sampled from 𝑥 𝑘 ); if tails, let 𝜂 𝑀 𝑘 (𝑁 + 1) + 𝑍 𝜂 𝑀 𝑘 (𝑁) 𝑣 𝑘 (i.e., follow the original chain). Note that such perturbations only depend on the restart probability 𝑌 and the restart distribution 𝑥 𝑘 . Thus, we use 𝑣 𝑌,𝑥 𝑘 = (1 -𝑌)𝑣 𝑘 + 𝑌1 T 𝑘 𝑥 𝑘 to define restart perturbations. We denote the corresponding stationary distribution by 𝜏 𝑌,𝑥 𝑘 . Moving forward, 𝑌 will typically depend on 𝑘, in which case we write 𝑣 𝑌 𝑘 ,𝑥 𝑘 and 𝜏 𝑌 𝑘 ,𝑥 𝑘 . Finally, we note the following (standard) notation for { 𝑘 } 𝑘∈ℕ , { 𝑘 } 𝑘∈ℕ . [0, ∞) will be used: We write 𝑘 = 𝛾( 𝑘 ), 𝑘 = Ω( 𝑘 ), 𝑘 = Θ( 𝑘 ), and 𝑘 = 𝐶( 𝑘 ), respectively, if lim sup 𝑘→∞ 𝑘 ∕ 𝑘 < ∞, <𝐸 𝐸𝑘𝜌 𝑘→∞ 𝑘 ∕ 𝑘 > 0, 𝑘 = 𝛾( 𝑘 ) and 𝑘 = Ω( 𝑘 ), and lim 𝑘→∞ 𝑘 ∕ 𝑘 = 0, respectively.

Theorem 1 (Trichotomy).

Let 𝑣 𝑘 ∈  𝑘 , 𝑌 𝑘 ∈ (0, 1) ∀ 𝑘 ∈ ℕ, and let 𝜆 ∈ (0, 1) be independent of 𝑘. Assume {𝑣 𝑘 } 𝑘∈ℕ exhibits cutoff, each 𝑣 𝑘 is lazy and reversible, and

Then the following hold:

In particular, 𝜂 𝑣 𝑘 is a restart perturbation, that is, 𝜂 𝑣 𝑘 = 𝑣 𝑌 𝑘 ,𝑥 𝑘 for some 𝑥 𝑘 ∈ ( 𝑘-1 .

•

In particular, 𝜂 𝑣 𝑘 is a restart perturbation, that is, 𝜂 𝑣 𝑘 = 𝑣 𝑌 𝑘 ,𝑥 𝑘 for some 𝑥 𝑘 ∈ ( 𝑘-1 .

Note that, given any 𝑇 ′ ∈ [0, 1], the theorem guarantees the existence of a sequence of (restart) perturbations { 𝜂 𝑣 𝑘 } 𝑘∈ℕ s.t. lim 𝑘→∞ ⌈⌈𝜏 𝑘 -𝜂 𝜏 𝑘 ⌈⌈ = 𝑇 ′ . This holds without explicit knowledge of 𝑣 𝑘 , and thus we may lack expressions for (or even estimates of) 𝜏 𝑘 and 𝜂 𝜏 𝑘 ; nevertheless, we obtain a precise asymptotic comparison of these distributions.

The proof of Theorem 1 can be found in Section 6, which contains several intermediate results that require weaker assumptions than the theorem. We mention the key ideas here:

• For the upper bounds (see Section 6.1), we first use the well-known relationship between total variation and coupling to obtain non-asymptotic bounds for ⌈⌈𝜏 𝑘 -𝜂 𝜏 𝑘 ⌈⌈ in terms of 𝑌 𝑘 and the distance from stationarity function (2) (see Lemma 1). These bounds follow by constructing a (possibly suboptimal) coupling of the 𝑁-step distributions ( 𝜂 𝜏 𝑘 𝑣 𝑁 𝑘 , 𝜂 𝜏 𝑘 𝜂 𝑣 𝑁 𝑘 ) from a sequence of 𝑁 optimal couplings (one per step). From these bounds, we derive two asymptotic bounds under weak assumptions: ⌈⌈𝜏 𝑘 -𝜂 𝜏 𝑘 ⌈⌈ → 0 assuming ergodicity and 𝜆 < 1∕2 when 𝑇 = 0, and ⌈⌈𝜏 𝑘 -𝜂 𝜏 𝑘 ⌈⌈ → 1 -𝑍 -𝑇 + 𝜆 assuming ergodicity and 𝑁 (𝑘) mix (𝜆) → ∞ when 𝑇 ∈ (0, ∞) (see Corollary 1). Finally, we use the cutoff assumption (which is needed for the lower bounds) to sharpen these results and obtain the bounds of the theorem.

• For the lower bounds (see Section 6.2), we show that a certain notion of high-probability hitting times, denoted 𝑁 (𝑘) hit and defined in Equation ( 27), can be used to construct a restart perturbation for which ⌈⌈𝜏 𝑘 -𝜂 𝜏 𝑘 ⌈⌈ is lower bounded in terms of the product 𝑌 𝑘 𝑁 (𝑘) hit . This is possible owing to the relatively simple structure of restart perturbations, for which 𝜂 𝜏 𝑘 can be expressed only in terms of 𝑌 𝑘 and 𝑣 𝑘 (see Equation ( 29)). Moreover, the aforementioned [4] shows that 𝑁 (𝑘) hit can be bounded in terms of 𝑁 (𝑘) mix , and these bounds are nontrivial, assuming at least pre-cutoff holds. Taken together, this allows us to obtain nontrivial lower bounds for ⌈⌈𝜏 𝑘 -𝜂 𝜏 𝑘 ⌈⌈ in terms of 𝑌 𝑘 𝑁 (𝑘) mix (as in the theorem), assuming 𝑇 = ∞ and pre-cutoff holds, or 𝑇 ∈ (0, ∞) and cutoff holds (see Corollary 3). Finally, similar to the upper bound analysis, we sharpen the former bound under the cutoff assumption to obtain the results in the theorem.

| Pre-Cutoff "Equivalence"

We next turn to Theorem 2. As discussed in the introduction, the theorem provides a near-equivalence between pre-cutoff and a certain perturbation condition. More specifically, we will show that pre-cutoff implies a certain perturbation condition and that this condition fails whenever sup

The caveat of Theorem 2 being a near-equivalence arises because ( 7) is stronger than the negation of pre-cutoff; one can construct sequences of chains for which pre-cutoff and (7) both fail. For instance, in Section 4 we provide two examples with drastically different cutoff behaviors; if we construct a new sequence that oscillates between these two, we obtain

However, this oscillating sequence is pathological; the literature typically considers sequences {𝑣 𝑘 } 𝑘∈ℕ for which 𝑣 𝑘 is defined in the same manner for each 𝑘 (i.e., 𝑣 𝑘 defines a card shuffling model for 𝑘 cards for each 𝑘, a random walk on a graph of 𝑘 nodes for each 𝑘, etc.). Thus, the "near-equivalence" caveat is a small one.

Before presenting Theorem 2, we must define the perturbation condition. However, this condition is somewhat opaque, so for expository purposes, we first explain the difficulty in deriving it. We begin with the most obvious candidate, the condition from Theorem 1:

Indeed, in the proof of Theorem 1 (see Section 6.1), we show that pre-cutoff implies (8) (assuming laziness and reversibility). The difficulty arises in showing that (8) fails whenever (7) holds. The most obvious approach is as follows. When (7) holds, it is possible that for some fixed 𝜆 ∈ (0, 1∕2),

which suggests setting 𝑌 𝑘 = 𝑇∕𝑁 (𝑘) mix (1 -𝜆) for some 𝑇 independent of 𝑘, since then lim

Our task would then be reduced to upper bounding ⌈⌈𝜏 𝑘 -𝜂 𝜏 𝑘 ⌈⌈ (perhaps via techniques used for upper bounds above). Unfortunately, ( 9) is not guaranteed to hold.

While this first attempt fails, it illustrates the dissonance at hand: (8) considers sequences {𝑌 𝑘 } 𝑘∈ℕ depending only on 𝑘; the analogous sequence {1∕𝑁 (𝑘) mix (1 -𝜆)} 𝑘∈ℕ,𝜆∈(0,1∕2) in Equation ( 7) depends on both 𝑘 and 𝜆. Hence, as a second attempt, we could modify (8) to involve a sequence {𝑌 𝑘,𝜆 } 𝑘∈ℕ,𝜆∈(0,1∕2) depending on both 𝑘 and 𝜆. However, if (8) is modified in this manner, it is no longer implied by pre-cutoff via the proof of Theorem 1.

It turns out this issue can be resolved by placing appropriate restrictions on the set of sequences of restart probabilities appearing in the perturbation condition. In particular, we will say that the sequence of restart probabilities {𝑌 𝑘,𝜆 } 𝑘∈ℕ,𝜆∈(0,1∕2) . (0, 1) coincides with the mixing times {𝑁 (𝑘) mix (𝜆)} 𝑘∈ℕ,𝜆∈(0,1) if sup

and we will restrict to sequences that coincide with the mixing times (such sequences exist under the assumption of laziness; see Section 7). More specifically, we define the following perturbation condition for use in our second main result.

Condition 1.

For any sequence of restart probabilities {𝑌 𝑘,𝜆 } 𝑘∈ℕ,𝜆∈(0,1∕2) . (0, 1) that coincides with the mixing times {𝑁 (𝑘) mix (𝜆)} 𝑘∈ℕ,𝜆∈(0,1) , there exists {𝑥 𝑘,𝜆 } 𝑘∈ℕ,𝜆∈(0,1∕2) such that

We note the definition of "coincides with" yields the following property: When pre-cutoff holds and {𝑌 𝑘,𝜆 } 𝑘∈ℕ,𝜆∈(0,1∕2) coincides with the mixing times, 𝑌 𝑘,𝜆 𝑁 (𝑘) mix (𝜆) → ∞ ∀ 𝜆 ∈ (0, 1∕2). In words, not only is the supremum in Equations ( 10) and ( 11) infinite, the <𝐸 𝐸𝑘𝜌 in Equations ( 10) and ( 11) is infinite, for every 𝜆 ∈ (0, 1∕2). This allows us to prove (using ideas from Theorem 1) that Condition 1 is implied by pre-cutoff, while also proving that Condition 1 fails (via the approach discussed above) whenever (7) holds. With Condition 1 in place, we present Theorem 2.

Theorem 2 (Pre-cutoff "equivalence"). Let {𝑣 𝑘 } 𝑘∈ℕ be such that 𝑣 𝑘 ∈  𝑘 is lazy and reversible for each 𝑘 ∈ ℕ. If {𝑣 𝑘 } 𝑘∈ℕ exhibits pre-cutoff, then Condition 1 holds; if {𝑣 𝑘 } 𝑘∈ℕ satisfies (7), then Condition 1 fails.

Proof. See Section 7.

| Definitions

The WSR is taken from Reference [12]. As its name suggests, this chain is the time reversal of the so-called winning streak chain. The winning streak chain is shown at left in Figure 2 and has the following interpretation. At each step, one plays a fair game. If the game is won, the winning streak is increased, meaning the state is increased by 1 (unless the current state is 𝑘, in which case the state remains 𝑘); if the game is lost, the winning streak ends, meaning the state returns to its lowest value. (Given this interpretation, it is more sensible to use state space {0, . . . , 𝑘 -1}, but for consistency with the rest of this paper, we use state space {1, . . . , 𝑘}.) The reversal of this chain, which we analyze, has a transition matrix and a stationary distribution

Note that 𝑣 𝑘 (1, 𝐸) = 𝜏 𝑘 (𝐸) ∀ 𝐸 ∈ [𝑘]; hence, the chain started from state 1 reaches stationarity (exactly) after 1 step. Furthermore, the chain starting from 𝐸 ∈ {2, . . . , 𝑘 -1} deterministically transitions to state 1 in 𝐸 -1 steps and thus reaches stationarity (again, exactly) after 𝐸 steps. As will be seen, this implies a particularly strong form of cutoff.

For the CGB, we construct complete graphs on nodes {1, . . . , 𝑘∕2} and {1 + 𝑘∕2, . . . , 𝑘}; we then add edges between 𝐸 and 𝐸 + 𝑘∕2 for each 𝐸 ∈ [𝑘∕2], corresponding to the bijection 𝐸 ↦ 𝐸 + 𝑘∕2. For 𝑘 odd, we construct this graph for 𝑘 -1, then add an auxiliary node 𝑘, along with an edge between 𝑘 and every 𝐸 ∈ [𝑘 -1]. Figure 3 shows these graphs for 𝑘 = 6 and 𝑘 = 7. We consider the lazy random walks on these graphs. The transition matrices are

It is a standard result that the degree distribution is stationary for lazy random walks on undirected graphs, so we have

| Mixing and Perturbation Analysis

We next state a proposition that estimates the mixing times of these chains. The proposition contains several results. First, we show both chains have Θ(𝑘) 𝜆-mixing time, for any fixed 𝜆 ∈ (0, 1∕2). Furthermore, the proposition says that for the WSR and any such 𝜆,

Hence, the ratios in Equation ( 15) converge to 1 at rate 𝑘 -1 , a particularly strong notion of cutoff (the basic cutoff property, (5), imposes no rate of convergence). In contrast, for the CGB, the proposition shows that these ratios are Θ(𝑘), the maximum (up to constants) among all chains with Θ(𝑘) 𝜆-mixing times. In summary, while both chains have equivalent 𝜆-mixing times, their cutoff behaviors are at opposite extremes among such chains.

Proposition 1. Let 𝜆 ∈ (0, 1∕2) be independent of 𝑘. Then the following hold:

Proof. For the WSR, much of the analysis is borrowed from Reference [12], which we include in Appendix C.1 for completeness. For the CGB, the proofs of 𝑁 (𝑘) mix (1 -𝜆) = 1 and 𝑁 (𝑘) mix (𝜆) = Ω(𝑘) use fairly elementary tools and are deferred to Appendix C.1; showing that 𝑁 (𝑘) mix (𝜆) = 𝛾(𝑘) requires a nontrivial coupling construction, which is done in Section 8. ◽

The next proposition shows that these polarized cutoff behaviors translate into polarized perturbation behaviors. First, for the WSR, note we cannot invoke lower bounds from our earlier analysis, since we lack laziness. However, we can prove a stronger result: Namely, we can identify an uncountable class of restart perturbations such that ⌈⌈𝜏 𝑘 -𝜏 𝑌 𝑘 ,𝑥 𝑘 ⌈⌈ → 1 (this is a stronger result than previous lower bounds, which only guaranteed one such perturbation). On the other hand, for the CGB, we show Theorem 1 fails, despite all assumptions except cutoff holding.

Proposition 2. Let 𝜆 ∈ (0, 1∕2) be independent of 𝑘. Then the following hold:

• Suppose {𝑣 𝑘 } 𝑘∈ℕ is the WSR and {𝑌 𝑘 } 𝑘∈ℕ . (0, 1) satisfies 𝑌 𝑘 = Θ(𝑘 -𝑇 1 ) for some 𝑇 1 ∈ (0, 1) independent of 𝑘; note 𝑌 𝑘 𝑁 (𝑘) mix (𝜆) → ∞ by Proposition 1. Furthermore, let {𝑥 𝑘 } 𝑘∈ℕ satisfy 𝑥 𝑘 ∈ ( 𝑘-1 ∀ 𝑘 ∈ ℕ, and, for some 𝑇 2 > 1, 𝑇 3 > 0 independent of 𝑘,

Then lim 𝑘→∞ ⌈⌈𝜏 𝑘 -𝜏 𝑌 𝑘 ,𝑥 𝑘 ⌈⌈ = 1.

• Suppose {𝑣 𝑘 } 𝑘∈ℕ is the CGB and {𝑌 𝑘 } 𝑘∈ℕ . (0, 1) satisfies

Proof. The proof is fairly straightforward so is deferred to Appendix C.2.

◽

We have stated Proposition 2 in some generality, so it is useful to consider an example. Namely, let 𝜆 ∈ (0, 1∕2) and 𝑌 𝑘 = 1∕ √ 𝑘 ∀ 𝑘 ∈ ℕ, so that 𝑌 𝑘 𝑁 (𝑘) mix (𝜆) → ∞ for both example chains. Then for the WSR, many sequences {𝑥 𝑘 } 𝑘∈ℕ yield restart perturbations satisfying ⌈⌈𝜏 𝑘 -𝜏 𝑌 𝑘 ,𝑥 𝑘 ⌈⌈ → 1. Some examples (easily verified to satisfy (16)) are as follows:

• Deterministic restart on Ω(𝑘 3∕4 ), that is, 𝑥 𝑘 = 𝑍 𝐸 𝑘 for some 𝐸 𝑘 = Ω(𝑘 3∕4 ).

In contrast, for this choice of 𝑌 𝑘 and any perturbation of the CGB, Proposition 2 implies that lim sup 𝑘→∞ ⌈⌈𝜏 𝑘 -𝜂 𝜏 𝑘 ⌈⌈ ≤ 1∕2. Thus, while many restart perturbations maximally perturb the WSR, no perturbation (restart or otherwise) can maximally perturb the CGB.

We now return to discuss the existing trichotomy results mentioned in the introduction, those from Reference [5][6][7][8]. All of these works consider the directed configuration model (DCM), a means of constructing a graph from a given degree sequence via random edge pairings, and variants thereof. It was recently shown that for random walks on sparse DCMs, and for a wider class of sparse randomly-generated chains, cutoff occurs at Θ(log 𝑘) steps [13,14]. More precisely, [13,14] prove a probabilistic analogue of (6), namely

where 𝑁 (𝑘) ent = Θ(log 𝑘) is defined in terms of the given degrees (see Section 1 of [14] and Equation (1) of [13] for details) and ℙ -→ denotes convergence in probability.

Using these results, Theorem 2 in Reference [5] states that for certain sequences of distributions {𝑥 𝑘 } 𝑘∈ℕ , the distance to stationarity 𝑌 𝑘 ,𝑥 𝑘 (⋅) corresponding to 𝑣 𝑌 𝑘 ,𝑥 𝑘 satisfies the following:

• If 𝑌 𝑘 𝑁 (𝑘) ent → 0, (17) holds with 𝑘 (⋅) replaced by 𝑌 𝑘 ,𝑥 𝑘 (⋅), that is, 𝑌 𝑘 ,𝑥 𝑘 (⋅) is a step function.

• If 𝑌 𝑘 𝑁 (𝑘) ent → (0, ∞), the behavior is intermediate: For 𝑁 < 𝑁 (𝑘) ent , 𝑌 𝑘 ,𝑥 𝑘 (𝑁) decays exponentially, as in the 𝑌 𝑘 𝑁 (𝑘) ent → ∞ case; for 𝑁 > 𝑁 (𝑘) ent ,

𝑌 𝑘 ,𝑥 𝑘 (𝑁) = 0, as in the 𝑌 𝑘 𝑁 (𝑘) ent → 0 case.

In Reference [6], the authors study a dynamic version of the DCM for which an 𝑌 𝑘 fraction of edges are randomly sampled and re-paired at each time step. The main result (Theorem 1.4) says the distance to stationarity of the non-backtracking random walk on this dynamic DCM follows a trichotomy similar to the one from Reference [5]. Similar results were established under weaker assumptions in Reference [7]. Finally, [8], also using ideas from References [13,14], studies the matrix Π 𝑘 with rows {𝜏 𝑌 𝑘 ,𝑍 𝐸 } 𝐸∈ [𝑘] , that is, the 𝐸-th row corresponds to the stationary distribution of the Markov chain obtained by restarting the simple random walk at node 𝐸. The authors study

which can be viewed as a measure of the dimension of Π 𝑘 , and whose form is motivated algorithmically (see Section 2.3 in Reference [8]). When 𝑣 𝑘 describes the random walk on the DCM and 𝑌 𝑘 = 𝑇∕𝑁 (𝑘) ent , the authors show  𝑘 (𝜆) = 𝛾(𝑘 𝜌 (𝑇,𝜆) ), where 𝜌 (𝑇, 𝜆) ∈ (0, 1) also depends on the given degrees (see Theorem 1 in Reference [8]). If instead 𝑌 𝑘 𝑁 (𝑘) ent → 0, the authors show  𝑘 (𝜆) = 𝛾 (1), and if 𝑌 𝑘 𝑁 (𝑘) ent → ∞, they conjecture  𝑘 (𝜆) = Ω(𝑘 ) ∀ ∈ (0, 1), for example,  𝑘 (𝜆) = Θ(𝑘∕ log 𝑘) (see Section 7.4 in Reference [8]).

Ultimately, as discussed in the introduction-Section 1-these results all echo Theorem 1 and hint at a deeper phenomenon. Since [5,6,8] all study Markov chains associated with the DCM, one could assume that properties of the DCM model may be the underlying reason for their results. In contrast, the present paper suggests that some notion of cutoff is the crucial property. Accordingly, it is unsurprising that the trichotomy results in References [5,8] rely on the cutoff results from References [13,14].

Our other result, Theorem 2, relates closely to the aforementioned [4]. Here it is shown that mixing cutoff ( 5) is equivalent to a certain notion of "hitting time cutoff". Namely, Theorem 3 in Reference [4] shows that for sequences of lazy, reversible, and irreducible chains, cutoff ( 5) is equivalent to each of the following:

Here, 𝑁 (𝑘) rel is the inverse spectral gap of 𝑣 𝑘 (see Equation (30) in Section 6.2), and 𝑁 (𝑘) hit ( , 𝜆) is the first time the chain has visited all sets of stationary measure at least with probability at least 1 -𝜆, from any starting state (see Equation (27) in Section 6.2). Hence, (18) and ( 19) roughly say that shortly after "large" sets are reached at all, they are reached with high probability. As discussed in Section 1, Theorem 2 nicely complements this result, since both the cutoff notion and the equivalent notion differ.

More broadly, the cutoff phenomenon has been established for a variety of chains. In addition to the aforementioned [13,14], a non-exhaustive list includes Markovian models of card shuffling [15,16], diffusion models [17,18], random walks on regular graphs [19], walks on Ramanujan graphs [20], non-backtracking walks [21], walks on dynamic graphs [22], walks on graphs with communities [23], walks on Abelian groups [24], and chains with a certain notion of non-negative curvature [11]. We refer readers to these papers and the references therein, along with the classical survey [25] and the textbooks [12,26], for further background on mixing times and the cutoff phenomenon.

Finally, we mention some prior work with less immediate connections to our own. We already discussed the work in References [9,10] which discusses the connection between mixing times and perturbation bounds. In the PageRank literature, another relevant paper is [27], which estimates 𝜏 𝑌 𝑘 ,𝑥 𝑘 as a mixture of 𝑥 𝑘 and the degree distribution; in this sense, the results in Reference [27] are more precise than ours, but they are restricted to a certain class of 𝑣 𝑘 .

Lemma 1.

Let 𝑣 𝑘 ∈  𝑘 and 𝑌 𝑘 ∈ (0, 1). Then for any 𝜂 𝑣 𝑘 ∈ (𝑣 𝑘 , 𝑌 𝑘 ) and any 𝑁 ∈ ℕ,

Proof of Lemma 1. Before proving the lemma, we recall the following standard notions (see Lemma 5 in Appendix A for details). A coupling of , ∈ ( 𝑘-1 is pair of random variables (𝑀, ) with marginal distributions and , ⌈⌈ -⌈⌈ = inf{ℙ(𝑀 ≠ ) ∶ (𝑀, ) is a coupling of ( , )}, and the infimum is attained. We call any such (𝑀, ) attaining the infimum an optimal coupling, and we say a coupling succeeds if 𝑀 = . Hence, an optimal coupling of ( , ) succeeds with probability 1 -⌈⌈ -⌈⌈.

To prove Lemma 1, we first use the triangle inequality, convexity, and the definition of the distance to stationarity function (2) to obtain ⌈⌈𝜏 𝑘 -𝜂 𝜏 𝑘 ⌈⌈ ≤ ⌈⌈𝜏 𝑘 -𝜂 𝜏 𝑘 𝑣 𝑁 𝑘 ⌈⌈ + ⌈⌈ 𝜂 𝜏 𝑘 𝑣 𝑁 𝑘 -𝜂 𝜏 𝑘 ⌈⌈ ≤ 𝑘 (𝑁) + ⌈⌈ 𝜂 𝜏 𝑘 𝑣 𝑁 𝑘 -𝜂 𝜏 𝑘 ⌈⌈ (20) Hence, it suffices to show ⌈⌈ 𝜂 𝜏 𝑘 𝑣 𝑁 𝑘 -𝜂 𝜏 𝑘 ⌈⌈ = ⌈⌈ 𝜂 𝜏 𝑘 𝑣 𝑁 𝑘 -𝜂 𝜏 𝑘 𝜂 𝑣 𝑁 𝑘 ⌈⌈ ≤ 1 -(1 -𝑌 𝑘 ) 𝑁 . To do so, we use a sequence of 𝑁 optimal couplings to construct a (possibly suboptimal) coupling of ( 𝜂 𝜏 𝑘 𝑣 𝑁 𝑘 , 𝜂 𝜏 𝑘 𝜂 𝑣 𝑁 𝑘 ). Our construction ensures that the coupling of ( 𝜂 𝜏 𝑘 𝑣 𝑁 𝑘 , 𝜂 𝜏 𝑘 𝜂 𝑣 𝑁 𝑘 ) succeeds if all 𝑁 optimal couplings succeed, and the definition of (𝑣 𝑘 , 𝑌 𝑘 ) ensures that each optimal coupling succeeds with probability at least 1 -𝑌 𝑘 . Hence, ( 𝜂 𝜏 𝑘 𝑣 𝑁 𝑘 , 𝜂 𝜏 𝑘 𝜂 𝑣 𝑁 𝑘 ) succeeds with probability at least (1 -𝑌 𝑘 ) 𝑁 , which implies the desired bound. This is made precise next. As discussed above, we construct a coupling to show ⌈⌈ 𝜂 𝜏 𝑘 𝑣 𝑁 𝑘 -𝜂 𝜏 𝑘 ⌈⌈ ≤ 1 -(1 -𝑌 𝑘 ) 𝑁 . Namely, we inductively define a sequence of random variables {𝑀 𝑘 ( ), 𝜂 𝑀 𝑘 ( )} 𝑁 =0 as follows: • For = 0, sample 𝑀 𝑘 ( ) from 𝜂 𝜏 𝑘 , and set 𝜂 𝑀 𝑘 ( ) = 𝑀 𝑘 ( ). • For ∈ {1, . . . , 𝑁}, consider two cases: 1. If 𝑀 𝑘 ( -1) ≠ 𝜂 𝑀 𝑘 ( -1), independently sample 𝑀 𝑘 ( ) from 𝑍 𝑀 𝑘 ( -1) 𝑣 𝑘 and 𝜂 𝑀 𝑘 ( ) from 𝑍 𝜂 𝑀 𝑘 ( -1) 𝜂 𝑣 𝑘 , respectively. 2. If 𝑀 𝑘 ( -1) = 𝜂 𝑀 𝑘 ( -1), let (𝑀 𝑘 ( ), 𝜂 𝑀 𝑘 ( )) be any optimal coupling of 𝑍 𝑀 𝑘 ( -1) 𝑣 𝑘 and 𝑍 𝜂 𝑀 𝑘 ( -1) 𝜂 𝑣 𝑘 = 𝑍 𝑀 𝑘 ( -1) 𝜂 𝑣 𝑘 . We claim 𝑀 𝑘 ( ) + 𝜂 𝜏 𝑘 𝑣 𝑘 , 𝜂 𝑀 𝑘 ( ) + 𝜂 𝜏 𝑘 ∀ ∈ {0, . . . , }, where + means the marginal distribution of is . Note that, since 𝜂 𝜏 𝑘 is the stationary distribution of 𝜂 𝑣 𝑘 , this claim is equivalent to 𝑀 𝑘 ( ) + 𝜂 𝜏 𝑘 𝑣 𝑘 , 𝜂 𝑀 𝑘 ( ) + 𝜂 𝜏 𝑘 𝜂 𝑣 𝑘 ∀ . For = 0 and Case 1 of ∈ {1, . . . , 𝑁}, this latter claim clearly holds inductively by the construction above; for Case 2 of ∈ {1, . . . , 𝑁}, it holds inductively and by the coupling definition. Therefore, by definition of optimal coupling, ⌈⌈ 𝜂 𝜏 𝑘 𝑣 𝑁 𝑘 -𝜂 𝜏 𝑘 ⌈⌈ ≤ 1 -ℙ(𝑀 𝑘 (𝑁) = 𝜂 𝑀 𝑘 (𝑁))

We thus seek a lower bound for ℙ(𝑀 𝑘 (𝑁) = 𝜂 𝑀 𝑘 (𝑁)). We first write

where 1(⋅) is the indicator function. Now conditioned on 𝑀 𝑘 (𝑁 -1), 𝜂 𝑀 𝑘 (𝑁 -1), the definition of an optimal coupling guarantees that, whenever 𝑀 𝑘 (𝑁 -1) = 𝜂 𝑀 𝑘 (𝑁 -1),

where the inequality holds pointwise by assumption 𝜂 𝑣 𝑘 ∈ (𝑣 𝑘 , 𝑌 𝑘 ). Using the previous two inequalities, and since 𝑀 𝑘 (0) = 𝜂 𝑀 𝑘 (0) by construction, we then obtain

Combining ( 20), (21), and ( 22) yields the desired inequality.

Using Lemma 1, we can obtain the following asymptotic bounds, which again require no assumptions of laziness, reversibility, or cutoff.

Corollary 1.

Let 𝑣 𝑘 ∈  𝑘 , 𝑌 𝑘 ∈ (0, 1) ∀ 𝑘 ∈ ℕ, and let 𝜆 ∈ (0, 1) be independent of 𝑘. Assume lim 𝑘→∞ 𝑌 𝑘 𝑁 (𝑘) mix (𝜆) = 𝑇 ∈ [0, ∞). Then the following hold:

Proof. To prove (23), we first use Lemma 1 and Bernoulli's inequality to write

Setting 𝑘 = ⌈1∕ ( 𝑌 𝑘 𝑁 (𝑘) mix (𝜆)⌉, choosing 𝑁 = 𝑘 𝑁 (𝑘) mix (𝜆), and using Lemma 6 from Appendix A (an elementary result for mixing times) then gives ⌈⌈𝜏 𝑘 -𝜂 𝜏 𝑘 ⌈⌈ ≤ 𝑘 𝑌 𝑘 𝑁 (𝑘) mix (𝜆) + (2𝜆) 𝑘 --→ 𝑘→∞ 0 where the limit holds since 𝑌 𝑘 𝑁 (𝑘) mix (𝜆) → 0, 𝜆 < 1∕2 by assumption.

To prove (24), we simply choose 𝑁 = 𝑁 (𝑘) mix (𝜆) in Lemma 1 and use (3) to obtain

where the limit holds since 𝑌 𝑘 𝑁 (𝑘) mix (𝜆) → 𝑇 by assumption. (In the case 𝑇 > log(1∕𝜆), the bound ⌈⌈𝜏 𝑘 -𝜂 𝜏 𝑘 ⌈⌈ ≤ 1 in ( 24) is obvious.) ◽ Finally, we prove the upper bounds of Theorem 1, which use the assumptions of laziness and cutoff to strengthen the results of the previous corollary. Roughly speaking, the cutoff assumption means that all mixing times are equivalent, which allows us to discard the 𝜆 < 1∕2 assumption when 𝑇 = 0, and to take 𝜆 arbitrarily small in Equation (24). Furthermore, the laziness assumption allows us to discard the assumption 𝑁 (𝑘) mix (𝜆) → ∞ when 𝑇 ∈ (0, ∞). The proof is fairly straightforward so is deferred to the appendix.

| Lower Bounds

We begin with some definitions. First, denote the hitting time of .

[𝑘] by 𝑘 ( ) = inf{𝑁 ∈ ℤ + ∶ 𝑀 𝑘 (𝑁) ∈ }. Given 1 , 3 ∈ (0, 1), we also define

where ℙ denotes probability conditioned on the chain starting from 𝑀 𝑘 (0) = . Thus, in words, 𝑁 (𝑘) hit (1 -3 , 1 ) is the first time at which the chain has visited all sets of stationary measure at least 1 -3 from any starting state with probability at least 1 -1 .

The first key idea of our lower bounds is that we can use this definition to construct a restart perturbation with a large perturbation error.

To illustrate this, we choose 3 ≈ 0 and 1 ≈ 1 and use the definition of 𝑁 (𝑘) hit to find a state 𝑘 and a set of states 𝑘 such that 𝜏 𝑘 ( 𝑘 ) ≈ 1 and

, we can find 𝑘 and 𝑘 such that ℙ 𝑘 (𝑀 𝑘 (𝑁) ∈ 𝑘 ) ≈ 0 ∀ 𝑁 < 1∕𝑌 𝑘 . Hence, if we perturb the chain by restarting at 𝑘 with probability 𝑌 𝑘 at each step, the perturbed chain will rarely visit 𝑘 (since the number of steps between restarts is 1∕𝑌 𝑘 in expectation). This implies 𝜂 𝜏 𝑘 ( 𝑘 ) ≈ 0, and since 𝜏 𝑘 ( 𝑘 ) ≈ 1 by definition, we obtain ⌈⌈𝜏 𝑘 -𝜂 𝜏 𝑘 ⌈⌈ ≈ 1.

More generally, the following lemma shows that we can find a perturbation such that the product 𝑌 𝑘 𝑁 (𝑘) hit (1 -3 , 1 ) controls the perturbation error ⌈⌈𝜏 𝑘 -𝜂 𝜏 𝑘 ⌈⌈. We note this lower bound does not require laziness, reversibility, or cutoff assumptions.

⌉

Proof. First note 1 -, 1 -2 ∈ (0, 1) by assumption on , so 𝑁 𝑘 ∶= 𝑁 (𝑘) hit (1 -, 1 -2 ) is well-defined. Hence, by definition,

Now set 𝜂 𝑣 𝑘 = 𝑣 𝑌 𝑘 ,𝑍 𝑘 (i.e., restart at 𝑘 with probability 𝑌 𝑘 ). Then by Lemma 7 in Appendix A (a well-known formula for the stationary distribution of a restart perturbation),

We consider the two summands in Equation (29) in turn. For the first summand, we note

where the second inequality holds for 𝑁 < 𝑁 𝑘 , and the third holds by (28). It follows that

For the second summand in Equation (29), we simply upper bound the probabilities by 1 to obtain

Taken together, we have shown 𝜂 𝜏 𝑘 ( 𝑘 ) < 2 + exp(-𝑌 𝑘 𝑁 𝑘 ). Combined with (28), we obtain

which completes the proof. ◽

We have thus identified a restart perturbation for which perturbation error is lower bounded in terms of 𝑌 𝑘 𝑁 (𝑘) hit (1 -3 , 1 ). The second key idea of our lower bounds, taken from the aforementioned [4], is that 𝑁 (𝑘) hit (1 -3 , 1 ) can be lower bounded in terms of 𝑁 (𝑘) mix (𝜆). To formulate this, we first define the relaxation time

where 1 - * 𝑘 is the absolute spectral gap of 𝑣 𝑘 , defined by

(Note 𝑣 𝑘 ∈  𝑘 ⇒ * 𝑘 < 1-see, for example, Lemma 12.1 in Reference [12]-so (30) is well-defined in this case.) We then have the following.

Lemma 3 (Corollary 3.1 in Reference [4]). Let 𝑣 𝑘 ∈  𝑘 and assume 𝑣 𝑘 is lazy and reversible. Then for any 1 , 2 , 3 ∈ (0, 1),

Combining the previous two lemmas, we obtain lower bounds of the form

This is the form we desire, except for the term 𝑁 (𝑘) rel . However, it is known that 𝑁 (𝑘) rel = 𝐶(𝑁 (𝑘) mix (𝜆)) when pre-cutoff holds, so we can obtain nontrivial lower bounds using (pre-)cutoff assumptions. In particular, the next corollary considers the cases when cutoff holds and 𝑌 𝑘 𝑁 (𝑘) mix (𝜆) → (0, ∞), or pre-cutoff holds and 𝑌 𝑘 𝑁 (𝑘) mix (𝜆) → ∞. Hence, a sharper convergence to stationarity requires a smaller perturbation magnitude (i.e., 𝑌 𝑘 𝑁 (𝑘) mix (𝜆) → (0, ∞) instead of 𝑌 𝑘 𝑁 (𝑘) mix (𝜆) → ∞) to obtain a useful lower bound on ⌈⌈𝜏 𝑘 -𝜂 𝜏 𝑘 ⌈⌈.

Corollary 3.

Let 𝑣 𝑘 ∈  𝑘 , 𝑌 𝑘 ∈ (0, 1) ∀ 𝑘 ∈ ℕ, and let ∈ (0, 1∕2) be independent of 𝑘. Assume each 𝑣 𝑘 is lazy and reversible and

Proof. We first prove (32). Note that the assumptions of Lemma 2 are satisfied for each 𝑘 ∈ ℕ, so we can find { 𝜂 𝑣 𝑘 } 𝑘∈ℕ with 𝜂 𝑣 𝑘 ∈ (𝑣 𝑘 , 𝑌 𝑘 ) for each 𝑘, and lim inf

Now when pre-cutoff holds, 𝑁 (𝑘) mix (1 -)∕𝑁 (𝑘) mix ( ) is lower bounded by a positive constant as 𝑘 → ∞ (by definition) and 𝑁 (𝑘) rel = 𝐶(𝑁 (𝑘) mix ( )) (by Lemma 6 in Appendix A). Thus, if 𝑌 𝑘 𝑁 (𝑘) mix ( ) → ∞, we obtain lim 𝑘→∞ 𝑌 𝑘 𝑁 (𝑘) mix ( )

and combining the previous two lines yields (32).

The proof of (33) is nearly identical, except 𝑁 (𝑘) mix (1 -)∕𝑁 (𝑘) mix ( ) → 1 when cutoff holds, so if 𝑌 𝑘 𝑁 (𝑘) mix ( ) → 𝑇 ∈ (0, ∞), the limit in the previous equation equals 𝑇. ◽

The bounds in Corollary 3 match the lower bounds of Theorem 1 except for the 3 terms. However, these are largely "nuisance terms": Roughly speaking, when cutoff holds, all -mixing times are equivalent, so one can apply Corollary 3 with arbitrarily small ensuring these nuisance terms vanish. This is formalized in the following corollary. The proof is delicate but uses elementary tools so is deferred to the appendix.

Lemma 4.

If pre-cutoff holds and {𝑌 𝑘,𝜆 } 𝑘∈ℕ,𝜆∈(0,1∕2) . (0, 1) coincides with the mixing times {𝑁 (𝑘) mix (𝜆)} 𝑘∈ℕ,𝜆∈(0,1) , then ∀ 𝜆 ∈ (0, 1∕2), lim 𝑘→∞ 𝑌 𝑘,𝜆 𝑁 (𝑘) mix (𝜆) = ∞.

Proof. Let 𝜆 ∈ (0, 1∕2); we aim to show 𝑌 𝑘,𝜆 𝑁 (𝑘)

where the first inequality holds by (4) (since 𝜆 < 1∕2), and the second holds by the lower bound of the interval in Equation (36). On the other hand, ∀ ∈ [𝜆, 1∕2),

where the first inequality holds by the upper bound of the interval in Equation (36) and by (4), and the second holds by (4) (since < 1∕2). Now since 𝑘 ∈ ℕ was arbitrary, (38) and (39) imply lim inf

Also, by definition of <𝐸 𝐸𝑘𝜌 and pre-cutoff, ∃ > > 0 independent of 𝑘, such that ∀ ∈ (0, 1∕2), lim inf 𝑘→∞ 𝑌 𝑘, 𝑁 (𝑘) mix ( )

-) 𝑁 (𝑘) mix ( ) lim inf 𝑘→∞ 𝑌 𝑘, 𝑁 (𝑘) mix ( ) ≥ >lim inf 𝑘→∞ 𝑌 𝑘, 𝑁 (𝑘) mix ( ) Combining the previous two bounds, and since these bounds hold ∀ ∈ (0, 1∕2), lim inf 𝑘→∞ 𝑌 𝑘,𝜆 𝑁 (𝑘) mix (𝜆) ≥ > sup ∈(0,1∕2) lim inf 𝑘→∞ 𝑌 𝑘, 𝑁 (𝑘) mix ( ) = ∞ where the equality holds by (36). ◽ We turn to the proof of the theorem. First, we show that pre-cutoff implies Condition 1. For this, let {𝑌 𝑘,𝜆 } 𝑘∈ℕ,𝜆∈(0,1∕2) . (0, 1) coincide with {𝑁 (𝑘) mix (𝜆)} 𝑘∈ℕ,𝜆∈(0,1) , and fix 𝜆 ∈ (0, 1∕2). Lemma 4 ensures 𝑌 𝑘,𝜆 𝑁 (𝑘) mix (𝜆) → ∞; hence, by Corollary 4, ∃ {𝑥 𝑘,𝜆 } 𝑘∈ℕ s.t. 𝑥 𝑘,𝜆 ∈ ( 𝑘-1 ∀ 𝑘 ∈ ℕ, lim 𝑘→∞ ⌈⌈𝜏 𝑘 -𝜏 𝑌 𝑘,𝜆 ,𝑥 𝑘,𝜆 ⌈⌈ = 1 Next, assume (7) holds. Let 𝑌 𝑘,𝜆 = 1∕(2𝑁 (𝑘) mix (1 -𝜆)) ∀ 𝑘 ∈ ℕ, 𝜆 ∈ (0, 1∕2). Then 𝑌 𝑘,𝜆 𝑌 𝑘, = 𝑁 (𝑘) mix (1 -) 𝑁 (𝑘) mix (1 -𝜆) ∀ 𝜆, ∈ (0, 1∕2) Furthermore, since (7) holds by assumption, sup 𝜆∈(0,1∕2) lim inf 𝑘→∞ 𝑌 𝑘,𝜆 𝑁 (𝑘) mix (𝜆) = 1 2 sup 𝜆∈(0,1∕2) lim inf 𝑘→∞ 𝑁 (𝑘) mix (𝜆) 𝑁 (𝑘) mix (1 -𝜆) = ∞ The previous two lines show that {𝑌 𝑘,𝜆 } 𝑘∈ℕ,𝜆∈(0,1∕2) coincides with {𝑁 (𝑘) mix (𝜆)} 𝑘∈ℕ,𝜆∈(0,1) . Fixing 𝜆 ∈ (0, 1∕2) and {𝑥 𝑘,𝜆 } 𝑘∈ℕ s.t. 𝑥 𝑘,𝜆 ∈ ( 𝑘-1 ∀ 𝑘 ∈ ℕ, we will show ⌈⌈𝜏 𝑘 -𝜏 𝑌 𝑘,𝜆 ,𝑥 𝑘,𝜆 ⌈⌈ ≤ 1 -𝜆 2 which will imply that Condition 1 fails. Toward this end, we first use Lemma 7 (a well-known formula for the stationary distribution of a restart perturbation) to write 𝜏 𝑘 -𝜏 𝑌 𝑘,𝜆 ,𝑥 𝑘,𝜆 = 𝑌 𝑘,𝜆 ∞ ∑ 𝑁=0 (1 -𝑌 𝑘,𝜆 ) 𝑁 (𝜏 𝑘 -𝑥 𝑘,𝜆 𝑣 𝑁 𝑘 ) Hence, by convexity and definition of the 𝑁-step distance from stationarity (2), ⌈⌈𝜏 𝑘 -𝜏 𝑌 𝑘,𝜆 ,𝑥 𝑘,𝜆 ⌈⌈ ≤ 𝑌 𝑘,𝜆 ∞ ∑ 𝑁=0 (1 -𝑌 𝑘,𝜆 ) 𝑁 ⌈⌈𝜏 𝑘 -𝑥 𝑘,𝜆 𝑣 𝑁 𝑘 ⌈⌈ ≤ 𝑌 𝑘,𝜆 ∞ ∑ 𝑁=0 (1 -𝑌 𝑘,𝜆 ) 𝑁 𝑘 (𝑁)

We thus obtain

where the final inequality is Bernoulli's.

We note that in (B), we move only one chain to ensure the chains do not switch cliques (meaning, e.g., 𝑀 𝑘 (𝑁) ∈ {1, . . . , 𝑘∕2}, 𝑘 (𝑁) ∈ {1 + 𝑘∕2, . . . , 𝑘} and 𝑀 𝑘 (𝑁 + 1) ∈ {1 + 𝑘∕2, . . . , 𝑘}, 𝑘 (𝑁 + 1) ∈ {1, . . . , 𝑘∕2}), which prolongs the time for the chains to meet. We also note that when the die lands on 2 or 3 in (C), both chains move within the clique; by swapping the chains when the die lands on 2, we can sample uniformly from the clique, excluding the states 𝑀 𝑘 (𝑁), 𝑘 (𝑁), when the die lands on 3.

To analyze this coupling, first suppose 𝑀 𝑘 (0) = 𝐸, 𝑘 (0) = , for 𝐸 ≠ , in the same clique. Then 𝑀 𝑘 (𝑁) ≠ 𝑘 (𝑁) implies that at each ∈ {0, . . . , 𝑁 -1}, one of the following occur:

• The coin in (C) lands on heads, so both chains remain lazy. This occurs with probability 1∕2.

• The coin in (C) lands on tails, and the die in (C) lands on 1 or 2, so that both chains move but to different states. This occurs with probability (1∕2)

By the independence of these coin flips and die rolls, it follows that

Next, suppose 𝑀 𝑘 (0) = 𝐸, 𝑘 (0) = , for 𝐸 ≠ , in different cliques. Fix 𝑁 ∈ ℕ, ∈ {1, . . . , 𝑁}, and let denote the event that 𝑀 𝑘 ( ), 𝑘 ( ) are in the same clique. Then by the Markov property,

For the first summand in Equation ( 43), we can use the time invariance of the Markov chains and the fact that (42) holds for any 𝐸 ≠ , in the same clique to obtain

For the second summand in Equation ( 43), note that implies 𝑀 𝑘 ( ′ ), 𝑘 ( ′ ) are not in the same clique for each ′ ≤ (since once the chains reach the same clique, they remain in the same clique forever). This in turn implies that at each such ′ , the chain that moves in (B) at step ′ moves within its current clique. Such moves occur with probability 1 -2∕𝑘. Thus, by independence,

| The Odd Case

When 𝑘 is odd, we could use a similar approach as used for the case of 𝑘 being even (bring the chains to the same clique, then bring them to the same state), but the auxiliary state 𝑘 complicates this. Hence, we instead leverage this auxiliary state as follows: We wait until both chains leave state 𝑘 (if necessary); we then ensure that the next colorred visit to 𝑘 by each chain occurs simultaneously (after

we conclude (53) is further bounded by 𝜆. We thus obtain for some 𝜆 independent of 𝑘,

Finally, we can combine (46) and ( 54) to obtain for some 𝜆 , 𝜆 independent of 𝑘,

We have completed the proof of 𝑁 (𝑘) mix (𝜆) = 𝛾(𝑘), assuming (51) holds. We now return to prove (51). Assume (for the sake of contradiction) that 𝑀 𝑘 ( * ) = 𝑘, 𝑀 𝑘 ( * + 1) ≠ 𝑘 for some * < . (i.e., the 𝑀 𝑘 -chain was non-lazy at some * < ). Then, by (B), the 𝑘 -chain was lazy at time * , that is, 𝑘 ( * ) = 𝑘 ( * + 1). Now consider two cases: 2. * < -1: By a similar argument, we have 𝑀 𝑘 ( * + 1) ≠ 𝑘, 𝑘 ( * + 1) ≠ 𝑘 and 𝑀 𝑘 ( * + 1) ≠ 𝑘 ( * + 1). This implies 𝑀 𝑘 ( * + 2), 𝑘 ( * + 2) were assigned via (C). In (C), the chains only move to 𝑘 if they move to 𝑘 together, after which point they remain together forever. Thus, neither chain can move to 𝑘 at time * + 2, else 𝑀 𝑘 ( ) ≠ 𝑘 ( ) in Equation (51) is contradicted. Repeating this argument for * + 3, . . . , then contradicts in Equation (51).

Since both cases yield contradictions, (51) is proven.

As a consequence of this inequality, we obtain

For the other statements, see Equation 4.34, Theorem 12.4, and Proposition 18.4 in Reference [12]. ◽ Finally, we have a formula for the stationary distribution of restart perturbations.

Lemma 7. Let 𝑣 𝑘 ∈  𝑘 , 𝑌 𝑘 ∈ (0, 1), 𝑥 𝑘 ∈ ( 𝑘-1 . Then 𝜏 𝑌 𝑘 ,𝑥 𝑘 = 𝑌 𝑘 ∞ ∑ 𝑁=0 (1 -𝑌 𝑘 ) 𝑁 𝑥 𝑘 𝑣 𝑁 𝑘 where (we recall) 𝜏 𝑌 𝑘 ,𝑥 𝑘 is the stationary distribution of 𝑣 𝑌 𝑘 ,𝑥 𝑘 = (1 -𝑌 𝑘 )𝑣 𝑘 + 𝑌 𝑘 1 T 𝑘 𝑥 𝑘 . Proof. Using global balance and the fact that 𝜏 𝑌 𝑘 ,𝑥 𝑘 sums to 1 (i.e., 𝜏 𝑌 𝑘 ,𝑥 𝑘 1 T 𝑘 = 1), 𝜏 𝑌 𝑘 ,𝑥 𝑘 = 𝜏 𝑌 𝑘 ,𝑥 𝑘 𝑣 𝑌 𝑘 ,𝑥 𝑘 = (1 -𝑌 𝑘 )𝜏 𝑌 𝑘 ,𝑥 𝑘 𝑣 𝑘 + 𝑌 𝑘 𝑥 𝑘 ⇒ 𝑌 𝑘 𝑥 𝑘 = 𝜏 𝑌 𝑘 ,𝑥 𝑘 ( 𝑘 -(1 -𝑌 𝑘 )𝑣 𝑘 )

Finally, using the well-known identity ( -

𝑁 for a matrix with spectral radius ( ) < 1, we obtain the desired result. ◽

Proof of Corollary 2

We first assume 𝜆 = 1∕4; we will then extend the proof to the case 𝜆 ≠ 1∕4. In the case 𝜆 = 1∕4 (in fact, any 𝜆 < 1∕2), (25) follows immediately from Corollary 1. To prove (26), assume for the sake of contradiction ∃ { 𝜂 𝑣 𝑘 } 𝑘∈ℕ with 𝜂 𝑣 𝑘 ∈ (𝑣 𝑘 , 𝑌 𝑘 ) ∀ 𝑘 ∈ ℕ and lim sup 𝑘→∞ ⌈⌈𝜏 𝑘 -𝜂 𝜏 𝑘 ⌈⌈ > 1 -𝑍 -𝑇 . Clearly, if this inequality holds, then the interval

is nonempty, so we can choose in this interval. Since < 1∕4 by construction, (4) implies

Hence, using the definition of 𝑇 and the cutoff assumption,

so that lim 𝑘→∞ 𝑌 𝑘 𝑁 (𝑘) mix ( ) = 𝑇. Assuming for the moment that 𝑁 (𝑘) mix ( ) → ∞, we can then use (24) and the choice of to obtain lim sup

which is a contradiction. Now to see why 𝑁 (𝑘) mix ( ) → ∞ holds, first note that ∀ ′ ∈ (0, ),

where the inequality holds by (4). Hence, by cutoff, we obtain ∀ ′ ∈ (0, ),

On the other hand, the previous inequality immediately holds ∀ ′ ∈ [ , 1) by ( 4). Therefore,

where the equality holds by Lemma 6 in Appendix A.

Finally, we extend the upper bounds to 𝜆 ≠ 1∕4, for which it suffices to show lim

so it suffices to show lim 𝑘→∞ 𝑁 (𝑘) mix ( )∕𝑁 (𝑘) mix (𝜆) = 1. This can be proven as follows:

• If 𝜆 ≤ ≤ 1 -𝜆, we have 𝑁 (𝑘) mix (1 -𝜆) ≤ 𝑁 (𝑘) mix ( ) ≤ 𝑁 (𝑘) mix (𝜆) by ( 4), so by cutoff, 4), so by cutoff,

the result holds by reversing the roles of 𝜆 and 1 -𝜆.

• Finally, 𝜆 ≤ 1 -𝜆 ≤ and 1 -𝜆 ≤ 𝜆 ≤ cannot occur since < 1∕2.

We have shown ∈ (0, 1∕2) and lim 𝑘→∞ 𝑌 𝑘 𝑁 (𝑘) mix ( ) = 𝑇 ∀ ∈ ℕ.

Hence, for each , we can use Corollary 3 to find { 𝜂 𝑣 ( ) 𝑘 } 𝑘∈ℕ s.t. 𝜂 𝑣 ( ) 𝑘 ∈ (𝑣 𝑘 , 𝑌 𝑘 ) ∀ 𝑘 ∈ ℕ, and lim inf 𝑘→∞ ⌈⌈𝜏 𝑘 -𝜂 𝜏 ( ) 𝑘 ⌈⌈ ≥ 1 -𝑍 -𝑇 -2 -( +1)

From here, the proof can be completed in a similar manner to the proof of (34), by simply replacing 1 with 1 -𝑍 -𝑇 in the analysis following (B57).

Proof of Proposition 2 Winning Streak Reversal

Let {𝑌 𝑘 } 𝑘∈ℕ , {𝑥 𝑘 } 𝑘∈ℕ , 𝑇 1 , 𝑇 2 , and 𝑇 3 be as in the statement of the proposition. For 𝑘 ∈ ℕ, set 𝑘 = ⌊𝑘 𝑇 1 (1+𝑇 2 )∕2 . Then by 𝑌 𝑘 = Θ(𝑘 -𝑇 1 ), 𝑇 1 > 0, and 𝑇 2 > 1,

Again using 𝑌 𝑘 = Θ(𝑘 -𝑇 1 ), 𝑇 1 > 0, and 𝑇 2 > 1, we also observe

2 )∕2 ⇒ lim 𝑘→∞ ⌊𝑇 3 𝑌 -𝑇 2 𝑘 ⌋ -𝑘 = ∞ Consequently, we can find a sequence of positive integers { ′ 𝑘 } 𝑘∈ℕ such that ⌊𝑇 3 𝑌 -𝑇 2 𝑘 ⌋ -𝑘 + 2 > ′ 𝑘 ∀ 𝑘 ∈ ℕsufficiently large, lim 𝑘→∞ ′ 𝑘 = ∞ (C8) Now letting 𝑍 [ ′ 𝑘 ] = { 𝐸∈[ ′ 𝑘 ] 𝑍 𝐸 = { ′ 𝑘 𝐸=1 𝑍 𝐸 , we can use Lemma 7 to obtain 𝜏 𝑌 𝑘 ,𝑥 𝑘 ([ ′ 𝑘 ]) = 𝑌 𝑘 ∞ { 𝑁=0 (1 -𝑌 𝑘 ) 𝑁 𝑥 𝑘 𝑣 𝑁 𝑘 𝑍 T [ ′ 𝑘 ] = 𝑌 𝑘 ∞ { 𝑁=0 (1 -𝑌 𝑘 ) 𝑁 𝑘 { 𝐸=1 𝑥 𝑘 (𝐸)𝑍 𝐸 𝑣 𝑁 𝑘 𝑍 T [ ′ 𝑘 ] = 𝑌 𝑘 𝑘 -1 { 𝑁=0 (1 -𝑌 𝑘 ) 𝑁 ⌊𝑇 3 𝑌 -𝑇 2 𝑘 ⌋ { 𝐸=1 𝑥 𝑘 (𝐸)𝑍 𝐸 𝑣 𝑁 𝑘 𝑍 T [ ′ 𝑘 ] + 𝑌 𝑘 ∞ { 𝑁= 𝑘 (1 -𝑌 𝑘 ) 𝑁 𝑘 { 𝐸=1 𝑥 𝑘 (𝐸)𝑍 𝐸 𝑣 𝑁 𝑘 𝑍 T [ ′ 𝑘 ] (C9) +𝑌 𝑘 𝑘 -1 { 𝑁=0 (1 -𝑌 𝑘 ) 𝑁 𝑘 { 𝐸=⌊𝑇 3 𝑌 -𝑇 2 𝑘 ⌋+1 𝑥 𝑘 (𝐸)𝑍 𝐸 𝑣 𝑁 𝑘 𝑍 T [ ′ 𝑘 ] (C10) To bound the summands in Equation (C9), we use 𝑍 𝐸 𝑣 𝑁 𝑘 𝑍 T [ ′ 𝑘 ] ≤ 1 ∀ 𝐸, 𝑁 by row stochasticity to obtain 𝑌 𝑘 𝑘 -1 ∑ 𝑁=0 (1 -𝑌 𝑘 ) 𝑁 ⌊𝑇 3 𝑌 -𝑇 2 𝑘 ⌋ ∑ 𝐸=1 𝑥 𝑘 (𝐸)𝑍 𝐸 𝑣 𝑁 𝑘 𝑍 T [ ′ 𝑘 ] ≤ 𝑌 𝑘 𝑘 -1 ∑ 𝑁=0 (1 -𝑌 𝑘 ) 𝑁 ⌊𝑇 3 𝑌 -𝑇 2 𝑘 ⌋ ∑ 𝐸=1 𝑥 𝑘 (𝐸) ≤ ⌊𝑇 3 𝑌 -𝑇 2 𝑘 ⌋ ∑ 𝐸=1 𝑥 𝑘 (𝐸), 𝑌 𝑘 ∞ ∑ 𝑁= 𝑘 (1 -𝑌 𝑘 ) 𝑁 𝑘 ∑ 𝐸=1 𝑥 𝑘 (𝐸)𝑍 𝐸 𝑣 𝑁 𝑘 𝑍 T [ ′ 𝑘 ] ≤ 𝑌 𝑘 ∞ ∑ 𝑁= 𝑘 (1 -𝑌 𝑘 ) 𝑁 = (1 -𝑌 𝑘 ) 𝑘 ≤ 𝑍 -𝑌 𝑘 𝑘 We next consider (C10). First note that, whenever 𝐸 -𝑁 > ′ 𝑘 > 0, we have by (12), 𝑍 𝐸 𝑣 𝑁 𝑘 𝑍 [ ′ 𝑘 ] = 𝑍 𝐸-𝑁 𝑍 [ ′ 𝑘 ] = 0. Also, every 𝐸, 𝑁 pair in the summation in Equation (C10) satisfies, for 𝑘 sufficiently large by (C8), 𝐸 -𝑁 ≥ ⌊𝑇 3 𝑌 -𝑇 2 𝑘 ⌋ + 1 -( 𝑘 -1) = ⌊𝑇 3 𝑌 -𝑇 2 𝑘 ⌋ -𝑘 + 2 > ′ 𝑘 which implies (C10) is zero for all 𝑘 large. We have therefore shown lim sup 𝑘→∞ 𝜏 𝑌 𝑘 ,𝑥 𝑘 ([ ′ 𝑘 ]) ≤ lim sup 𝑘→∞ ⎛ ⎜ ⎜ ⎝ ⌊𝑇 3 𝑌 -𝑇 2 𝑘 ∑ 𝐸=1 𝑥 𝑘 (𝐸) + exp(-𝑌 𝑘 𝑘 ) ⎞ ⎟ ⎟ ⎠ = 0 where the equality holds by assumption and (C7). Since also 𝜏 𝑌 𝑘 ,𝑥 𝑘 ([ ′ 𝑘 ]) ≥ 0 ∀ 𝑘 ∈ ℕ, we conclude lim 𝑘→∞ 𝜏 𝑌 𝑘 ,𝑥 𝑘 ([ ′ 𝑘 ]) = 0. On the other hand, 𝜏 𝑘 ([ ′ 𝑘 ]) = ′ 𝑘 ∑ 𝐸=1 𝜏 𝑘 (𝐸) = ′ 𝑘 ∑ 𝐸=1 2 -𝐸 = 1 -2 -′ 𝑘 --→ 𝑘→∞ 1 where the limit holds since ′ 𝑘 → ∞ by (C8). Combining arguments, we obtain 1 ≥ lim sup 𝑘→∞ ⌈⌈𝜏 𝑘 -𝜏 𝑌 𝑘 ,𝑥 𝑘 ⌈⌈ ≥ lim inf 𝑘→∞ ⌈⌈𝜏 𝑘 -𝜏 𝑌 𝑘 ,𝑥 𝑘 ⌈⌈ ≥ lim inf 𝑘→∞ 𝜏 𝑘 ([ ′ 𝑘 ]) -𝜏 𝑌 𝑘 ,𝑥 𝑘 ([ ′ 𝑘 ]) = 1 Complete Graph Bijection Let {𝑌 𝑘 } 𝑘∈ℕ , { 𝜂 𝑣 𝑘 } 𝑘∈ℕ be given. Then ⌈⌈𝜏 𝑘 -𝜂 𝜏 𝑘 ⌈⌈ ≤ max 𝐸∈[𝑘] ⌈⌈𝜏 𝑘 -𝑍 𝐸 𝑣 𝑘 ⌈⌈ + max 𝐸∈[𝑘] ⌈⌈𝑍 𝐸 𝑣 𝑘 -𝑍 𝐸 𝜂 𝑣 𝑘 ⌈⌈ ≤ 𝑘 (1) + 𝑌 𝑘 ∀ 𝑘 ∈ ℕ where we have used Lemma 5, global balance, and the fact that 𝜂 𝑣 𝑘 ∈ (𝑣 𝑘 , 𝑌 𝑘 ). Thus, using (C2) from Appendix C.0.1 and the assumption lim sup𝑌 𝑘 = 𝑌, we obtain lim sup 𝑘→∞ ⌈⌈𝜏 𝑘 -𝜂 𝜏 𝑘 ⌈⌈ ≤ lim sup 𝑘→∞ 𝑘 (1) + lim sup 𝑘→∞ 𝑌 𝑘 = 1 2 + 𝑌 which completes the proof.