# Diameters of Symmetric and Lifted Simple Exclusion Models

Xusheng Zhang<fnref n="1" /> Ⓒ · Werner Krauth<fnref n="2" />,<fnref n="3" />

Received: 4 December 2023 / Accepted: 23 July 2024 / Published online: 13 August 2024
© The Author(s) 2024

## Abstract

We determine diameters of Markov chains describing one-dimensional N-particle models with an exclusion interaction, namely the symmetric simple exclusion process (SSEP) and one of its non-reversible liftings, the lifted totally asymmetric simple exclusion process (TASEP). The diameters provide lower bounds for the mixing times, and we discuss the implications of our findings for the analysis of these models.

**Keywords** Markov chains · Symmetric simple exclusion process (SSEP) · Totally asymmetric simple exclusion process (TASEP) · Non-reversibility · Monte Carlo algorithms

## 1 Exclusion Models

Arguably the simplest models for gases of interacting particles are the lattice exclusion models [1, 2]. One-dimensional exclusion models describe N hard-sphere particles moving on a one-dimensional lattice with L sites. The original model is the symmetric simple exclusion process (SSEP) [3], which implements a discrete Markov chain based on the Metropolis algorithm. A configuration $x = \{x_1, x_2, \dots, x_N\}$ in the sample space $\Omega^{SSEP}$ is an ordered N-tuple with $x_1 < x_2 < \dots < x_N$ of the positions of the N particles, which are indistinguishable. In the SSEP, a single move, from time t to time t + 1, first samples uniformly at random an active particle i that attempts to move, and then proposes, with equal probability, a forward or a backward move. If this move would violate the exclusion condition, it is rejected:

$$ \underbrace{\left( \left| \bullet \right| \left| \bullet \right| \left| \bullet \right| \left| \bullet \right| \right)}_{x^{(t)} \in \Omega^{SSEP}} \rightarrow \underbrace{\left( \left| \bullet \right| \left| \bullet \right| \left| \bullet \right| \left| \bullet \right| \right)}_{\text{choice of active } i} \rightarrow \underbrace{\left( \left| \bullet \right| \left| \bullet \right| \left| \bullet \right| \left| \bullet \right| \right)}_{x^{(t+1)} \in \Omega^{SSEP}} \quad \left\{ \begin{array}{l} p = \frac{1}{2} \\ p = \frac{1}{2} \end{array} \right. \quad (1) $$

Communicated by Gregory Schehr.

<figure><img src="image_1.png" /></figure>

Xusheng Zhang
xushengz@psu.edu

Werner Krauth
werner.krauth@ens.fr

<footnote n="1">¹ Department of Computer Science and Engineering, Pennsylvania State University, W342 Westgate Building, Penn State, University Park, PA 16802, USA</footnote>

<footnote n="2">² Laboratoire de Physique de l'Ecole normale supérieure, ENS, Université PSL, CNRS, Sorbonne Université, Université de Paris Cité, 24 rue Lhomond, 75005 Paris, France</footnote>

<footnote n="3">³ Rudolf Peierls Centre for Theoretical Physics, University of Oxford, Oxford OX1 3PU, UK</footnote>
The SSEP is well-defined both for periodic and hard-wall boundary conditions:

* In hard-wall boundary conditions, if a particle at time $t$ attempts to hop beyond the boundary of the lattice, its move is rejected so that $x^{(t+1)} = x^{(t)}$.

* In periodic boundary conditions, the lattice is treated as if it wraps around, meaning that particles leaving the lattice from one end re-enter from the opposite end. This creates a toroidal geometry.

The much studied TASEP (totally asymmetric simple exclusion process) [4] differs from the SSEP in that, at each time step, a forward move is proposed:

$$ \underbrace{\left( \begin{smallmatrix} \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \end{smallmatrix} \right)}_{x^{(t)} \in \Omega^{\text{TASEP}}} \rightarrow \left\{ \begin{array}{ll} \underbrace{\left( \begin{smallmatrix} \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \end{smallmatrix} \right)}_{\text{choice of active } i} \rightarrow \underbrace{\left( \begin{smallmatrix} \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \end{smallmatrix} \right)}_{p = 1/N} & \text{p = 1/N} \\ \underbrace{\left( \begin{smallmatrix} \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \end{smallmatrix} \right)}_{x^{(t+1)} \in \Omega^{\text{TASEP}}} \rightarrow \underbrace{\left( \begin{smallmatrix} \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \end{smallmatrix} \right)}_{p = 1/N} & \text{p = 1/N} \end{array} \right. \quad (2) $$

Here, we require periodic boundary conditions because of the fixed direction of moves. The TASEP can be interpreted as one half of a lifting [5] of the SSEP [6]. In this paper, we consider the lifted TASEP [7, 8]. A configuration $x$ in $\Omega^{L-T}$ again consists of an ordered $N$-tuple $\{x_1, x_2, \dots, x_N\}$ with $x_1 < x_2 < \dots < x_N$, and in addition the position $x_i \in x$ of the active particle $i$, which is the only one that can move:

$$ \begin{array}{c} \begin{tikzpicture}[baseline={([yshift=-0.5ex]current bounding box.center)}] \\ \draw[fill] (0,0) circle (0.3); \node at (0,0) {●}; \draw[fill] (1,0) circle (0.3); \node at (1,0) {●}; \draw[fill] (2,0) circle (0.3); \node at (2,0) {●}; \draw[fill] (3,0) circle (0.3); \node at (3,0) {●}; \end{tikzpicture} \rightarrow \begin{tikzpicture}[baseline={([yshift=-0.5ex]current bounding box.center)}] \\ \draw[fill] (0,0) circle (0.3); \node at (0,0) {●}; \draw[fill] (1,0) circle (0.3); \node at (1,0) {●}; \draw[fill] (2,0) circle (0.3); \node at (2,0) {●}; \draw[fill] (3,0) circle (0.3); \node at (3,0) {●}; \end{tikzpicture} \rightarrow \left\{ \begin{array}{ll} \begin{tikzpicture}[baseline={([yshift=-0.5ex]current bounding box.center)}] \\ \draw[fill] (0,0) circle (0.3); \node at (0,0) {●}; \draw[fill] (1,0) circle (0.3); \node at (1,0) {●}; \draw[fill] (2,0) circle (0.3); \node at (2,0) {●}; \draw[fill] (3,0) circle (0.3); \node at (3,0) {●}; \end{tikzpicture} & p = \alpha \text{ (pullback move)} \\ \begin{tikzpicture}[baseline={([yshift=-0.5ex]current bounding box.center)}] \\ \draw[fill] (0,0) circle (0.3); \node at (0,0) {●}; \draw[fill] (1,0) circle (0.3); \node at (1,0) {●}; \draw[fill] (2,0) circle (0.3); \node at (2,0) {●}; \draw[fill] (3,0) circle (0.3); \node at (3,0) {●}; \end{tikzpicture} & p = \bar{\alpha} \text{ (forward move)} \end{array} \right. \end{array} \quad (3) $$

$$ \underbrace{\left( \begin{smallmatrix} \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \end{smallmatrix} \right)}_{x^{(t)} \in \Omega^{L-T}} \rightarrow \underbrace{\left( \begin{smallmatrix} \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \end{smallmatrix} \right)}_{\text{deterministic}} \rightarrow \underbrace{\left( \begin{smallmatrix} \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \end{smallmatrix} \right)}_{x^{(t+1)} \in \Omega^{L-T}} \rightarrow \left\{ \begin{array}{ll} \begin{tikzpicture}[baseline={([yshift=-0.5ex]current bounding box.center)}] \\ \draw[fill] (0,0) circle (0.3); \node at (0,0) {●}; \draw[fill] (1,0) circle (0.3); \node at (1,0) {●}; \draw[fill] (2,0) circle (0.3); \node at (2,0) {●}; \draw[fill] (3,0) circle (0.3); \node at (3,0) {●}; \end{tikzpicture} & p = \alpha \text{ (pullback move)} \\ \begin{tikzpicture}[baseline={([yshift=-0.5ex]current bounding box.center)}] \\ \draw[fill] (0,0) circle (0.3); \node at (0,0) {●}; \draw[fill] (1,0) circle (0.3); \node at (1,0) {●}; \draw[fill] (2,0) circle (0.3); \node at (2,0) {●}; \draw[fill] (3,0) circle (0.3); \node at (3,0) {●}; \end{tikzpicture} & p = \bar{\alpha} \text{ (forward move)} \end{array} \right. \quad (4) $$

where $\bar{\alpha} = 1 - \alpha$. As sketched in Eqs. (3) and (4), from a sample $x^{(t)}$, the active particle $i$ first advances deterministically, but if it is blocked ($x_{i+1} = x_i + 1$, with periodic boundary conditions in $i$ and $x$), it passes the *pointer* on to the blocking particle $i + 1$. Then, the move from $x^{(t)}$ to $x^{(t+1)}$ is completed by transferring the pointer with probability $\alpha$ to the preceding particle (pullback move from $x^{(t)}$ to $x^{(t+1)}$) or otherwise with probability $\bar{\alpha}$, by taking no further action (forward move from $x^{(t)}$ to $x^{(t+1)}$) (see the right-hand sides of Eqs. (3) and (4)). The transition matrix of this Markov chain is doubly stochastic, so that in the stationary state, all configurations $x \in \Omega^{L-T}$ are equally probable [7].

The lifted TASEP is a one-dimensional lattice reduction for the hard-sphere event-chain Monte Carlo algorithm [9]. Its parameter $\alpha$ corresponds to a factor field [8]. The model is integrable by Bethe ansatz [7], although many questions remain. Compared to the SSEP, the lifted TASEP can also be seen as a kinetically constrained lattice gas [10], as each of its configurations is connected only to two other configurations, whereas in the SSEP, the connectivity is $2N$. Nevertheless, we will find that the diameter of the lifted TASEP is only roughly double that of the SSEP. Non-rigorous exact enumerations for small system sizes indicate that for a critical value $\alpha_{crit}$ of the pullback, the mixing time (the time it takes to be close to the uniform distribution in total variation distance, starting from a worst-case configuration) scales as $O(N^2)$ (for $N \propto L$), the same scaling as we derive here rigorously for the diameter. In Eqs. (1) and (2), configurations are represented by the positions of the particles and in Eqs. (3) and (4), an additional pointer is introduced.
<table><caption>**Table 1** Diameter $d_{N,L}^{SSEP}$ of the SSEP with periodic boundary conditions, obtained by exact enumeration. Data are compatible with Eq. (8)</caption><thead><tr><th>L \ N</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th></tr></thead><tbody><tr><td>4</td><td>2</td><td>2</td><td>2</td><td>0</td><td></td><td></td></tr><tr><td>5</td><td>2</td><td>3</td><td>3</td><td>2</td><td>0</td><td></td></tr><tr><td>6</td><td>3</td><td>4</td><td>5</td><td>4</td><td>3</td><td>0</td></tr><tr><td>7</td><td>3</td><td>5</td><td>6</td><td>6</td><td>5</td><td>3</td></tr><tr><td>8</td><td>4</td><td>6</td><td>8</td><td>8</td><td>8</td><td>6</td></tr><tr><td>9</td><td>4</td><td>7</td><td>9</td><td>10</td><td>10</td><td>9</td></tr><tr><td>10</td><td>5</td><td>8</td><td>11</td><td>12</td><td>13</td><td>12</td></tr><tr><td>11</td><td>5</td><td>9</td><td>12</td><td>14</td><td>15</td><td>15</td></tr><tr><td>12</td><td>6</td><td>10</td><td>14</td><td>16</td><td>18</td><td>18</td></tr></tbody></table>

## 2 Diameters of Exclusion Models

Let $P$ be a Markov chain with sample space $\Omega$ and stationary distribution $\pi$. We use $P^t(x, \cdot)$ to denote the distribution of the chain at time $t$, assuming $x$ as the starting configuration. Then we refer to

$$ t_{\text{mix}}(P) := \min_t \left\{ t \ge 0, \max_{x \in \Omega} \| P^t(x, \cdot) - \pi \|_{TV} \le \frac{1}{4} \right\} \quad (5) $$

as the mixing time of $P$, where $\| \cdot \|_{TV}$ denotes the total variation distance. The diameter of a discrete-time Markov chain $P$ in $\Omega$ is defined as

$$ d = \max_{X,Y \in \Omega} d(X, Y), \quad (6) $$

where $d(X, Y)$ is the smallest number of moves of $P$ needed to reach $Y$ from $X$. For non-reversible Markov chains, $d(X, Y)$ may differ from $d(Y, X)$. The diameter bounds the mixing time from below by $d/2$ [11]. The diameter of a lifted Markov chain cannot be smaller than that of its *collapsed chain* (the chain of which it is a *lifting*). Although we are interested in the diameter of the *lifted TASEP*, we therefore first compute that of the *SSEP*. On the other hand, the diameter of a *lifted Markov chain* can be much larger than that of its *collapsed chain*. As an example, the *lifted TASEP* for $\alpha = 0$ is not irreducible, so that its diameter is infinite for finite $N$ and $L$. Naturally, the diameter of the *lifted TASEP* is independent of $\alpha$, for $0 < \alpha < 1$.

### 2.1 Diameter of the SSEP

We establish the diameter $d_{N,P}^{SSEP}$ of the SSEP with hard-wall boundary conditions and, analogously, the diameter $d_{N,P}^{SSEP}$ for the periodic SSEP (see Table 1 for examples)

**Theorem 1** Let $N \le L$. For hard-wall boundary conditions, we have

$$ d_{N,L}^{SSEP} = N(L-N) \quad (\text{hard-wall boundary conditions}), \quad (7) $$

while, for periodic boundary conditions, the following is true:

$$ d_{N,L}^{SSEP} = \left\lfloor \frac{N(L-N)}{2} \right\rfloor \quad (\text{periodic boundary conditions}). \quad (8) $$
Before proving Theorem 1, we provide an upper bound for the diameter which is inde-
pendent of boundary conditions (Lemma 1), as well as a tool to reduce the periodic SSEP to
the hard-wall SSEP (Lemma 2).

**Lemma 1** Let $x = \{x_1, x_2, \dots, x_N\}$ and $y = \{y_1, y_2, \dots, y_N\}$ be two configurations in $\Omega^{\text{SEP}}$. Then, for both periodic and hard-wall boundary conditions, we have

$$
d^{\text{SSEP}}(x, y) \le \sum_{i=1}^{N} |y_i - x_i|. \tag{9}
$$

Consequently, $d_{N,L}^{\text{SSEP}}$, $d_{N,L}^{[\text{SEP}]} \le N(L-N)$.

**Proof** For fixed $L$, we prove by induction on $N \le L$ that $x$ can reach $y$ at most $\sum_{i=1}^N |y_i - x_i|$ moves; these moves do not invoke periodic boundary conditions, and for each particle $i$, the direction of moves taken from $x_i$ to $y_i$ are *monotone*, that is, either all forward or all backward. The case $N=1$ is obvious. Suppose the induction holds for $N \le k$. Now consider $N = k+1$. We claim that there exists a *flexible particle* at $x_i \in x$ such that there are no particles in $x$ within the interval $[x_i, y_i]$ or $[y_i, x_i]$ (whichever is a valid interval), except the flexible particle itself. Before displacing any other particle, we can move the flexible particle from $x_i$ to $y_i$ using monotone SSEP moves only, without invoking periodic boundary conditions. After this movement, we apply the induction hypothesis to two smaller instances whose number of particles is at most $k$: we can move particles in $\{x_1, \dots, x_{i-1}\}$ to $\{y_1, \dots, y_{i-1}\}$ in $\sum_{j=1}^{i-1} |y_j - x_j|$ monotone moves without invoking periodic boundary conditions; similarly, we can move particles in $\{x_{i+1}, \dots, x_N\}$ to $\{y_{i+1}, \dots, y_N\}$ in $\sum_{j=i+1}^N |y_j - x_j|$ monotone moves without invoking periodic boundary conditions. These two instances are independent of each other because $y_i$ divides the $[1, L]$ into halves. More precisely, if $x_i < y_i$ then $x_{i-1}, y_{i-1} < y_i < y_{i+1}$ and by the property of flexible particle, $x_{i+1} > y_i$; if $x_i > y_i$ then $x_{i+1}, y_{i+1} > y_i > y_{i-1}$ and by the property of flexible particle, $x_{i-1} < y_i$. Hence, we establish the induction.

It remains to show the existence of a flexible particle. For the sake of contradiction, we assume that there is no flexible particle. If $y_1 \le x_1$, then the particle $i=1$, at $x_1$, is flexible. If the particle $i=1$, at $x_1$, is not flexible, then we must have $x_1 < x_2 \le y_1$. This also implies $x_2 < y_2$. Moreover, if $x_2$ is not flexible, then we have $x_2 < x_3 \le y_2$. We continue in this fashion and obtain for each $i=1, 2, \dots, N-1$ that $x_i < x_{i+1} \le y_i$. At the end, we know $x_N \le y_{N-1} < y_N$. Since, by definition, particle $N$ is the most forward, it must be flexible, so there is a contradiction. $\square$

With the following lemma, we reduce the SSEP with periodic boundary conditions to the
one with hard-wall boundary conditions. We denote by $[a, b]$ the periodic interval of $a$ and
$b$, in other words the interval from $a$ to $b$ if $a \le b$ and, using this definition, $[a, L] \cup [1, b]$
if $a > b$.

**Lemma 2** Let $x = \{x_1, x_2, \dots, x_N\}$ and $y = \{y_1, y_2, \dots, y_N\}$ be configurations in $\Omega^{\text{SEP}}$.
There then exists a periodic interval $[a, b]$ of length $\lfloor L/2 \rfloor$ or $\lfloor L/2 \rfloor + 1$ that contains the
same number of particles in $x$ and in $y$.

**Proof of Lemma 2** With periodic boundary conditions, there are *L* distinct periodic intervals of length *m* := ⌊*L*/2⌋ + 1. Let *S*₀ = [*a*₀, *b*₀] be one of the intervals such that |*x* ∩ *S*₀| - |*y* ∩ *S*₀| achieves its maximum among these *L* intervals. Let *S*ᵢ := [*a*ᵢ, *b*ᵢ] be the translation of *S*₀ by
Alternatively, in the case $L_1 = L/2 + 1$ and $L_2 = L/2 - 1$, a similar computation yields for the hard-wall diameters:

$$d_{N_1, L_1}^{[SSEP]} + d_{N_2, L_2}^{[SSEP]} \le N_1(L_1 - N_1) + N_2(L_2 - N_2) \quad (20)$$

$$= k \left( \frac{L}{2} + 1 - k \right) + (N - k) \left[ \frac{L}{2} - 1 - (N - k) \right] \quad (21)$$

$$= \left[ k \cdot \frac{L}{2} + (N - k) \cdot \frac{L}{2} \right] - \underbrace{[k^2 + (N - k)^2 - k + (N - k)]}_{f_1(k)}, \quad (22)$$

where $f_1(k) : \mathbb{R} \to \mathbb{R}$ given by $f_1(k) = k^2 + (N-k)^2 - k + (N-k)$. By checking the derivative of $f_1$, we see that for any $k \ge 0$,

$$f_1(k) \ge f_1\left(\frac{N-1}{2}\right) = \frac{N^2-1}{2}. \quad (23)$$

Thus,

$$d_{N,L}^{\text{SSEP}} \le d_{N_1,L_1}^{[\text{SSEP}]} + d_{N_2,L_2}^{[\text{SSEP}]} \le \frac{NL}{2} - f_1(k) \le \frac{NL}{2} - \frac{N^2-1}{2} = \frac{N(L-N)}{2} + \frac{1}{2}. \quad (24)$$

If $N$ is odd, then

$$d_{N,L}^{\text{SSEP}} \le \frac{N(L-N)}{2} + \frac{1}{2} = \left\lceil \frac{N(L-N)}{2} \right\rceil. \quad (25)$$

If $N$ is even, then

$$d_{N,L}^{\text{SSEP}} \le \frac{N(L-N)}{2} + \frac{1}{2} = \left\lceil \frac{N(L-N)}{2} \right\rceil + \frac{1}{2}. \quad (26)$$

Since $d_{N,L}^{\text{SSEP}}$ is an integer and $\lceil \frac{N(L-N)}{2} \rceil$ in this case is the largest integer satisfying the above inequality, we have

$$d_{N,L}^{\text{SSEP}} \le \left\lceil \frac{N(L-N)}{2} \right\rceil. \quad (27)$$

When $L$ is odd, Lemma 2 in turn implies the existence of a periodic interval $[a, b] \subseteq [1, L]$ of length $\lceil L/2 \rceil$ or $\lfloor L/2 \rfloor$ with the same number of particles in $x$ and in $y$. In either case, we can choose to set $L_1 = \lceil L/2 \rceil$, $N_1 = k$, $L_2 = \lfloor L/2 \rfloor$ and $N_2 = N - k$ for some $k \in [0, N]$. By an analogous computation, we have

$$d_{N,L}^{\text{SSEP}} \le d_{N_1,L_1}^{[\text{SSEP}]} + d_{N_2,L_2}^{[\text{SSEP}]} \le \frac{NL}{2} - \underbrace{\left[ \left( k + \frac{1}{2} \right) k + (N-k) \left( N - k + \frac{1}{2} \right) \right]}_{f_2(k)}, \quad (28)$$

with $f_2(k) = (k + \frac{1}{2})k + (N - k)(N - k - \frac{1}{2})$. Again, by checking the derivative of $f_2$, we obtain that for any $k \ge 0$,

$$f_2(k) \ge f_2\left(\frac{2N-1}{4}\right) = \frac{N^2-1}{2} - \frac{1}{8}. \quad (29)$$

Thus,

$$d_{N,L}^{\text{SSEP}} \le \frac{NL}{2} - f_2(k) = \frac{N(L-N)}{2} + \frac{1}{8}. \quad (30)$$
**Lemma 4** Assume $L > N \ge 3$. For any two configurations $x = \{x_1, \dots, x_N\}$ and $y = \{y_1, \dots, y_N\}$, there exists a cyclic relabeling of $y$, denoted as $y' = \{y'_1, \dots, y'_N\}$, satisfying

$$1 \le y'_{m+1} < y'_{m+2} < \dots < y'_N < y'_1 < \dots < y'_m \le L \quad (50)$$

with an integer $m \in [0, N]$, such that

$$D(x_i, y'_i) \le L - N + 2, \quad \text{for all } i = 1, \dots, N, \quad (51)$$

and

$$y'_i \ge x_i + 2 \quad \text{for all } i = 1, \dots, m. \quad (52)$$

**Lemma 5** Assume $L > N \ge 3$. Let $x$ and $y$ be two arbitrary configurations, with $\hat{C}_x = \{\tilde{x}_1, \dots, \tilde{x}_N\}$ a successor of $x$ (with foremost active particle) and $C_y = \{\tilde{y}_1, \dots, \tilde{y}_N\}$ an ancestor (with backmost active particle). Suppose that $\hat{C}_x = \{\tilde{x}_1, \dots, \tilde{x}_N\}$ and the cyclically relabeled configuration $C'_y = \{\tilde{y}'_1, \dots, \tilde{y}'_N\}$ satisfy the conditions Eqs. (50) and (52) of Lemma 4 with an integer $m \in [0, N]$. Then we have that

$$d(\hat{C}_x, C'_y) \le \sum_{i=1}^{N} D(\tilde{x}_i, \tilde{y}'_i) + \mathcal{O}(L). \quad (53)$$

Now we use Lemmas 4 and 5 to complete the analysis of the stage 2 in Eq. (49). By applying Lemma 4 to $\hat{C}_x$ and $C_y$, we obtain an $m$ and a cyclically relabeled configuration $C'_y = \{\tilde{y}'_1, \dots, \tilde{y}'_N\}$ such that Eqs. (50), (51) and (52) are satisfied. With the same $m$ and the cyclically relabeled sequence $C'_y$ for $C_y$, Lemma 5 then suggests

$$d(\hat{C}_x, C'_y) \le \sum_{i=1}^{N} D(\tilde{x}_i, \tilde{y}'_i) + \mathcal{O}(L) \le N(L - N + 2) + \mathcal{O}(L), \quad (54)$$

where the last inequality follows from Eq. (51).

Therefore, $x$ reaches $y$ in at most

$$2(L - 1) + N(L - N + 2) + \mathcal{O}(L) = N(L - N) + \mathcal{O}(L) \quad (55)$$

moves, which establishes Eq. (42).

□

We provide the proofs of Lemmas 4 and 5 in the appendix.

## 3 Discussion

The discussed diameter bounds are compatible with the proven [12, 13] or conjectured [7] mixing times for the SSEP and the lifted TASEP, respectively. In particular, the diameter of the lifted TASEP, which is independent of $\alpha$ for $0 < \alpha < 1$, provides a first geometrical characteristic of its sample space. In particular, it sets a lower bound on its mixing time for all values of the pullback $\alpha$. For non-critical pullbacks, numerical simulations [7, 8, 14] indicate a mixing-time scaling as $N^{5/2}$, much larger than the diameter bound $t_{\text{mix}} \ge d/2$. However, for $\alpha = \alpha_{\text{crit}}$, numerical simulations for $2N = L$ [7] (see also [8]) are compatible with a mixing time $t_{\text{mix}} \to N^2$ (for $N \to \infty$), which would saturate the diameter bound up to a factor of two. An asymptotically sharp diameter bound (up to a constant factor), for $\alpha = \alpha_{\text{crit}}$, would be exceptional as diameter bounds are in general very weak [11]. Given the importance of the model, it would be interesting to obtain other geometrical characteristics,
as the α-dependent conductance of the underlying graph. It appears also possible to obtain the mixing time of the lifted TASEP rigorously, given that this was achieved for the SSEP [12, 13], where it is ~ $N^3 \log N$ and for the TASEP [15], where it is ~ $N^{5/2}$. At present, the inverse-gap scaling for the lifted TASEP is known only from the Bethe ansatz, and it shows a pronounced dependence on α. It will be fascinating to understand whether this α dependence is reflected in the basic geometry of the sample space and whether it can be obtained rigorously.

## A Supporting Proofs

We provide proofs of Lemmas 4 and 5.

**Proof of Lemma 4** We provide the following Algorithm 1 that inputs configurations x and y and returns the cyclic relabeling y' characterized by an integer m and satisfying Eqs. (50), (51) and (52).

**Algorithm 1** Find y' and m in the proof of Lemma 4

**Require:** $1 \le x_1 < \dots < x_N \le L$, $1 \le y_1 < \dots < y_N \le L$

**Ensure:** $y'_i \in y$ for all $i = 1, \dots, N$, and $m \in [0, N]$

**Ensure:** $1 \le y'_{m+1} < y'_{m+2} < \dots < y'_N < y'_1 < \dots < y_m \le L$

**Ensure:** $y'_i \ge x_i + 2$ for all $i = 1, \dots, m$

1: $m \leftarrow N$

2: **while** $m > 0$ **do**

3: &nbsp;&nbsp;&nbsp;&nbsp;**for** $i = 1, 2, \dots, m$ **do**

4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$y'_i \leftarrow y_{N-m+i}$

5: &nbsp;&nbsp;&nbsp;&nbsp;**end for**

6: &nbsp;&nbsp;&nbsp;&nbsp;**for** $i = 1, \dots, N-m$ **do**

7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$y'_{m+i} \leftarrow y_i$

8: &nbsp;&nbsp;&nbsp;&nbsp;**end for**

9: &nbsp;&nbsp;&nbsp;&nbsp;**if** $y'$ and $m$ satisfy Eq. (52) **then**

10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**return** $y'$ and $m$

11: &nbsp;&nbsp;&nbsp;&nbsp;**end if**

12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$m \leftarrow m - 1$

13: &nbsp;&nbsp;&nbsp;&nbsp;**end while**

14: **return** $y' = \{y_1, y_2, \dots, y_N\}$ and $m = 0$

Clearly, if Algorithm 1 exits through Line 14, the output satisfies Eqs. (50) and (52). If Algorithm 1 exits through Line 10, its output satisfies Eq. (52) due to Line 9 and satisfies Eq. (50) due to the assignment in Lines 3-8.

Now we show that the output of Algorithm 1 also satisfies Eq. (51). First suppose that Algorithm 1 terminates with $m = N$. Since $x_i \ge i$, $y'_i \le L - (N - i)$ and $y'_i \ge x_i + 2$ it then holds that

$$D(x_i, y'_i) = y'_i - x_i \le L - (N - i) - i = L - N. \quad (56)$$

As Eq. (56) holds for $i = 1, \dots, N$, the case $m = N$ has thus been handled.

Second, we may suppose that Algorithm 1 terminates with $m < N$. Since Algorithm 1 does not satisfy Eq. (52) for $m + 1$, one of two following conditions are satisfied (still for $m < N$):

(i) $y'_N = y_{N-m} < x_1 + 2$,

(ii) There exists $i \le m$ such that $y'_i = y_{N-m+i} < x_{i+1} + 2$.
Under the case (i), we have

$$x_1 + (L - y'_N) > x_1 + (L - x_1 - 2) = L - 2 \quad (57)$$

For any $j \in [1, m]$, since $x_j < y'_j \le L$, it holds that

$$D(x_j, y'_j) \le L - (x_j + (L - y'_j)) = L - (x_1 + (L - y'_N)) + (x_1 - x_j) + (y'_j - y'_N). \quad (58)$$

It follows from Eqs. (57) and (58) that

$$D(x_j, y'_j) < 2 - (j - 1) + [L - (N - j)] = L - N + 3. \quad (59)$$

For $j \in [m+1, N]$, $x_j$ reaches $y'_j$ across the periodic boundary. By an analogous computation, we also have

$$D(x_j, y'_j) \le y'_j + (L - x_j) \le y'_N - (N - j) + (L - x_j) \quad (60)$$

$$< (x_1 + 2) + (L - x_j) - (N - j) \quad (61)$$

$$\le L + 2 - (j - 1) - (N - j) = L - N + 3. \quad (62)$$

Next we consider the case (ii). For $j \in [1, m]$, we have

$$D(x_j, y'_j) \le L - (x_j + (L - y'_j)) \quad (63)$$

$$= L - (x_{i+1} + (L - y'_i)) + (x_{i+1} - x_j) + (y'_j - y'_i) \quad (64)$$

$$< 2 + (x_{i+1} - x_j) + (y'_j - y'_i), \quad (65)$$

where Eq. (65) follows from (ii). If $j \ge i + 1$, then $x_{i+1} - x_j \le i + 1 - j$ and $y'_j - y'_i \le L - N + j - i$, so we obtain

$$2 + (x_{i+1} - x_j) + (y'_j - y'_i) \le 2 + (i + 1 - j) + (L - N + j - i) = L - N + 3. \quad (66)$$

If $j \le i$, then $x_{i+1} - x_j \le L - N + (i + 1) - j$ and $y'_j - y'_i \le j - i$ so again we obtain

$$2 + (x_{i+1} - x_j) + (y'_j - y'_i) \le 2 + (L - N + (i + 1) - j) + (j - i) = L - N + 3. \quad (67)$$

Combining inequalities Eqs. (63) and (67), we establish that $D(x_j, y'_j) < L - N + 3$. For $j \in [m + 1, N]$, it holds that

$$D(x_j, y'_j) \le y'_j + (L - x_j) \le y'_i - (i + N - j) + (L - x_j). \quad (68)$$

By (ii), we have

$$y'_i - (i + N - j) + (L - x_j) < x_{i+1} + 2 + L - N - x_j - (i - j) \quad (69)$$

$$= L - N + 2 + (x_{i+1} - x_j) - (i - j) \quad (70)$$

$$\le L - N + 2 + (i + 1 - j) - (i - j) \quad (71)$$

$$= L - N + 3. \quad (72)$$

The inequalities Eqs. (68) and (72) imply that $D(x_j, y'_j) < L - N + 3$.

In both cases we have shown that $D(x_j, y'_j) < L - N + 3$ for all $j = 1, \dots, N$, and Eq. (51) follows as $D(x_j, y'_j)$ is an integer. □
**Proof of Lemma 5** Since configurations x and y are inconsequential to this proof, to simplify the notations, instead of writing $\hat{C}_x = \{\tilde{x}_1, \dots, \tilde{x}_N\}$ for the successor of x and $C'_y = \{\tilde{y}'_1, \dots, \tilde{y}'_N\}$ for the cyclic relabeling of the ancestor $C_y$ of y, we write $\hat{C}_x = \{x_1, \dots, x_N\}$ and $C'_y = \{y_1, \dots, y_N\}$. Recall that configuration $\hat{C}_x$ is an ordered N-tuple, so we could refer to the particle at $x_i$ as the particle i for each $i = 1, \dots, N$.

We first discuss two simple cases. If $m = N$, we can directly move each particle i to $y_i$ in the order of $i = N, \dots, 1$; in this case $d(\hat{C}_x, C'_y) = \sum_i D(x_i, y_i)$. If $m = N-1$, we just move the particle N across the periodic boundary to position 1 (first pushing any blocking particles forward by executing Lines 2-4 of Algorithm 2 if $x_1 = 1$), then successfully move particles $N-1, \dots, 1$ to $y_{N-1}, \dots, y_1$ in the order of $N-1, \dots, 1$, and finally move the particle N to $y_N$ if $y_N > 1$. Reaching $C'_y$ from $\hat{C}_x$ through these steps implies $d(\hat{C}_x, C'_y) \le \sum_i D(x_i, y_i) + O(N)$, where we spend additional $O(N)$ steps for the need to push the blocking particles forward at the beginning.

In the rest of the proof, we assume $m \le N-2$. Note that this assumption together with (51) ensures that

$$D(x_i, y_i) \ge 2 \quad \text{for } i \in [m+1, N]. \qquad (73)$$

Now, given any pair of $(\hat{C}_x, C'_y)$, we provide the following Algorithm 2 that reaches $C'_y$ from $\hat{C}_x$ through the lifted TASEP steps.

**Algorithm 2** An algorithm to reach $C'_y$ from $\hat{C}_x$ in Lemma 5

Require: $m \le N-2, L > N \ge 3$.

Require: $1 \le x_1 < \dots < x_N \le L, 1 \le y_{m+1} < \dots < y_N < y_1 < \dots < y_m \le L$

Require: $D(x_i, y_i) \ge 2 \quad \text{for } i \in [1, N]$

Ensure: particle i is at $y_i$ for all $i = 1, \dots, N$, and the pointer is on $y_{m+1}$

1: **if** $x_N = L$ and $x_1 = 1$ **then**

2: Transfer the pointer to particle 1

3: Use pullback moves to send particle 1 one step forward

4: (If particle 1 is blocked, send particles 2, 3, ... forward as well)

5: **end if** (The pointer should be back on particle N.)

6: **repeat**

7: **for** $i = N, N-1, \dots, m+1$ **do**

8: Attempt to move particle i to $y_i - 1$ (The pointer should then be on $i-1$)

9: (Use forward moves to reach $y_i - 2$, and use one pullback move to reach $y_i - 1$)

10: (Before being blocked by $i+1$, particle i transfers the pointer to $i-1$ by a pullback)

11: **end for** (The pointer should then be on m)

12: **for** $i = m, m-1, \dots, 1$ **do**

13: Attempt to move particle i to $y_i$

14: **end for** (The pointer should then be on N)

15: **until** at least one attempts succeeds

16: **for** $i = N, N-1, \dots, m+2$ **do**

17: Attempt to move particle i to $y_i$

18: **end for**

19: **if** particle m is at $y_m$ **then**

20: Move particle m + 1 to $y_{m+1}$ via forward moves

21: **else**:

22: CLEANUP($y_1, \dots, y_N, m$)

23: **end if**

We first verify the validity of Algorithm 2 in scenarios where the steps might be unclear. In Lines 8, 13 and 17, the attempted moves for the particle i could be blocked by the particle i + 1, but at least in all these cases, a single pullback move could still take place due to
**Algorithm 3 CLEANUP subroutine used in Line 22 of Algorithm 2**

1: Let $l_1 \in [1, m]$ be the least number such that the particle $l_1$ is not at $y_{l_1}$

2: **for** $i = m + 1, m, \dots, l_1 + 1$ **do**

3: Use forward moves to send particle $i$ to $y_{i-1}$, unless $i$ is at $y_{i-1}$ already

4: Use a pullback move to send $i$ to $y_{i-1} + 1$, and transfer the pointer to $i - 1$

5: **end for**

6: **if** $l_1 = 1$ and particle $N$ is not at $y_N$ **then**

7: Let $l_2 \in (m + 1, N]$ be the least number such that particle $l_2$ is not at $y_{l_2}$

8: Use forward moves to send particle 1 to $y_1 - 1$, unless 1 is at $y_1 - 1$ already

9: Use a pullback move to send particle 1 to $y_1$ and transfer the pointer to $N$

10: **for** $i = N, \dots, l_2 + 1$ **do**

11: Use forward moves to send particle $i$ to $y_{i-1}$, unless $i$ is at $y_{i-1}$ already

12: Use a pullback move to send particle $i$ to $y_i$ and transfer the pointer to $i - 1$

13: **end for**

14: **for** $i = l_2, \dots, N, 1, \dots, m$ **do**

15: Use forward moves to send particle $i$ to $y_i$, unless $i$ is at $y_i$ already

16: Use a forward move to transfer the pointer to $i + 1$

17: **end for**

18: **else**:

19: **for** $i = l_1, \dots, m$ **do**

20: Use forward moves to send particle $i$ to $y_i$, unless $i$ is at $y_i$ already

21: Use a forward move to transfer the pointer to $i + 1$

22: **end for**

23: **end if**

24: Move particle $m + 1$ to $y_{m+1}$ if needed

Eqs. (73) and (51), and the pointer always successfully transfers to the particle $i - 1$. Thus, operations in Lines 7-14 are always valid moves of the lifted TASEP. In addition, we need to verify that an infinite loop never takes place in Lines 6-15: since particles keep moving forward, the algorithm will eventually break out the repeat-until loop, and hence terminate in finite time.

To see the correctness of Algorithm 2, we make several useful observations. Observe that in Lines 7-11, if any particle $i$ successfully reaches $y_i - 1$, then the particle $i$ is unable to block particle $i - 1$ in the upcoming iteration of $i - 1$. Consequently, all particles $i - 1, \dots, m + 1$ reach $y_{i-1}, \dots, y_{m+1}$ successfully in Line 8. Similarly, in Lines 12-14, if any particle $i$ successfully reaches $y_i$ then all particles $i - 1, \dots, 1$ reach their assigned destinations in Line 13. Hence, when the Algorithm 2 breaks out the repeat-until loop, either the particle 1 has arrived at $y_1$ or the particle $m + 1$ has arrived at $y_{m+1} - 1$.

**Case 1:** particle 1 has arrived at $y_1$. Since $y_1 > y_N > \dots > y_{m+1}$ by assumption, in Lines 16-18, all attempts will be successful. Next we consider the two cases in Line 19. By the previous observation, if particle $m$ has arrived at $y_m$, which can only happen in Line 13, then each particle $i$ has arrived at $y_i$ for $i \in [1, m]$. Hence if the algorithm reaches Line 20, the only unfinished particle is the particle $m + 1$, which is then sent to $y_{m+1}$. Alternatively, if particle $m$ is not at $y_m$ in Line 19, then we enter the CLEANUP subroutine in Algorithm 3. In Lines 2-5 of Algorithm 3, for each $i \in [m + 1, l_1 + 1]$, since particle $i + 1$ has been at position $y_i + 1$, these steps in Lines 2-5 will not be blocked by $i + 1$ and thus they execute successfully. By the assumption of case 1, we have $l_1 > 1$, so we enter the else branch in Line 18. For each $i \in [l_1, m]$, from our earlier discussions, the particle $i + 1$ has been staying at $y_i + 1$, so moving each particle $i$ to $y_i$ would not get blocked by $i + 1$; after Line 20 succeeds, particles $i$ and $i + 1$ are adjacent, so the forward move in Line 21 would also be justified. So far all particles except $m + 1$ have arrived at their destinations. Finally, particle $m + 1$ arrives
at $y_{m+1}$ in Line 24. Therefore, the final configuration equals to $C'_y$, and we conclude the case 1.

**Case 2:** particle 1 has not arrived at $y_1$ but particle $m+1$ arrives at $y_{m+1}-1$. If $y_{m+1} \neq 1$, then in the last iteration of the repeat-until loop, all attempts in Line 13 of Algorithm 2 will be successful since particle $m+1$ has crossed the periodic boundary and will not able to block any of the movements in Lines 12-14. Then particle 1 would have arrived at $y_1$ but this contradicts our assumption. Thus, the only possibility that Case 2 could happen is $y_{m+1} = 1$. $y_m = L, \dots, y_1 = L-m$. Moreover, just before the execution of Line 16 of Algorithm 2, particle 1 is at $L-m-1$, particle 2 is at $L-m, \dots$, and particle $m+1$ is at $L$. Following this, Lines 16-18 ensure that there exists $l_2 \in [m+2, N]$ such that particle $i$ is blocked for $N \ge i \ge l_2$ while particle $i$ is at $y_i$ for $m+2 \le i < l_2$. As in this case particle $m$ is not at $y_m$, we enter the CLEANUP subroutine. In Lines 3-4 of Algorithm 3, we will send particle $m+1$ to $y_m+1 = 1$. If particle $N$ has been at $y_N$, the rest of proof follows analogous arguments as in Case 1. If particle $N$ has not been at $y_N$, additional steps in Lines 7-17 of Algorithm 3 are needed to make sure both the final positions of particles $l_2, \dots, N$ and the location of the pointer are correct. Noticing that the particles $l_2, \dots, N, 1, \dots, m+1$ are all adjacent to each other, the validity of these steps are readily verified.

Lastly, we count the total number of lifted TASEP steps used in Algorithm 2. Each particle $i$ travels a distance $D(x_i, y_i)$ through a combination of forward and pullback moves; in addition, in Lines 2-4 of Algorithm 2 and in Lines 16, 21 of Algorithm 3, we use a total of $O(L)$ forward moves to transfer the pointers without moving any particles. Therefore, the number of steps required to reach $C'_y$ from $\bar{C}_x$ is at most

$$ \sum_{i=1}^{N} D(x_i, y_i) + O(L), \qquad (74) $$

so we establish Eq. (53).

<figure><img src="image_2.png" /></figure>

**Acknowledgements** We thank A. C. Maggs for helpful discussions. We thank the mathematical research institute MATRIX in Australia where this research was initiated.

**Open Access** This article is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License, which permits any non-commercial use, sharing, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if you modified the licensed material. You do not have permission under this licence to share adapted material derived from this article or parts of it. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by-nc-nd/4.0/.

## References

1. Liggett, T.M.: Interacting Particle Systems. Grundlehren der Mathematischen Wissenschaften, Springer, New York (1985)

2. Liggett, T.M.: Stochastic Interacting Systems: Contact, Voter and Exclusion Processes. Grundlehren der Mathematischen Wissenschaften, p. 332. Springer, Berlin (1999). https://doi.org/10.1007/978-3-662-03990-8

3. Spitzer, F.: Interaction of Markov processes. Adv. Math. 5(2), 246-290 (1970). https://doi.org/10.1016/0001-8708(70)90034-4
4. Chou, T., Mallick, K., Zia, R.K.P.: Non-equilibrium statistical mechanics: from a paradigmatic model to biological transport. Rep. Prog. Phys. **74**(11), 116601 (2011)

5. Chen, F., Lovász, L., Pak, I.: Lifting Markov Chains to Speed up Mixing. In: Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 275 (1999)

6. Krauth, W.: Event-chain Monte Carlo: foundations, applications, and prospects. Front. Phys. **9**, 229 (2021)

7. Essler, F.H.L., Krauth, W.: Lifted TASEP: a Bethe ansatz integrable paradigm for non-reversible Markov chains (2023)

8. Lei, Z., Krauth, W., Maggs, A.C.: Event-chain Monte Carlo with factor fields. Phys. Rev. E **4**, 99 (2019)

9. Bernard, E.P., Krauth, W., Wilson, D.B.: Event-chain Monte Carlo algorithms for hard-sphere systems. Phys. Rev. E **80**, 056704 (2009). https://doi.org/10.1103/PhysRevE.80.056704

10. Cancrini, N., Martinelli, F., Roberto, C., Toninelli, C.: Kinetically constrained lattice gases. Commun. Math. Phys. **297**(2), 299–344 (2010). https://doi.org/10.1007/s00220-010-1038-3

11. Levin, D.A., Peres, Y.: Markov Chains and Mixing Times. American Mathematical Society, 2nd edn. Springer, New York (2017)

12. Lacoin, H.: The cutoff profile for the simple exclusion process on the circle. Ann. Probab. **44**(5), 3399–3430 (2016)

13. Lacoin, H.: The simple exclusion process on the circle has a diffusive cutoff window. Ann. Inst. H. Poincaré Probab. Stat. **53**(3), 1402–1437 (2017)

14. Kapfer, S.C., Krauth, W.: Irreversible local Markov chains with rapid convergence towards equilibrium. Phys. Rev. Lett. **119**, 240603 (2017). https://doi.org/10.1103/PhysRevLett.119.240603

15. Baik, J., Liu, Z.: TASEP on a ring in sub-relaxation time scale. J. Stat. Phys. **165**(6), 1051–1085 (2016). https://doi.org/10.1007/s10955-016-1665-y

**Publisher's Note** Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.