# Repeated Block Averages:
entropic time and mixing profiles

Pietro Caputo, Matteo Quattropani, Federico Sau  Pietro Caputo
Università degli Studi di Roma Tre<EMAIL_ADDRESS>Matteo
Quattropani
Sapienza Università di Roma<EMAIL_ADDRESS>Federico Sau
Università degli Studi di Trieste<EMAIL_ADDRESS>
###### Abstract.

We consider randomized dynamics over the $n$-simplex, where at each step a
random set, or _block_ , of coordinates is evenly averaged. When all blocks
have size 2, this reduces to the _repeated averages_ studied in [CDSZ22], a
version of the _averaging process_ on a graph [AL12]. We study the convergence
to equilibrium of this process as a function of the distribution of the block
size, and provide sharp conditions for the emergence of the _cutoff
phenomenon_. Moreover, we characterize the size of the cutoff window and
provide an explicit Gaussian cutoff profile. To complete the analysis, we
study in detail the simplified case where the block size is not random. We
show that the absence of a cutoff is equivalent to having blocks of size
$n^{\Omega(1)}$, in which case we provide a convergence in distribution for
the total variation distance at any given time, showing that, on the proper
time scale, it remains constantly 1 up to an exponentially distributed random
time, after which it decays following a Poissonian profile.

###### Key words and phrases:

Mixing times of Markov chains; cutoff phenomenon; exchange models; averaging
process

###### 2020 Mathematics Subject Classification:

Primary 60K35; Secondary 82B20; 82C26

##  1\. Introduction

The following process is commonly referred to as Repeated Averages. Given a
probability vector $\eta=(\eta(1),\dots,\eta(n))$, one step of the dynamics
consists in picking two distinct coordinates $x,y$ uniformly at random and
replacing both $\eta(x)$ and $\eta(y)$ by $(\eta(x)+\eta(y))/2$. Iteration of
this single step defines a discrete time, random dynamical system on the
$n$-simplex, converging with high probability to the fixed point given by the
uniform distribution $\pi(x)\equiv 1/n$. Despite the simplicity of this
process, a precise understanding of its convergence was obtained only very
recently in [CDSZ22], where the process was shown to exhibit a cutoff
phenomenon at time $t=c\,n\log n$, with $c=1/2\log 2$, and with an explicit
gaussian mixing profile in a time window of size $n\sqrt{\log n}$. We refer to
[CDSZ22] for a precise description of the result and for more background.

It is natural to ask what happens when the two–coordinate averaging at each
step is replaced by a $k$-coordinate averaging, where $k\geq 2$ is an integer.
We refer to this as the Repeated Block Average (or, simply, Block Average)
process. While an adaptation of the techniques in [CDSZ22] readily implies
that, for fixed $k\in{\mathbb{N}}$, the analogous cutoff phenomenon takes
place at time $t=c\,n\log n$ with $c=1/k\log k$, cases where $k$ is itself a
random variable and/or is allowed to grow with $n$ provide a richer
phenomenology.

In this paper we develop a robust approach to the Block Average process, which
allows us to derive a complete description of the total variation distance
from stationarity in such contexts, including sharp criteria for the
occurrence of cutoff and explicit descriptions of the mixing profile within
the cutoff window in terms of the convolution of two normal random variables.
Our approach is undoubtedly inspired by the methods introduced in [CDSZ22],
but our analysis departs from that work in several key places. In particular,
we bypass the discretization technique, a crucial ingredient in the proof of
the main results of [CDSZ22], by viewing the Block Average process as the
projection of a richer fragmentation process, which we call the pile dynamics,
and which encodes the history of all averaging events.

If the block sizes at each step of the dynamics are i.i.d. copies of an
integer random variable $X\geq 2$, we show that whenever cutoff occurs, then
it takes place at the entropic time

$t_{\rm ent}=\frac{n\log n}{{\mathbb{E}}[X\log X]}\;\text{.}$ (1.1)

Intuitively, $t_{\rm ent}$ is the number of steps required by the Block
Average process started at a Dirac mass to reach an entropy of order $\log n$.
It can be seen as the analogue of the entropic time introduced in [BCS19] in
the context of random walks on random graphs. In line with this perspective,
we link the occurrence of cutoff to a Weak Law of Large Numbers for
$\mu^{-1}\log n$ i.i.d. copies of $\log Y$, where $Y$ is the size-biased
version of the block-size $X$, and $\mu={\mathbb{E}}\big{[}\log Y\big{]}$ is
its mean, provided that $\mu^{-1}\log n\gg 1$. We shall refer to this
asymptotic inequality, which turns out to be necessary for cutoff to occur, as
the entropic product condition (Proposition 2.6 and Theorem 2.7).

We strengthen this result by determining the corresponding cutoff window and
Gaussian profile in the case where $\log Y$ additionally satisfies a Central
Limit Theorem. Interestingly, we describe our profiles as arising from the
interplay of two distinct sources of randomness. Roughly speaking, a source of
Gaussian fluctuations arises from the randomness of the block sizes, while
another stems from the random choice of the elements forming the block
(Theorems 2.8 and 2.10).

When the block size $X$ is deterministically equal to $k=k(n)$, we show that
cutoff occurs if and only if $k=n^{o(1)}$. In other terms, the product
condition $\mu^{-1}\log n\gg 1$ mentioned above becomes a necessary and
sufficient condition for the occurrence of cutoff in this case (Corollary
2.12). On the other hand, when $k=n^{\Omega(1)}$, the total-variation distance
does not necessarily concentrate. We study this case by a suitable multi-scale
analysis for Block Averages which successfully captures its limiting Poisson-
like profile (Theorem 2.13).

We end this introduction with some comments on related work. The two-
coordinate average process analyzed in [CDSZ22] is the complete graph (or mean
field) version of the so called Averaging Process on a graph $G=(V,E)$,
defined as above with the difference that the two coordinates $x,y$ are now
picked uniformly at random among the edges of $G$, that is, the unordered
pairs $\\{x,y\\}\in E$. The systematic mathematical study of the Averaging
Process on a graph has been initiated in [AL12], where some general facts
about convergence in $L^{2}$ and in relative entropy where obtained. Repeated
averages along the edges of a graph represents a natural toy model for
stochastic processes on graphs with a richer structure, with remarkable
applications to opinion dynamics, consensus finding, gossip algorithms, and
even quantum computing, see [CDSZ22, MSW22] for further motivation and
background. We also refer to [MSW22], [QS23], [CQS23], and [Sau24] for further
general results and for some mixing analysis on certain specific families of
graphs. The Averaging process can also be studied on hypergraphs, so that a
single step now consists in a full average of all the masses on the vertices
in a given hyperedge. This point of view was taken in [Spi22], where the
$L^{2}$ convergence was analyzed. We note that the Block Average process
introduced above can be seen as a mean field version of the Averaging Process
on a hypergraph. Convergence in relative entropy for Block Averages can be
deduced from the estimates in [BC24].

##  2\. Model and main results

###  2.1. Block Average process

Fix an integer $n\geq 2$, and write $V=[n]=\\{1,\dots,n\\}$. Let $\Delta$
denote the set of probability vectors $\eta=(\eta(x))_{x\in V}$. We view
$\eta$ as a mass distribution over the vertex set $V$. Given $A\subset V$,
$\eta\in\Delta$, we write $\varPsi_{A}\eta\in\Delta$ for the mass distribution
obtained after averaging in $A$,

$x\in
V\longmapsto\varPsi_{A}\eta(x)=\begin{cases}\textstyle{\frac{1}{|A|}\sum_{y\in
A}\eta(y)}&\text{if}\ x\in A\\\ \eta(x)&\text{else}\;\text{.}\end{cases}$
(2.1)

Given a random variable $X$ with values in $\\{2,\dots,n\\}$, let
$X_{1},X_{2},\dots$ denote i.i.d. copies of $X$ and let $A_{1},A_{2},\dots$
denote independent choices of uniformly random subsets such that $A_{t}\subset
V$ has size $|A_{t}|=X_{t}$. The $X$-Block Average process is defined as the
discrete time evolution $\eta_{1},\eta_{2},\dots$ given by

$\eta_{t}=\varPsi_{A_{t}}\varPsi_{A_{t-1}}\cdots\varPsi_{A_{1}}\eta\;\text{.}$
(2.2)

We consider the total variation distance from stationarity

$d_{\rm TV}(t)=\|\eta_{t}-\pi\|_{\rm TV}\;\text{,}\;\;$ (2.3)

where $\|v\|_{\rm TV}=\frac{1}{2}\sum_{x\in V}|v(x)|$, and $\pi$ denotes the
uniform distribution $\pi(x)\equiv 1/n$. It is not hard to check that for any
initial mass distribution $\eta\in\Delta$, the sequence of random variables
$d_{\rm TV}(t)$, $t\in{\mathbb{N}}$, is almost surely non-increasing and
converging to $0$, and that the worst initial condition is obtained by placing
all the mass in a single site $x_{0}\in V$; see, e.g., [CQS23]. From now on,
unless otherwise stated, we assume that the initial state is such a Dirac
mass.

Our goal is to quantify this convergence in the limit $n\to\infty$. To this
end, we define the _$\varepsilon$ -mixing time_ of the process as

$t_{\rm mix}(\varepsilon)=\inf\\{t\in{\mathbb{N}}:\;\mathds{E}\left[d_{\rm
TV}(t)\right]<\varepsilon\\}\;\text{,}\;\;$ (2.4)

where $\mathds{E}$ denotes expectation over the Block Average process. The
process is said to exhibit the cutoff phenomenon if the mixing time is, to
leading order, insensitive of the value of $\varepsilon$, that is, if

$t_{\rm mix}(\varepsilon)\sim t_{\rm
mix}(1-\varepsilon)\;\text{,}\;\;\qquad\varepsilon\in(0,1)\;\text{,}\;\;$
(2.5)

where, for two positive sequences $a=a(n),b=b(n)$, we write $a\sim b$ for
$a(n)/b(n)\to 1$. We shall also adopt the standard asymptotic notation $a\ll
b$ for $a(n)/b(n)\to 0$, and $a\asymp b$ if $a(n)/b(n)$ and $b(n)/a(n)$ are
both bounded. Similarly, we write $a\lesssim b$ if $a(n)/b(n)$ stays bounded.

###  2.2. Entropic time and other timescales

We shall identify the entropic time (1.1) as the relevant mixing timescale for
Block Averages, regardless of the block size distribution, see Theorem 2.5.
Before introducing this result, we review and introduce some other relevant
timescales for the process.

As in the usual Averaging Process [AL12], a simple duality relates the mass
distribution $\eta_{t}$ to the corresponding random walk. In our case, a
direct computation, see Appendix A, shows that if the process is started at
the Dirac mass at $x_{0}\in V$, then for all $t\in{\mathbb{N}}$ and $x\in V$,

$\mathds{E}[\eta_{t}(x)]=P_{\rm RW}^{t}(x_{0},x)\;\text{,}\;\;$ (2.6)

where $P_{\rm RW}$ is the transition matrix of the random walk on $V$ obtained
as follows. If the current state is $x$, the next state $y$ is obtained by
first sampling an integer $k$ distributed as the random variable $X$, then a
uniformly random subset $A\subset V$ with size $k$, and finally taking $y\in
A$ uniformly at random if $x\in A$, otherwise $y=x$ if $x\notin A$. It is
straightforward to check that $P_{\rm RW}$ has one eigenvalue $1$, while all
remaining ones are equal to $1-\frac{{\mathbb{E}}[X]-1}{n-1}$. In particular,
the inverse of the spectral gap, referred to as the relaxation time is given
by (see Appendix A)

$t_{\rm rel}=\frac{n-1}{\mathds{E}[X]-1}\;\text{.}$ (2.7)

Observe that $t_{\rm rel}\in[1,n-1]$, and the extremes $1$, and $n-1$ are
reached only in case $X$ is deterministically equal to $n$ and $2$,
respectively. The relaxation time controls convergence to stationarity of the
Block Average process in $L^{2}$ norm, see [AL12] for the usual averaging
process on graphs, and see [Spi22] for the hypergraph version. In our setup,
this can be formulated as follows.

######  Proposition 2.1.

For any initial distribution $\eta\in\Delta$, the $X$-Block Average process
satisfies

$\mathds{E}\bigg{[}\bigg{\|}\frac{\eta_{t}}{\pi}-1\bigg{\|}_{2}^{2}\bigg{]}=\bigg{(}1-\frac{1}{t_{\rm
rel}}\bigg{)}^{t}\,\bigg{\|}\frac{\eta}{\pi}-1\bigg{\|}_{2}^{2}\;\text{,}\;\;\qquad
t\in{\mathbb{N}}\;\text{,}\;\;$ (2.8)

where $\|v\|_{2}:=(\sum_{x\in V}\pi(x)|v(x)|^{2})^{\frac{1}{2}}$ for all
$v\in\mathbb{R}^{V}$.

For the reader’s convenience, we record the proof of this estimate in the
Appendix A. Using Schwarz’ inequality and the fact that
$\|\frac{\eta}{\pi}-1\|_{2}^{2}\leq n-1$, Proposition 2.1 implies a
preliminary upper bound on mixing times:

$t_{\rm mix}(\varepsilon)\leq t_{\rm rel}\,\big{(}\log
n-2\log\varepsilon\big{)}\ ,\qquad\varepsilon\in(0,1)\ .$ (2.9)

An alternative upper bound can be obtained by using relative entropy. Let
$t_{\rm ent}$ denote the entropic time defined in (1.1), and let
$D(\eta\|\pi)$ denote the relative entropy (or KL divergence) of
$\eta\in\Delta$ with respect to $\pi$. The following is a direct consequence
of [BC24, Theorem 1.1].

######  Proposition 2.2.

For all $t\in{\mathbb{N}}$, all initial $\eta\in\Delta$,

$\mathds{E}[D(\eta_{t}\|\pi)]\leq\bigg{(}1-\frac{1}{t_{\rm
ent}}\bigg{)}^{t}D(\eta\|\pi)\;\text{.}$ (2.10)

###### Proof.

An equivalent formulation of [BC24, Theorem 1.1] states that if $A_{1}$ is a
random subset as in (2.2), then, for all $\eta\in\Delta$,

$\mathds{E}[D(\varPsi_{A_{1}}\eta\|\pi)]\leq(1-\kappa)D(\eta\|\pi)\;\text{,}\;\;\qquad\kappa=\frac{1}{t_{\rm
ent}}\;\text{.}$ (2.11)

Iteration of the above estimate yields the conclusion. ∎

Since $D(\eta\|\pi)\leq\log n$, Pinsker inequality and Proposition 2.2 imply
the upper bound

$t_{\rm mix}(\varepsilon)\leq 2t_{\rm ent}\,\big{(}\log\log
n-\log(\sqrt{2}\varepsilon)\big{)}\ ,\qquad\varepsilon\in(0,1)\ .$ (2.12)

######  Remark 2.3.

The entropic time and the relaxation time always satisfy

$1\leq\frac{t_{\rm ent}}{t_{\rm
rel}}\leq\,\frac{n}{n-1}\frac{\mathds{E}[X]-1}{\mathds{E}[X]}\frac{\log
n}{\log{\mathbb{E}}[X]}\ .$ (2.13)

Indeed, the first inequality follows by integrating $(X-1)\,n\log
n-(n-1)\,X\log X\geq 0$, while the second is Jensen inequality
$\mathds{E}[X\log X]\geq\mathds{E}[X]\log\mathds{E}[X]$.

Following [MSW22], relative entropy may be used also to obtain a preliminary
lower bound.

######  Proposition 2.4.

For all $t\in{\mathbb{N}}$, all initial $\eta\in\Delta$,

$\mathds{E}[D(\eta_{t}\|\pi)]\geq D(\eta\|\pi)-\frac{t\,\log n}{t_{\rm
ent}}\;\text{.}$ (2.14)

The proof of Proposition 2.4 is a simple adaptation of the argument in
[MSW22], and its proof is reported in Appendix A. When $\eta$ is a Dirac mass
one has $D(\eta\|\pi)=\log n$, so using a reversed Pinsker inequality,
Proposition 2.4 yields a lower bound on mixing times:

$t_{\rm mix}(\varepsilon)\geq\left(1-\frac{\varepsilon\,n}{n-1}\right)t_{\rm
ent}\;\text{,}\;\;\qquad\varepsilon\in(0,1)\;\text{.}$ (2.15)

Our first result shows that $t_{\rm ent}$ is the right timescale for the decay
of the random sequence $d_{\rm TV}(t)$. In particular, the lower bound (2.15)
is rather sharp.

######  Theorem 2.5.

For any block size distribution, $t_{\rm mix}(\varepsilon)\asymp t_{\rm ent}$,
for all $\varepsilon\in(0,1)$.

###  2.3. Cutoff phenomenon

We now turn our attention to the occurrence of cutoff, as well as to the
identification of the cutoff window and cutoff profile.

We start with a Block Average version of the well-known _product condition_
for reversible Markov chains, stating that if the relaxation time is not much
smaller than the mixing time then there is no cutoff, see, e.g., [LP17,
Section 18.3].

######  Proposition 2.6 (Entropic product condition).

Cutoff as in (2.5) implies $t_{\rm ent}\gg t_{\rm rel}$.

A natural question is whether this entropic product condition is sufficient
for cutoff in our context. In the usual Markov chain setting, this equivalence
holds for specific classes of Markov chains [DLP10, BHP17, Sal23], but it is
not true in general; see, e.g., [LP17, Example 18.7]. Counterexamples to this
equivalence for Block Averages, akin to the example in the aforementioned
reference, are discussed in Section 8 below. Nevertheless, in Theorem 2.7, we
establish a sufficient condition for cutoff based on a strengthened entropic
product condition.

In order to state that, let us introduce one of the key quantities of our
analysis. Let $Y$ be the size-biased version of $X$, so that the parameters
$\mu=\mathds{E}[\log Y]$ and $\sigma^{2}=\operatorname{Var}(\log Y)$ satisfy

$\displaystyle\mu=\frac{\mathds{E}[X\log
X]}{\mathds{E}[X]}\;\text{,}\;\;\qquad\sigma^{2}=\frac{\mathds{E}[X(\log
X)^{2}]}{\mathds{E}[X]}-\mu^{2}\;\text{.}$ (2.16)

With this notation, the entropic time $t_{\rm ent}$ in (1.1) reads

$t_{\rm ent}=\frac{n\log n}{\mathds{E}[X]\,\mu}\;\text{,}\;\;$ (2.17)

whereas the entropic product condition $t_{\rm ent}\gg t_{\rm rel}$ in
Proposition 2.6 becomes

$\displaystyle\mu\ll\log(n)\;\text{.}$ (2.18)

Our next result shows that this condition is sufficient if combined with a
Weak Law of Large Numbers (WLLN) for the variables $\log Y$. We say that $\log
Y$ satisfies the WLLN if

$\lim_{n\to\infty}\mathds{P}\bigg{(}\bigg{|}\frac{1}{\log
n}{\sum_{s=1}^{\mu^{-1}\log n}\left(\log
Y_{s}-\mu\right)}\bigg{|}>\delta\bigg{)}=0\;\text{,}\;\;\qquad\delta>0\;\text{.}$
(2.19)

######  Theorem 2.7 (Cutoff).

Assume the entropic product condition (2.18) and the WLLN (2.19). Then the
Block Average process has cutoff, with $t_{\rm mix}(\varepsilon)\sim t_{\rm
ent}$, $\varepsilon\in(0,1)$.

In words, Theorem 2.7 states that the abrupt convergence to equilibrium for
Block Averages at time $t_{\rm ent}$ is parallel to a WLLN — the simplest
concentration phenomenon in probability — for some auxiliary i.i.d. triangular
arrays of length $\mu^{-1}\log n$. The next result (Theorem 2.8) pushes this
analogy further, establishing that the minimal assumption

$\sigma^{2}\ll{\mu\log n}\;\text{,}\;\;$ (2.20)

yields estimates on the size of the cutoff window. This condition is minimal
because, in general, $\sigma^{2}\leq\mu\log n$ always holds true (cf. (2.16)
and $X\leq n$). Note also that, by Chebyshev inequality, (2.20) alone clearly
implies (2.19).

######  Theorem 2.8 (Cutoff window).

Assume (2.18) and (2.20). Then, the quantity

$t_{\rm w}=\left(1+\frac{\sigma}{\mu}\right)\frac{n\sqrt{\log
n}}{\mathds{E}[X]\sqrt{\mu}}$ (2.21)

satisfies $t_{\rm w}\ll t_{\rm ent}$, and

$t_{\rm mix}(\varepsilon)-t_{\rm mix}(1-\varepsilon)\lesssim t_{\rm
w}\;\text{,}\;\;\qquad\varepsilon\in(0,\tfrac{1}{2})\;\text{.}$ (2.22)

######  Remark 2.9.

The assumptions in Theorem 2.8 may be equivalently restated as

$\displaystyle\frac{t_{\rm ent}}{t_{\rm rel}}\gg
1+\frac{\sigma^{2}}{\mu^{2}}\;\text{,}\;\;$ (2.23)

that is, as a strengthened version of the entropic product condition in
(2.18).

To complete the picture, one is typically interested in capturing the second-
order terms of the mixing times or, equivalently, determining the so-called
cutoff profile. It turns out that, next to the assumptions of Theorem 2.8,
having a Central Limit Theorem (CLT) for $\log Y$ — in place of the WLLN in
(2.19) — suffices to grant a non-trivial Gaussian profile inside the window
$t_{\rm w}$ introduced in Theorem 2.8. To simplify the exposition we consider
two separate scenarios, according to whether the size of the blocks $X$ is
deterministic or not:

  * •

scenario 1: (2.18) holds, and $\sigma\equiv 0$

  * •

scenario 2: (2.18) and (2.20) hold, $\sigma\neq 0$ for all $n\in{\mathbb{N}}$,
and the CLT holds:

$\lim_{n\to\infty}\mathds{P}\bigg{(}\sqrt{\frac{\mu}{\log
n}}\;\sum_{s=1}^{\mu^{-1}\log n}\frac{\log
Y_{s}-\mu}{\sigma}>\beta\bigg{)}=\Phi(-\beta)\;\text{,}\;\;\qquad\beta\in\mathbb{R}\;\text{,}\;\;$
(2.24)

where $\Phi$ is the CDF of a standard Gaussian.

######  Theorem 2.10 (Cutoff profile).

Assume either scenario 1 or scenario 2. Letting $\varrho=\frac{\sigma}{\mu}$,

$d_{\rm TV}(t_{\rm ent}+\beta t_{\rm
w})-\Phi\bigg{(}-\beta\frac{1+\varrho}{\sqrt{1+\varrho^{2}}}\bigg{)}\overset{\mathds{P}}{\longrightarrow}0\;\text{,}\;\;\qquad\beta\in\mathbb{R}\;\text{.}$
(2.25)

Here we use the notation $\overset{\mathds{P}}{\longrightarrow}$ for
convergence in probability. We also note that, as usual, all quantities in the
above expressions (like $\mu,\sigma,\varrho$) are allowed to vary with $n$,
and we do not necessarily assume convergence of the sequence
$\Phi\big{(}-\beta(1+\varrho)/\sqrt{1+\varrho^{2}}\big{)}$.

Figure 2.1.  The cutoff profile in (2.25) for three values of $\varrho$,
namely $\varrho=0,1,5$ (in blue, red and green, respectively).

######  Remark 2.11.

In view of Feller’s theorem (see, e.g., [AL06, Theorem 11.1.5]), simple
manipulations show that, under (2.18) and (2.20), the CLT assumption in (2.24)
is equivalent to the following Lindeberg condition for the triangular array
$\log Y$:

$\lim_{n\to\infty}\mathds{E}\bigg{[}\bigg{(}\frac{\log
Y-\mu}{\sigma}\bigg{)}^{2}\,{\bf 1}_{\left|\frac{\log
Y-\mu}{\sigma}\right|>\delta\sqrt{\frac{\log
n}{\mu}}}\bigg{]}=0\;\text{,}\;\;\qquad\delta>0\;\text{.}$ (2.26)

As already anticipated in the introduction, the factor $\varrho$ appearing in
the cutoff profile

$\beta\in\mathbb{R}\longmapsto\Psi_{\varrho}(\beta)=\Phi\bigg{(}-\beta\frac{1+\varrho}{\sqrt{1+\varrho^{2}}}\bigg{)}\in[0,1]\;\text{,}\;\;$
(2.27)

accounts for the competition of two sources of fluctuations, one from the
block sizes and one from the randomness of the block composition. In
particular, when $\varrho=0$ or $\infty$, only one of the two fluctuations
asymptotically survives. Note that the factor $\varrho$ crucially enters also
in the definition of the cutoff window $t_{\rm w}$ as defined in (2.21).

It is worth to point out the symmetry of the profile with respect to
$\varrho$, that is,

$\Psi_{\varrho}(\beta)=\Psi_{\varrho^{-1}}(\beta)\;\text{,}\;\;\qquad\beta\in\mathbb{R}\;\text{.}$
(2.28)

As a consequence of this symmetry and the monotonicity of
$\varrho\in[0,1]\mapsto(1+\varrho)/{\sqrt{{1+\varrho^{2}}}}$, the curve
associated to $\varrho=0$ is above (resp. below) the one associated to
$\varrho=1$ on the positive (resp. negative) half-line, whereas all other
curves for $\varrho\not\in\\{0,1,\infty\\}$ are sandwiched between these two;
see Figure 2.1.

###  2.4. Deterministic block sizes

When the block size $X$ (and, thus, $\log Y$) is deterministic, Proposition
2.6 and Theorem 2.10 (assuming scenario 1) yield a full characterization of
cutoff – including the cutoff profile – in terms of the entropic product
condition only, as summarized by the following corollary. Note that, in the
deterministic case $X\equiv k$, one has

$t_{\rm rel}=\frac{n-1}{k-1}\;\text{,}\;\;\qquad t_{\rm ent}=\frac{n\log
n}{k\log k}\;\text{,}\;\;\qquad t_{\rm w}=\frac{n\sqrt{\log n}}{k\sqrt{\log
k}}\;\text{.}$ (2.29)

######  Corollary 2.12 (Cutoff for deterministic sizes).

Assume $X\equiv k$, for some sequence $k=k(n)$. Then, the following conditions
are equivalent:

  * •

$\log k\ll\log n$;

  * •

cutoff occurs at time $t_{\rm ent}$ and, further,

$d_{\rm TV}(t_{\rm ent}+\beta t_{\rm
w})\overset{\mathds{P}}{\longrightarrow}\Phi(-\beta)\;\text{,}\;\;\qquad\beta\in\mathbb{R}\;\text{.}$
(2.30)

In particular, Corollary 2.12 includes the main result of [CDSZ22], which
corresponds to $X\equiv 2$.

We now turn to the analysis of mixing in the non-cutoff regime, in case of
deterministic block sizes $X\equiv k$. By Corollary 2.12, we, thus, consider
the case where $k=n^{\delta}$, $\delta\in(0,1)$.

As usual, the initial mass $\eta\in\Delta$ is assumed to be a Dirac delta at a
single site $x_{0}\in V$. The next result shows that after the first random
time at which the initial mass is updated, the total variation distance
concentrates on the timescale $n/k$ around the survival function of a Poisson
process of unit rate.

######  Theorem 2.13 (Non-cutoff for deterministic sizes).

Fix $\delta\in(0,1)$ satisfying $\delta^{-1}\notin\mathbb{N}$, and take
$X\equiv k$, with $k=n^{\delta}$. Set $\bar{t}(\beta)={\beta n/k}$, for
$\beta\geq 0$, and define the random time

$\tau_{\rm start}=\inf\\{t\geq 1:\;x_{0}\in A_{t}\\}\;\text{.}$ (2.31)

Then,

$d_{\rm TV}(\tau_{\rm
start}+\bar{t}(\beta))\overset{\mathds{P}}{\longrightarrow}\Pr\left(\tau_{\lfloor\delta^{-1}\rfloor}>\beta\right)\;\text{,}\;\;\qquad\beta\geq
0\;\text{,}\;\;$ (2.32)

where $\tau_{j}$ is the $j$-th arrival time of a Poisson process of unit rate.

Figure 2.2. The plot represents the decay over time of $t\mapsto d_{\rm
TV}(\tau_{\rm start}+t)$ in a single realization with $n=10^{7}$ and
$k=n^{0.7}$ (left) and $k=n^{0.4}$ (right), up to the time $t$ such that
$d_{\rm TV}(\tau_{\rm start}+t)=0.2$.

######  Remark 2.14.

The assumption $\delta^{-1}\not\in\mathbb{N}$ is not of purely technical
nature, and the reason of its appearance will be further discussed in Section
7; see Remark 7.4.

Since $\tau_{\rm start}$ is geometrically distributed with mean $n/k$, we can
restate (2.32) as a convergence in distribution for the random variable
$d_{\rm TV}(t)$, that is,

$d_{\rm TV}(\bar{t}(\beta))\overset{\rm
d}{\longrightarrow}\mathds{1}_{S\geq\beta}+\mathds{1}_{S<\beta}\Pr\left(\tau_{\lfloor\delta^{-1}\rfloor}>\beta-S\right)\;\text{,}\;\;\qquad\beta\geq
0\;\text{,}\;\;$ (2.33)

where $S\overset{\rm d}{=}{\rm Exp}(1)$ is a unit rate exponential random
variable, independent of $\tau_{\lfloor\delta^{-1}\rfloor}$. Finally, taking
expectations in (2.33), we readily get

$\mathds{E}[d_{\rm
TV}(\bar{t}(\beta))]\longrightarrow\Pr\big{(}\tau_{\lfloor\delta^{-1}\rfloor+1}>\beta\big{)}\;\text{,}\;\;\qquad\beta\geq
0\;\text{.}$ (2.34)

In words, the above results state that the mixing of the process is
articulated into two distinct phases. At first, mixing needs to be triggered,
by redistributing the unit mass initially placed in a single site. This first
time $\tau_{\rm start}$ is random, and approximately exponentially distributed
with mean $n/k$. After this triggering time, the distance starts to decay
(again on timescales $n/k$), now in a deterministic way, following a
Poissonian profile. A similar two-phase decay has been recently observed on a
related redistribution model [AHHN24].

###  2.5. Outline of the paper

The rest of the paper is organized as follows. Section 3 is devoted to present
the main tools of our analysis. There, we introduce the _pile dynamics_ ,
derive the distribution of the size of a typical pile and its asymptotic
behavior, and establish general upper and lower bounds on the total variation
distance. In Section 4 we prove Theorem 2.5, while in Section 5 we prove the
cutoff results in Theorem 2.7 and Theorem 2.8, and Section 6 is devoted to the
proof of Theorem 2.10 on the cutoff profile. In Section 7 we focus on the
deterministic setup, proving Theorem 2.13. Finally, in Section 8 we provide
some examples showing the sharpness of the conditions in Theorems 2.7, 2.8 and
2.10.

##  3\. Piles & infinitesimal chunks

In this section, we introduce the central objects employed in the proofs of
our main results. Specifically, we present a richer representation of the
block-average dynamics in terms of piles and infinitesimal chunks, rather than
just the mass distribution $\eta_{t}$. Following the evolution of sufficiently
many of these piles will be key to measuring the flatness of the mass
distribution. The notion of piles and chunks is introduced in Section 3.1. In
Sections 3.2 and 3.3, we characterize the explicit distribution and
corresponding asymptotic identities for the size of what we refer to as a
“typical pile”. These findings are exploited and refined in later sections.

###  3.1. Pile-chunk dynamics

The original process is characterized by the variables $\eta_{t}(x)$, $t\geq
0,x\in V$, where $\eta_{t}(x)$ denotes the mass at vertex $x$ at time $t$,
with the initial distribution $\eta_{0}$ given by the Dirac mass ${\bf
1}_{x_{0}}$ at some $x_{0}\in V$. A finer description is obtained by keeping
track of the distinct mass fragments produced by each averaging event, so that
the mass $\eta_{t}(x)$ is given by the sum of the masses of all fragments
present at $x$ at time $t$. These fragments are called _piles_ , and their
evolution can be formally defined as follows. At time zero there is only one
pile at $x_{0}\in V$, with mass equal to $\eta_{0}(x_{0})=1$. Whenever there
is an averaging event at the block $A\subset V$ with $|A|=k$, for every $x\in
A$, each pile present at $x$ is independently split into $k$ labeled piles of
equal mass, and the $k$ new piles are assigned to the sites $y\in A$ using a
uniformly random permutation of $\\{1,\dots,k\\}$. In this way, at each time
$t$, for each $x\in V$, if $\eta_{t}(x)>0$, then there is a finite number of
piles at $x$, whose total mass equals $\eta_{t}(x)$, which we denote
$(\zeta_{t}^{(1)}(x),\zeta_{t}^{(2)}(x),\ldots,\zeta_{t}^{(L)}(x))$, for some
$L=L_{t}(x)\in\mathbb{N}$. We refer to this new process $(\zeta_{t})_{t\geq
0}$ as the pile dynamics. Thus, letting $|\zeta_{t}^{(i)}(x)|\in[0,1]$ denote
the size of the pile $\zeta_{t}^{(i)}(x)$, at any time $t\geq 0$ one has

$\sum_{i}|\zeta_{t}^{(i)}(x)|=\eta_{t}(x)\;\text{,}\;\;\qquad t\geq
0\;\text{,}\;\;x\in V\,.$ (3.1)

We further enrich the pile dynamics $(\zeta_{t})_{t\geq 0}$ by adding a mark
to one of the piles, which we interpret as the evolution of an “infinitesimal
chunk of mass”, and which we denote by $U$. The mark $U$ belongs initially to
the unique pile at $x_{0}$. At each averaging event at the block $A\subset V$
with $|A|=k$, if the mark belongs to a pile sitting at one of the vertices of
$A$, then the mark chooses uniformly at random one of the $k$ fragments into
which its own pile is split and sticks to it until the next averaging event.
When the mark belongs to a pile that is not involved in the averaging, the
mark does not move. Thus, at any time $t\geq 0$, the infinitesimal chunk $U$
belongs to a single pile of the system, denoted, with slight abuse of
notation, $\zeta_{t}(U)$, and has a position, referred to as $e_{t}(U)\in V$,
namely the vertex at which the pile $\zeta_{t}(U)$ sits. We also refer to
$\zeta_{t}(U)$ as the marked pile, or the _typical pile_.

It follows from the above construction that the evolution of the position
$e_{t}(U)$ of the infinitesimal chunk $U$, if we ignore all other variables,
is simply the random walk with transition matrix $P_{\rm RW}$ introduced in
(2.6). Furthermore, if we condition on a realization of all the block updates,
at each time $t\geq 0$, by construction the probability that $U$ is at some
$x\in V$ at time $t$ coincides with $\eta_{t}(x)$, i.e., $\mathds{P}$-a.s.,

${\mathsf{P}}_{U}(e_{t}(U)=x)=\eta_{t}(x)\;\text{,}\;\;\qquad t\geq
0\;\text{,}\;\;x\in V\;\text{,}\;\;$ (3.2)

where ${\mathsf{P}}_{U}$ denotes the quenched law of the evolution of the
infinitesimal chunk $U$. We shall write $\mathsf{E}_{U}$ for the corresponding
expectation. Taking the $\mathds{E}$-expectation on both sides of (3.2), that
is averaging over all block updates, we recover the duality relation (2.6).

The analysis of the evolution of the size $|\zeta_{t}(U)|$ of the marked pile
will be another key ingredient in our proofs. Specifically, we shall fully
exploit the following identity

$\mathds{P}(|\zeta_{t}(U)|\in\mathcal{A})=\mathds{E}\left[|\eta_{t}^{\mathcal{A}}|\right]\;\text{,}\;\;\qquad
t\geq 0\;\text{,}\;\;\mathcal{A}\subset[0,1]\;\text{,}\;\;$ (3.3)

where $\eta_{t}^{\mathcal{A}}$ is defined as the mass configuration obtained
from $\eta_{t}$ by considering only the piles with size in $\mathcal{A}$, and
$|\eta_{t}^{\mathcal{A}}|$ stands for its total mass $\leq 1$. This is easily
derived by taking the expectation with respect to $\mathds{P}$ of the quenched
identity

${\mathsf{P}}_{U}(|\zeta_{t}(U)|\in\mathcal{A})=|\eta_{t}^{\mathcal{A}}|\;\text{,}\;\;\qquad
t\geq 0\;\text{,}\;\;\mathcal{A}\subset[0,1]\;\text{.}$ (3.4)

Indeed, by the definition of the marked pile dynamics, the probability that
$U$ is in a pile of a given size coincides with the total amount of mass in
piles of that size. More generally, we combine (3.2) and (3.4) to obtain,
e.g.,

${\mathsf{P}}_{U}(e_{t}(U)=x\,,\,|\zeta_{t}(U)|\in\mathcal{A}\,,\,\eta_{t}\in\mathcal{B})={\bf
1}\\{\eta_{t}\in\mathcal{B}\\}\,\eta_{t}^{\mathcal{A}}(x)\;\text{,}\;\;$ (3.5)

where $t\geq 0$, $\mathcal{A}\subset[0,1]$, $\mathcal{B}\subset\Delta$, and
$x\in V$. An identity of this type allows us to follow selected portions of
the mass evolving via block averages, depending on the size of the piles and
their locations. As an example of its applications, see, e.g., (4.13) in
Section 4.2.

Moreover, we will gain refined information by following several infinitesimal
chunks $U,U^{\prime},U^{\prime\prime}$, etc., and their piles at the same
time. Their dynamics is defined as follows. All chunks belong initially to the
same pile at $x_{0}$, and when an average event occurs with block $A$, the
chunks independently – albeit simultaneously – uniformly choose one among the
newly generated sub-piles, and stick to it until the next averaging event. It
is worth to mention that, as soon as different infinitesimal chunks join
different piles (and, thus, relocate to different sites), they will never sit
on the same pile at later times. This, however, does not prevent them to have
the same position later on. In formulas, this means that
$\zeta_{t}(U)=\zeta_{t}(U^{\prime})$ if and only if
$\zeta_{s}(U)=\zeta_{s}(U^{\prime})$ for all $s\leq t$, whereas
$e_{t}(U)=e_{t}(U^{\prime})$ does not necessarily imply
$\zeta_{t}(U)=\zeta_{t}(U^{\prime})$. We employ this approach in several
places below; see, e.g., (4.14), Lemma 4.1, Lemma 7.6. In analogy with the
notation used for a single mark, we will write, e.g.,
$\mathsf{P}_{U,U^{\prime},U^{\prime\prime}}$ and
$\mathsf{E}_{U,U^{\prime},U^{\prime\prime}}$ for the joint quenched law and
expectation of the chunks $U,U^{\prime},U^{\prime\prime}$.

We remark that this pile-chunk representation may be viewed as a more flexible
version of the “particle model” introduced in [CDSZ22, Definition 2.5].
Roughly speaking, the authors in [CDSZ22] start by first discretizing the mass
by forming a finite number of equal-sized piles, and then consider their
evolution in a fashion similar to the one described above, with the important
difference that piles which are either too small or that meet other piles
coming from different locations get discarded. These two operations are
crucial when dealing with such a discretized version of the mass average
dynamics. As we will show, our continuous pile-chunk dynamics avoids any
discretization issue, and actually allows us to track the pile dynamics even
when meeting events between piles occur. This will play a prominent role in
Section 7, where we consider block updates of such large size that cutoff is
destroyed, and yet we are still able to identity the mixing profile.

###  3.2. Distribution of the size of a typical pile

Consider an infinitesimal chunk $U$ as described in the previous section.
Since our blocks are chosen uniformly at random and independently, the size
$|\zeta_{t}(U)|$ of its pile has a rather explicit distribution:

$|\zeta_{t}(U)|\overset{\rm d}{=}\prod_{s=1}^{t}Z_{s}^{-1}\;\text{,}\;\;\qquad
t\geq 1\;\text{,}\;\;$ (3.6)

where, letting $X_{s}$ denote the size of the block chosen at step $s$, the
random variables $(Z_{s})_{s\geq 1}$ are i.i.d. with law given by

$\mathds{P}(Z_{s}=1\mid
X_{s})=1-\frac{X_{s}}{n}\;\text{,}\;\;\qquad\mathds{P}(Z_{s}=X_{s}\mid
X_{s})=\frac{X_{s}}{n}\;\text{.}$ (3.7)

Indeed, $Z_{s}=1$ corresponds to the event “the uniformly-chosen block of size
$X_{s}$ did not involve the chunk $U$”, while $Z_{s}>1$ encodes the
information that the update of size $X_{s}$ did hit the site $e_{s}(U)\in V$
and, thus, split the pile $\zeta_{s}(U)$ into $Z_{s}=X_{s}$ sub-piles. This
readily implies (3.6) and (3.7).

Thus, for all $t\geq 1$ and $\theta\in(0,1)$,

$\displaystyle\mathds{P}\big{(}|\zeta_{t}(U)|>\theta\big{)}$
$\displaystyle=\mathds{P}\bigg{(}\sum_{s=1}^{t}\log
Z_{s}<-\log\theta\bigg{)}\;\text{,}\;\;$ (3.8)

and part of our work will go into deriving sharp asymptotics for the
probability on the right-hand side. For this purpose, let $T=T(t)$ be the
number of successful splittings, i.e.,

$T=T(t):=\\#\\{s\leq t:Z_{s}>1\\}\in\\{0,1,\ldots,t\\}\;\text{,}\;\;$ (3.9)

which satisfies

$T\overset{\rm d}{=}{\rm Bin}(t,\mathds{P}(Z_{1}>1))\overset{\rm d}{=}{\rm
Bin}\bigg{(}t,\frac{\mathds{E}[X]}{n}\bigg{)}\;\text{.}$ (3.10)

Further, let us define $Y_{s}:=Z_{s}\mid\\{Z_{s}>1\\}$, whose law is nothing
but the size-biased distribution of $X_{s}$, that is, letting
$p_{X}(k):=\mathds{P}(X_{s}=k)$, we have

$p_{Y}(k):=\mathds{P}(Y_{s}=k)=\mathds{P}(Z_{s}=k\mid
Z_{s}>1)=\frac{\mathds{P}(X_{s}=k)\frac{k}{n}}{\sum_{k=2}^{n}\mathds{P}(X_{s}=k)\frac{k}{n}}=\frac{k\,p_{X}(k)}{\mathds{E}[X]}\;\text{,}\;\;$
(3.11)

for all $k\in\\{2,\ldots,n\\}$. Hence, we obtain

$\displaystyle\begin{aligned}
\mathds{P}\bigg{(}\sum_{s=1}^{t}\log(Z_{s})<-\log\theta\bigg{)}&=\mathds{P}\bigg{(}\sum_{s=1}^{T}\log
Z_{s}<{-\log\theta}\,\bigg{|}\,Z_{s}>1\,,\,\forall\,s\leq T\bigg{)}\\\
&=\mathds{P}\bigg{(}\sum_{s=1}^{T}\log
Y_{s}<{-\log\theta}\bigg{)}\;\text{.}\end{aligned}$ (3.12)

By collecting the above steps and observing that, conditional to
$T=T(t)\in\\{1,\ldots,t\\}$, the variables $(Y_{s})_{s\geq 1}$ are all i.i.d.
and distributed as in (3.11), we just proved the following crucial result.

######  Lemma 3.1 (Size of a typical pile).

For all $t\geq 1$ and $\theta\in(0,1)$, we have

$\mathds{P}\big{(}|\zeta_{t}(U)|>\theta\big{)}=\mathds{P}\bigg{(}\sum_{s=1}^{T}\log
Y_{s}<-\log\theta\bigg{)}\;\text{,}\;\;$ (3.13)

where $T\overset{\rm d}{=}{\rm Bin}(t,\frac{\mathds{E}[X]}{n})$,
$(Y_{s})_{s\geq 1}$ are i.i.d. with distribution $p_{Y}$ given in (3.11), and
all random variables are mutually independent.

If one believes the heuristics that the system is at equilibrium as soon as
the typical pile has size $\approx\frac{1}{n}$, that is

$t_{\rm mix}\approx\inf\left\\{t\geq
0\mid\mathds{P}\left(|\zeta_{t}(U)|\approx\tfrac{1}{n}\right)\approx
1\right\\}\;\text{,}\;\;$ (3.14)

then Lemma 3.1 provides an efficient tool to guess the mixing time simply via
a LLN for $\log Y$. Furthermore, in the cutoff regime, by controlling the
fluctuations of $\log Y$ (that is, having a CLT), one may hope that this same
heuristics could yield a candidate for the size of the window, and, possibly
even the corresponding profile. In the rest of the paper, we turn the
heuristics in (3.14) into a rigorous framework. Moreover, we show how a
Gaussian profile, with a variance depending on the interplay between the
fluctuations of $T$ and $\log Y$, arises in presence of cutoff.

######  Remark 3.2.

Analogues of Lemma 3.1, and of the heuristics in (3.14), appear in other works
on random walks on random graphs [BHS17, BCS18, BCS19], as well as in
[CDSZ22], with some remarkable differences. In [BHS17, BCS18, BCS19],
$Y_{s}^{-1}$ is the (out-)degree of a random vertex sampled with probability
proportional to its (in-)degrees, but $T\equiv t$ deterministically. In
[CDSZ22], $T\overset{\rm d}{=}{\rm Bin}(t,\frac{2}{n})$, but $\log Y\equiv\log
2$ deterministically.

###  3.3. Asymptotics for the size of a typical pile

A crucial step in the proofs of our main results consists in determining
precise asymptotics for the tail probability of $|\zeta_{t}(U)|$, the typical
size of a pile, appearing in Lemma 3.1. This is the content of the following
three lemmas (whose proof is deferred to the end of the section), dealing with
the assumptions in Theorem 2.7, 2.8, and 2.10, respectively. As already
mentioned, the representation provided in Lemma 3.1 plays a crucial role here.
In particular, we shall apply (3.13) with $\theta=e^{\psi}/n$ for some
$\psi\ll\log n$, yielding

$\mathds{P}\bigg{(}|\zeta_{t}(U)|>\frac{e^{\psi}}{n}\bigg{)}=\mathds{P}\bigg{(}\sum_{s=1}^{T}\log
Y_{s}<\log n-\psi\bigg{)}\;\text{.}$ (3.15)

The first lemma covers the setting in Theorem 2.7.

######  Lemma 3.3.

Assume (2.18) and a WLLN for $\log Y$ as in (2.19). Then, for all
$0<\psi\ll\log n$, we have

$\displaystyle\lim_{n\to\infty}\mathds{P}\bigg{(}|\zeta_{at_{\rm
ent}}(U)|>\frac{e^{\psi}}{n}\bigg{)}=\begin{dcases}1&\text{if}\ a<1\\\
0&\text{if}\ a>1\;\text{.}\end{dcases}$ (3.16)

The second lemma deals with the setting in Theorem 2.8. Let us introduce a
convenient shorthand notation: recalling $t_{\rm ent}$ and $t_{\rm w}$ from
(2.17) and (2.21), respectively, set

$t_{*}(\beta)=t_{\rm ent}+\beta t_{\rm
w}\;\text{,}\;\;\qquad\beta\in\mathbb{R}\;\text{.}$ (3.17)

######  Lemma 3.4.

Assume (2.18) and (2.20). Then, for all $\gamma\in\mathbb{R}$ and
$\psi=\gamma\sqrt{\mu\log n}$, we have

$\lim_{\beta\to-\infty}\liminf_{n\to\infty}\mathds{P}\bigg{(}|\zeta_{t_{*}(\beta)}(U)|>\frac{e^{\psi}}{n}\bigg{)}=1\;\text{,}\;\;\quad\lim_{\beta\to\infty}\limsup_{n\to\infty}\mathds{P}\bigg{(}|\zeta_{t_{*}(\beta)}(U)|>\frac{e^{\psi}}{n}\bigg{)}=0\;\text{,}\;\;$
(3.18)

where $t_{*}(\beta)$ is defined in (3.17).

The third lemma is concerned with the setting in Theorem 2.10. Here, we shall
exploit Lemma 3.5 which deals with a joint CLT for both variables $T$ and
$\log Y$ on the right-hand side (3.15). This suggests the convolution-type
form of the limiting probabilities that we find in (3.20) below. Observe that
this limit profile coincides with the one in Theorem 2.10 (see Remark 3.6).

######  Lemma 3.5.

In the setting of Theorem 2.10, for all $\gamma\in\mathbb{R}$ and
$\psi=\gamma\sqrt{\mu\log n}$, we have

$\displaystyle\lim_{n\to\infty}\left|\mathds{P}\bigg{(}|\zeta_{t_{*}(\beta)}(U)|>\frac{e^{\psi}}{n}\bigg{)}-\Xi_{\varrho}(\beta,\gamma)\right|=0\;\text{,}\;\;\qquad\beta\in\mathbb{R}\;\text{,}\;\;$
(3.19)

where $t_{*}(\beta)$ is given in (3.17), and

$\Xi_{\varrho}(\beta,\gamma)=\int_{-\infty}^{\infty}\varphi(\alpha)\,\Phi(-\tfrac{1}{\varrho}\left(\alpha+\beta(1+\varrho)+\gamma\right))\,{\rm
d}\alpha\;\text{.}$ (3.20)

Here, $\varphi$ is the pdf of a standard Gaussian. As a convention, we set
$\Xi_{0}(\beta,\gamma)=\Phi(-\beta)$.

######  Remark 3.6.

Although $\Xi_{\varrho}(\beta,\gamma)$ and the cutoff profile in Theorem 2.10
look different at first sight, they are essentially the same function. Indeed,
a simple manipulation with convolution of two Gaussian pdf’s yields

$\Xi_{\varrho}(\beta,\gamma)=\Phi\bigg{(}-\frac{\beta\left(1+\varrho\right)+\gamma}{\sqrt{1+\varrho^{2}}}\bigg{)}\;\text{,}\;\;$
(3.21)

which, indeed, coincides with the cutoff profile found in Theorem 2.10 after
taking $\gamma\to 0$.

We shall prove the three above lemmas in a unified way.

###### Proof of Lemmas 3.3, 3.4 and 3.5.

Recall from Lemma 3.1 that, for all $t\geq 0$, we have

$\mathds{P}\bigg{(}|\zeta_{t}(U)|>\frac{e^{\psi}}{n}\bigg{)}=\sum_{m=0}^{t}\mathds{P}\big{(}T=m\big{)}\,\mathds{P}\bigg{(}\sum_{s=1}^{m}\log
Y_{s}<\log n-\psi\bigg{)}\;\text{,}\;\;$ (3.22)

with $T\overset{\rm d}{=}{\rm Bin}(t,\frac{\mathds{E}[X]}{n})$, $Y\sim p_{Y}$
(cf. (3.11)), and all random variables are independent. Now, introduce the
following piecewise constant functions of $\alpha\in\mathbb{R}$:

$m(\alpha)\coloneqq\lfloor\mathds{E}[T]+\alpha\sqrt{{\rm
Var}(T)}\rfloor\;\text{,}\;\;$ (3.23)
$\varphi_{n}(\alpha)\coloneqq\mathds{P}(T=m(\alpha))\sqrt{{\rm
Var}(T)}\;\text{,}\;\;\qquad
f_{n}(\alpha)\coloneqq\mathds{P}\left(\sum_{s=1}^{m(\alpha)}\log Y_{s}<\log
n-\psi\right)\;\text{.}$ (3.24)

With these definitions, the right-hand side of (3.22) becomes

$\sum_{m=0}^{t}\mathds{P}\big{(}T=m\big{)}\,\mathds{P}\bigg{(}\sum_{s=1}^{m}\log
Y_{s}<\log
n-\psi\bigg{)}=\int_{\mathbb{R}}\varphi_{n}(\alpha)\,f_{n}(\alpha)\,{\rm
d}\alpha\;\text{.}$ (3.25)

By condition (2.18), we have $\frac{\mathds{E}[X]}{n}\ll 1$; hence, provided
that $t\frac{\mathds{E}[X]}{n}\gg 1$,

${\rm Var}(T)\sim\mathds{E}[T]=\frac{t\,\mathds{E}[X]}{n}\gg 1\;\text{.}$
(3.26)

Moreover, since $T$ is a sum of integer-valued i.i.d. random variables, the
following local CLT holds true (see, e.g., [Tao15, Theorem 7]): recalling
$\varphi_{n}$ in (3.24) and that $\varphi:\mathbb{R}\to\mathbb{R}_{+}$ denotes
the pdf of a standard Gaussian,

$\sup_{\alpha\in\mathbb{R}}|\varphi_{n}(\alpha)-\varphi(\alpha)|\ll
1\;\text{.}$ (3.27)

Hence, since $\int_{\mathbb{R}}\varphi_{n}=\int_{\mathbb{R}}\varphi=1$,
Scheffe’s lemma, (3.27) and $|f_{n}|\leq 1$ yield

$\int_{\mathbb{R}}\varphi_{n}(\alpha)\,f_{n}(\alpha)\,{\rm
d}\alpha\sim\int_{\mathbb{R}}\varphi(\alpha)\,f_{n}(\alpha)\,{\rm
d}\alpha\;\text{.}$ (3.28)

We are thus left to establishing limits for the right-hand side above. In
particular, since $\varphi$ is integrable and smooth, and $|f_{n}|\leq 1$, it
suffices to determine $\liminf_{n\to\infty}$ and $\limsup_{n\to\infty}$, for
a.e. $\alpha\in\mathbb{R}$, of

$f_{n}(\alpha)=\mathds{P}\bigg{(}\sum_{s=1}^{m(\alpha)}(\log Y_{s}-\mu)<\log
n-\mu\,m(\alpha)-\psi\bigg{)}\;\text{.}$ (3.29)

We divide the rest of the proof into three cases, one for each lemma. We
emphasize that, for all three definitions of $t$, the condition in (3.26)
(and, thus, (3.28)) is automatically verified.

Case of Lemma 3.3. Fix $t=at_{\rm ent}$ with $a>0$, and $0<\psi\ll\log n$.
Then, the expression in (3.29) is is estimated, for all $n\in\mathbb{N}$
sufficiently large, $\alpha\in\mathbb{R}$, and $C=C(a,\alpha)>0$, by

$\displaystyle f_{n}(\alpha)$
$\displaystyle\geq\mathds{P}\bigg{(}\sum_{s=1}^{m(\alpha)}(\log
Y_{s}-\mu)<(1-a)\log n-C\sqrt{\log n}-\psi\bigg{)}$ (3.30) $\displaystyle
f_{n}(\alpha)$ $\displaystyle\leq\mathds{P}\bigg{(}\sum_{s=1}^{m(\alpha)}(\log
Y_{s}-\mu)<(1-a)\log n+C\sqrt{\log n}-\psi\bigg{)}\;\text{.}$ (3.31)

By the WLLN assumption in (2.19) and the fact that $(\log
Y_{s})_{s=1}^{m(\alpha)}$ are i.i.d., this proves that, for all
$\alpha\in\mathbb{R}$,

$f_{n}(\alpha)\xrightarrow{n\to\infty}\begin{dcases}1&\text{if}\ a<1\\\
0&\text{if}\ a>1\;\text{,}\end{dcases}$ (3.32)

thus, establishing the desired claim for this case.

Case of Lemma 3.4. Recall (3.17). Fix $t=t_{*}(\beta)=t_{\rm ent}+\beta t_{\rm
w}$ with $\beta\in\mathbb{R}$, and $\psi=\gamma\sqrt{\mu\log n}$ with
$\gamma\in\mathbb{R}$. Thanks to the assumption (2.20), the expression in
(3.29) is estimated, for all $\alpha,\beta,\gamma\in\mathbb{R}$,
$n\in\mathbb{N}$ sufficiently large and some $1\ll\xi\ll\sqrt{\mu\log n}$, by

$\displaystyle f_{n}(\alpha)$
$\displaystyle\geq\mathds{P}\bigg{(}\sum_{s=1}^{m(\alpha)}(\log
Y_{s}-\mu)<-\left(\beta\left(1+\frac{\sigma}{\mu}\right)+\alpha+\gamma\right)\sqrt{\mu\log
n}-\xi\bigg{)}$ (3.33) $\displaystyle f_{n}(\alpha)$
$\displaystyle\leq\mathds{P}\bigg{(}\sum_{s=1}^{m(\alpha)}(\log
Y_{s}-\mu)<-\left(\beta\left(1+\frac{\sigma}{\mu}\right)+\alpha+\gamma\right)\sqrt{\mu\log
n}+\xi\bigg{)}\;\text{.}$ (3.34)

By Chebyshev inequality, we further get

$\displaystyle f_{n}(\alpha)$ $\displaystyle\geq
1-\frac{8}{\beta^{2}}\bigg{(}\frac{\frac{\sigma}{\mu}}{1+\frac{\sigma}{\mu}}\bigg{)}^{2}\geq
1-\frac{8}{\beta^{2}}\;\text{,}\;\;$ $\displaystyle\beta<-2(\alpha+\gamma)$
(3.35) $\displaystyle f_{n}(\alpha)$
$\displaystyle\leq\frac{8}{\beta^{2}}\bigg{(}\frac{\frac{\sigma}{\mu}}{1+\frac{\sigma}{\mu}}\bigg{)}^{2}\leq\frac{8}{\beta^{2}}\;\text{,}\;\;$
$\displaystyle\beta>2(\alpha+\gamma)\;\text{.}$ (3.36)

Hence, taking $\beta\to-\infty$ and $\beta\to\infty$, respectively, yields the
desired claim for this case.

Case of Lemma 3.5. Let

$g_{n}(\alpha)\coloneqq\begin{dcases}{\bf
1}\\{\alpha+\beta+\gamma<0\\}&\text{if}\ \sigma=0\\\
\Phi(-\mu/\sigma\left(\alpha+\beta\left(1+\sigma/\mu\right)+\gamma\right))&\text{if}\
\sigma>0\;\text{.}\end{dcases}$ (3.37)

By setting $t=t_{*}(\beta)$ and $\psi=\gamma\sqrt{\mu\log n}$ as in the
previous case, the assumption in (2.20) ensures that, for all
$\alpha,\beta,\gamma\in\mathbb{R}$ such that $\alpha+\beta+\gamma\neq 0$,

$f_{n}(\alpha)\sim\begin{dcases}{\bf 1}\\{\alpha+\beta+\gamma<0\\}&\text{if}\
\sigma=0\\\ \mathds{P}\bigg{(}\sqrt{\frac{\mu}{\log n}}\sum_{s=1}^{\frac{\log
n}{\mu}}\frac{\log
Y_{s}-\mu}{\sigma}<-L(\alpha,\beta,\gamma)\bigg{)}&\text{if}\
\sigma>0\;\text{,}\end{dcases}$ (3.38)

with

$L(\alpha,\beta,\gamma)=\frac{\mu}{\sigma}\left(\beta\left(1+\frac{\sigma}{\mu}\right)+\alpha+\gamma\right)\;\text{.}$
(3.39)

Hence, the CLT assumption in (2.24) yields, for all
$\alpha,\beta,\gamma\in\mathbb{R}$ satisfying $\alpha+\beta+\gamma\neq 0$,

$f_{n}(\alpha)-g_{n}(\alpha)\xrightarrow{n\to\infty}0\;\text{.}$ (3.40)

This concludes the proof of the third case. ∎

We turn to a discussion of general upper and lower bounds for
$\mathds{E}[d_{\rm TV}(t)]$, which will be used several times in our proofs.
The upper bound is based on an idea from [CDSZ22], while the lower bound uses
explicitly the pile dynamics introduced in Section 3.

###  3.4. A general upper bound for $\mathds{E}[d_{\rm TV}(t)]$

Given a fixed time $t$, we consider a sub-probability distribution
$\tilde{\eta}_{t}\leq\eta_{t}$, obtained by removing some of the piles from
the current configuration $\eta_{t}$. The precise definition of
$\tilde{\eta}_{t}$ will be specified in the applications and it is not
important at this stage. Next, we let the system evolve from time $t$ to time
$t+s$, for some fixed time $s$, with initial distribution $\tilde{\eta}_{t}$.
This can be coupled to $\eta_{t+s}$ by using the same updates in the time
interval $[t,t+s]$. By the triangle inequality and the fact that
$|\eta_{r}|=1$ for all $r\geq 0$, we get

$\displaystyle\|\eta_{t+s}-\pi\|_{\rm TV}$
$\displaystyle\leq\frac{1}{2}\left\\{\sum_{x\in
V}\left|\eta_{t+s}(x)-\frac{1}{n}-\left(\tilde{\eta}_{t+s}(x)-\frac{|\tilde{\eta}_{t}|}{n}\right)\right|+\sum_{x\in
V}\left|\tilde{\eta}_{t+s}(x)-\frac{|\tilde{\eta}_{t}|}{n}\right|\right\\}$
(3.41)
$\displaystyle=1-|\tilde{\eta}_{t}|+|\tilde{\eta}_{t}|\left\|\frac{\tilde{\eta}_{t+s}}{|\tilde{\eta}_{t}|}-\pi\right\|_{\rm
TV}\leq
1-|\tilde{\eta}_{t}|+\frac{|\tilde{\eta}_{t}|}{2}\left\|\frac{\tilde{\eta}_{t+s}}{|\tilde{\eta}_{t}|\pi}-1\right\|_{2}\;\text{.}$
(3.42)

Taking expectation on both sides, letting $\mathcal{F}_{t}$ denote the
$\sigma$-algebra up to time $t$, Jensen inequalities and the $L^{2}$-bound in
Proposition 2.1 yield

$\displaystyle\mathds{E}[\|\eta_{t+s}-\pi\|_{\rm TV}]$ $\displaystyle\leq
1-\mathds{E}[|\tilde{\eta}_{t}|]+\frac{1}{2}\,\mathds{E}\bigg{[}|\tilde{\eta}_{t}|\mathds{E}\bigg{[}\bigg{\|}\frac{\tilde{\eta}_{t+s}}{|\tilde{\eta}_{t}|\pi}-1\bigg{\|}_{2}\bigg{|}\mathcal{F}_{t}\bigg{]}\bigg{]}$
(3.43) $\displaystyle\leq
1-\mathds{E}[|\tilde{\eta}_{t}|]+\frac{1}{2}\bigg{(}1-\frac{1}{t_{\rm
rel}}\bigg{)}^{s/2}\mathds{E}\bigg{[}|\tilde{\eta}_{t}|\bigg{\|}\frac{\tilde{\eta}_{t}}{|\tilde{\eta}_{t}|\pi}-1\bigg{\|}_{2}\bigg{]}$
(3.44) $\displaystyle\leq
1-\mathds{E}[|\tilde{\eta}_{t}|]+\frac{e^{-s/(2t_{\rm
rel})}}{2}\,n\,\mathds{E}\Big{[}\max_{x\in V}\tilde{\eta}_{t}(x)\Big{]}\ .$
(3.45)

For later reference, we rephrase the above argument in terms of a lemma.

######  Lemma 3.7.

For all initial sub-distributions $0\leq\xi\leq\eta_{0}$ and times $s\geq 0$,
we have

$\mathds{E}[\|\eta_{s}-\pi\|_{\rm TV}]\leq
1-\mathds{E}[|\xi|]+\exp\left(-s/2t_{\rm
rel}\right)n\,\mathds{E}\left[\|\xi\|_{\infty}\right]\ .$ (3.46)

###  3.5. A general lower bound for $\mathds{E}[d_{\rm TV}(t)]$

Consider the process $(\eta_{t})_{t\geq 0}$ and the corresponding pile
dynamics $(\zeta_{t})_{t\geq 0}$. For a fixed time $t\geq 0$, $a>1$, let
$w_{t}=w_{t}^{a}$ denote the mass distribution obtained after the removal of
all piles having mass smaller than $\frac{a}{n}$.

######  Lemma 3.8.

For all $t\geq 0$, $a>1$, and $\varepsilon\in(0,1)$, almost surely

$\|\eta_{t}-\pi\|_{\rm TV}\geq{\bf
1}\\{|w_{t}|>1-\varepsilon\\}\left(1-\varepsilon-a^{-1}\right)\;\text{.}$
(3.47)

Moreover,

$\mathds{E}[\|\eta_{t}-\pi\|_{\rm
TV}]\geq\big{(}1-\varepsilon^{-1}\mathds{P}(|\zeta_{t}(U)|<\tfrac{a}{n})\big{)}(1-\varepsilon-a^{-1})\;\text{.}$
(3.48)

###### Proof.

Note that

$\|\eta_{t}-\pi\|_{\rm TV}=\sum_{x\in
V}[\eta_{t}(x)-\tfrac{1}{n}]_{+}\geq\sum_{x\in
V}[w_{t}(x)-\tfrac{1}{n}]_{+}=|w_{t}|-\tfrac{1}{n}|\\{y\mid
w_{t}(y)\geq\tfrac{a}{n}\\}.$ (3.49)

On the other hand, $|\\{y\mid w_{t}(y)\geq\tfrac{a}{n}\\}|\leq\frac{n}{a}$.
Thus, restricting to the event $|w_{t}|>1-\varepsilon$ yields the claim
(3.47). Next, by Markov inequality, and using (3.3),

$\mathds{P}(|w_{t}|>1-\varepsilon)\geq
1-\frac{1-\mathds{E}[|w_{t}|]}{\varepsilon}=1-\frac{\mathds{P}(|\zeta_{t}(U)|<\tfrac{a}{n})}{\varepsilon}\,.$
(3.50)

Taking expectations on both sides of (3.47) we obtain (3.48). ∎

##  4\. Asymptotic equivalence of $t_{\rm ent}$ and $t_{\rm mix}$

In this section we prove Theorem 2.5.

###  4.1. Proof of lower bound in Theorem 2.5

Recall from (2.17) the definition of $t_{\rm ent}$, and let
$\varepsilon\in(0,1)$ and $\delta>0$. By applying the general lower bound in
(3.48) with $t=\delta t_{\rm ent}$ and $a=\varepsilon^{-1}>1$, we have

$\mathds{E}[\|\eta_{t}-\pi\|_{\rm
TV}]\geq\big{(}1-\varepsilon^{-1}\mathds{P}(|\zeta_{t}(U)|<\tfrac{1}{\varepsilon
n})\big{)}\left(1-2\varepsilon\right)\;\text{.}$ (4.1)

To bound the above probability, we employ the result in Lemma 3.1. Let
$T\sim{\rm Bin}(t,\mathds{E}[X]/n)$ and, independently, let $(Y_{s})_{s\geq
1}$ be i.i.d. with $Y_{s}\sim p_{Y}$. For all $n\in\mathbb{N}$ sufficiently
large,

$\displaystyle\mathds{P}(|\zeta_{t}(U)|<\tfrac{1}{\varepsilon n})$
$\displaystyle=\mathds{P}\bigg{(}\sum_{s=1}^{T}\log Y_{s}>\log
n+\log\varepsilon\bigg{)}\leq\sum_{m=0}^{t}\mathds{P}(T=m)\,\frac{m\mathds{E}[\log
Y]}{\log n+\log\varepsilon}$ (4.2)
$\displaystyle=\frac{\mathds{E}[T]\mathds{E}[\log Y]}{\log
n+\log\varepsilon}=\delta\,\frac{\log n}{\log
n+\log\varepsilon}\;\text{,}\;\;$ (4.3)

where we used Markov inequality and the definition $t=\delta t_{\rm ent}$.
Therefore, the desired result follows by taking first $n\to\infty$, then
$\delta\to 0$, and finally $\varepsilon\to 0$.

###  4.2. Proof of upper bound in Theorem 2.5

Fix $t=at_{\rm ent}$, $w=\sqrt{\frac{\log n}{\mu}}\in[1,\sqrt{\log n}]$, and
define

$t_{\star}(a,b)=t+bt_{\rm rel}w=at_{\rm ent}+bt_{\rm rel}w$

for some $b>0$. Observe that, since $\mu\leq\log(n)$,

$\frac{n\log(n)}{\mu\mathds{E}[X]}=t_{\rm ent}\geq\frac{1}{2}t_{\rm
rel}w=\frac{1}{2}\frac{n-1}{\mathds{E}[X]-1}\sqrt{\frac{\log(n)}{\mu}}\;\text{,}\;\;$

and therefore, for all constant $a,b>0$, $t_{\star}(a,b)\asymp t_{\rm ent}$.

Let $\eta_{t}^{*}$ be the restriction of $\eta_{t}$ to those piles of mass
smaller than $\frac{1}{n}$. Define $S(k):=\sum_{s=1}^{T}\log(Y_{s})$,
$k\in{\mathbb{N}}$. By Lemma 3.1 for all $a>0$ large enough,

$\displaystyle\mathds{E}[|\eta_{t}^{*}|]$
$\displaystyle=\mathds{P}(|\zeta_{t}(U)|<\tfrac{1}{n})=\mathds{P}\left(S(T)>\log(n)\right)$
(4.4)
$\displaystyle\geq\mathds{P}\left(S(\lceil\tfrac{a\log(n)}{2\mu}\rceil)>\log(n)\;\text{,}\;\;T>\tfrac{a\log(n)}{2\mu}\right)$
(4.5)
$\displaystyle=\mathds{P}\left(S(\lceil\tfrac{a\log(n)}{2\mu}\rceil)>\log(n)\right)\,\mathds{P}\left(T>\tfrac{a\log(n)}{2\mu}\right)\;\text{.}$
(4.6)

Note that the second probability on the right-hand side of (4.6) goes to $1$
provided $a>0$ is large enough. Similarly, the first probability on the right-
hand side of (4.6) satisfies, for any $a>6$,

$\displaystyle\mathds{P}\left(S(\lceil\tfrac{a\log(n)}{2\mu}\rceil)>\log(n)\right)$
$\displaystyle\geq
1-\mathds{P}\left(\left|S(\lceil\tfrac{a\log(n)}{2\mu}\rceil)-\tfrac{a}{2}\log(n)\right|\geq\tfrac{a}{3}\log(n)\right)$
(4.7) $\displaystyle\geq 1-\frac{9\sigma^{2}}{2a\mu\log(n)}\;\text{.}$ (4.8)

Since $\sigma^{2}\leq\mu\log(n)$, for any $\varepsilon>0$, taking
$a=a(\varepsilon)$ large enough,

$\mathds{E}[|\eta_{t}^{*}|]=\mathds{P}(|\zeta_{t}(U)|<\tfrac{1}{n})\geq
1-\varepsilon\;\text{.}$ (4.9)

Next, for some $c>0$, define

$\tilde{\eta}_{t}(x):=\eta_{t}^{*}(x)\mathds{1}\\{\eta_{t}^{*}(x)\leq\tfrac{e^{cw}}{n}\\}\
,$ (4.10)

and note that with this definition of $\tilde{\eta}_{t}$, by Lemma 3.7 we have

$\displaystyle\begin{aligned} \mathds{E}[\|\eta_{t_{\star}(a,b)}-\pi\|_{\rm
TV}]&\leq 1-\mathds{E}[|\tilde{\eta}_{t}|]+\exp\left(-bw/2+cw\right)\\\
&=1-\mathds{E}[|\eta_{t}^{*}|]+\mathds{E}[|\eta_{t}^{*}(B)|]+\exp\left(-b\tfrac{w}{2}+cw\right)\;\text{,}\;\;\end{aligned}$
(4.11)

where $B:=\\{x\in V\mid\eta_{t}^{*}(x)>\frac{e^{cw}}{n}\\}$, so that

$\mathds{E}[|\tilde{\eta}_{t}|]=\sum_{x\in
V}\mathds{E}\big{[}\eta_{t}^{*}(x)\mathds{1}\\{\eta_{t}^{*}(x)\leq\tfrac{e^{cw}}{n}\\}\big{]}=\mathds{E}[|\eta_{t}^{*}|]-\mathds{E}[\eta_{t}^{*}(B)]\;\text{.}$
(4.12)

By (4.9) and (4.11), it suffices to prove $\mathds{E}[\eta_{t}^{*}(B)]\to 0$
after taking the limits $n\to\infty$ and, then, $c\to\infty$. To this end, we
crucially exploit the identity (3.5) for the pile-chunk dynamics. We have

$\displaystyle\eta_{t}^{*}(B)$ $\displaystyle=\mathsf{P}_{U}(e_{t}(U)\in
B\,,|\zeta_{t}(U)|<\tfrac{1}{n})$ (4.13)
$\displaystyle=\mathsf{P}_{U}(\eta_{t}^{*}(e_{t}(U))>\tfrac{e^{cw}}{n}\,,\,|\zeta_{t}(U)|<\tfrac{1}{n})$
$\displaystyle=\mathsf{E}_{U}\big{[}{\bf
1}\\{\eta_{t}^{*}(e_{t}(U))>\tfrac{e^{cw}}{n}\,,\,|\zeta_{t}(U)|<\tfrac{1}{n}\\}\big{]}$
$\displaystyle=\sum_{x\in V}\mathsf{E}_{U}\big{[}{\bf
1}\\{\eta_{t}^{*}(x)>\tfrac{e^{cw}}{n}\,,\,e_{t}(U)=x\,,\,|\zeta_{t}(U)|<\tfrac{1}{n}\\}\big{]}$
$\displaystyle=\sum_{x\in V}{\bf
1}\\{\eta_{t}^{*}(x)>\tfrac{e^{cw}}{n}\\}\,\mathsf{P}_{U}\big{(}e_{t}(U)=x\,,\,|\zeta_{t}(U)|<\tfrac{1}{n}\big{)}\;\text{.}$

By taking expectation in (4.13), applying Markov inequality, and reasoning as
in Section 3.1, we then deduce

$\displaystyle\mathds{E}[\eta_{t}^{*}(B)]$
$\displaystyle\leq\frac{n}{e^{cw}}\sum_{x\in
V}\mathds{E}\big{[}\eta_{t}^{*}(x)\,\mathsf{P}_{U}\big{(}e_{t}(U)=x\,,\,|\zeta_{t}(U)|<\tfrac{1}{n}\big{)}\big{]}$
(4.14) $\displaystyle=\frac{n}{e^{cw}}\sum_{x\in
V}\mathds{E}\big{[}\mathsf{P}_{U,U^{\prime}}(e_{t}(U)=e_{t}(U^{\prime})=x\,,\,|\zeta_{t}(U)|<\tfrac{1}{n}\,,\,|\zeta_{t}(U^{\prime})|<\tfrac{1}{n})\big{]}$
$\displaystyle=\frac{n}{e^{cw}}\,\mathds{P}\big{(}e_{t}(U)=e_{t}(U^{\prime})\,,\,|\zeta_{t}(U)|<\tfrac{1}{n}\,,\,|\zeta_{t}(U^{\prime})|<\tfrac{1}{n}\big{)}\;\text{.}$

We now estimate the above probability.

######  Lemma 4.1.

For all $t\geq 0$, $\theta\in(0,1)$, and $n\in\mathbb{N}$ sufficiently large,
we have

$\mathds{P}\big{(}e_{t}(U)=e_{t}(U^{\prime})\,,\,|\zeta_{t}(U)|<\theta\,,\,|\zeta_{t}(U^{\prime})|<\theta\big{)}\leq\theta+\frac{1}{n}\;\text{.}$
(4.15)

###### Proof.

First, observe that, under the event
$\\{|\zeta_{t}(U)|<\theta\,,\,|\zeta_{t}(U^{\prime})|<\theta\\}$, the
probability that $U$ and $U^{\prime}$ sit on the same pile is at most
$\theta$. Indeed,

$\displaystyle\mathds{P}\left(\zeta_{t}(U)=\zeta_{t}(U^{\prime})\,,\,|\zeta_{t}(U)|<\theta\,,\,|\zeta_{t}(U^{\prime})|<\theta\right)$
(4.16)
$\displaystyle=\mathds{P}\left(\zeta_{t}(U)=\zeta_{t}(U^{\prime})\,,\,|\zeta_{t}(U)|<\theta\right)$
(4.17) $\displaystyle=\mathds{E}[{\bf
1}\\{|\zeta_{t}(U)|<\theta\\}\mathds{P}(\zeta_{t}(U)=\zeta_{t}(U^{\prime})\mid|\zeta_{t}(U)|)]$
(4.18)
$\displaystyle\leq\theta\,\mathds{P}(|\zeta_{t}(U)|<\theta)\leq\theta\;\text{.}$
(4.19)

Hence, up to errors of size $\theta$ and recalling that initially we have
$\\{e_{0}(U)=e_{0}(U^{\prime})\\}$, the probability that the event
$\\{e_{t}(U)=e_{t}(U^{\prime})\\}$ occurs is given by the probability of the
following event: there exists a time $r\in[1,t)$ at which the two chunks go to
different sites, there exists a time $s\in[r+1,t]$ in which they sit on the
same vertex for the first time after $r$, and then we have
$\\{e_{\ell}(U)=e_{\ell}(U^{\prime})\,,\,\forall\ell\in[s,t]\\}$. In formulas,
this means

$\mathds{P}\big{(}e_{t}(U)=e_{t}(U^{\prime})\,,\,|\zeta_{t}(U)|<\theta\,,\,|\zeta_{t}(U^{\prime})|<\theta\big{)}\leq\theta+\mathds{P}(\exists\,s\leq
t\ \text{s.t.}\ \mathcal{M}_{s-1}^{c}\cap\mathcal{M}_{s,t})\;\text{,}\;\;$
(4.20)

where we define the events
$\mathcal{M}_{r}\coloneqq\\{e_{r}(U)=e_{r}(U^{\prime})\\}$, and, for $s<t$,
$\mathcal{M}_{s,t}\coloneqq\cap_{r=s}^{t}\,\mathcal{M}_{r}$. We now estimate
the probability on the right-hand side of (4.20). A union bound yields

$\mathds{P}(\exists\,s\leq t\ \text{s.t.}\
\mathcal{M}_{s-1}^{c}\cap\mathcal{M}_{s,t})\leq\sum_{s\leq
t}\mathds{P}(\mathcal{M}_{s-1}^{c}\cap\mathcal{M}_{s,t})\ .$ (4.21)

Furthermore, by the Markov property,

$\displaystyle\mathds{P}(\mathcal{M}_{s-1}^{c}\cap\mathcal{M}_{s,t})$
$\displaystyle=\mathds{P}(\mathcal{M}_{s+1,t}\mid\mathcal{M}_{s})\,\mathds{P}(\mathcal{M}_{s}\mid\mathcal{M}_{s-1}^{c})\,\mathds{P}(\mathcal{M}_{s-1}^{c})$
(4.22)
$\displaystyle\leq\mathds{P}(\mathcal{M}_{s+1,t}\mid\mathcal{M}_{s})\,\mathds{P}(\mathcal{M}_{s}\mid\mathcal{M}_{s-1}^{c})$
(4.23)
$\displaystyle=\mathds{P}(\mathcal{M}_{s+1,t}\mid\mathcal{M}_{s})\sum_{k=2}^{n}p_{X}(k)\frac{k(k-1)}{n(n-1)}\frac{1}{k}$
(4.24)
$\displaystyle=\mathds{P}(\mathcal{M}_{s+1,t}\mid\mathcal{M}_{s})\,\frac{1}{n}\frac{1}{t_{\rm
rel}}\ ,\qquad s<t\ ,$ (4.25)

where the second-to-last step follows from the fact that the probability of
selecting a $k$-block containing the two vertices $e_{s-1}(U)\neq
e_{s-1}(U^{\prime})$ is
$\binom{n-2}{k-2}/\binom{n}{k}=\frac{k\left(k-1\right)}{n\left(n-1\right)}$,
while $\frac{1}{k}$ is the probability of having them sitting on the same site
after they have been both involved in a $k$-block update. Analogously, we have

$\mathds{P}\left(\mathcal{M}_{t-1}^{c}\cap\mathcal{M}_{t}\right)\leq\frac{1}{n}\frac{1}{t_{\rm
rel}}\ .$ (4.26)

By the Markov property, stationarity and $e_{0}(U)=e_{0}(U^{\prime})$,

$\mathds{P}(\mathcal{M}_{s+1,t}\mid\mathcal{M}_{s})=\prod_{u=s}^{t-1}\mathds{P}(\mathcal{M}_{u+1}\mid\mathcal{M}_{u})=\left(\mathds{P}(\mathcal{M}_{1})\right)^{t-s}\;\text{.}$
(4.27)

Moreover,

$\mathds{P}(\mathcal{M}_{1})=\sum_{k=2}^{n}p_{X}(k)\left\\{\left(1-\frac{k}{n}\right)+\left(\frac{k}{n}\frac{1}{k}\right)\right\\}=1-\frac{n}{n-1}\frac{1}{t_{\rm
rel}}\leq 1-\frac{1}{t_{\rm rel}}\;\text{.}$ (4.28)

Summarizing,

$\displaystyle\mathds{P}(\exists\,s\leq t\ \text{s.t.}\
\mathcal{M}_{s-1}^{c}\cap\mathcal{M}_{s,t})$
$\displaystyle\leq\frac{1}{n}\frac{1}{t_{\rm rel}}\sum_{s\leq
t}\left(1-\frac{1}{t_{\rm rel}}\right)^{t-s}\leq\frac{1}{n}\ .$ (4.29)

This and (4.20) yield the desired result. ∎

By applying Lemma 4.1 to (4.14), we obtain

$\mathds{E}[\eta_{t}^{*}(B)]\leq 2e^{-cw}\;\text{,}\;\;$ (4.30)

and, thus, the upper bound in Theorem 2.5 follows after choosing $b>c>0$
sufficiently large.

##  5\. Cutoff

In this section we first establish Proposition 2.6, and then prove Theorem 2.7
and Theorem 2.8.

###  5.1. The entropic product condition is necessary for cutoff

By Jensen inequality,

$\mathds{E}[d_{\rm TV}(t)]=\mathds{E}\big{[}\big{\|}\eta_{t}-\pi\big{\|}_{\rm
TV}\big{]}\geq\big{\|}\mathds{E}[\eta_{t}]-\pi\big{\|}_{\rm
TV}\geq\frac{1}{2}\bigg{(}1-\frac{1}{t_{\rm rel}}\bigg{)}^{t}\ ,$ (5.1)

where we use the duality (2.6) and a well-known lower bound for the distance-
to-equilibrium of ${\rm RW}$; see, e.g., [LP17, Eq. (12.15)]. Observe that
(5.1) ensures that

$\frac{t_{\rm mix}(\varepsilon)}{t_{\rm mix}(1/4)}\geq\frac{t_{\rm
rel}-1}{t_{\rm mix}(1/4)}\log\bigg{(}\frac{1}{2\varepsilon}\bigg{)}\;\text{.}$
(5.2)

Therefore, if $t_{\rm ent}\lesssim t_{\rm rel}$, then Theorem 2.5 and (5.2)
imply that the ratio $t_{\rm mix}(\varepsilon)/t_{\rm mix}(1/4)$ diverges to
$\infty$, uniformly over $n$, as $\varepsilon\to 0$. In other words, the
condition $t_{\rm rel}\ll t_{\rm ent}$ is necessary for the sequence
$t\mapsto\mathds{E}[d_{\rm TV}(t)]$ to exhibit cutoff. This proves Proposition
2.6.

###  5.2. Proof of lower bounds in Theorems 2.7 and 2.8

Fix $\varepsilon\in(0,1)$. Assume (2.18) and (2.19), and apply the estimate in
(3.48) with $t=(1-\varepsilon)t_{\rm ent}$ and $a=e^{\psi}$, for some
$1\ll\psi\ll\log n$. Then, Lemma 3.3 ensures that

$\lim_{n\to\infty}\mathds{P}(|\zeta_{t}(U)|<\tfrac{e^{\psi}}{n})=1\;\text{,}\;\;$
(5.3)

hence, concluding the proof of the lower bound of Theorem 2.7.

We proceed similarly, for the lower bound in Theorem 2.8. Use the notation in
Lemma 3.5 and assume (2.18) and (2.20). Applying the estimate in (3.48) with
$t=t_{*}(\beta):=t_{\rm ent}+\beta t_{\rm w}$, $a=e^{\psi}$, where
$\psi:=\gamma\sqrt{\mu\log n}$, for some $\gamma>0$. (Note that conditions
(2.18)–(2.20) ensure that $t_{\rm w}\ll t_{\rm ent}$; moreover, we have
$\psi\gg 1$.) Then, Lemma 3.4 ensures that, for all $\gamma>0$,

$\lim_{\beta\to-\infty}\lim_{n\to\infty}\mathds{P}(|\zeta_{t}(U)|<\tfrac{e^{\psi}}{n})=1\;\text{.}$
(5.4)

###  5.3. Proof of upper bounds in Theorems 2.7 and 2.8

Fix any $t,s\geq 0$, $\psi>0$ and, given the block-averaging and the
corresponding pile dynamics, split $\eta_{t}$ into two parts: $\eta_{t}^{+}$
denotes the mass consisting of piles of size $\geq\frac{e^{\psi}}{n}$,
$\eta_{t}^{-}$ the rest, so that $\eta_{t}=\eta_{t}^{+}+\eta_{t}^{-}$. We now
consider the coupled processes $(\eta_{t+s}^{+},\eta_{t+s}^{-})_{s\geq 0}$
starting at $\eta_{t}^{+}$ and $\eta_{t}^{-}$, respectively, and evolving
according to the same block averages. By the triangle inequality, we get, for
all $s\geq 0$,

$\displaystyle\mathds{E}[d_{\rm TV}(t+s)]$
$\displaystyle\leq\mathds{E}\bigg{[}|\eta_{t}^{+}|\,\bigg{\|}\frac{\eta_{t+s}^{+}}{|\eta_{t}^{+}|}-\pi\bigg{\|}_{\rm
TV}\bigg{]}+\mathds{E}\bigg{[}|\eta_{t}^{-}|\,\bigg{\|}\frac{\eta_{t+s}^{-}}{|\eta_{t}^{-}|}-\pi\bigg{\|}_{\rm
TV}\bigg{]}$ (5.5)
$\displaystyle\leq\mathds{E}[|\eta_{t}^{+}|]+\mathds{E}\bigg{[}|\eta_{t}^{-}|\,\bigg{\|}\frac{\eta_{t+s}^{-}}{|\eta_{t}^{-}|}-\pi\bigg{\|}_{\rm
TV}\bigg{]}$ (5.6)
$\displaystyle=\mathds{P}\bigg{(}|\zeta_{t}(U)|>\frac{e^{\psi}}{n}\bigg{)}+\mathds{E}\bigg{[}|\eta_{t}^{-}|\,\bigg{\|}\frac{\eta_{t+s}^{-}}{|\eta_{t}^{-}|}-\pi\bigg{\|}_{\rm
TV}\bigg{]}\;\text{.}$ (5.7)

Now, let us consider the sub-configuration $\eta_{t+s/2}^{*}$ of
$\eta_{t+s/2}^{-}$ given by

$\eta_{t+s/2}^{*}(x):=\eta_{t+s/2}^{-}(x)\,{\bf
1}\\{\eta_{t+s/2}^{-}(x)\leq\tfrac{e^{3\psi}}{n}\\}\;\text{,}\;\;\qquad x\in
V\;\text{.}$ (5.8)

Hence, by the Markov property and the upper bound in Lemma 3.7, we obtain

$\displaystyle\mathds{E}\bigg{[}|\eta_{t}^{-}|\,\bigg{\|}\frac{\eta_{t+s}^{-}}{|\eta_{t}^{-}|}-\pi\bigg{\|}_{\rm
TV}\bigg{]}$
$\displaystyle\leq\mathds{E}\bigg{[}|\eta_{t}^{-}|\bigg{(}1-\frac{|\eta_{t+s/2}^{*}|}{|\eta_{t}^{-}|}\bigg{)}+|\eta_{t}^{-}|\exp\left(-s/4t_{\rm
rel}+3\psi\right)\bigg{]}$ (5.9)
$\displaystyle\leq\mathds{E}[|\eta_{t}^{-}|]-\mathds{E}[|\eta_{t+s/2}^{*}|]+\exp\left(-s/4t_{\rm
rel}+3\psi\right)$ (5.10)
$\displaystyle=\mathds{E}[|\eta_{t}^{-}|]-\mathds{E}[|\eta_{t+s/2}^{*}|]+\exp\left(-\psi\right)\;\text{,}\;\;$
(5.11)

where the last identity holds by choosing $s=16t_{\rm rel}\psi\geq 0$.

Letting $B:=\\{x\in V:\eta_{t+s/2}^{-}(x)>\frac{e^{3\psi}}{n}\\}$ so that
$\eta_{t+s/2}^{-}(B)=|\eta_{t}^{-}|-|\eta_{t+s/2}^{*}|$, we obtain, by arguing
as in (4.14),

$\displaystyle\mathds{E}[\eta_{t+s/2}^{-}(B)]$
$\displaystyle\leq\frac{n}{e^{3\psi}}\,\mathds{P}(e_{t+s/2}(U)=e_{t+s/2}(U^{\prime})\,,\,|\zeta_{t}(U)|<\tfrac{e^{\psi}}{n}\,,\,|\zeta_{t}(U^{\prime})|<\tfrac{e^{\psi}}{n})$
(5.12)
$\displaystyle\leq\frac{n}{e^{3\psi}}\,\mathds{P}(e_{t+s/2}(U)=e_{t+s/2}(U^{\prime})\,,\,|\zeta_{t+s/2}(U)|<\tfrac{e^{\psi}}{n}\,,\,|\zeta_{t+s/2}(U^{\prime})|<\tfrac{e^{\psi}}{n})\;\text{,}\;\;$
(5.13)

where the last step holds true because the pile sizes are a.s. non-increasing.
By applying Lemma 4.1, we further get

$\mathds{E}[\eta_{t+s/2}^{-}(B)]\leq\frac{n}{e^{3\psi}}\left(\frac{e^{\psi}}{n}+\frac{1}{n}\right)\leq
2e^{-2\psi}\;\text{.}$ (5.14)

Putting all things together, we get

$\mathds{E}[d_{\rm
TV}(t+s)]\leq\mathds{P}\bigg{(}|\zeta_{t}(U)|>\frac{e^{\psi}}{n}\bigg{)}+2e^{-2\psi}+e^{-\psi}\;\text{.}$
(5.15)

This is the key estimate to conclude the proofs of Theorems 2.7 and 2.8.

In case of Theorem 2.7, the desired claim follows by choosing any
$1\ll\psi\ll\frac{t_{\rm ent}}{t_{\rm rel}}\lesssim\log(n)$ and
$t=(1-\varepsilon)t_{\rm ent}$ for any $\varepsilon\in(0,1)$. With this choice
$s=16t_{\rm rel}\psi\ll t$ and the right-hand side of (5.15) goes to zero
thanks to Lemma 3.3 and $\psi\gg 1$.

Similarly, for Theorem 2.8, we fix $\beta\in\mathbb{R}$, and set $t=t_{\rm
ent}+\beta t_{\rm w}$. Recall that, since $\mu\ll\sqrt{\log n}$ by assumption
(2.18), there exists $\gamma\ll 1$ satisfying $\gamma\sqrt{\frac{\log
n}{\mu}}\gg 1$. For such a sequence $\gamma\ll 1$, set
$\psi:=\delta\sqrt{\mu\log n}$, with $\delta=\frac{\gamma}{\mu}>0$. With this
definition, we have (cf. (2.21) and (2.7))

$1\ll\psi\ll\frac{t_{\rm w}}{t_{\rm rel}}\;\text{,}\;\;$ (5.16)

and therefore $s=16t_{\rm rel}\psi\ll t_{\rm w}$. In conclusion, thanks to
Lemma 3.4 and (5.16), the right hand side of (5.15) goes to zero by letting
first $n\to\infty$ and then $\beta\to\infty$. This concludes the proof of both
theorems.

##  6\. Cutoff profile

This section is devoted to the proof of Theorem 2.10. We start by noting that
the lower bound can be obtained arguing as in Section 5.2, using Lemma 3.5 in
place of the rougher estimates in Lemmas 3.3 and 3.4. More precisely, assume
(2.18) and (2.20), and, in the notation in Lemma 3.5, apply the estimate in
(3.48) with $t=t_{*}(\beta):=t_{\rm ent}+\beta t_{\rm w}$, $a=e^{\psi}$, where
$\psi:=\gamma\sqrt{\mu\log n}$, for some $\gamma>0$. Recall that conditions
(2.18)–(2.20) ensure that $t_{\rm w}\ll t_{\rm ent}$ and $\psi\gg 1$. Then,
Lemma 3.5 ensures that, for all $\beta\in\mathbb{R}$ and $\gamma>0$,

$\lim_{n\to\infty}\bigg{|}\mathds{P}(|\zeta_{t}(U)|<\tfrac{e^{\psi}}{n})-\big{(}1-\Xi_{\varrho}(\beta,\gamma)\big{)}\bigg{|}=0\;\text{,}\;\;$
(6.1)

and to conclude the proof of the lower bound it is enough to recall Remark 3.6
and use the triangular inequality.

Therefore, in order to prove Theorem 2.10 we are left to show that, for all
$\beta\in\mathbb{R}$ and $\varepsilon\in(0,1)$, we have

$\mathds{P}\big{(}d_{\rm
TV}(t_{*}(\beta))>\Psi_{\varrho}(\beta)-\varepsilon\big{)}\xrightarrow{n\to\infty}1\;\text{.}$
(6.2)

For this purpose, we fix $\gamma>0$ and apply (3.47) with $a=e^{\psi}>1$,
$\psi:=\gamma\sqrt{\mu\log n}$, and replacing therein $1-\varepsilon$ by
$\Psi_{\varrho}(\beta)-\varepsilon/2$ (cf. (2.27)). With this notation, recall
that $w_{t}$, $t\geq 0$, stands for the sub-probability measure on $V$
obtained by removing from $\eta_{t}$ all the piles having mass smaller than
$e^{\psi}/n$. We obtain

$\displaystyle\mathds{P}(d_{\rm
TV}(t_{*}(\beta))>\Psi_{\varrho}(\beta)-\varepsilon)$ (6.3)
$\displaystyle\geq\mathds{P}(d_{\rm
TV}(t_{*}(\beta))>\Psi_{\varrho}(\beta)-\varepsilon\,,\,|w_{t_{*}(\beta)}|>\Psi_{\varrho}(\beta)-\varepsilon/2)$
(6.4)
$\displaystyle\geq\mathds{P}(\Psi_{\varrho}(\beta)-\varepsilon/2-e^{-\psi}>\Psi_{\varrho}(\beta)-\varepsilon\,,\,|w_{t_{*}(\beta)}|>\Psi_{\varrho}(\beta)-\varepsilon/2)$
(6.5)
$\displaystyle=\mathds{P}(|w_{t_{*}(\beta)}|>\Psi_{\varrho}(\beta)-\varepsilon/2)\;\text{,}\;\;$
(6.6)

where the last step holds for all $n\in\mathbb{N}$ sufficiently large, because
$\psi\gg 1$.

To conclude the proof, in the next section we show that, for all
$\beta\in\mathbb{R}$ and $\varepsilon\in(0,1)$,

$\mathds{P}\left(|w_{t_{*}(\beta)}|>\Psi_{\varrho}(\beta)-\varepsilon/2\right)\to
1\,.$ (6.7)

To do so, we use a second moment argument, showing that

$\mathds{E}[|w_{t_{*}(\beta)}|^{2}]\sim\mathds{E}[|w_{t_{*}(\beta)}|]^{2}\;\text{.}$
(6.8)

Since
$\mathds{E}[|w_{t_{*}(\beta)}|]=\mathds{P}\big{(}|\zeta_{t_{*}(\beta)}(U)|>\frac{e^{\psi}}{n}\big{)}$,
by Lemma 3.5, we would obtain

$\mathds{E}[|w_{t_{*}(\beta)}|]\sim\Psi_{\varrho}(\beta)\;\text{.}$ (6.9)

Then, (6.7) follows at once by (6.8), (6.9), and Chebyshev inequality.

###  6.1. Proof of (6.8)

Recall that we are under the assumptions of Theorem 2.10, and that
$\psi:=\gamma\sqrt{\mu\log n}$, with $\gamma>0$ fixed. Recall the definition
of $t_{*}(\beta)$ in (3.17), and note that under our assumptions we have

$t_{\rm w}=\left(1+\frac{\sigma}{\mu}\right)\frac{n\sqrt{\log
n}}{\mathds{E}[X]\sqrt{\mu}}\gtrsim t_{\rm rel}\sqrt{\frac{\log n}{\mu}}\gg
t_{\rm rel}.$ (6.10)

To ease the reading, in this subsection we use the shortcut $t=t_{*}(\beta)$.

The second moment in (6.8) reads as

$\mathds{E}[|w_{t}|^{2}]=\mathds{P}\left(|\zeta_{t}(U)|\geq\frac{e^{\psi}}{n}\,,|\zeta_{t}(U^{\prime})|\geq\frac{e^{\psi}}{n}\right)\,.$
(6.11)

Introducing the events

$\mathcal{S}_{U}:=\left\\{|\zeta_{t}(U)|<\frac{e^{\psi}}{n}\right\\}\;\text{,}\;\;\qquad\mathcal{S}_{U^{\prime}}:=\left\\{|\zeta_{t}(U^{\prime})|<\frac{e^{\psi}}{n}\right\\}\,.$
(6.12)

We shall prove
$\mathds{P}(\mathcal{S}_{U}^{c}\cap\mathcal{S}_{U^{\prime}}^{c})\sim\mathds{P}(\mathcal{S}_{U}^{c})^{2}$,
or, equivalently,

$\mathds{P}(\mathcal{S}_{U}\cap\mathcal{S}_{U^{\prime}})\sim\mathds{P}(\mathcal{S}_{U})^{2}\;\text{.}$
(6.13)

Let us introduce another timescale, $t_{\rm sep}$, such that

$t_{\rm rel}\ll t_{\rm sep}\ll t_{\rm
rel}\sqrt{\frac{\log(n)}{\mu}}\;\text{,}\;\;$ (6.14)

and call

$\tau_{\rm sep}:=\inf\\{s\geq 0\mid e_{s}(U)\neq
e_{s}(U^{\prime})\\}\;\text{.}$ (6.15)

Consider the event

$\mathcal{E}_{1}:=\\{\tau_{\rm sep}\leq t_{\rm sep}\\}\;\text{.}$ (6.16)

Since the number of effective updates for a chunk up to time $t_{\rm sep}$ is
distributed as $T\sim{\rm Bin}(t_{\rm sep},\mathds{P}(Z>1))$, and the
probability that two chunks sit together after an update is at most $1/2$, we
get

$\begin{split}\mathds{P}(\mathcal{E}_{1}^{c})&\leq\sum_{r=0}^{t_{\rm
sep}}2^{-r}\,\mathds{P}({\rm Bin}(t_{\rm sep},\mathds{P}(Z>1))=r)\ll
1\;\text{,}\;\;\end{split}$ (6.17)

where the last step used $\mathds{P}(Z>1)=\frac{\mathds{E}[X]}{n}\asymp t_{\rm
rel}^{-1}$, as well as the first inequality in (6.14).

We now further introduce two diverging scales, $\theta$ and $K$, satisfying

$\theta\gg\frac{t_{\rm sep}}{t_{\rm rel}}\;\text{,}\;\;\qquad\log
K-\mu\gg(\sigma+1)\sqrt{\theta}\;\text{.}$ (6.18)

Define

$\mathcal{E}_{2}:=\\{\text{the number of updates involving either $U$ or
$U^{\prime}$ before $t_{\rm sep}$ is at most $\theta$}\\}\;\text{.}$ (6.19)

Then, by a union bound and arguing as in (6.17), we obtain

$\mathds{P}(\mathcal{E}_{2}^{c})\leq 2\mathds{P}({\rm Bin}(t_{\rm
sep},\mathds{P}(Z>1))\geq\theta)\ll 1\;\text{,}\;\;$ (6.20)

where the last step follows from the first inequality in (6.18). Moreover,
consider

$\mathcal{E}_{3}:=\\{\text{all updates involving either $U$ or $U^{\prime}$
within $t_{\rm sep}$ are made by blocks of size $\leq K$}\\}\;\text{.}$ (6.21)

Then, by a union bound and Markov inequality, we get

$\mathds{P}(\mathcal{E}_{3}\cap\mathcal{E}_{2})\geq 1-2\mathds{P}\left({\rm
Bin}(\theta,\mathds{P}(Y>K))>0\right)\geq
1-2\theta\mathds{P}(Y>K)\;\text{,}\;\;$ (6.22)

Since Chebyshev inequality and the second inequality in (6.18) ensure

$\mathds{P}(Y>K)=\mathds{P}(\log Y>\log K)=\mathds{P}\left(\log Y-\mu>\log
K-\mu\right)\leq\frac{\sigma^{2}}{(\log
K-\mu)^{2}}\ll\frac{1}{\theta}\;\text{,}\;\;$ (6.23)

we obtain

$\mathds{P}(\mathcal{E}_{2}\cap\mathcal{E}_{3})\sim 1\;\text{.}$ (6.24)

Hence, $\mathds{P}(\mathcal{E}_{1}\cap\mathcal{E}_{2}\cap\mathcal{E}_{3})\sim
1$, and observe that, under
$\mathcal{E}_{1}\cap\mathcal{E}_{2}\cap\mathcal{E}_{3}$, we have
(deterministically)

$|\zeta_{t_{\rm sep}}(U)|,|\zeta_{t_{\rm sep}}(U^{\prime})|\geq
K^{-\theta}\;\text{.}$ (6.25)

Therefore, we proved that with high probability $U$ and $U^{\prime}$ ever
visited different sites (hence, in particular, sit on distinct piles) within
time $t_{\rm sep}$ and their piles at that time are still relatively large (if
$\theta$ and $K$ are not too large). More precisely, by (2.18) and (2.20), we
can choose $\theta$ and $K$ so to satisfy (6.18), as well as

$\theta\log(K)\ll\psi\asymp\sqrt{\mu\log n}\;\text{.}$ (6.26)

As we are interested in the probability of
$\mathcal{S}_{U}\cap\mathcal{S}_{U^{\prime}}$, we have, by (6.17) and (6.24),

$\mathds{P}\big{(}\mathcal{S}_{U}\cap\mathcal{S}_{U^{\prime}}\big{)}\sim\mathds{P}\big{(}\mathcal{S}_{U}\cap\mathcal{S}_{U^{\prime}}\mid\mathcal{E}_{1}\cap\mathcal{E}_{2}\cap\mathcal{E}_{3}\big{)}\;\text{,}\;\;$
(6.27)

which, by (6.25) and the Markov property, is further estimated as follows

$\displaystyle\begin{aligned}
\mathds{P}(\mathcal{S}_{U}\cap\mathcal{S}_{U^{\prime}})&\geq\inf_{z,z^{\prime},r}\widehat{\mathds{P}}_{z,z^{\prime}}\bigg{(}|\zeta_{t-r}(U)|<\frac{e^{\psi}}{n}\,,\,|\zeta_{t-r}(U^{\prime})|<\frac{e^{\psi}}{n}\bigg{)}\;\text{,}\;\;\\\
\mathds{P}(\mathcal{S}_{U}\cap\mathcal{S}_{U^{\prime}})&\leq\sup_{z,z^{\prime},r}\widehat{\mathds{P}}_{r,r^{\prime}}\bigg{(}|\zeta_{t-r}(U)|\leq\frac{e^{\psi}}{n}\,,\,|\zeta_{t-r}(U^{\prime})|<\frac{e^{\psi}}{n}\bigg{)}\;\text{,}\;\;\end{aligned}$
(6.28)

where both $\inf$ and $\sup$ above run over
$(z,z^{\prime},r)\in[K^{-\theta},1]^{2}\times\\{0,\ldots,t_{\rm sep}\\}$,
whereas $\widehat{\mathds{P}}_{z,z^{\prime}}$ denotes the law of two chunks,
initially placed on two different piles of size $z$ and $z^{\prime}$,
respectively.

We now prove the following claim: letting $(A_{s})_{s\geq 1}\subset V$ denote
the random sequence of blocks, and

$\mathcal{E}_{4}:=\\{{\nexists}s\in(\tau_{\rm sep},t]\ \text{s.t.}\
e_{s}(U)\,,\,e_{s}(U^{\prime})\in A_{s}\\}\;\text{,}\;\;$ (6.29)

we have

$\mathds{P}(\mathcal{E}_{4})\to 1\;\text{.}$ (6.30)

By Markov inequality and the definition $t=t_{*}(\beta)\sim t_{\rm ent}$ (cf.
(2.17)), we obtain

$\mathds{P}(\mathcal{E}_{4}^{c})\leq
t\sum_{k=2}^{n}p_{X}(k)\frac{\binom{n-2}{k-2}}{\binom{n}{k}}\lesssim\frac{t_{\rm
ent}\,\mathds{E}[X^{2}]}{n^{2}}\;\text{.}$ (6.31)

Hence, it suffices to prove that the right-hand side above vanishes under our
assumptions. This is the content of the following lemma.

######  Lemma 6.1.

Under conditions (2.18) and (2.20), we have

${t_{\rm ent}\,\mathds{E}[X^{2}]}\ll n^{2}\;\text{.}$ (6.32)

###### Proof.

From the definition of $t_{\rm ent}$ in (2.17), it suffices to prove

$\frac{\mathds{E}[X^{2}]}{\mathds{E}[X\log X]}\ll\frac{n}{\log n}\;\text{.}$
(6.33)

For any $A>0$, and since $y\in[2,\infty)\mapsto y/\log(y)$ is increasing, we
can factorize the numerator in (6.33) as follows

$\displaystyle\mathds{E}[X^{2}]$ $\displaystyle=\mathds{E}[X^{2}{\bf
1}(X/\log(X)\leq A)]+\mathds{E}[X^{2}{\bf 1}(X/\log(X)>A)]$ (6.34)
$\displaystyle\leq
A\,\mathds{E}[X\log(X)]+\frac{n}{\log(n)}\,\mathds{E}[X\log(X){\bf
1}(X/\log(X)>A)]\;\text{,}\;\;$ (6.35)

from which it follows that

$\frac{\mathds{E}[X^{2}]}{\mathds{E}[X\log(X)]}\leq
A+\frac{n}{\log(n)}\frac{\mathds{E}[X\log(X){\bf
1}(X/\log(X)>A)]}{\mathds{E}[X\log(X)]}\;\text{.}$ (6.36)

Recalling that $X\geq 2$, we further bound

$\frac{\mathds{E}[X\log(X){\bf
1}(X/\log(X)>A)]}{\mathds{E}[X\log(X)]}\leq\frac{\mathds{E}[X\log(X){\bf
1}(X>A)]}{\mathds{E}[X\log(X)]}\;\text{.}$ (6.37)

To prove (6.33), observe that

$\frac{\mathds{E}[X\log^{2}(X)]}{\mathds{E}[X\log(X)]}\geq\frac{\mathds{E}[X\log^{2}(X){\bf
1}(X>A)]}{\mathds{E}[X\log(X)]}\geq\log(A)\frac{\mathds{E}[X\log(X){\bf
1}(X>A)]}{\mathds{E}[X\log(X)]}\;\text{,}\;\;$ (6.38)

and now argue by contradiction choosing, e.g., $A=\sqrt{n}$. Assume that the
ratio on the right-hand side of (6.37) does not go to zero when $n\to\infty$.
Then, we would have

${\mathds{E}[X\log^{2}(X)]}\gtrsim{\log(A)}\mathds{E}[X\log(X)]\quad\iff\quad\frac{\mathds{E}[X\log^{2}(X)]}{\mathds{E}[X]}\gtrsim\mu\log(A)\;\text{.}$
(6.39)

Since $A=\sqrt{n}$, by exploiting (2.18) and subtracting
$\mu^{2}\ll\mu\log(n)$ on both sides, we then obtain

$\sigma^{2}\gtrsim\mu\log(n)\;\text{,}\;\;$ (6.40)

which contradicts (2.20). We can therefore deduce that it must be the case
that

$\frac{\mathds{E}[X\log(X){\bf 1}(X>A)]}{\mathds{E}[X\log(X)]}\to
0\;\text{,}\;\;$ (6.41)

and the proof of (6.33) follows from (6.36) and (6.41) with $A=\sqrt{n}$. ∎

In what follows, fix $z,z^{\prime}\in[K^{-\theta},1]^{2}$ and
$t^{\prime}=t-r\in\\{t-t_{\rm sep},\ldots,t\\}$. Going back to (6.28), and
combining it with (6.30), we have

$\displaystyle\widehat{\mathds{P}}_{z,z^{\prime}}\bigg{(}|\zeta_{t^{\prime}}(U)|<\frac{e^{\psi}}{n}\,,\,|\zeta_{t^{\prime}}(U^{\prime})|<\frac{e^{\psi}}{n}\bigg{)}$
(6.42)
$\displaystyle\qquad=\widehat{\mathds{P}}_{z,z^{\prime}}\bigg{(}|\zeta_{t^{\prime}}(U)|<\frac{e^{\psi}}{n}\,,\,|\zeta_{t^{\prime}}(U^{\prime})|<\frac{e^{\psi}}{n}\,,\,\mathcal{E}_{4}\bigg{)}+o(1)$
(6.43)
$\displaystyle\qquad=\mathds{P}\bigg{(}\prod_{s=1}^{t^{\prime}}Z_{s}^{-1}<\frac{e^{\psi}}{zn}\,,\,\prod_{s=1}^{t^{\prime}}(Z_{s}^{\prime})^{-1}<\frac{e^{\psi}}{z^{\prime}n}\bigg{)}+o(1)\;\text{,}\;\;$
(6.44)

where the random vectors $((Z_{s},Z_{s}^{\prime}))_{s=1}^{t^{\prime}}$ are
i.i.d., marginally distributed as in (3.7), and jointly as

$\displaystyle\mathds{P}(Z_{s}=Z_{s}^{\prime}=1\mid
X_{s})=\frac{(n-X_{s})(n-X_{s}-1)}{n(n-1)}\sim
1-\frac{2X_{s}}{n}+\frac{X^{2}_{s}-X_{s}}{n^{2}}\;\text{,}\;\;$ (6.45)
$\displaystyle\mathds{P}(Z_{s}=X_{s}\,,\,Z_{s}^{\prime}=1\mid
X_{s})=\mathds{P}(Z_{s}=1\,,\,Z_{s}^{\prime}=X_{s}\mid X_{s})$ (6.46)
$\displaystyle\qquad=\frac{n(n-1)-(n-X_{s})(n-X_{s}-1)}{2n(n-1)}\sim\frac{X_{s}}{n}-\frac{X^{2}_{s}-X_{s}}{2n^{2}}\;\text{,}\;\;$
(6.47) $\displaystyle\mathds{P}(Z_{s}=Z_{s}^{\prime}=X_{s}\mid
X_{s})=\frac{X_{s}(X_{s}-1)}{n(n-1)}\sim\frac{X_{s}(X_{s}-1)}{n^{2}}\;\text{.}$
(6.48)

We shall prove In particular, given $X_{s}$, $Z_{s}$ and $Z_{s}^{\prime}$ are
not independent. We shall compare this sequence with
$((Z_{s},\widetilde{Z}_{s}))_{s=1}^{t^{\prime}}$, with $Z_{s}$ and
$\widetilde{Z}_{s}$ i.i.d., conditionally on $X_{s}$. More precisely,

$\displaystyle\mathds{P}(Z_{s}=\widetilde{Z}_{s}=1\mid
X_{s})=\left(1-\frac{X_{s}}{n}\right)^{2}=1-\frac{2X_{s}}{n}+\frac{X_{s}^{2}}{n^{2}}\;\text{,}\;\;$
(6.49) $\displaystyle\mathds{P}(Z_{s}=X_{s}\,,\,\widetilde{Z}_{s}=1\mid
X_{s})=\mathds{P}(Z_{s}=1\,,\,Z_{s}^{\prime}=X_{s}\mid X_{s})$ (6.50)
$\displaystyle\qquad=\left(1-\frac{X_{s}}{n}\right)\frac{X_{s}}{n}=\frac{X_{s}}{n}-\frac{X^{2}_{s}}{n^{2}}\;\text{,}\;\;$
(6.51) $\displaystyle\mathds{P}(Z_{s}=\widetilde{Z}_{s}=X_{s}\mid
X_{s})=\frac{X_{s}^{2}}{n^{2}}\;\text{.}$ (6.52)

As a consequence, given $(X_{s})_{s\leq t^{\prime}}$, $(Z_{s},Z_{s}^{\prime})$
can be coupled with $(Z_{s},\widetilde{Z}_{s})$ at a ${\rm TV}$-cost

$\big{\|}(Z_{s},Z_{s}^{\prime}\mid X_{s})_{s\leq
t^{\prime}}-(Z_{s},\widetilde{Z}_{s}\mid X_{s})_{s\leq
t^{\prime}}\big{\|}_{\rm TV}\leq
2\sum_{s=1}^{t^{\prime}}\frac{X_{s}^{2}}{n^{2}}\leq 2\sum_{s=1}^{2t_{\rm
ent}}\frac{X_{s}^{2}}{n^{2}}\;\text{,}\;\;$ (6.53)

whose expectation vanishes by Lemma 6.1. Henceforth, by Markov inequality, we
have

$\mathds{P}\bigg{(}\prod_{s=1}^{t^{\prime}}Z_{s}^{-1}<\frac{e^{\psi}}{zn}\,,\,\prod_{s=1}^{t^{\prime}}(Z_{s}^{\prime})^{-1}<\frac{e^{\psi}}{z^{\prime}n}\bigg{)}=\mathds{P}\bigg{(}\prod_{s=1}^{t^{\prime}}Z_{s}^{-1}<\frac{e^{\psi}}{zn}\,,\,\prod_{s=1}^{t^{\prime}}\widetilde{Z}_{s}^{-1}<\frac{e^{\psi}}{z^{\prime}n}\bigg{)}+o(1)\;\text{.}$
(6.54)

By the independence of $(Z_{s})_{s\geq 1}$ and $(\widetilde{Z}_{s})_{s\geq 1}$
conditioned to $(X_{s})_{s\geq 1}$, we have

$\displaystyle\mathds{P}\bigg{(}\prod_{s=1}^{t^{\prime}}Z_{s}^{-1}<\frac{e^{\psi}}{zn}\,,\,\prod_{s=1}^{t^{\prime}}\widetilde{Z}_{s}^{-1}<\frac{e^{\psi}}{z^{\prime}n}\bigg{)}$
(6.55)
$\displaystyle=\mathds{E}\bigg{[}\mathds{P}\bigg{(}\prod_{s=1}^{t^{\prime}}Z_{s}^{-1}<\frac{e^{\psi}}{zn}\bigg{|}(X_{s})_{s=1}^{t^{\prime}}\bigg{)}\mathds{P}\bigg{(}\prod_{s=1}^{t^{\prime}}\widetilde{Z}_{s}^{-1}<\frac{e^{\psi}}{z^{\prime}n}\bigg{|}(X_{s})_{s=1}^{t^{\prime}}\bigg{)}\bigg{]}\;\text{.}$
(6.56)

We want to show, uniformly over $z,z^{\prime}\in[K^{-\theta},1]$ and
$t^{\prime}\in\\{t-t_{\rm sep},\ldots,t\\}$, that

$\displaystyle\begin{aligned}
&\mathds{E}\bigg{[}\mathds{P}\bigg{(}\prod_{s=1}^{t^{\prime}}Z_{s}^{-1}<\frac{e^{\psi}}{zn}\bigg{|}(X_{s})_{s=1}^{t^{\prime}}\bigg{)}\mathds{P}\bigg{(}\prod_{s=1}^{t^{\prime}}\widetilde{Z}_{s}^{-1}<\frac{e^{\psi}}{z^{\prime}n}\bigg{|}(X_{s})_{s=1}^{t^{\prime}}\bigg{)}\bigg{]}\\\
&\qquad\sim\mathds{E}\bigg{[}\mathds{P}\bigg{(}\prod_{s=1}^{t^{\prime}}Z_{s}^{-1}<\frac{e^{\psi}}{zn}\bigg{|}(X_{s})_{s=1}^{t^{\prime}}\bigg{)}\bigg{]}\mathds{E}\bigg{[}\mathds{P}\bigg{(}\prod_{s=1}^{t^{\prime}}\widetilde{Z}_{s}^{-1}<\frac{e^{\psi}}{z^{\prime}n}\bigg{|}(X_{s})_{s=1}^{t^{\prime}}\bigg{)}\bigg{]}\\\
&\qquad\sim\mathds{P}(\mathcal{S}_{U})^{2}\;\text{.}\end{aligned}$ (6.57)

We now separately prove both approximations in (6.57).

First approximation in (6.57). In what follows, write
$\bar{X}:=(X_{1},\ldots,X_{t^{\prime}})$. In order to prove the first
approximation in (6.57), by Cauchy-Schwarz inequality, it suffices to show

$\sup_{z,t^{\prime}}{\rm Var}\big{(}f(\bar{X})\big{)}\ll
1\;\text{,}\;\;\quad\text{with}\
f(\bar{X})=f_{z,t^{\prime}}(\bar{X}):=\mathds{P}\bigg{(}\prod_{s=1}^{t^{\prime}}Z_{s}^{-1}<\frac{e^{\psi}}{zn}\bigg{|}\bar{X}\bigg{)}\;\text{,}\;\;$
(6.58)

where the supremum runs over $z\in[K^{-\theta},1]$ and
$t^{\prime}\in\\{t-t_{\rm sep},\ldots,t\\}$. Since $\bar{X}$ has i.i.d.
components, we may estimate the above variance by Efron–Stein inequality (see,
e.g., [BLM13, Theorem 3.1]):

$\displaystyle{\rm Var}(f(\bar{X}))$
$\displaystyle\leq\frac{1}{2}\sum_{s=1}^{t^{\prime}}\mathds{E}\big{[}\big{(}f(\bar{X})-f(\bar{X}^{(s)})\big{)}^{2}\big{]}=\frac{t^{\prime}}{2}\,\mathds{E}\big{[}\big{(}f(\bar{X})-f(\bar{X}^{(1)})\big{)}^{2}\big{]}\;\text{,}\;\;$
(6.59)

where, given $\bar{X}$, we defined
$\bar{X}^{(s)}:=(X_{1},\ldots,X_{s-1},X_{s}^{\prime},X_{s+1},\ldots,X_{t^{\prime}})$,
with $X_{s}^{\prime}$ being an independent copy of $X_{s}$, whereas the second
step follows by the symmetry of the function $f$. Let us introduce some
shorthand notation: $W:=\sum_{s=2}^{t^{\prime}}\log(Z_{s})$,
$W_{1}:=\log(Z_{1})$, $W_{1}^{\prime}:=\log(Z_{1}^{\prime})$, and $h:=\log
n-\psi+\log z$. By the tower property, we obtain

$\displaystyle f(\bar{X})-f(\bar{X}^{(1)})$ (6.60)
$\displaystyle=\mathds{P}(W_{1}+W>h\mid\bar{X})-\mathds{P}(W_{1}^{\prime}+W>h\mid\bar{X}^{(1)})$
(6.61) $\displaystyle=\mathds{E}[\mathds{P}(W_{1}+W>h\mid
X_{1},W)-\mathds{P}(W_{1}^{\prime}+W>h\mid X_{1}^{\prime},W)\mid
X_{2},\ldots,X_{t^{\prime}}]$ (6.62)
$\displaystyle=\sum_{w=0}^{\infty}\mathds{P}(W=w\mid
X_{2},\ldots,X_{t^{\prime}})\left\\{\mathds{P}(W_{1}+w>h\mid
X_{1})-\mathds{P}(W_{1}^{\prime}+w>h\mid X_{1}^{\prime})\right\\}\;\text{.}$
(6.63)

By Jensen inequality, we have

$\displaystyle\big{(}f(\bar{X})-f(\bar{X}^{(1)})\big{)}^{2}$ (6.64)
$\displaystyle\leq\sum_{w=0}^{\infty}\mathds{P}(W=w\mid
X_{2},\ldots,X_{t^{\prime}})\left(\mathds{P}(W_{1}+w>h\mid
X_{1})-\mathds{P}(W_{1}^{\prime}+w>h\mid
X_{1}^{\prime})\right)^{2}\;\text{,}\;\;$ (6.65)

and, further taking expectation with respect to $\bar{X}$ and $\bar{X}^{(1)}$,
we get, by the independence of the $X$-variables,

$\displaystyle\mathds{E}\big{[}\big{(}f(\bar{X})-f(\bar{X}^{(1)})\big{)}^{2}\big{]}$
(6.66)
$\displaystyle\leq\sum_{w=0}^{\infty}\mathds{E}\big{[}\mathds{P}(W=w\mid
X_{2},\ldots,X_{t^{\prime}})\big{]}\mathds{E}\big{[}\big{(}\mathds{P}(W_{1}>h-w\mid
X_{1})-\mathds{P}(W_{1}^{\prime}>h-w\mid X_{1}^{\prime})\big{)}^{2}\big{]}$
(6.67) $\displaystyle\leq 2\sum_{w=0}^{h}\mathds{E}\big{[}\mathds{P}(W=w\mid
X_{2},\ldots,X_{t^{\prime}})\big{]}\mathds{E}\big{[}\big{(}\mathds{P}(W_{1}>h-w\mid
X_{1})\big{)}^{2}\big{]}\;\text{.}$ (6.68)

Since, by (3.7) (recall $W_{1}\in\\{0,\log(X_{1})\\}$) and $w\leq h$, we have

$\mathds{P}(W_{1}>h-w\mid X_{1})=\frac{X_{1}}{n}\,{\bf
1}\\{\log(X_{1})>h-w\\}\leq\frac{X_{1}}{n}\;\text{,}\;\;$ (6.69)

the right-hand side of (6.68) is further bounded above by

$\displaystyle 2\sum_{w=0}^{h}\mathds{E}\big{[}\mathds{P}(W=w\mid
X_{2},\ldots,X_{t^{\prime}})\big{]}\frac{\mathds{E}\big{[}X^{2}\big{]}}{n^{2}}\leq
2\,\frac{\mathds{E}\big{[}X^{2}\big{]}}{n^{2}}\;\text{.}$ (6.70)

In conclusion, plugging this back into (6.59), we obtain, uniformly over
$z\in[K^{-\theta},1]$ and $t^{\prime}\in\\{t-t_{\rm sep},\ldots,t\\}$,

${\rm Var}(f(\bar{X}))\leq t^{\prime}\,\frac{\mathds{E}[X^{2}]}{n^{2}}\lesssim
t_{\rm ent}\frac{\mathds{E}[X^{2}]}{n^{2}}\;\text{,}\;\;$ (6.71)

and, thus, the desired claim in (6.58) by Lemma 6.1.

Second approximation in (6.57). Recalling the definition of the event
$\mathcal{S}_{U}$ from (6.12), and the identity in Lemma 3.1 (see also
(3.12)), we need to show, uniformly over $z\in[K^{-\theta},1]$ and
$t^{\prime}\in\\{t-t_{\rm sep},\ldots,t\\}$,

$\mathds{P}\bigg{(}|\zeta_{t}(U)|<\frac{e^{\psi}}{n}\bigg{)}=\mathds{P}\bigg{(}\prod_{s=1}^{t}Z_{s}^{-1}<\frac{e^{\psi}}{n}\bigg{)}\sim\mathds{P}\bigg{(}\prod_{s=1}^{t^{\prime}}Z_{s}^{-1}<\frac{e^{\psi}}{zn}\bigg{)}=\mathds{P}\bigg{(}|\zeta_{t^{\prime}}(U)|<\frac{e^{\psi}}{zn}\bigg{)}\;\text{.}$
(6.72)

Thanks to (6.26), we have $|\log z|\ll\psi\ll\log n$, ensuring

$\mathds{P}\bigg{(}\prod_{s=1}^{t^{\prime}}Z_{s}^{-1}<\frac{e^{\psi}}{zn}\bigg{)}\sim\mathds{P}\bigg{(}\prod_{s=1}^{t^{\prime}}Z_{s}^{-1}<\frac{e^{\psi}}{n}\bigg{)}\;\text{.}$
(6.73)

Similarly, since $t_{\rm sep}/t_{\rm rel}\gg 1$ diverges arbitrarily slow
(satisfying, in particular, (6.14)), for any $m\gg 1$ satisfying
$\mu\frac{t_{\rm sep}}{t_{\rm rel}}\ll\log m\ll\psi\asymp\sqrt{\mu\log n}$,
Markov inequality yields

$\mathds{P}\bigg{(}\sum_{s={t^{\prime}}+1}^{t}\log Z_{s}\geq\log
m\bigg{)}\leq\frac{t_{\rm sep}\,\mathds{E}[\log Z]}{\log m}=\frac{t_{\rm
sep}\,\mathds{E}[X\log X]}{n\log m}\ll 1\;\text{.}$ (6.74)

Since $\log m\ll\psi$, we finally get

$\mathds{P}\bigg{(}\prod_{s=1}^{t^{\prime}}Z_{s}^{-1}<\frac{e^{\psi}}{n}\bigg{)}\sim\mathds{P}\bigg{(}\prod_{s=1}^{t}Z_{s}^{-1}<\frac{e^{\psi}}{n}\bigg{)}\;\text{.}$
(6.75)

and this concludes the proof of (6.13) and, thus, of (6.8). ∎

##  7\. Deterministic block size

In this section, we assume that the blocks’ sizes are deterministically equal
to $k$. Since the case $\frac{\log k}{\log n}\to 0$ is already covered by
Theorem 2.10, we focus on the alternative scenario, namely,
$\limsup_{n\to\infty}\frac{\log k}{\log n}>0$. For simplicity of exposition,
we shall pass to a converging subsequence, and assume

$\exists\lim_{n\to\infty}\frac{\log k}{\log n}>0\;\text{.}$ (7.1)

By Propositions 2.6 and 2.5, cutoff does not occur in this case, and $d_{\rm
TV}$ decays non-trivially on the timescale $n/k$, which coincides, at first
order, with $t_{\rm rel}=\frac{n-1}{k-1}$.

A crucial role is played by the first time in which the site initially
possessing all the mass is involved in a block update. Letting $\tau_{\rm
start}$ denote this time, we have

$\tau_{\rm start}\overset{\rm d}{=}{\rm Geo}(k/n)\;\text{,}\;\;$ (7.2)

and, thus,

$\mathds{P}(\tau_{\rm
start}>\lfloor\beta\tfrac{n}{k}\rfloor)=\left(1-\frac{k}{n}\right)^{\lfloor\beta\frac{n}{k}\rfloor}\;\text{,}\;\;\qquad\beta>0\;\text{.}$
(7.3)

As a consequence, if $\frac{k}{n}\to 0$, $\frac{k}{n}\tau_{\rm
start}\overset{{\rm d}}{\longrightarrow}{\rm Exp}(1)$; otherwise, if
$\frac{k}{n}\to c\in(0,1]$, $\tau_{\rm start}\overset{{\rm
d}}{\longrightarrow}{\rm Geo}(c)$. The core of the mixing phenomenology begins
after this first update. In what follows, for simplicity, we will often denote
by $\eta^{\rm start}$ a configuration having $k$ vertices of mass $k^{-1}$
(the labels of these vertices is not relevant to our scope).

We divide the analysis of the scenario in (7.1) into two regimes, dealt with
in Sections 7.1 and 7.2, respectively:

$\lim_{n\to\infty}\frac{\log k}{\log
n}\in\left[5/6,1\right]\;\text{,}\;\;\qquad\lim_{n\to\infty}\frac{\log k}{\log
n}\in\left(0,5/6\right]\;\text{.}$ (7.4)

######  Remark 7.1.

The value $5/6$ in (7.4) does not have any particular meaning, and the proof
actually works for any constant strictly larger than $1/2$. In other words,
the approach employed for the first regime can be tuned to work for any value
of $k>n^{1/2+o(1)}$. Nevertheless, we found more convenient to present the
proof up to this arbitrary threshold, while incorporating the values of
$n^{1/2}\ll k\ll n^{5/6}$ into the second regime.

Before starting our analysis, let us recall the following elementary identity

$\Pr\left(\tau_{j}>\beta\right)=\Pr\left({\rm Poi}(\beta)\leq
j-1\right)\;\text{,}\;\;\qquad
j\in\mathbb{N}\;\text{,}\;\;\beta>0\;\text{,}\;\;$ (7.5)

where ${\rm Poi}(\beta)$ stands for a Poisson random variable of parameter
$\beta$.

###  7.1. First regime in (7.4)

In this section, we consider $k=cn$, for some sequence $c=c_{n}\in(0,1)$
satisfying

$\lim_{n\to\infty}\frac{\log k}{\log
n}=\lim_{n\to\infty}1-\frac{\log\frac{1}{c}}{\log n}\geq 5/6\;\text{.}$ (7.6)

Note that we skip the trivial case $c\sim 1$, for which, w.h.p., we have
$\tau_{\rm start}=1$ and $d_{\rm TV}(\tau_{\rm start})=1-c\to 0$.

######  Proposition 7.2.

Letting $k=cn$, under the assumption in (7.6), we have, for all $\beta\geq 0$,

$d_{\rm TV}(\tau_{\rm
start}+\lfloor\beta\tfrac{n}{k}\rfloor-1)\overset{\mathds{P}}{\longrightarrow}\left(1-\bar{c}\right)^{\beta}\;\text{,}\;\;\quad\text{if}\
\lim_{n\to\infty}c\eqqcolon\bar{c}>0\;\text{,}\;\;$ (7.7)

whereas

$d_{\rm TV}(\tau_{\rm
start}+\lfloor\beta\tfrac{n}{k}\rfloor-1)\overset{\mathds{P}}{\longrightarrow}e^{-\beta}\;\text{,}\;\;\quad\text{if}\
\lim_{n\to\infty}c=0\;\text{.}$ (7.8)

###### Proof.

Right after time $\tau_{\rm start}$, the vertex set $V$ can be partitioned
into two subsets: the vertices having mass $k^{-1}$ and those having mass
zero. Call $B_{0}^{\rm big}$ the former subset, $B_{0}^{\rm void}$ the latter
one. Clearly, $|B_{0}^{\rm big}|=k$, and therefore

$d_{\rm TV}(\tau_{\rm start})=1-c\;\text{.}$ (7.9)

Letting $A_{1}$ be the subset of vertices sampled at time $\tau_{\rm start}+1$
to perform an update, we further define $A_{1}^{\star}\subset B_{0}^{\rm big}$
as the subset of vertices in $A_{1}$ having mass $k^{-1}$. Then,

$|A_{1}^{\star}|\overset{\rm d}{=}{\rm HyperGeo}(n,k,k)\;\text{.}$ (7.10)

Suppose that $|A_{1}^{\star}|=j$. Then, at time $\tau_{\rm start}+1$, there
are $k-j$ vertices with mass $k^{-1}$, $k$ vertices with mass $jk^{-2}$, while
the remaining vertices have mass zero. By concentration of hypergeometric
random variables we have (see, e.g., [Ser74]), for all $n$ large enough,

$\mathds{P}(||A_{1}^{\star}|-c|B^{\rm
big}_{0}||>k^{2/3})\leq\exp(-k^{1/4})\;\text{.}$ (7.11)

In other words, there exists a random variable $E_{1}\in\mathbb{R}$ satisfying

$|A_{1}^{\star}|=\frac{k}{n}|B_{0}^{\rm
big}|\left(1+E_{1}\right)=c^{2}n\left(1+E_{1}\right)\;\text{,}\;\;$ (7.12)

and, by (7.6),

$\mathds{P}(|E_{1}|>n^{-1/5})\leq p\coloneqq\exp(-k^{1/4})\;\text{.}$ (7.13)

Therefore, after the $(\tau_{\rm start}+1)$-th update, the vertices in $V$ can
be partitioned into three sets:

$\displaystyle\begin{aligned} B_{1}^{\rm big}&\coloneqq\\{x\in
V\mid\eta_{\tau_{\rm start}+1}(x)=k^{-1}\\}\;\text{,}\;\;\\\ B_{1}^{\rm
void}&\coloneqq\\{x\in V\mid\eta_{\tau_{\rm start}+1}(x)=0\\}\;\text{,}\;\;\\\
B_{1}^{\rm eq}&\coloneqq\\{x\in
V\mid\left(1-|E_{1}|\right)n^{-1}\leq\eta_{\tau_{\rm
start}+1}(x)\leq\left(1+|E_{1}|\right)n^{-1}\\}\;\text{,}\;\;\end{aligned}$
(7.14)

having sizes

$\displaystyle|B_{1}^{\rm big}|$
$\displaystyle=k-|A_{1}^{\star}|\in\big{[}\left(1-|E_{1}|\right)c(1-c)n\,,\,\left(1+|E_{1}|\right)c(1-c)n\big{]}\;\text{,}\;\;$
(7.15) $\displaystyle|B_{1}^{\rm eq}|$ $\displaystyle=k\;\text{.}$ (7.16)

Henceforth,

$|B_{1}^{\rm big}|(k^{-1}-n^{-1})\leq d_{\rm TV}(\tau_{\rm
start}+1)\leq|B_{1}^{\rm big}|(k^{-1}-n^{-1})+|B_{1}^{\rm
eq}|\frac{|E_{1}|}{n}\;\text{,}\;\;$ (7.17)

and, in conclusion, with probability at least $p$ (defined as in (7.13)),

$d_{\rm TV}(\tau_{\rm
start}+1)=(1+O(n^{-1/5}))(1-c)^{2}+O\big{(}n^{-1/5}\big{)}\;\text{.}$ (7.18)

We can now argue by induction. Let us fix some $t\geq 2$, and assume that at
time $t-1$, with probability at least $(1-p)^{t-1}$, we have

$\displaystyle|B_{t-1}^{\rm big}|$
$\displaystyle=(1+O(n^{-1/5}))^{t-1}c(1-c)^{t-1}n\;\text{,}\;\;$ (7.19)
$\displaystyle|B_{t-1}^{\rm eq}|$
$\displaystyle=(1+O(n^{-1/5}))^{t-1}\left(1-(1-c)^{t-1}\right)n\;\text{,}\;\;$
(7.20)

where we used a notation analogous to that in (7.14), that is,

$\displaystyle B_{t-1}^{\rm big}$ $\displaystyle\coloneqq\\{x\in
V\mid\eta_{\tau_{\rm start}+t-1}(x)=k^{-1}\\}$ (7.21) $\displaystyle
B_{t-1}^{\rm void}$ $\displaystyle\coloneqq\\{x\in V\mid\eta_{\tau_{\rm
start}+t-1}(x)=0\\}\;\text{,}\;\;$ (7.22) $\displaystyle B_{t-1}^{\rm eq}$
$\displaystyle\coloneqq V\setminus\\{B_{t-1}^{\rm big}\cup B_{t-1}^{\rm
void}\\}\;\text{.}$ (7.23)

Observe that this implies that, with probability at least $(1-p)^{t-1}$,

$d_{\rm TV}(\tau_{\rm
start}+t-1)=(1+O(n^{-1/5}))\,(1-c)^{t}+O(n^{-1/5})\;\text{.}$ (7.24)

Under this event at time $t-1$, when we update vertices in the random block
$A_{t}$, we get, with probability at least $1-p$ again by concentration of
hypergeometrics,

$\displaystyle|A_{t}^{\star}|$
$\displaystyle=\frac{k}{n}\,(1+O(n^{-1/5}))\,|B_{t-1}^{\rm
big}|=(1+O(n^{-1/5}))^{t}\,c^{2}(1-c)^{t-1}\,n\;\text{,}\;\;$ (7.25)
$\displaystyle|A_{t}^{\rm eq}|$
$\displaystyle=\frac{k}{n}\,(1+O(n^{-1/5}))\,|B_{t-1}^{\rm
eq}|=(1+O(n^{-1/5}))^{t}\,c(1-(1-c)^{t-1})\,n\;\text{.}$ (7.26)

Altogether, with probability at least $(1-p)^{t}$, each vertex in $A_{t}$ has
mass equal to

$(1+O(n^{-1/5}))^{t}\left[c^{2}(1-c)^{t-1}nk^{-1}+c(1-(1-c)^{t-1})\right]k^{-1}=(1+O(n^{-1/5}))^{t}\,n^{-1}\;\text{,}\;\;$
(7.27)

and, furthermore,

$\displaystyle|B_{t}^{\rm big}|$
$\displaystyle=(1+O(n^{-1/5}))^{t}\,[|B_{t-1}^{\rm
big}|-|A_{t}^{\star}|]=(1+O(n^{-1/5}))^{t}\,c(1-c)^{t}n\;\text{,}\;\;$ (7.28)
$\displaystyle|B_{t}^{\rm eq}|$
$\displaystyle=(1+O(n^{-1/5}))^{t}(|B_{t-1}^{\rm eq}|-|A_{t}^{\rm
eq}|+k)=(1+O(n^{-1/5}))^{t}\,(1-(1-c)^{t})\,n\;\text{.}$ (7.29)

Consequently, with probability at least $(1-p)^{t}$, we have

$d_{\rm TV}(\tau_{\rm
start}+t)=(1+O(n^{-1/5}))^{t}\,(1-c)^{t+1}+O\big{(}n^{-1/5}\big{)}\;\text{.}$
(7.30)

In conclusion, taking
$\bar{t}(\beta)=\lfloor\beta\frac{n}{k}\rfloor=\lfloor\beta c^{-1}\rfloor$ for
any $\beta>0$, if $c\not\to 0$, (7.30) yields

$d_{\rm TV}(\tau_{\rm
start}+\bar{t}(\beta))\sim(1-c)^{\bar{t}(\beta)+1}\;\text{,}\;\;$ (7.31)

and the proof is complete in this case. If $c\to 0$ (yet, satisfying (7.6),
thus, $c\gg n^{-1/5}$), we rather obtain

$\displaystyle d_{\rm TV}(\tau_{\rm start}+\bar{t}(\beta))\sim
e^{-\beta}\;\text{.}$

This concludes the proof of the proposition. ∎

###  7.2. Second regime in (7.4)

In this section, we consider $k=n^{\delta}$, for some sequence
$\delta=\delta_{n}\in(0,1)$ such that the second condition in (7.4) holds
true, that is,

$\delta\longrightarrow\bar{\delta}\in(0,5/6]\;\text{.}$ (7.32)

######  Proposition 7.3.

Letting $k=n^{\delta}$, under the assumption in (7.32), we have, for all
$\beta\geq 0$ and w.h.p.,

$\Pr\left({\rm Poi}(\beta)<\frac{1-\delta}{\delta}\right)\leq d_{\rm
TV}(\tau_{\rm start}+\lfloor\beta\tfrac{n}{k}\rfloor)\leq\Pr\left({\rm
Poi}(\beta)\leq\frac{1-\delta}{\delta}\right)\;\text{.}$ (7.33)

In particular, if $\bar{\delta}^{-1}\notin\mathbb{N}$, then lower and upper
bounds coincide, yielding, for all $\beta\geq 0$,

$d_{\rm TV}(\tau_{\rm start}+\lfloor\beta\tfrac{n}{k}\rfloor)-\Pr\left({\rm
Poi}(\beta)\leq\frac{1-\delta}{\delta}\right)\overset{\mathds{P}}{\longrightarrow}0\;\text{.}$
(7.34)

######  Remark 7.4.

For simplicity, we stated the convergence result in (7.34) for
$\bar{\delta}^{-1}\notin\mathbb{N}$. Nevertheless, analogous convergence
results hold also when $\bar{\delta}^{-1}\in\mathbb{N}$, provided that there
exists some $\varphi$ such that $\log\log(n)\ll\varphi\ll\log(n)$ and

$|j\delta-1|\gg\frac{\varphi}{\log(n)}\,,\qquad\forall j\in\mathbb{N}\,.$
(7.35)

Clearly, under this additional assumption, we have, for any $j\in\mathbb{N}$,
the following dichotomy

$\text{either}\qquad k^{-j}\ll\frac{e^{-\varphi}}{n}\qquad\text{or}\qquad
k^{-j}\gg\frac{e^{\varphi}}{n}\;\text{.}$ (7.36)

In particular, under (7.35), (7.34) holds if $\delta\uparrow\bar{\delta}$,
whereas $\delta\downarrow\bar{\delta}$ yields (7.34) with “$<$” in place of
“$\leq$”.

In cases where the condition (7.35) fails to hold, simulations suggest that
neither one of the bounds in Proposition (7.3) is sharp; see Figure 7.1 for
some simulations when $k=\sqrt{n}$, to be compared with Figure 7.2, which
considers an instance of the case $\bar{\delta}^{-1}\notin\mathbb{N}$.

Figure 7.1. We simulate the process with $n=10^{6}$ and $k=\sqrt{n}$, starting
at $\eta_{0}=\eta^{\rm start}$. We plot the empirical CDF of the entries of
$\eta_{t}$ restricted to the entries for which $\eta_{t}\leq\frac{5}{n}$, when
$t$ is the first time in which the sequence $d_{\rm TV}(t)$ assumes the values
$0.7,0.5,0.3,0.1,0.01$. The final plot is the behavior of the TV distance and
the bounds in Proposition 7.3.

Figure 7.2. Same as Figure 7.1, but with $k=\lfloor n^{0.7}\rfloor=15849$. In
this case, contrarily to the case $\varepsilon=1/2$ in Figure 7.1, the
empirical mass distribution on the scale $1/n$ is unimodal, having its bulk
around $1$.

We split the proof of the above proposition into lower and upper bounds in the
two subsequent subsections.

####  7.2.1. Proof of the lower bound in Proposition 7.3

For any $t\geq 0$, we employ the notation in Section 3.5 and call $w_{t}$ the
sub-probability measure on $V$ obtained by removing from $\eta_{t}$ all the
piles of size smaller than $e^{\varphi}/n$, for some prescribed
$\log\log(n)\ll\varphi\ll\log(n)$. Thanks to Lemma 3.8, it suffices to prove
the following lemma.

######  Lemma 7.5.

Fix $\beta>0$, $t=\bar{t}(\beta)\coloneqq\lfloor\beta\tfrac{n}{k}\rfloor$ and
consider the process starting at $\eta_{0}=\eta^{\rm start}$. Then,

$|w_{t}|-\Pr\left({\rm
Poi}(\beta)<\frac{1-\delta}{\delta}\right)\overset{\mathds{P}}{\longrightarrow}0\;\text{.}$
(7.37)

###### Proof.

We start by showing that

$\mathds{E}[|w_{t}|]-\Pr\left({\rm
Poi}(\beta)<\frac{1-\delta}{\delta}\right)\overset{\mathds{P}}{\longrightarrow}0\;\text{.}$
(7.38)

By specializing Lemma 3.1 to the particular case $Y\equiv k$, and recalling
that $\eta_{0}=\eta^{\rm start}$, we have

$\displaystyle\mathds{E}[|w_{t}|]=\mathds{P}\left(|\zeta_{t}(U)|>\frac{e^{\varphi}}{n}\right)$
$\displaystyle=\mathds{P}\left(k^{-T-1}>\frac{e^{\varphi}}{n}\right)=\mathds{P}\left(T<\frac{1-\delta}{\delta}+\frac{\varphi}{\log(k)}\right)\,,$

where $T\overset{\rm d}{=}{\rm Bin}(t,k/n)$. By Le Cam theorem, we have

$\|T-{\rm Poi}(\beta)\|_{\rm
TV}\leq\sum_{s=1}^{t}\frac{k^{2}}{n^{2}}\leq\beta\frac{k}{n}\longrightarrow
0\;\text{,}\;\;$ (7.39)

hence, being $\varphi\ll\log(k)$, (7.38) follows.

Using Chebyshev inequality, we conclude the proof of the lemma as soon as we
prove

$\mathds{E}[|w_{t}|^{2}]\leq\mathds{E}[|w_{t}|]^{2}+o(1)\;\text{.}$ (7.40)

The proof of this estimate follows exactly the same lines of arguments
employed in the proof of (6.8), with a single important difference: since here
we start from $\eta_{0}=\eta^{\rm start}$, then $\tau_{\rm sep}=0$ (cf.
(6.14)) with probability $1-\frac{1}{k}$; therefore, we can set $t_{\rm
sep}=0$ and $\theta=1$ in that proof. (Note that, with these choices, the
event $\mathcal{E}_{3}$ therein is irrelevant.) ∎

####  7.2.2. Proof of the upper bound in Proposition 7.3

Fix $\beta>0$, $t=\bar{t}(\beta)\coloneqq\lfloor\beta\tfrac{n}{k}\rfloor$, and
consider the process starting from $\eta_{0}=\eta^{\rm start}$. Define, for
$j\geq 1$, $\hat{\eta}^{(j)}$ as the restriction of $\eta_{t}$ to the piles
having size $k^{-j}$.

For any fixed $C\in\mathbb{N}$, arguing as in the proof of Lemma 7.5, and
taking a union bound, we get

$\max_{j\leq
C}\bigg{|}|\hat{\eta}^{(j)}|-p_{j-1}(\beta)\bigg{|}\overset{\mathds{P}}{\to}0\;\text{,}\;\;\quad\text{with}\
p_{j}(\gamma)\coloneqq\Pr({\rm Poi}(\beta)=j)\;\text{.}$ (7.41)

Fix some $\phi$ satisfying $\log\log(n)\ll\phi\ll\log(n)$, and define

$j_{\star}:=\max\left\\{j\in\mathbb{N}\mid
k^{-j}>\frac{e^{\varphi}}{n}\right\\}\;\text{.}$ (7.42)

Note that, for this choice of $\varphi$ and since
$\bar{\delta}^{-1}\notin\mathbb{N}$ by assumption, we have

$k^{-j}<\frac{e^{-\varphi}}{n}\;\text{,}\;\;\quad j>j_{\star}\;\text{.}$
(7.43)

Now fix any $j\in(j_{\star},C]$. We now aim at showing that: for any
$\varepsilon>0$,

$\lim_{n\to\infty}\mathds{P}\left(\exists x\in V\text{ s.t.
}{\hat{\eta}^{(j)}(x)}\geq\frac{(1+\varepsilon)p_{j-1}(\beta)}{n}\right)=0\;\text{.}$
(7.44)

By an application of the union bound and the generalized Markov inequality we
deduce that, for any $q\in\mathbb{N}$,

$\mathds{P}\left(\exists x\in V\text{ s.t.
}{\hat{\eta}^{(j)}(x)}\geq\frac{(1+\varepsilon)p_{j-1}(\beta)}{n}\right)\leq
n\times\frac{\max_{x\in
V}\mathds{E}\bigg{[}\big{(}{\hat{\eta}^{(j)}(x)}\big{)}^{q}\bigg{]}}{n^{-q}\times(1+\varepsilon)^{q}p_{j-1}(\gamma)^{q}}\,.$
(7.45)

The following lemma, which controls the high moments of $\hat{\eta}^{(j)}(x)$
for $j>j_{\star}$, is the key technical ingredient of our proof.

######  Lemma 7.6.

Fix $j>j_{\star}$, $q=\lfloor\log(n)^{2}\rfloor$, and $\varepsilon>0$. Then,
for all $n$ sufficiently large,

$\max_{x\in
V}\mathds{E}\bigg{[}\big{(}{\hat{\eta}^{(j)}(x)}\big{)}^{q}\bigg{]}\leq\left(\frac{(1+\tfrac{\varepsilon}{2})p_{j-1}(\gamma)}{n}\right)^{q}\;\text{.}$
(7.46)

Observe that (7.44) follows at once from (7.45) and (7.46). We postpone the
proof of Lemma 7.6 to the end of this section, and we now show how the upper
bound in Proposition 7.3 follows from (7.44).

Fix $\delta>0$. By the triangular inequality we have that, w.h.p., $d_{\rm
TV}(t)$ is bounded above by

$\displaystyle\sum_{j\geq
1}|\hat{\eta}^{(j)}|\left\|\frac{\hat{\eta}^{(j)}}{|\hat{\eta}^{(j)}|}-\pi\right\|_{\rm
TV}$ (7.47)
$\displaystyle\leq\sum_{j=1}^{j_{\star}}|\hat{\eta}^{(j)}|+\sum_{j=j_{\star}+1}^{C}|\hat{\eta}^{(j)}|\left\|\frac{\hat{\eta}^{(j)}}{|\hat{\eta}^{(j)}|}-\pi\right\|_{\rm
TV}+\sum_{j>C}|\hat{\eta}^{(j)}|$ (7.48)
$\displaystyle\leq\left(1+\varepsilon\right)\Pr\left({\rm
Poi}(\beta)\leq\frac{1-\delta}{\delta}\right)+\sum_{j=j_{\star}+1}^{C}|\hat{\eta}^{(j)}|\left\|\frac{\hat{\eta}^{(j)}}{|\hat{\eta}^{(j)}|}-\pi\right\|_{\rm
TV}+\Pr({\rm Poi}(\beta)>C)+\delta\;\text{,}\;\;$ (7.49)

where in the second line we bounded by $1$ the TV-distances associated to
$j\leq j_{\star}$ and $j>C$, whereas in the third one we used (7.41) and the
following identity

$\sum_{j=1}^{j_{\star}}p_{j-1}(\beta)=\Pr\left({\rm Poi}(\beta)\leq
j_{\star}-1\right)=\Pr\left({\rm
Poi}(\beta)\leq\frac{1-\delta}{\delta}\right)\;\text{,}\;\;$ (7.50)

which holds true in view of the definition of $j_{\star}$ in (7.42) (recall
$k=n^{\delta}$). Furthermore, for any $j>j_{\star}$, by (7.41) and Lemma 7.6,
we obtain, w.h.p.,

$\displaystyle|\hat{\eta}^{(j)}|\left\|\frac{\hat{\eta}^{(j)}}{|\hat{\eta}^{(j)}|}-\pi\right\|_{\rm
TV}$ $\displaystyle=\sum_{x\in
V}\left[\hat{\eta}^{(j)}(x)-\frac{|\hat{\eta}^{(j)}|}{n}\right]_{+}$ (7.51)
$\displaystyle\leq\sum_{x\in
V}\left[\hat{\eta}^{(j)}(x)-\frac{(1-\varepsilon)p_{j-1}(\beta)}{n}\right]_{+}$
(7.52) $\displaystyle\leq\sum_{x\in
V}\left[\left(1+\frac{\varepsilon}{2}\right)\frac{p_{j-1}(\beta)}{n}-\frac{(1-\varepsilon)p_{j-1}(\beta)}{n}\right]_{+}=\frac{3}{2}\varepsilon
p_{j-1}(\beta)\;\text{.}$ (7.53)

Plugging this estimate into the right-hand side of (7.47), we get, for any
$\varepsilon\in(0,1)$ and $C\in\mathbb{N}$, w.h.p.,

$\begin{split}d_{\rm TV}(t)&\leq\left(1+\varepsilon\right)\Pr\left({\rm
Poi}(\beta)\leq\frac{1-\delta}{\delta}\right)+\frac{3}{2}\varepsilon+\Pr({\rm
Poi}(\beta)>C)+\varepsilon\;\text{,}\;\;\end{split}$ (7.54)

and the desired result follows by taking $C\to\infty$ and $\varepsilon\to 0$.

We are left with the proof of Lemma 7.6.

###### Proof of Lemma 7.6.

Recall that $\eta_{0}=\eta^{\rm start}$, $\beta>0$,
$t=\bar{t}(\beta)\coloneqq\lfloor\beta\frac{n}{k}\rfloor$,
$q=\lfloor\log(n)^{2}\rfloor$, and $j>j_{\star}$. Consider the collection of
random chunks $U_{1},\dots,U_{q}$. For a given $x\in V$, define the events

$\mathcal{J}_{i}=\\{|\zeta_{t}(U_{i})|=k^{-j}\\}\;\text{,}\;\;\qquad\mathcal{X}_{i}=\\{e_{t}(U_{i})=x\\}\;\text{,}\;\;\qquad
i\leq q\;\text{.}$ (7.55)

Note that, quenching the block dynamics up to time $t$, we write

$\big{(}{\hat{\eta}^{(j)}(x)}\big{)}^{q}={\mathsf{P}_{U_{1},\dots,U_{q}}\left(\bigcap_{i\leq
q}\mathcal{X}_{i}\cap\mathcal{J}_{i}\right)}\;\text{,}\;\;$ (7.56)

and taking expectations on both sides yields

$\displaystyle\mathds{E}$
$\displaystyle\left[({\hat{\eta}^{(j)}(x)})^{q}\right]=\mathds{P}\left(\bigcap_{i\leq
q}\left(\mathcal{X}_{i}\cap\mathcal{J}_{i}\right)\right)$ (7.57)
$\displaystyle=\mathds{P}\left(\mathcal{J}_{1}\right)\mathds{P}\left(\mathcal{X}_{1}\mid\mathcal{J}_{1}\right)\prod_{i=1}^{q-1}\mathds{P}\big{(}\mathcal{J}_{i+1}\mid\cap_{\ell\leq
i}(\mathcal{J}_{\ell}\cap\mathcal{X}_{\ell})\big{)}\mathds{P}\big{(}\mathcal{X}_{i+1}\mid\mathcal{J}_{i+1}\cap_{\ell\leq
i}(\mathcal{J}_{\ell}\cap\mathcal{X}_{\ell})\big{)}\;\text{.}$ (7.58)

We start by bounding the first probability on the right-hand side of (7.57).
By the same argument employed to show (7.38)

$\mathds{P}(\mathcal{J}_{1})\sim p_{j-1}(\beta)\,.$ (7.59)

For the second probability on the right-hand side of (7.57) we claim that,
uniformly in $x\in V$, $t\geq 0$ and $j>j_{\star}$,

$\mathds{P}(\mathcal{X}_{1}\mid\mathcal{J}_{1})\leq(1+o(1))\,\frac{1}{n}\;\text{.}$
(7.60)

Indeed, letting, for all $h=0,\ldots,j-1$, $\mathcal{Y}_{1}(h)$ be the event
that the last arrival at $x$ occurs at the $h$-th jump of $U_{1}$ (here,
$\mathcal{Y}_{1}(0)$ represents the event that $U_{1}$ starts at $x\in V$ and
never leaves this vertex for the subsequent $j$ jumps). Then,

$\displaystyle\mathds{P}(\mathcal{X}_{1}\mid\mathcal{J}_{1})$
$\displaystyle=\sum_{h=0}^{j-1}\mathds{P}(\mathcal{X}_{1}\cap\mathcal{Y}_{1}(h)\mid\mathcal{J}_{1})$
(7.61) $\displaystyle={\bf 1}_{\eta^{\rm
start}(x)>0}\,k^{-j}+\sum_{h=1}^{j-1}\mathds{P}(\mathcal{X}_{1}\cap\mathcal{Y}_{1}(h)\mid\mathcal{J}_{1})$
(7.62) $\displaystyle\leq{\bf 1}_{\eta^{\rm
start}(x)>0}\,k^{-j}+\sum_{h=1}^{j-1}\frac{k-1}{n-1}\frac{1}{k}k^{-(j-1-h)}\;\text{,}\;\;$
(7.63)

where the second identity follows because the probability of starting at $x$
is $\frac{1}{k}$, and never leaving it for $j-1$ jumps is $k^{-(j-1)}$,
whereas the second inequality used that the probability of jumping to $x$
starting from somewhere else equals $\frac{k-1}{n-1}\frac{1}{k}$. Since we
chose $j>j_{\star}$ and assumed that $\varphi\ll\log(n)$, we have
$k^{-j}\ll\frac{1}{n}$, ensuring the claim in (7.60).

Now we aim at proving that: uniformly, for all $i<q$,

$\mathds{P}\big{(}\mathcal{J}_{i+1}\mid\cap_{\ell\leq
i}(\mathcal{J}_{\ell}\cap\mathcal{X}_{\ell})\big{)}\leq
p_{j-1}(\beta)+o(1)\;\text{.}$ (7.64)

The idea is the following: consider the event

$\mathcal{Q}_{i+1}=\\{\nexists(s,\ell)\in\\{0,\dots,t\\}\times\\{1,\dots,i\\}\
\text{s.t.}\ e_{s}(U_{i+1}),e_{s}(U_{\ell})\in A_{s}\\}\;\text{,}\;\;$ (7.65)

and split

$\mathds{P}\big{(}\mathcal{J}_{i+1}\mid\cap_{\ell\leq
i}(\mathcal{J}_{\ell}\cap\mathcal{X}_{\ell})\big{)}\leq\mathds{P}\big{(}\mathcal{Q}_{i+1}^{c}\mid\cap_{\ell\leq
i}(\mathcal{J}_{\ell}\cap\mathcal{X}_{\ell})\big{)}+\mathds{P}\big{(}\mathcal{J}_{i+1}\cap\mathcal{Q}_{i+1}\mid\cap_{\ell\leq
i}(\mathcal{J}_{\ell}\cap\mathcal{X}_{\ell})\big{)}\;\text{.}$ (7.66)

In words:

  * •

Either the $(i+1)$-th chunk ever jump together with some other chunk among
$U_{1},\dots,U_{i}$: this event has probability at most

$\frac{i}{k}+i\left(j-1\right)\frac{k-1}{n-i}\leq\frac{q}{k}+\left(j-1\right)q\,\frac{k}{n-q}\;\text{.}$
(7.67)

Indeed, $\frac{i}{k}$ estimates the probability that $U_{i+1}$ starts at the
same location of either one of $U_{1},\dots,U_{i}$; provided that $U_{i+1}$
does not start at any of the initial location of $U_{1},\dots,U_{i}$, the
second summand accounts for the probability that there exist a chunk among
$U_{1},\dots,U_{i}$ and an update of such a chunk (which are exactly $j-1$ in
our conditional probability space) in which also $U_{i+1}$ is involved.

  * •

Or, under $\mathcal{Q}_{i+1}$, $U_{i+1}$ does exactly $j-1$ jumps. Call
$\bar{p}$ the probability of this event, which can be bounded uniformly in
$i<q$ as follows

$\bar{p}\leq\max_{a\in\\{0,\dots,q(j-1)\\}}\max_{b\in\\{0,\dots,q\\}}\mathds{P}\left({\rm
Bin}(t-a,\tfrac{k}{n-b})=j-1\right)\,.$ (7.68)

Indeed, in the conditional probability space and under $\mathcal{Q}_{i+1}$, at
each time $s\leq t$ the probability of sampling $e_{s}(U_{i+1})$ is either
zero (if any among $U_{1},\dots,U_{i}$ is involved in the update at time $s$)
or bounded above by $\frac{k}{n-(i-1)}$ (if none among $U_{1},\dots,U_{i}$ is
involved in the update at time $s$). By the Poisson approximation of
Binomials,

$\max_{a\in\\{0,\dots,q(j-1)\\}}\max_{b\in\\{0,\dots,q\\}}\left|\Pr\big{(}{\rm
Bin}(t-a,\tfrac{k}{n-b})=j-1\big{)}-\Pr\big{(}{\rm
Poi}(\beta)=j-1\big{)}\right|\to 0\,.$ (7.69)

Therefore,

$\bar{p}\leq p_{j-1}(\beta)+o(1)\;\text{.}$ (7.70)

We are left with considering the probability

$\mathds{P}\big{(}\mathcal{X}_{i+1}\mid\mathcal{J}_{i+1}\cap_{\ell\leq
i}(\mathcal{J}_{\ell}\cap\mathcal{X}_{\ell})\big{)}\;\text{,}\;\;\qquad
i\in\\{1,\dots,q-1\\}\;\text{.}$ (7.71)

To ease the understanding, we start by considering the case $i=1$. For a fixed
realization of the trajectory of $U_{1}$ which satisfies
$\mathcal{J}_{1}\cap\mathcal{X}_{1}$ and conditionally on $\mathcal{J}_{2}$,
the event that $\mathcal{X}_{2}$ can occur in three different ways:

  1. (i)

either $U_{1}$ and $U_{2}$ are at the same vertex at all times;

  2. (ii)

or $U_{2}$ and $U_{1}$ walk together for a number of jumps $r\in[0,j-1)$, the
$r$-th jump put them on different vertices, and then they meet at the $s$-th
jump of both $U_{1}$ and $U_{2}$, $s\in(r,j-1]$ and they continue their
journey together up to reaching $x$ at their $(j-1)$-th jump;

  3. (iii)

or the two chunks meet and separate more than once.

Clearly the conditional probability of the event in (i) can be bounded from
above by

$k^{-j}\ll\frac{e^{-\varphi}}{n}\ll\frac{1}{n}\;\text{,}\;\;$ (7.72)

where we simply used (7.42), $j>j_{\star}$, and (7.36). Alternatively, called
$\mathcal{G}_{2}$ the event in (ii), we have

$\displaystyle\mathds{P}(\mathcal{G}_{2}\mid\mathcal{J}_{1}\cap\mathcal{X}_{1}\cap\mathcal{J}_{2})\leq\sum_{s=1}^{j-1}\frac{k-1}{n-1}\times\frac{1}{k}\times
k^{-j+1+s}\,,$ (7.73)

Indeed, given that they are on the same vertex, the probability they remain on
the same vertex after a jump is $k^{-1}$. On the other hand, if they are on
different vertices, the probability they meet at the next jump of $U_{1}$
(which is measurable) is $\frac{k-1}{n-1}\times\frac{1}{k}$. Therefore

$\displaystyle\mathds{P}(\mathcal{G}_{2}\mid\mathcal{J}_{1}\cap\mathcal{X}_{1}\cap\mathcal{J}_{2})$
$\displaystyle\leq\sum_{s=1}^{j-1}\frac{k-1}{n-1}\times\frac{1}{k}\times
k^{-j+1+s}$ (7.74)
$\displaystyle\sim\frac{1}{n}\sum_{s=1}^{j-1}k^{-j+1+s}\sim\frac{1}{n}\,.$
(7.75)

Finally, the conditional probability of the event in (iii) can be immediately
bounded by

$\sum_{a=2}^{j/2}\left[\frac{k-1}{n-1}\times\frac{1}{k}\right]^{a}\lesssim
n^{-2}\;\text{.}$ (7.76)

In conclusion,

$\mathds{P}(\mathcal{X}_{2}\mid\mathcal{J}_{1}\cap\mathcal{X}_{1}\cap\mathcal{J}_{2})\leq(1+o(1))\frac{1}{n}\,.$
(7.77)

We now argue iteratively. Fixed $i\geq 2$ and a realization of the
trajectories of $U_{1},\dots,U_{i}$ which satisfies $\bigcap_{\ell\leq
i}\mathcal{J}_{\ell}\cap\mathcal{X}_{\ell}$. Conditionally on these
trajectories and $\mathcal{J}_{i+1}$, the event $\mathcal{X}_{i+1}$ can occur
in either one of the following three ways:

  1. (i)

for all times $t^{\prime}\leq t$, we have

$e_{t^{\prime}}(U_{i+1})\in F_{t^{\prime}}\coloneqq\\{y\in V\mid
e_{t^{\prime}}(U_{\ell})=y\text{ for some }\ell\leq i\\}\,;$

  2. (ii)

$U_{i+1}$ walks together with at least one of the other chunks (possibly not
always the same) for a number of jumps $r\in[0,j-1)$, $U_{i+1}$ departs from
all the other chunks at the $r$-th jump, and then it meets some
$U_{\ell^{\prime}}$ at the their $s$-th jump, for some $s\in(r,j-1]$, and they
continue their journey together up to reaching $x$ at their $(j-1)$-th jump;

  3. (iii)

There exists times $0\leq t^{(1)}<t^{(2)}<t^{(3)}<t^{(4)}\leq t$ such that
$e_{t^{(1)}}(U_{i+1})\not\in F_{t^{(1)}}$, $e_{t^{(2)}}(U_{i+1})\in
F_{t^{(2)}}$, $e_{t^{(3)}}(U_{i+1})\not\in F_{t^{(3)}}$ and
$e_{t^{(4)}}(U_{i+1})\in F_{t^{(4)}}$.

Again, the conditional probabilities of the event in (iii) is easy to bound by

$\sum_{a=2}^{j/2}\left[i\times\frac{k-1}{n-i}\times\frac{1}{k}\right]^{a}\ll
n^{-1}\,.$ (7.78)

Similarly, the probability of the event in (i) can be bounded from above by

$\left(\frac{q}{k}\right)^{j}\ll\frac{q^{j}e^{-\varphi}}{n}\ll\frac{1}{n}\,$
(7.79)

where the asymptotic inequality follows by the choice $\varphi\gg\log\log(n)$,
$q=\lfloor\log(n)^{2}\rfloor$, and $j>j_{\star}$ is constant (cf. (7.42) and
(7.36)). Concerning the conditional probability of the event in (ii), it can
be bounded by

$\displaystyle\mathds{P}\left(\mathcal{G}_{i+1}\,\bigg{\rvert}\,\mathcal{J}_{i+1}\cap\bigg{(}\bigcap_{\ell\leq
i}\mathcal{J}_{\ell}\cap\mathcal{X}_{\ell}\bigg{)}\right)$ (7.80)
$\displaystyle\qquad\leq\sum_{r=0}^{j-2}(\mathds{1}_{r>0}i+1)k^{-r}\sum_{s=r+1}^{j-1}(\mathds{1}_{s<j-1}i+1)\frac{k-1}{n-i}\times\frac{1}{k}\times
k^{-j+1+s}$ (7.81)
$\displaystyle\qquad\sim\frac{1}{n-i}\sum_{r=0}^{j-2}k^{-r}(\mathds{1}_{r>0}i+1)\sum_{s=r+1}^{j-1}k^{-j+1+s}(\mathds{1}_{s<j-1}i+1)\sim\frac{1}{n}\;\text{,}\;\;$
(7.82)

where we only used $i\leq q=\lfloor\log(n)^{2}\rfloor$. This ends the proof of
the lemma. ∎

##  8\. Sharpness of the conditions in Theorems 2.7 and 2.10

In this section, we discuss a particularly simple parametric class of block-
size distributions of the form

$p_{X}(2)=1-\frac{a}{n}\;\text{,}\;\;\qquad
p_{X}(n)=\frac{a}{n}\;\text{,}\;\;$ (8.1)

for some positive sequence $a=a_{n}$, which plays the role of a real
parameter. This parameter, running over $[0,n]$, interpolates between the two
following extreme cases: (i) when all the blocks have size $2$ (i.e., $a=0$),
thus, there is cutoff with (standard) Gaussian profile; (ii) when the blocks
all have size $n$ (i.e., $a=n$), so that a single update suffices to reach
perfect equilibrium. In particular, case (i) coincides with the model in
[CDSZ22].

Since we are interested in the regime of small $a$, we assume $a\ll 1$ all
throughout this section. Under this condition, we have

$\displaystyle\mathds{E}[X]$ $\displaystyle\sim 2$ (8.2)
$\displaystyle\mathds{E}[X\log X]$ $\displaystyle\sim 2\log 2+a\log n$ (8.3)
$\displaystyle\mathds{E}[X(\log X)^{2}]$ $\displaystyle\sim 2(\log
2)^{2}+a(\log n)^{2}\;\text{,}\;\;$ (8.4)

and, thus,

$\mu\sim\log 2+\frac{a}{2}\log
n\;\text{,}\;\;\qquad\sigma^{2}\sim\frac{a}{4}(\log n)^{2}\;\text{.}$ (8.5)

As a consequence, the entropic product condition in (2.18) is satisfied if and
only $a\ll 1$, whereas condition (2.20) is verified if and only if $a\ll(\log
n)^{-1}$. Finally, note that condition (2.26) holds true anytime $a\ll(\log
n)^{-1}$.

We analyze this simple example with two distinct scopes:

  * •

Section 8.1. We examine the robustness of the cutoff phenomenon. Indeed, our
process corresponds to the regular block-size model in [CDSZ22], but with the
modification that, at any time and independently of everything else, there is
a small probability that the system immediately reaches equilibrium. We show
that a mixing trichotomy (see the dedicated section below for more details)
takes place depending on the scaling of $a$, and comment on the universality
of this behavior.

  * •

Section 8.2. We investigate the sharpness of Theorem 2.10 by analyzing the
regime $(\log n)^{-2}\lesssim a\ll(\log n)^{-1}$. This example shows that,
even if (2.18) and (2.20) are in force, the convergence in (2.25) might fail
in absence of (2.24) or, equivalently, (2.26) (see Remark 2.11).

###  8.1. Cutoff, half-cutoff, and metastability: a trichotomy

Consider the example in (8.1). Depending on whether $a$ is much smaller than,
larger than, or of the same order as $(\log n)^{-1}$, we observe three
different behaviors:

_Cutoff._ As already observed above, if $a\ll\log(n)^{-1}$, then Theorem 2.10
applies. In particular, we have cutoff at $\frac{n\log n}{2\log 2}$ with a
window of size $n\sqrt{\log n}$ and, since $\varrho=\frac{\sigma}{\mu}\ll 1$,
with a standard Gaussian profile.

_Metastability._ If $(\log n)^{-1}\ll a\ll 1$, although the entropic product
condition (2.18) holds, the condition (2.20) fails in this context. Actually,
it is not difficult to check that even the weaker WLLN in (2.19) does not
hold; therefore, cutoff as in Theorem 2.7 does not occur.

In this case, the random sequence $t\mapsto d_{\rm TV}(t)$ shows a “cutoff at
a random time”, on the scale $t_{\rm ent}\sim\frac{n}{a}\ll n\log n$. Indeed,
w.h.p., the sequence $t\mapsto d_{\rm TV}(t)$ will go from being almost one to
be exactly zero in a single random step, coinciding with the random time

$\tau\coloneqq\\{t\geq 1\mid X_{t}=n\\}\;\text{.}$ (8.6)

which is geometrically distributed with mean $n/a$. Since this value coincides
with the mixing timescale $t_{\rm ent}\sim n/a$, the sequence
$t\mapsto\mathds{E}[d_{\rm TV}(t)]$ does not exhibit cutoff. Furthermore,
passing to the expected distance-to-equilibrium, we observe an exponential
decay: for every $s\geq 0$, $\mathds{E}[d_{\rm TV}(st_{\rm ent})]\sim e^{-s}$.

This is the clear signature of a metastable behavior: the system goes to
equilibrium because of the realization of a single event occurring at a random
exponential time. Furthermore, this example shows that the entropic product
condition (2.18) alone does not suffice to imply cutoff.

_Half-cutoff._ In the intermediate regime $a=c(\log n)^{-1}$, $c>0$, the
sequence $t\mapsto d_{\rm TV}(t)$ exhibits cutoff at a random point on the
scale $n\log n$. However, since $t_{\rm ent}=\frac{n\log n}{2\log 2+c}\asymp
n\log n$, such a random time is constrained to be at most $t_{\rm
CDSZ}=\frac{n\log n}{2\log 2}$, the cutoff time for the $2$-block model in
[CDSZ22]. Indeed, under the event $\tau>(1+\varepsilon)t_{\rm CDSZ}$ (which
has probability $e^{-(1+\varepsilon)\frac{c}{2\log 2}}$), the sequence $d_{\rm
TV}(t)$ exhibits cutoff at $t_{\rm CDSZ}$. On the other hand, for all
$s\in(0,1)$ and $\delta>0$,

$\mathds{P}\big{(}d_{\rm TV}(st_{\rm CDSZ})>1-\delta\big{)}\sim
e^{-s\,\frac{c}{2\log 2}}\;\text{,}\;\;$ (8.7)

and therefore, for any sequence $\varepsilon=\varepsilon_{n}\to 0$
sufficiently slow, we have

$\mathds{P}\big{(}d_{\rm TV}((1-\varepsilon)t_{\rm CDSZ})>1-\delta\,,\,d_{\rm
TV}((1+\varepsilon)t_{\rm CDSZ})<\delta\big{)}\sim e^{-\frac{c}{2\log
2}}\;\text{.}$

We conclude that, for any fixed $s\neq 1$,

$\mathds{E}[d_{\rm TV}(st_{\rm CDSZ})]\longrightarrow{\bf
1}_{s<1}e^{-s\,\frac{c}{2\log 2}}\;\text{.}$ (8.8)

Such a trichotomy cutoff–half-cutoff–metastability is not a peculiar feature
of this model, only. Indeed, several other parametric models (see, e.g.,
[CQ21a, CQ21b, AGHH19, AGHHN22]), have been shown to exhibit the very same
behavior. In fact, when considering a certain model exhibiting cutoff (such as
the case $X=2$ a.s.) and a parametric perturbation of the model which allows
the system to reach equilibrium as consequence of the realization of a certain
event which occurs at a random exponential time (such as the event $X=n$, in
our case), one should expect the existence of a critical scale for the
perturbation parameter in which the two effects (cutoff vs. exponential decay)
coexist, giving rise to a _half-cutoff_ as in (8.8).

###  8.2. The role of condition (2.26) in Theorem 2.10

Consider again the case $a\ll(\log n)^{-1}$. Under this condition, the
resulting Block Average process can be coupled, w.h.p., to the model with
$a=0$ up to times $t\gg t_{\rm ent}=\frac{n\log(n)}{2\log(2)}$. As a
consequence, both models exhibit cutoff at $t_{\rm ent}$, with cutoff window
and standard Gaussian profile as predicted for the model in [CDSZ22], i.e.,
(8.1) with $a=0$. This complete cutoff phenomenology does not always
correspond, however, to the one that Theorems 2.8 and 2.10 would indicate.

Indeed, choosing, e.g., $a=\log(n)^{-1-\alpha}$ for some $\alpha\in(0,1)$ in
Theorem 2.8 would estimate the cutoff window by

$t_{\rm w}\sim\left(1+\frac{\sigma}{\mu}\right)\sqrt{\frac{\log
n}{\mu}}\asymp(\log n)^{1-\frac{\alpha}{2}}\;\text{,}\;\;$ (8.9)

which is much larger than $\sqrt{\log n}$, the actual size of the cutoff
window in [CDSZ22]. What goes wrong in Theorem 2.10 is the validity of (2.24)
or, equivalently, (2.26). In this sense, conditions (2.18) and (2.20) without
(2.24) do not suffice to determine the cutoff profile.

## Appendix A

For completeness, here we collect some elementary computations from Section
2.2.

###  A.1. Duality in (2.6)

For any $x\in V$ and $\eta=\eta_{0}\in\Delta$, we have

$\displaystyle\mathds{E}[\eta_{1}(x)]=\mathds{E}[\varPsi_{A}(\eta)(x)]=\sum_{k=2}^{n}\frac{p_{X}(k)}{\binom{n}{k}}\sum_{|B|=k}\varPsi_{B}\eta(x)$
(A.1)
$\displaystyle=\sum_{k=2}^{n}\frac{p_{X}(k)}{\binom{n}{k}}\sum_{|B|=k}{\bf
1}_{B}(x)\left(\frac{1}{k}\sum_{y\in
B}\eta(y)\right)+\eta(x)\sum_{k=2}^{n}\frac{p_{X}(k)}{\binom{n}{k}}\sum_{|B|=k}{\bf
1}_{B^{c}}(x)$ (A.2)
$\displaystyle=\sum_{k=2}^{n}\frac{p_{X}(k)}{\binom{n}{k}}\sum_{|B|=k}{\bf
1}_{B}(x)\left(\frac{1}{k}\sum_{y:y\neq x}{\bf
1}_{B}(y)\,\eta(y)+\frac{1}{k}\,\eta(x)\right)+\eta(x)\sum_{k=2}^{n}\frac{p_{X}(k)}{\binom{n}{k}}\sum_{|B|=k}{\bf
1}_{B^{c}}(x)$ (A.3) $\displaystyle=\sum_{y:y\neq
x}\eta(y)\sum_{k=2}^{n}\frac{p_{X}(k)}{\binom{n}{k}k}\sum_{|B|=k}{\bf
1}_{B}(x){\bf
1}_{B}(y)+\eta(x)\sum_{k=2}^{n}\frac{p_{X}(k)}{\binom{n}{k}}\sum_{|B|=k}\left(\frac{1}{k}{\bf
1}_{B}(x)+{\bf 1}_{B^{c}}(x)\right)$ (A.4) $\displaystyle=\sum_{y:y\neq
x}\eta(y)\sum_{k=2}^{n}p_{X}(x)\frac{\binom{n-2}{k-2}}{\binom{n}{k}k}+\eta(x)\sum_{k=2}^{n}p_{X}(k)\left(\frac{\binom{n-1}{k-1}}{\binom{n}{k}k}+\frac{\binom{n-1}{k}}{\binom{n}{k}}\right)$
(A.5) $\displaystyle=\sum_{y\in V:\,y\neq
x}\eta(y)\sum_{k=2}^{n}p_{X}(k)\left(\frac{k-1}{n(n-1)}\right)+\eta(x)\sum_{k=2}^{n}p_{X}(k)\left(\frac{1}{n}+1-\frac{k}{n}\right)$
(A.6) $\displaystyle=\frac{\mathds{E}[X]-1}{n(n-1)}\sum_{y\in V:\,y\neq
x}\eta(y)+\left(1-\frac{\mathds{E}[X]-1}{n}\right)\eta(x)\ .$ (A.7)

The right-hand side above indeed coincides with

$\sum_{y\in V}\eta(y)\,P_{\rm RW}(y,x)=\sum_{y\in V}P_{\rm
RW}(x,y)\,\eta(y)\;\text{.}$ (A.8)

###  A.2. Proof of Proposition 2.1

Note that, for every $B\subset V$, we have

$\displaystyle\bigg{\|}\frac{\varPsi_{B}\eta}{\pi}\bigg{\|}_{2}^{2}-\bigg{\|}\frac{\eta}{\pi}\bigg{\|}_{2}^{2}$
$\displaystyle=\bigg{\|}{\bf
1}_{B}\frac{\varPsi_{B}\eta}{\pi}\bigg{\|}_{2}^{2}-\bigg{\|}{\bf
1}_{B}\frac{\eta}{\pi}\bigg{\|}_{2}^{2}$ (A.9)
$\displaystyle=\frac{\eta(B)^{2}}{\pi(B)}-\bigg{\|}{\bf
1}_{B}\frac{\eta}{\pi}\bigg{\|}_{2}^{2}$ (A.10) $\displaystyle=n\sum_{x\in
B}\eta(x)\,\big{(}\varPsi_{B}\eta(x)-\eta(x)\big{)}$ (A.11)
$\displaystyle=\frac{n}{|B|}\sum_{x,y\in
B}\eta(x)\,\big{(}\eta(y)-\eta(x)\big{)}\ .$ (A.12)

We further get

$\displaystyle\mathds{E}\bigg{[}\bigg{\|}\frac{\eta_{1}}{\pi}-1\bigg{\|}_{2}^{2}\bigg{]}-\bigg{\|}\frac{\eta}{\pi}-1\bigg{\|}_{2}^{2}$
(A.13)
$\displaystyle=\sum_{k=2}^{n}p_{X}(k)\,\frac{1}{\binom{n}{k}}\sum_{|B|=k}\bigg{(}\bigg{\|}\frac{\varPsi_{B}\eta}{\pi}\bigg{\|}_{2}^{2}-\bigg{\|}\frac{\eta}{\pi}\bigg{\|}_{2}^{2}\bigg{)}$
(A.14)
$\displaystyle=\sum_{k=2}^{n}p_{X}(k)\,\frac{1}{\binom{n}{k}}\sum_{|B|=k}\frac{n}{k}\sum_{x,y\in
B}\eta(x)\,\big{(}\eta(y)-\eta(x)\big{)}$ (A.15) $\displaystyle=\sum_{x,y\in
V}\sum_{k=2}^{n}p_{X}(k)\,\frac{1}{\binom{n-1}{k-1}}\sum_{|B|=k}{\bf
1}_{B}(x){\bf 1}_{B}(y)\,\eta(x)\,\big{(}\eta(y)-\eta(x)\big{)}$ (A.16)
$\displaystyle=\sum_{\begin{subarray}{c}x,y\in V\\\ x\neq
y\end{subarray}}\eta(x)\,\big{(}\eta(y)-\eta(x)\big{)}\sum_{k=2}^{n}p_{X}(k)\,\frac{1}{\binom{n-1}{k-1}}\sum_{|B|=k}{\bf
1}_{B}(x){\bf 1}_{B}(y)$ (A.17) $\displaystyle=\sum_{x,y\in
V}\eta(x)\,\big{(}\eta(y)-\eta(x)\big{)}\sum_{k=2}^{n}p_{X}(k)\,\frac{\binom{n-2}{k-2}}{\binom{n-1}{k-1}}$
(A.18) $\displaystyle=\frac{\mathds{E}[X]-1}{n-1}\sum_{x,y\in
V}\eta(x)\,\big{(}\eta(y)-\eta(x)\big{)}$ (A.19)
$\displaystyle=-\frac{1}{t_{\rm
rel}}\,\bigg{\|}\frac{\eta}{\pi}-1\bigg{\|}_{2}^{2}\;\text{,}\;\;$ (A.20)

where for the last identity we used the definition in (2.7). Hence, we obtain

$\mathds{E}\left[\bigg{\|}\frac{\eta_{1}}{\pi}-1\bigg{\|}_{2}^{2}\right]=\bigg{(}1-\frac{1}{t_{\rm