# Shift-Invariance of the Colored TASEP and Finishing Times of the Oriented
Swap Process

Lingfu Zhang Department of Mathematics, Princeton University, e-mail:
<EMAIL_ADDRESS>
###### Abstract

We prove a new shift-invariance property of the colored TASEP. It is in the
same spirit as recent results of Borodin-Gorin-Wheeler, Dauvergen, and
Galashin, while out of the scope of the generality of their methods. Our proof
takes shift-invariance of the colored six-vertex model as an input, and uses
analyticity of the probability functions and induction arguments. We apply our
shift-invariance to prove a distributional identity between the finishing
times of the oriented swap process and the point-to-line passage times in
exponential last-passage percolation, which is conjectured by Bisi-Cunden-
Gibbons-Romik and Bufetov-Gorin-Romik, and is also equivalent to a purely
combinatorial identity in relation with the Edelman-Greene correspondence.
With known results from last-passage percolation, this also implies new
asymptotic results on the finishing times of the oriented swap process.

##  1 Introduction

The Totally Asymmetric Simple Exclusion Process (TASEP) is a classical model
in the category of interacting particle system, where one considers a
collection of particles in $\mathbb{Z}$, such that each site contains at most
one particle. There is an independent Poisson clock on each edge $(x,x+1)$,
such that when it rings, if there is a particle at site $x$, and the site
$x+1$ is empty, then the particle jumps to site $x+1$. See e.g. the book of
Liggett [Lig12] and references therein.

The colored TASEP is a variant of this model: there is a particle at each site
in $\mathbb{Z}$, and each particle has an additional property called _color_ ,
which is usually integer-valued. A particle with a smaller color is considered
‘stronger’ than a particle with a larger color: when the Poisson clock on edge
$(x,x+1)$ rings, if the particles on sites $x$ and $x+1$ have colors $i$ and
$j$ respectively, then they would swap if and only if $i<j$. The uncolored
TASEP can be viewed as a colored TASEP with two color: particles with the
larger color correspond to holes, and particles with the smaller color
correspond to particles. Another degeneration of the colored TASEP is TASEP
with second-class particles. In such models there are normal particles,
second-class particles, and holes on $\mathbb{Z}$. The rule is that a normal
or second-class particle can jump to a hole right next to it, and a normal
particle can swap with a second-class particle right next to it. Such models
involving second-class particles have proven powerful in understanding the
evolution of the TASEP and related exactly solvable models [FKS91, Fer92,
DJLS93, Spe94, BCS06, BS10, MSZ21].

In this paper we consider the following colored TASEP, studied in e.g. [AHR09,
AAV11, Buf20, BF20, BB21]. The particles have mutually different colors, and
initially the particle at each site $x$ is colored $x$. The configuration of
this process at any time $t\geq 0$ can be viewed as a bijection
$\zeta_{t}:\mathbb{Z}\to\mathbb{Z}$, where $\zeta_{0}$ is the identity map,
and $t\mapsto\zeta_{t}(x)$ is cadlag for each $x\in\mathbb{Z}$. There are
several distributional identities for this process, due to natural symmetries.
For example, take any $y\in\mathbb{Z}$, the function $x\mapsto\eta_{t}(x-y)+y$
has the same distribution as $\eta_{t}$. There is also a reflection symmetry,
which says that $x\mapsto-\eta_{t}(-x)$ has the same distribution as
$\eta_{t}$. There are also some less obvious equal in distribution or
symmetries that have been proved previously. For example, in [AAV11], it is
proved that $\zeta_{t}$ and its inverse (as a permutation of $\mathbb{Z}$)
have the same distribution. A version of this symmetry in a finite interval is
given in [AHR09]. A more general color-to-position symmetry is also proved in
[BB21] (and also [Buf20]).

In this paper we present a new shift-invariance property, concerning the
multi-time distribution of this colored TASEP. A major motivation and
application of our result is to prove a conjectured identity between the
directed last-passage percolation with i.i.d. exponential weights (LPP), and
the oriented swap process (OSP), which is a type of random sorting networks,
and can be viewed as the colored TASEP in a finite interval. Using this
identity, we can use results from LPP to deduce asymptotic results of OSP. For
OSP we show convergence to the Airy2 process of the vector of the finishing
times, under the KPZ scaling; and the site where the last swap happens has
fluctuation in the order of $N^{2/3}$ (for OSP with $N$ numbers). In a smaller
scale, the finishing times converge to random walks in total variation
distance.

Our shift-invariance is in a similar spirit as various other hidden invariance
in exactly solvable models, from [BGW19, Dau20, Gal20], as will be discussed
in Section 1.2; however, the approach we take is quite different from these
previous works. In particular, we avoid working with formulae from algebraic
combinatorics or representation theory. Our starting point is a crucial input
of a shift-invariance property of the colored six-vertex model, proved in
[Gal20]. Our central idea is to use analyticity of the distribution functions,
combined with independence properties of the colored TASEP in different space-
time areas. See Section 2.1 for a more detailed explanation of our strategy.

###  1.1 Passage times and last-passage percolation

To state our results we start with the following setups. For the colored TASEP
starting from the identity map, it is also equivalent to the coupling of a
family of (uncolored) TASEP, starting with step initial conditions. More
precisely, for each $A\in\mathbb{Z}$, we consider a TASEP such that initially,
there is a particle on each site $\leq A$, and each site $>A$ is empty. For
time $t\geq 0$, we denote the configuration as
$\mu^{A}_{t}:\mathbb{Z}\to\\{0,\infty\\}$, where $0$ denotes a particle and
$\infty$ denotes a hole. We couple $\mu^{A}=(\mu^{A}_{t})_{t\geq 0}$ for all
$A\in\mathbb{Z}$, such that the jump of particles follow the same Poisson
clock. Such $\mu^{A}$ can be obtained from $\zeta=(\zeta_{t})_{t\geq 0}$: we
just let $\mu^{A}_{t}(x)=0$ if $\zeta_{t}(x)\leq A$, and
$\mu^{A}_{t}(x)=\infty$ if $\zeta_{t}(x)>A$. We can also recover $\zeta$ from
such $\mu^{A}$ for all $A\in\mathbb{Z}$, by letting
$\zeta_{t}(x)=\min\\{A\in\mathbb{Z}:\mu^{A}_{t}(x)=0\\}$.

The evolution of the colored TASEP $\zeta$ could also be described by the
following family of random variables, which we call _passage times_. For each
$A\in\mathbb{Z}$ and $B,C\in\mathbb{N}$, denote

$\displaystyle T_{B,C}^{A}$ $\displaystyle=\inf\\{t\geq 0:|\\{x\geq
A+B+1-C:\zeta_{t}(x)\leq A\\}|\geq C\\}$ $\displaystyle=\inf\\{t\geq
0:|\\{x\geq A+B+1-C:\mu^{A}_{t}(x)=0\\}|\geq C\\},$

i.e., $T_{B,C}^{A}$ is the first time, when in $\mu^{A}$ there are at least
$C$ particles on or to the right of site $A+B+1-C$. From
$\\{T_{B,C}^{A}\\}_{B,C\in\mathbb{N}}$ we can recover the evolution of
$\mu^{A}$. We take such random variables and notations partially due to the
connection between TASEP (uncolored) and LPP, dating back to Rost [Ros81]. We
now state this connection, and we start by formally defining the model of 2D
LPP (with i.i.d. exponential weights).

To each vertex $v\in\mathbb{Z}^{2}$ we associate an independent weight
$\omega(v)$ with $\operatorname{Exp}(1)$ distribution. For two vertices
$u,v\in\mathbb{Z}^{2}$, we say $u\leq v$ if $u$ is coordinate-wise less than
or equal to $v$. For such $u,v$ and any up-right path $\gamma$ from $u$ to
$v$, we define the _passage time of the path_ to be

$L(\gamma):=\sum_{w\in\gamma}\omega(w).$

Then almost surely there is a unique up-right path from $u$ to $v$ that has
the largest passage time. We would always assume such uniqueness in this
paper, and we call this path the _geodesic_ $\Gamma_{u,v}$, and call
$L_{u,v}:=L(\Gamma_{u,v})$ the _passage time from $u$ to $v$_.

For any $A\in\mathbb{Z}$, we can couple $\mu^{A}$ with a family of i.i.d.
$\operatorname{Exp}(1)$ random variables
$\\{\omega^{A}(v)\\}_{v\in\mathbb{N}^{2}}$, where for any $B,C\in\mathbb{N}$,
$\omega^{A}((B,C))$ would be the waiting time for the $B$-th leftmost hole to
swap with the $C$-th rightmost particle. We note that at any time $t$, the
$B$-th leftmost hole is to the right of the $C$-th rightmost particle, if and
only if there are at least $C$ particles on or to the right of site $A+B+1-C$.
Thus for the swap (between the $B$-th leftmost hole and the $C$-th rightmost
particle), one starts the ‘waiting’ when there are $C-1$ particles on or to
the right of site $A+B+2-C$, and another particle arrives at site $A+B-C$.
Thus we can formally write

$\omega^{A}((B,C))=T^{A}_{B,C}-T^{A}_{B-1,C}\vee T^{A}_{B,C-1},$

where we assume that $T^{A}_{B-1,C}=0$ if $B=1$, and $T^{A}_{B,C-1}=0$ if
$C=1$. Such $\omega^{A}((B,C))$ are i.i.d. $\operatorname{Exp}(1)$ for
$B,C\in\mathbb{N}$, since in $\mu^{A}$, the jumps happen with rate $1$
independently.

Let $L^{A}_{u,v}$ denote the passage time from $u$ to $v$ under the random
field $\omega^{A}$. Then we would have $L^{A}_{(1,1),(B,C)}=T^{A}_{B,C}$ for
any $B,C\in\mathbb{N}$, which explains the name of ‘passage times’ for
$T^{A}_{B,C}$.

From this connection between LPP and TASEP, we get a coupling of random fields
$\omega^{A}$ for different $A$. We now give a more direct but slightly more
involved description of such coupling. From $\omega^{A}$ one can get
$\omega^{A+1}$ in the following way. Take a family of i.i.d.
$\operatorname{Exp}(1)$ random variables $\\{E_{i,j}\\}_{i,j\in\mathbb{N}}$,
independent of $\omega^{A}$. We then recursively define a function
$\pi:\mathbb{Z}_{\geq 0}\to\mathbb{N}$ and a sequence of times
$\\{J_{i}\\}_{i=0}^{\infty}$, as follows. Let $\pi(0)=1$ and $J_{0}=0$. Given
any $\pi(i)$ and $J_{i}$, we let

$\pi(i+1)=\inf\\{j\geq\pi(i):(L^{A}_{(1,1),(i+1,j)}-L^{A}_{(1,1),(i+2,j-1)}\vee
J_{i})\geq E_{i+1,j}\\},$

and $J_{i+1}=L^{A}_{(1,1),(i+2,\pi(i+1)-1)}\vee J_{i}+E_{i+1,\pi(i+1)}$. Then
for $B,C\in\mathbb{N}$, we let

$L^{A+1}_{(1,1),(B,C)}=\begin{cases}L^{A}_{(1,1),(B,C-1)},\quad&C>\pi(B),\\\
L^{A}_{(1,1),(B+1,C)},\quad&C<\pi(B),\\\ J_{B},\quad&C=\pi(B).\end{cases}$

From this we can get $\omega^{A+1}$ via
$\omega^{A+1}_{B,C}=L^{A+1}_{(1,1),(B,C)}-L^{A+1}_{(1,1),(B-1,C)}\vee
L^{A+1}_{(1,1),(B,C-1)}$. We note that the above random variables are defined
from the colored TASEP: each $E_{i,j}$ corresponds to the waiting time for the
$i$-th right jump of the particle colored $A+1$, when there are $j-1$
particles with smaller colors to its right; each $J_{i}$ corresponds to the
time when the particle colored $A+1$ makes the $i$-th jump to the right, and
$\pi(i)-1$ corresponds to the number of particles with smaller colors to its
right at time $J_{i}$.

In other words, the function $\pi$ splits $\omega^{A}$ into two parts; and by
shifting the upper left part by $(0,1)$ and shifting the lower right part by
$(-1,0)$, we get $\omega^{A+1}$, except for some vertices around the boundary.
By repeating this procedure, we can get $\omega^{A^{\prime}}$ for any
$A^{\prime}>A$; and by the reflection symmetry we can do a similar procedure
to get $\omega^{A^{\prime}}$ for any $A^{\prime}<A$. More precisely, for any
$k\in\mathbb{N}$, we can find non-decreasing function
$\pi_{1},\ldots,\pi_{k}:\mathbb{N}\to\mathbb{N}$, with
$\pi_{1}<\cdots<\pi_{k}$, such that they split $\omega^{A}$ into $k+1$ parts.
For the $i$-th part from the top, we shift it by $(1-i,k+1-i)$, and we would
get $\omega^{A+k}$, except for vertices around the boundaries.

###  1.2 Colored TASEP identities

$x+y=2$

$x+y=2$

Figure 1:  By Theorem 1.1, the maximum of the blue passage times, of the green
passage times, and the red passage time have the same joint distributions, in
both diagrams. Note that this is not the shift-invariance of LPP, since for
each starting point $(1+A,1-A)$, the last-passage time is for a different set
of random field $\omega^{A}$, associated with the TASEP $\mu^{A}$.

We now state our shift-invariance of $\zeta$, using a graphical
representation. For each $A\in\mathbb{Z}$ and $B,C\in\mathbb{N}$, let
$\mathcal{R}^{A}_{B,C}$ be the rectangle of lattice points
$[1+A,B-A]\times[1+A,C-A]\cap\mathbb{Z}^{2}$. From the connection with LPP,
$T^{A}_{B,C}$ can be thought as the passage time from the bottom-left corner
to the up-right corner of $\mathcal{R}^{A}_{B,C}$, where the random field is
$\omega^{A}$ shifted by $(A,-A)$. For two rectangles
$\mathcal{R},\mathcal{R}^{\prime}\subset\mathbb{Z}^{2}$, we say
$\mathcal{R}\leq\mathcal{R}^{\prime}$ if the projection of $\mathcal{R}$ onto
the first coordinate contains the projection of $\mathcal{R}^{\prime}$ onto
the first coordinate; and the projection of $\mathcal{R}$ onto the second
coordinate is contained in the projection of $\mathcal{R}^{\prime}$ onto the
second coordinate. We say that $\mathcal{R}$ and $\mathcal{R}^{\prime}$ are
_ordered_ if $\mathcal{R}\leq\mathcal{R}^{\prime}$ or
$\mathcal{R}^{\prime}\leq\mathcal{R}$.

Our results state that one can shift these rectangles while the joint
distribution of the passage times is invariant, if certain ordering relations
are preserved.

######  Theorem 1.1.

Let $g\in\mathbb{N}$, $k_{1},\ldots,k_{g}\in\mathbb{N}$, and take
$A_{i,j}\in\mathbb{Z}$, $B_{i,j},C_{i,j}\in\mathbb{N}$, for all $1\leq i\leq
g$ and $1\leq j\leq k_{i}$. Let $1\leq\iota<g$, and for any $1\leq i\leq g$
and $1\leq j\leq k_{i}$ we let $A_{i,j}^{+}=A_{i,j}+\mathds{1}[i>\iota]$.
Suppose that for any $1\leq i<i^{\prime}\leq g$, and $1\leq j\leq k_{i},1\leq
j^{\prime}\leq k_{i^{\prime}}$ we have
$\mathcal{R}^{A_{i,j}}_{B_{i,j},C_{i,j}}\leq\mathcal{R}^{A_{i^{\prime},j^{\prime}}}_{B_{i^{\prime},j^{\prime}},C_{i^{\prime},j^{\prime}}}$and
$\mathcal{R}^{A_{i,j}^{+}}_{B_{i,j},C_{i,j}}\leq\mathcal{R}^{A_{i^{\prime},j^{\prime}}^{+}}_{B_{i^{\prime},j^{\prime}},C_{i^{\prime},j^{\prime}}}$.
Then the vectors $\\{\max_{1\leq j\leq
k_{i}}T_{B_{i,j},C_{i,j}}^{A_{i,j}}\\}_{i=1}^{g}$ and $\\{\max_{1\leq j\leq
k_{i}}T_{B_{i,j},C_{i,j}}^{A_{i,j}^{+}}\\}_{i=1}^{g}$ are equal in
distribution.

See Figure 1 for an illustration of an equal in distribution that can be
achieved with this theorem.

We also state the shift-invariance in another setting, with some slightly
different constraints on the parameters.

######  Theorem 1.2.

Let $g\in\mathbb{N}$, and $A_{i},A_{i}^{\prime}\in\mathbb{Z}$,
$B_{i},C_{i}\in\mathbb{N}$ for each $1\leq i\leq g$. Let $V_{i}$ be the
rectangle consisting of all
$(B,C)\in[1,B_{i}]\times[1,C_{i}]\cap\mathbb{Z}^{2}$, such that
$\mathcal{R}^{A_{j}}_{B_{j},C_{j}}$ and $\mathcal{R}^{A_{i}}_{B,C}$ are
ordered, $\mathcal{R}^{A_{j}^{\prime}}_{B_{j},C_{j}}$ and
$\mathcal{R}^{A_{i}^{\prime}}_{B,C}$ are ordered, for each $1\leq j\leq g$.
Then $\\{\\{T^{A_{i}}_{B,C}\\}_{(B,C)\in V_{i}}\\}_{i=1}^{g}$ has the same
distribution as $\\{\\{T^{A_{i}^{\prime}}_{B,C}\\}_{(B,C)\in
V_{i}}\\}_{i=1}^{g}$.

From these identities we get invariance for some related objects. For example,
in LPP one can locally construct geodesics using passage times; thus we
immediately get the following equal in distribution of geodesics.

For each $A\in\mathbb{Z}$ and $B,C\in\mathbb{N}$, we let $\Gamma^{A}_{B,C}$ be
the LPP geodesic from $(1,1)$ to $(B,C)$, with the random field $\omega^{A}$
given by $\mu^{A}$.

######  Corollary 1.3.

In the setting of Theorem 1.2, let $W_{i}\subset V_{i}$ consist of all
$(B,C)\in\mathbb{Z}^{2}$, such that
$\\{(B-1,C),(B,C-1)\\}\cap\mathbb{N}^{2}\subset V_{i}$. Then
$\\{\Gamma^{A_{i}}_{B_{i},C_{i}}\cap W_{i}\\}_{i=1}^{g}$ has the same
distribution as $\\{\Gamma^{A_{i}^{\prime}}_{B_{i},C_{i}}\cap
W_{i}\\}_{i=1}^{g}$.

See Figure 2 for an illustration of Theorem 1.2 and Corollary 1.3.

$x+y=2$

$x+y=2$

Figure 2:  An illustration of Theorem 1.2 and Corollary 1.3: the green, red,
and blue passage times, and the shape of part of the geodesics, are all equal
in distribution, in the left and the right diagrams.

Our shift-invariance might look similar as various other hidden invariance in
exactly solvable models, from [BGW19, Dau20, Gal20], and we now explain the
relation between ours and these previous result.

With the connection to LPP, our results take a similar form as those in
[Dau20]. In particular, for the ordered relation between two lattice
rectangles $\mathcal{R},\mathcal{R}^{\prime}$, it is equivalent to the
following notion widely used in [Dau20]: for any up-right paths from the
bottom-left corner to the up-right corner in $\mathcal{R}$ and
$\mathcal{R}^{\prime}$ respectively, they must intersect. However, as noted
above, for $\mu^{A}$ with different $A\in\mathbb{Z}$, the corresponding LPP
random fields are different, and coupled in a non-trivial way, thus the above
identities do not follow from the results in [Dau20]. We also do not see a
proof our results using the framework or similar arguments as those in
[Dau20], via certain conditional independence obtained from the RSK
correspondence.

In [BGW19, Gal20], certain shift- and flip-invariance are proved for the
colored six-vertex model. Our colored TASEP can be obtained from the colored
six-vertex model, by passing the parameters there to a certain limit. As
pointed out in [BGR20, Remark 2.3], when passing the shift- or flip-invariance
from the colored six-vertex model to the colored TASEP, one would get equal in
distribution of the configuration at a single time (see e.g. [BGR20, Theorem
2.2] and Theorem 2.3 below). The shift-invariance of passage times (of Theorem
1.1 and 1.2) is effectively an equal in distribution concerning the
configurations in different times, thus does not follow from these results. On
the other hand, it seems that there is no corresponding arguments as those in
the proofs in [BGW19, Gal20] in the degenerated setting of the colored TASEP
model, since the full power of the colored stochastic six-vertex model would
be necessary in their proofs.

We also note that our Theorem 1.1 is in a spirit close to the main results in
[BGW19], for we require that all pairs of rectangles (of different $i$’s) are
ordered. It is asked as [BGW19, Conjecture 1.5] whether such shift-invariance
holds in more generality, with ordering imposed only for endpoints where
relative shift happens. This has been answered in [Gal20] and [Dau20] in
different settings. It would be natural to ask if similar extension holds for
our results, i.e., are some of the ordering inequalities in Theorem 1.1 not
necessary for the shift-invariance to hold? Our Theorem 1.2 can be viewed as
one step toward this, for there we allow rectangles with the same $A_{i}$ to
be not ordered. See Section 6.1 for some further discussions on this.

###  1.3 The oriented swap process and the conjectured identity

Consider the Cayley graph of the symmetric group $S_{N}$, generated by swaps
of numbers at adjacent sites $k$ and $k+1$, for each $1\leq k\leq N-1$. A
_sorting network_ is a shortest path between the identity permutation
$(1,\ldots,N)$ and the reverse permutation $(N,\ldots,1)$; or equivalently, it
is a sequence of $N(N-1)/2$ adjacent swaps, from the identity permutation to
the reverse permutation. We note that to make the number of swaps being
$N(N-1)/2$ (the smallest possible value), for any swap it must be that the a
number swaps with a larger number right next to it.

One natural way of defining a random sorting network is to assign equal
probability to each sorting network. Such model has been extensively studied
in [AHRV07, AGH12, Roz16, GR19, DV20, Dau18]. A different natural way of
defining a random sorting network is the so-called oriented swap process
(OSP), from [AHR09]. One lets the permutation evolve in a continuous way, such
that at any time, for each two adjacent sites, if the number at the left site
is smaller than the number at the right site, with rate $1$ these two numbers
swap. More formally, one can think of OSP as a finite interval version of the
colored TASEP. Consider $N$ particles on the finite lattice
$\\{1,\ldots,N\\}$, such that initially (at time $0$) the particle at site
each $k$ is colored $k$. For each edge $(k,k+1)$ (for $1\leq k\leq N-1$),
there is an independent Poisson clock that rings at rate $1$; and whenever it
rings, the particles occupying the sites $k$ and $k+1$ would attempt to swap.
Suppose that these two particles have colors $i$ and $j$ respectively, then
the the swap succeeds only if $i<j$, i.e., only if the swap increases the
number of inversions in the sequence of particle colors.

We consider the vector of _finishing times_
$\mathbf{U}_{N}=(U_{N}(1),\ldots,U_{N}(N-1))$, where $U_{N}(k)$ is the last
time such that a swap happens between the sites $k$ and $k+1$. As has been
observed in [AHR09], for each individual $k$, the time $U_{N}(k)$ has the same
distribution as $L_{(1,1),(k,N-k)}$. Using this, it is proved that if we let
$N\to\infty$ and assume $k/N\to y$ for some $0<y<1$, then $U_{N}(k)$ would
grow linearly in $N$ with a fluctuation in the order of $N^{1/3}$, and (after
appropriate rescaling) the fluctuation converges to GUE Tracy-Widom
distribution ([AHR09, Theorem 1.6]).

It is also asked in [AHR09] about the asymptotic behaviour of the _absorbing
time_ of OSP, i.e., $\max_{1\leq k\leq N-1}U_{N}(k)$. It is conjectured by
Bisi, Cunden, Bibbson and Romik that the vector $\mathbf{U}_{N}$ and
$\\{L_{(1,1),(k,N-k)}\\}_{k=1}^{N-1}$ are equal in distribution ([BCGR20a,
Conjecture 1.2] and [BCGR20b, Conjecture 1.2]); and conditioned on such equal
in distribution they show the that the absorbing time of OSP (after
appropriate rescaling) converges to the GOE Tracy-Widom distribution.

Starting from this, in [BGR20] it is proved that that $\max_{1\leq k\leq
N-1}U_{n}(k)$ has the same distribution as $\max_{1\leq k\leq
N-1}L_{(1,1),(k,N-k)}$, using equal in distribution identities from the
colored six-vertex model, obtained in [BGW19]. The later corresponds to the
passage time of TASEP with flat initial condition, and it known to converge to
the Tracy-Widom GOE distribution (see e.g. [BFPS07, Sas05]). Thus the OSP
absorbing time convergence problem is settled in [BGR20]. However, the joint
equal in distribution between $\mathbf{U}_{N}$ and
$\\{L_{(1,1),(k,N-k)}\\}_{k=1}^{N-1}$ remains open. As pointed out in [BGR20],
such joint equal in distribution does not followed directly from any known
bijections, and also escapes the generality of the method taken there, and
some new ideas would be needed.

In [BCGR20a], several other special cases of the joint equal in distribution
have been verified. For example, it is shown that the equal in distribution
holds for $2\leq N\leq 6$, by a computer assisted proof using the equivalent
combinatorial formulation (see Section 1.3.2); and it is also shown that
$(U_{N}(1),U_{N}(N-1))$ has the same distribution as
$(L_{(1,1),(1,N-1)},L_{(1,1),(N-1,1)})$.

Using Theorem 1.1, we prove the desired joint equal in distribution, thus
resolve [BCGR20a, Conjecture 1.2] (also stated as [BGR20, Conjecture 1.3]).

######  Theorem 1.4.

The vectors $\mathbf{U}_{N}$ and $\\{L_{(1,1),(k,N-k)}\\}_{k=1}^{N-1}$ are
equal in distribution.

####  1.3.1 Asymptotic results

With the equal in distribution of Theorem 1.4, we can deduce results on the
OSP finishing times from corresponding LPP results, strengthening results in
[AHR09].

Let $\mathcal{A}_{2}$ denote the Airy2 process on $\mathbb{R}$, which is
stationary and ergodic, and $\mathcal{A}_{2}(0)$ has the GUE Tracy-Widom
distribution; then the fluctuation of the vector $\mathbf{U}_{N}$ would
converge to $\mathcal{A}_{2}$ minus a parabola.

######  Theorem 1.5.

For any $y\in(0,1)$, as $N\to\infty$, the function

$x\mapsto\frac{(y(1-y))^{1/6}}{(1+2\sqrt{y(1-y)})^{2/3}N^{1/3}}(U_{N}(\lfloor
yN+xN^{2/3}\rfloor)-(1+2\sqrt{y(1-y)})N-\frac{1-2y}{\sqrt{y(1-y)}}xN^{2/3})$

weakly converges to $\mathcal{A}_{2}(x)-x^{2}$, in the topology of uniform
convergence on compact sets.

We consider the _last swap location_ $k_{*}\in\\{1,\cdots,N-1\\}$, such that
the last swap is between sites $k_{*}$ and $k_{*}+1$. We then get the
following convergence about $k_{*}$.

######  Theorem 1.6.

As $N\to\infty$, $\frac{k_{*}-N/2}{N^{2/3}}$ would converge in distribution,
to $\operatorname{argmax}_{x}\mathcal{A}_{2}(x)-x^{2}$.

In a scale smaller than $N^{2/3}$, the local fluctuations would be simple
random walks.

######  Theorem 1.7.

Take any $y\in(0,1)$, and positive integers $K_{N}$ such that
$N^{-2/3}K_{N}\to 0$ as $N\to\infty$. Consider two random functions
$f_{N},g_{N}:[-K_{N},K_{N}]\cap\mathbb{Z}\to\mathbb{R}$, where
$f_{N}(x)=U_{N}(\lfloor yN\rfloor+x)-U_{N}(\lfloor yN\rfloor+x)$, and $g_{N}$
is a two-sided random walk, such that $g_{N}(x+1)-g_{N}(x)$ are i.i.d. for
each $-K_{N}\leq x<K_{N}$, with

$\mathbb{P}[g_{N}(x+1)-g_{N}(x)=t]=\begin{cases}\frac{\sqrt{y(1-y)}}{1+2\sqrt{y(1-y)}}e^{-\frac{\sqrt{y}t}{\sqrt{y}+\sqrt{1-y}}}\;\;&t\geq
0,\\\
\frac{\sqrt{y(1-y)}}{1+2\sqrt{y(1-y)}}e^{\frac{\sqrt{1-y}t}{\sqrt{y}+\sqrt{1-y}}}\;\;&t<0.\end{cases}$

Then the total variation distance between $f_{N}$ and $g_{N}$ decays to zero,
as $N\to\infty$.

Using the shift-invariance, we can also get the distribution of the OSP local
dynamics, near the finishing times. As an example, the following result can be
directly deduced from Theorem 1.7.

For any $1\leq k\leq N$, we consider the last jump of the number $k$ in OSP
(of size $N$), and we denote $\operatorname{Left}(N,k)$ as the event where the
last jump of $k$ is to the left. Noting that this event
$\operatorname{Left}(N,k)$ is equivalent to that $U_{N}(N+1-k)>U_{N}(N-k)$
(assuming that $U_{N}(0)=U_{N}(N)=0$), we immediately get the following
result.

######  Corollary 1.8.

Take any $y\in(0,1)$, and a sequence of integers $k_{N}$ such that
$N^{-1}k_{N}\to y$ as $N\to\infty$. Then we have that
$\mathbb{P}[\operatorname{Left}(N,k_{N})]\to\frac{\sqrt{y}}{\sqrt{y}+\sqrt{1-y}}$.

####  1.3.2 An equivalent formulation: Young tableaux and sorting networks

In [BCGR20a], it is proved that there is an equivalent formulation of Theorem
1.4 in combinatorics, which gives an identity between rational functions
raising from Young tableaux and sorting networks, and could be seen as an
extension of the Edelman-Greene correspondence [EG87]. We record this result
here.

We would mostly follow the notations in [BCGR20a]. Denote $\delta_{N}$ as the
Young diagram of $N-1$ rows, where the $k$-th row has $N-k$ boxes, and let
$\operatorname{SYT}(\delta_{N})$ denote all Young tableaux with shape
$\delta_{N}$, i.e., all $\lambda=\\{\lambda_{i,j}\\}_{i,j\geq 1,i+j\leq N}$,
such that these numbers are precisely $1,\ldots,N(N-1)/2$, and
$\lambda_{i,j}<\lambda_{i+1,j}\wedge\lambda_{i,j+1}$, for any $i,j\geq 1$,
$i+j\leq N-1$. For each $\lambda\in\operatorname{SYT}(\delta_{N})$, we denote
$\operatorname{cor}_{\lambda}=(\lambda_{N-1,1},\ldots,\lambda_{1,N-1})$ as the
vector of the last entries of each row. Let $\sigma_{\lambda}\in S_{N-1}$ be a
permutation, such that for any $1\leq i<j\leq N-1$, we have
$\sigma_{\lambda}(i)<\sigma_{\lambda}(j)$ if and only if
$\operatorname{cor}_{\lambda}(i)<\operatorname{cor}_{\lambda}(j)$. We let
$\overline{\operatorname{cor}}_{\lambda}$ be the increasing rearrangement of
$\operatorname{cor}_{\lambda}$, i.e.
$\overline{\operatorname{cor}}_{\lambda}=\operatorname{cor}_{\lambda}\circ\sigma_{\lambda}^{-1}$.
We also define a $N(N-1)/2$ dimensional vector $\operatorname{deg}_{\lambda}$
as follows: we consider the sequence of Young diagrams
$\emptyset=\delta_{\lambda}^{(0)},\delta_{\lambda}^{(1)},\ldots,\delta_{\lambda}^{(N(N-1)/2)}=\delta_{N}$,
such that each $\delta_{\lambda}^{(k)}$ contains all boxes $(i,j)$ with
$\lambda_{i,j}\leq k$. Then for each $0\leq k\leq N(N-1)/2-1$, we let
$\operatorname{deg}_{\lambda}(k)$ be the number of boxes
$(i,j)\subset\delta_{N}\setminus\delta_{\lambda}^{(k)}$, such that
$\delta_{\lambda}^{(k)}\cup\\{(i,j)\\}$ is a Young subdiagram of $\delta_{N}$.
For each permutation $\sigma\in S_{N-1}$, we take the rational function
$F_{\sigma}\in\mathbb{C}(x_{1},\ldots,x_{N-1})$ as

$F_{\sigma}(x_{1},\ldots,x_{N-1})=\sum_{\lambda\in\operatorname{SYT}(\delta_{N}),\sigma_{\lambda}=\sigma}\prod_{k=1}^{N-1}\prod_{i=\overline{\operatorname{cor}}_{\lambda}(k-1)+1}^{\overline{\operatorname{cor}}_{\lambda}(k)}\frac{1}{x_{k}+\operatorname{deg}_{\lambda}(i)}.$

There is a similar set of quantities in the sorting network. Let
$\operatorname{SN}_{N}$ be the collection of all sorting networks from
$(1,\ldots,N)$ to $(N,\ldots,1)$, where each
$s=(s_{1},\ldots,s_{N(N-1)/2})\in\operatorname{SN}_{N}$ is a sequence of
numbers, each in $\\{1,\ldots,N-1\\}$, such that the numbers at sites $s_{k}$
and $s_{k}+1$ are swapped at step $k$. We let
$\operatorname{last}_{s}=(\operatorname{last}_{s}(1),\ldots,\operatorname{last}_{s}(N-1))$
such that $\operatorname{last}_{s}(k)=\max\\{1\leq i\leq N(N-1)/2:s_{i}=k\\}$
for each $1\leq k\leq N-1$. Let $\sigma_{s}\in S_{N-1}$ be a permutation, such
that for any $1\leq i<j\leq N-1$, we have $\sigma_{s}(i)<\sigma_{s}(j)$ if and
only if $\operatorname{last}_{s}(i)<\operatorname{last}_{s}(j)$, and let
$\overline{\operatorname{last}}_{s}=\operatorname{last}_{s}\circ\sigma_{s}$.
For each $0\leq k\leq N(N-1)/2-1$, we let $\operatorname{deg}_{s}(k)=|\\{1\leq
i\leq N-1:v^{(k)}(i)<v^{(k)}(i+1)\\}|$, where $v^{(k)}\in S_{N-1}$ is the
configuration of the sorting network $s$ after the $k$-th step. For each
permutation $\sigma\in S_{N-1}$, we take the rational function
$G_{\sigma}\in\mathbb{C}(x_{1},\ldots,x_{N-1})$ as

$G_{\sigma}(x_{1},\ldots,x_{N-1})=\sum_{s\in\operatorname{SN}_{N},\sigma_{s}=\sigma}\prod_{k=1}^{N-1}\prod_{i=\operatorname{last}_{s}(k-1)+1}^{\operatorname{last}_{s}(k)}\frac{1}{x_{k}+\operatorname{deg}_{s}(i)}.$

As proved in [BCGR20a], from the density functions and taking certain Fourier
transforms, Theorem 1.4 is equivalent to the following.

######  Theorem 1.9.

For $N\geq 2$ and any $\sigma\in S_{N-1}$, we have that

$F_{\sigma}(x_{1},\ldots,x_{N-1})=G_{\sigma}(x_{1},\ldots,x_{N-1}).$

We remark that, as pointed out in [BCGR20a], this does not directly follow
from the Edelman-Greene correspondence. If one denotes this correspondence as
a bijection
$\operatorname{EG}_{N}:\operatorname{SYT}_{N}\to\operatorname{SN}_{N}$, then
their would be
$\operatorname{last}_{\operatorname{EG}_{N}(\lambda)}=\operatorname{cor}_{\lambda}$
and $\sigma_{\operatorname{EG}_{N}(\lambda)}=\sigma_{\lambda}$ for any
$\lambda\in\operatorname{SYT}_{N}$; and one also has that
$|\\{\lambda\in\operatorname{SYT}(\delta_{N}),\sigma_{\lambda}=\sigma\\}|=|\\{s\in\operatorname{SN}_{N},\sigma_{s}=\sigma\\}|$.
However, the identity that

$\prod_{k=1}^{N-1}\prod_{i=\overline{\operatorname{cor}}_{\lambda}(k-1)+1}^{\overline{\operatorname{cor}}_{\lambda}(k)}\frac{1}{x_{k}+\operatorname{deg}_{\lambda}(i)}=\prod_{k=1}^{N-1}\prod_{i=\operatorname{last}_{\operatorname{EG}(\lambda)}(k-1)+1}^{\operatorname{last}_{\operatorname{EG}(\lambda)}(k)}\frac{1}{x_{k}+\operatorname{deg}_{\operatorname{EG}(\lambda)}(i)}$

is not generally true for any $\lambda\in\operatorname{SYT}_{N}$.

### Organization of the remaining text

The remaining text would mainly focus on proving the above results. In Section
2 we state the general strategy, by explaining an input from the colored six-
vertex model, and sketching the proof of Theorem 1.1 for a simple example. In
Section 3 we prove some basic results in different aspects, which will be
repeatedly used in the proofs. Theorem 1.1 is proved in the next two sections.
We would use an induction in our proof, and Section 4 is for the setup and
framework, and Section 5 is for more detailed arguments. In Section 6 we
deduce Theorem 1.2 from Theorem 1.1, and we also discuss some possible further
extensions of the results in Section 6.1. In Section 7 we prove Theorem 1.4,
and explain how it implies the asymptotic results.

### Acknowledgement

The author would like to thank Jiaoyang Huang for first bringing the
conjectures in [BCGR20a] into his attention; and thank the organizers of the
BIRS workshop: Permutations and Probability, and a talk by Dan Romik, for
introducing some related backgrounds. The author would also like to thank
Vadim Gorin for some very valuable feedback on an earlier draft of this paper.

##  2 Input from the colored six-vertex model and proof strategy

In this section we explain the general approach to prove Theorem 1.1 and
Theorem 1.2.

We shall take an input from [Gal20], which is a distributional identity of the
colored six-vertex model, and we pass it to the colored TASEP limit. Similar
inputs from the colored six-vertex model to the colored TASEP have appeared in
[BGR20]. This gives a same-time distributional identity (Theorem 2.3 below).
Our main work is to upgrade it to a multi-time distributional identity, for
which we use an induction argument, exploiting the fact that the passage times
have analytic distribution functions, and some conditional independence of the
passage times.

To setup the arguments, we first state the colored six-vertex model input. In
Section 2.1 we will explain the upgrading strategy via a simple example.

Our notations for the colored six-vertex model follow those in [BGW19]. We
consider the model as random colored up-right paths in the positive quadrant
$\mathbb{N}^{2}$. All the paths enter the quadrant from the left boundary,
such that for each $i\in\mathbb{N}$, there is a path of color $i$ entering
from the left in row $i$. Given the entering paths, they progress in the up-
right direction within the quadrant. For each vertex of the lattice, given the
colors of the entering paths along the bottom and left adjacent edges, we
choose the colors of the exiting paths along the top and right edges according
to the following probabilities (see Figure 3). Let $0\leq b_{2}<b_{1}<1$ be
two parameters. Suppose the path entering from the bottom is in color $i$, and
the path entering from the left is in color $j$. If $i\leq j$, then with
probability $b_{1}$, the path exiting from the top is in color $i$, and the
path exiting from the right is in color $j$; and with probability $1-b_{1}$,
the path exiting from the top is in color $j$, and the path exiting from the
right is in color $i$. If $i>j$, it has the same transition probability, with
$b_{1}$ replaced by $b_{2}$. We also use color $0$ to encode absence of path.

$j$$i$$j$$i$$i\leq j$$i>j$$b_{1}$$1-b_{1}$$b_{2}$$1-b_{2}$ Figure 3:
Probabilities at each vertex of the colored six-vertex model.

We next define the height function. For each $m\in\mathbb{N}$ and
$x,y\in(\mathbb{N}-\frac{1}{2})^{2}$, we denote $\mathcal{H}^{m}_{6v}(x,y)$ as
the number of paths that are in color $\geq m$, and pass below $(x,y)$.

A particular case of the main result in [Gal20, Theorem 1.6] is as follows, in
the above notations.

######  Theorem 2.1.

Let $l,n\in\mathbb{N}$, $\\{m_{i}\\}_{i=1}^{l}\in\mathbb{N}^{l}$,
$\\{m_{i}^{\prime}\\}_{i=1}^{n}\in\mathbb{N}^{n}$, and
$\\{(x_{i},y_{i})\\}_{i=1}^{l}\in(\mathbb{N}-\frac{1}{2})^{2l}$,
$\\{(x_{i}^{\prime},y_{i}^{\prime})\\}_{i=1}^{n}\in(\mathbb{N}-\frac{1}{2})^{2n}$,
such that

  1. 1.

$\max_{1\leq i\leq l}m_{i}<\min_{1\leq i\leq n}m_{i}^{\prime}$,

  2. 2.

$x_{1}\leq\cdots\leq x_{l}\leq x_{1}^{\prime}\leq\cdots\leq x_{n}^{\prime}$,
and $y_{1}\geq\cdots\geq y_{l}\geq y_{1}^{\prime}\geq\cdots\geq
y_{n}^{\prime}$.

Then these $l+n$ dimensional vectors
$(\\{\mathcal{H}^{m_{i}}_{6v}(x_{i},y_{i})\\}_{i=1}^{l},\\{\mathcal{H}^{m_{i}^{\prime}}_{6v}(x_{i}^{\prime},y_{i}^{\prime})\\}_{i=1}^{n})$
and
$(\\{\mathcal{H}^{m_{i}+1}_{6v}(x_{i},y_{i}+1)\\}_{i=1}^{l},\\{\mathcal{H}^{m_{i}^{\prime}}_{6v}(x_{i}^{\prime},y_{i}^{\prime})\\}_{i=1}^{n})$
would have the same distribution.

We next state the limit transition to TASEP. It is first observed in [BCG16],
and then proved in [Agg17], for the six-vertex model without colors; the
colored version follows the same proof. For this we introduce the height
function: for any $A\in\mathbb{Z}$ and $B\in\mathbb{N}$, let $h_{A,B}(t)$ be
the number of particles with color $\leq A$ at site $\geq B$ at time $t$; or
equivalently, it is the number of particles at site $\geq B$ in $\mu^{A}_{t}$.
For any $C\in\mathbb{N}$, the event $I_{A,B,C}^{t}$ would be equivalent to
$h_{A,B}(t)\geq C$.

######  Theorem 2.2.

Take $b_{1}=\varepsilon$ and $b_{2}=0$, then there is

$\mathcal{H}_{6v}^{A+1}(\lfloor\varepsilon^{-1}t\rfloor+1/2,\lfloor\varepsilon^{-1}t\rfloor+B-1/2)+A-B+1\to
h_{A,B}(t),$

in the sense of joint convergence in distribution of any finitely many
$(t,A,B)\in[0,\infty)\times\mathbb{Z}_{\geq 0}\times\mathbb{Z}$.

From this and Theorem 2.1, we get the following single time equal in
distribution. For each $A\in\mathbb{Z}$ and $B,C\in\mathbb{N}$, let
$I_{A,B,C}^{t}$ be the event where $T_{B,C}^{A}\leq t$.

######  Theorem 2.3.

Suppose that $l,n\in\mathbb{N}$, and $\\{A_{i}\\}_{i=1}^{l}\in\mathbb{Z}^{l}$,
$\\{A_{i}^{\prime}\\}_{i=1}^{n}\in\mathbb{Z}^{n}$,
$\\{B_{i}\\}_{i=1}^{l},\\{C_{i}\\}_{i=1}^{l}\in\mathbb{N}^{l}$,
$\\{B_{i}^{\prime}\\}_{i=1}^{n},\\{C_{i}^{\prime}\\}_{i=1}^{n}\in\mathbb{N}^{n}$,
such that

$A_{1},\ldots,A_{l}<A_{1}^{\prime},\ldots,A_{n}^{\prime},$

and

$A_{1}+B_{1}-C_{1},\ldots,A_{l}+B_{l}-C_{l}\geq
A_{1}^{\prime}+B_{1}^{\prime}-C_{1}^{\prime},\ldots,A_{n}^{\prime}+B_{n}^{\prime}-C_{n}^{\prime}.$

Then for any $t>0$, we have

$\mathbb{P}\left[\left(\bigcap_{i=1}^{l}I_{A_{i},B_{i},C_{i}}^{t}\right)\cap\left(\bigcap_{i=1}^{n}I_{A_{i}^{\prime},B_{i}^{\prime},C_{i}^{\prime}}^{t}\right)\right]=\mathbb{P}\left[\left(\bigcap_{i=1}^{l}I_{A_{i}+1,B_{i},C_{i}}^{t}\right)\cap\left(\bigcap_{i=1}^{n}I_{A_{i}^{\prime},B_{i}^{\prime},C_{i}^{\prime}}^{t}\right)\right].$

###### Proof.

It suffices to consider the case where each $A_{i}\geq 0$ and each
$A_{i}^{\prime}\geq 0$. Denote $\mathcal{E}$ as the event where

$\mathcal{H}_{6v}^{A_{i}+1}(\lfloor\varepsilon^{-1}t\rfloor+1/2,\lfloor\varepsilon^{-1}t\rfloor+A_{i}+B_{i}-C_{i}+1/2)\geq
B_{i}$

for each $1\leq i\leq l$, and $\mathcal{E}_{+}$ as the event where

$\mathcal{H}_{6v}^{A_{i}+2}(\lfloor\varepsilon^{-1}t\rfloor+1/2,\lfloor\varepsilon^{-1}t\rfloor+A_{i}+B_{i}-C_{i}+3/2)\geq
B_{i}$

for each $1\leq i\leq l$. Also denote $\mathcal{E}^{\prime}$ as the event
where

$\mathcal{H}_{6v}^{A_{i}^{\prime}+1}(\lfloor\varepsilon^{-1}t\rfloor+1/2,\lfloor\varepsilon^{-1}t\rfloor+A_{i}^{\prime}+B_{i}^{\prime}-C_{i}^{\prime}+1/2)\geq
B_{i}^{\prime}$

for each $1\leq i\leq n$. By Theorem 2.1 we have
$\mathbb{P}[\mathcal{E}\cap\mathcal{E}^{\prime}]=\mathbb{P}[\mathcal{E}_{+}\cap\mathcal{E}^{\prime}]$.
Then by Theorem 2.2, the conclusion follows by sending $\varepsilon\to 0$. ∎

In [BGR20], a slightly weaker result is stated ([BGR20, Theorem 2.2]), using
inputs from [BGW19]. Such same-time equal in distribution identity, combined
with the connection between OSP and the colored TASEP from [AHR09], would give
the equal in distribution between the OSP absorbing time $\max_{1\leq k\leq
N-1}U_{n}(k)$ and $\max_{1\leq k\leq N-1}L_{(1,1),(k,N-k)}$, as shown in
[BGR20].

To get our results, the main work would be to upgrade Theorem 2.3 to the
following multi-time equal in distribution.

######  Theorem 2.4.

Let $g\in\mathbb{N}$, $k_{1},\ldots,k_{g}\in\mathbb{N}$, and take
$A_{i,j}\in\mathbb{Z}$, $B_{i,j},C_{i,j}\in\mathbb{N}$, for all $1\leq i\leq
g$ and $1\leq j\leq k_{i}$. Let $1\leq\iota<g$, and for any $1\leq i\leq g$
and $1\leq j\leq k_{i}$ we let $A_{i,j}^{+}=A_{i,j}+\mathds{1}[i>\iota]$.
Suppose that for any $1\leq i<i^{\prime}\leq g$, and $1\leq j\leq k_{i},1\leq
j^{\prime}\leq k_{i^{\prime}}$ we have

$A_{i,j}\leq A_{i^{\prime},j^{\prime}},\quad A_{i,j}^{+}+B_{i,j}\geq
A_{i^{\prime},j^{\prime}}^{+}+B_{i^{\prime},j^{\prime}},\quad
A_{i,j}^{+}-C_{i,j}\geq
A_{i^{\prime},j^{\prime}}^{+}-C_{i^{\prime},j^{\prime}}.$

Then for any $t_{1},\ldots,t_{g}>0$, we have

$\mathbb{P}\left[\bigcap_{i=1}^{g}\bigcap_{j=1}^{k_{i}}I_{A_{i,j},B_{i,j},C_{i,j}}^{t_{i}}\right]=\mathbb{P}\left[\bigcap_{i=1}^{g}\bigcap_{j=1}^{k_{i}}I_{A_{i,j}^{+},B_{i,j},C_{i,j}}^{t_{i}}\right].$

We note that this is equivalent to Theorem 1.1. To see this, just note that
for any $A_{1},A_{2}\in\mathbb{Z}$ and $B_{1},B_{2},C_{1},C_{2}\in\mathbb{N}$,
the condition
$\mathcal{R}_{B_{1},C_{1}}^{A_{1}}\leq\mathcal{R}_{B_{2},C_{2}}^{A_{2}}$ is
equivalent to that $A_{1}\leq A_{2}$, and $A_{1}+B_{1}\geq A_{2}+B_{2}$,
$A_{1}-C_{1}\geq A_{2}-C_{2}$.

###  2.1 Proof strategy: a simple example

To better present our proof of Theorem 2.4, we sketch the proof of a simple
example, to illustrate how to prove multi-time equal in distribution from
Theorem 2.3.

######  Example 2.5.

Take some $B,C\in\mathbb{N}$, $B,C\geq 2$. For any $t_{1},t_{2}>0$, we have
that

$\mathbb{P}[T^{0}_{B,1}\leq t_{1},T^{0}_{1,C}\leq
t_{2}]=\mathbb{P}[T^{0}_{B,1}\leq t_{1},T^{1}_{1,C}\leq t_{2}].$

As we only concern certain passage times, we can simplify the model to contain
only two particles: the first one $P_{1}$ is the rightmost particle in
$\mu^{0}$, which starts at site $0$ and jumps to the right; the second one
$P_{2}$ is the leftmost hole in $\mu^{0}$ or $\mu^{1}$, which starts at site
$1$ or $2$, and jumps to the left. The waiting times for each jump is
$\operatorname{Exp}(1)$ independently, except for when $P_{1}$ is to left next
to $P_{2}$: then they swap with $\operatorname{Exp}(1)$ waiting time.

We just consider the case where $t_{1}<t_{2}$, and the case where
$t_{1}>t_{2}$ could follow a similar argument. A key observation is that,
since the time $T^{0}_{2,1}$, i.e. the time when $P_{1}$ arrives at site $2$,
the future evolution of $P_{1}$ and $P_{2}$ would be independent. This is
because, no matter $P_{2}$ starts from site $1$ or $2$, at time $T^{0}_{2,1}$
it must be to the left of $P_{1}$, thus these two particles have swapped
already, and all future waiting times would be independent. In particular,
$T^{0}_{B,1}-T^{0}_{2,1}$ would just be the sum of $B-2$ i.i.d.
$\operatorname{Exp}(1)$ random variables.

We consider functions $f:t\mapsto\mathbb{P}[T^{0}_{2,1}\leq t,T^{0}_{1,C}\leq
t_{2}]$ and $f^{+}:t\mapsto\mathbb{P}[T^{0}_{2,1}\leq t,T^{1}_{1,C}\leq
t_{2}]$. Thus it suffices to show that $f(t)=f^{+}(t)$ for any
$t\in[0,t_{2}]$. We use Theorem 2.3 to deduce this. For any large
$B^{\prime}\in\mathbb{N}$, $B^{\prime}\geq 2$, we have
$\mathbb{P}[T^{0}_{B^{\prime},1},T^{0}_{1,C}\leq
t_{2}]=\mathbb{P}[T^{0}_{B^{\prime},1},T^{1}_{1,C}\leq t_{2}]$. We can also
write

$\mathbb{P}[T^{0}_{B^{\prime},1},T^{0}_{1,C}\leq
t_{2}]=\int_{0}^{t_{2}}f(t)\frac{(t_{2}-t)^{B^{\prime}-3}e^{-(t_{2}-t)}}{(B^{\prime}-2)!}dt,$

and

$\mathbb{P}[T^{0}_{B^{\prime},1},T^{1}_{1,C}\leq
t_{2}]=\int_{0}^{t_{2}}f^{+}(t)\frac{(t_{2}-t)^{B^{\prime}-3}e^{-(t_{2}-t)}}{(B^{\prime}-2)!}dt.$

Thus we have

$\int_{0}^{t_{2}}(f(t)-f^{+}(t))(t_{2}-t)^{B^{\prime}-3}e^{-(t_{2}-t)}dt=0,\quad\forall
B^{\prime}\in\mathbb{N},\;B^{\prime}\geq 2.$ (2.1)

Suppose that the function $f-f^{+}$ is analytic, we can deduce that
$f-f^{+}=0$. Otherwise, one can find some $\beta\in\mathbb{Z}_{\geq 0}$ and
$D\neq 0$, such that $\lim_{t\to 0}t^{-\beta}(f(t)-f^{+}(t))=D$. By taking
$B^{\prime}$ large, we can make $(t_{2}-t)^{B^{\prime}-3}e^{-(t_{2}-t)}$ decay
fast as $t$ grows from $0$, and get a contradiction with (2.1).

Our proof for Theorem 2.4 follows the same strategy.

  1. 1.

We would find certain stopping times, which we call ‘cutting times’, like the
time $T^{0}_{2,1}$ in the above example. We prove that the evolution after
these times would be independent, for two sets of particles.

  2. 2.

The next step would be to show that the cutting time distribution would be
invariant under shift. For this we apply Theorem 2.3, and get formulae similar
to (2.1).

  3. 3.

We then prove that the probability density function of cutting times is
analytic.

  4. 4.

We analyze the transition probability from cutting times (i.e. the
distribution of $T^{0}_{B^{\prime},1}-T^{0}_{2,1}$ in the example): we would
show that by taking the corresponding $B^{\prime}$s large enough, the
transition distribution would concentrate on small $t$. Thus we conclude that
the cutting time distributions would be the same.

From Example 2.5 and these outlined steps, the main difference in the proof of
Theorem 2.4 is an induction argument, on the number of different times. In
Step 2, instead of directly using Theorem 2.3, we would use the induction
hypothesis.

We remark that in the setting of multiple times and multiple particles, the
independence property in Step 1 would be delicate. Thus a main difficulty in
our proof is to design the appropriate setup, mainly including the induction
setup and the choice of the cutting times, to get the independence property.

##  3 Preliminaries

In this section we give some basic results that would be used in our proofs. A
reader may skip proofs in this section for a moment, while the results and
some notations are used in the later text.

###  3.1 Projections to finitely many particles

For simplicity of notations and arguments, we introduce the following
‘projections’ of $\zeta$, which are (colored or uncolored) TASEPs with
finitely many particles.

First, for any $A\in\mathbb{Z}$ and $C\in\mathbb{N}$, we denote
$\mu^{A,C}=(\mu_{t}^{A,C})_{t\geq 0}$ as the process, where for each
$x\in\mathbb{Z}$ and $t\geq 0$, we have $\mu_{t}^{A,C}(x)=0$ if
$\mu_{t}^{A}(x)=0$ and $|\\{y\geq x:\mu_{t}^{A}(y)=0\\}|\leq C$; otherwise we
have $\mu_{t}^{A,C}(x)=\infty$. In words, $\mu_{t}^{A,C}$ keeps the $C$
rightmost particles in $\mu_{t}^{A}$ and changes other particles to holes.
This is also equivalent to applying to $\mu_{t}^{A}$ the ‘$C$ cut-off
operator’ from [AHR09] (see also Section 7). Then $\mu^{A,C}$ encodes a TASEP
with $C$ particles, starting from sites $A-C+1,\cdots,A$, where $0$ denotes
particles and $\infty$ denotes holes, and it evolves using the same Poisson
clock as $\zeta$.

We now take any $A\in\mathbb{Z}$ and $C\in\mathbb{N}$, and consider the
process $\hat{\mu}^{A,C}=(\hat{\mu}_{t}^{A,C})_{t\geq 0}$, defined as follows.
For each $x\in\mathbb{Z}$, $t\geq 0$, we denote
$\hat{\mu}^{A,C}_{t}(x)=\min\\{1\leq i\leq
C:\mu_{t}^{A-C+i,i}(x)=0\\}\cup\\{\infty\\}$.

We then verify the following statement. We note that we take a slightly misuse
of notions (here and for the rest of this paper): in a colored TASEP, unless
otherwise noted, a hole means a particle colored by $\infty$, and a particle
means one colored by a finite number.

######  Lemma 3.1.

The process $\hat{\mu}^{A,C}$ is a colored TASEP on $\mathbb{Z}$, where there
are only finitely many particles, at sites $A-C+1,\cdots,A$ initially, and are
colored by $1,\cdots,C$, respectively.

###### Proof.

For each $1\leq i<C$, $t\geq 0$, and $x\in\mathbb{Z}$, if
$\mu_{t}^{A-C+i,i}(x)=0$, we have that $\mu_{t}^{A-C+i}(x)=0$, and $|\\{y\geq
x:\mu_{t}^{A-C+i}(y)=0\\}|\leq i$. Thus we have $\mu_{t}^{A-C+i+1}(x)=0$, and
$|\\{y\geq x:\mu_{t}^{A-C+i+1}(y)=0\\}|\leq i+1$, so
$\mu_{t}^{A-C+i+1,i+1}(x)=0$. This means that there is exactly one
$x\in\mathbb{Z}$ with $\mu_{t}^{A-C+i,i}(x)=\infty$ and
$\mu_{t}^{A-C+i+1,i+1}(x)=0$, which is the only $x\in\mathbb{Z}$ with
$\hat{\mu}_{t}^{A,C}(x)=i$. We then get the conclusion from the fact that for
each $1\leq i\leq C$, $\mu^{A-C+i,i}$ is a TASEP with $i$ particles starting
from $A-C+1,\cdots,A-C+i$, and they evolve with the same Poisson clocks. ∎

While such projection is only on finitely many particles, it still contains
much information on passage times in the original process.

######  Lemma 3.2.

For any $A^{\prime}\in\mathbb{Z}$, $B^{\prime},C^{\prime}\in\mathbb{N}$, such
that $A^{\prime}\leq A$, $A^{\prime}-C^{\prime}\geq A-C$, the number
$T^{A^{\prime}}_{B^{\prime},C^{\prime}}$ is determined by
$\hat{\mu}_{t}^{A,C}$, as

$T^{A^{\prime}}_{B^{\prime},C^{\prime}}=\inf\\{t>0:|\\{x\in\mathbb{Z}:x\geq
A^{\prime}+B^{\prime}+1-C^{\prime},\hat{\mu}_{t}^{A,C}(x)\leq
A^{\prime}-A+C\\}|\geq C^{\prime}\\}.$

In particular, the configuration $\hat{\mu}_{t}^{A^{\prime},C^{\prime}}$ is
determined by $\hat{\mu}_{t}^{A,C}$.

###### Proof.

From the construction, for any $x\in\mathbb{Z}$, we have that
$\hat{\mu}_{t}^{A,C}(x)\leq A^{\prime}-A+C$ if and only if there is some
$1\leq i\leq A^{\prime}-A+C$, such that $\mu_{t}^{A-C+i,i}(x)=0$, thus if and
only if $\hat{\mu}_{t}^{A^{\prime},A^{\prime}-A+C}(x)<\infty$. Thus the right
hand side is the first time $t$ when $|\\{x\geq
A^{\prime}+B^{\prime}+1-C^{\prime}:\hat{\mu}_{t}^{A^{\prime},A^{\prime}-A+C}(x)<\infty\\}|\geq
C^{\prime}$. Since $A^{\prime}-A+C\geq C^{\prime}$, this is also the first
time $t$ when $|\\{x\geq
A^{\prime}+B^{\prime}+1-C^{\prime}:\hat{\mu}_{t}^{A^{\prime}}(x)<\infty\\}|\geq
C^{\prime}$, which is precisely $T^{A^{\prime}}_{B^{\prime},C^{\prime}}$. ∎

###  3.2 Poisson field

We use $\Pi$ to denote the Poisson clock of the original colored TASEP
$\zeta$; i.e. $\Pi$ is a Poisson field on $\mathbb{Z}\times[0,\infty)$, where
for each $x\in\mathbb{Z}$ and any $0\leq a<b$, $\Pi(\\{x\\}\times[a,b])$ would
be the number of times that the clock on the edge $(x-1,x)$ rings in the time
interval $[a,b]$. Throughout this paper, we shall also assume (the probability
$1$ event) that for any two different points $(x_{1},t_{1})$ and
$(x_{2},t_{2})$ in the Poisson field $\Pi$, we have $t_{1}\neq t_{2}$ and
$t_{1},t_{2}>0$.

We would use the following two lemmas, which say that for certain events on
passage times, they could be determined by $\Pi$ on some subsets of
$\mathbb{Z}\times[0,\infty)$.

######  Lemma 3.3.

For each $x\in\mathbb{Z}$ we let $t_{x}\in[0,\infty)\cup\\{\infty\\}$. Let
$U=\\{(x,t):x\in\mathbb{Z},t\leq t_{x}\\}$. Take any $A\in\mathbb{Z}$ and
$B,C\in\mathbb{N}$, and $0\leq s\leq t_{A+B-C+1}$. Then the event
$I_{A,B,C}^{s}\cap\left(\bigcap_{C^{\prime}=1}^{C}I_{A,B,C^{\prime}}^{t_{A+B-C^{\prime}+1}}\right)\cap\left(\bigcap_{B^{\prime}=1}^{B}I_{A,B^{\prime},C}^{t_{A+B^{\prime}-C+1}}\right)$
is determined by $\Pi$ on $U$.

###### Proof.

Denote the event in this lemma as $\mathcal{E}$. For each
$B^{\prime},C^{\prime}\in\mathbb{N}$, $B^{\prime}\leq B$ and $C^{\prime}\leq
C$, we can determine $T^{A}_{B^{\prime},C^{\prime}}$ as the smallest
$t>T^{A}_{B^{\prime}-1,C^{\prime}}\vee T^{A}_{B^{\prime},C^{\prime}-1}$; here
for any $B^{\prime},C^{\prime}$ we take
$T^{A}_{B^{\prime},0}=T^{A}_{0,C^{\prime}}=0$. We can then inductively
determine if the event $\mathcal{E}$ holds, as follows. Suppose that we’ve
determined $I^{t_{A+B^{\prime}-C^{\prime}}}_{A,B^{\prime}-1,C^{\prime}}$ and
$T^{A}_{B^{\prime}-1,C^{\prime}}\mathds{1}[T^{A}_{B^{\prime}-1,C^{\prime}}\leq
t_{A+B^{\prime}-C^{\prime}}]$, and also
$I^{t_{A+B^{\prime}-C^{\prime}+2}}_{A,B^{\prime},C^{\prime}-1}$ and
$T^{A}_{B^{\prime},C^{\prime}-1}\mathds{1}[T^{A}_{B^{\prime},C^{\prime}-1}\leq
t_{A+B^{\prime}-C^{\prime}+2}]$. Then by $\Pi$ on $U$ we can then determine if
$I^{t_{A+B^{\prime}-C^{\prime}+1}}_{A,B^{\prime},C^{\prime}}$ holds; and if it
holds, we can further determine the value of $T^{A}_{B^{\prime},C^{\prime}}$.
Thus the conclusion follows. ∎

######  Lemma 3.4.

Take any $A\in\mathbb{Z}$ and $B,C\in\mathbb{N}$, $s>0$, and a sequence of
integers $0=B_{0}\leq B_{1}\leq\cdots\leq B_{C}\leq C$. Suppose
$i_{*}=\max_{0\leq i\leq C}B_{i_{*}}=0$, we take $\\{t_{i}\\}_{i=1}^{C}$ such
that $t_{i}=0$ for any $i\leq i_{*}$, and $t_{i}<t_{i+1}<s$ for any $i_{*}\leq
i<C$. Let $U\subset\mathbb{Z}\times[0,\infty)$, where
$U=\bigcup_{i=1}^{C}\\{(x,t):x\geq A+B_{i}-i+1,t_{i}<t\leq s\\}$. Conditional
on $T^{A}_{B_{i},i}=t_{i}$ for each $1\leq i\leq C$, $B_{i}>0$, we have that
the event $I^{s}_{A,B,C}$ is determined by $\Pi$ on $U$.

###### Proof.

We take $T^{A}_{B^{\prime},0}=T^{A}_{0,C^{\prime}}=0$ for any
$B^{\prime},C^{\prime}\in\mathbb{N}$.

Let
$S=\\{(B^{\prime},C^{\prime})\in\mathbb{N}^{2}:B_{C^{\prime}}<B^{\prime}\leq
B\\}$. For $(B^{\prime},C^{\prime})\in S$, we can determine
$I^{s}_{A,B^{\prime},C^{\prime}}$ and
$T_{A,B^{\prime},C^{\prime}}\mathds{1}[T_{A,B^{\prime},C^{\prime}}\leq s]$ by
induction in $B^{\prime}+C^{\prime}$, as follows. Take any
$(B^{\prime},C^{\prime})\in S$. If $(B^{\prime}-1,C^{\prime})\in S$, we has
that $I^{s}_{A,B^{\prime}-1,C^{\prime}}$ and
$T^{A}_{B^{\prime}-1,C^{\prime}}\mathds{1}[T^{A}_{B^{\prime}-1,C^{\prime}}\leq
s]$ have been determined; otherwise we must have that
$B^{\prime}-1=B_{C^{\prime}}$, and
$T^{A}_{B^{\prime}-1,C^{\prime}}=t_{C^{\prime}}\leq s$. If
$(B^{\prime},C^{\prime}-1)\in S$, we have that
$I^{s}_{A,B^{\prime},C^{\prime}-1}$ and
$T^{A}_{B^{\prime},C^{\prime}-1}\mathds{1}[T^{A}_{B^{\prime},C^{\prime}-1}\leq
s]$ have been determined, and $T^{A}_{B^{\prime},C^{\prime}-1}\leq s$;
otherwise we must have that $C^{\prime}-1=0$, and
$T^{A}_{B^{\prime},C^{\prime}-1}=0$. In any case, if
$I^{s}_{A,B^{\prime}-1,C^{\prime}}$ or $I^{s}_{A,B^{\prime},C^{\prime}-1}$
does not hold, we have that $I^{s}_{A,B^{\prime},C^{\prime}}$ does not hold.
If $I^{s}_{A,B^{\prime}-1,C^{\prime}}\cap I^{s}_{A,B^{\prime},C^{\prime}-1}$
holds, we can determine $I^{s}_{A,B^{\prime},C^{\prime}}$ and
$T_{A,B^{\prime},C^{\prime}}\mathds{1}[T_{A,B^{\prime},C^{\prime}}\leq s]$, by
taking the smallest $t>T_{A,B^{\prime}-1,C^{\prime}}\vee
T_{A,B^{\prime},C^{\prime}-1}$, such that there is a point at
$(A+B^{\prime}-C^{\prime}+1,t)$ in $\Pi$. By $\Pi$ on $U$ we can determine
whether such $t\leq s$, and its value if $t\leq s$. Thus by induction the
conclusion follows. ∎

###  3.3 Sum of exponential random variables

We would need the following basic results, on analyticity of density functions
of sums of independent exponential random variables.

######  Lemma 3.5.

Let $m\in\mathbb{N}$, $E_{1},\cdots,E_{m}$ be i.i.d. $\operatorname{Exp}(1)$
random variables, and $a_{1},\cdots,a_{m}>0$. The function

$r\mapsto\mathbb{P}\left[\sum_{i=1}^{m}a_{i}E_{i}=r\right],$

is analytic in $[0,\infty)$, and can be extended to an analytic function on
$\mathbb{C}$.

######  Lemma 3.6.

Let $m\in\mathbb{N}$, $E_{1},\cdots,E_{m}$ be i.i.d. $\operatorname{Exp}(1)$
random variables, and $a_{1},\cdots,a_{m}>0$. Take integers $1\leq
m_{1}<\cdots<m_{k}\leq m$, and $0<t_{1}<\cdots<t_{k}$. The function

$r\mapsto\mathbb{P}\left[\sum_{i=1}^{m_{j}}a_{i}E_{i}<t_{j}-r,\;\forall 1\leq
j\leq k\right],$

is analytic in $[0,t_{1}]$, and can be extended to an analytic function on
$\mathbb{C}$.

To prove these two lemmas, we consider the following space $\Gamma_{n}$ of
analytic functions on $\mathbb{C}^{n}$, which consists of all (finite) linear
combinations of

$(r_{1},\cdots,r_{n})\mapsto\prod_{i=1}^{n}r_{i}^{a_{i}}e^{b_{i}r_{i}}$

where $a_{1},\cdots,a_{n}\in\mathbb{Z}_{\geq 0}$, and
$b_{1},\cdots,b_{n}\in\mathbb{R}$. We have the following properties.

######  Lemma 3.7.

For any $f_{1},f_{2}\in\Gamma_{1}$, there is $f_{3}\in\Gamma_{1}$, such that
for any $r>0$, we have

$f_{3}(r)=\int_{0}^{r}f_{1}(s)f_{2}(r-s)ds.$

###### Proof.

Without loss of generality, we can assume that $f_{1}(r)=r^{a_{1}}e^{b_{1}r}$
and $f_{2}(r)=r^{a_{2}}e^{b_{2}r}$, for some $a_{1},a_{2}\in\mathbb{Z}_{\geq
0}$ and $b_{1},b_{2}\in\mathbb{R}$. When $b_{1}=b_{2}$, we have

$\int_{0}^{r}f_{1}(s)f_{2}(r-s)ds=e^{b_{1}r}\int_{0}^{r}s^{a_{1}}(r-s)^{a_{2}}ds,$

and the integral is a polynomial of $r$. When $b_{1}\neq b_{2}$, we have

$\int_{0}^{r}f_{1}(s)f_{2}(r-s)ds=e^{b_{2}r}\int_{0}^{r}s^{a_{1}}(r-s)^{a_{2}}e^{(b_{1}-b_{2})s}ds,$

and the integral would be $F_{1}(r)+F_{2}(r)e^{(b_{1}-b_{2})r}$, for some
polynomials $F_{1},F_{2}$. Thus the conclusion follows. ∎

######  Lemma 3.8.

For any $f_{1}\in\Gamma_{n}$, and $0<t_{1}<\cdots<t_{n}$, there is
$f_{2}\in\Gamma_{1}$, such that

$f_{2}(r)=\int_{\sum_{i^{\prime}=1}^{i}s_{i^{\prime}}<t_{i}-r,\forall 1\leq
i\leq n}f_{1}(s_{1},\cdots,s_{n})\prod_{i=1}^{n}ds_{i},$

for any $r\in[0,t_{1}]$.

To prove this we need the following lemma.

######  Lemma 3.9.

For any $f_{1}\in\Gamma_{n+1}$, and $t>0$, there is $f_{2}\in\Gamma_{n}$, such
that

$f_{2}(s_{1},\cdots,s_{n})=\int_{0}^{t-\sum_{i=1}^{n}s_{i}}f_{1}(s_{1},\cdots,s_{n+1})ds_{n+1},$

for any $s_{1},\cdots,s_{n}\geq 0$ with $\sum_{i=1}^{n}s_{i}<t$.

###### Proof.

Without loss of generality we assume that
$f_{1}(s_{1},\cdots,s_{n+1})=\prod_{i=1}^{n+1}s_{i}^{a_{i}}e^{b_{i}s_{i}}$,
where each $a_{i}\in\mathbb{Z}_{\geq 0}$ and $b_{i}\in\mathbb{R}$. Then we
have

$\displaystyle\int_{0}^{t-\sum_{i=1}^{n}s_{i}}\prod_{i=1}^{n+1}s_{i}^{a_{i}}e^{b_{i}s_{i}}ds_{n+1}$
$\displaystyle=\int_{0}^{t-\sum_{i=1}^{n}s_{i}}s_{n+1}^{a_{n+1}}e^{b_{n+1}s_{n+1}}ds_{n+1}\prod_{i=1}^{n}s_{i}^{a_{i}}e^{b_{i}s_{i}}$
$\displaystyle=\left(F\left(t-\sum_{i=1}^{n}s_{i}\right)e^{b_{n+1}(t-\sum_{i=1}^{n}s_{i})}-\frac{a_{n+1}!}{b_{n+1}^{a_{n+1}+1}}\right)\prod_{i=1}^{n}s_{i}^{a_{i}}e^{b_{i}s_{i}},$

where $F$ is a polynomial. Then the conclusion follows. ∎

###### Proof of Lemma 3.8.

For each $0\leq m\leq n$, we can inductively prove that there is some
$g_{m}\in\Gamma_{n-m+1}$, such that

$g_{m}(s_{1},\cdots,s_{n-m},r)=\int_{\sum_{i^{\prime}=1}^{i}s_{i^{\prime}}<t_{i}-r,\forall
n-m+1\leq i\leq n}f_{1}(s_{1},\cdots,s_{n})\prod_{i=n-m+1}^{n}ds_{i},$ (3.1)

for any $s_{1},\cdots,s_{n-m},r\geq 0$ with
$r+\sum_{i=1}^{n-m}s_{i}<t_{n-m+1}$. Indeed, for the base case we just take
$g_{0}(s_{1},\cdots,s_{n},r)=f_{1}(s_{1},\cdots,s_{n})$. Then given $g_{m}$
for some $0\leq m<n$, by Lemma 3.9 we let $g_{m+1}\in\Gamma_{n-m}$ be the
function with

$g_{m+1}(s_{1},\cdots,s_{n-m-1},r)=\int_{0}^{t_{n-m}-r-\sum_{i=1}^{n-m-1}s_{i}}g_{m}(s_{1},\cdots,s_{n-m},r)ds_{n-m},$

for any $s_{1},\cdots,s_{n-m-1},r\geq 0$ with
$r+\sum_{i=1}^{n-m-1}s_{i}<t_{n-m}$. Then this $g_{m+1}$ satisfies (3.1).
Finally we just take $f_{2}=g_{n}$, and the conclusion follows. ∎

We can now prove the lemmas on the probabilities about sums of exponential
random variables.

###### Proof of Lemma 3.5.

By induction in $m$, the conclusion follows from Lemma 3.7, using that for
each $1\leq i\leq m$, the function
$r\mapsto\mathbb{P}[a_{i}E_{i}=r]=e^{-r/a_{i}}$ can be analytically extended
to a function in $\Gamma_{1}$. ∎

###### Proof of Lemma 3.6.

Denote $m_{0}=0$. By Lemma 3.5, for each $1\leq j\leq k$ we take
$f_{j}\in\Gamma_{1}$ such that

$f_{j}(s)=\mathbb{P}\left[\sum_{i=m_{j-1}+1}^{m_{j}}a_{i}E_{i}=s\right].$

Then by Lemma 3.8, we can find $f\in\Gamma_{1}$, such that

$f(r)=\int_{\sum_{i=1}^{j}s_{i}<t_{j}-r,\forall 1\leq j\leq
k}\prod_{j=1}^{k}f_{j}(s_{j})ds_{j}=\mathbb{P}\left[\sum_{i=1}^{m_{j}}a_{i}E_{i}<t_{j}-r,\;\forall
1\leq j\leq k\right],$

for any $r\in[0,t_{1}]$. Thus the conclusion follows. ∎

##  4 Inductive setup

We do induction to prove Theorem 2.4. In this section we setup the induction,
defining the ‘cutting times’, and prove an independence result (Lemma 4.1),
which corresponds two step 1 in Section 2.1.

Let $\hat{g}=g$ if $t_{\iota}\neq t_{\iota+1}$, and $\hat{g}=g-1$ if
$t_{\iota}=t_{\iota+1}$, and we do induction on $\hat{g}$. The base case where
$\hat{g}=0$ follows directly from Theorem 2.3. Now we assume that $\hat{g}\geq
1$.

Take $1\leq\tau\leq g$ such that $t_{\tau}\leq t_{i}$ for any $1\leq i\leq g$.
Without loss of generality (and by symmetry) we assume that $\tau\leq\iota$;
and if $t_{\iota}=t_{\iota+1}$, we assume that $\iota\geq 2$. Denote

$I=\bigcap_{i=\tau+1}^{g}\bigcap_{j=1}^{k_{i}}I_{A_{i,j},B_{i,j},C_{i,j}}^{t_{i}},\quad
I^{+}=\bigcap_{i=\tau+1}^{g}\bigcap_{j=1}^{k_{i}}I_{A_{i,j}^{+},B_{i,j},C_{i,j}}^{t_{i}},$

and

$J=\bigcap_{i=1}^{\tau}\bigcap_{j=1}^{k_{i}}I_{A_{i,j},B_{i,j},C_{i,j}}^{t_{i}}.$

By the induction hypothesis we have that $\mathbb{P}[I]=\mathbb{P}[I^{+}]$.
The goal would be to prove that $\mathbb{P}[J\mid I]=\mathbb{P}[J\mid I^{+}]$.

Let $A_{*}=\min_{\tau<i\leq g,1\leq j\leq k_{i}}A_{i,j}$, and take
$B_{*},C_{*}$ such that

$A_{*}+B_{*}=\max_{\tau<i\leq g,1\leq j\leq k_{i}}A_{i,j}+B_{i,j},$

and

$A_{*}-C_{*}=\min_{1\leq i\leq\tau,1\leq j\leq k_{i}}A_{i,j}-C_{i,j}.$

We then have that $B_{*},C_{*}\in\mathbb{N}$. Indeed, we would have that
$B_{*}\geq B_{i,j}$ for any $\tau<i\leq g$ and $1\leq j\leq k_{i}$. We would
also have that $A_{*}\geq\max_{1\leq i\leq\tau,1\leq j\leq k_{i}}A_{i,j}$, so
$C_{*}\geq C_{i,j}$ for any $1\leq i\leq\tau$ and $1\leq j\leq k_{i}$.

We shall mainly work with the projection $\hat{\mu}^{A_{*},C_{*}}$; and for
simplicity of notations we also denote it as $\eta$. From Lemma 3.2, we have
that $J$ is measurable with respect of the sigma-algebra generated by $\eta$.

We now define a series of stopping times in $\eta$, which we call the _cutting
times_ : for each $1\leq i\leq C_{*}$, we let $R_{i}$ be the first time when
the site $A_{*}+B_{*}+1-i$ is occupied by a particle in $\eta$; i.e.

$R_{i}=\inf\\{t\geq 0:\eta_{t}(A_{*}+B_{*}+1-i)<\infty\\}.$

Then almost surely we have that $R_{1}<\cdots<R_{C_{*}}$. We also let
$R_{C_{*}+1}=\infty$ for simplicity of notations in the later text. For each
$1\leq i\leq C_{*}$ we also let $L_{i}=\eta_{R_{i}}(A_{*}+B_{*}+1-i)$. Our
general idea is to take $\\{\mathds{1}[R_{i}\leq
t_{\tau}]R_{i}\\}_{i=1}^{C_{*}}$ and $\\{L_{i}\\}_{i=1}^{C_{*}}$ as the
intermediate information between $I$ (or $I^{+}$) and $J$. Our first step is
to show that, given $\\{\mathds{1}[R_{i}\leq t_{\tau}]R_{i}\\}_{i=1}^{C_{*}}$
and $\\{L_{i}\\}_{i=1}^{C_{*}}$, the two events would be independent.

######  Lemma 4.1.

For any $1\leq k\leq C_{*}$, $0<r_{1}<\cdots<r_{k}<t_{\tau}$, and any mutually
distinct $l_{1},\cdots,l_{k}\in\\{1,\cdots,C_{*}\\}$, we have

$\mathbb{P}[J\mid\\{R_{i}\\}_{i=1}^{k}=\\{r_{i}\\}_{i=1}^{k},R_{k+1}>t_{\tau},\\{L_{i}\\}_{i=1}^{k}=\\{l_{i}\\}_{i=1}^{k},I]\\\
=\mathbb{P}[J\mid\\{R_{i}\\}_{i=1}^{k}=\\{r_{i}\\}_{i=1}^{k},R_{k+1}>t_{\tau},\\{L_{i}\\}_{i=1}^{k}=\\{l_{i}\\}_{i=1}^{k},I^{+}].$
(4.1)

time$A_{*}+B_{*}-k\;$$A_{*}+B_{*}\;$$U_{-}$$U_{+}$ Figure 4:  An illustration
of the Poisson field $\Pi$ and the areas $U_{-}$ and $U_{+}$. The green points
indicate space time locations where the colors are given by
$\\{L_{i}\\}_{i=1}^{k}$. The red paths are the trajectories of the first two
particles in $\mu^{A_{i,j}}$, for some $1\leq i\leq\tau$ and $1\leq j\leq
k_{i}$.

###### Proof.

The general idea is to show that given the cutting time information, the
events $I$ or $I^{+}$ and $J$ would be determined by the Poisson clocks in two
disjoint areas.

We consider two cases. First, suppose that there is some $1\leq j\leq
k_{\tau}$ such that

$|\\{i:1\leq i\leq k,l_{i}\leq C_{*}+A_{\tau,j}-A_{*}\\}|<C_{\tau,j}.$ (4.2)

In this case, if $\\{L_{i}\\}_{i=1}^{k}=\\{l_{i}\\}_{i=1}^{k}$ and
$R_{k+1}>t_{\tau}$, we have that

$|\\{x\in\mathbb{Z}:x\geq
A_{\tau,j}+B_{\tau,j}+1-C_{\tau,j},\eta_{t_{\tau}}(x)\leq
C_{*}+A_{\tau,j}-A_{*}\\}|<C_{\tau,j}$

which implies that $T^{A_{\tau,j}}_{B_{\tau,j},C_{\tau,j}}>t_{\tau}$. Thus we
have that both sides of (4.1) would equal $0$.

In the second case, we assume that (4.2) is not true for any $1\leq j\leq
k_{\tau}$. Then for any $1\leq i\leq\tau$ and $1\leq j\leq k_{i}$, we have

$|\\{i^{\prime}:1\leq i^{\prime}\leq k,l_{i^{\prime}}\leq
C_{*}+A_{i,j}-A_{*}\\}|\geq C_{i,j}.$ (4.3)

We denote $\mathcal{E}_{-}$ as the event
$\\{R_{i}\\}_{i=1}^{k}=\\{r_{i}\\}_{i=1}^{k},R_{k+1}>t_{\tau},\\{L_{i}\\}_{i=1}^{k}=\\{l_{i}\\}_{i=1}^{k}$.
We would show that conditional on $\mathcal{E}_{-}$, the events $I$ and $J$
are independent, and the events $I^{+}$ and $J$ are also independent.

We recall the Poisson field $\Pi$ on $\mathbb{Z}\times[0,\infty)$, where for
each $x\in\mathbb{Z}$ and any $0\leq a<b$, $\Pi(\\{x\\}\times[a,b])$ would be
the number of times that the clock on the edge $(x-1,x)$ rings, in the time
interval $[a,b]$. Denote

$U^{-}:=\\{(x,t):x\leq A_{*}+B_{*}-k\\}\cup\bigcup_{i=1}^{k}\\{(x,t):0\leq
t\leq r_{i},x\leq A_{*}+B_{*}-i+1\\},$

and $U^{+}=\mathbb{Z}\times[0,\infty)\setminus U^{-}$. See Figure 4. By Lemma
3.3, we have that the event $\mathcal{E}_{-}$ is measurable with respect to
$\Pi$ on $U^{-}$; thus it is independent of $\Pi$ on $U^{+}$.

We then claim that conditional on $\mathcal{E}_{-}$, the event $I$ is
measurable with respect to $\Pi$ on $U^{-}$. Indeed, given $\mathcal{E}_{-}$,
for any $\tau<i\leq g$ and $1\leq j\leq k_{i}$, we have
$T^{A_{i,j}}_{B_{i,j},i^{\prime}}\leq r_{i^{\prime}}$, for any $1\leq
i^{\prime}\leq k$. Also note that $A_{i,j}+B_{i,j}-i^{\prime}+1\leq
A_{*}+B_{*}-i^{\prime}+1$ for $1\leq i^{\prime}\leq k$, and
$A_{i,j}+B_{i,j}-i^{\prime}+1\leq A_{*}+B_{*}-k$ for $k<i^{\prime}\leq
C_{i,j}$. This implies that for any $1\leq i^{\prime}\leq C_{i,j}$, we would
have $(A_{i,j}+B_{i,j}-i^{\prime}+1,T^{A_{i,j}}_{B_{i,j},i^{\prime}})\in
U^{-}$. Thus conditional on $\mathcal{E}_{-}$, the event
$I^{t_{i}}_{A_{i,j},B_{i,j},C_{i,j}}$ is equivalent to

$\left(\bigcap_{i^{\prime}=1}^{B_{i,j}}I^{t_{i}}_{A_{i,j},i^{\prime},C_{i,j}}\right)\cap\\{(A_{i,j}+B_{i,j}-i^{\prime}+1,T^{A_{i,j}}_{B_{i,j},i^{\prime}})\in
U^{-}.\forall 1\leq i^{\prime}\leq C_{i,j}\\},$

which is determined by $\Pi$ on $U^{-}$, according to Lemma 3.3. Thus the
claim holds. Similarly, conditional on $\mathcal{E}_{-}$, the event $I^{+}$ is
also measurable with respect to $\Pi$ on $U^{-}$.

We next show that conditional on $\mathcal{E}_{-}$, the event $J$ is
measurable with respect to $\Pi$ on $U^{+}$. Take any $1\leq i\leq\tau$ and
$1\leq j\leq k_{i}$. Let $\kappa[1]<\cdots<\kappa[C_{i,j}]$ be the first
$C_{i,j}$ numbers in the set $\\{i^{\prime}:1\leq i^{\prime}\leq
k,l_{i^{\prime}}\leq C_{*}+A_{i,j}-A_{*}\\}$. For any $1\leq i^{\prime}\leq
C_{i,j}$, we take $B^{\prime}_{i^{\prime}}\in\mathbb{N}$ such that
$A_{i,j}+B^{\prime}_{i^{\prime}}-i^{\prime}+1=A_{*}+B_{*}-\kappa[i^{\prime}]+1$.
We then have that
$T^{A_{i,j}}_{B_{i^{\prime}},i^{\prime}}=r_{\kappa[i^{\prime}]}$, given
$\mathcal{E}_{-}$. Then by Lemma 3.4, conditional on $\mathcal{E}_{-}$, the
event $I_{A_{i,j},B_{i,j},C_{i,j}}^{t_{i}}$ is determined by $\Pi$ on $U^{+}$.

Thus we conclude that the events $I$ and $J$ are independent, and the events
$I^{+}$ and $J$ are also independent, conditional on $\mathcal{E}_{-}$; so
$\mathbb{P}[J\mid\mathcal{E}_{-}\cap
I]=\mathbb{P}[J\mid\mathcal{E}_{-}]=\mathbb{P}[J\mid\mathcal{E}_{-}\cap
I^{+}]$, and the conclusion follows. ∎

Given the above lemma, it remains to show that conditional on
$\\{\mathds{1}[R_{i}\leq t_{\tau}]R_{i}\\}_{i=1}^{C_{*}}$ and
$\\{L_{i}\\}_{i=1}^{C_{*}}$, the probabilities of $I$ and $I^{+}$ are the
same. We state this as the following identity.

######  Proposition 4.2.

For any $1\leq k\leq C_{*}$, $0<r_{1}<\cdots<r_{k}<t_{\tau}$, and any mutually
distinct $l_{1},\cdots,l_{k}\in\\{1,\cdots,C_{*}\\}$, we have

$\mathbb{P}[\\{R_{i}\\}_{i=1}^{k}=\\{r_{i}\\}_{i=1}^{k},R_{k+1}>t_{\tau},\\{L_{i}\\}_{i=1}^{k}=\\{l_{i}\\}_{i=1}^{k}\mid
I]\\\
=\mathbb{P}[\\{R_{i}\\}_{i=1}^{k}=\\{r_{i}\\}_{i=1}^{k},R_{k+1}>t_{\tau},\\{L_{i}\\}_{i=1}^{k}=\\{l_{i}\\}_{i=1}^{k}\mid
I^{+}].$ (4.4)

This will be proved in the next section, assuming that Theorem 2.4 is true for
any smaller $\hat{g}$. It is now immediate to deduce Theorem 2.4 from
Proposition 4.2

###### Proof of Theorem 2.4.

Assuming Proposition 4.2, with Lemma 4.1 we have that $\\{\mathds{1}[R_{i}\leq
t_{\tau}]R_{i}\\}_{i=1}^{C_{*}}$, $\\{L_{i}\\}_{i=1}^{C_{*}}$, and
$\mathds{1}[J]$ have the same joint distribution, conditional on $I$ or
$I^{+}$. In particular, we have that $\mathbb{P}[J\mid I]=\mathbb{P}[J\mid
I^{+}]$. Thus the proof concludes by the principle of induction. ∎

##  5 Equal probabilities conditional on cutting information

We prove Proposition 4.2 in this section. The main inputs are information
proved by the induction hypothesis, i.e., Theorem 2.4 for smaller $\hat{g}$,
and that the density function for $\\{\mathds{1}[R_{i}\leq
t_{\tau}]R_{i}\\}_{i=1}^{C_{*}}$ and $\\{L_{i}\\}_{i=1}^{C_{*}}$ are analytic.

###  5.1 Analyticity

We prove the the density function of the cutting time infomation is analytic,
by writing the cutting times as sums of independent exponential random
variables, and using results from Section 3.3.

######  Lemma 5.1.

For any $1\leq k\leq C_{*}$, and any mutually distinct
$l_{1},\cdots,l_{k}\in\\{1,\cdots,C_{*}\\}$, and $\hat{I}=I$ or $I^{+}$, the
function

$(r_{1},\cdots,r_{k})\mapsto\mathbb{P}[\\{R_{i}\\}_{i=1}^{k}=\\{r_{i}\\}_{i=1}^{k},\\{L_{i}\\}_{i=1}^{k}=\\{l_{i}\\}_{i=1}^{k},\hat{I}]$

is analytic in the space
$\\{(r_{1},\cdots,r_{k}):0<r_{1}<\cdots<r_{k}<t_{\tau}\\}$, and it can be
analytically extended to $\mathbb{C}^{k}$.

###### Proof.

We prove for the case where $\hat{I}=I$, and the other case where
$\hat{I}=I^{+}$ follows similarly.

Let $A_{0}=\max_{\tau<i\leq g,1\leq j\leq k_{i}}A_{i,j}$, and take
$B_{0},C_{0}$ such that

$A_{0}+B_{0}=\max_{\tau<i\leq g,1\leq j\leq k_{i}}A_{i,j}+B_{i,j},\quad
A_{0}-C_{0}=\min_{\tau<i\leq g,1\leq j\leq k_{i}}A_{i,j}-C_{i,j}.$

We would have $B_{0}\in\mathbb{N}$, since there exists some $i_{*},j_{*}$ such
that $A_{0}=A_{i_{*},j_{*}}$, and then $B_{0}\geq B_{i_{*},j_{*}}$; we also
have $C_{0}\in\mathbb{N}$, since $C_{0}\geq C_{i,j}$ for any $\tau<i\leq g$
and $1\leq j\leq k_{i}$. For any $\tau<i\leq g$ and $1\leq j\leq k_{i}$, we
have $A_{i,j}\geq A_{0}\geq A_{*}$ and $A_{i,j}-C_{i,j}\leq A_{0}-C_{0}\leq
A_{*}-C_{*}$; so by Lemma 3.2, the process $\eta=\hat{\mu}^{A_{*},C_{*}}$ and
the time $T_{B_{i,j},C_{i,j}}^{A_{i,j}}$ would be determined by
$\hat{\mu}^{A_{0},C_{0}}$.

We consider a process $\xi$, which can be thought of as
$\hat{\mu}^{A_{0},C_{0}}$, while any particle disappears once arrives at site
$A_{0}+B_{0}+1$. To be more precise, for any $x\in\mathbb{Z}$ and $t\geq 0$,
we let $\xi_{t}(x)=\infty$ if $x>A_{0}+B_{0}$, and
$\xi_{t}(x)=\hat{\mu}_{t}^{A_{0},C_{0}}(x)$ otherwise. As
$A_{0}+B_{0}=A_{*}+B_{*}\geq A_{i,j}+B_{i,j}$, for any $\tau<i\leq g$ and
$1\leq j\leq k_{i}$, we would have that $\eta$ on
$\mathbb{Z}\cap(-\infty,A_{*}+B_{*}]$ is determined by $\xi$, and
$T_{B_{i,j},C_{i,j}}^{A_{i,j}}$ would be a certain swap time in $\xi$.

Suppose the total number of swaps (of two particles, or of a particle jumping
to an empty site) in the process $\xi$ is $M$. Then we always have that $M\leq
B_{0}C_{0}+C_{0}^{2}$. This bound is from the following reasoning: for the
particle colored $i$, it would move from $A_{0}-C_{0}+i$ to $A_{0}+B_{0}+1$,
and it can be swapped with a smaller colored particle $i-1$ times; thus it can
jump to the right at most $(A_{0}+B_{0}+1)-(A_{0}-C_{0}+i)+(i-1)=B_{0}+C_{0}$
times.

For $1\leq i\leq M$, we take $X_{i}\in\mathbb{Z}$ such that the $i$-th swap is
between sites $X_{i}$ and $X_{i}+1$, and it happens at time $w_{i}$. Take
$w_{0}=0$, and for each $1\leq i\leq M$ we let $E_{i}=w_{i}-w_{i-1}$. Then
conditional on $M$ and $\\{X_{i}\\}_{i=1}^{M}$, we have that
$\\{E_{i}\\}_{i=1}^{M}$ are independent, and the distribution for $E_{i}$ is
$\operatorname{Exp}(1/a_{i})$, where $a_{i}$ is the number of possible swaps
at time $w_{i-1}$; i.e.,

$a_{i}=|\\{x\in\mathbb{Z}:\xi_{w_{i-1}}(x)<\xi_{w_{i-1}}(x+1)\\}|.$

Note that for each $i$, such $a_{i}$ is determined by $M$ and
$\\{X_{j}\\}_{j=1}^{M}$, since $\xi_{w_{i-1}}$ is determined by
$\\{X_{j}\\}_{j=1}^{i-1}$.

From the bound of $M$, we have that there are finitely many $m$ and
$\\{x_{i}\\}_{i=1}^{m}$, such that
$\mathbb{P}[M=m,\\{X_{i}\\}_{i=1}^{M}=\\{x_{i}\\}_{i=1}^{m}]>0$. It remains to
show that for any such $m$ and $\\{x_{i}\\}_{i=1}^{m}$, the function

$(r_{1},\cdots,r_{k})\mapsto\mathbb{P}[\\{R_{j}\\}_{j=1}^{k}=\\{r_{j}\\}_{j=1}^{k},\\{L_{j}\\}_{j=1}^{k}=\\{l_{j}\\}_{j=1}^{k},I\mid
M=m,\\{X_{i}\\}_{i=1}^{M}=\\{x_{i}\\}_{i=1}^{m}]$

is analytic in the region
$\\{(r_{1},\cdots,r_{k}):0<r_{1}<\cdots<r_{k}<t_{\tau}\\}$; and it can be
analytically extended to $\mathbb{C}^{k}$.

We note that $\\{L_{i}\\}_{i=1}^{k}$ is determined by $M$ and
$\\{X_{i}\\}_{i=1}^{M}$, so it remains to consider the function

$(r_{1},\cdots,r_{k})\mapsto\mathbb{P}[\\{R_{i}\\}_{i=1}^{k}=\\{r_{i}\\}_{i=1}^{k},I\mid
M=m,\\{X_{i}\\}_{i=1}^{M}=\\{x_{i}\\}_{i=1}^{m}].$ (5.1)

For each $1\leq i\leq k$, we have
$R_{i}\in\\{w_{i^{\prime}}\\}_{i^{\prime}=1}^{M}$; and we let $\kappa[i]$ be
the number such that $R_{i}=w_{\kappa[i]}$. Then we have
$\kappa[1]<\kappa[2]<\cdots<\kappa[k]$. For each $\tau+1\leq i\leq g$ and
$1\leq j\leq k_{i}$, we would have
$T^{A_{i,j}}_{B_{i,j},C_{i,j}}\in\\{w_{i^{\prime}}\\}_{i^{\prime}=1}^{M}$; and
we let $\overline{\kappa}[i]$ be the number such that $\max_{1\leq j\leq
k_{i}}T^{A_{i,j}}_{B_{i,j},C_{i,j}}=w_{\overline{\kappa}[i]}$. We note that
the indices $\\{\kappa[i]\\}_{i=1}^{k}$ and
$\\{\overline{\kappa}[i]\\}_{i=\tau+1}^{g}$ are determined by $M$ and
$\\{X_{i}\\}_{i=1}^{M}$. We also denote $\kappa[0]=0$ and $r_{0}=0$.

Since $\\{E_{i}\\}_{i=1}^{M}$ are independent exponential random variables, we
can then write the function (5.1) as

$\mathbb{P}\left[\sum_{i^{\prime}=\kappa[k]+1}^{\overline{\kappa}[i]}E_{i^{\prime}}<t_{i}-r_{k},\;\forall\tau+1\leq
i\leq
g,\overline{\kappa}[i]>\kappa[k]\right]\prod_{i=1}^{k}\mathbb{P}\left[\sum_{i^{\prime}=\kappa[i-1]+1}^{\kappa[i]}E_{i^{\prime}}=r_{i}-r_{i-1}\right].$

By applying Lemma 3.5 or Lemma 3.6 to each factor, we get that this is
analytic for $0<r_{1}<\cdots<r_{k}<t_{\tau}$, and can be analytically extended
to $\mathbb{C}^{k}$. Thus the conclusion follows. ∎

###  5.2 Partial order and induction in cutting time colors

Throughout this subsection, we assume that Theorem 2.4 is true for any smaller
$\hat{g}$.

Let $\Lambda$ be the space of all sequences $\\{l_{i}\\}_{i=1}^{k}$, for any
$0\leq k\leq C_{*}$ and mutually distinct
$l_{1},\cdots,l_{k}\in\\{1,\cdots,C_{*}\\}$. We define a partial order $\prec$
on the $\Lambda$: for any $\\{l_{i}\\}_{i=1}^{k}$ and
$\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}}$, we let
$\\{l_{i}\\}_{i=1}^{k}\prec\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}}$, if one of
the following conditions are satisfied:

  1. 1.

$k^{\prime}<k$, and $l_{i}^{\prime}=l_{i}$ for $1\leq i\leq k^{\prime}$.

  2. 2.

$k^{\prime}=k$, and we can apply a ‘swap operation’ to $\\{l_{i}\\}_{i=1}^{k}$
to get $\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}}$; i.e., for some $1\leq i<k$
with $l_{i}>l_{i+1}$, there is $l_{i}^{\prime}=l_{i+1}$ and
$l_{i+1}=l_{i}^{\prime}$, and $l_{j}=l_{j}^{\prime}$ for any $1\leq j\leq k$,
$j\not\in\\{i,i+1\\}$.

Also, suppose
$\\{l_{i}\\}_{i=1}^{k}\prec\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}}$ and
$\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}}\prec\\{l_{i}^{\prime\prime}\\}_{i=1}^{k^{\prime\prime}}$,
we let
$\\{l_{i}\\}_{i=1}^{k}\prec\\{l_{i}^{\prime\prime}\\}_{i=1}^{k^{\prime\prime}}$.
In other words, from some $\\{l_{i}\\}_{i=1}^{k}\in\Lambda$, the sequences
that are greater than it under $\prec$ are those that can be obtained in the
following way: first apply a sequence of swap operation, then take the first
$k^{\prime}$ numbers for some $1\leq k^{\prime}\leq k$. For simplicity of
notations, we let
$\\{l_{i}\\}_{i=1}^{k}\preceq\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}}$ if
$\\{l_{i}\\}_{i=1}^{k}\prec\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}}$ or
$\\{l_{i}\\}_{i=1}^{k}=\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}}$.

We prove Proposition 4.2 by induction in $\\{l_{i}\\}_{i=1}^{k}\in\Lambda$,
under the ordering $\prec$. Below we shall fix
$\\{l_{i}\\}_{i=1}^{k}\in\Lambda$, and assume that Proposition 4.2 is true for
any $\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}}\prec\\{l_{i}\\}_{i=1}^{k}$.

We now state the input from the induction hypothesis of Theorem 2.4.

Take $\lambda\in\mathbb{N}$. For each $1\leq i\leq k$ we denote
$m_{i}=2^{\lambda^{k+1-i}}$. We assume that $\lambda$ is large enough so that
$m_{1}>\cdots>m_{k}>A_{*}+B_{*}$. Denote $t_{*}=t_{\tau+1}$. Denote
$\mathcal{E}$ as the event where
$\\{\eta_{t_{*}}(m_{i})\\}_{i=1}^{k}=\\{l_{i}\\}_{i=1}^{k}$ and
$\eta_{t_{*}}(x)=\infty,x\in[m_{k},\infty)\setminus\\{m_{i}\\}_{i=1}^{k}$.

######  Lemma 5.2.

We have $\mathbb{P}[\mathcal{E}\mid I]=\mathbb{P}[\mathcal{E}\mid I^{+}]$.

###### Proof.

We note that $\mathcal{E}$ is equivalent to the following event (denoted as
$\mathcal{E}^{\prime}$):

  1. 1.

$T^{A}_{B,C}\leq t_{*}$, for any $A\leq A_{*}$, $A-C\geq A_{*}-C_{*}$,
$A+B-C+1\geq m_{k}$, such that $|\\{1\leq i\leq k:A_{*}-C_{*}+l_{i}\leq
A,m_{i}\geq A+B-C+1\\}|\geq C$;

  2. 2.

$T^{A}_{B,C}>t_{*}$, for any $A\leq A_{*}$, $A-C\geq A_{*}-C_{*}$,
$A+B-C+1\geq m_{k}$, such that $|\\{1\leq i\leq k:A_{*}-C_{*}+l_{i}\leq
A,m_{i}\geq A+B-C+1\\}|<C$.

It is straight forward to see that $\mathcal{E}^{\prime}$ is implied by
$\mathcal{E}$. For the other direction: from $\mathcal{E}^{\prime}$ we can
determine $|\\{x\geq x_{0}:\eta_{t_{*}}(x)\leq i\\}|$ for each $x_{0}\geq
m_{*}$ and each $1\leq i\leq C_{*}$; thus by varying $x_{0}$ we can determine
the set $\\{x\geq m_{k}:\eta_{t_{*}}(x)\leq i\\}$ for each $1\leq i\leq
C_{*}$; and by further varying $i$ we determine $\eta_{t_{*}}(x)$ for each
$x\geq m_{k}$, and this could imply $\mathcal{E}$.

Take any $k_{0}\in\mathbb{N}$, and
$\\{A_{0,j}\\}_{j=1}^{k_{0}}\in\mathbb{Z}^{k_{0}}$,
$\\{B_{0,j}\\}_{j=1}^{k_{0}}\in\mathbb{N}^{k_{0}}$,
$\\{C_{0,j}\\}_{j=1}^{k_{0}}\in\mathbb{N}^{k_{0}}$, such that each
$A_{0,j}\leq A_{*}$, $A_{0,j}-C_{0,j}\geq A_{*}-C_{*}$,
$A_{0,j}+B_{0,j}-C_{0,j}+1\geq m_{k}$. We then apply Theorem 2.4 to
$g^{\prime}\in\mathbb{N}$,
$k_{1}^{\prime},\ldots,k_{g^{\prime}}^{\prime}\in\mathbb{N}$, and
$A_{i,j}^{\prime}\in\mathbb{Z}$,
$B_{i,j}^{\prime},C_{i,j}^{\prime}\in\mathbb{N}$ for $1\leq i\leq g^{\prime}$
and $1\leq j\leq k_{i}^{\prime}$, and $1\leq\iota^{\prime}<g^{\prime}$,
$t_{1}^{\prime},\ldots,t_{g^{\prime}}^{\prime}$, where

  1. 1.

$g^{\prime}=g-\tau$, $\iota^{\prime}=\iota-\tau$, $t_{i}^{\prime}=t_{\tau+i}$
for each $1\leq i\leq g^{\prime}$,

  2. 2.

$k_{1}^{\prime}=k_{\tau+1}+k_{0}$, $k_{i}^{\prime}=k_{\tau+i}$ for each
$1<i\leq g^{\prime}$,

  3. 3.

$\\{A_{1,j}^{\prime}\\}_{j=1}^{k_{1}^{\prime}}=\\{A_{0,j}\\}_{j=1}^{k_{0}}\cup\\{A_{\tau+1,j}\\}_{j=1}^{k_{\tau+1}}$,
$\\{B_{1,j}^{\prime}\\}_{j=1}^{k_{1}^{\prime}}=\\{B_{0,j}\\}_{j=1}^{k_{0}}\cup\\{B_{\tau+1,j}\\}_{j=1}^{k_{\tau+1}}$,
$\\{C_{1,j}^{\prime}\\}_{j=1}^{k_{1}^{\prime}}=\\{C_{0,j}\\}_{j=1}^{k_{0}}\cup\\{C_{\tau+1,j}\\}_{j=1}^{k_{\tau+1}}$;
and $A_{i,j}^{\prime}=A_{\tau+i,j}$, $B_{i,j}^{\prime}=B_{\tau+i,j}$,
$C_{i,j}^{\prime}=C_{\tau+i,j}$ for each $1<i\leq g^{\prime}$ and $1\leq j\leq
k_{i}^{\prime}$.

Under this setting, if $t_{\iota}\neq t_{\iota+1}$, the corresponding
$\hat{g}^{\prime}$ would be $g^{\prime}=g-\tau<g=\hat{g}$; otherwise, if
$\tau<\iota$ we would have
$\hat{g}^{\prime}=g^{\prime}-1=g-\tau-1<g-1=\hat{g}$, and if $\tau=\iota$ we
would have $\tau\geq 2$, so $\hat{g}^{\prime}=g-\tau<g-1=\hat{g}$. Thus by the
induction hypothesis of Theorem 2.4, we conclude that

$\mathbb{P}\left[\bigcap_{j=1}^{k_{0}}I^{t_{*}}_{A_{0,j},B_{0,j},C_{0,j}}\cap
I\right]=\mathbb{P}\left[\bigcap_{j=1}^{k_{0}}I^{t_{*}}_{A_{0,j},B_{0,j},C_{0,j}}\cap
I^{+}\right].$

Then by inclusion-exclusion principle, and taking different
$\\{A_{0,j}\\}_{j=1}^{k_{0}}$, $\\{B_{0,j}\\}_{j=1}^{k_{0}}$,
$\\{C_{0,j}\\}_{j=1}^{k_{0}}$, we get $\mathbb{P}[\mathcal{E}^{\prime}\cap
I]=\mathbb{P}[\mathcal{E}^{\prime}\cap I^{+}]$, so the conclusion follows. ∎

For each $\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}}\in\Lambda$ and
$0<r_{1}<\cdots<r_{k^{\prime}}<t_{\tau}$, and $\hat{I}=I$ or $I^{+}$, we
denote

$F(\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}},\\{r_{i}\\}_{i=1}^{k^{\prime}},\hat{I})=\mathbb{P}[\mathcal{E}\mid\\{R_{i}\\}_{i=1}^{k^{\prime}}=\\{r_{i}\\}_{i=1}^{k^{\prime}},R_{k^{\prime}+1}>t_{\tau},\\{L_{i}\\}_{i=1}^{k^{\prime}}=\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}},\hat{I}],$

and

$G(\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}},\\{r_{i}\\}_{i=1}^{k^{\prime}},\hat{I})=\mathbb{P}[\\{R_{i}\\}_{i=1}^{k^{\prime}}=\\{r_{i}\\}_{i=1}^{k^{\prime}},R_{k^{\prime}+1}>t_{\tau},\\{L_{i}\\}_{i=1}^{k^{\prime}}=\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}}\mid\hat{I}].$

Then using the cutting time information, we can write

$\mathbb{P}[\mathcal{E}\mid\hat{I}]=\sum_{\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}}\in\Lambda}\int_{0<r_{1}<\cdots<r_{k^{\prime}}<t_{\tau}}F(\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}},\\{r_{i}\\}_{i=1}^{k^{\prime}},\hat{I})G(\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}},\\{r_{i}\\}_{i=1}^{k^{\prime}},\hat{I})\prod_{i=1}^{k^{\prime}}dr_{i},$
(5.2)

for $\hat{I}=I$ or $I^{+}$.

To prove Proposition 4.2, we need to show that
$G(\\{l_{i}\\}_{i=1}^{k},\\{r_{i}\\}_{i=1}^{k},I)=G(\\{l_{i}\\}_{i=1}^{k},\\{r_{i}\\}_{i=1}^{k},I^{+})$
for any $0<r_{1}<\cdots<r_{k}<t_{\tau}$; and by the induction hypothesis we
assume that
$G(\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}},\\{r_{i}\\}_{i=1}^{k^{\prime}},I)=G(\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}},\\{r_{i}\\}_{i=1}^{k^{\prime}},I^{+})$
for any $\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}}\prec\\{l_{i}\\}_{i=1}^{k}$
and any $0<r_{1}<\cdots<r_{k^{\prime}}<t_{\tau}$. We then need to analyze the
properties of the function $F$, which is the transition probability from the
cutting time information to $\mathcal{E}$, as $\lambda\to\infty$.

We next state a few such results. A general heuristics behind these following
lemmas is as follows. As $\lambda$ is taken large, to make the event
$\mathcal{E}$ happen, for each $1\leq i\leq k$ the particle in $\eta$ with
color $l_{i}$ would move to the right with speed $\frac{m_{i}}{t_{*}-R_{i}}$,
from time $R_{i}$. Thus from the choice of each $m_{i}$, the particles evolve
mostly independently.

The first two results are essentially bounds on the transition probabilities.

######  Lemma 5.3.

For any
$\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}}\not\preceq\\{l_{i}\\}_{i=1}^{k}$, and
$\alpha_{1},\cdots,\alpha_{k}\in\mathbb{Z}_{\geq 0}$, and $\hat{I}=I$ or
$\hat{I}=I^{+}$, we have

$\prod_{i=1}^{k}\frac{m_{i}^{\alpha_{i}}\cdot
m_{i}!}{t_{*}^{m_{i}}}\int_{0<r_{1}<\cdots<r_{k^{\prime}}<t_{\tau}}F(\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}},\\{r_{i}\\}_{i=1}^{k^{\prime}},\hat{I})\prod_{i=1}^{k^{\prime}}dr_{i}\to
0,$

as we send $\lambda\to\infty$.

The idea behind this lemma is as follows. Since
$\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}}\not\preceq\\{l_{i}\\}_{i=1}^{k}$, the
event $\mathcal{E}$ does not happen, unless
$\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}}$ does not contain $l_{i}$ for some
$1\leq i\leq k$. This is by the definition of the ordering $\prec$. This
implies that for the particle colored $l_{i}$, its corresponding cutting time
would be $>t_{\tau}$; thus it has a much smaller probability of arriving at
$m_{i}$ at time $t_{*}$ (compared to the case where it has a small cutting
time).

######  Lemma 5.4.

For any $\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}}\preceq\\{l_{i}\\}_{i=1}^{k}$,
and any $\alpha_{1},\cdots,\alpha_{k}\in\mathbb{Z}_{\geq 0}$, we have

$\prod_{i=1}^{k}\frac{m_{i}^{\alpha_{i}}\cdot
m_{i}!}{t_{*}^{m_{i}}}\int_{0<r_{1}<\cdots<r_{k^{\prime}}<t_{\tau}}\big{|}F(\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}},\\{r_{i}\\}_{i=1}^{k^{\prime}},I)-F(\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}},\\{r_{i}\\}_{i=1}^{k^{\prime}},I^{+})\big{|}\prod_{i=1}^{k^{\prime}}dr_{i}\to
0,$

as we send $\lambda\to\infty$.

For this lemma, we note that the expression is non-zero, because the event $I$
or $I^{+}$ would affect the cutting time information after time $t_{\tau}$.
However, when $\lambda$ is large, the particles move fast to the right, and
any particle with a cutting time $>t_{\tau}$ can hardly affect the evolution
of those with colors in $\\{l_{i}\\}_{i=1}^{k}$.

The next result is a more refined asymptotic result of the transition
probability, with scaling of times.

######  Lemma 5.5.

Take any $s_{1},\ldots,s_{k}>0$. As we send $\lambda\to\infty$, there is

$\prod_{i=1}^{k}\frac{(m_{i}-(A_{*}+B_{*}+1-i))!}{t_{*}^{m_{i}-(A_{*}+B_{*}+1-i)}}F(\\{l_{i}\\}_{i=1}^{k},\\{\frac{s_{i}}{m_{i}}\\}_{i=1}^{k},I)\to
e^{-kt_{*}}\prod_{i=1}^{k}e^{-s_{i}/t_{*}}.$

In addition, when $\lambda$ is large enough (depending on
$A_{*},B_{*},C_{*},t_{*},t_{\tau}$), and
$0<\frac{s_{1}}{m_{1}}<\cdots<\frac{s_{k}}{m_{k}}<t_{\tau}$, the left hand
side is bounded by $\prod_{i=1}^{k}2e^{-s_{i}/t_{*}}$.

We leave the proofs of these lemmas to the next subsections. We now finish the
proof of Proposition 4.2 assuming them.

###### Proof of Proposition 4.2.

For $\mathbb{P}[\mathcal{E}\mid I]=\mathbb{P}[\mathcal{E}\mid I^{+}]$ from
Lemma 5.2, we apply (5.2) to both hand sides. Take any
$\alpha_{1},\cdots,\alpha_{k}\in\mathbb{Z}_{\geq 0}$, we multiply both sides
by $\prod_{i=1}^{k}\frac{m_{i}^{\alpha_{i}}\cdot m_{i}!}{t_{*}^{m_{i}}}$, and
get

$\sum_{\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}}\in\Lambda}\prod_{i=1}^{k}\frac{m_{i}^{\alpha_{i}}\cdot
m_{i}!}{t_{*}^{m_{i}}}\int_{0<r_{1}<\cdots<r_{k^{\prime}}<t_{\tau}}F(\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}},\\{r_{i}\\}_{i=1}^{k^{\prime}},I)G(\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}},\\{r_{i}\\}_{i=1}^{k^{\prime}},I)\prod_{i=1}^{k^{\prime}}dr_{i}\\\
=\sum_{\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}}\in\Lambda}\prod_{i=1}^{k}\frac{m_{i}^{\alpha_{i}}\cdot
m_{i}!}{t_{*}^{m_{i}}}\int_{0<r_{1}<\cdots<r_{k^{\prime}}<t_{\tau}}F(\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}},\\{r_{i}\\}_{i=1}^{k^{\prime}},I^{+})G(\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}},\\{r_{i}\\}_{i=1}^{k^{\prime}},I^{+})\prod_{i=1}^{k^{\prime}}dr_{i}.$

We would then send $\lambda\to\infty$, and analyze the behaviour of each term
in the summations in both sides.

We claim that
$G(\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}},\\{r_{i}\\}_{i=1}^{k^{\prime}},\hat{I})$
is bounded, uniformly in $\hat{I}=I$ or $\hat{I}=I^{+}$, and
$\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}}\in\Lambda$,
$0<r_{1}<\cdots<r_{k^{\prime}}<t_{\tau}$. Indeed, we just have

$\displaystyle
G(\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}},\\{r_{i}\\}_{i=1}^{k^{\prime}},\hat{I})=$
$\displaystyle\mathbb{P}[\\{R_{i}\\}_{i=1}^{k^{\prime}}=\\{r_{i}\\}_{i=1}^{k^{\prime}},R_{k^{\prime}+1}>t_{\tau},\\{L_{i}\\}_{i=1}^{k^{\prime}}=\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}}\mid\hat{I}]$
$\displaystyle\leq$
$\displaystyle\mathbb{P}[\hat{I}]^{-1}\mathbb{P}[\\{R_{i}\\}_{i=1}^{k^{\prime}}=\\{r_{i}\\}_{i=1}^{k^{\prime}},\\{L_{i}\\}_{i=1}^{k^{\prime}}=\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}},\hat{I}].$

By Lemma 5.1, for each $\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}}$ and $\hat{I}$
this is analytic as a function of $0<r_{1}<\cdots<r_{k^{\prime}}<t_{\tau}$,
and has an extension to $\mathbb{C}^{k^{\prime}}$, thus must be bounded
uniformly in $0<r_{1}<\cdots<r_{k^{\prime}}<t_{\tau}$. As there are only
finitely many choices of $\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}}$ and
$\hat{I}$, the above claim then follows.

With this claim, by Lemma 5.3, for any
$\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}}\not\preceq\\{l_{i}\\}_{i=1}^{k}$ and
$\hat{I}=I$ or $I^{+}$, we have

$\prod_{i=1}^{k}\frac{m_{i}^{\alpha_{i}}\cdot
m_{i}!}{t_{*}^{m_{i}}}\int_{0<r_{1}<\cdots<r_{k^{\prime}}<t_{\tau}}F(\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}},\\{r_{i}\\}_{i=1}^{k^{\prime}},\hat{I})G(\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}},\\{r_{i}\\}_{i=1}^{k^{\prime}},\hat{I})\prod_{i=1}^{k^{\prime}}dr_{i}\to
0,$

as $\lambda\to\infty$. For any
$\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}}\prec\\{l_{i}\\}_{i=1}^{k}$, by the
induction hypothesis (of this proposition), we have that
$G(\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}},\\{r_{i}\\}_{i=1}^{k^{\prime}},I)=G(\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}},\\{r_{i}\\}_{i=1}^{k^{\prime}},I^{+})$.
Thus the difference

$\prod_{i=1}^{k}\frac{m_{i}^{\alpha_{i}}\cdot
m_{i}!}{t_{*}^{m_{i}}}\int_{0<r_{1}<\cdots<r_{k^{\prime}}<t_{\tau}}F(\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}},\\{r_{i}\\}_{i=1}^{k^{\prime}},I)G(\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}},\\{r_{i}\\}_{i=1}^{k^{\prime}},I)\prod_{i=1}^{k^{\prime}}dr_{i}\\\
-\prod_{i=1}^{k}\frac{m_{i}^{\alpha_{i}}\cdot
m_{i}!}{t_{*}^{m_{i}}}\int_{0<r_{1}<\cdots<r_{k^{\prime}}<t_{\tau}}F(\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}},\\{r_{i}\\}_{i=1}^{k^{\prime}},I^{+})G(\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}},\\{r_{i}\\}_{i=1}^{k^{\prime}},I^{+})\prod_{i=1}^{k^{\prime}}dr_{i}$

equals

$\prod_{i=1}^{k}\frac{m_{i}^{\alpha_{i}}\cdot
m_{i}!}{t_{*}^{m_{i}}}\int_{0<r_{1}<\cdots<r_{k^{\prime}}<t_{\tau}}\big{(}F(\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}},\\{r_{i}\\}_{i=1}^{k^{\prime}},I)-F(\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}},\\{r_{i}\\}_{i=1}^{k^{\prime}},I^{+})\big{)}\\\
\times
G(\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}},\\{r_{i}\\}_{i=1}^{k^{\prime}},I)\prod_{i=1}^{k^{\prime}}dr_{i}.$

As
$G(\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}},\\{r_{i}\\}_{i=1}^{k^{\prime}},I)$
is uniformly bounded, by Lemma 5.4 we have that this expression $\to 0$ as
$\lambda\to\infty$.

Now it only remains the term where
$\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}}=\\{l_{i}\\}_{i=1}^{k}$, i.e. as
$\lambda\to\infty$ we have

$\prod_{i=1}^{k}\frac{m_{i}^{\alpha_{i}}\cdot
m_{i}!}{t_{*}^{m_{i}}}\int_{0<r_{1}<\cdots<r_{k}<t_{\tau}}F(\\{l_{i}\\}_{i=1}^{k},\\{r_{i}\\}_{i=1}^{k},I)G(\\{l_{i}\\}_{i=1}^{k},\\{r_{i}\\}_{i=1}^{k},I)\prod_{i=1}^{k}dr_{i}\\\
-\prod_{i=1}^{k}\frac{m_{i}^{\alpha_{i}}\cdot
m_{i}!}{t_{*}^{m_{i}}}\int_{0<r_{1}<\cdots<r_{k}<t_{\tau}}F(\\{l_{i}\\}_{i=1}^{k},\\{r_{i}\\}_{i=1}^{k},I^{+})G(\\{l_{i}\\}_{i=1}^{k},\\{r_{i}\\}_{i=1}^{k},I^{+})\prod_{i=1}^{k}dr_{i}\to
0.$

By Lemma 5.4 we have that as $\lambda\to\infty$,

$\prod_{i=1}^{k}\frac{m_{i}^{\alpha_{i}}\cdot
m_{i}!}{t_{*}^{m_{i}}}\int_{0<r_{1}<\cdots<r_{k}<t_{\tau}}(F(\\{l_{i}\\}_{i=1}^{k},\\{r_{i}\\}_{i=1}^{k},I)-F(\\{l_{i}\\}_{i=1}^{k},\\{r_{i}\\}_{i=1}^{k},I^{+}))\\\
\times
G(\\{l_{i}\\}_{i=1}^{k},\\{r_{i}\\}_{i=1}^{k},I^{+})\prod_{i=1}^{k}dr_{i}\to
0,$

since $G(\\{l_{i}\\}_{i=1}^{k},\\{r_{i}\\}_{i=1}^{k},I^{+})$ is uniformly
bounded. Thus we have that

$\prod_{i=1}^{k}\frac{m_{i}^{\alpha_{i}}\cdot
m_{i}!}{t_{*}^{m_{i}}}\int_{0<r_{1}<\cdots<r_{k}<t_{\tau}}F(\\{l_{i}\\}_{i=1}^{k},\\{r_{i}\\}_{i=1}^{k},I)\\\
\times(G(\\{l_{i}\\}_{i=1}^{k},\\{r_{i}\\}_{i=1}^{k},I)-G(\\{l_{i}\\}_{i=1}^{k},\\{r_{i}\\}_{i=1}^{k},I^{+}))\prod_{i=1}^{k}dr_{i}\to
0,$ (5.3)

as we send $\lambda\to\infty$.

By Lemma 5.1, the function

$(r_{1},\ldots,r_{k})\mapsto
G(\\{l_{i}\\}_{i=1}^{k},\\{r_{i}\\}_{i=1}^{k},I)-G(\\{l_{i}\\}_{i=1}^{k},\\{r_{i}\\}_{i=1}^{k},I^{+})$
(5.4)

would be analytic for $0<r_{1}<\cdots<r_{k}<t_{\tau}$, and can be analytically
extended to $\mathbb{C}^{k}$. Thus if it is not identically $0$, by taking the
first (in the dictionary order of the powers) nonzero term in its Taylor
expansion, there would exist $\beta_{1},\cdots,\beta_{k}\in\mathbb{Z}_{\geq
0}$, such that for any $s_{1},\cdots,s_{k}>0$, we have

$\prod_{i=1}^{k}m_{i}^{\beta_{i}}(G(\\{l_{i}\\}_{i=1}^{k},\\{\frac{s_{i}}{m_{i}}\\}_{i=1}^{k},I)-G(\\{l_{i}\\}_{i=1}^{k},\\{\frac{s_{i}}{m_{i}}\\}_{i=1}^{k},I^{+}))\to
D\prod_{i=1}^{k}s_{i}^{\beta_{i}},$

where $D\neq 0$ is a constant; and that the absolute value of the left hand
side is bounded by some constant, uniformly in all $m_{i}$ and $s_{i}$. Using
this and Lemma 5.5, by dominated convergence theorem we get a contradiction
with (5.3). Thus we have that (5.4) must be $0$, i.e.,
$G(\\{l_{i}\\}_{i=1}^{k},\\{r_{i}\\}_{i=1}^{k},I)=G(\\{l_{i}\\}_{i=1}^{k},\\{r_{i}\\}_{i=1}^{k},I^{+})$
for any $0<r_{1}<\cdots<r_{k}<t_{\tau}$, which is precisely the conclusion we
want. ∎

###  5.3 Bounds on transition probabilities from cutting times

In this subsection we prove Lemma 5.3 and 5.4. We start with the pre-limit
bounds. The first one is a straight forward approximation by independent jumps
to the right.

######  Lemma 5.6.

Let $\\{l_{i}^{\prime}\\}_{i=1}^{C_{*}}$ be any permutation of
$1,\cdots,C_{*}$, and let $\kappa[j]$ be the number such that
$l_{\kappa[j]}^{\prime}=l_{j}$ for any $1\leq j\leq k$. Take any
$0<r_{1}<\cdots<r_{C_{*}}$. If each $r_{\kappa[j]}<t_{*}$, and $\lambda$ is
large enough (depending on $t_{*}$ and $A_{*}+B_{*}$), we have

$\mathbb{P}[\mathcal{E}\mid\\{R_{i}\\}_{i=1}^{C_{*}}=\\{r_{i}\\}_{i=1}^{C_{*}},\\{L_{i}\\}_{i=1}^{C_{*}}=\\{l_{i}^{\prime}\\}_{i=1}^{C_{*}}]<\prod_{j=1}^{k}2e^{-(t_{*}-r_{\kappa[j]})}\frac{(t_{*}-r_{\kappa[j]})^{m_{j}-(A_{*}+B_{*}+1-\kappa[j])}}{(m_{j}-(A_{*}+B_{*}+1-\kappa[j]))!}.$

If $r_{\kappa[j]}\geq t_{*}$ for some $1\leq j\leq k$ then the left hand side
equals zero.

###### Proof.

The second part is obvious from the definition of $\mathcal{E}$, so we focus
on the first part. Below we assume events
$\\{R_{i}\\}_{i=1}^{C_{*}}=\\{r_{i}\\}_{i=1}^{C_{*}},\\{L_{i}\\}_{i=1}^{C_{*}}=\\{l_{i}^{\prime}\\}_{i=1}^{C_{*}}$.

For each $1\leq j\leq k$, and $i^{\prime}\in\mathbb{N}$, we let
$w_{j,i^{\prime}}$ be the time when the particle colored
$l_{\kappa[j]}^{\prime}=l_{j}$ makes the $i^{\prime}$-th jump to the right
since time $r_{\kappa[j]}$. Note that here we simply ignore jumps to the left.
We also denote $w_{j,0}=r_{\kappa[j]}$. Denote $E_{j,i^{\prime}}$ as the total
amount of time, between times $w_{j,i^{\prime}-1}$ and $w_{j,i^{\prime}}$,
such that the particle right next to the particle colored
$l_{\kappa[j]}^{\prime}=l_{j}$ has a larger color; i.e., when that particle is
able to jump to the right. Then we would have that $E_{j,i^{\prime}}$ for all
$1\leq j\leq k$ and $i^{\prime}\in\mathbb{N}$ are i.i.d.
$\operatorname{Exp}(1)$.

Under the event $\mathcal{E}$ we must have that

$\sum_{i^{\prime}=1}^{m_{j}-(A_{*}+B_{*}+1-\kappa[j])}E_{j,i^{\prime}}\leq
t_{*}-r_{\kappa[j]},$

for each $1\leq j\leq k$. Thus we get the conclusion from the probability of
such event for each $j$, assuming that $m_{j}-(A_{*}+B_{*}+1-\kappa[j])$ is
large enough. ∎

The next pre-limit bound is on the difference of the transition probability,
for different sets of cutting time information.

######  Lemma 5.7.

Let $\\{l_{i}^{\prime}\\}_{i=1}^{C_{*}}$ and
$\\{\overline{l}_{i}^{\prime}\\}_{i=1}^{C_{*}}$ be two permutation of
$1,\cdots,C_{*}$, and take $0<r_{1}<\cdots<r_{C_{*}}$,
$0<\overline{r}_{1}<\cdots<\overline{r}_{C_{*}}$. Let $1\leq k^{\prime}\leq
C_{*}$, and suppose that $l_{i}^{\prime}=\overline{l}_{i}^{\prime}$,
$r_{i}=\overline{r}_{i}$ for each $1\leq i\leq k^{\prime}$, and
$r_{k^{\prime}}<t_{\tau}$, and
$r_{k^{\prime}+1},\overline{r}_{k^{\prime}+1}>t_{\tau}$ if $k^{\prime}<C_{*}$.
Let $\kappa[j]$ be the number such that $l_{\kappa[j]}^{\prime}=l_{j}$ for any
$1\leq j\leq k$, and we also assume that each $\kappa[j]\leq k^{\prime}$. Then
we have

$\left|\mathbb{P}[\mathcal{E}\mid\\{R_{i}\\}_{i=1}^{C_{*}}=\\{r_{i}\\}_{i=1}^{C_{*}},\\{L_{i}\\}_{i=1}^{C_{*}}=\\{l_{i}^{\prime}\\}_{i=1}^{C_{*}}]-\mathbb{P}[\mathcal{E}\mid\\{R_{i}\\}_{i=1}^{C_{*}}=\\{\overline{r}_{i}\\}_{i=1}^{C_{*}},\\{L_{i}\\}_{i=1}^{C_{*}}=\\{\overline{l}_{i}^{\prime}\\}_{i=1}^{C_{*}}]\right|\\\
<H\left(\sum_{j=1}^{k}m_{j}^{2}\left(\frac{t_{*}-t_{\tau}}{t_{*}-r_{\kappa[j]}}\right)^{m_{j}}\right)\prod_{j=1}^{k}\frac{(t_{*}-r_{\kappa[j]})^{m_{j}}}{(m_{j}-(A_{*}+B_{*}+1-\kappa[j]))!},$

if $\lambda>H$. Here $H$ is a large constant depending on
$A_{*},B_{*},C_{*},t_{*},t_{\tau}$.

The general idea of this lemma is that, for two sets of cutting time
information that differ only after time $t_{\tau}$, the transition
probabilities are close. This is because that the particles would jump fast,
and it is unlikely for a particle joining after time $t_{\tau}$ to catch up
with and affect the evolution of those particles to its right.

###### Proof.

We take $\overline{\eta}$ as a copy of $\eta$, and we consider the evolution
of $\eta$ on $\Omega=\bigcup_{1\leq i\leq C_{*}}\\{(x,t):x\geq
A_{*}+B_{*}+1-i,t\geq r_{i}\\}$, and the evolution of $\overline{\eta}$ on
$\overline{\Omega}=\bigcup_{1\leq i\leq C_{*}}\\{(x,t):x\geq
A_{*}+B_{*}+1-i,t\geq\overline{r}_{i}\\}$, conditional on
$\\{R_{i}\\}_{i=1}^{C_{*}}=\\{r_{i}\\}_{i=1}^{C_{*}},\\{L_{i}\\}_{i=1}^{C_{*}}=\\{l_{i}^{\prime}\\}_{i=1}^{C_{*}}$
or
$\\{R_{i}\\}_{i=1}^{C_{*}}=\\{\overline{r}_{i}\\}_{i=1}^{C_{*}},\\{L_{i}\\}_{i=1}^{C_{*}}=\\{\overline{l}_{i}^{\prime}\\}_{i=1}^{C_{*}}$,
respectively. We couple $\eta$ and $\overline{\eta}$ by using the same Poisson
clocks $\Omega\cap\overline{\Omega}$. We consider an additional particle
$p_{*}:[t_{\tau},\infty)\to\mathbb{Z}$, such that
$p_{*}(t_{\tau})=A_{*}+B_{*}-k^{\prime}$, and it jumps to the right according
to the Poisson clock of the edge to the right of it, until
$T_{*}:=\inf\\{t\geq t_{\tau}:\eta_{t}(p_{*}(t))\in\\{l_{i}\\}_{i=1}^{k}\\}$,
the time when $p_{*}$ catches up with the particles in $\eta$. We let $p_{*}$
continue to jump to the right with rate $1$ after time $T_{*}$, but use
independent Poisson clocks.

At any time $t\in[t_{\tau},T_{*}]$, in either $\eta$ or $\overline{\eta}$,
there is no particle to the right of $p_{*}(t)$ with color in
$\\{l_{i}^{\prime}\\}_{i=k^{\prime}+1}^{C_{*}}=\\{\overline{l}_{i}^{\prime}\\}_{i=k^{\prime}+1}^{C_{*}}$.
Then we have that $\eta_{t}$ and $\overline{\eta}_{t}$ are the same on
$[p_{*}(t)+1,\infty)\cap\mathbb{Z}$. Thus if $T_{*}\geq t_{*}$, the event
$\mathcal{E}$ holds for $\eta$ if and only if it holds for $\overline{\eta}$.
With symmetry between $\eta$ and $\overline{\eta}$, it now suffices to upper
bound

$\mathbb{P}[\mathcal{E},T_{*}<t_{*}\mid\\{R_{i}\\}_{i=1}^{C_{*}}=\\{r_{i}\\}_{i=1}^{C_{*}},\\{L_{i}\\}_{i=1}^{C_{*}}=\\{l_{i}^{\prime}\\}_{i=1}^{C_{*}}].$

For each $i^{\prime}\in\mathbb{N}$, we let $E_{i^{\prime}}$ be the waiting
time between the $i^{\prime}-1$-th jump and the $i^{\prime}$-th jump of the
particle $p_{*}$. For each $1\leq j\leq k$, we again take $E_{j,i^{\prime}}$
as in the proof of Lemma 5.6; i.e., it is the waiting time for the
$i^{\prime}$-th jump to the right since time $r_{\kappa[j]}$, for the particle
colored $l_{\kappa[j]}^{\prime}=l_{j}$. Then we have that they are all
independent $\operatorname{Exp}(1)$ random variables, since before $T_{*}$ the
particle $p_{*}$ is always to the left of the particle colored
$l_{\kappa[j]}^{\prime}=l_{j}$.

The events $\mathcal{E},T_{*}<t_{*}$ imply the following:

  1. 1.

for each $1\leq j\leq k$,

$\sum_{i^{\prime}=1}^{m_{j}-(A_{*}+B_{*}+1-\kappa[j])}E_{j,i^{\prime}}\leq
t_{*}-r_{\kappa[j]};$

  2. 2.

for some $1\leq\overline{j}\leq k$ and some $1\leq\overline{i}\leq
m_{\overline{j}}-(A_{*}+B_{*}+1-\kappa[\overline{j}])$,
$\gamma\in\mathbb{Z}_{\geq 0}$, there is

$\sum_{i^{\prime}=1}^{m_{\overline{j}}-(A_{*}+B_{*}+1-\kappa[\overline{j}])+\gamma}E_{\overline{j},i^{\prime}}\leq
t_{*}-r_{\kappa[\overline{j}]},\quad\sum_{i^{\prime}=1}^{\overline{i}-\kappa[\overline{j}]+k^{\prime}}E_{i^{\prime}}+\sum_{i^{\prime}=\overline{i}+\gamma}^{m_{\overline{j}}-(A_{*}+B_{*}+1-\kappa[\overline{j}])+\gamma}E_{\overline{j},i^{\prime}}\leq
t_{*}-t_{\tau}.$

Here $\gamma$ corresponds to the number of left steps the particle colored
$l_{\kappa[\overline{j}]}^{\prime}$ has taken before $T_{*}$, and
$A_{*}+B_{*}+\overline{i}-\kappa[\overline{j}]$ corresponds to $p_{*}(T_{*})$.

When $\lambda$ is large enough, the probability of the first event (for each
$1\leq j\leq k$) is bounded by

$2e^{-(t_{*}-r_{\kappa[j]})}\frac{(t_{*}-r_{\kappa[j]})^{m_{j}-(A_{*}+B_{*}+1-\kappa[j])}}{(m_{j}-(A_{*}+B_{*}+1-\kappa[j]))!}.$

For the second event, for fixed $\overline{j},\overline{i},\gamma$, when
$\lambda$ is large enough, the probability is bounded by

$2e^{-(t_{*}-r_{\kappa[\overline{j}]})}\frac{(t_{*}-r_{\kappa[\overline{j}]})^{m_{\overline{j}}-A_{*}-B_{*}+\kappa[\overline{j}]+\gamma-1}}{(m_{\overline{j}}-A_{*}-B_{*}+\kappa[\overline{j}]+\gamma-1)!}\wedge
2e^{-(t_{*}-t_{\tau})}\frac{(t_{*}-t_{\tau})^{m_{\overline{j}}-A_{*}-B_{*}+k^{\prime}}}{(m_{\overline{j}}-A_{*}-B_{*}+k^{\prime})!}.$

Below we use $H$ to denote a large constant depending on
$A_{*},B_{*},C_{*},t_{*},t_{\tau}$, and the value can change from line to
line. We first sum over $\gamma$, and the above is bounded by
$Hm_{\overline{j}}\frac{(t_{*}-t_{\tau})^{m_{\overline{j}}-A_{*}-B_{*}+k^{\prime}}}{(m_{\overline{j}}-A_{*}-B_{*}+k^{\prime})!}$;
then by summing over $\overline{i}$ we get an upper bound of

$Hm_{\overline{j}}^{2}\frac{(t_{*}-t_{\tau})^{m_{\overline{j}}-A_{*}-B_{*}+k^{\prime}}}{(m_{\overline{j}}-A_{*}-B_{*}+k^{\prime})!}<Hm_{\overline{j}}^{2}\frac{(t_{*}-t_{\tau})^{m_{\overline{j}}-(A_{*}+B_{*}+1-\kappa[\overline{j}])}}{(m_{\overline{j}}-(A_{*}+B_{*}+1-\kappa[\overline{j}]))!}.$

Then with the bounds for the probabilities of the first event for each
$j\neq\overline{j}$, by summing over $\overline{j}$ the conclusion follows. ∎

To deduce Lemma 5.3 and 5.4 from the the above two lemmas, we need one
additional result, on the relation between $\mathcal{E}$,
$\\{R_{i}\\}_{i=1}^{C_{*}},\\{L_{i}\\}_{i=1}^{C_{*}}$, and $I$ or $I^{+}$.

######  Lemma 5.8.

Let $\\{l_{i}^{\prime}\\}_{i=1}^{C_{*}}$ be any permutation of
$1,\cdots,C_{*}$, $\hat{I}=I$ or $I^{+}$, and take any
$0<r_{1}<\cdots<r_{C_{*}}$. If $\lambda$ is large enough (depending on $t_{*}$
and $A_{*}+B_{*}$), we have

$\mathbb{P}[\mathcal{E}\mid\\{R_{i}\\}_{i=1}^{C_{*}}=\\{r_{i}\\}_{i=1}^{C_{*}},\\{L_{i}\\}_{i=1}^{C_{*}}=\\{l_{i}^{\prime}\\}_{i=1}^{C_{*}},\hat{I}]=\mathbb{P}[\mathcal{E}\mid\\{R_{i}\\}_{i=1}^{C_{*}}=\\{r_{i}\\}_{i=1}^{C_{*}},\\{L_{i}\\}_{i=1}^{C_{*}}=\\{l_{i}^{\prime}\\}_{i=1}^{C_{*}}].$

###### Proof.

This proof follows a similar idea as the proof of Lemma 4.1.

We denote $\mathcal{E}_{-}$ as the event where
$\\{R_{i}\\}_{i=1}^{C_{*}}=\\{r_{i}\\}_{i=1}^{C_{*}},\\{L_{i}\\}_{i=1}^{C_{*}}=\\{l_{i}^{\prime}\\}_{i=1}^{C_{*}}$.
We would show that conditional on $\mathcal{E}_{-}$, the events $\hat{I}$ and
$\mathcal{E}$ are independent.

We recall the Poisson field $\Pi$ on $\mathbb{Z}\times[0,\infty)$, where for
each $x\in\mathbb{Z}$ and any $0\leq a<b$, $\Pi(\\{x\\}\times[a,b])$ would be
the number of times that the clock on the edge $(x-1,x)$ rings, in the time
interval $[a,b]$. Denote

$U^{-}:=\\{(x,t):x\leq
A_{*}+B_{*}-C_{*}\\}\cup\bigcup_{i=1}^{C_{*}}\\{(x,t):0\leq t<r_{i},x\leq
A_{*}+B_{*}-i+1\\},$

and $U^{+}=\mathbb{Z}\times[0,\infty)\setminus U^{-}$. By Lemma 3.3, we have
that the event $\mathcal{E}_{-}$ is measurable with respect to $\Pi$ on
$U_{-}$, so independent of $\Pi$ on $U_{+}$.

We then claim that conditional on $\mathcal{E}_{-}$, the event $\hat{I}$ is
measurable with respect to $\Pi$ on $U^{-}$. Indeed, given $\mathcal{E}_{-}$,
for any $\tau<i\leq g$ and $1\leq j\leq k_{i}$, we would have that
$(A_{i,j}+B_{i,j}-i^{\prime}+1,T^{A_{i,j}}_{B_{i,j},i^{\prime}})\in U^{-}$ and
$(A_{i,j}^{+}+B_{i,j}-i^{\prime}+1,T^{A_{i,j}^{+}}_{B_{i,j},i^{\prime}})\in
U^{-}$ for any $1\leq i^{\prime}\leq C_{i,j}$. Thus by Lemma 3.3, conditional
on $\mathcal{E}_{-}$, $T^{A_{i,j}}_{B_{i,j},C_{i,j}}$ and
$T^{A_{i,j}^{+}}_{B_{i,j},C_{i,j}}$ are measurable with respect to $\Pi$ on
$U^{-}$.

We next show that conditional on $\mathcal{E}_{-}$, the event $\mathcal{E}$ is
measurable with respect to $\Pi$ on $U^{+}$, when $\lambda$ is large enough.
Recall from the proof of Lemma 5.2, that the event $\mathcal{E}$ is determined
by $I_{A,B,C}^{t_{*}}$, for all $A\in\mathbb{Z}$ and $B,C\in\mathbb{N}$, such
that $A\leq A_{*}$, $A-C\geq A_{*}-C_{*}$, and $A+B-C+1\geq m_{k}$. By taking
$\lambda$ large enough we would have that $A+B-C+1\geq A_{*}+B_{*}$. We next
show that for such $A,B,C$, the event $I_{A,B,C}^{t_{*}}$ is determined by
$\Pi$ on $U^{+}$, conditional on $\mathcal{E}_{-}$.

Indeed, let $\kappa[1]<\cdots<\kappa[C]$ be the first $C$ numbers in the set
$\\{i:1\leq i\leq C_{*},l^{\prime}_{i}\leq C_{*}+A-A_{*}\\}$. For any $1\leq
i\leq C$, we take $B^{\prime}_{i}\in\mathbb{N}$ such that
$A+B^{\prime}_{i}-i+1=A_{*}+B_{*}-\kappa[i]+1$. We then have that
$T^{A}_{B^{\prime}_{i},i}=r_{\kappa[i]}$, given $\mathcal{E}_{-}$. Then by
Lemma 3.4, conditional on $\mathcal{E}_{-}$, the event $I_{A,B,C}^{t_{*}}$ is
determined by $\Pi$ on $U^{+}$.

By considering all such $A,B,C$, we have that $\mathcal{E}$ is determined by
$\Pi$ on $U^{+}$, conditional on $\mathcal{E}_{-}$. Thus we conclude that the
events $\hat{I}$ and $\mathcal{E}$ are independent conditional on
$\mathcal{E}_{-}$, and that the conclusion follows. ∎

We can now prove Lemma 5.3 using Lemma 5.6 and 5.8.

###### Proof of Lemma 5.3.

For each $1\leq j\leq k$, let $\kappa[j]$ be the number such that
$l_{\kappa[j]}^{\prime}=l_{j}$, if
$l_{j}\in\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}}$, and $\kappa[j]=0$
otherwise. By Lemma 5.6 and 5.8, we have

$F(\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}},\\{r_{i}\\}_{i=1}^{k^{\prime}},\hat{I})\\\
<H\prod_{j:1\leq j\leq
k,\kappa[j]>0}\frac{t_{*}^{m_{j}}}{(m_{j}-A_{*}-B_{*}-1+\kappa[j])!}\prod_{j:1\leq
j\leq
k,\kappa[j]=0}\frac{(t_{*}-t_{\tau})^{m_{j}}}{(m_{j}-A_{*}-B_{*}+k^{\prime})!}.$

where $H$ is a constant depending on $t_{*},t_{\tau},A_{*},B_{*},C_{*}$.

We next integrate over all $0<r_{1}<\cdots<r_{k^{\prime}}<t_{\tau}$, and
multiply $\prod_{j=1}^{k}\frac{m_{j}^{\alpha_{j}}\cdot
m_{j}!}{t_{*}^{m_{j}}}$; then we get that

$\prod_{i=1}^{k}\frac{m_{i}^{\alpha_{i}}\cdot
m_{i}!}{t_{*}^{m_{i}}}\int_{0<r_{1}<\cdots<r_{k^{\prime}}<t_{\tau}}\mathbb{P}[\mathcal{E}\mid\\{R_{i}\\}_{i=1}^{k^{\prime}}=\\{r_{i}\\}_{i=1}^{k^{\prime}},R_{k^{\prime}+1}>t_{\tau},\\{L_{i}\\}_{i=1}^{k^{\prime}}=\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}},\hat{I}]\prod_{i=1}^{k^{\prime}}dr_{i}\\\
<Ht_{\tau}^{k^{\prime}}\prod_{j:1\leq j\leq
k,\kappa[j]>0}\frac{m_{j}^{\alpha_{j}}\cdot
m_{j}!}{(m_{j}-A_{*}-B_{*}-1+\kappa[j])!}\prod_{j:1\leq j\leq
k,\kappa[j]=0}\frac{m_{j}^{\alpha_{j}}\cdot
m_{j}!(1-t_{\tau}/t_{*})^{m_{j}}}{(m_{j}-A_{*}-B_{*}+k^{\prime})!}\\\ \leq
Ht_{\tau}^{k^{\prime}}\prod_{j=1}^{k}m_{j}^{\alpha_{j}+|A_{*}+B_{*}|}\prod_{j:1\leq
j\leq k,\kappa[j]=0}(1-t_{\tau}/t_{*})^{m_{j}}.$

Assuming that there exists some $j$ such that $\kappa[j]=0$, we must have that
the last line $\to 0$ as $\lambda\to\infty$.

Finally we consider the case where $\kappa[j]>0$ for each $1\leq j\leq k$. In
this case we must have that $k^{\prime}\geq k$. We claim that we would always
have that
$\mathbb{P}[\mathcal{E}\mid\\{R_{i}\\}_{i=1}^{k^{\prime}}=\\{r_{i}\\}_{i=1}^{k^{\prime}},R_{k^{\prime}+1}>t_{\tau},\\{L_{i}\\}_{i=1}^{k^{\prime}}=\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}},\hat{I}]=0$;
otherwise, we can take a sequence of swaps starting from
$\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}}$, ending with $\\{l_{i}\\}_{i=1}^{k}$
being the first $k$ coordinates. Thus we have
$\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}}\preceq\\{l_{i}\\}_{i=1}^{k}$ from the
definition of the partial ordering $\prec$, which contracts with a condition
in the statement. Thus the conclusion holds. ∎

For Lemma 5.4, it is deduced from Lemma 5.7 and 5.8.

###### Proof of Lemma 5.4.

Since $\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}}\preceq\\{l_{i}\\}_{i=1}^{k}$,
for each $1\leq j\leq k$ we can find $\kappa[j]$ such that
$l_{\kappa[j]}^{\prime}=l_{j}$. By Lemma 5.8, we have that

$\displaystyle|F(\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}},\\{r_{i}\\}_{i=1}^{k^{\prime}},I)-F(\\{l_{i}^{\prime}\\}_{i=1}^{k^{\prime}},\\{r_{i}\\}_{i=1}^{k^{\prime}},I^{+})|$
$\displaystyle\leq$
$\displaystyle\sup_{\\{r_{i}\\}_{i=k^{\prime}+1}^{C_{*}},\\{l_{i}^{\prime}\\}_{i=k^{\prime}+1}^{C_{*}}}\mathbb{P}[\mathcal{E}\mid\\{R_{i}\\}_{i=1}^{C_{*}}=\\{r_{i}\\}_{i=1}^{C_{*}},\\{L_{i}\\}_{i=1}^{C_{*}}=\\{l_{i}^{\prime}\\}_{i=1}^{C_{*}}]$
$\displaystyle-\inf_{\\{r_{i}\\}_{i=k^{\prime}+1}^{C_{*}},\\{l_{i}^{\prime}\\}_{i=k^{\prime}+1}^{C_{*}}}\mathbb{P}[\mathcal{E}\mid\\{R_{i}\\}_{i=1}^{C_{*}}=\\{r_{i}\\}_{i=1}^{C_{*}},\\{L_{i}\\}_{i=1}^{C_{*}}=\\{l_{i}^{\prime}\\}_{i=1}^{C_{*}}],$

where $\sup$ and $\inf$ are over all $\\{r_{i}\\}_{i=k^{\prime}+1}^{C_{*}}$
with $r_{C_{*}}>\cdots>r_{k^{\prime}+1}>t_{\tau}$, and all
$\\{l_{i}^{\prime}\\}_{i=k^{\prime}+1}^{C_{*}}$ such that
$\\{l_{i}^{\prime}\\}_{i=1}^{C_{*}}$ is a permutation of $1,\cdots,C_{*}$. By
Lemma 5.7, when $\lambda>H$ this is bounded by

$\displaystyle
H\left(\sum_{j=1}^{k}m_{j}^{2}\left(\frac{t_{*}-t_{\tau}}{t_{*}-r_{\kappa[j]}}\right)^{m_{j}}\right)\prod_{j=1}^{k}\frac{(t_{*}-r_{\kappa[j]})^{m_{j}}}{(m_{j}-(A_{*}+B_{*}+1-\kappa[j]))!}$
$\displaystyle\leq$ $\displaystyle
H\left(\sum_{j=1}^{k}m_{j}^{2}(1-t_{\tau}/t_{*})^{m_{j}}\right)\prod_{j=1}^{k}\frac{t_{*}^{m_{j}}}{(m_{j}-(A_{*}+B_{*}+1-\kappa[j]))!}$

for $H$ being a large constant depending on
$A_{*},B_{*},C_{*},t_{*},t_{\tau}$. By integrating over
$0<r_{1}<\cdots<r_{k^{\prime}}<t_{\tau}$ and multiplying
$\prod_{j=1}^{k}\frac{m_{j}^{\alpha_{j}}\cdot m_{j}!}{t_{*}^{m_{j}}}$, we get
an upper bound of

$Ht_{\tau}^{k^{\prime}}\left(\sum_{j=1}^{k}m_{j}^{2}(1-t_{\tau}/t_{*})^{m_{j}}\right)\prod_{j=1}^{k}m_{j}^{\alpha_{j}+|A_{*}+B_{*}|}<kHt_{\tau}^{k^{\prime}}m_{1}^{2}(1-t_{\tau}/t_{*})^{m_{k}}\prod_{j=1}^{k}m_{j}^{\alpha_{j}+|A_{*}+B_{*}|},$

which $\to 0$ as $\lambda\to\infty$. ∎

###  5.4 Asymptote of transition probability from cutting

This subsection is devoted to the proof of Lemma 5.5.

For the second statement, by Lemma 5.6 and 5.8, when $\lambda$ is large we
have the bound

$\prod_{i=1}^{k}2e^{-(t_{*}-s_{i}/m_{i})}\left(1-\frac{s_{i}}{m_{i}t_{*}}\right)^{m_{i}-(A_{*}+B_{*}+1-i)}<\prod_{i=1}^{k}2e^{-s_{i}/t_{*}},$

where the inequality is by the fact that
$\left(1-\frac{s_{i}}{m_{i}t_{*}}\right)^{m_{i}}\leq e^{-s_{i}/t_{*}}$, and
$e^{-(t_{*}-s_{i}/m_{i})}\left(1-\frac{s_{i}}{m_{i}t_{*}}\right)^{|A_{*}+B_{*}|}<1$.

Below we prove the first statement. We denote $\mathcal{D}$ as the
intersection of the events
$\\{R_{i}\\}_{i=1}^{k}=\\{\frac{s_{i}}{m_{i}}\\}_{i=1}^{k},R_{k+1}>t_{\tau},\\{L_{i}\\}_{i=1}^{k}=\\{l_{i}\\}_{i=1}^{k}$
and $I$, for simplicity of notations.

Conditional on $\mathcal{D}$, we recall the following setup from proofs in the
previous subsection. For each $1\leq j\leq k$, and $i^{\prime}\in\mathbb{N}$,
we let $w_{j,i^{\prime}}$ be the time when the particle colored $l_{j}$ makes
the $i^{\prime}$-th jump to the right since $\frac{s_{j}}{m_{j}}$ (note that
we ignore jumps to the left). We also denote $w_{j,0}=\frac{s_{j}}{m_{j}}$.
Denote $E_{j,i^{\prime}}$ as follows: it is the time between
$w_{j,i^{\prime}-1}$ and $w_{j,i^{\prime}}$ such that the particle right next
to the particle colored $l_{j}$ has a larger color. We also consider an
additional particle $p_{*}:[t_{\tau},\infty)\to\mathbb{Z}$, such that
$p_{*}(t_{\tau})=A_{*}+B_{*}-k$, and it jumps to the right according to the
same Poisson clock as the one on the edge to the right of it, until time
$T_{*}:=\inf\\{t\geq t_{\tau}:\eta(p_{*}(t))\in\\{l_{i}\\}_{i=1}^{k}\\}$. We
let $p_{*}$ continue to jump to the right with rate $1$ after time $T_{*}$,
but use some independent Poisson clocks. For each $i^{\prime}\in\mathbb{N}$,
we let $E_{k+1,i^{\prime}}$ be the waiting time between the $i^{\prime}-1$-th
jump and the $i^{\prime}$-th jump of $p_{*}$. Then all these
$E_{j,i^{\prime}}$, for $1\leq j\leq k+1$ and $i^{\prime}\in\mathbb{N}$, are
independent $\operatorname{Exp}(1)$ random variables.

We next consider the event $\mathcal{E}_{1}$, defined as follows. For each
$1\leq j\leq k$ and $1\leq\gamma\leq m_{j}-A_{*}-B_{*}-1+j$, we have

$\frac{s_{j}}{m_{j}}+\sum_{i^{\prime}=1}^{\gamma}E_{j,i^{\prime}}<\frac{s_{j+1}}{m_{j+1}}+\sum_{i^{\prime}=1}^{\gamma}E_{j+1,i^{\prime}}.$

Here and below we take $m_{k+1}=1$ and $s_{k+1}=t_{\tau}$. We can then think
of $\mathcal{E}_{1}$ as the event where the particle colored $l_{j+1}$ does
not catch up with the particle colored $l_{j}$, for each $1\leq j<k$; and the
particle $p_{*}$ does not catch up with the particle colored $l_{k}$.

We also let $\mathcal{E}_{2}$ be the event where for each $1\leq j\leq k$,

$\sum_{i^{\prime}=1}^{m_{j}-A_{*}-B_{*}-1+j}E_{j,i^{\prime}}\leq
t_{*}-\frac{s_{j}}{m_{j}}\leq\sum_{i^{\prime}=1}^{m_{j}-A_{*}-B_{*}+j}E_{j,i^{\prime}},$

and let $\mathcal{E}_{2}^{\prime}$ be the event where for each $1\leq j\leq
k$,

$\sum_{i^{\prime}=1}^{m_{j}-A_{*}-B_{*}-1+j}E_{j,i^{\prime}}\leq
t_{*}-\frac{s_{j}}{m_{j}}.$ (5.5)

Then conditional on $\mathcal{D}$, we have that
$\mathcal{E}\cap\mathcal{E}_{1}=\mathcal{E}_{2}\cap\mathcal{E}_{1}$, and
$\mathcal{E},\mathcal{E}_{2}\subset\mathcal{E}_{2}^{\prime}$. We also note
that

$\mathbb{P}[\mathcal{E}_{2}\mid\mathcal{D}]=\prod_{j=1}^{k}e^{-(t_{*}-\frac{s_{j}}{m_{j}})}\frac{(t_{*}-\frac{s_{j}}{m_{j}})^{m_{j}-A_{*}-B_{*}-1+j}}{(m_{j}-A_{*}-B_{*}-1+j)!},$

since $\mathcal{E}_{2}$ precisely means that for each $1\leq j\leq k$, for a
Poisson point process on $[0,t_{*}-\frac{s_{j}}{m_{j}}]$ there are
$m_{j}-A_{*}-B_{*}-1+j$ particles. This implies that

$\prod_{j=1}^{k}\frac{(m_{j}-A_{*}-B_{*}-1+j)!}{t_{*}^{m_{j}-A_{*}-B_{*}-1+j}}\mathbb{P}[\mathcal{E}_{2}\mid\mathcal{D}]\to
e^{-kt_{*}}\prod_{j=1}^{k}e^{-s_{j}/t_{*}},$ (5.6)

as we send $\lambda\to\infty$. It now suffices to bound
$\mathbb{P}[\mathcal{E}\setminus\mathcal{E}_{1}\mid\mathcal{D}]+\mathbb{P}[\mathcal{E}_{2}\setminus\mathcal{E}_{1}\mid\mathcal{D}]$,
thus suffices to bound
$\mathbb{P}[\mathcal{E}_{2}^{\prime}\setminus\mathcal{E}_{1}\mid\mathcal{D}]$.

For each $1\leq\overline{j}\leq k$, we let $\mathcal{E}^{(\overline{j})}$
denote the event where there exists $1\leq\gamma\leq
m_{\overline{j}}-A_{*}-B_{*}-1+\overline{j}$, such that

$\sum_{i^{\prime}=1}^{\gamma}E_{\overline{j}+1,i^{\prime}}+\sum_{i^{\prime}=\gamma+1}^{m_{\overline{j}}-A_{*}-B_{*}-1+\overline{j}}E_{\overline{j},i^{\prime}}\leq
t_{*}-\frac{s_{\overline{j}+1}}{m_{\overline{j}+1}}.$ (5.7)

We then have that
$\mathcal{E}_{2}^{\prime}\setminus\mathcal{E}_{1}\subset\bigcup_{\overline{j}=1}^{k}\mathcal{E}^{(\overline{j})}$.

Below we let $H$ denote a large number depending on
$t_{*},t_{\tau},A_{*},B_{*},C_{*}$, and the value can change from line to
line. When $\lambda>H$, for given $\gamma$ the probability of (5.7) is bounded
by

$2e^{-(t_{*}-\frac{s_{\overline{j}+1}}{m_{\overline{j}+1}})}\frac{(t_{*}-\frac{s_{\overline{j}+1}}{m_{\overline{j}+1}})^{m_{\overline{j}}-A_{*}-B_{*}-1+\overline{j}}}{(m_{\overline{j}}-A_{*}-B_{*}-1+\overline{j})!}.$

By summing over $\gamma$ we get

$\mathbb{P}[\mathcal{E}^{(\overline{j})}\mid\mathcal{D}]<\frac{Hm_{\overline{j}}(t_{*}-\frac{s_{\overline{j}+1}}{m_{\overline{j}+1}})^{m_{\overline{j}}}}{(m_{\overline{j}}-A_{*}-B_{*}-1+\overline{j})!}.$

We also note that (5.5) for $j<\overline{j}$ is independent of
$\mathcal{E}^{(\overline{j})}$. These imply that

$\mathbb{P}[\mathcal{E}_{2}^{\prime}\setminus\mathcal{E}_{1}\mid\mathcal{D}]<\sum_{\overline{j}=1}^{k}\frac{Hm_{\overline{j}}(t_{*}-\frac{s_{\overline{j}+1}}{m_{\overline{j}+1}})^{m_{\overline{j}}}}{(m_{\overline{j}}-A_{*}-B_{*}-1+\overline{j})!}\prod_{j=1}^{\overline{j}-1}\frac{(t_{*}-\frac{s_{j}}{m_{j}})^{m_{j}}}{(m_{j}-A_{*}-B_{*}-1+j)!},$

so

$\prod_{j=1}^{k}\frac{(m_{j}-A_{*}-B_{*}-1+j)!}{t_{*}^{m_{j}-A_{*}-B_{*}-1+j}}\mathbb{P}[\mathcal{E}_{2}^{\prime}\setminus\mathcal{E}_{1}\mid\mathcal{D}]\\\
<\sum_{\overline{j}=1}^{k}\frac{Hm_{\overline{j}}(t_{*}-\frac{s_{\overline{j}+1}}{m_{\overline{j}+1}})^{m_{\overline{j}}}}{t_{*}^{m_{\overline{j}}}}\prod_{j=1}^{\overline{j}-1}\frac{(t_{*}-\frac{s_{j}}{m_{j}})^{m_{j}}}{t_{*}^{m_{j}}}\prod_{j=\overline{j}+1}^{k}\frac{(m_{j}-A_{*}-B_{*}-1+j)!}{t_{*}^{m_{j}}}.$

For the $\overline{j}$-th summand in the right hand side, as we send
$\lambda\to\infty$, we get

$\frac{m_{\overline{j}}(t_{*}-\frac{s_{\overline{j}+1}}{m_{\overline{j}+1}})^{m_{\overline{j}}}}{t_{*}^{m_{\overline{j}}}}e^{\frac{s_{\overline{j}+1}}{t_{*}}\frac{m_{\overline{j}}}{m_{\overline{j}+1}}}\to
0,$

since by taking the logarithm, we get

$\log(m_{\overline{j}})+\frac{s_{\overline{j}+1}}{t_{*}}\frac{m_{\overline{j}}}{m_{\overline{j}+1}}\left(1+\frac{t_{*}m_{\overline{j}+1}}{s_{\overline{j}+1}}\log\left(1-\frac{s_{\overline{j}+1}}{t_{*}m_{\overline{j}+1}}\right)\right)<\log(m_{\overline{j}})-\frac{1}{2}\frac{s_{\overline{j}+1}}{t_{*}}\frac{m_{\overline{j}}}{m_{\overline{j}+1}}\frac{s_{\overline{j}+1}}{t_{*}m_{\overline{j}+1}},$

where the inequality is by the elementary inequality of
$1+x^{-1}\log(1-x)<-x/2$ (for any $0<x<1$). As $\lambda\to\infty$ this
$\to-\infty$. For each $1\leq j<\overline{j}$, we have

$\frac{(t_{*}-\frac{s_{j}}{m_{j}})^{m_{j}}}{t_{*}^{m_{j}}}\to
e^{-s_{j}/t_{*}},$

and for each $\overline{j}<j\leq k$, we have

$e^{-\frac{1}{k}\frac{s_{\overline{j}+1}}{t_{*}}\frac{m_{\overline{j}}}{m_{\overline{j}+1}}}\frac{(m_{j}-A_{*}-B_{*}-1+j)!}{t_{*}^{m_{j}}}\to
0$

Thus we conclude that

$\prod_{j=1}^{k}\frac{(m_{j}-A_{*}-B_{*}-1+j)!}{t_{*}^{m_{j}-A_{*}-B_{*}-1+j}}\mathbb{P}[\mathcal{E}_{2}^{\prime}\setminus\mathcal{E}_{1}\mid\mathcal{D}]\to
0,$

as $\lambda\to\infty$. This with (5.6) implies the conclusion of Lemma 5.5.

##  6 Extensions of the shift-invariance

In this section, we first deduce Theorem 1.2 from Theorem 1.1, and we then
discuss some other directions of extending the shift-invariance.

time$A_{1}+B_{1}^{-}-C_{1}+1$$A_{1}+B_{1}-C_{1}+1$$A_{1}+B_{1}-C_{1}^{-}+1$$A_{2}+B_{2}^{-}-C_{2}+1$$A_{2}+B_{2}-C_{2}+1$$A_{2}+B_{2}-C_{2}^{-}+1$$A_{3}+B_{3}^{-}-C_{3}+1$$A_{3}+B_{3}-C_{3}+1$$A_{3}+B_{3}-C_{3}^{-}+1$$U_{1}$$U_{2}$$U_{3}$
Figure 5:  An illustration of the Poisson field $\Pi$ and the areas $U_{i}$.
Each horizontal segment indicates a particle in $\Pi$.

###### Proof of Theorem 1.2.

Without loss of generality we assume that each $V_{i}\neq\emptyset$, since
otherwise we just ignore it. By symmetry we assume that
$\mathcal{R}^{A_{i}}_{B_{i},C_{i}}\leq\mathcal{R}^{A_{i+1}}_{B_{i+1},C_{i+1}}$
and
$\mathcal{R}^{A_{i}^{\prime}}_{B_{i},C_{i}}\leq\mathcal{R}^{A_{i+1}^{\prime}}_{B_{i+1},C_{i+1}}$
for any $1\leq i<g$. For any $1\leq i<g$, we also assume that either
$A_{i}<A_{i+1}$ or $A_{i}^{\prime}<A_{i+1}^{\prime}$, i.e., we do not have
both $A_{i}=A_{i+1}$ and $A_{i}^{\prime}=A_{i+1}^{\prime}$. This is because,
otherwise we can combine $\\{T_{B,C}^{A_{i}}\\}_{(B,C)\in V_{i}}$ and
$\\{T_{B,C}^{A_{i+1}}\\}_{(B,C)\in V_{i+1}}$, and combine
$\\{T_{B,C}^{A_{i}^{\prime}}\\}_{(B,C)\in V_{i}}$ and
$\\{T_{B,C}^{A_{i+1}^{\prime}}\\}_{(B,C)\in V_{i+1}}$.

From the definitions, there is some $B_{i}^{-},C_{i}^{-}\in\mathbb{N}$, such
that $V_{i}=[B_{i}^{-},B_{i}]\times[C_{i}^{-},C_{i}]\cap\mathbb{Z}^{2}$. We
would also have that $[A_{i}+B_{i}^{-}-C_{i},A_{i}+B_{i}-C_{i}^{-}]$ for all
$1\leq i\leq g$ are mutually disjoint. Indeed, for any $1\leq i<g$, we would
have $A_{i}\leq A_{i+1}$, $A_{i}+B_{i}^{-}\geq A_{i+1}+B_{i+1}$ and
$A_{i}-C_{i}\geq A_{i+1}-C_{i+1}^{-}$. Thus we have
$A_{i}+B_{i}^{-}-C_{i}>A_{i+1}+B_{i+1}-C_{i+1}^{-}$, since otherwise we must
have that $A_{i}=A_{i+1}$, $B_{i}^{-}=B_{i+1}$, and $C_{i}=C_{i+1}^{-}$; note
that $A_{i}^{\prime}+B_{i}^{-}\geq A_{i+1}^{\prime}+B_{i+1}$ and
$A_{i}^{\prime}\leq A_{i+1}^{\prime}$, so $A_{i}^{\prime}=A_{i+1}^{\prime}$,
and we get a contradiction with our assumption above.

Take $\overline{V}_{i}=\\{(B_{i}^{-},C):C_{i}^{-}\leq C\leq
C_{i}\\}\cup\\{(B,C_{i}^{-}):B_{i}^{-}\leq B\leq B_{i}\\}$, the lower and left
boundary of $V_{i}$. By Theorem 1.1, the passages times
$\\{\\{T^{A_{i}}_{B,C}\\}_{(B,C)\in\overline{V}_{i}}\\}_{i=1}^{g}$ and
$\\{\\{T^{A_{i}^{\prime}}_{B,C}\\}_{(B,C)\in\overline{V}_{i}}\\}_{i=1}^{g}$
have the same joint distribution.

We take a family of positive real numbers
$\\{\\{t^{i}_{B,C}\\}_{(B,C)\in\overline{V}_{i}}\\}_{i=1}^{g}$, satisfying the
following conditions: for any $C^{-}_{i}\leq C<C_{i}$ we have
$t^{i}_{B^{-}_{i},C}<t^{i}_{B^{-}_{i},C+1}$; for any $B^{-}_{i}\leq B<B_{i}$
we have $t^{i}_{B,C^{-}_{i}}<t^{i}_{B+1,C^{-}_{i}}$.

Let $U_{i}\subset\mathbb{Z}\times[0,\infty)$ be the following set

$\left(\bigcup_{C^{-}_{i}<C\leq
C_{i}}\\{(A_{i}+B^{-}_{i}-C+1,t):t>t^{i}_{B,C^{-}_{i}}\\}\right)\cup\left(\bigcup_{B^{-}_{i}<B\leq
B_{i}}\\{(A_{i}+B-C^{-}_{i}+1,t):t>t^{i}_{B^{-}_{i},C}\\}\right),$

and let $U=\bigcup_{i=1}^{g}U_{i}$. See Figure 5. Similarly, we take
$U_{i}^{\prime}=\\{(x+A_{i}^{\prime}-A_{i},t):(x,t)\in U_{i}\\}$ and
$U^{\prime}=\bigcup_{i=1}^{g}U_{i}^{\prime}$.

Recall the Poisson field $\Pi$ on $\mathbb{Z}\times[0,\infty)$, where for each
$x\in\mathbb{Z}$ and any $0\leq a<b$, $\Pi(\\{x\\}\times[a,b])$ would be the
number of times that the clock on the edge $(x-1,x)$ rings, in the time
interval $[a,b]$. We would show the following:

  1. (i)

The event
$\\{\\{T^{A_{i}}_{B,C}\\}_{(B,C)\in\overline{V}_{i}}\\}_{i=1}^{g}=\\{\\{t^{i}_{B,C}\\}_{(B,C)\in\overline{V}_{i}}\\}_{i=1}^{g}$
is determined by $\Pi$ on $\mathbb{Z}\times[0,\infty)\setminus U$.

  2. (ii)

Given
$\\{\\{T^{A_{i}}_{B,C}\\}_{(B,C)\in\overline{V}_{i}}\\}_{i=1}^{g}=\\{\\{t^{i}_{B,C}\\}_{(B,C)\in\overline{V}_{i}}\\}_{i=1}^{g}$,
then $\\{T^{A_{i}}_{B,C}\\}_{(B,C)\in{V_{i}\setminus\overline{V}_{i}}}$ is
determined by $\Pi$ on $U_{i}$.

We first prove (i). For any $1\leq B^{\prime}<B_{i}^{-}$ and any $j>i$, there
must be $T^{A_{i}}_{B^{\prime},C_{i}}\leq T^{A_{j}}_{B,C}$ if
$A_{i}+B^{\prime}-C_{i}=A_{j}+B-C$ for some $(B,C)\in\overline{V}_{j}$.
Indeed, in $\mu^{A_{j}}_{T^{A_{j}}_{B,C}}$, there are at least $C$ particles
on or to the right of $A_{j}+B-C+1$; thus in $\mu^{A_{i}}_{T^{A_{j}}_{B,C}}$,
there are at least $C+A_{i}-A_{j}\geq C_{i}$ particles on or to the right of
$A_{j}+B-C+1=A_{i}+B^{\prime}-C_{i}+1$, implying that
$T^{A_{i}}_{B^{\prime},C_{i}}\leq T^{A_{j}}_{B,C}$. Similarly, for any $1\leq
C^{\prime}<C_{i}^{-}$ and any $j<i$, there must be
$T^{A_{i}}_{B_{i},C^{\prime}}\leq T^{A_{j}}_{B,C}$ if
$A_{i}+B_{i}-C^{\prime}=A_{j}+B-C$ for some $(B,C)\in\overline{V}_{i}$. Thus
the event
$\\{\\{T^{A_{i}}_{B,C}\\}_{(B,C)\in\overline{V}_{i}}\\}_{i=1}^{g}=\\{\\{t^{i}_{B,C}\\}_{(B,C)\in\overline{V}_{i}}\\}_{i=1}^{g}$
would imply that
$(A_{i}+B^{\prime}-C^{\prime}+1,T^{A_{i}}_{B^{\prime},C^{\prime}})\in\mathbb{Z}\times[0,\infty)\setminus
U$ for any $1\leq B^{\prime}\leq B_{i}^{-}$, $1\leq C^{\prime}\leq C_{i}$, or
$1\leq B^{\prime}\leq B_{i}$, $1\leq C^{\prime}\leq C_{i}^{-}$. By Lemma 3.3,
the intersection of these two events would be determined by $\Pi$ on
$\mathbb{Z}\times[0,\infty)\setminus U$, so we would get (i).

For (ii), the passage time $T^{A_{i}}_{B,C}$ for each
$(B,C)\in{V_{i}\setminus\overline{V}_{i}}$ is the smallest
$t>T^{A_{i}}_{B-1,C}\vee T^{A_{i}}_{B,C+1}$, such that there is a point at
$(t,A_{i}+B-C+1)$ in $\Pi$. Thus given
$\\{\\{T^{A_{i}}_{B,C}\\}_{(B,C)\in\overline{V}_{i}}\\}_{i=1}^{g}=\\{\\{t^{i}_{B,C}\\}_{(B,C)\in\overline{V}_{i}}\\}_{i=1}^{g}$,
we can determine
$\\{T^{A_{i}}_{B,C}\\}_{(B,C)\in{V_{i}\setminus\overline{V}_{i}}}$ by $\Pi$ on
$U_{i}$, recursively.

Then we have that conditional on
$\\{\\{T^{A_{i}}_{B,C}\\}_{(B,C)\in\overline{V}_{i}}\\}_{i=1}^{g}=\\{\\{t^{i}_{B,C}\\}_{(B,C)\in\overline{V}_{i}}\\}_{i=1}^{g}$,
the distributions of
$\\{T^{A_{i}}_{B,C}\\}_{(B,C)\in{V_{i}\setminus\overline{V}_{i}}}$ are
independent for each $1\leq i\leq g$, since all $U_{i}$ are mutually disjoint.
From the arguments of (ii), we would also see that for each $1\leq i\leq g$,
the distribution of
$\\{T^{A_{i}}_{B,C}\\}_{(B,C)\in{V_{i}\setminus\overline{V}_{i}}}$ conditional
on
$\\{\\{T^{A_{i}}_{B,C}\\}_{(B,C)\in\overline{V}_{i}}\\}_{i=1}^{g}=\\{\\{t^{i}_{B,C}\\}_{(B,C)\in\overline{V}_{i}}\\}_{i=1}^{g}$,
is the same as the distribution of
$\\{T^{A_{i}^{\prime}}_{B,C}\\}_{(B,C)\in{V_{i}\setminus\overline{V}_{i}}}$
conditional on
$\\{\\{T^{A_{i}^{\prime}}_{B,C}\\}_{(B,C)\in\overline{V}_{i}}\\}_{i=1}^{g}=\\{\\{t^{i}_{B,C}\\}_{(B,C)\in\overline{V}_{i}}\\}_{i=1}^{g}$.
These together imply that
$\\{\\{T^{A_{i}}_{B,C}\\}_{(B,C)\in{V_{i}}}\\}_{i=1}^{g}$ has the same
distribution as
$\\{\\{T^{A_{i}^{\prime}}_{B,C}\\}_{(B,C)\in{V_{i}}}\\}_{i=1}^{g}$. ∎

For completeness we also give the proof of Corollary 1.3

###### Proof of Corollary 1.3.

We assume that $T_{B,C}^{A}=0$ for any $A\in\mathbb{Z}$ and
$B,C\in\mathbb{Z}_{\geq 0}$, $BC=0$.

For each $1\leq i\leq g$, and take any $(B,C)\in\Gamma_{B_{i},C_{i}}^{A_{i}}$,
then the following results would be true: we would have
$(B-1,C)\in\Gamma_{B_{i},C_{i}}^{A_{i}}$, if
$T_{B-1,C}^{A_{i}}>T_{B,C-1}^{A_{i}}$; and we would have
$(B,C-1)\in\Gamma_{B_{i},C_{i}}^{A_{i}}$, if
$T_{B-1,C}^{A_{i}}<T_{B,C-1}^{A_{i}}$. The same results would be true if we
replace $A_{i}$ by $A_{i}^{\prime}$. Since $\\{\\{T^{A_{i}}_{B,C}\\}_{(B,C)\in
V_{i}}\\}_{i=1}^{g}$ has the same distribution as
$\\{\\{T^{A_{i}^{\prime}}_{B,C}\\}_{(B,C)\in V_{i}}\\}_{i=1}^{g}$ by Theorem
1.2, we must have that $\mathds{1}[T_{B-1,C}^{A_{i}}<T_{B,C-1}^{A_{i}}]$ has
the same distribution as
$\mathds{1}[T_{B-1,C}^{A_{i}^{\prime}}<T_{B,C-1}^{A_{i}^{\prime}}]$, jointly
for all $1\leq i\leq g$ and $B,C\in W_{i}$. Thus the conclusion follows. ∎

###  6.1 Some further questions

We now discuss some other possible extensions to Theorem 1.1 and Theorem 1.2.

A major question is whether some shift constraints in Theorem 1.1 and Theorem
1.2 can be lifted. Let’s consider just two passage times. Using arguments that
slightly generalize those in Example 2.5, or some simplification of the proof
of Theorem 1.1, we can get the following conditional equal in distribution.

######  Example 6.1.

Take $A_{1},A_{2},A_{2}^{\prime}\in\mathbb{Z}$,
$B_{1},B_{2},C_{1},C_{2}\in\mathbb{N}$, satisfying the following conditions:
$A_{1}\leq A_{2},A_{2}^{\prime}$, $A_{1}+B_{1}-C_{1}\geq
A_{2}+B_{2}-C_{2},A_{2}+B_{2}^{\prime}-C_{2}$, and $A_{1}+B_{1}\geq
A_{2}+B_{2},A_{2}^{\prime}+B_{2}$. For any $0<t_{1}\leq t_{2}$, we have

$\mathbb{P}[T^{A_{1}}_{B_{1},C_{1}}<t_{1},T^{A_{2}}_{B_{2},C_{2}}<t_{2}]=\mathbb{P}[T^{0}_{B,1}<t_{1},T^{1}_{1,C}<t_{2}].$

We note that this statement is non-trivial only if $C_{1}<C_{2}$, since
otherwise we would have that $T^{A_{1}}_{B_{1},C_{1}}\leq
T^{A_{2}}_{B_{2},C_{2}}$ and $T^{A_{1}}_{B_{1},C_{1}}\leq
T^{A_{2}^{\prime}}_{B_{2},C_{2}}$. The main difference between this example
and Theorem 1.2 is that, here the condition $A_{1}-C_{1}\geq
A_{2}-C_{2},A_{2}^{\prime}-C_{2}$ is replaced by the weaker ones
$A_{1}+B_{1}-C_{1}\geq A_{2}+B_{2}-C_{2},A_{2}+B_{2}^{\prime}-C_{2}$; whereas
the equal in distribution only holds in half of the space $[0,\infty)^{2}$.

To see that the condition $t_{1}\leq t_{2}$ is necessary, we can compute the
following example.

######  Example 6.2.

For any $t_{1},t_{2}>0$, we have

$\mathbb{P}[T^{0}_{3,1}=t_{1},T^{0}_{1,2}=t_{2}]=\mathbb{P}[T^{0}_{3,1}=t_{1},T^{1}_{1,2}=t_{2}]\\\
=\begin{cases}e^{-t_{2}}-e^{-t_{1}-t_{2}}(1+t_{1}),\quad&\text{ if }t_{1}\leq
t_{2}\\\ e^{-t_{1}}(t_{1}-t_{2}+1)-e^{-t_{1}-t_{2}}(1+t_{1}),\quad&\text{ if
}t_{1}>t_{2}\end{cases},$

and

$\mathbb{P}[T^{0}_{3,1}=t_{1},T^{2}_{1,2}=t_{2}]\\\
=\begin{cases}e^{-t_{2}}-e^{-t_{1}-t_{2}}(1+t_{1}),\quad&\text{ if }t_{1}\leq
t_{2}\\\
2e^{-t_{1}}+e^{-t_{1}-t_{2}}(t_{2}(t_{1}-t_{2})^{2}/2-2(t_{2}+1)),\quad&\text{
if }t_{1}>t_{2}\end{cases}.$

From this, it seems that the constraint of rectangle ordering is needed to get
equal in distribution. However, we expect that some conditional equal in
distribution would hold with weaker constraints, and it would be interesting
to find such an identity generalizing Example 6.1 to more then two passage
times.

In another direction (of lifting some shift constraints), one could ask
whether the ordering condition can be imposed only on pairs of passage times
where relative shift happens. To be more precise, one can consider the
following question, which is in a similar spirit as [BGW19, Conjecture 1.5].

######  Question 6.3.

Let $g\in\mathbb{N}$, and take $A_{i}\in\mathbb{Z}$,
$B_{i},C_{i}\in\mathbb{N}$, for all $1\leq i\leq g$. Let $1\leq\iota<g$, and
for any $1\leq i\leq g$ we let $A_{i}^{+}=A_{i}+\mathds{1}[i>\iota]$. Suppose
that for any $1\leq i\leq\iota<i^{\prime}\leq g$, we have
$\mathcal{R}^{A_{i}}_{B_{i},C_{i}}\leq\mathcal{R}^{A_{i^{\prime}}}_{B_{i^{\prime}},C_{i^{\prime}}}$and
$\mathcal{R}^{A_{i}^{+}}_{B_{i},C_{i}}\leq\mathcal{R}^{A_{i^{\prime}}^{+}}_{B_{i^{\prime}},C_{i^{\prime}}}$.
Are the vectors $\\{T_{B_{i},C_{i}}^{A_{i}}\\}_{i=1}^{g}$ and
$\\{T_{B_{i},C_{i}}^{A_{i}^{+}}\\}_{i=1}^{g}$ equal in distribution?

This equal in distribution (if true) would imply both Theorem 1.1 and Theorem
1.2. The main difference of this with Theorem 1.1 and Theorem 1.2 is that, the
rectangles $\mathcal{R}^{A_{i}}_{B_{i},C_{i}}$ for $1\leq i\leq\iota$ or for
$\iota<i\leq g$ are not ordered, and these $A_{i}$ can be different. We hope
that an answer to this question would give a better understanding of the
limitation of and the mechanism behind these equal in distributions in the
colored TASEP.

It is also natural to ask if some equal in distribution could be obtained for
the height function of the colored six-vertex model. For example, can we prove
some shift-invariance of the height function for more general points (than