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, is a finite abelian group equipped with a probability measure , and we consider a -valued continuous-time Markov chain with initial condition and generator acting on as follows:
We call an abelian random walk with jump distribution . An important special case is that where is uniform on a set : the process is then exactly a simple random walk on the Cayley graph , i.e. the directed graph with vertices and edges
Coming back to the general case, we may, upon restricting the group if needed, assume that is generated by the support of . This guarantees that the law of approaches the uniform law on as . A standard way to quantify this convergence is through the total-variation distance to equilibrium, defined at any time as follows:
This function decreases continuously from to , and the time at which it reaches a given precision is known as the mixing time:
The default value for is , in which case we simply write . 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
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 , through the smallest non-zero jump rate:
The second is the spectral gap of , i.e. the difference between its two largest eigenvalues, once projected onto the real axis. Since commutes with its transpose , this is also the spectral gap of the symmetric generator , and we have the variational characterization
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 , we have
where is a constant that depends only on .
This estimate will be shown to be sharp, except for the constant (see Theorem 2 below). It becomes particularly interesting when the size of the group 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 depends on a size parameter , which is kept implicit to lighten notation, and we consider the large-volume limit where . In this regime, it is sometimes the case that
Here and throughout the paper, we use the standard asymptotic notation , , , and to mean, respectively, that the ratio tends to , to , remains bounded away from , from , and from both as . In words, (9) means that instead of decaying gradually from to over time, the distance to equilibrium approaches a step function as . 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
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 , , , 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
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
In words, the condition (12) simply means that each generator 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:
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 be positive numbers satisfying . Then, there is a sequence of (symmetric) abelian Cayley graphs such that
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
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 -valued random variable with law is classically defined as
To define the varentropy of , we simply replace the above expectation with a variance:
Following the lecture notes [26], we say that the random walk satisfies an information-theoretic differential inequality (IDI) with rate if
As shown in [26 Lemma 5.4], this inequality systematically implies the window estimate
where denotes the supremum of the rate function over the interval . This approach was first implemented in the context of non-negatively curved diffusions [27], which were shown to satisfy the IDI (18) with . 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 (see (15) above), and the latter always diverges in the cutoff regime [20]. Using a different approach, we here manage to replace the term with the much smaller (and optimal) quantity , which crucially remains bounded throughout the regime (13).
Theorem 3 (Universal IDI). Any abelian random walk satisfies the IDI (18) with rate
Before proving this result, let us quickly explain why it implies our main estimate.
Proof of Theorem 1. The function classically satisfies for all , see, e.g., [26 Lemma 1.1]. Recalling that , this implies
for any . Since the function defined at (20) is increasing, we immediately deduce that its supremum over the interval satisfies
On the other hand, the classical inequality (see, e.g., [26 Remark 1.1]) ensures that . Thus, (19) yields the desired conclusion, with .
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 ). 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 with non-increasing birth rates , non-decreasing death rates and stationary law . Then, the Poincaré inequality
holds with , where denotes the smallest non-zero jump rate to .
Proof. A classical use of Hardy inequalities (see [19 Proposition 3]) asserts that for any birth-death chain, the optimal constant in the Poincaré inequality (22) satisfies
where we have introduced the quantities
Here, all intervals are implicitly restricted to and the supremum over an empty set is interpreted as zero. Now, for any , the detailed balance equation gives
and our assumption ensures that the right-hand side is a non-increasing function of . Thus, is a log-concave distribution. In particular, for all in with , we have
Using this estimate and inside the definition of , we obtain
where the second inequality uses the fact that is non-increasing, by log-concavity of . By symmetry, the same bound applies to , and the proof is complete. □
As is clear from its proof, the above lemma is inherently restricted to situations where 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 be defined by
with the right-hand side being interpreted as when . This function is easily checked to be continuous, increasing and concave. For , we then introduce the shorthand
Proposition 1 (Weighted Poincaré inequality for the Poisson distribution). Let be the Poisson distribution with mean . Then, for any , we have
where .
Proof. Consider the birth-death chain with stationary law defined as follows: for each , the jump rates from to and from to are respectively given by
The fact that is increasing readily implies that is decreasing. On the other hand, the fact that is concave with ensures that is decreasing, so that is increasing. Thus, Lemma 1 applies, and it only remains to show that
To do so, we choose in the above infimum. For ,
thanks to the classical estimate for . On the other hand, for ,
Together, those two estimates guarantee that (31) holds, since .
By tensorization, the above proposition admits the following multi-dimensional extension.
Proposition 2 (Tensorized version). Let be the tensor product of Poisson laws with respective means . Then, for any ,
where denotes the canonical basis of and the function in Proposition 1.
Proof. Fix . Proposition 1 allows us to estimate the variance of when viewed as a function of the -th coordinate only, the values of the remaining coordinates being fixed. Specifically, for every , we have
where we have used the shorthand on the right-hand side. Multiplying by and summing over yields
where denotes the expected conditional variance of given all coordinates except the -th one. At this point, the desired conclusion readily follows from the fact that
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 , in order to obtain a local Poincaré inequality for the random walk with jump distribution . The fact that our weight has the form , with increasing and concave turns out to play a crucial role here.
Proposition 3 (Projected version). Fix and set . Then,
for every function , where is as in Theorem 3.
Proof. Write with , and let be the tensor product of Poisson laws with respective means , where . By construction, is then the image of under the map defined by
Thus, for any , we have and Proposition 2 gives
where we have crucially used the super-additivity property
which holds for any countable collection of positive numbers, by concavity of .
Finally, since is the image of under , we have for all ,
Since is non-decreasing in its second argument, this implies
Inserting this into the previous computation concludes the proof, since . □
We are now in a position to establish the universal IDI promised in Theorem 3.
Proof of Theorem 3. Fix and set . Applying Proposition 3 to the function , and using the particular expression of , we obtain
where the last line classically follows from the Fokker–Planck equation . □
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
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 , there is a constant , independent of the pair , such that
Proof. We can assume that , otherwise the claim is trivial. Write with , and fix . By Markov’s inequality, there is a chance at least that no more than jumps are made during the time interval . Moreover, on that event, the random variable is confined to the set
This combinatorial description implies that
Note that the function thus defined is increasing. In particular, if
for some , then recalling that , we deduce that
Putting things together, we conclude that
Finally, note that once is fixed, the exponent can be made arbitrarily close to by choosing small enough. In particular, it can be chosen so that the right-hand side of (47) is larger than , independently of the pair . ∎
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 , a jump distribution and a number , all depending on an implicit parameter in such a way that the random walk with jump distribution satisfies gap and . Then the random walk with jump distribution
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 whose support is much smaller, but which still mixes extremely fast. Here, in addition, we would like the resulting measure
to be uniform on its support. This forces and to be uniform on disjoint sets, with sizes proportional to and respectively. Recalling that our initial jump distribution should satisfy the product condition and have mixing time of order , 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 on the cyclic group is given by
for . We define the spectral radius as the [0,1]-valued number
This parameter controls the mixing properties of the random walk, as summarized next.
Lemma 3 (Spectral bounds). The random walk with jump distribution satisfies
for all and all , where denotes the Poisson law with mean .
Proof. The transition matrix describing the effect of a jump according to can readily be diagonalized in the standard Fourier basis of , and its eigenvalues are exactly the complex numbers , . Since the generator (1) is , the first claim follows. Moreover, the Cauchy-Schwarz inequality yields
where the third line is Parseval’s identity. Replacing with its -fold convolution and using the convolution-product property of the Fourier transform, we obtain
for each . Finally, note that by definition, our random walk satisfies
Since the total-variation distance is convex, we conclude that
for any and any , as desired. ▫
Lemma 4. (Random measures mix quickly.) Consider the (symmetric) random measure
where is an integer and are independent and uniform on . Then,
Proof. Fix . When applied to the random measure (61), the formula (50) gives
This is the empirical mean of independent, centered, -valued variables, so
for any , by Hoeffding’s inequality. Choosing sets the right-hand side to . Since , taking a union bound over half of the 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 . Then, for each , there is a symmetric set such that simple random walk on satisfies
;
;
;
for every .
In particular, the product condition is satisfied but there is no cutoff.
:::`
Proof. We omit the index to lighten notation. Set and . Let be independent and uniformly distributed on and consider the random symmetric subset of defined as follows:
We claim that has the desired properties with high probability as . First observe that , 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
showing (i). Moreover, on the same event, the uniform law on coincides with
where and is the uniform measure on , while
By Lemma 4, we have with high probability,
By linearity and the convolution-product property of the Fourier transform, this implies which, in view of Lemma 3, guarantees (ii), as well as half of (iii), namely . To prove the other half, fix and set . During the time interval , a random walk with jump distribution has chance
to use no jump in and no more than jumps in , in which case it lies in
Using the function in the proof of Lemma 2, we have
Choosing so small that ensures that , and we conclude that
establishing . Finally, since the distance to equilibrium decreases under convolution, is at most the distance to equilibrium at time for a random walk with jump distribution , and applying Lemma 3 to the latter yields
for all and . In view of (69), choosing is enough to guarantee that the first term vanishes, and since , we conclude that for every ,
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 , and for the spectral gap, mixing time and distance to equilibrium of a simple random walk on the abelian Cayley graph . Let satisfy . We consider two (-dependent) symmetric abelian Cayley graphs and . The first one is such that
and its existence is guaranteed, for example, by the random construction in Lemma 4 (take and with and independent and uniform). For the second one, we simply invoke Proposition 4 with to obtain, after extraction, a graph satisfying
as well as the following property, which crucially precludes the occurrence of a cutoff:
Now, we claim that the properties announced in the theorem are satisfied by the Cartesian product of and , i.e. the Cayley graph defined by
We first note that this graph has the desired sparsity . Indeed,
Also, observe that the simple random walk on can be described as , where are independent simple random walks on respectively, and where
This decomposition into independent coordinates guarantees that
for all . In particular, it follows that
while (xref)(76) shows that for any fixed ,
Thus, the simple random walk on does not exhibit cutoff. Yet, we have
so that the product condition is satisfied. Finally, the absence of cutoff implies that for small enough , , while a direct evaluation shows that the right-hand side of our main window estimate (Theorem 1) is also .
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]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]David Aldous and Persi Diaconis. Shuffling cards and stopping times. The American Mathematical Monthly, 93(5):333–348, 1986.DOI
- [3]Noga Alon and Yuval Roichman. Random Cayley graphs and expanders. Random Structures & Algorithms, 5(2):271–284, 1994.DOI
- [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]Riddhipratim Basu, Jonathan Hermon, and Yuval Peres. Characterization of cutoff for reversible Markov chains. The Annals of Probability, 45(3):1448–1487, 2017.
- [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]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]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]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]Bradley Efron and Charles Stein. The jackknife estimate of variance. The Annals of Statistics, 9(3):586–596, 1981.DOI
- [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]Jonathan Hermon, Xiangying Huang, and Justin Salez. Cutoff for random walks on nilpotent groups, 2026.arxiv.org/abs/2610.35561
- [13]Jonathan Hermon and Sam Olesker-Taylor. Cutoff for random walks on upper triangular matrices. 2019.arxiv.org/abs/1911.02974
- [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]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]Robert Hough. Mixing and cut-off in cycle walks. Electronic Journal of Probability, 22:1–49, 2017.DOI
- [17]Xiangying Huang. Conjugacy-invariant random walks on nilpotent groups, 2026.arxiv.org/abs/2601.03384
- [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]Laurent Miclo. An example of application of discrete Hardy’s inequalities. Markov Processes and Related Fields, 5(3):319–330, 1999.
- [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]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]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]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]Justin Salez. University of cutoff for exclusion with reservoirs. The Annals of Probability, 51(2):478–494, 2023.arxiv.org/abs/2201.03463
- [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]Justin Salez. Modern aspects of Markov chains: entropy, curvature and the cutoff phenomenon, 2025. Saint-Flour lecture notes.arxiv.org/abs/2508.21055
- [27]Justin Salez. Cutoff for non-negatively curved diffusions. Inventiones Mathematicae, 246, 2026.arxiv.org/abs/2501.01304