The Local Limit of Random Sorting Networks
Omer Angel Duncan Dauvergne Alexander E. Holroyd Bálint Virág











bibcount
lbibitem
  
  bibcount.

bibsetup
   1
       
agsm


  theoremTheoremTheorems
  customthmTheoremTheorems
  lemmaLemmaLemmas
  propPropositionPropositions
  defnDefinitionDefinitions
  corollaryCorollaryCorollaries
  sectionSectionSections
  figureFigureFigures
  


letterpaper



equationsection








[],a;








plain
theoremTheoremsection
corollarytheoremCorollary
proptheoremProposition
lemmatheoremLemma

definition
*definitionDefinition 
exampletheoremExample
*remarkRemark






































































innercustomthmTheorem

  


















The Local Limit of Random Sorting Networks
    Omer Angel 
  Duncan Dauvergne
  Alexander E. Holroyd
  Bálint Virág 
    December 30, 2023
=========================================================================




   A sorting network is a geodesic path from 12 ⋯ n to n ⋯ 21
  in the Cayley graph of S_n generated by adjacent transpositions.
  For a uniformly random sorting network, we establish the existence of a
  local limit of the process of space-time locations of transpositions in a neighbourhood of an for a∈[0,1] as n→∞.  Here time
  is scaled by a factor of 1/n and space is not scaled.

  The limit is a swap process U on ℤ.  We show that U is
  stationary and mixing with respect to the spatial shift and has
  time-stationary increments.  Moreover, the only dependence on a is
  through time scaling by a factor of √(a(1-a)).

To establish the existence of U, we find a local limit for staircase-shaped Young tableaux. These Young tableaux are related to sorting networks through a bijection of Edelman and Greene.
  















§ INTRODUCTION



Consider the Cayley graph of the symmetric group S_n where the edges are given by adjacent transpositions
π_i = (i, i+1) for i ∈{1, …, n-1}.  The permutation
farthest from the identity 𝕀_n = 12⋯ n is the reverse permutation
_n = n⋯ 21, at distance n2. A sorting network is a path in this Cayley graph from the
identity to the reverse permutation of minimal possible length, namely
N = n2.  Equivalently, a sorting network is a representation _n = π_k_1π_k_2⋯π_k_N, with the path being the sequence _t = Π_i ≤ tπ_k_i, so that _0 = 𝕀_n and _N = _n.

For this reason, sorting networks are also known as reduced decompositions of the reverse permutation. Under this name, the combinatorics of sorting networks have been studied in detail, and there are connections between sorting networks and Schubert calculus, quasisymmetric functions, zonotopal tilings of polygons, and aspects of representation theory. We refer the reader to <cit.> and <cit.>  for more background in this direction.


   
    < g r a p h i c s >

   A “wiring diagram" for a sorting network with n = 4. In
     this diagram, trajectories are drawn as continuous curves for
     clarity, whereas our definition specifies that trajectories make jumps at swap
     times.
   


Sorting networks also arise in computer science, as a sorting network can be viewed as an algorithm for sorting a list.  Consider an array with
n elements, and let π_k_1 ,π_k_2, …, π_k_N be the
sequence of adjacent transpositions in a sorting network. At each step
i, instead of swapping the elements at positions k_i and
k_i+1, rearrange these elements in increasing order.  After all N
steps, this process will sort the entire array from any initial
order. If we start with _n, then every comparison will result in
a swap. 

It is helpful to think of the elements of {1,…,n} as labeled
particles.  Each step in the sorting network has the effect of swapping
the locations of two adjacent particles.  In this way, we can talk of
the particles as having -valued trajectories, with jumps of
{0,± 1} at integer times. Exactly two particles make a non-zero
jump at each time.  We denote by H_k(·) the trajectory of
particle k. Specifically, for t≤ N we have
σ_⌊ t ⌋(H_k(t)) = k (here and later
⌊ t ⌋ denotes the integer part).


The number of sorting networks of order n has been computed by
<cit.>.  Stanley observed that the number of sorting
networks equals the number of standard Young tableaux of a certain
staircase shape.  A bijective proof of this was provided by <cit.>.  Later, another bijective proof was
found by <cit.>, and recently <cit.> proved that the two bijections coincide.

modify paragraph
The study of random sorting networks was initiated by
<cit.>.


That paper considered the possible scaling limits
of sorting networks, namely weak limits of the scaled process

    lim_n→∞1/n H_⌊ an ⌋(t/N).

Here, space is rescaled by a factor of n and time by a factor of
N=n2.  With this scaling, H_⌊ an ⌋ becomes a function from
[0,1] to [0,1], starting at a and terminating at 1-a.  It is
not a priori clear that the limit exists (in distribution) or even that the
limit is continuous.  While existence of the above limit is still an
open problem, it is shown in <cit.> that the scaled
trajectories are equicontinuous in probability, and that subsequential
limits are
Hölder(α) for any α<1/2.  

It is also conjectured –
based on strong numerical evidence – that particle trajectories
converge to sine curves as n →∞.  We refer the reader to
<cit.> and <cit.>  for further
results and conjectures in this direction.

See also <cit.> for the scaling limit of certain
non-uniform random sorting networks under this scaling.  Different local
properties of random sorting networks have also been studied in
<cit.>.



 §.§ Limits of Sorting Networks


In this paper we are interested in local limits of sorting networks.
These limits are local in the sense that space is not scaled at all.
However, time still needs to be scaled by a factor of 1/n to observe a
non-constant process.  Thus instead of the sorting process finishing at
time N, it will finish at time N/n = (n-1)/2.

consistently use space-time, not time-space! Should look through -done
require no simultaneous jumps? do we prove this? Yes (injectivity).


  A swap function is a function U: ×_+ → with
  the following properties:
  
  
  * For each x, we have that U(x,·) is cadlag.
  
  * For each t we have that U(·,t) is a permutation of .
  
  * Define the trajectory H_x(t) by U(H_x(t),t)=x.  Then H_x
    is a cadlag path with nearest neighbour jumps for each x
    (i.e. the inverse permutation U^-1 is pointwise cadlag).
    
  * For any time t ∈ (0, ∞) and any x ∈, 
  
    lim_s → t^- U(x, s) = U(x + 1, t)     if and only if    lim_s → t^- U(x +1, s) = U(x, t).

  
  
  We think of a swap function as a collection of particle trajectories {H_x(·) : x ∈}.
Condition (iv) guarantees that the only way that a particle at position x can move up at time t is if the particle at position x+1 moves down. That is, particles move by swapping with their neighbours.   


We let  be the space of swap functions endowed with the following topology. A sequence of swap functions U_n → U if each of the cadlag paths U_n(x, ·) → U(x, ·) and H_n, x(·) → H_x(·). Convergence of cadlag paths is convergence in the Skorokhod topology. We refer to a random swap function as a swap process.



Our main result is the following limit theorem.

1
  There exists a swap process U so that the following holds.  Let
  u∈(-1,1), and let {k_n : n ∈} be any sequence such that k_n/n→ (1+u)/2.  Consider
  the shifted, and time scaled swap process
  
    U_n(x,t) = σ^n_⌊ nt/√(1-u^2)⌋(k_n + x) - k_n,

  where σ^n is a uniformly random n-element sorting network. Then
  
    U_n  U.

  Moreover, U is stationary and mixing of all orders with respect to
  the spatial shift, and has stationary increments in time: the
  permutation (U(·,s)^-1U(·,s+t))_t≥ 0 has the same law
  as (U(·,t))_t≥ 0.


The scaling in Theorem <ref> can be thought of in the following way. We first choose a spatial location u ∈ (-1 , 1) and look at a finite window around the position (1 + u)n/2. That is, we are concerned with particles whose labels are in a window [(1+u)n/2 - K, (1 + u)n/2 + K]. We want to know what the start of the sorting network looks like in this local window, at a scale where we see each of the individual swaps in the limit. To do this, we need to rescale time by a factor of 1/n. Note that the semicircle factor of √(1 - u^2) accounts for the fact that the swap rate is slower outside of the center of a random sorting network. On the global scale, this was proven in <cit.>, so the slow-down does not come as a surprise.


To precisely define each U_n, for x such that k_n+x∉{1,…,n}, we
use the convention that U_n(x,t)=x. For t>N/n we use the convention
that U_n(x,t) = U_n(x,N/n).  By doing this, any sorting network corresponds to a swap function. Convergence in the above theorem is weak convergence in the topology on .

 Recall also that a process is spatially
mixing of order m if translations by k_1,…,k_m are
asymptotically independent as min |k_i-k_j| →∞.  Spatial
mixing (even of order 2) of the system implies ergodicity.














  













As a by-product of the proof, we also show that for any t,
there is a bi-infinite sequence of particles in the limit process U that have
not moved by time t.  Consequently,  can be split into finite
intervals that are preserved by the permutation U(·, t).
Furthermore, we prove convergence in expectation of the number of swaps
between positions x and x+1 by some time t.  Specifically, if
s(x, t, U) is the number of swaps between positions x and x+1
up to time t in the process U, then 

    s(x, t, U_n) → s(x, t, U) = 4/πt
        as n→∞.

The expected number of swaps here agrees with corresponding global result obtained in <cit.>.

Theorem <ref> is proven in the k=0 case as Theorem <ref>.  The
general case is a consequence of Theorem <ref>.





 §.§ Limits of Young tableaux


To prove Theorem <ref>, we will first prove a limit theorem for
staircase Young tableaux, and then use the Edelman-Greene bijection to
translate this into a theorem about sorting networks. This theorem is of
interest in its own right.

Recall that for an integer N, a partition λ of N is
a non-increasing sequence (λ_1,…,λ_n) of positive
integers adding up to N.  The size of λ is
N = |λ| = ∑λ_i.

We shall use the convention ={1,2,…}.  The Young
  diagram associated with λ is the set A⊂×
given by A = {(i,j) : j ≤λ_i}.  A Young diagram is
traditionally drawn with a square for each element, and elements of A
are referred to as squares.  The lattice × is usually
oriented so that the square (1,1) is in the top left corner of the
lattice, but a different orientation will be convenient for us as
discussed below.


The staircase Young diagram of order n is the diagram of the
partition (n-1,n-2,…,1), of size N=n2.  

A standard Young tableau of shape λ is an order-preserving
bijection f: A→{1,…,N}, i.e., f is increasing in both i
and j.  For both the statement of our results and their proofs, it
will be more convenient to work with reverse standard Young
  tableaux, where the bijection is order-reversing.  Clearly
f ↦ N+1-f is a bijection between standard and reverse standard
Young tableaux.

Our second main result is a limit theorem for the entries near the diagonal of a
uniformly random staircase shaped Young tableau of order n.  To
introduce this theorem, we must first change the coordinate system for
staircase Young tableaux.



   
    < g r a p h i c s >

   The staircase Young diagram of order 5, i.e., of
     λ = (4,3,2,1), with squares labelled by a reverse standard
     Young tableau, shown in both the usual and in our coordinate system
     in .  One can think of the Young diagram λ = (4,3,2,1)
     as ten blocks in a triangular pile.  The entries in a tableau of
     shape λ give a possible order in which to place these
     blocks in the pile while respecting gravity.
   


Define = {(x,y) ∈× : x+y ∈ 2}.  We introduce a
partial order on  given by (x,y) ≤ (x',y') if x+y ≤ x'+y'
and y-x ≤ y'-x' (i.e. (x,y)≤ (x',y') if there is a path in
the lattice from the (x,y) to (x',y'), increasing in the
y-coordinate.  For (c,n-1) ∈, define 
T(c,n) = {z ∈ : z ≤ (c,n-1)}.
The set T(c,n) is the image of a staircase shaped Young diagram of
order n by the mapping (i,j)↦ (c-i+j, n+1-i-j).
We extend the definition of
a staircase diagram of order n and use that term for T(c,n). 
We call the value c the
center of the diagram.

The order on
T(c,n) induced by the order on  corresponds to reversing the
order on the Young diagram induced by the order on ×.  Therefore any order-preserving
bijection G: T(c,n) →{1,…,N} is a reverse standard Young
tableau.  We extend G to a function from → [0, ∞] by
setting G(z) = ∞ for all z ∉ T(c,n).  In the topology of
pointwise convergence in this function space, we then have the following
theorem about convergence of uniformly random reverse standard Young tableaux.

2

  There exists a random function F:→[0,∞) such that the
  following holds.  Fix u∈(-1,1), and a sequence k_n with
  k_n/n→ u.  Let G_n be a uniformly random staircase
  Young tableau on T(k_n,n). Then
  
    G_n/n1/√(1 - u^2) F.

  Moreover F is stationary and mixing of all orders with respect to
  translations by (2m,0) for m ∈.


The different components of Theorem
<ref> are proved in Theorem <ref>,
Proposition <ref>, and Theorem <ref> below.




 §.§ Overview


The structure of the paper is as follows.  Section <ref> contains the
necessary background about Young tableaux and the Edelman–Greene
bijection, as well as some basic domination lemmas about Young tableaux.  This will allow us to conclude Theorem <ref> from the limit theorem for staircase Young tableaux, Theorem <ref>. Section
<ref> contains the proof of Theorem <ref> for the case u=0.
reformulate is not quite right. revise overview - done...

In order to translate Theorem <ref> using the Edelman–Greene
bijection to a theorem about sorting networks, we require certain
regularity properties of the Young tableau limit.  These are proved in
Sections <ref> and <ref>.  Finally, we deduce Theorem <ref> in the case u=0 in
Section <ref>.  In Section <ref>, we extend Theorem <ref> and consequently
Theorem <ref> to arbitrary u ∈ (-1, 1) by exploiting a monotonicity
property of random Young tableaux.



Remark.     We note that <cit.> have results
that overlap some of ours.  Our proof of the local limit is
probabilistic, and is based on the Edelman–Greene bijection, the hook
formula and an associated growth process, and a monotonicity property
for random 
Young tableaux.  Gorin and Rahman take a very different approach,
using a contour integral formula for Gelfand–Tsetlin patterns discovered by 
<cit.>.  This allows them to get determinantal
formulas for the limiting process.  While for many models exact formulas
are the only known approach to limit theorems, we show that for random
Young tableaux the local limit and its properties can also be
established from first principles.






§ THE HOOK FORMULA, THE EDELMAN–GREENE BIJECTION AND TABLEAU PROCESSES


In this section, we introduce some preliminary information regarding
Young tableaux and the Edelman–Greene bijection. We then use the hook formula to prove some basic domination lemmas about pairs of growing tableau processes.


  
The hook formula.

Let d(λ) be the number of reverse standard Young tableaux of shape
λ. <cit.> proved
a remarkable formula for d(λ).  To state it, we first need
some definitions.  Let A() ⊂× be the Young diagram of
shape λ. For a square z = (i,j) ∈ A(), define the hook
of z by

    H_z = {(i,j') ∈ A : j' ≥ j}∪{(i',j) ∈ A: i'
      ≥ i}.

Define the hook length of z by h_z = |H_z|.  We also define
the reverse hook for z by

    R_z = {w∈ A{z} : z ∈ H_w}.

The reverse hook will be of use later when manipulating the hook formula. We note here for future use hook lengths and reverse hook lengths in . For a point z = (x, y) in a diagram T(c, n), we have that h_z = 2y - 1, and that |R_z| = n - 1 - y.


  With the above notations, we have
  
    d(λ) = |λ|!/∏_z ∈ A(λ) h_z.






  
The Edelman–Greene bijection.

For the staircase Young diagram of order n, the hook formula gives

    d(λ_n) = n2!/1^n 3^n-1 5^n-2 (2n -3)^1.

As noted, this is also the formula for the number of  sorting networks
of order n given in <cit.>.  We now describe the
bijection between these two sets given by <cit.>.

We recount here a version of the Edelman–Greene bijection for rotated
(defined on subsets of ) reverse standard Young tableaux.  More
precisely, the map as we describe it gives a bijection between Young
tableaux on the diagram T(c,n) and sorting networks of size n with
particles located at positions {c-(n-1), c-(n-1)+2, …, c+(n-1)}.
Note that here particles are located at positions in 2, and not in  as in the statement of Theorem <ref>.
This is done to optimize the description of the bijection.  To
accommodate this, for odd k we use π_k to denote the swap of the particles at positions
k-1 and k+1.
what is a sorting network on an interval? I've removed  this language.

Given a reverse standard Young tableau G: T(c,n) →{1,…,N}, we
generate a sorting network π_k_1π_k_2, π_k_N and a sequence of Young
tableaux (G_t)_t≤ N, starting with G_0=G.  Recall that by
convention G(z)=∞ for z∉ T(c,n).  We repeat the following for
t∈{1,…,N}, computing k_t and G_t from
G_t-1.  (See <ref> for an example.)







  

  Step 1: Find the point z_*∈ such that the value of
  G_t-1(z_*) is minimal.  Clearly z_*= (k,1) for some odd k.  Set k_t = k.


  Step 2: Recursively compute the “sliding path” z_1,z_2,… as
  follows. Set z_1=z_*.  If z_i = (x,i), then
  z_i+1∈ (x± 1, i+1) is chosen to be the point with a smaller value of
  G_t-1.  If both are infinite then the choice is immaterial.


  Step 3: Perform sliding to update G: If z is in the sliding
  path, so that z=z_i for some i then let
  G_t(z) = G_t-1(z_i+1).  Otherwise, let G_t(z) = G_t-1(z).




  
    < g r a p h i c s >

  The first three iterations in the Edelman–Greene bijection.
    Squares not shown have G_t(z)=∞.  In each iteration, (the start of) the sliding path is in bold.
  



  
    < g r a p h i c s >

  The Edelman–Greene bijection applied to a tableau of order
    n=4.  The particles are labelled A–D to distinguish them from the
    entries in the tableau.  The sorting network corresponds to the
    wiring diagram shown in <ref>.
  


The output of the Edelman–Greene bijection is the swap sequence (k_i)
of length N=n2, taking odd values
k_i ∈ [c-(n-2),c+(n-2)].  Edelman and Greene proved that applying
the given sequence of swaps will reverse the elements of the interval
[c-(n-1),c+(n-1)] ⊂ 2, and moreover, that any sorting network
on this interval results from a unique reverse standard Young tableau on
T(c,n).












 §.§ Uniform Young tableaux




The Edelman–Greene bijection allows us to sample a uniformly random
sorting network of size n given a uniformly random reverse standard Young tableau of
shape T(c,n).  We say a set A⊂ is downward closed if whenever z ∈ A and
w≤ z, then w∈ A.  In the language of Young diagrams,
such an A is a special case of a skew Young diagram.  Given a reverse
standard Young tableau G on T(c,n), let A_i = {z : G(z) ≤ i}.
Monotonicity of G implies that A_i is downward closed.  Moreover
|A_i| = i for each i∈{0,…,N}, and we have
A_i ⊂ A_i+1.  Thus a Young tableau on T(c,n) can be viewed
as a maximal sequence of downward closed subsets
A_0 = ∅⊂ A_1 ⊂ A_2 ⊂…⊂ A_N =
T(c,n).  The complementary sets B_i=T(c, n) ∖ A_i are rotated Young
diagrams, and G|_B_i is a reverse standard Young tableau on that
diagram (with entries shifted by i).
 
If B is a Young diagram, and G is a reverse standard Young tableau
on B, then G(z)=1 for some square z∈ B, and this square must
have hook H_z = {z}.  We call such squares corners of B.
The restriction of G to B∖{z} is a reverse standard Young
tableau with all values increased by 1.  This observation allows us to
use the hook formula to find the probability that in a uniformly random
reverse standard Young tableau of shape λ, the square containing
1 is a given corner z. We call this the hook probability, denoted
(B,z).  A simple calculation shows that

    (B,z) = d(B∖{z})/d(B)
      = 1/|B|∏_y ∈ R_z(h_y/h_y - 1).


This gives a simple procedure for sampling a uniformly random reverse
standard Young tableau on any diagram B: Pick a random corner z_1 of
B with probability mass function (B,z) and set G(z_1)=1.
Recursively pick a corner z_2 of B∖{z}
and set G(z_2) = 2, and repeat until all elements of B have been chosen.  In terms of the corresponding growing
sequence of sub-diagrams, this takes the following form: Set
A_0 = ∅.  Having chosen {A_0,…,A_i-1}, pick a corner
z_i of B∖ A_i-1 with probability mass function
(B∖ A_i-1, z_i), and let G(z_i)=i and
A_i = A_i-1∪{z_i}.  We will primarily be interested in this
process when B is a staircase diagram T(c,n).


  While the hook probabilities have an explicit formula, which we use
  directly, one can sample a corner of a diagram with this distribution
  very efficiently using the hook walk, a process described in
  <cit.>.  We omit the mechanism of the walk since we do
  not need it, but remark that it can be used to provide alternate
  proofs of some of the stochastic domination lemmas that follow.





 §.§ Continuous time growth


A significant simplification of our analysis is achieved by Poissonizing
time.  Instead of generating a sequence of growing diagrams A_i, we
shall define a continuous time process with the same jump distribution
but moving at the times of a Poisson process.

The staircase tableau process (or simply tableau process) is a
Markov process X(t) = X(c,n,r)(t).  Its law is determined by
parameters c,n and r, and it is related to the uniform reverse
standard Young tableau of T(c,n).  The state space of this process
comprises all downward closed subsets A ⊂ T(c,n).  The initial
state is X(0) = ∅.  If A and A∪{z} are two states,
then the rate of jump from A to A∪{z} is 

    v_X(z, A) = r ·(T(c, n) ∖ A, z).

When the process X is clear from context we omit the subscript on the rate v. No other jumps are possible.  



Note that the parameter r simply
multiplies all jump rates, so that the process X(n,c,r)(t) has the
same law as X(n,c,1)(rt).  Running these processes at different rates
will be useful, hence the inclusion of r in the notations.  The state
T(c,n) is absorbing. The total rate of jumps from any other state is
r, so the first n  2 jump times of the process coincide with points in a rate-r Poisson process.

Given the process X, let the inclusion time of a square z be defined by

    F(z) = inf{t : z ∈ X(t)}.

These determine the process X, since we have X(t) = {z : F(z) ≤
t}.  Note that F is naturally defined on all
of , with F(z)=∞ for z∉ T_c,n, so that F ∈
[0,∞]^. We refer to F as the inclusion function for X.
The first convergence theorem we prove can now be stated.

 
   
  Let X_n = X_n(c_n,n,n) be a sequence of tableau processes with
  c_n=o(n), and let F_n be the corresponding sequence of inclusion
  functions.  Then F_n  F for some random
  F:→_+.  Moreover, the limit F is translation invariant, in
  the sense that F  F  τ, where τ (x,y) = (x+2, y).


We will use the notation τ throughout the paper to signify horizontal translation on .

Fix the following: done


By the law of large numbers for the Poisson process, the limit of the inclusion functions F_n for the processes X_n is the same as the limit of a uniformly random reverse standard Young tableau on T(c_n, n) with entries scaled by 1/n. Thus Theorem <ref> immediately implies the convergence and translation invariance in Theorem <ref> in the case u = 0. We will similarly prove Theorem <ref> for u ≠ 0 in Section <ref> by again Poissonizing time, noting that this does not change the limit.



Note also that T(c, n) is only defined when c and n have opposite parity, so when taking tableau limits for constant c, we may need to change the value of c by 1, depending on whether n is odd or even. In all of our proofs, shifting the position that the tableaux are centered at by 1 does not affect any of the arguments, as all of the domination lemmas we use are unaffected by distance changes of size o(n). Therefore from now on, we will ignore issues of the parity of c and n.




 §.§ Stochastic domination


A central tool in our proof of existence of certain limits is stochastic
domination of growth processes.  Subsets of  are naturally ordered
by inclusion.  For coupled tableau processes X and X', we say that X is
dominated by X' up to time T if for all t≤ T
we have X(t) ⊂ X'(t).  In terms of the inclusion functions, this
can be stated equivalently as F ≥ F' ∧ T in the pointwise order on inclusion functions (note the order
reversal: a smaller process X corresponds to larger inclusion times
F.)  In light of Strassen's theorem (see <cit.>), we have that X
is stochastically dominated by X' if there is a coupling of the two so
that domination holds, and write X  X' up to time T.










The next lemma gives a sufficient condition for stochastic domination of
one tableau process by another, in terms of their rates.


  
  Let X_1 and X_2 be two tableau processes on the diagrams T(c_1, n_1) and T(c_2, n_2) respectively. Let  be some
  subset of the state space of X, and let the stopping time T be the
  first time t that X_1(t) ∉.  Suppose that for any
  A_1 ∈, any state A_2 with A_1 ⊂ A_2, and for any lattice
  point z we have
  
    v_X_1(z, A_1) ≤ v_X_2(z, A_2),

  provided both are non-zero.  Then X_1  X_2 up to time T.







  Suppose first that  is the entire state space of X_1. The proof when  is not the whole state space goes through in the same way. 
  
  We define a Markov process Y whose state space is all pairs
  (A_1, A_2) with A_1 ⊂ A_2 such that Y
  has marginals X_1 and X_2.  We define the transitions rates of Y
  out of a state (A_1, A_2) as follows.  Let C_1 be the set of all
  corners of T(c_1, n_1)∖ A_1, C_2 be the set of all corners
  of T(c_2, n_2)∖ A_2, and C_1' be the set of all corners
  belonging to both T(c_1, n_1)∖ A_1 and
  T(c_2, n_2)∖ A_1. 
  
  For z ∈ C_1', Y transitions to state
  (A_1 ∪{z}, A_2 ∪{z}) with rate v_X_1(z, A_1). Y
  also transitions to state (A_1, A_2 ∪{z}) with rate
  v_X_2(z, A_2) - v_X_1(z, A_1). For z ∈ C_2  C_1', Y
  transitions to state (A_1 , A_2 ∪{z}) with rate
  v_X_2(z, A_1).  For z ∈ C_1  C_1', Y transitions to
  state (A_1 ∪{z}, A_2) with rate v_X_1(z, A_1).

  It is easy to check that Y has the correct marginals and provides a
  coupling of X_1 and X_2 with X_1 ≤ X_2.


We can further simplify which rates we need to compare to prove stochastic domination with the following observation.



Suppose X(t) = X(c, n, r)(t) is a tableau process, and  A_1 ⊂ A_2. Then v(z, A_1) ≤ v(z, A_2) for any point z ∉ A_2.



The only interesting case here is when z is a corner for both T(c, n) ∖ A_1 and T(c, n) ∖ A_2. Then by Equation (<ref>) and the hook probability formula,


    v(z, A_i)= r/T(c, n) ∖ A_i∏_y ∈ R^i_z(1 + 1/h^i_y -1).


Here R^i_z refers to the reverse hook for z in the diagram T(c, n) ∖ A_i, and h^i_y refers to the cardinality of the hook for y in the same diagram. We have that R^1_z = R^2_z, and each of these are simply the reverse hook for z in T(c, n). Also, h^2_y ≤ h^1_y for all y since T(c, n) ∖ A_2  T(c, n) ∖ A_1, and T(c, n) ∖ A_2≤T(c, n) ∖ A_1. Putting this together, we get that v(z, A_1) ≤ v(z, A_2), as desired.




To prove the more general stochastic domination result, we need the following lemma to help bound hook probabilities.



Let a, b be either two integers greater than 1 or two half-integers greater than 1, and define

    y= ∏_i=a^b (1 + 1/2i -1) = ∏_i=a^b 2i/2i -1,

where the product runs over integers between a and b if both are integers, and over half-integers between a and b if both are half-integers.
Then

    √(2b-1/2a-1) < y < √(2b/2a-2).






We have x < y < z where

    x=∏_i=a^b 2i+1/2i ,      z =∏_i=a^b
    2i-1/2i-2.

Then xy and yz are telescoping products given by

    xy=2b -1/2a-1,      yz=2b/2a-2

so we get √(xy)< y <√(yz).


Now we can prove the following more general lemma about stochastic domination.


Let T(c_1,n_1)  T(c_2, n_2), and consider two tableau
processes

    X_1 = X_1(c_1, n_1, n_1),     and     X_2 =
      X_2(c_2, n_2, θ n_2).

Fix ∈ (0,1), and let T be the stopping time when
⌊n_12⌋ lattice points have been added to
X_1.  Let the difference between the horizontal centers of the two
tableau processes be d= |c_1 -c_2|. Then X_1  X_2 up to time T,
provided that


    θ > (n_2 -1)n_1/(n_1 - 1)(n_2 - 2)((1- )√(1- (n_1 + d/n_2-2)^2))^-1.




We may assume that c_1 = d and c_2 = 0. By Lemmas <ref> and <ref> it suffices to show that for any state A with A≤⌊n_1  2⌋, and any corner z of both T(d, n_1) ∖ A and T(0, n_2) ∖ A we have  

    v_X_1(z, A) ≤ v_X_2(z, A).

Let R_z^1 be the reverse hook of z in T(d, n_1), and let h_y^1 be the hook length of y in T(d, n_1)∖ A, and similarly define R_z^2 and h_y^2 for T(0, n_2).
To get a simple expression for v_X_2(z, A)/v_X_1(z, A), observe that if y ∈ R_z^1, then y ∈ R_z^2 and h_y^1 = h^2_y for such y.  Thus


    v_X_2(z, A)/v_X_1(z, A) = θn_2/n_1T(d, n_1) ∖ A/T(0, n_2) ∖ A∏_y ∈ R_z^2 ∖ R_z^1(1 + 1/h_y^2 -1).



We will show that this is always greater than 1. For y = (y_1, y_2) to be in R_z^2 ∖ R_z^1 where z =(z_1, z_2), one of two possibilities must occur. Either

    (y_1, y_2) ∈ E_1    = { (z_1- i , z_2 + i) : z_2 - z_1 + 2i ∈ (n_1 - 1 - d,  n_2 -1]}, 
    
    (y_1, y_2) ∈ E_2    = { (z_1+ i , z_2 + i) : z_1 + z_2 + 2i ∈ (n_1 - 1+ d,  n_2 -1]}.

For (y_1, y_2) = (z_1- i , z_2 + i) ∈ E_1 and for y =(z_1+ i , z_2 + i)∈ E_2, the hook for y is of length 1 + (y_2 -z_2) + (y_2 - 1) = 2i + z_2. Thus using Lemma <ref>, we find that


    ∏_y ∈ R_z^2 ∖ R_z^1(1 + 1/h_y^2 -1)    = 
    ∏_i = [n_1 - 1 - d - z_2 + z_1]/2 + 1^[n_2 -1 - z_2 + z_1]/2   (1 + 1/2i + z_2 - 1)∏_i = [n_1 - 1 + d - z_2 - z_1]/2 + 1^[n_2 - 1 - z_2 - z_1)]/2(1 + 1/2i + z_2 - 1) 
        >  √((n_2 -2)^2 - z_1^2/n_1^2 - (z_1 - d)^2).

Thus for the quantity (<ref>) to be greater than 1, we need


    θ≥n_1/n_2T(0, n_2) ∖ A/T(d, n_1) ∖ A√(n_1^2 - (z_1 - d)^2/(n_2 -2)^2 - z_1^2),

for all values of z_1 and A with A≤⌊n_1  2⌋. We then have the following chain of inequalities for the right hand side of (<ref>), which show that the inequality (<ref>) holds for the values of θ specified in the Lemma.


    n_1/n_2T(0, n_2) ∖ A/T(d, n_1) ∖ A√(n_1^2 - (z_1 - d)^2/(n_2 -2)^2 - z_1^2)   < n_1/n_2n_2  2/(1-)n_1  2n_1/n_2 -2(1 - (z_1/n_2-2)^2)^-1/2
       ≤(n_2 -1)n_1/(n_1 - 1)(n_2 -2)((1- )√(1- (n_1 + d/n_2-2)^2))^-1




We will use this lemma when n_1 is much smaller than n_2, the value  small, and the distance d grows linearly with n_2. In this case we have the following asymptotic version of the stochastic domination.



Let X(un + a_n, n, n/√(1 - u^2))(t) be a sequence of tableau processes for n ∈, where u ∈ (-1, 1) and a_n=o(n) is a sequence of integers. Then for any _1 > 2_2 ∈ (0,1), for all sufficiently large m there exists some N(m) such that

    X(un + a_n, n, (1+ _1)n/√(1 - u^2))  X(0, m, m)

up to time T, for all values of n ≥ N(m).
Here T is the stopping time when _2 m  2 lattice points have been added to the process X(0, m, m).


Finally, we will also state Lemma <ref> for domination of a tableau process over two independently coupled tableau processes, as this will be necessary for the proof that the tableau limit is mixing. The proof goes through analogously.



Let T(b_1, n_1) and T(c_1, n_1) be disjoint sets with T(b_1, n_1) ∪ T(c_1, n_1)  T(c_2, n_2), and consider three tableau processes 

    X_1(t) = X_1(c_1, n_1, n_1),     X'_1(t) = X_1(b_1, n_1, n_1)    and     X_2(t) =
      X_2(c_2, n_2, θ n_2).


Let Y be the process given by the union of independent copies of X_1 and X_1'. Let d = max (|c_2 - c_1|, |c_2 -b_1|). Then if  and θ are as in the statement of Lemma <ref> (with the new definition for d), we have that Y  X_2 up to a stopping time T. In this case T is the stopping when either ⌊n_1  2⌋ lattice points have been added to X_1 or X_1'.
  







Inclusion Functions and Convergence

















We want to show that for a sequence of tableau processes X_n (t) = X_n (0, n, n)(t), that the corresponding inclusion functions converge in the weak topology on the space of probability measures on [0, ∞] ^. To do this, we use the monotonicity established by Corollary <ref>, which will be exploited using the following lemmas.











Let G_n be a tight sequence of random variables taking values in [0, ∞)^m. Suppose that for every > 0, there exists a sequence of random variables G^_n such that (G^_n ≠ G_n) → 0 as n →∞ and such that the following holds. For all sufficiently large M there is some N ∈ such that

    G_n  (1+ )G^_M     for all  n ≥ N.

Then the sequence G_n has a distributional limit G.


We leave the proof of this lemma for the appendix (Section <ref>), as it is fairly standard but somewhat lengthy.



Let X_n = X_n(a_n, n, n) be a sequence of tableau processes  with a_n =o(n) and let F_n be the corresponding sequence of inclusion functions. Then for any z ∈,

    {F_n(z) : n   large enough so that  z ∈ T(0, n)}
 is a tight as a sequence taking values in [0, ∞).


 
    
    < g r a p h i c s >
 
    The set A_n in the proof of Lemma <ref>. As the size of the Young diagram goes to infinity, the proportion of T(0, n) taken up by A_n increases to 1/2, as the point z does not grow with n.
    
 


Let z = (x, y) and  consider the set A_n = {z' ∈ T(a_n, n) : z' ≥ z}. Then A_n is a rectangle and as n→∞ the relative size |A_n|/|T(a_n,n)|→ 1/2. Moreover, no square in A_n is added before z.



Now let n be large enough so that A_n > n^2/8, and let m, θ be such that

    θ > n (m-1)/(n - 1)(m-2)(1/4√(1- (n + |a_n - a_m|/m - 2)^2))^-1.

By Lemma <ref>, θ X_m dominates X_n until the time when 3/4n  2 squares have been added to X_n. By this time at least one square from A_n must have been added to X_n, so z must have been added to X_n. Therefore  θ F_n (z)  F_m(z).



As the right hand side of (<ref>) is bounded uniformly for large m for a fixed value of n, there is some K > 0 such that  K F_n(z)  F_m for all large m, so {F_n(z)} is tight.
 

 Now we can prove Theorem <ref>, which as mentioned previously corresponds precisely with Theorem <ref> in the case u = 0, and proves all parts of the Theorem in that case except for the mixing property with respect to spatial shift.






First assume that a_n=0 for all n.
Since the product topology on [0, ∞]^ is compact, F_n has subsequential limits. Suppose that there are two subsequential limits F^a ≠ F^b. Then for some finite set K, the restrictions F^a|_K and F^b|_K are not equal. Define T_n^ to be the stopping time when n  2 lattice points have been added to X_n. T_n^∞ as n →∞, so for any z,  (F_n(z) ≤ T_n^) → 1 as n →∞ since

    {F_n(z) : n   large enough so that  z ∈ T(0, n)}

is tight by Lemma <ref>. Defining F^_n by  to be F^_n(z) = F(z) for F(z) ≤ T_n^ and F^_n(z) = ∞ otherwise, 
(F^_n|_K ≠ F_n|_K) → 0 as n →∞.




Now by Corollary <ref>, for large enough m there exists N(m) such that X(0, n, (1 + 3)n)  X(0, m, m) up to time T_m^, for all n ≥ N. This implies that (1 + 3 ) F^_m(z)  F_n(z). Under these conditions we can appeal to Lemma <ref>, which gives that F_n|_K does indeed have a distributional limit, contradicting that F_1|_K ≠ F_2|_K . Thus F_n itself has some distributional limit F. Note that F ∈ [0, ∞)^ almost surely since each {F_n(z)} is a tight sequence on [0, ∞).



The same proof works in the case when X_n is centred at a_n for a sequence a_n = o(n), since all the domination lemmas can be used in exactly the same way. Moreover, translation invariance follows by comparing the sequences X_n (a_n, n, n) and X_n (a_n + 2, n, n) since the difference between the center points, d_n = 2 = o(n).




Bounding Rates of Adding Lattice Points

The goal of this section and the next one is to establish regularity properties of the limit F of random Young tableaux in order to apply the Edelman-Greene bijection. In order to do this we will show that at every time t, the points in the limit tableau that are added before time t form a set of disjoint downward closed subsets of , and that the limit F is still an order-preserving injection. The key to both of these proofs is the following proposition about bounding the rates of adding points in the finite tableau processes.

Throughout this section we let X_n be the tableau process X_n(0, n, n).



 There exist constants K_1 and K_2 such that for any z ∈  and for any t,

    [ sup_s ≤ t  v(z, X_n(s)) ] ≤ K_1t+ K_2,

for all large enough n (how large we need to take n depends on the square z).




The cylindrical tableau process.     To prove this proposition we introduce cylindrical Young diagrams and the cylindrical tableau process. Define (n), the discrete cylinder of size n, to be the set of equivalence classes of points (x, y) in { (x, y) ∈ :  1 ≤ y ≤ n - 1} where (x, y) ∼ (x', y') if y = y' and x ≡ x' 2(n-1). This cylinder has the following partial order inherited from the partial order on . For (x, y), (x', y') ∈(n), (x, y) ≤ (x', y') if (x', y') ∼ (x”, y”) for some (x”, y”) ∈ with (x', y) ≤ (x”, y”). 

Thus we have a notion of downward closed sets in (n), and notions of corners, hooks, and reverse hooks in (n) ∖ A for any downward closed set A (n) by thinking of (n) as a cylindrical Young diagram. As in a usual Young diagram, for any corner z ∈(n) ∖ A we can define the “hook probability" for z by


    ((n)∖ A, z) = 1/(n) ∖ A∏_y ∈ R_z(1 + 1/h_y -1).


 Now we define the cylindrical tableau process C(t) = C(n, r)(t) on (n) with rate r as the continuous time Markov process C(t) where a square z is added to configuration A at rate

    v_C(z,A)=r  ((n)∖ A,z).
 Note that the hook probabilities in  cylindrical tableaux do not sum to 1 as they do with staircase tableaux. This is not an issue as we are only using the hook probabilities to define rates, not as actual probabilities.



The symmetry in the cylindrical process makes it easier to bound the expectation of the rate v_C(z, C(t)). We can then use that the staircase tableau process can be coupled with an appropriately sped up cylindrical process in a way that allows rates in the staircase process to be controlled by the rates in the cylindrical process. This will prove Proposition <ref>.




The modified rate.     Instead of working with v(z, A), we will replace it with a monotone increasing function w(z,A) called the modified rate.  The modified rate w_C(z, A) is the rate of adding z to the configuration A with the cone
S_z={z' : z' ≥ z}
above z removed. More precisely

    w_C(z,A)=v_C(z,A∖ S_z).





By the definition of v, the modified rate satisfies

    w_C(z, A) = r/(n) ∖ A∪ S_z ∏_y ∈ R_z(1 + 1/f^z_y -1).

Here f_y^z is the hook length of y in the residual tableau corresponding to the state A∖ S_z.








We also define w_X(z, A) for a staircase tableau process X in the analogous way. 



Since v_C is monotone in A as long as z_C has not been added, we get that w_C is monotone in A (even if z has been added). Therefore to prove Proposition  <ref> it suffices to prove the following.

 

For all large enough n, we have

    [ sup_s ≤ t  w_X(z, X_n(s)) ] =  w_X(z, X_n(t)) ≤ K_1t+ K_2




We first need a lemma bounding the products in the hook probability formula.



Let A be a downward closed subset of 𝒞(n), and let β be the maximal second coordinate of squares in A. Then we have

    ∏_y ∈ R_z(1 + 1/f^z_y(A) -1)
    < 2 n (β + 1).



If we order squares in the reverse hook of z by their second coordinate (s+1 below), we get upper bounds on the individual factors. This gives an overall upper bound

    ∏_s = 1^n-1(1 + 1/s + (s - β)^+)^2
    = (β + 1)^2 ∏_s = (β + 3)/2^n - 1 - β(2s/2s -1)^2< 2 n (β + 1).

The last inequality is from Lemma <ref>.


 The same bound holds in the staircase tableau case.


Next, we bound w(z, A) for z at the bottom of the cylinder.



Let ℬ denote the bottom row of 𝒞(n). Then we have that 

    ∑_z∈ℬ w(z, A) ≤ 48(|A| + n),

in the rate n cylindrical tableau process.


We have only included the explicit constant 48 in the above proposition to streamline the proof. It is far from optimal for large n.

For z∈ℬ, define

    D^z=∏_y ∈ R_z(1 + 1/f^z_y(A) -1).

It suffices to show that

    ∑_z∈ℬ D^z ≤ 12 (n |A|+ n^2),

since (n) ∖ A∪ S_z≥S_z≥n  2. To establish this bound, we will build the set A in |A| steps by starting with A_0=∅ and repeatedly adding a single square (α_i,β_i) to A_i-1 to get A_i. We do this in a way so that A_i stays downward closed and β_i are non-decreasing.

Define the quantities D^z_i for A_i analogously to D^z.
By simple algebra,

    ∑_z∈ℬ D^z ≤ nmax_z∈ℬD_0^z+∑_i=1^|A|[max_z∈ℬD^z_i-1]∑_z∈ℬ|D^z_i/D^z_i-1 - 1|.

By defining β_0=0, we have that β_i is the maximal y-coordinate of a square in A_i.
The first term on the right is bounded above by 2n^2 by Lemma <ref>. By the same lemma, 

    max_z∈ℬD^z_i-1≤ 2n(β_i-1+1)≤ 2n(β_i+1) ≤ 4n β_i,

since β_i ≥ 1 for i ≥ 1. So it suffices to show that for any i ≥ 1, we have

    ∑_z∈ℬ|D_i^z/D_i-1^z-1 |≤3/β_i.

To do this, recall that A_i=A_i-1∪{(α_i,β_i)}. Note that if for z∈ℬ we have z≤ (α_i,β_i) then D_i^z/D_i-1^z=1. Let ℬ'=ℬ∖{z:z ≤ (α_i,β_i)}. Then |ℬ'|=n-1-β_i.

For any z∈ℬ' the reverse hooks R_z and R_(α_i,β_i) intersect at exactly two points, one on the right leg of R_z and one on the left. Call the y-coordinates of these points s_z and s'_z, respectively. As we move z, these intersection points exhaust the set R_(α_i,β_i). More precisely, s and s' are both bijections from ℬ' to  {β_i+1,…, n-1}. For z∈ℬ' we have

    D_i^z/D_i-1^z=Q(s_z)Q(s'_z),

where

    Q(s)=
    1 + 1/2s - β_i  - 2/1 + 1/2s - β_i - 1 =  (2s - β_i -1)^2/(2s - β_i- 2)(2s - β_i).

Since s and s' are bijections, Cauchy-Schwarz gives

    ∑_z∈ℬ' Q(s_z)Q(s'_z) ≤∑_s=β_i+1^n-1 Q(s)^2.

By simple algebra Q(s)≥ 1 and

    Q(s)^2-1≤3/(2s-β_i - 1)^2.

So the left hand side of (<ref>) is bounded above by

    ∑_s=β_i+1^n-13/(2s-β_i - 1)^2< 3/β_i.
































Now we can embed the staircase tableau of size n into the cylinder (n) by identifying the subset T(0, n) with its equivalence class in (n). Thus we can talk about stochastic domination of a cylindrical tableau process over a staircase tableau process, and we can talk about domination of modified rates.



Let T be the time at which n^2/4 particles have been added to the tableau process X_n(t). Let C_n(t) be a cylinder process on (n) with rate 8n. Then there exists a coupling so that for n ≥ 3,

    X_n(t) ≤ C_n(t)      for all t≤ T.

Moreover, for any z in the bottom row of T(0, n), w_C(z, C_n(t)) ≥ w_X(z, X_n(t)) for all t ≤ T in this coupling.



To prove the existence of a coupling, it suffices to show that for any A, and any lattice point z that is both a corner of (n)∖ A and T(0, n) ∖ A, that
v_X_n(z, A) ≤ v_C_n(z, A).
From here we can appeal to Lemmas <ref> and <ref>, which can be proven in the exact same way if one of the processes is a cylinder process.



Reverse hooks in (n) are larger than reverse hooks in T(0, n), and for y ∈(n)∩ T(0, n), we have h_y^X = h_y^C, so

    ∏_y ∈ R^z_X(1 + h^X_y/h^X_y -1) ≤∏_y ∈ R^z_C(1 + h^C_y/h^C_y -1).

 Also,


    (n)∖ A/T(0, n) ∖ A≤ 8

for all n ≥ 3. Combining the inequalities (<ref>) and (<ref>) proves the lemma. The relation among modified rates follows in the same way.




Now we can prove Proposition <ref> for z in the bottom row of T(0, n).


Let T be the stopping time when (2t+1) n squares have been added to the tableau process X_n. Since the times of adding squares are the points of a rate n Poisson process, it is easy to check that

    (T<t) ≤ e^-L n
 for some universal constant L.

Observe the naive bound that w_X(z, X_n(t)) ≤ n for all n. We can now use Lemma <ref> together with the monotonicity of modified rates to get:

    [ sup_s ≤ t  v_X(z, X(s)) ]    ≤ w_X(z, X_n(t)) 
       ≤[ w_C(z, C_n(t))  1_t < T] + ne^-L n
       ≤ w_C(z, C_n(T))  + ne^-L n.

Finally, using Proposition <ref> and the rotational symmetry of the cylinder process, we get that

    w_C(z, C_n(T))  + ne^-L n≤ 48((2t+1) + 1) + ne^-L n≤ K_1t + K_2,

completing the proof.



Finally, we show that for any fixed z' ≥ z ∈, that for large enough n, the modified rate for adding z' to X_n is always bounded by twice the modified rate for adding z. 
This extends Proposition <ref> to encompass all z ∈, and therefore completes the proof of Proposition <ref>.

 Let z' ≥ z = (z_1, z_2) and for a downward closed subset A  T(0, n) let w(z, A) and w(z', A)  be the modified rates in X_n. Then

    lim_n →∞(sup_A  T(0, n)w(z', A)/w(z, A)) = 1.

Specifically, for all large enough n, we have that w(z', X(t)) ≤ 2w(z, X(t)) for all t.


  We only prove this in the case z' = (z_1 + 1, z_2 +1), as the general case follows by symmetry and induction. Observe first that the supremum on the right hand side of (<ref>) is at least 1 for every n, since w(z', T(0, n)) = w(z, T(0, n)) for all n. Also, it is easy to see that

    T(0, n) ∖ A ∪ S_z/ T(0, n) ∖ A ∪ S_z'→ 1

as n →∞, since S_z/n^2 → 1/4 as n →∞, but S_z  S_z'/n → 1/2. Therefore to complete the proof it suffices to show that for any configuration A  T(0, n), that


    ∏_y ∈ R_z'(1 + 1/f^z'_y -1) ≤∏_y ∈ R_z(1 + 1/f^z_y -1).



To prove this, let y' = (y_1 + 1, y_2 + 1) ∈ R_z'. It is clear that y = (y_1, y_2) must be in R_z. Moreover, if (x_1, x_2) ∈ H_y in the configuration T(0, n) ∖ A ∪ S_z, then (x_1 + 1, x_2 + 1) ∈ H_y' in the configuration T(0, n) ∖ A ∪ S_z'. This gives an injective mapping of R_z' into R_z that does not decrease hook length, proving (<ref>).





Regularity and Mixing of the Limit F

In Theorem <ref> we showed that the inclusion functions of random staircase Young tableaux have a limit F. In this section we establish regularity properties and mixing of F using the results of Section <ref>. 



F is almost surely injective.



Suppose not. Since there are only countably many pairs of points in , then there exists a pair (z_1, z_2) ∈^2 with (F(z_1) = F(z_2)) = δ > 0. Then for any > 0, there is some N such that (|F_n(z_2) - F_n(z_1)| < ) ≥δ/2 for all n ≥ N. Without loss of generality, we can remove the absolute values at the expense of a factor of 1/2 to get

    (0≤ F_n(z_2) - F_n(z_1) < ) ≥δ/4.


Let T be the stopping time when z_1 is added to the process X_n. The probability of adding z_2 in the interval [T, T + ] is bounded by the integral of the rate in that interval. This gives that

    (0 ≤ F_n(z_2) - F_n(z_1) < )    ≤sup_s ∈ [T, T + ] v(z_2, X_n(t)) 
       ≤ Kt  + (sup_s ≤ t v(z_2,  X_n(s)) ≥ Kt) + (T > t - ).

By Proposition <ref> we can choose K and t large enough and independently of  to make the last two terms on the right hand side arbitrarily small for all large enough n. Taking  close to 0 then contradicts (<ref>).


 

For each z, the distribution of F(z) has no atoms. 




The proof that F has no atoms is the same as the proof that F is almost surely injective, except instead of conducting the analysis at a stopping time T when the square z_1 is added, we conduct it at a (deterministic) time t. 



The limit F is mixing
Recall that a measure μ is k-mixing with respect to a measure-preserving transformation τ if for any measurable sets A_1, , A_k,

    lim_m_1, …, m_k →∞μ(A_1 ∩τ^-m_1A_2 ∩…∩τ^-m_1 - m_2 -  - m_k A_k) = ∏_i=1^k μ(A_i).

 Note that this proposition completes the proof of Theorem <ref> in the case u =0.



The limit F is mixing of all orders with respect to the spatial shift τ.


We first present an outline of the proof that F is 2-mixing. Fix m, and consider two sets A^r and B^r of the form

    A^r =  ∏_i ∈ T(0, m) [0, a_i]      B^r = ∏_i ∈ T(0, m) [0, b_i],

and let 

    A = A^r ×∏_i ∉ T(0, m) [0, ∞)      B = B^r ×∏_i ∉ T(0, m) [0, ∞).

By Dynkin's  π- Theorem, it suffices to show that

    (F  ∈ A ∩τ^-K B) →(F ∈ A)(F ∈ B)  K →∞,

for any such A and B. To show this, we will approximate the value of F on A ∩τ^-K B in two different ways. Figure <ref> illustrates the two approximations used. For the first approximation,  take two disjoint tableaux T(0, ⌊ K/2 ⌋) and T(-K, ⌊ K/2 ⌋) and run independent, rate-⌊ K/2 ⌋ tableau processes Y_1 and Y_2 on each of these tableaux. Let G_K, 1 and G_K, 2 be the inclusion functions for Y_1 and Y_2. For K ≫ m, convergence of G_K, 1 and G_K, 2 to F implies that (G_K, 1∈ A) is very close to (F ∈ A), and similarly for G_K, 2 and τ^-KB.



For the second approximation, take n ≫ K, and let X_n be the rate-n tableau process on T(0, n) with inclusion function F_n. Since n ≫ K, the convergence of F_n to F implies that 
(F_n ∈ A ∩τ^-K B) is close to (F ∈ A ∩τ^-K B), and that (F_n ∈ A) and (F_n ∈τ^-K B) are close to (F ∈ A) and (F ∈ B) respectively.



Finally, we can use the domination Lemma <ref> to show that a small speed-up of X_n dominates the union of the independent processes Y_1 and Y_2 up to a large stopping time. This in turn implies that up to a small error, 

    (F_n ∈ A ∩τ^-K B) < (G_K, 1∈β A)(G_K, 2∈βτ^-K B),
 where β is the value of the speed-up. Combining this with our previous relationships between probabilities implies that (G_K, 1∈ A)(G_K, 2∈τ^-K B) must be very close to (F_n ∈ A ∩τ^-K B). Passing to the limit in n and then K then proves that F is 2-mixing, noting that 

    (G_K, 2∈τ^-K B) →(F ∈ B)  n →∞

by spatial stationarity.



The general case can be proven using the same method, with the main difference being that in that case, we approximate the limit F with n disjoint independent tableau processes instead of 2. For simplicity, we only prove 2-mixing below.


   
    < g r a p h i c s >

   The two approximating processes used in the proof of Proposition <ref>. The first approximation pairs two disjoint processes on T(0, ⌊ K/2 ⌋) and T(-K, ⌊ K/2 ⌋) for K ≫ m and the second approximation takes a tableau process on T(0, n) for n ≫ K.
   


 The proof exactly follows the outline of what is stated above, but with precise bookkeeping regarding the error terms.  



















With notation as in the outline, first note that it suffices to show that for large enough n,

    |(F_n ∈ A ∩τ^-K B) - (G_K, 1∈ A)(G_K, 2∈τ^-K B)| < _K

where _K → 0 as K →∞. To see that (<ref>) implies (<ref>), let 

    |(F ∈ A)(F ∈ B) - (G_K, 1∈ A)(G_K, 2∈τ^-KB)| = δ_K.

 Taking n →∞ in (<ref>) and replacing G_K, 1 and G_K, 2 with F, we get that

    | (F ∈ A ∩τ^-K B) - (F ∈ A)(F ∈ B)| ≤_K + δ_K.

We can pass to the limit in F_n since A ∩ B is a set of continuity of H by Corollary <ref>. Moreover, δ_K → 0 as K →∞ since A and B are sets of continuity of F by the same corollary and using the spatial stationarity of F.



Now let γ > 0, define 
    β =  K + 1/(1- γ)(K - 4),
 and let

    α_K,  = max{(F(i) ∈[c, β c ] : c ∈{a_i, b_i})}.

We have chosen β in a way so that if n is large enough, then the tableau process X^β_n on the tableau T(0, n) with speed β n stochastically dominates the independent coupling of the tableau processes Y_1 and Y_2 up to time T_. Here T_ is the time when either ⌊ K/2 ⌋ 2 squares have been added to Y_1 or ⌊ K/2 ⌋ 2 squares have been added to Y_2. This can be seen by comparing with the condition in Lemma <ref>. 



Therefore letting M = max{a_i, b_i}, we have

    (G_K, 1∈ A)(G_K, 2∈τ^-K B) < (F_n/β∈ A ∩τ^-KB) + (T_γ < M).

Moreover, we have that for all large enough n, 

    (F_n/β∈ A ∩τ^-K B )    = (F_n ∈β A ∩τ^-Kβ B )
       < (F_n ∈ A ∩τ^-K B) + 2m(m-1)_K, .

Here β A = {β x : x ∈ A }, and similarly for B. For the above inequality to hold, n just needs to be large enough so that 

    max{(F_n(i) ∈[c, β c ] : c ∈{a_i, b_i})} < 2 _K, .
 
Combining the above two inequalities, we get that 

    (G_K, 1∈ A)(G_K, 2∈τ^-K B) < (F_n ∈ A ∩τ^-K B) + 2m(m-1)_K,  + (T_γ < M).

We can similarly get that

    (G_K, 1∈ A^c)(G_K, 2∈τ^-K B^c) > (F_n ∈ A^c ∩τ^-K B^c) - 2m(m-1)_K,  - (T_γ < M).

Finally, let 

    _K = max{|(G_K, 1∈ A) - (F ∈ A)|,  |(G_K, 2∈τ^-KB) - (F ∈τ^-K B)|}.
 
For large enough n, we have that 

    |(F_n ∈ A) - (G_K, 1∈ A)| < 2_K  |(F_n ∈τ^-KB) - (G_K, 1∈τ^-KB)|

since A and B are sets of continuity of F. This similarly holds for A^c and B^c. Therefore
 
    |((G_K, 1∈ A)(G_K, 2∈τ^-K B)    - (G_K, 1∈ A^c)(G_K, 2∈τ^-K B^c))
    
     -    ((F_n ∈ A ∩τ^-K B) - (F_n ∈ A^c ∩τ^-K B^c)) | < 4 _K.

 Combining this bound with (<ref>) and (<ref>) gives that for all large enough n,
 
    |((G_K, 1∈ A)(G_K, 2∈τ^-K B)    - (F_n ∈ A ∩τ^-K B)|
        < 4m(m-1)_K,  + 2(T_ < M) + 4 _K.

 
Now note that for any fixed value of > 0, as K →∞, we can choose a sequence _K → 0 such that (T__K > M) <. With this sequence of _Ks, _K, _K→ 0 as K →∞. 

Noting also that _K → 0 as K →∞, this shows that the left hand side of (<ref>) tends to 0 as n →∞. 

























Inclusion times for squares in the bottom row



We can also use the rate bound to get a lower bound on the probability that it takes a long time to add any given square in the bottom row. Note that by spatial stationarity of the limit F, it suffices to prove this for the square z_0 = (1, 1). We can then combine this with the mixing property of F to show that at any time infinitely many squares have not been added.



 The idea here is to modify the process X_n to create a new process Y_n. Y_n will be  X_n, but with the hook probabilities modified so that Y_n never adds z_0. We will then show that X_n and Y_n can always be coupled so that at any time t they are equal with positive probability P independent of n.


The construction of Y_n. Y_n is a Markov process with the same state space as the tableau process X_n, namely:

    { A  T(0, n) : A    is downward closed}.

If A = Y_n(t), and  z is corner of T(0, n) ∖ A with z ≠ z_0, then we add the point z to Y_n with rate


    n (T(0, n) ∖ A, z)/1 - (T(0, n) ∖ A, z_0).

In words, the rates in Y_n for squares that can be added are given by the rates in X_n times

    1/1 - (T(0, n) ∖ A, z_0).

Note that this only makes sense as long as there are squares other than z_0 that can be added to Y_n. Once z_0 is the only square left that can be added, we can define Y_n so that nothing happens past that point. We first show that Y_n is dominated by a sped-up version of X_n. Note that the total rate of jumps from any non-terminal state in Y_n is exactly n.

 
Let M < n(n-1)/128, and let T_M be the stopping time when M squares have been added to Y_n. Then letting X^2_n = X(0, n, 2n) be a tableau process on T(0, n) with speed 2n, we have that Y_n  X^2_n up to time T_M.
 

 Suppose that A is some configuration with fewer than n(n-1)/128 points added. The maximum height of A is bounded by n/8 - 1, since any square of height n/8 - 1 lies above a triangle with n(n-1/8)/128 squares. By the remark following Lemma <ref> this implies a  bound on the hook probabilities, namely

    (T(0, n) ∖ A, z_0) ≤1/n  2 - M 2 n n/8 < 1/2

for n ≥ 3. Then by (<ref>) we have domination of the rates of Y_n by those in X^2_n. Lemmas <ref> and <ref> (more precisely, the proofs of those lemmas,) then imply stochastic domination.

Now we couple X_n and Y_n to bound the probability of adding z_0.


There exist constants K and L such that for any t>0



    {F(z_0) > t }≥ e^-Kt -L t^2.




 Couple X_n and Y_n so that they add squares at the same times (we can do this since the total rate of exiting non-absorbing states in X_n and Y_n is n), and add the same squares until the time when X_n adds square 0. Now let M ∈, and for m ∈ let T_m be the stopping time when the mth square is added to X_n. Let  be the set of maximal sequences {A_0 = ∅ A_1  A_M} of downward closed subsets of T(0,n)  such that z_0 ∉ A_M.  Then we have

    (X_n(t) = Y_n(t)) ≥(T_M ≥ t)∑_{A_m}∈(X(T_m) = A_m  m ≤ M)

Using the transition probabilities for Y_n the sum above can be written as

    ∑_{A_m}∈(Y(T_m) = A_m  m ≤ M) ∏_m=1^M (1 - ( T(0, n)  A_m-1, z_0   )).

We may write this as an expectation

    ∏_m=1^M(1 - ( T(0, n)  Y_n(T_m-1) ,z_0   ))≥(1 - ( T(0, n)  Y_n(T_M), z_0   ))^M.

The
 inequality follows since the probabilities are monotone. 
By Jensen's inequality we get the lower bound

    (1 - ( T(0, n)  Y_n(T_M), z_0   ))^M

We use Lemma <ref> to bound the expectation above. Assume 
M ≤n(n-1)/128, then X^2_n(T_M) stochastically dominates Y_n(T_M), that is in some coupling X^2_n(T_M)≥ Y_n(T_M), and since z_0∉ Y_n(T_M), we have X^2_n(T_M) S_z_0≥ Y_n(T_M), where S_z_0 is the set of squares that are greater than z_0 in the partial order. By monotonicity of the rates we have

    ( T(0, n)  Y_n(T_M), z_0   ) ≤( T(0, n)  (X^2_n(T_M)∖ S_z_0), z_0   ).

We can bound the rates in X^2_n  S_z_0 at some fixed time s=2M/n by Proposition <ref> from the previous section. Here note that the rate of adding z_0 to X^2_n  S_z_0 is the modified rate of adding z_0 to X_n.  We get the upper bound

    ( T(0, n)  (X^2_n(s)∖ S_z_0), z_0   ) + (T_M>s) ≤K_1/n+K_2 M/n^2 + e^-K_3n,

where bound on (T_M > s) follows from the tail probabilities of the Poisson distribution. Monotonicity of the rates implies that this is also an upper bound for ( T(0, n)  (X^2_n(T_M)∖ S_z_0), z_0).
Putting everything together and setting M=2tn, we get for large enough n

    (X_n(t) = Y_n(t)) ≥(T_M > t)(1 - K_1+2 K_2 t/n-e^-K_3n) ^2tn.

Letting n→∞ gives that 

    lim_n →∞(X_n(t) = Y_n(t)) ≥ e^-Kt - Lt^2,

for some constants L and K. Using that F(z_0) has a continuous distribution (Corollary <ref>) then finishes the proof.


The mixing of F combined with Lemma <ref> implies that at any time, a bi-infinite sequence of squares has not been added. This is a direct consequence of the fact that mixing implies ergodicity.



For any time t, there are almost surely infinitely many values of x > 0 and infinitely many values of x < 0 such that F(x, 1) > t.





Sorting Networks at the Center

Now we are finally in a position to prove the existence of the local limit of random sorting networks at the center. Let  be the space of swap functions. Define  to be the set of all functions G: → [0, ∞] such that the following two conditions hold. 



i) Let B = {z ∈ : G(z) ≠∞}. Then G|_B is order-preserving and injective.

ii) For any t, we have that  G(x, 1) > t for infinitely many x> 0 and x < 0.



We will define a map EG: → which will generalize the Edelman-Greene bijection. To do this we first define swap functions EG_t(G) for every t > 0. These swap functions will be EG(G) defined up to time t > 0. Consider the set of points 
    A = {z : G(z) ≤ t}.
 Since G(x, 1) > t for infinitely many x> 0 and x < 0 and G is order-preserving on , A breaks down into infinitely many finite downward closed sets A_i such that each A_i lies in some T(ℓ_i, k_i) and the sets T(ℓ_i, k_i) are disjoint. We can then define the swap function on each T(ℓ_i, k_i) individually up to time t using the regular Edelman-Greene bijection on that diagram, since these swap functions don't interact before time t and G|_B is order-preserving and injective.



Now define the process EG(G) by letting 

    EG(G)(x, r) = EG_t(G)(x, r),

where t is any time greater than r. This is well-defined since for r < s < t, EG_t(G)(x, r) = EG_s(G)(x, r).




It is easy to see that EG is continuous on , by checking that EG_t is continuous for all t. This is clear since if G_n → G in , for any subset T(ℓ_i, k_i), eventually G_n will be identically ordered to G on T(ℓ_i, k_i) and so the ordering of the swaps given by the Edelman-Greene bijection will be the same for G_n and G on T(ℓ_i, k_i). Moreover, the times at which these swaps occur converge in the limit. This implies convergence of both the cadlag paths of the permutation EG(G_n)(·, x) and the cadlag paths of the inverse permutation, thus showing that EG is continuous.



Finally, by Corollary <ref> and Proposition <ref>, we know that our tableau process limit F ∈ almost surely, so 

    U_n = EG(F_n) → U = EG (F)

 in distribution as well by the continuity of the map EG. This proves convergence of random sorting networks at the center to a swap process U. The only thing left to do to prove Theorem <ref> when u=0 is to show that the limit EG(F) has time-stationary increments, as the spatial stationarity and mixing follow from the spatial stationarity and mixing of F.


 U has time-stationary increments. Namely, the distribution of the process  (U(·,s)^-1U(·,s+t)), t≥ 0) does not depend on s.





The sequence of transpositions {π_i_1, π_i_k} in a random sorting network is equal in law to the sequence {π_i_ℓ, π_i_ℓ + k -1}.  To prove this time stationarity, note that if we remove the first swap π_i_1 from a sorting network, we can get another sorting network by adding the swap π_n - i_1 to the end of the sorting network. This result was first proved in <cit.>.



We use this idea to extend the process U_n, which only completes n  2 swaps at the first n  2 times of a rate-n Poisson process Π_n, to a process U_n^*, which completes swaps at every time in Π_n. Let the first N swaps in U_n^* be as in U_n and then recursively define the kth swap in U_n^* to be equal to π_n - j, where π_j is the (k - n  2)th swap in U_n^* for k > N. Then U_n^* is a time-stationary process, and U_n^*(x, t) = U_n (x, t) for all t ≤ T_n, where T_n is the n  2th point in Π_n.



 Since T_n ∞ as n →∞, and U_n  U, U_n^*  U as well. Finally, since each U_n^* has stationary increments, U must have stationary increments as well. 



Putting this all together, we obtain Theorem <ref> in the u=0 case.

 

Let a_n be a sequence of integers with a_n = o(n). Let U_n be the swap process defined by 

    U_n(x, t) = ^n_⌊ nt ⌋(a_n + x) - a_n,

where ^n is an n-element random sorting network. Then 

    U_n  U,

where U is a swap process that is stationarity and mixing of all orders with respect to the spatial shift, and has time-stationary increments.



The Local Limit Outside the Center

In this section, we prove that the local limit of random reverse standard staircase Young tableaux exists at distance ⌊ un ⌋+ o(n) outside the center. This will immediately imply the existence of the local limit outside the center for sorting networks via the Edelman-Greene map EG in Section <ref>. 



Let u ∈ (-1, 1), a_n = o(n), and let G_n be the inclusion functions for the sequence of tableau processes X_n(⌊ un ⌋  + a_n, n, n). Then
 
    G_n   F^u = 1/√(1 - u^2)F,

 where F is the limit when u = 0.


We will assume that a_n = 0 throughout, as it is easy to use domination lemmas to conclude Theorem <ref> for general a_n from this case. The basic idea of the proof is as follows. 
By using the domination lemmas in Section <ref>, it is easy to see that any subsequential limit G at a distance ⌊ un ⌋ outside the center must be stochastically dominated by F^u, so we just need to show domination in the opposite direction. For this, we show that the expected heights in the tableau process corresponding to F^u are greater than expected heights in the tableau process corresponding to G at every location and every time.



 Note that it is possible to get domination in the opposite direction for almost every value of u by comparing the number of squares in a tableau process at time t with the expected number of squares in each of processes shifted by u, integrated over all u ∈ (-1, 1). However, this approach only proves Theorem <ref> for almost every u. To prove the theorem for any u, we take the following approach. 
 
 By considering the inclusion functions G_n of the shifted tableau processes as elements of = [0, ∞]^ we have a set  of subsequential limits of G_n by compactness. Consider largest and smallest elements in  in the stochastic ordering on inclusion functions. Such elements exist since  is closed and the space of probability measures on  is compact. Call G ∈ a limsup if for any G' ∈, G'  G if and only if G' = G. Similarly, we define a liminf in  to be any G ∈ such that for G' ∈, G'  G if and only if G' = G. 
 
 We show that these elements are translation invariant, and that any translation invariant element of  has expected heights less than those of F^u. Therefore any limsup or liminf in  must be F^u. As any element in  must lie between a liminf and a limsup, this allows us to conclude that = { F^u }.
 

Shifted tableau processes.     We introduce new notation for the tableau processes used in this section, using Y instead of X to distinguish from centered tableau processes. For a fixed value of u ∈ (-1, 1), define Y^K_n(t) to be the rate Kn tableau process on the diagram T(⌊ un ⌋, n).  When K = 1, we omit the superscript. To establish the translation invariance of liminfs and limsups, we need a basic domination lemma involving these processes.


 Fix u ∈ (-1, 1), and choose ℓ so that for every n, 
    T(⌊ un ⌋, n)  T(⌊ u(n +ℓ) ⌋+ 2, n + ℓ),    
       T(⌊ un ⌋ + 2, n)  T(⌊ u(n+ℓ) ⌋, n + ℓ).

Let T_n be the time when n  2/2 squares have been added to Y_n, and let θ_n = n+4ℓ/n - 1. Then for all large enough n,

    Y_n+2ℓ^θ_n^2τ Y_n+ℓ^θ_n Y_n     
       Y_n+2ℓ^θ_n^2 Y_n+ℓ^θ_n Y_n,


where all stochastic domination holds up to time T_n.
 

As before, τ is the spatial shift. Thus τ Y^K_n(t) is exactly Y^K_n shifted by 2 units to the right so that it lives on the diagram T(⌊ un ⌋ + 2, n). The essence of this lemma is that we can get domination of the shifted process τ Y_n_1 over Y_n by letting n_1 be slightly larger than n, and slightly speeding up τ Y_n_1. The precise value of the speed-up θ_n is not important here, only that θ_n → 1 as n →∞.

 
 
We just prove that τ Y_n+ℓ^θ_n Y_n up to time T_n, as the rest of the inequalities follow using the same argument. By Lemmas <ref> and <ref>, we just need to show that if Y_n and τ Y_n+ℓ^θ_n are in the same configuration A, and z is a corner of both T(⌊ un ⌋, n)  A and T(⌊ u(n + ℓ) ⌋ + 2, n+ℓ)  A, that v_n(z, A) < v_n+ℓ(z, A), where v_n and v_n+ℓ refer to rates in Y_n and Y_n+ℓ^θ_n, respectively. To see this, observe that for any set A of cardinality at most n  2/2,

    v_n+ℓ(z, A)/v_n(z, A)   = θ_n n+ℓ/nT(⌊ un ⌋, n) ∖ A/T(⌊ u(n + ℓ) ⌋ + 2, n + ℓ) ∖ A∏_y ∈ R_z^n+ℓ∖ R_z^n(1 + 1/h_y^n+ℓ -1) 
       ≥(n+ 4ℓ)(n+ℓ)/n(n-1)n(n-1)/2(n+ℓ)(n+ℓ-1) - n(n-1)
        > 1.

 
 Now we can characterize liminfs and limsups in .


 
   Suppose G ∈ is a limsup (or a liminf). Then G is translation invariant.
 

 
Throughout this proof, we let G^K_n be the inclusion function of Y^K_n(t). Let G_n(i)→ G for some liminf G ∈ (the case for G a limsup is similar). Note that by Lemma <ref>, G'  G for any subsequential limit G' of G^θ_n(i)^2_n(i) + 2ℓ.  By passing to the limit, we remove any issues with the stopping time T_n from Lemma <ref> since T_n ∞ as n →∞. Such limits exist by compactness of .



However, since θ_n^2 → 1 as n →∞, G' is also a subsequential limit of G_n(i) + 2ℓ, so since G is a liminf, G' = G. Therefore G^θ_n(i)^2_n(i) + 2ℓ G. Now again by Lemma <ref>, we have that 

    G^θ_n(i)^2_n(i) + 2ℓG^θ_n(i)_n(i) + ℓG_n(i)    
       G^θ_n(i)^2_n(i) + 2ℓG^θ_n(i)_n(i) + ℓ∘τG_n(i),

where G_* = G ∧ T_n for each of the inclusion functions G_* corresponding to the tableau processes in (<ref>). Note here that if G is the inclusion function for the process Y, then G ∘τ is the inclusion function for the shifted process τ Y. By the squeeze theorem, and the facts that θ_n → 1 and T_n ∞, this implies that both G_n(i) + ℓ G and G_n(i) + ℓ∘τ G, allowing us to conclude that G  ∘τ G.
 

 We now aim to show that every translation-invariant element G ∈ is the rescaled central limit F^u by comparing heights. For any J ∈, x ∈ 2 + 1 and t ∈ [0, ∞), define the height function

 
    h(J, x, t) = {z = (z_1, z_2): z_1 = x  x + 1  J(z) < t }.


 We first prove the following lemmas about the expected heights in F.


h(F, x, t) is finite for all t ∈ [0, ∞) and x ∈ 2.



Note that F_n  F, and that

    h(F_n, x, t)  h(F, x, t)

for all t and x since F has no atoms. Recall also that the tableau processes X_n are dominated by a sped-up cylinder process C(n, 8n) up to the stopping time T_n when n^2/4 squares have been to X_n. 
Since T_n→∞ in probability as n→∞, we also have 

    h(F_n ,x, t∧ T_n)  h(F, x, t).

By the symmetry of the cylinder, the expected height at x at time t in C(n, 8 n) is 8t, so by Fatou's lemma,


    h(F, x, t) ≤lim inf_n →∞ h(F_n, x, t∧ T_n) ≤ 8 t.



 
  Let T^n_t to be the stopping time when ⌊ nt ⌋ squares have been added to the centered tableau process X_n = X(0, n, n). There exists a subsequence {n_i : i ∈} such that 
 
    h(F_n_i, x, T^n_i_t) → h(F, x, t).






 
 
We find a dominating “infinite tableau process" for the sequence of tableau processes X_n. We can find an increasing sequence {n_i : i ∈} and a decreasing sequence {δ_i : i ∈} such that for all i, the tableau process 

    Z_i = X(0, n_i, (1 + δ_i)n_i)

 stochastically dominates the process Z_i-1 up to time T^n_i-1_t, and such that

    ∏_i=1^∞(1 + δ_i) < ∞.

Finding such sequences can easily be done by iteratively choosing n_1, n_2 and  appropriately in Lemma <ref> (noting that that domination in that lemma is up to the time when n_1^2 squares have been added, so we can let  become arbitrarily small for large n_1 and still have domination up to time T^n_1_t).
Then letting J_i be the inclusion function for Z_i, we have

    J_i = ∏_j=1^i(1 + δ_j)^-1F_n_i J = ∏_j=1^∞ (1 + δ_j)^-1 F.
 J_i is a monotone decreasing sequence in the stochastic ordering. Moreover,
F_n_i J_i  J  so h(F_n_i, x, t)   h(J, x, t),
for every x and t. Finally, heights in J have finite expectation by Lemma <ref> as J is a sped-up version of F. Therefore the dominated convergence theorem, 

    h(F_n_i, x, t) → h(F, x, t).

As |  h(F_n_i, x, t) -  h(F_n_i, x, T^n_i_t)| → 0 as n →∞, this completes the proof.

  In order to compare the heights in F^u and G we will need to translate the tableau processes to swap processes on the integers. The reason for doing this is that we can relate the expected height at position x to the expected number of swaps at position x, and the expected number of swaps at any position in a sorting network is given by the following theorem from <cit.>.
  
  
  Let  be a random sorting network on n particles given by a sequence of adjacent transpositions {π_k_1, π_k_N}, and let a_n be a sequence of positive integers with 2a_n/n - 1→ u ∈ (-1, 1). Then
  
    n(k_1 = a_n) →4/π√(1 - u^2)        ({i ≤ Cn : k_i = a_n}) →4C/π√(1 - u^2).

    
    
We use this theorem to prove the following lemma about expected height in F.




    lim_t → 0 h(F, 0, t)/t≥4/π.




By Lemma <ref>, we can first replace h(F, 0, t) by lim_n →∞ h(F_n_i, 0, T^n_i_t). Now we replace h(F_n_i, 0, t) by the strictly smaller quantity (F_n_i(z_0) < T^n_i_t) where z_0 = (1,1), and note that

    (F_n_i(z_0) < T^n_i_t) ≥  1 - (1 - p_i/n_i)^⌊ n_it ⌋

where p_i = v_X_n_i (z_0, ∅). We can make this replacement since the rate of adding the square z_0 is monotone increasing in time. Now by Theorem <ref>, p_i →4/π as i →∞, so we have

    lim_t → 0 h(F, 0, t)/t≥lim_t → 01 - e^-4t/π/t = 4/π,

as desired.

  For x ∈ 2 + 1, we now define s(J, x, t) to be the number of swaps at location x before time t in the swap process EG(J), where the map EG is as in Section <ref>.  We then have the following relationships between heights and swaps.

 
 
 Let x ∈ 2, t ∈ [0, ∞), and let G ∈ be translation invariant. Then G ∈ and h(G, x, t) =  s(G, x, t) ( is defined at the beginning of Section <ref>). We also have that h(F, x, t) =  s(F, x, t). 
 

 
We can use the bound in Lemma <ref> to conclude that G  F, thus implying that at any time t, there is a bi-infinite sequence of squares in the bottom row that have not been added to G. Moreover, there exists a constant C such that for all large enough n the modified rates in each G_n are bounded up to the stopping time T when n^2/4 squares have been added by C times the modified rate in F_n. This allows us to conclude that G is injective, by the proof of Proposition <ref>. Therefore G ∈.



Thus we can apply the Edelman-Greene map EG from Section <ref> to G, giving a translation-invariant swap process EG(G) and allowing us to define s(G, x, t) for all t. We now show that h(G, x, t) =  s(G, x, t). By translation invariance, it suffices to consider the case x = 1. For each square z ∈, let π(z) ∈ 2  + 1 be the location of the swap in EG(G) corresponding to the square z. Since only squares z' ≥ z_0 can have π(z) = 1, we have


    s(G, 1, t)    = ∑_z' ≥ z_0(F(z') < t π(z') = 1) 
       = ∑_i=1^∞∑_j ∈ [1 - (i-1),  1 + (i-1)](F(j, i) < t π(j, i) = 1) 
       = ∑_i=1^∞∑_j ∈ [1 - (i-1),  1 + (i-1)](F(q_i, i) < t π(q_i, i) = 1+ q_i - j).

Here q_i is either 1 or 2 depending on the parity of i. The second equality is just rearranging terms in the sum and the final equality comes from the translation invariance of the swap process. Since 
    π(q_i, i) ∈ [q_i - (i-1),  q_i + (i-1)],
 we have

    ∑_j ∈ [- i , i ](F(q_i, i) < t π(q_i, i) = 1 - j) = (F(q_i, i) < t),

and so the final line of (<ref>) is equal to h(G, 1, t). The exact same proof works for F.


 
 
 Suppose G ∈ is translation invariant. Then G 1/√(1 - u^2)F.
 

 
 First define 
 
    = {f: 2 + 1 ×_+ →},

and define  H: → by H(J) = h(J, ·, ·). Note that H a strictly decreasing function with respect to the pointwise orders on   and . As every G ∈ satisfies G  F^u, to show that F^u  G it suffices to show that h(G, x, t) ≤ h(F^u, x, t) for all x and t. By Theorem <ref>,
 
    s(G_n, 0, t)  →(4/π√(1 - u^2))t.

Then by Fatou's Lemma and Lemma <ref> we have that
 
    h(G, 0, t) =  s(G, 0, t) ≤lim_n →∞ s(G_n, 0, t)    =  (4/π√(1 - u^2)) t.


Now by the time-stationarity of the increments in the limit EG(F) (Proposition <ref>), we have that s(F, 0, t) is linear in time. Therefore h(F, 0, t) must be linear in time as well since it is equal to 
s(F, 0, t) by Lemma <ref>. Combining this with Lemma <ref> gives that h(F, 0, t) = K t for some K ≥4/π, so


    h( F^u, 0, t) ≥(4/π√(1 - u^2))t,

which combined with (<ref>) gives the desired result.




We can finally combine Propositions <ref> and
<ref> to conclude the convergence of the processes
G_n to F^u, which completes the proof of Theorem
<ref>. This in turn completes the proofs of
Theorems <ref> and <ref>.


Proposition <ref> also allows us to conclude the following proposition about expected heights in F, and therefore swaps in EG(F).

 For any x and t, we have

    h(F, x, t) =  s(F, x, t) = 4/πt.





Appendix


G_n is tight, so it has subsequential limits in distribution. Suppose that G^1 and G^2 are two different subsequential limits of G. Then there are subsequences G_(i) G^1 and G_β(i) G^2. Without loss of generality, we can assume that there are some numbers a_1,  a_m  > 0 such that


    (G^1 ∈∏_k=1^m[0, a_k]) - (G^2 ∈∏_k=1^m[0, a_k]) > 0.

Then there is some δ > 0 such that


    (G^1 ∈∏_k=1^m[0, a_k+ δ)) - (G^2 ∈∏_i=1^m[0, a_k + 2 δ]) > 0,

By weak convergence, we get the following chain of inequalities.

    lim sup_i →∞(G_β(i)∈∏_k=1^m[0, a_k + 2 δ])    ≤(G^2 ∈∏_k=1^m[0, a_k + 2 δ]) 
       < (G^1 ∈∏_k=1^m[0, a_k + δ)) 
       ≤lim inf_i →∞(G_(i)∈∏_k=1^m[0, a_k + δ)).

 However, letting = δ/a + δ where a = max_k a_k, for any large enough i there exists some J such that for all j ≥ J,

 
    ( G^_(i)∈∏_k=1^m[0, a_k + δ))    ≤((1 + ) G^_(i)∈∏_k=1^m[0, a_k + 2δ]) 
       ≤(G_β(j)∈∏_k=1^m[0, a_k + 2δ] ),

since (1+)G^_(i) G_β(j) for all large enough j by assumption. Thus

 
    lim sup_i →∞( G_β(i)∈∏_k=1^m[0, a_k + 2δ] ) ≥lim inf_i →∞(G_(i)^∈∏_k=1^m[0, a_k + δ)),

which contradicts (<ref>), since
 
    lim inf_i →∞(G^_(i)∈∏_k=1^m[0, a_k + δ))    = lim inf_i →∞(G_(i)∈∏_k=1^m[0, a_k + δ)).

  Thus G^1 = G^2 for any two subsequential limits of G_n, so G_n has a distributional limit.




Acknowledgements. Omer Angel was supported in part by NSERC. Duncan Dauvergne was supported by an NSERC CGS D scholarship. Bálint Virág was supported by the 
Canada Research Chair program, the NSERC Discovery Accelerator
grant, the MTA Momentum Random Spectra research group, and the ERC 
consolidator grant 648017 (Abert). We would also like to thank the Banff International Research Station for hosting a focussed research group that initiated this research.






