betaFeedback

WorksMathematics

Cutoff on abelian groups

Abstract

We prove the long-predicted equivalence between the cutoff phenomenon and the product condition along any sequence of abelian random walks whose inverse transition probabilities grow at most logarithmically with the size of the group. Our result does not require reversibility, and comes with a sharp quantitative estimate on the mixing window. Moreover, we show that our sparsity restriction is optimal by constructing abelian Cayley graphs which satisfy the product condition but fail to exhibit cutoff, and whose degrees are arbitrarily close to being logarithmic in the volume.

Introduction

Main estimate

Throughout this paper, GG is a finite abelian group equipped with a probability measure μ∈P(G)\mu\in\mathcal{P}(G), and we consider a GG-valued continuous-time Markov chain X=(Xt)t≥0X = (X_t)_{t \ge0} with initial condition X0=0X_0 = 0 and generator L\mathcal{L} acting on L2(G)L^2(G) as follows:

Lf(g):=∑s∈Gμ(s)[f(g+s)−f(g)].(1)\mathcal{L}f(g) := \sum_{s \in G} \mu(s) [f(g+s) - f(g)]. \tag*{(1)}

We call XX an abelian random walk with jump distribution μ\mu. An important special case is that where μ\mu is uniform on a set S⊆GS \subseteq G: the process XX is then exactly a simple random walk on the Cayley graph Γ=Cay⁡(G,S)\Gamma= \operatorname{Cay}(G,S), i.e. the directed graph with vertices and edges

VΓ:=G,andEΓ:={(g,g+s):g∈G, s∈S}.(2)V_\Gamma:= G, \qquad\text{and} \qquad E_\Gamma:= \{(g,g+s): g \in G,\,s \in S\}. \tag*{(2)}

Coming back to the general case, we may, upon restricting the group if needed, assume that GG is generated by the support of μ\mu. This guarantees that the law of XtX_t approaches the uniform law UU on GG as t→∞t \to\infty. A standard way to quantify this convergence is through the total-variation distance to equilibrium, defined at any time t≥0t \ge0 as follows:

d(t):=max⁡A⊆G∣P(Xt∈A)−U(A)∣.(3)d(t) := \max_{A \subseteq G} \left|\mathbb{P}(X_t \in A) - U(A)\right|. \tag*{(3)}

This function decreases continuously from d(0)=1−1/∣G∣d(0) = 1 - 1/|G| to d(∞)=0d(\infty) = 0, and the time at which it reaches a given precision ε∈(0,1)\varepsilon\in(0,1) is known as the mixing time:

tMIX(ε):=inf⁡{t≥0:d(t)≤ε}.(4)\mathrm{t}_{\mathrm{MIX}}(\varepsilon) := \inf\{t \ge0: d(t) \le\varepsilon\}. \tag*{(4)}

The default value for ε\varepsilon is 1/(2e)1/(2e), in which case we simply write tMIX\mathrm{t}_{\mathrm{MIX}}. This quantity describes how long the process needs to be run in order to approach equilibrium. Motivated by the celebrated cutoff phenomenon, we here seek to understand how abrupt the transition from out-of-equilibrium to equilibrium is. This is captured by the difference

wMIX(ε):=tMIX(ε)−tMIX(1−ε),(5)\mathrm{w}_{\mathrm{MIX}}(\varepsilon) := \mathrm{t}_{\mathrm{MIX}}(\varepsilon) - \mathrm{t}_{\mathrm{MIX}}(1-\varepsilon), \tag*{(5)}

known as the width of the mixing window. Our main contribution is a sharp estimate on this subtle quantity, in terms of two basic statistics of the random walk. The first one controls the sparsity of the jump distribution μ\mu, through the smallest non-zero jump rate:

μ⋆:=min⁡{μ(s):s∈supp⁡(μ)}.(6)\mu_\star:= \min\{\mu(s): s \in\operatorname{supp}(\mu)\}. \tag*{(6)}

The second is the spectral gap of L\mathcal{L}, i.e. the difference between its two largest eigenvalues, once projected onto the real axis. Since L\mathcal{L} commutes with its transpose LT\mathcal{L}^{\mathsf{T}}, this is also the spectral gap of the symmetric generator (L+LT)/2(\mathcal{L}+\mathcal{L}^{\mathsf{T}})/2, and we have the variational characterization

gap⁡=inf⁡{⟨f,−Lf⟩:f∈L2(G),⟨f,1⟩=0,⟨f,f⟩=1}.(7)\operatorname{gap}=\inf\{\langle f,-\mathcal{L}f\rangle:f\in L^2(G),\langle f,1\rangle=0,\langle f,f\rangle=1\}. \tag*{(7)}

With this notation at hand, our main result is the following simple estimate on the width of the mixing window, valid for any abelian random walk.

Theorem 1 (Width of the mixing window). For any ε∈(0,1/2)\varepsilon\in(0,1/2), we have

wMIX(ε)≤CεtMIXgap⁡max⁡{1,log⁡(1μ⋆tMIX)}.(8)w_{\mathrm{MIX}}(\varepsilon)\le C_{\varepsilon}\sqrt{\frac{t_{\mathrm{MIX}}}{\operatorname{gap}}\max\left\{1,\log\left(\frac{1}{\mu_{\star}t_{\mathrm{MIX}}}\right)\right\}}. \tag*{(8)}

where Cε<∞C_{\varepsilon}<\infty is a constant that depends only on ε\varepsilon.

This estimate will be shown to be sharp, except for the constant CεC_{\varepsilon} (see Theorem 2 below). It becomes particularly interesting when the size of the group GG gets large, because it implies that certain abelian random walks exhibit a remarkably abrupt transition from out-of-equilibrium to equilibrium known as a cutoff phenomenon.

Implications for cutoff

As is often the case in concrete models, we now assume that the pair (G,μ)(G,\mu) depends on a size parameter n≥1n\ge1, which is kept implicit to lighten notation, and we consider the large-volume limit where n→∞n\to\infty. In this regime, it is sometimes the case that

∀ε∈(0,1/2),tMIX≫wMIX(ε).(9)\forall\varepsilon\in(0,1/2),\qquad t_{\mathrm{MIX}}\gg w_{\mathrm{MIX}}(\varepsilon). \tag*{(9)}

Here and throughout the paper, we use the standard asymptotic notation u≫vu\gg v, u∼vu\sim v, u=Ω(v)u=\Omega(v), u=O(v)u=O(v) and u=Θ(v)u=\Theta(v) to mean, respectively, that the ratio u/vu/v tends to ∞\infty, to 11, remains bounded away from 00, from ∞\infty, and from both as n→∞n\to\infty. In words, (9) means that instead of decaying gradually from 11 to 00 over time, the distance to equilibrium t↦d(t)t\mapsto d(t) approaches a step function as n→∞n\to\infty. Such an abrupt transition from out-of-equilibrium to equilibrium is known as a cutoff. We refer the reader to the seminal works [8, 1, 2, 6] and the recent lecture notes [26] for an introduction to this fascinating phenomenon. Despite the accumulation of several examples, an exact characterization is still missing, even in the simple setting of abelian random walks. As a corollary of Theorem 1, we obtain the following simple sufficient condition for a sequence of abelian random walks to exhibit cutoff.

Corollary 1 (Cutoff). A sequence of abelian random walks exhibits cutoff as soon as

gap⁡ tmix≫max⁡{1,log⁡(1μ⋆tmix)}.(10)\operatorname{gap}\,t_{\mathrm{mix}} \gg\max\left\{1,\log\left(\frac{1}{\mu_{\star}t_{\mathrm{mix}}}\right)\right\}. \tag*{(10)}

To the best of our knowledge, this criterion covers all instances of cutoff on abelian groups in the literature, including those where the jump distribution is random [16, 15]. It also provides new interesting examples, such as the abelian sandpile Markov chain introduced in [18], which has tmix=Θ(nlog⁡n)t_{\mathrm{mix}}=\Theta(n\log n), gap⁡=Θ(1/n)\operatorname{gap}=\Theta(1/n), μ⋆=Θ(1/n)\mu_{\star}=\Theta(1/n), and hence exhibits cutoff. Perhaps more importantly, Corollary 1 has the following conceptual interest. Recall that any sequence of Markov chains exhibiting cutoff must satisfy the celebrated product condition

gap⁡ tmix≫1,(11)\operatorname{gap}\,t_{\mathrm{mix}} \gg1, \tag*{(11)}

but that this is generically not enough; see, e.g., [26 Section 1.5]. For abelian random walks, Corollary 1 shows that this classical necessary condition is actually sufficient, as long as

μ⋆tmix=Ω(1).(12)\mu_{\star}t_{\mathrm{mix}}=\Omega(1). \tag*{(12)}

In words, the condition (12) simply means that each generator s∈supp⁡(μ)s\in\operatorname{supp}(\mu) has a non-vanishing chance of being actually used during mixing. As we will see, this natural requirement holds in particular throughout the logarithmically sparse regime, defined as follows:

1μ⋆=O(log⁡∣G∣).(13)\frac{1}{\mu_{\star}}=O(\log|G|). \tag*{(13)}

This leads to the following result, which partially resolves [12 Conjecture 1] and adds the class of logarithmically sparse abelian random walks to the slowly growing list of Markov processes for which cutoff reduces to the product condition [9, 5, 24, 27, 12].

Corollary 2 (Logarithmic sparsity). The cutoff phenomenon (9) is equivalent to the product condition (11) along any sequence of abelian random walks satisfying (13).

In particular, this completely characterizes cutoff for simple random walk on abelian Cayley graphs whose degrees are at most logarithmic in the volume. Finally, our next result shows that this restriction is optimal, and that our main window estimate is sharp.

Theorem 2 (Sharpness). Let (an)n≥1(a_n)_{n\ge1} be positive numbers satisfying 1≪log⁡an≪log⁡n1\ll\log a_n\ll\log n. Then, there is a sequence of (symmetric) abelian Cayley graphs {Cay⁡(Gn,Sn)}n≥1\{\operatorname{Cay}(G_n,S_n)\}_{n\ge1} such that

∣Sn∣∼anlog⁡∣Gn∣,(14)|S_n|\sim a_n\log|G_n|, \tag*{(14)}

on which simple random walk satisfies the product condition but fails to exhibit cutoff. Moreover, the two sides of the window estimate (8) are of the same order for small enough $\varepsilon>0.

Related work

Random walks on abelian groups have long provided a rich class of models with enough structure and symmetry to serve as an ideal testbed for the exploration of mixing times and the cutoff phenomenon. A pioneering work of Diaconis and Saloff-Coste [7] implies, in particular, that cutoff cannot occur when the number of generators remains bounded, due to the failure of the product condition. On the positive side, cutoff has been established for various families of abelian Cayley graphs with growing degrees, and most notably random instances obtained by choosing the generators uniformly at random. This body of work builds on a fertile research program proposed by Aldous and Diaconis in [2], and on the famous discovery, by Alon and Roichman, that random Cayley graphs exhibit optimal expansion [3]. See, in particular, the inspiring study [16] by Hough on cyclic groups, and the impressive series [14, 15] by Hermon and Olesker-Taylor on general abelian groups. All those instances are covered by our main result.

A complementary line of research consists in seeking systematic criteria for the occurrence of cutoff phenomena, without relying on the detailed, model-specific analysis of mixing times. In particular, the varentropy approach introduced by Salez in [25] and refined by Pedrotti and Salez in [23] shows that cutoff follows from the product-like condition

gap⁡tMIX≫log⁡1μ∗(15)\operatorname{gap} t_{\mathrm{MIX}} \gg\log\frac{1}{\mu_*} \tag*{(15)}

along any sequence of Markov chains with non-negative curvature and symmetric support. (see, e.g., [26, Theorem 5.3]) When specialized to abelian random walks, this requirement is, however, much stronger than the one in our Corollary 1. In particular, it is not even satisfied on the standard hypercube. The present paper can be seen as an optimal refinement of the varentropy approach, when tailored to the special case of abelian random walks.

Finally, the relevance of abelian random walks extends beyond abelian groups themselves. Indeed, the mixing behavior of several non-commutative random walks has been found to be governed by that of their abelianization. Instances of this general dimensional reduction appear notably in the analysis of random walks on upper-triangular matrices by Arias-Castro, Diaconis and Stanley [4], Nestoridi [21], and Nestoridi and Sly [22], as well as in the study of random Cayley graphs by Hermon and Olesker-Taylor [13]. More recently, Huang [17] and Hermon, Huang and Salez [12] showed that a large class of random walks on nilpotent groups exhibit cutoff if and only if their abelianizations do. This clearly motivates a thorough study of cutoff on abelian groups, which is the aim of the present paper.

Proof of the main estimate

Our proof of Theorem 1 relies on the general varentropy approach developed in the series of works [25, 11, 27, 23, 26]. Let us briefly recall it in the present context, where the state space is finite and the stationary distribution uniform.

The varentropy approach

The Shannon entropy of a GG-valued random variable ZZ with law ν\nu is classically defined as

Ent⁡(Z):=∑g∈Gν(g)log⁡1ν(g)=E[log⁡1ν(Z)].(16)\operatorname{Ent}(Z) := \sum_{g \in G} \nu(g) \log\frac{1}{\nu(g)} = \mathbb{E}\left[\log\frac{1}{\nu(Z)}\right]. \tag*{(16)}

To define the varentropy of ZZ, we simply replace the above expectation with a variance:

Varent⁡(Z):=Var⁡[log⁡1ν(Z)].(17)\operatorname{Varent}(Z) := \operatorname{Var}\left[\log\frac{1}{\nu(Z)}\right]. \tag*{(17)}

Following the lecture notes [26], we say that the random walk (Xt)t≥0(X_t)_{t \ge0} satisfies an information-theoretic differential inequality (IDI) with rate Ψ:(0,∞)→(0,∞)\Psi: (0,\infty) \to(0,\infty) if

∀t>0,Varent⁡(Xt)≤Ψ(t)ddtEnt⁡(Xt).(18)\forall t > 0,\qquad\operatorname{Varent}(X_t) \le\Psi(t) \frac{\mathrm{d}}{\mathrm{d}t}\operatorname{Ent}(X_t). \tag*{(18)}

As shown in [26 Lemma 5.4], this inequality systematically implies the window estimate

∀ε∈(0,1/2),ε3wmix⁡(ε)≤1gap⁡+Mεgap⁡,(19)\forall\varepsilon\in(0,1/2),\qquad\varepsilon^3 w_{\operatorname{mix}}(\varepsilon) \le\frac{1}{\operatorname{gap}} + \sqrt{\frac{M_\varepsilon}{\operatorname{gap}}}, \tag*{(19)}

where MεM_\varepsilon denotes the supremum of the rate function Ψ\Psi over the interval [tmix⁡(1−ε),tmix⁡(ε)][t_{\operatorname{mix}}(1-\varepsilon),t_{\operatorname{mix}}(\varepsilon)]. This approach was first implemented in the context of non-negatively curved diffusions [27], which were shown to satisfy the IDI (18) with Ψ(t)=2t\Psi(t)=2t. In view of (19), this implies that their cutoff is characterized by the product condition. The theory was later extended to non-negatively curved Markov chains on finite state spaces [23], including abelian random walks. However, the lack of a chain rule on discrete spaces incurs an extra logarithmic dependency in 1μ⋆\frac{1}{\mu_\star} (see (15) above), and the latter always diverges in the cutoff regime [20]. Using a different approach, we here manage to replace the term 1μ⋆\frac{1}{\mu_\star} with the much smaller (and optimal) quantity 1μ⋆tmix⁡\frac{1}{\mu_\star t_{\operatorname{mix}}}, which crucially remains bounded throughout the regime (13).

Theorem 3 (Universal IDI). Any abelian random walk satisfies the IDI (18) with rate

Ψ(t):=550tmax⁡{1,log⁡1μ⋆t}.(20)\Psi(t) := 550t \max\left\{1,\log\frac{1}{\mu_\star t}\right\}. \tag*{(20)}

Before proving this result, let us quickly explain why it implies our main estimate.

Proof of Theorem 1. The function t↦d(t)t \mapsto\mathrm{d}(t) classically satisfies d(t+s)≤2d(t)d(s)\mathrm{d}(t+s) \le2\mathrm{d}(t)\mathrm{d}(s) for all t,s≥0t,s \ge0, see, e.g., [26 Lemma 1.1]. Recalling that tMIX=tMIX(1/(2e))t_{\mathrm{MIX}}=t_{\mathrm{MIX}}(1/(2e)), this implies

tMIX(ε)≤⌈log⁡1ε⌉tMIX,(21)t_{\mathrm{MIX}}(\varepsilon) \le\left\lceil\log\frac{1}{\varepsilon} \right\rceil t_{\mathrm{MIX}}, \tag*{(21)}

for any ε∈(0,1)\varepsilon\in(0,1). Since the function Ψ\Psi defined at (20) is increasing, we immediately deduce that its supremum over the interval [tMIX(1−ε),tMIX(ε)][t_{\mathrm{MIX}}(1-\varepsilon),t_{\mathrm{MIX}}(\varepsilon)] satisfies

Mε≤550⌈log⁡1ε⌉tMIXmax⁡{1,log⁡1μ⋆tMIX}.M_{\varepsilon} \le550\left\lceil\log\frac{1}{\varepsilon} \right\rceil t_{\mathrm{MIX}} \max\left\{1,\log\frac{1}{\mu_{\star}t_{\mathrm{MIX}}}\right\}.

On the other hand, the classical inequality gap⁡tMIX≥1\operatorname{gap} t_{\mathrm{MIX}} \ge1 (see, e.g., [26 Remark 1.1]) ensures that 1gap⁡≤tMIXgap⁡\frac{1}{\operatorname{gap}} \le\sqrt{\frac{t_{\mathrm{MIX}}}{\operatorname{gap}}}. Thus, (19) yields the desired conclusion, with Cε=1+550⌈log⁡1ε⌉ε3C_{\varepsilon}=\frac{1+\sqrt{550\left\lceil\log\frac{1}{\varepsilon}\right\rceil}}{\varepsilon^3}.

In order to prove Theorem 3, we will exploit the elementary observation that an abelian random walk can be realized as the image, under a suitable projection, of independent Poisson processes (namely, those counting the jumps in each direction s∈supp⁡(μ)s \in\operatorname{supp}(\mu)). As a consequence, varentropy estimates along the random walk can be deduced from appropriate weighted Poincaré inequalities for Poisson distributions.

Poincaré inequality for Poisson distributions

Our starting point is a simple lemma, which appears to be new and of independent interest.

Lemma 1 (Poincaré inequality for attractive birth-death chains). Consider an irreducible birth-death chain on an interval I⊆ZI \subseteq\mathbb{Z} with non-increasing birth rates (q+(x))x∈I(q_{+}(x))_{x\in I}, non-decreasing death rates (q−(x))x∈I(q_{-}(x))_{x\in I} and stationary law π\pi. Then, the Poincaré inequality

∀f∈L2(π),Var⁡π(f)≤C∑x∈Iπ(x)q+(x)[f(x+1)−f(x)]2,(22)\forall f \in L^2(\pi),\quad\operatorname{Var}_{\pi}(f) \le C\sum_{x\in I}\pi(x)q_{+}(x)\left[f(x+1)-f(x)\right]^2, \tag*{(22)}

holds with C=inf⁡o∈I4π2(o)q⋆(o)C=\inf_{o\in I}\frac{4}{\pi^2(o)q_{\star}(o)}, where q⋆(o)q_{\star}(o) denotes the smallest non-zero jump rate to oo.

Proof. A classical use of Hardy inequalities (see [19 Proposition 3]) asserts that for any birth-death chain, the optimal constant CC in the Poincaré inequality (22) satisfies

C≤4inf⁡o∈I{B+(o)∨B−(o)},(23)C \le4\inf_{o\in I}\{B_{+}(o)\vee B_{-}(o)\}, \tag*{(23)}

where we have introduced the quantities

B+(o):=sup⁡x∈(o,∞)∑y=o+1xπ([x,∞))π(y)q−(y)andB−(o):=sup⁡x∈(−∞,o)∑y=xo−1π((−∞,x])π(y)q+(y).B_{+}(o) := \sup_{x\in(o,\infty)} \sum_{y=o+1}^{x} \frac{\pi([x,\infty))}{\pi(y)q_{-}(y)} \quad\text{and}\quad B_{-}(o) := \sup_{x\in(-\infty,o)} \sum_{y=x}^{o-1} \frac{\pi((-\infty,x])}{\pi(y)q_{+}(y)}.

Here, all intervals are implicitly restricted to I\mathbb{I} and the supremum over an empty set is interpreted as zero. Now, for any x∈Ix\in\mathbb{I}, the detailed balance equation gives

π(x+1)π(x)=q+(x)q−(x+1),(24)\frac{\pi(x+1)}{\pi(x)} = \frac{q_{+}(x)}{q_{-}(x+1)}, \tag*{(24)}

and our assumption ensures that the right-hand side is a non-increasing function of xx. Thus, π\pi is a log-concave distribution. In particular, for all o,y,xo,y,x in I\mathbb{I} with o<y≤xo<y\leq x, we have

π(y)≥π(x)π(o)π(o+x−y).(25)\pi(y) \geq\frac{\pi(x)\pi(o)}{\pi(o+x-y)}. \tag*{(25)}

Using this estimate and q−(y)≥q−(o+1)≥q⋆(o)q_{-}(y)\geq q_{-}(o+1)\geq q_{\star}(o) inside the definition of B+(o)B_{+}(o), we obtain

B+(o)≤sup⁡x∈(o,∞){π([o,x))π([x,∞))π(x)π(o)q⋆(o)}≤1π2(o)q⋆(o),B_{+}(o) \leq\sup_{x\in(o,\infty)} \left\{\frac{\pi([o,x))\pi([x,\infty))}{\pi(x)\pi(o)q_{\star}(o)}\right\} \leq\frac{1}{\pi^{2}(o)q_{\star}(o)},

where the second inequality uses the fact that x↦π([x,∞))π(x)x\mapsto\frac{\pi([x,\infty))}{\pi(x)} is non-increasing, by log-concavity of π\pi. By symmetry, the same bound applies to B−(o)B_{-}(o), and the proof is complete. □

As is clear from its proof, the above lemma is inherently restricted to situations where π\pi is log-concave. Fortunately for us, this is the case of Poisson distributions. There are of course many natural choices of monotone birth-death rates that are reversible with respect to a Poisson distribution, and each leads to a different weighted Poincaré inequality. The particular weight appearing in the next proposition will turn out to be the right one for establishing our target IDI in the next section. Let ϕ:(0,∞)→(0,∞)\phi:(0,\infty)\to(0,\infty) be defined by

ϕ(u):=u−1−log⁡ulog⁡2u,(26)\phi(u) := \frac{u-1-\log u}{\log^{2}u}, \tag*{(26)}

with the right-hand side being interpreted as 1/21/2 when u=1u=1. This function is easily checked to be continuous, increasing and concave. For u,v>0u,v>0, we then introduce the shorthand

w(u,v):=uϕ(vu).(27)w(u,v) := u\phi\left(\frac{v}{u}\right). \tag*{(27)}

Proposition 1 (Weighted Poincaré inequality for the Poisson distribution). Let π\pi be the Poisson distribution with mean t∈(0,∞)t \in(0,\infty). Then, for any f∈L2(π)f \in L^2(\pi), we have

Var⁡π(f)≤ψ(t)∑x=0∞w(π(x),π(x+1))[f(x+1)−f(x)]2(28)\operatorname{Var}_{\pi}(f) \le\psi(t)\sum_{x=0}^{\infty} w\bigl(\pi(x),\pi(x+1)\bigr)\bigl[f(x+1)-f(x)\bigr]^2 \tag*{(28)}

where ψ(t):=550tmax⁡{1,log⁡1t}\psi(t):=550t\max\left\{1,\log\frac{1}{t}\right\}.

Proof. Consider the birth-death chain with stationary law π\pi defined as follows: for each x∈Z+x \in\mathbb{Z}_+, the jump rates from xx to x+1x+1 and from x+1x+1 to xx are respectively given by

q+(x):=w(π(x),π(x+1))π(x)=ϕ(tx+1),(29)q_+(x):=\frac{w\bigl(\pi(x),\pi(x+1)\bigr)}{\pi(x)}=\phi\left(\frac{t}{x+1}\right), \tag*{(29)}
q−(x+1):=w(π(x),π(x+1))π(x+1)=x+1tϕ(tx+1).(30)q_-(x+1):=\frac{w\bigl(\pi(x),\pi(x+1)\bigr)}{\pi(x+1)}=\frac{x+1}{t}\phi\left(\frac{t}{x+1}\right). \tag*{(30)}

The fact that ϕ\phi is increasing readily implies that x↦q+(x)x\mapsto q_+(x) is decreasing. On the other hand, the fact that ϕ\phi is concave with ϕ(0+)=0\phi(0+)=0 ensures that u↦ϕ(u)/uu\mapsto\phi(u)/u is decreasing, so that x↦q−(x)x\mapsto q_-(x) is increasing. Thus, Lemma 1 applies, and it only remains to show that

inf⁡x∈Z+{4π2(x)q⋆(x)}≤550tmax⁡{1,log⁡1t}.(31)\inf_{x\in\mathbb{Z}_+}\left\{\frac{4}{\pi^2(x)q_\star(x)}\right\}\le550t\max\left\{1,\log\frac{1}{t}\right\}. \tag*{(31)}

To do so, we choose x=⌊t⌋x=\lfloor t\rfloor in the above infimum. For t≥1t\ge1,

q⋆(⌊t⌋)=min⁡{ϕ(t⌊t⌋),⌊t⌋+1tϕ(t⌊t⌋+1)}≥ϕ(1)=12,(32)q_\star(\lfloor t\rfloor)=\min\left\{\phi\left(\frac{t}{\lfloor t\rfloor}\right),\frac{\lfloor t\rfloor+1}{t}\phi\left(\frac{t}{\lfloor t\rfloor+1}\right)\right\}\ge\phi(1)=\frac{1}{2}, \tag*{(32)}
π(⌊t⌋)=e−tt⌊t⌋⌊t⌋!≥13et,(33)\pi(\lfloor t\rfloor)=\frac{e^{-t}t^{\lfloor t\rfloor}}{\lfloor t\rfloor!}\ge\frac{1}{3e\sqrt{t}}, \tag*{(33)}

thanks to the classical estimate n!≤3n(ne)nn!\le3\sqrt{n}\left(\frac{n}{e}\right)^n for n≥1n\ge1. On the other hand, for t<1t<1,

π2(0)q⋆(0)=ϕ(t)te2t≥13te2log⁡1t.(34)\pi^2(0)q_\star(0)=\frac{\phi(t)}{te^{2t}}\ge\frac{1}{3te^2\log\frac{1}{t}}. \tag*{(34)}

Together, those two estimates guarantee that (31) holds, since 72e2≈53272e^2\approx532.

By tensorization, the above proposition admits the following multi-dimensional extension.

Proposition 2 (Tensorized version). Let π=π1⊗⋯⊗πd∈P(Z+d)\pi=\pi_1\otimes\cdots\otimes\pi_d\in\mathcal{P}(\mathbb{Z}_+^d) be the tensor product of d≥1d\ge1 Poisson laws with respective means t1,…,td∈(0,∞)t_1,\ldots,t_d\in(0,\infty). Then, for any f∈L2(π)f\in L^2(\pi),

Var⁡π(f)≤∑i=1dψ(ti)∑x∈Z+dw(π(x),π(x+ei))[f(x+ei)−f(x)]2(35)\operatorname{Var}_{\pi}(f)\le\sum_{i=1}^{d}\psi(t_i)\sum_{x\in\mathbb{Z}_+^d}w\bigl(\pi(x),\pi(x+e_i)\bigr)\bigl[f(x+e_i)-f(x)\bigr]^2 \tag*{(35)}

where (e1,…,en)(e_1,\ldots,e_n) denotes the canonical basis of Zd\mathbb{Z}^d and ψ\psi the function in Proposition 1.

Proof. Fix i∈{1,…,d}i \in\{1,\ldots,d\}. Proposition 1 allows us to estimate the variance of ff when viewed as a function of the ii-th coordinate only, the values of the remaining coordinates being fixed. Specifically, for every (x1,…,xi−1,xi+1,…,xd)∈Z+d−1(x_1,\ldots,x_{i-1},x_{i+1},\ldots,x_d) \in\mathbb{Z}_+^{d-1}, we have

Var⁡πi[f(x1,…,xi−1,⋅,xi+1,…,xd)]≤ψ(ti)∑xi=0∞w(πi(xi),πi(xi+1))[f(x+ei)−f(x)]2=ψ(ti)∑xi=0∞πi(xi)ϕ(π(x+ei)π(x))[f(x+ei)−f(x)]2,\begin{aligned} \operatorname{Var}_{\pi_i}\left[f(x_1,\ldots,x_{i-1},\cdot,x_{i+1},\ldots,x_d)\right] &\le\psi(t_i)\sum_{x_i=0}^{\infty}w\left(\pi_i(x_i),\pi_i(x_i+1)\right)\left[f(x+e_i)-f(x)\right]^2 \\ &= \psi(t_i)\sum_{x_i=0}^{\infty}\pi_i(x_i)\phi\left(\frac{\pi(x+e_i)}{\pi(x)}\right)\left[f(x+e_i)-f(x)\right]^2, \end{aligned}

where we have used the shorthand x=(x1,…,xd)x=(x_1,\ldots,x_d) on the right-hand side. Multiplying by π1(x1)⋯πi−1(xi−1)πi+1(xi+1)⋯πd(xd)\pi_1(x_1)\cdots\pi_{i-1}(x_{i-1})\pi_{i+1}(x_{i+1})\cdots\pi_d(x_d) and summing over x1,…,xi−1,xi+1,…,xdx_1,\ldots,x_{i-1},x_{i+1},\ldots,x_d yields

Var⁡π,i(f)≤ψ(ti)∑x∈Z+dπ(x)ϕ(π(x+ei)π(x))[f(x+ei)−f(x)]2,\operatorname{Var}_{\pi,i}(f)\le\psi(t_i)\sum_{x\in\mathbb{Z}_+^d}\pi(x)\phi\left(\frac{\pi(x+e_i)}{\pi(x)}\right)\left[f(x+e_i)-f(x)\right]^2,

where Var⁡π,i(f)\operatorname{Var}_{\pi,i}(f) denotes the expected conditional variance of ff given all coordinates except the ii-th one. At this point, the desired conclusion readily follows from the fact that

Var⁡π(f)≤∑i=1dVar⁡π,i(f),\operatorname{Var}_{\pi}(f)\le\sum_{i=1}^{d}\operatorname{Var}_{\pi,i}(f),

which is the well-known tensorization property of the variance [10].

Projection onto abelian groups

As announced long ago, we can finally project our Poincaré inequality for Poisson distributions onto the abelian group GG, in order to obtain a local Poincaré inequality for the random walk X=(Xt)t≥0X=(X_t)_{t\ge0} with jump distribution μ\mu. The fact that our weight has the form w(u,v)=uϕ(vu)w(u,v)=u\phi\left(\frac{v}{u}\right), with ϕ\phi increasing and concave turns out to play a crucial role here.

Proposition 3 (Projected version). Fix t>0t>0 and set μt:=law⁡(Xt)\mu_t:=\operatorname{law}(X_t). Then,

Var⁡μt(f)≤Ψ(t)∑g,s∈Gμ(s)w(μt(g),μt(g+s))[f(g+s)−f(g)]2,(36)\operatorname{Var}_{\mu_t}(f)\le\Psi(t)\sum_{g,s\in G}\mu(s)w\left(\mu_t(g),\mu_t(g+s)\right)\left[f(g+s)-f(g)\right]^2, \tag*{(36)}

for every function f:G→Rf:G\to\mathbb{R}, where Ψ\Psi is as in Theorem 3.

Proof. Write supp⁡(μ)={s1,…,sd}\operatorname{supp}(\mu)=\{s_1,\ldots,s_d\} with d=∣supp⁡(μ)∣d=\lvert\operatorname{supp}(\mu)\rvert, and let π∈P(Z+d)\pi\in\mathcal{P}(\mathbb{Z}_+^d) be the tensor product of dd Poisson laws with respective means t1,…,tdt_1,\ldots,t_d, where ti:=tμ(si)t_i:=t\mu(s_i). By construction, μt\mu_t is then the image of π\pi under the map ρ:Z+d→G\rho:\mathbb{Z}_+^d\to G defined by

ρ(v):=v1s1+⋯+vdsd.(37)\rho(v):=v_1s_1+\cdots+v_ds_d. \tag*{(37)}

Thus, for any f∈RGf \in\mathbb{R}^{G}, we have Var⁡μt(f)=Var⁡π(f∘ρ)\operatorname{Var}_{\mu_t}(f)=\operatorname{Var}_{\pi}(f\circ\rho) and Proposition 2 gives

Var⁡μt(f)≤∑i=1dψ(ti)∑x∈Z+dw(π(x),π(x+ei))[(f∘ρ)(x+ei)−(f∘ρ)(x)]2=∑i=1dψ(ti)∑g∈G∑x∈ρ−1(g)w(π(x),π(x+ei))[f(g+si)−f(g)]2≤∑i=1dψ(ti)∑g∈Gw(∑x∈ρ−1(g)π(x),∑x∈ρ−1(g)π(x+ei))[f(g+si)−f(g)]2,\begin{aligned} \operatorname{Var}_{\mu_t}(f) &\le\sum_{i=1}^{d}\psi(t_i)\sum_{x\in\mathbb{Z}_{+}^{d}}w\bigl(\pi(x),\pi(x+e_i)\bigr)\bigl[(f\circ\rho)(x+e_i)-(f\circ\rho)(x)\bigr]^2\\ &=\sum_{i=1}^{d}\psi(t_i)\sum_{g\in G}\sum_{x\in\rho^{-1}(g)}w\bigl(\pi(x),\pi(x+e_i)\bigr)\bigl[f(g+s_i)-f(g)\bigr]^2\\ &\le\sum_{i=1}^{d}\psi(t_i)\sum_{g\in G}w\left(\sum_{x\in\rho^{-1}(g)}\pi(x),\sum_{x\in\rho^{-1}(g)}\pi(x+e_i)\right)\bigl[f(g+s_i)-f(g)\bigr]^2, \end{aligned}

where we have crucially used the super-additivity property

∑i∈Iw(ui,vi)=∑i∈Iuiϕ(viui)≤∑i∈Iuiϕ(∑i∈Ivi∑i∈Iui)=w(∑i∈Iui,∑i∈Ivi),(38)\sum_{i\in I}w(u_i,v_i)=\sum_{i\in I}u_i\phi\left(\frac{v_i}{u_i}\right)\le\sum_{i\in I}u_i\phi\left(\frac{\sum_{i\in I}v_i}{\sum_{i\in I}u_i}\right)=w\left(\sum_{i\in I}u_i,\sum_{i\in I}v_i\right), \tag*{(38)}

which holds for any countable collection (ui,vi)i∈I(u_i,v_i)_{i\in I} of positive numbers, by concavity of ϕ\phi.

Finally, since μt\mu_t is the image of π\pi under ρ\rho, we have for all g∈Gg\in G,

∑x∈ρ−1(g)π(x)=μt(g)and∑x∈ρ−1(g)π(x+ei)≤μt(g+si).(39)\sum_{x\in\rho^{-1}(g)}\pi(x)=\mu_t(g)\quad\text{and}\quad\sum_{x\in\rho^{-1}(g)}\pi(x+e_i)\le\mu_t(g+s_i). \tag*{(39)}

Since w(⋅,⋅)w(\cdot,\cdot) is non-decreasing in its second argument, this implies

w(∑x∈ρ−1(g)π(x),∑x∈ρ−1(g)π(x+ei))≤w(μt(g),μt(g+si)).(40)w\left(\sum_{x\in\rho^{-1}(g)}\pi(x),\sum_{x\in\rho^{-1}(g)}\pi(x+e_i)\right)\le w\bigl(\mu_t(g),\mu_t(g+s_i)\bigr). \tag*{(40)}

Inserting this into the previous computation concludes the proof, since ψ(ti)≤Ψ(t)μ(si)\psi(t_i)\le\Psi(t)\mu(s_i). □

We are now in a position to establish the universal IDI promised in Theorem 3.

Proof of Theorem 3. Fix t>0t>0 and set μt:=law⁡(Xt)\mu_t:=\operatorname{law}(X_t). Applying Proposition 3 to the function f:g↦log⁡μt(g)f:g\mapsto\log\mu_t(g), and using the particular expression of ww, we obtain

Var⁡ent(Xt)≤Ψ(t)∑s∈Gμ(s)∑g∈Gw(μt(g),μt(g+s))[log⁡μt(g+s)μt(g)]2=Ψ(t)∑s∈Gμ(s)∑g∈G[μt(g+s)−μt(g)−μt(g)log⁡μt(g+s)μt(g)]=Ψ(t)ddtEnt⁡(Xt),\begin{aligned} \operatorname{Var}_{\mathrm{ent}}(X_t) &\le\Psi(t)\sum_{s\in G}\mu(s)\sum_{g\in G}w\bigl(\mu_t(g),\mu_t(g+s)\bigr)\left[\log\frac{\mu_t(g+s)}{\mu_t(g)}\right]^2\\ &=\Psi(t)\sum_{s\in G}\mu(s)\sum_{g\in G}\left[\mu_t(g+s)-\mu_t(g)-\mu_t(g)\log\frac{\mu_t(g+s)}{\mu_t(g)}\right]\\ &=\Psi(t)\frac{\mathrm{d}}{\mathrm{d}t}\operatorname{Ent}(X_t), \end{aligned}

where the last line classically follows from the Fokker–Planck equation ddtμt=L†μt\frac{\mathrm{d}}{\mathrm{d}t}\mu_t=\mathcal{L}^{\dagger}\mu_t. □

We have already explained how this leads to our main estimate (Theorem 1), and the latter readily implies our general sufficient criterion for cutoff (Corollary 1). Finally, the fact that the latter reduces to the product condition in the logarithmically sparse regime (Corollary 2) is a direct consequence of the observation that

∣supp⁡(μ)∣≤1μ⋆,(41)|\operatorname{supp}(\mu)| \le\frac{1}{\mu_{\star}}, \tag*{(41)}

together with the following simple estimate on the mixing time of abelian random walks.

Lemma 2 (Slow mixing for sparse abelian random walks). For every a>0a>0, there is a constant η=η(a)>0\eta=\eta(a)>0, independent of the pair (G,μ)(G,\mu), such that

∣supp⁡(μ)∣≤alog⁡∣G∣⟹tmix≥ηlog⁡∣G∣.(42)|\operatorname{supp}(\mu)| \le a\log|G| \quad\Longrightarrow\quad t_{\mathrm{mix}} \ge\eta\log|G|. \tag*{(42)}

Proof. We can assume that ∣G∣≥2|G|\ge2, otherwise the claim is trivial. Write supp⁡(μ)={s1,…,sd}\operatorname{supp}(\mu)=\{s_1,\ldots,s_d\} with d=∣supp⁡(μ)∣d=|\operatorname{supp}(\mu)|, and fix t≥0t\ge0. By Markov’s inequality, there is a chance at least 3/43/4 that no more than r=⌊4t⌋r=\lfloor4t\rfloor jumps are made during the time interval [0,t][0,t]. Moreover, on that event, the random variable XtX_t is confined to the set

A:={x1s1+⋯+xdsd:(x1,…,xd)∈Z+d, x1+⋯+xd≤r}.(43)A:=\left\{x_1s_1+\cdots+x_ds_d:(x_1,\ldots,x_d)\in\mathbb{Z}_+^d,\ x_1+\cdots+x_d\le r\right\}. \tag*{(43)}

This combinatorial description implies that

∣A∣≤(r+dr)≤eh(r,d),whereh(r,d):=r+rlog⁡(1+dr).(44)|A|\le\binom{r+d}{r}\le e^{h(r,d)},\qquad\text{where}\qquad h(r,d):=r+r\log\left(1+\frac{d}{r}\right). \tag*{(44)}

Note that the function h:(0,∞)2→(0,∞)h:(0,\infty)^2\to(0,\infty) thus defined is increasing. In particular, if

d≤alog⁡∣G∣,andt≤ηlog⁡∣G∣(45)d\le a\log|G|,\qquad\text{and}\qquad t\le\eta\log|G| \tag*{(45)}

for some a,η∈(0,∞)a,\eta\in(0,\infty), then recalling that r=⌊4t⌋r=\lfloor4t\rfloor, we deduce that

∣A∣≤eh(4ηlog⁡∣G∣,alog⁡∣G∣)=∣G∣h(4η,a).(46)|A|\le e^{h(4\eta\log|G|,a\log|G|)}=|G|^{h(4\eta,a)}. \tag*{(46)}

Putting things together, we conclude that

d(t)≥P(Xt∈A)−U(A)≥34−(1∣G∣)1−h(4η,a).(47)d(t)\ge\mathbb{P}(X_t\in A)-\mathcal{U}(A)\ge\frac{3}{4}-\left(\frac{1}{|G|}\right)^{1-h(4\eta,a)}. \tag*{(47)}

Finally, note that once a>0a>0 is fixed, the exponent 1−h(4η,a)1-h(4\eta,a) can be made arbitrarily close to 11 by choosing η\eta small enough. In particular, it can be chosen so that the right-hand side of (47) is larger than 1/(2e)1/(2e), independently of the pair (G,μ)(G,\mu). ∎

Proof of sharpness

Our proof of Theorem 2 builds upon the classical observation that rank-one perturbations can destroy cutoff while preserving the product condition. More precisely, consider a finite group GG, a jump distribution μ∈P(G)\mu\in\mathcal{P}(G) and a number θ∈(0,1)\theta\in(0,1), all depending on an implicit parameter n≥1n \ge1 in such a way that the random walk with jump distribution μ\mu satisfies gap tmix≫1t_{\mathrm{mix}} \gg1 and θtmix=Θ(1)\theta t_{\mathrm{mix}} = \Theta(1). Then the random walk with jump distribution

ν:=(1−θ)μ+θU(48)\nu:= (1-\theta)\mu+\theta U \tag*{(48)}

still satisfies the product condition, but fails to exhibit cutoff (see, e.g., [26 Section 1.5]). Unfortunately, such examples are not reasonable, in the sense that the jump distribution (48) has full support. To obtain sparser examples, a natural idea is to replace the uniform law by a sparse approximation of it, i.e. a measure σ∈P(G)\sigma\in\mathcal{P}(G) whose support is much smaller, but which still mixes extremely fast. Here, in addition, we would like the resulting measure

ν:=(1−θ)μ+θσ(49)\nu:= (1-\theta)\mu+\theta\sigma \tag*{(49)}

to be uniform on its support. This forces μ\mu and σ\sigma to be uniform on disjoint sets, with sizes proportional to 1−θ1-\theta and θ\theta respectively. Recalling that our initial jump distribution μ\mu should satisfy the product condition and have mixing time of order 1/θ1/\theta, we obtain a rather constrained set of specifications. The latter turns out to be feasible, as we will see. To keep our analysis as simple as possible, we implement this strategy on cyclic groups.

Fourier analysis on cyclic groups

The Fourier transform of a probability measure μ\mu on the cyclic group G=ZnG=\mathbb{Z}_n is given by

μ^(z):=∑y∈Gμ(y)exp⁡(2iπzyn),(50)\widehat{\mu}(z) := \sum_{y\in G}\mu(y)\exp\left(\frac{2i\pi zy}{n}\right), \tag*{(50)}

for z∈Gz \in G. We define the spectral radius ϱ=ϱ(μ)\varrho=\varrho(\mu) as the [0,1]-valued number

ϱ:=max⁡z∈G∖{0}∣μ^(z)∣.(51)\varrho:= \max_{z\in G\setminus\{0\}}\lvert\widehat{\mu}(z)\rvert. \tag*{(51)}

This parameter controls the mixing properties of the random walk, as summarized next.

Lemma 3 (Spectral bounds). The random walk with jump distribution μ\mu satisfies

gap⁡≥1−ϱandd(t)≤nϱr+1+∑k=0rpt(k),(52)\operatorname{gap} \ge1-\varrho\quad\text{and}\quad d(t) \le\sqrt{n}\varrho^{r+1}+\sum_{k=0}^{r}p_t(k), \tag*{(52)}

for all t≥0t\ge0 and all r∈Z+r\in\mathbb{Z}_+, where pt∈P(Z+)p_t\in\mathcal{P}(\mathbb{Z}_+) denotes the Poisson law with mean tt.

Proof. The transition matrix T(x,y):=μ(y−x)T(x,y):=\mu(y-x) describing the effect of a jump according to μ\mu can readily be diagonalized in the standard Fourier basis of L2(G)L^2(G), and its eigenvalues are exactly the complex numbers μ^(z)\widehat{\mu}(z), z∈Gz\in G. Since the generator (1) is L=T−Id⁡\mathcal{L}=T-\operatorname{Id}, the first claim follows. Moreover, the Cauchy-Schwarz inequality yields

2dTV(μ,U)=∑x∈G∣μ(x)−1n∣(53)2d_{\mathrm{TV}}(\mu,\mathcal{U})=\sum_{x\in G}\left|\mu(x)-\frac{1}{n}\right| \tag*{(53)}
≤n∑x∈G∣μ(x)−1n∣2(54)\le\sqrt{n\sum_{x\in G}\left|\mu(x)-\frac{1}{n}\right|^2} \tag*{(54)}
=∑z∈G∖{0}∣μ^(z)∣2(55)=\sqrt{\sum_{z\in G\setminus\{0\}}|\widehat{\mu}(z)|^2} \tag*{(55)}
≤nϱ,(56)\le\sqrt{n}\varrho, \tag*{(56)}

where the third line is Parseval’s identity. Replacing μ\mu with its kk-fold convolution μ⋆k\mu^{\star k} and using the convolution-product property μ1⋆μ2^=μ^1μ^2\widehat{\mu_1\star\mu_2}=\widehat{\mu}_1\widehat{\mu}_2 of the Fourier transform, we obtain

dTV(μ⋆k,U)≤nϱk,(57)d_{\mathrm{TV}}(\mu^{\star k},\mathcal{U})\le\sqrt{n}\varrho^k, \tag*{(57)}

for each k∈Z+k\in\mathbb{Z}_+. Finally, note that by definition, our random walk X=(Xt)t≥0X=(X_t)_{t\ge0} satisfies

law⁡(Xt)=∑k=0∞pt(k)μ⋆k.(58)\operatorname{law}(X_t)=\sum_{k=0}^{\infty}p_t(k)\mu^{\star k}. \tag*{(58)}

Since the total-variation distance is convex, we conclude that

d(t)≤∑k=0∞pt(k)dTV(μ⋆k,U)(59)d(t)\le\sum_{k=0}^{\infty}p_t(k)d_{\mathrm{TV}}(\mu^{\star k},\mathcal{U}) \tag*{(59)}
≤nϱr+1+∑k=0rpt(k),(60)\le\sqrt{n}\varrho^{r+1}+\sum_{k=0}^{r}p_t(k), \tag*{(60)}

for any t≥0t\ge0 and any r∈Z+r\in\mathbb{Z}_+, as desired. ▫

Lemma 4. (Random measures mix quickly.) Consider the (symmetric) random measure

μ:=1d∑k=1dδYk+δ−Yk2,(61)\mu:= \frac{1}{d}\sum_{k=1}^{d}\frac{\delta_{Y_k}+\delta_{-Y_k}}{2}, \tag*{(61)}

where d≥1d \ge1 is an integer and Y1,…,YdY_1,\ldots,Y_d are independent and uniform on G=ZnG=\mathbb{Z}_n. Then,

P(ρ(μ)≥2log⁡nd)≤1n.(62)\mathbb{P}\left(\rho(\mu)\ge2\sqrt{\frac{\log n}{d}}\right)\le\frac{1}{n}. \tag*{(62)}

Proof. Fix z∈G∖{0}z\in G\setminus\{0\}. When applied to the random measure (61), the formula (50) gives

μ^(z)=1d∑k=1dcos⁡(2πzYkn).(63)\widehat{\mu}(z)=\frac{1}{d}\sum_{k=1}^{d}\cos\left(\frac{2\pi zY_k}{n}\right). \tag*{(63)}

This is the empirical mean of dd independent, centered, [−1,1][-1,1]-valued variables, so

P(∣μ^(z)∣≥a)≤2e−da22,(64)\mathbb{P}\left(\left|\widehat{\mu}(z)\right|\ge a\right)\le2e^{-\frac{da^2}{2}}, \tag*{(64)}

for any a≥0a\ge0, by Hoeffding’s inequality. Choosing a=2(log⁡n)/da=2\sqrt{(\log n)/d} sets the right-hand side to 2/n22/n^2. Since μ^(−z)=μ^(z)\widehat{\mu}(-z)=\widehat{\mu}(z), taking a union bound over half of the z∈G∖{0}z\in G\setminus\{0\} suffices.

Achieving polynomial degrees

The above lemmas already allow us to prove the following dense version of Theorem 2.

Proposition 4. (Polynomially sparse examples.) Fix α∈(0,1/2)\alpha\in(0,1/2). Then, for each n≥1n\ge1, there is a symmetric set Sn⊆ZnS_n\subseteq\mathbb{Z}_n such that simple random walk on Cay⁡(Zn,Sn)\operatorname{Cay}(\mathbb{Z}_n,S_n) satisfies

  • (i) ∣Sn∣∼nα(i)\ |S_n|\sim n^\alpha;

  • (ii) gap⁡=Ω(1)(ii)\ \operatorname{gap}=\Omega(1);

  • (iii) tmix=Θ(log⁡n)(iii)\ t_{\mathrm{mix}}=\Theta(\log n);

  • (iv) lim sup⁡n→∞d(ulog⁡n)<1(iv)\ \limsup_{n\to\infty}\mathrm{d}(u\log n)<1 for every u>0u>0.

In particular, the product condition is satisfied but there is no cutoff.

:::`

Proof. We omit the index nn to lighten notation. Set d:=⌊10log⁡n⌋d := \lfloor10\log n\rfloor and m:=⌊nα/(40log⁡n)⌋m := \lfloor n^{\alpha}/(40\log n)\rfloor. Let Y1,…,Yd,Z1,…,ZmY_1,\ldots,Y_d,Z_1,\ldots,Z_m be independent and uniformly distributed on Zn\mathbb{Z}_n and consider the random symmetric subset of Zn\mathbb{Z}_n defined as follows:

S:=±({Z1,…,Zm}∪⋃i=1d[Yi−m,Yi+m]).(65)S := \pm\left(\{Z_1,\ldots,Z_m\}\cup\bigcup_{i=1}^{d}[Y_i-m,Y_i+m]\right). \tag*{(65)}

We claim that SS has the desired properties with high probability as n→∞n\to\infty. First observe that (dm)2≪n(dm)^2\ll n, so that with high probability, no repetition occurs in the list of elements appearing on the right-hand side of (65). On that event, we have

∣S∣=2m+2d(2m+1)∼nα,(66)|S|=2m+2d(2m+1)\sim n^\alpha, \tag*{(66)}

showing (i). Moreover, on the same event, the uniform law on SS coincides with

ν:=(1−θ)(ξ⋆μ)+θσ,(67)\nu:= (1-\theta)(\xi\star\mu)+\theta\sigma, \tag*{(67)}

where θ=2m∣S∣∼120log⁡n\theta=\frac{2m}{|S|}\sim\frac{1}{20\log n} and ξ\xi is the uniform measure on [−m,m][-m,m], while

μ:=12d∑j=1d(δYj+δ−Yj)andσ:=12m∑j=1m(δZj+δ−Zj).(68)\mu:=\frac{1}{2d}\sum_{j=1}^{d}(\delta_{Y_j}+\delta_{-Y_j}) \qquad\text{and}\qquad \sigma:=\frac{1}{2m}\sum_{j=1}^{m}(\delta_{Z_j}+\delta_{-Z_j}). \tag*{(68)}

By Lemma 4, we have with high probability,

ϱ(μ)≤23andϱ(σ)≤13log⁡nnα/2.(69)\varrho(\mu)\le\frac{2}{3} \qquad\text{and}\qquad \varrho(\sigma)\le\frac{13\log n}{n^{\alpha/2}}. \tag*{(69)}

By linearity and the convolution-product property of the Fourier transform, this implies ϱ(ν)≤2/3\varrho(\nu)\le2/3 which, in view of Lemma 3, guarantees (ii), as well as half of (iii), namely tMIX=O(log⁡n)t_{\mathrm{MIX}}=O(\log n). To prove the other half, fix u>0u>0 and set t:=⌈ulog⁡n⌉t:=\lceil u\log n\rceil. During the time interval [0,t][0,t], a random walk with jump distribution ν\nu has chance

q:=e−θt∑k=0tp(1−θ)t(k)∼12e−u/20(70)q:=e^{-\theta t}\sum_{k=0}^{t}p_{(1-\theta)t}(k)\sim\frac{1}{2}e^{-u/20} \tag*{(70)}

to use no jump in supp⁡(σ)\operatorname{supp}(\sigma) and no more than tt jumps in supp⁡(ξ⋆μ)\operatorname{supp}(\xi\star\mu), in which case it lies in

A:=[−tm,tm]+⋃i=0tsupp⁡(μ⋆i).(71)A:=[-tm,tm]+\bigcup_{i=0}^{t}\operatorname{supp}(\mu^{\star i}). \tag*{(71)}

Using the function hh in the proof of Lemma 2, we have

∣A∣≤(2tm+1)(2d+tt)=O(n12+h(u,20)).(72)|A|\le(2tm+1)\binom{2d+t}{t}=O\left(n^{\frac{1}{2}+h(u,20)}\right). \tag*{(72)}

Choosing uu so small that h(u,20)<1/2h(u,20)<1/2 ensures that U(A)≪1\mathcal{U}(A)\ll1, and we conclude that

lim inf⁡n→∞d(ulog⁡n)≥12e−u20≥14.(73)\liminf_{n\to\infty} d(u\log n)\ge\frac{1}{2}e^{-\frac{u}{20}}\ge\frac{1}{4}. \tag*{(73)}

establishing tmix=Ω(log⁡n)t_{\mathrm{mix}}=\Omega(\log n). Finally, since the distance to equilibrium decreases under convolution, d(t)d(t) is at most the distance to equilibrium at time θt\theta t for a random walk with jump distribution σ\sigma, and applying Lemma 3 to the latter yields

d(t)≤n[ϱ(σ)]r+1+∑j=0rpθt(j),d(t)\le\sqrt{n}[\varrho(\sigma)]^{r+1}+\sum_{j=0}^{r}p_{\theta t}(j),

for all t≥0t\ge0 and r∈Z+r\in\mathbb{Z}_{+}. In view of (69), choosing r=⌊1/α⌋r=\lfloor1/\alpha\rfloor is enough to guarantee that the first term vanishes, and since θ∼1/(20log⁡n)\theta\sim1/(20\log n), we conclude that for every u>0u>0,

lim sup⁡n→∞d(ulog⁡n)≤∑j=0rpu/20(j).\limsup_{n\to\infty}d(u\log n)\le\sum_{j=0}^{r}p_{u/20}(j).

The right-hand side is of course less than 1, and (iv) is proved.

Achieving near-logarithmic degrees

In this final section, we improve the polynomial sparsity of the above construction to the near-logarithmic one promised in Theorem 2. Rather than decreasing the degree of the graph, our idea is to artificially increase its volume by embedding the walk into a much larger group. Specifically, we add an independent coordinate whose dimension is exponentially large, but which mixes so fast that it does not affect the overall distance to equilibrium.

Proof of Theorem 2. We use the notation gap⁡(Γ)\operatorname{gap}(\Gamma), tmix(Γ)t_{\mathrm{mix}}(\Gamma) and dΓ(⋅)d_{\Gamma}(\cdot) for the spectral gap, mixing time and distance to equilibrium of a simple random walk on the abelian Cayley graph Γ\Gamma. Let (an)n≥1(a_n)_{n\ge1} satisfy 1≪log⁡an≪log⁡n1\ll\log a_n\ll\log n. We consider two (nn-dependent) symmetric abelian Cayley graphs Γ1=Cay⁡(G1,S1)\Gamma_1=\operatorname{Cay}(G_1,S_1) and Γ2=Cay⁡(G2,S2)\Gamma_2=\operatorname{Cay}(G_2,S_2). The first one is such that

∣G1∣=n,∣S1∣∼anlog⁡n,gap⁡(Γ1)=Θ(1),tmix(Γ1)≪log⁡n,(74)|G_1|=n,\qquad|S_1|\sim a_n\log n,\qquad\operatorname{gap}(\Gamma_1)=\Theta(1),\qquad t_{\mathrm{mix}}(\Gamma_1)\ll\log n, \tag*{(74)}

and its existence is guaranteed, for example, by the random construction in Lemma 4 (take G1=ZnG_1=\mathbb{Z}_n and S1={±Y1,…,±Yd}S_1=\{\pm Y_1,\ldots,\pm Y_d\} with d=⌊(anlog⁡n)/2⌋d=\lfloor(a_n\log n)/2\rfloor and Y1,…,YdY_1,\ldots,Y_d independent and uniform). For the second one, we simply invoke Proposition 4 with α=1/3\alpha=1/3 to obtain, after extraction, a graph satisfying

∣G2∣∼an3,∣S2∣∼an,gap⁡(Γ2)=Θ(1),tmix(Γ2)=Θ(log⁡an),(75)|G_2|\sim a_n^3,\qquad|S_2|\sim a_n,\qquad\operatorname{gap}(\Gamma_2)=\Theta(1),\qquad t_{\mathrm{mix}}(\Gamma_2)=\Theta(\log a_n), \tag*{(75)}

as well as the following property, which crucially precludes the occurrence of a cutoff:

∀u>0,lim sup⁡n→∞dΓ2(ulog⁡an)<1.(76)\forall u > 0,\qquad\limsup_{n\to\infty} d_{\Gamma_2}(u\log a_n) < 1. \tag*{(76)}

Now, we claim that the properties announced in the theorem are satisfied by the Cartesian product of Γ1\Gamma_1 and Γ2\Gamma_2, i.e. the Cayley graph Γ=Cay⁡(G,S)\Gamma=\operatorname{Cay}(G,S) defined by

G:=G1×G2,andS:=(S1×{0})∪({0}×S2).(77)G := G_1 \times G_2,\qquad\text{and}\qquad S := (S_1 \times\{0\}) \cup(\{0\} \times S_2). \tag*{(77)}

We first note that this graph has the desired sparsity ∣S∣∼anlog⁡∣G∣|S| \sim a_n\log|G|. Indeed,

log⁡∣G∣=log⁡∣G1∣+log⁡∣G2∣∼log⁡nand∣S∣=∣S1∣+∣S2∣∼anlog⁡n.(78)\log|G| = \log|G_1| + \log|G_2| \sim\log n\qquad\text{and}\qquad|S| = |S_1| + |S_2| \sim a_n\log n. \tag*{(78)}

Also, observe that the simple random walk on Γ\Gamma can be described as X(t)=(X1(θ1t),X2(θ2t))X(t)=(X_1(\theta_1t),X_2(\theta_2t)), where X1,X2X_1,X_2 are independent simple random walks on Γ1,Γ2\Gamma_1,\Gamma_2 respectively, and where

θ1=∣S1∣∣S∣∼1andθ2=∣S2∣∣S∣∼1log⁡n.(79)\theta_1 = \frac{|S_1|}{|S|} \sim1\qquad\text{and}\qquad\theta_2 = \frac{|S_2|}{|S|} \sim\frac{1}{\log n}. \tag*{(79)}

This decomposition into independent coordinates guarantees that

max⁡{dΓ1(θ1t),dΓ2(θ2t)}≤dΓ(t)≤dΓ1(θ1t)+dΓ2(θ2t),(80)\max\{d_{\Gamma_1}(\theta_1t),d_{\Gamma_2}(\theta_2t)\}\le d_\Gamma(t)\le d_{\Gamma_1}(\theta_1t)+d_{\Gamma_2}(\theta_2t), \tag*{(80)}

for all t≥0t\ge0. In particular, it follows that

tmix(Γ)=Θ(tmix(Γ1)θ1+tmix(Γ2)θ2)=Θ(log⁡nlog⁡an),(81)t_{\mathrm{mix}}(\Gamma)=\Theta\left(\frac{t_{\mathrm{mix}}(\Gamma_1)}{\theta_1}+\frac{t_{\mathrm{mix}}(\Gamma_2)}{\theta_2}\right)=\Theta(\log n\log a_n), \tag*{(81)}

while (xref)(76) shows that for any fixed u>0u>0,

lim sup⁡n→∞dΓ(utmix(Γ))<1.(82)\limsup_{n\to\infty}d_\Gamma(ut_{\mathrm{mix}}(\Gamma))<1. \tag*{(82)}

Thus, the simple random walk on Γ\Gamma does not exhibit cutoff. Yet, we have

gap⁡(Γ)=min⁡{θ1gap⁡(Γ1),θ2gap⁡(Γ2)}=Θ(1log⁡n),(83)\operatorname{gap}(\Gamma)=\min\{\theta_1\operatorname{gap}(\Gamma_1),\theta_2\operatorname{gap}(\Gamma_2)\}=\Theta\left(\frac{1}{\log n}\right), \tag*{(83)}

so that the product condition is satisfied. Finally, the absence of cutoff implies that for small enough ε>0\varepsilon>0, wmix(ε)=Θ(tmix)=Θ(log⁡nlog⁡an)w_{\mathrm{mix}}(\varepsilon)=\Theta(t_{\mathrm{mix}})=\Theta(\log n\log a_n), while a direct evaluation shows that the right-hand side of our main window estimate (Theorem 1) is also Θ(log⁡nlog⁡an)\Theta(\log n\log a_n).

Acknowledgment and AI-use statement

This work was partially supported by the ERC consolidator grant 101123174. AI was only used for typos and bibliography. The writing, ideas and proofs are entirely our own.

References

  1. [1]David Aldous. Random walks on finite groups and rapidly mixing Markov chains. In Séminaire de Probabilités XVII, volume 986 of Lecture Notes in Mathematics, pages 243–297. Springer, 1983.DOI
  2. [2]David Aldous and Persi Diaconis. Shuffling cards and stopping times. The American Mathematical Monthly, 93(5):333–348, 1986.DOI
  3. [3]Noga Alon and Yuval Roichman. Random Cayley graphs and expanders. Random Structures & Algorithms, 5(2):271–284, 1994.DOI
  4. [4]Ery Arias-Castro, Persi Diaconis, and Richard Stanley. A super-class walk on upper-triangular matrices. Journal of Algebra, 278(2):739–765, 2004.
  5. [5]Riddhipratim Basu, Jonathan Hermon, and Yuval Peres. Characterization of cutoff for reversible Markov chains. The Annals of Probability, 45(3):1448–1487, 2017.
  6. [6]Persi Diaconis. The cutoff phenomenon in finite Markov chains. Proceedings of the National Academy of Sciences, 93(4):1659–1664, 1996.pubmed.ncbi.nlm.nih.gov/11607633
  7. [7]Persi Diaconis and Laurent Saloff-Coste. Moderate growth and random walk on finite groups. Geometric and Functional Analysis, 4(1):1–36, 1994.DOI
  8. [8]Persi Diaconis and Mehrdad Shahshahani. Generating a random permutation with random transpositions. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, 57:159–179, 1981.DOI
  9. [9]Jian Ding, Eyal Lubetzky, and Yuval Peres. Total variation cutoff in birth-and-death chains. Probability Theory and Related Fields, 146(1–2):61–85, 2010.
  10. [10]Bradley Efron and Charles Stein. The jackknife estimate of variance. The Annals of Statistics, 9(3):586–596, 1981.DOI
  11. [11]Jonathan Hermon, Xiangying Huang, Francesco Pedrotti, and Justin Salez. Concentration of information on discrete groups. Probability Theory and Related Fields, 196(3):2085–2102, 2026.arxiv.org/abs/2409.16869
  12. [12]Jonathan Hermon, Xiangying Huang, and Justin Salez. Cutoff for random walks on nilpotent groups, 2026.arxiv.org/abs/2610.35561
  13. [13]Jonathan Hermon and Sam Olesker-Taylor. Cutoff for random walks on upper triangular matrices. 2019.arxiv.org/abs/1911.02974
  14. [14]Jonathan Hermon and Sam Olesker-Taylor. Geometry of random Cayley graphs of Abelian groups. The Annals of Applied Probability, 33(5):3520–3562, 2023.DOI
  15. [15]Jonathan Hermon and Sam Olesker-Taylor. Cutoff for almost all random walks on Abelian groups. Journal of the European Mathematical Society, 28(5):1913–1977, 2026.arxiv.org/abs/2102.02809
  16. [16]Robert Hough. Mixing and cut-off in cycle walks. Electronic Journal of Probability, 22:1–49, 2017.DOI
  17. [17]Xiangying Huang. Conjugacy-invariant random walks on nilpotent groups, 2026.arxiv.org/abs/2601.03384
  18. [18]Robin Kaiser, Ecaterina Sava-Huss, and Yuwen Wang. Abelian sandpiles on Sierpiński gasket graphs. The Electronic Journal of Combinatorics, 31(1):P1.6, 2024.arxiv.org/abs/2209.03169
  19. [19]Laurent Miclo. An example of application of discrete Hardy’s inequalities. Markov Processes and Related Fields, 5(3):319–330, 1999.
  20. [20]Florentin Münch and Justin Salez. Mixing time and expansion of non-negatively curved Markov chains. Journal de l’École polytechnique — Mathématiques, 10:575–590, 2023.arxiv.org/abs/2206.08294
  21. [21]Evita Nestoridi. Super-character theory and comparison arguments for a random walk on the upper triangular matrices. Journal of Algebra, 521:97–113, 2019.arxiv.org/abs/1609.01238
  22. [22]Evita Nestoridi and Allan Sly. The random walk on upper triangular matrices over ℤ/mℤ. Probability Theory and Related Fields, 187(3–4):571–601, 2023.arxiv.org/abs/2012.08731
  23. [23]Francesco Pedrotti and Justin Salez. A new cutoff criterion for non-negatively curved chains. Duke Mathematical Journal, 2025. To appear.arxiv.org/abs/2501.13079
  24. [24]Justin Salez. University of cutoff for exclusion with reservoirs. The Annals of Probability, 51(2):478–494, 2023.arxiv.org/abs/2201.03463
  25. [25]Justin Salez. Cutoff for non-negatively curved Markov chains. Journal of the European Mathematical Society, 26(11):4375–4392, 2024.arxiv.org/abs/2102.05597
  26. [26]Justin Salez. Modern aspects of Markov chains: entropy, curvature and the cutoff phenomenon, 2025. Saint-Flour lecture notes.arxiv.org/abs/2508.21055
  27. [27]Justin Salez. Cutoff for non-negatively curved diffusions. Inventiones Mathematicae, 246, 2026.arxiv.org/abs/2501.01304

Paper details

vlnc:W_hb5fear6
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

AI

View statement
Looking for related papers…
Contents