Oriented swap process and last passage percolation notes

This page can be used for writing up results in more or less finished form. See the talk page for discussion and more sketchy/incomplete ideas.

1. Oriented swap process (OSP)
2. Last passage percolation (LPP)
3. Point-to-line and line-to-line LPP
4. Particle and block finishing times
5. The absorbing time

add definitions here

\begin{align*} T(a,b;c,d) &= \max_{\pi \in \Pi_{(a,b)\to(c,d)}} \sum_{(i,j)\in \pi} X_{i,j} \quad \textrm{(last passage percolation time from }(a,b)\textrm{ to }(c,d) \textrm{)} \\ \mathbf{V}^n &= (V^n_1,\ldots,V^n_{n-1}) \quad \qquad \qquad \qquad \qquad \qquad \qquad \textrm{(block finishing times)} \\ \mathbf{U}^n &= (T(1,1; n,1), T(1,1; n-1,2), \ldots, T(1,1; 1,n)) \qquad \textrm{(point to line last passage percolation)} \\ \mathbf{W}^n &= (T(1,1; n,1), T(2,1; n,2), \ldots, T(n,1; n,n)) \qquad \textrm{(line to line last passage percolation)} \end{align*}

Theorem. $ \mathbf{U}^n \stackrel{D}{=} \mathbf{W}^n $

Proof. add this

Conjecture. $ \mathbf{V}^n \stackrel{D}{=} \mathbf{W}^n $

Proposition. Let $f_n(x_1,\ldots,x_n)$ denote the joint density function of the random vector $\mathbf{U}^n$. Then we have the recurrence relation $$ f_{n+1}(x_1,\ldots,x_{n+1}) = \exp\left( - \sum_{k=1}^{n+1} x_k \right) \int_0^{x_1 \wedge x_2} \int_0^{x_2 \wedge x_3} \ldots \int_0^{x_n \wedge x_{n+1}} f_n(y_1,\ldots,y_n) \exp\left( \sum_{k=1}^{n+1} y_{k-1} \vee y_k \right) dy_n \, dy_{n-1} \ldots dy_2 \, dy_1 $$

add this

add an explanation of the algorithm for computing the joint density of the finishing times

Weak version of the main conjecture. For $n\ge2$ and $1\le k< n$, we have the equality in distribution $$ (V^n_k, V^n_{k+1}) \stackrel{D}{=} (U^n_k, U^n_{k+1}). $$

It seems reasonable to try to attack the main conjecture by trying to prove the weaker version first, in the hope that a proof might reveal hints of a more general idea. As it turns out, this weaker version already leads us to some interesting combinatorial idea, and specifically the jeu de taquin map.

Consider as before an array $(X_{i,j)})_{i,j\ge 1}$ of iid $\operatorname{Exp}(1)$ random variables. Denote $$ X_{i,j}' = \begin{cases} 0 & \textrm{if }(i,j)=(1,1) \\ X_{i,j} & \textrm{otherwise.} \end{cases} $$ Let $T_{i,j}=T(1,1;i,j)$ denote the last passage percolation times (from the corner $(1,1)$) associated with the array $(X_{i,j})_{i,j}$. We have $$ (U^n_k,U^n_{k+1}) = (T_{k, n+1-k}, T_{k+1, n-k}). $$ Similarly, let $T'_{i,j}=T'(1,1;i,j)$ denote the last passage percolation times associated with the modified array $(X_{i,j}')_{i,j}$. We are actually only interested in the rectangular $(k+1)\times (n-k)$ subarray $$ \boldsymbol{\tau}^{(n,k)} = (T'_{i,j})_{1\le i\le k+1, 1\le j\le n-k} $$ Let $$ \mathbf{t}^{(n,k)} = (T''_{i,j})_{1\le i\le k+1, 1\le j\le n-k, (i,j)\neq (k+1,n-k)} $$ be a new array obtained from the array $\boldsymbol{\tau}^{(n,k)}$ by performing a jeu de taquin sliding operation, as in the figure below:

Figure 1. The jeu de taquin sliding operation. Here, the path for sliding the array entries is chosen so as to preserve the monotonicity of the entries along rows and columns.

Proposition. We have the equality in distribution $$ (V^n_k, V^n_{k+1}) \stackrel{D}{=} (T_{k, n+1-k}'', T_{k+1, n-k}''). $$

Proof. Using a standard idea from the Oriented Swap Process paper, the random variables $V^n_k$ and $V^n_{k+1}$ can be associated with a TASEP-like interacting particle system on the discrete interval $[1,n]$ that at time $0$ has ordinary (first-class) particles in positions $1,\ldots,k$, a second-class particle in position $k+1$, and holes in positions $k+2,\ldots,n$. The system then evolves according to the usual (multi-class) TASEP rules. Now, it turns out that such a system can be described in terms of an ordinary TASEP with only first-class particles and holes: this is a generalization of the idea described in section 7 of the paper Jeu de taquin dynamics on infinite Young tableaux and second class particles by Romik and Sniady. More precisely, the finite-interval process with the second-class particle is isomorphic to an ordinary TASEP on the interval $[1,n+1]$ with initial conditions $\eta_0 = (\overbrace{1,\ldots,1}^{k},0,1,\overbrace{0,\ldots,0}^{n-k-1})$ — it can be checked that the position of the $(0,1)$ pair (referred to as the $*$-pair in the Romik-Sniady paper) evolves in the same way as the second-class particle in the original process.

The next thing to note is that this TASEP with initial condition $\eta_0$ can be described in terms of a last passage percolation process with precisely the weight array $\boldsymbol{\tau}^{(n,k)}$ using the standard correspondence between TASEPs and LPP, since setting the corner weight $X_{1,1}'$ achieves the goal of causing the standard step initial configuration $(1,\ldots,1,1,0,0,\ldots,0)$ to jump immediately to $\eta_0$ at time $t=0$; from there the evolution proceeds according to the usual TASEP rules.

Finally, one needs to check that under this way of realizing the random vector $(V^n_k, V^n_{k+1})$, the vector maps precisely to $(T_{k, n+1-k}'', T_{k+1, n-k}'')$. This is related to the fact, also explained in the Romik-Sniady paper, that the jeu de taquin path precisely encodes the path of the second class particle (vertical steps of the jeu de taquin path correspond to the second-class particle moving to the left, and horizontal steps correspond to the second-class particle moving to the right). One can now separate into two cases depending on whether the jeu de taquin path ever makes it to the last column of the array; this division into cases corresponds precisely to the question of which of the two random variables $V^n_k$, $V^n_{k+1}$ is smaller in value. Need to explain this better - I will add more details later. $\Box$

In view of the proposition, we see that the weakened conjecture can be reformulated as follows:

Weak version of the conjecture, reformulated version. We have the equality in distribution $$ (T_{k, n+1-k}'', T_{k+1, n-k}'') \stackrel{D}{=} (T_{k, n+1-k}, T_{k+1, n-k}). $$

It can be checked that it is not the case that $T_{i,j}'' \stackrel{D}{=} T_{i,j}$ for all $i,j$.

• K. Johansson, M. Rahman. Multi-time distributions in discrete polynuclear growth.
• K. Johansson. The two time distribution in discrete last passage percolation.
• D. Romik, P. Sniady. Jeu de taquin dynamics on infinite Young tableaux and second class particles.