\documentclass[finalversion]{FPSAC2018}
\articlenumber{95}

\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}


\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\newtheorem{alg}[thm]{Algorithm}

\theoremstyle{remark}
\newtheorem{remark}[thm]{Remark}
\newtheorem{example}[thm]{Example}

\newcommand{\Comment}[1]{{\color{blue} \sf ($\clubsuit$ #1 $\clubsuit$)}}

\DeclareMathOperator{\MLQ}{MLQ}
\DeclareMathOperator{\TASEP}{TASEP}
\DeclareMathOperator{\wt}{wt}
\DeclareMathOperator{\Left}{Left}
\DeclareMathOperator{\Up}{Up}
\DeclareMathOperator{\AMLQ}{AMLQ}
\DeclareMathOperator{\RAT}{RAT}
\DeclareMathOperator{\CRT}{CRT}
\DeclareMathOperator{\weight}{weight}
\DeclareMathOperator{\rest}{rest}
\DeclareMathOperator{\umv}{umv}
\DeclareMathOperator{\ufree}{ufree}
\DeclareMathOperator{\lfree}{lfree}



\title{Bijection from multiline queues to rhombic tableaux for the inhomogeneous 2-TASEP}

\author{Olya
Mandelshtam\thanks{\href{mailto:olya@math.brown.edu}{olya@math.brown.edu}.
Olya Mandelshtam was supported by the Postdoctoral Presidential
Fellowship and NSF grant DMS-1704874.}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Brown University, Providence, Rhode Island}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{
The 2-TASEP is a model describing the dynamics of first and second class particles hopping in one direction on a finite 1D lattice. For the 2-TASEP with periodic boundary conditions, there is a well-known description for the stationary probabilities in terms of \emph{multiline queues} of Ferarri and Martin. On the other hand, for the 2-TASEP with open boundary conditions, there is a rich connection to tableaux combinatorics: its stationary probabilities are described using \emph{rhombic alternative tableaux}. In this article, we unify the two approaches by defining a new object, the \emph{toric rhombic tableaux} and describing a simple bijection between these tableaux and multiline queues for the 2-TASEP with periodic boundary conditions. Furthermore, with a natural modification of both the rhombic alternative tableaux and the toric rhombic tableaux, we obtain a tableaux interpretation for probabilities of the inhomogeneous 2-TASEP both with periodic and open boundary conditions, in which different classes of particles hop with different rates. Through our bijection, our result generalizes a result of Ayyer and Linusson on multiline queues. 
}

%% put your French abstract here, or comment this out if you don't have one
%\resume{French French French}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{multispecies TASEP, multiline queues, rhombic tableaux}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{95-Mandelshtam.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle


%% define your title in the usual way



%The multispecies TASEP with periodic boundary conditions is a model describing the dynamics of particles of different classes hopping in one direction on the finite lattice $\mathbb{Z}/n\mathbb{Z}$. When all classes of particles hop at the same rate (the \emph{homogeneous} TASEP), there is a well-known description for the stationary probabilities in terms of \emph{multiline queues} of Ferarri and Martin. On the other hand, there is a rich connection to tableaux combinatorics for the stationary probabilities of the multispecies TASEP with open boundary conditions: for the two-species TASEP, its stationary probabilities are described using \emph{rhombic alternative tableaux} (RAT), which specialize to the well-studied alternative tableaux for the one-species TASEP. In this paper, we unify the two approaches by defining a new object, the \emph{toric rhombic tableaux} and describing two simple bijections between these tableaux and multiline queues for the two-species TASEP. Our tableaux give probabilities for the two-species TASEP on $\mathbb{Z}/n\mathbb{Z}$ and are closely related to the rhombic alternative tableaux. Furthermore, with a natural modification of the toric alternative tableaux, we obtain an interpretation for probabilities of the \emph{inhomogeneous two-species TASEP}, in which different classes of particles hop with different rates. Following our bijection, our result generalizes a result of Ayyer and Linusson on multiline queues. 


\section{Introduction}

The 2-TASEP is a Markov chain describing class 1 and 2 particles hopping in one direction on a finite 1D lattice with $n$ sites, with priority given to the class 2 particles. The 2-TASEP with open boundaries is strongly connected to a rich garden of combinatorial objects, including tableaux (alternative tableaux \cite{V08}, permutation tableaux \cite{CW07}, staircase tableaux \cite{CW11,CMW15}). More specifically, stationary probabilities for states of the 2-TASEP with open boundaries can be expressed as a sum over weighted fillings of certain tableaux \cite{MV16}. The 2-TASEP with periodic boundary conditions, on the other hand, is a special case of the $k$-TASEP on $\mathbb{Z}/n\mathbb{Z}$, which has been studied primarily using multiline queues of Ferrari and Martin \cite{FM09}: stationary probabilities for states of the 2-TASEP with periodic boundary conditions can be expressed by enumerating the corresponding multiline queues \cite{ALS09}. Our goal is to draw a parallel between the two methods by describing a bijection between certain tableaux and multiline queues in the 2-TASEP case.

The 2-TASEP of size $n$ has sites numbered 1 through $n$ with each site occupied by 1, 2, or 0, representing the particles of class 1 and 2 and holes, respectively. The possible transitions of the 2-TASEP chain are the following, all occurring with rate 1:
\[X\ 2\ 0\ Y \mathrel{\mathop{\rightarrow}^{1}} X\ 0\ 2\ Y, \qquad X\ 2\ 1\ Y \mathrel{\mathop{\rightarrow}^{1}} X\ 1\ 2\ Y, \qquad X\ 1\ 0\ Y \mathrel{\mathop{\rightarrow}^{1}} X\ 0\ 1\ Y,\]
where $X$, $Y$ are words in $\{2,1,0\}$. In the open boundary case, the bulk transitions are the same as above, with parameters $\alpha$ and $\beta$ dictating the rates of boundary transitions:
\[
0\ Y \mathrel{\mathop{\rightarrow}^{\alpha}} 2\ Y,\qquad \qquad Y\ 2 \mathrel{\mathop{\rightarrow}^{\beta}} Y\ 0.
\]

In Section \ref{sec:prelim}, we define the multiline queues (MLQ) and rhombic alternative tableaux (RAT), which are the main objects we work with. Our first main result is in Section \ref{sec:CRT}, in which we define the \emph{cylindric rhombic tableaux} (CRT) and give a direct bijection $\Psi_{\CRT}$ with MLQs.

\begin{thm}
For $X$ a state of the 2-TASEP and $\CRT(X)$ denoting the set of associated cylindric rhombic tableaux, the stationary probability of $X$ is proportional to $|\CRT(X)|$. 
\end{thm}

\begin{thm}
For $X$ a state of the 2-TASEP and $\MLQ(X)$ denoting the set of associated multiline queues, $\Psi_{\CRT}:\MLQ(X)\rightarrow\CRT(X)$ is a bijection.
\end{thm}

The inhomogeneous 2-TASEP with periodic boundary conditions is a generalization with additional parameters $x_2$, $x_1$, which are the respective rates of the transitions $21\rightarrow12$ and $10\rightarrow01$ (by normalization, $20\rightarrow02$ still has rate 1). In their paper studying a Markov chain on permutations similar to the inhomogeneous $k$-TASEP with transition rates $x_{ij}$ between particles of class $i$ and $j$ for $k\geq i >j\geq0$, Lam and Williams conjectured that stationary probabilities for this process are proportional to polynomials in the $x_{ij}$'s with positive integer coefficients \cite{LW12}. This conjecture was solved when $x_1=1$ by Ayyer and Linusson for the 2-TASEP \cite{AL14}. Using our tableaux approach, in Section \ref{sec:inhomog} we present a simple solution incorporating $x_2$ and $x_1$ for the 2-TASEP case by putting weights $\wt(T)$ on CRT; our solution recovers the result of \cite{AL14}. 

\begin{thm}
For $X$ a state of the inhomogeneous 2-TASEP with periodic boundary conditions and with transition rates $x_2,x_1$, the stationary probability of $X$ is proportional to $\sum_{T\in\CRT(X)}\wt(T)$.
\end{thm}

Finally, we are able to naturally extend our results to the inhomogeneous 2-TASEP with open boundaries: in Section \ref{sec:AMLQ}, we use our bijection to define \emph{acyclic multiline queues} which are in bijection with the RAT, and put weights $\wt_M(T)$ on the RAT to obtain an analogous formula for the stationary probabilities.

\begin{thm}
For $X$ a state of the inhomogeneous 2-TASEP with open boundaries and with transition rates $x_2$, $x_1$, the stationary probability of $X$ is proportional to $\sum_{T\in\RAT(X)}\wt_M(T)$.
\end{thm}

This is an extended abstract of the article \cite{man17}.

\section{Preliminaries}\label{sec:prelim}

A state of the 2-TASEP is represented by a word $X=X_1\ldots X_n$ where $X_i \in \{2,1,0\}$. For the 2-TASEP with periodic boundary conditions, we consider $X_1$ and $X_n$ to be adjacent. To distinguish between the different 2-TASEPs we study, we will write $\TASEP(n,r)$ representing states of the 2-TASEP with open boundaries with $n$ particles and exactly $r$ class 1 particles, and $\TASEP(k,r,\ell)$ representing states of the 2-TASEP with periodic boundary conditions and exactly $k$ class 2 particles, $r$ class 1 particles, and $\ell$ holes.

We define the two main objects we work with in the 2-TASEP context: multiline queues (MLQs) and rhombic alternative tableaux (RAT). %Our definition of multiline queues will be limited to the 2-TASEP case, although they have a more general definition to compute probabilities of the $k$-TASEP with periodic boundary conditions.

\subsection{Multiline queues}
%MLQs, first introduced by Ferrari and Martin, give an elegant combinatorial formula for the stationary probabilities of the $k$-TASEP on a ring \cite{FerrariMartin}. The formula holds for any $k$, but for our purposes we define only MLQs that correspond to the 2-TASEP.

An MLQ of size $(k,r,l)$ with $n:=k+r+\ell$ is a choice of $\ell$ and $\ell+r$ locations in the top and bottom rows, respectively, of a $2\times n$ array. Locations are labeled from left to right with $[1,n]$. We identify the left and right edges of the array, making it a cylinder; thus location 1 is to the right of and adjacent to location $n$. 

\begin{figure}[!ht]
  \centerline{\includegraphics[width=0.4\linewidth]{MLQ_example_.pdf}}
\centering
% \caption{An MLQ of size $(k,r,\ell)$ with $n=k+r+\ell$.}\label{fig:MLQ_ex}
 \end{figure}

%, with each such choice corresponding in a unique way to some state of $\TASEP(k,r,\ell)$. The elegant combinatorial formula of Ferrari and Martin states that the stationary probability of a state of $\TASEP(k,r,\ell)$ is proportional to the number of multiline queues corresponding to that state \cite{FM09}. 
Each MLQ corresponds uniquely to a state of the $\TASEP(k,r,\ell)$, which we call its type. To determine the type of an MLQ, we describe a \emph{ball drop algorithm}, consisting of balls from the top row dropping to occupy balls in the bottom row. 

\begin{figure}[!ht]
  \centerline{\includegraphics[width=\linewidth]{MLQ_drops.pdf}}
\centering
 \caption{The steps of Algorithm \ref{alg:drop} for an MLQ of type $X=12200120200$. The white (occupied) bottom row balls are the 0-balls, and the weight vector is $(1,1,0,0,2)$.}\label{fig:MLQ}
 \end{figure}

\begin{alg}[Ball drop]\label{alg:drop}
Let $y_1<\cdots<y_{\ell}$ be the locations of the top row balls in the MLQ. For $i=\ell,\ldots,1$:

\textbf{Ball drop of $y_i$.} Drop the top row ball at $y_i$ to the bottom row to occupy the first unoccupied bottom row ball weakly to its right, while marking every unmarked vacancy it hits on its path. The bottom row ball it occupies is marked as a 0-ball. The \emph{hitting weight} of the occupied 0-ball is the number of vacancies that were marked during the drop. 

\textbf{Output.} All bottom row balls that are not 0-balls (i.e.~were not hit by a dropping top row ball) are marked as 1-balls. A state of the 2-TASEP is read off the bottom row by associating 0-balls, 1-balls, and vacancies to holes, class 1, and class 2 particles, respectively. The output of the algorithm is the type $X$ of the MLQ and a weight vector $(w_1,\ldots,w_{\ell})$ of hitting weights from left to right.
\end{alg}

See Figure \ref{fig:MLQ} for an example of Algorithm \ref{alg:drop}.

%\begin{remark}
%In fact, the type of the MLQ is independent of the order in which top row balls are dropped, but we require that balls are dropped from right to left to obtain a unique weight vector for each MLQ.
%\end{remark}

\begin{lem}\label{uniqueness}
Given the output of the type $X\in\TASEP(k,r,\ell)$ and weight vector $(w_1,\ldots,w_{\ell})$ of Algorithm \ref{alg:drop}, one can uniquely determine the locations of the top row balls of an MLQ.
\end{lem}

Lemma \ref{uniqueness} is proved by reversing Algorithm \ref{alg:drop} with weight vector $(w_1,\ldots,w_{\ell})$ and ``lifting'' the 0-balls at locations $x_1<\cdots<x_{\ell}$ such that the 0-ball at $x_i$ marks the first $w_i$ unmarked vacancies to its left. Observe that at the end of Algorithm \ref{alg:drop}, each marked vacancy will have been marked by exactly one dropping ball. Consequently, it can be shown that when the lifts are performed from left to right, the original locations of the top row balls of the MLQ are recovered. %by the \emph{ball lift algorithm}.  

%\begin{alg}[Ball lift]\label{ball_lift}
%Let $x_1<\cdots<x_{\ell}$ be the locations of the 0-balls of an MLQ of type $X$ with corresponding weights $(w_1,\ldots,w_{\ell})$. At initialization, the top row is empty and all bottom row vacancies are unmarked. For $i=1,\ldots,\ell$, perform a \emph{ball lift} from a 0-ball at $x_i$ with weight $w_i$ by placing a top row ball directly above the $w_i$'th consecutive unmarked vacancy to the left of $x_i$, while marking each of those $w_i$ unmarked vacancies. 
%\end{alg}
 
% \begin{figure}[!ht]
%  \centerline{\includegraphics[width=\linewidth]{../ToricRat/TRATsource/Tfig7.jpeg}}
%\centering
% \caption{Both figures represent the same  On the left, the top row balls are dropped from right to left, and on the right the top row balls are dropped in arbitrary order. }\label{fig:MLQ}
% \end{figure}

\begin{figure}[!ht]
  \centerline{\includegraphics[width=0.9\linewidth]{MLQ_X.pdf}}
\centering
 \caption{$\MLQ(X)$ for $X=12020$ with weight vectors $(0,2), (1,1), (1,0), (0,1), (0,0)$.}\label{MLQs}
 \end{figure}
 
Since the $\ell$ balls in the top row and the $r+\ell$ balls in the bottom row are chosen independently, there is a total of ${n\choose\ell}{n\choose k}$ MLQs of size $(k,r,\ell)$. The following theorem of Ferrari and Martin gives an elegant expression for probabilities of the 2-TASEP with periodic boundary conditions. We remark that this theorem also holds for the $k$-TASEP with a more general definition of MLQs. Let $\MLQ(X)$ be the set of MLQs of type $X$. 

\begin{thm}[\cite{FM09}]\label{thm_mlq}
Let $X\in\TASEP(k,r,\ell)$ for $n:=k+r+\ell$ be a state of the 2-TASEP with periodic boundary conditions. Then the stationary probability of $X$ is $\Pr(X)=\frac{1}{{n \choose k}{n \choose \ell}}|\MLQ(X)|$.
\end{thm} 

\begin{example}
From Figure \ref{MLQs}, for $X=12020$ we obtain $\Pr(X)=\frac{5}{{5\choose2}{5\choose2}}=\frac{1}{20}$.
\end{example}

\subsection{Rhombic alternative tableaux}

The RAT were defined by the author and Viennot in \cite{MV16} as a solution for the more general 2-ASEP model with open boundaries, in which the parameter $q$ dictates the rate at which particles can hop in the opposing direction (setting $q=0$ recovers the 2-TASEP). In this section, we give a definition of the subset of RAT corresponding to the $q=0$ case.

The RAT are fillings with up-arrows and left-arrows of a tiling of a closed shape whose boundary is composed of south, southwest, and west edges on a triangular lattice. The tiles are three types of rhombic tiles which we call 20-tiles, 10-tiles, and 21-tiles. Each tile can contain an arrow that points either towards its left vertical edge or the top horizontal edge with the condition that any tile that is ``pointed to'' by an arrow must be empty; we call them \emph{left-arrows} and \emph{up-arrows} respectively.  We give a precise definition below.

\begin{defn}\label{def:P(X)}
Let $X\in \TASEP(n,r)$ such that $X$ has $k$ 2's and $\ell$ 0's with $k+r+\ell=n$. Define a lattice path $P(X)$ as follows: reading $X$ from left to right, draw a south edge for a 2, a southwest edge for a 1, and a west edge for a 0. From the northeast corner of $P(X)$, draw $\ell$ west edges followed by $r$ southwest edges, followed by $k$ south edges, thus obtaining a closed region $\Gamma(X)$, whose southeast boundary is $P(X)$. We call $\Gamma(X)$ a \emph{rhombic diagram}.
\end{defn}

Call a rhombus with south and west edges a \emph{20-tile}, a rhombus with west and southwest edges a \emph{10-tile}, and a rhombus with south and southwest edges a \emph{21-tile}. Choose a tiling $\mathcal{T}$ with the 20-tiles, 21-tiles, and 10-tiles on $\Gamma(X)$. 

\begin{defn}
A \emph{north-strip} is a connected strip composed of adjacent 20- and 10-tiles. A \emph{west-strip} is a connected strip composed of adjacent 20- and 21-tiles. The 20-tile and the 21-tile can contain a \emph{left-arrow}, while the 20-tile and the 10-tile can contain an \emph{up-arrow}. See Figure \ref{all_strips}.
\end{defn}

\begin{defn}
A tile is \emph{pointed at} by an arrow if it is in the same west-strip to the left of a left-arrow or if it is in the same north-strip above an up-arrow. Conversely, a tile is \emph{free} if it is not pointed at by any arrow (a tile containing an arrow is considered free).
\end{defn}

\begin{figure}[!ht]
%\begin{minipage}{0.65\linewidth}
  \centerline{\includegraphics[width=\linewidth]{RAT_strips_tiles.pdf}}
 \centering
  \caption{(a.) 20-, 21-, and 10-tiles; (b.) left-arrows and up-arrows and the tiles they point to; (c.) all west-strips and north-strips in $\Gamma(X)$ for $X=122001200$.}\label{all_strips}
% \end{minipage}
\noindent
\end{figure}



\begin{defn}\label{def:RAT}
A \emph{rhombic alternative tableau} of type $X\in\TASEP(n,r)$ is a rhombic diagram $\Gamma(X)$ with some tiling $\mathcal{T}$ that is filled with up-arrows and left-arrows such that:
\begin{enumerate}
\item[(i.)] a tile must be empty if it is pointed at by an up-arrow or a left-arrow, and
\item[(ii.)] a free tile must contain an up-arrow or a left-arrow.
\end{enumerate}
\end{defn}

\begin{defn}
The \emph{weight} of a RAT $R$ of size $(n,r)$ with $\ufree(R)$ north-strips free of up-arrows and $\lfree(R)$ west-strips free of left-arrows is $\wt(R) = \alpha^{n-r-\ufree(R)}\beta^{n-r-\lfree(R)}$.
\end{defn}

For $X\in\TASEP(n,r)$, we define $\RAT_{\mathcal{T}}(X)$ to be the set of fillings of $\Gamma(X)$ with some fixed tiling $\mathcal{T}$. Because it turns out $\sum_{R\in\RAT_{\mathcal{T}}(X)}\wt(R)$ is independent of the tiling (see Prop 2.8 of \cite{MV16}), we define $\weight(X)=\sum_{R\in\RAT_{\mathcal{T}}(X)}\wt(R)$ for arbitrary tiling $\mathcal{T}$.

%The following lemma addresses equivalence of tilings. It is well known that any two tilings can be obtained from one another via some series of flips, where a flip is a switch of configurations in Figure \ref{flip_bij}. A \emph{filling-preserving flip} is a weight-preserving map from the filling of a tiling $\mathcal{T}$ to a filling of a tiling $\mathcal{T}'$, where $\mathcal{T}$ and $\mathcal{T}'$ differ by a single flip, with all other tiles and their contents identical in the two tilings. Figure \ref{flip_bij} shows the four possible cases of a filling-preserving flip. A full proof of this property of rhombic tableaux is given in Proposition 2.8 of \cite{MV15}.

%\begin{figure}[!ht]
%  \centerline{\includegraphics[height=1in]{../ToricRat/TRATsource/Tfig25.jpeg}}
%\centering
% \caption{A \emph{flip} is the switch from one hexagonal configuration to another in a tiling, all four cases of which are shown.}% In this figure we see the four cases of possible fillings of a hexagonal configuration of tiles in a tiling. The dashed blue lines through the west-strips (resp.~red lines through the north strips) represent the presence of left-arrows (resp.~up-arrows) in those strips.}
% \label{flip_bij}
%\end{figure}


%\begin{lem}\label{lem:flips}
%Let $\mathcal{T}$ and $\mathcal{T}'$ be arbitrary tilings on $\Gamma(X)$. Then
%\[ \sum_{R\in\RAT_{\mathcal{T}}(X)}\wt(R)=\sum_{R\in\RAT_{\mathcal{T}'}(X)}\wt(R).
%\]
%\end{lem}
%
%As a consequence of Lemma \ref{lem:flips}, we are able to define the weight of a state $X$.
%\begin{defn}
%Fix any tiling $\mathcal{T}$ on $\Gamma(X)$. Define 
%\[\weight(X) = \sum_{R\in\RAT_{\mathcal{T}}(X)}\wt(R).\]
%\end{defn}

The following result is Theorem {3.1} in \cite{MV16}, and is proved with the canonical Matrix Ansatz technique.

\begin{thm}[\cite{MV16}]\label{RAT_thm}
Let $X\in\TASEP(n,r)$ be a state of the 2-TASEP with open boundary conditions. The stationary probability of $X$ is $\Pr(X)=\frac{1}{\mathcal{Z}_{n,r}}\weight(X)$,
where $\mathcal{Z}_{n,r}=\sum_{X\in\TASEP(n,r)}\weight(X)$.
\end{thm}


\section{Cylindric rhombic tableaux}\label{sec:CRT}

We introduce tableaux that we call \emph{cylindric rhombic tableaux} (CRT), related to the RAT, for an analogous formula for the stationary probabilities of the 2-TASEP with periodic boundary conditions. 


\begin{figure}[!ht]
%\begin{minipage}{0.65\linewidth}
  \centerline{\includegraphics[width=0.7\linewidth]{H_X.pdf}}
 \centering
 \caption{For $X=1120200120$, (a.) $X$-strip and (b.) cylindric diagram $\mathcal{H}(X)$.}\label{fig:H_X}
\noindent
\end{figure}


Let $X=X_1\ldots X_n\in\TASEP(k,r,\ell)$ with $n:=k+r+\ell$. %For the rest of this section, we choose a cyclic shift of $X$ such that $X_1=1$. 
Define an \emph{$X$-strip} to be a connected strip of 20-tiles and 21-tiles, which is built from right to left by reading $X$ from left to right and appending a 20-tile for every 0 and a 21-tile for every 1. %Define the path $P(X)$ to be a lattice path consisting of south, west, and southwest steps which is constructed from NE to SW by reading $X$ from left to right and appending a south step for every 2, a west step for every 0, and a southwest step for every 1. 
We define the \emph{cylindric diagram} $\mathcal{H}(X)$ to be a stack of $k$ $X$-strips on top of each other with $P(X)$ as in \cref{def:P(X)} superimposed (see \cref{fig:H_X}).

Identify the vertical edges on the left boundary of $\mathcal{H}(X)$ with the corresponding vertical edges belonging to the same west-strip on the right boundary, making $\mathcal{H}(X)$ a cylinder. We carry over all definitions of tiles, strips, and arrows from the RAT. Set each west-strip to start at the tile directly west of $P(X)$ and end at the tile directly east of $P(X)$. We break symmetry with north-strips, however, by setting each north-strip (which are by construction composed of strips of $k$ 20-tiles) to run from bottom to top of $\mathcal{H}(X)$, disregarding the position of $P(X)$.

%\begin{remark}
%It is certainly possible to define a cylindric diagram of type $X$ for $X_1\neq 1$. However, it suffices to limit ourselves to setting $X_1=1$ to simplify our presentation, with one caveat: we must take extra care in our proofs for the cases where $X=1Y2$ or $X=10Y$.
%\end{remark}


\begin{defn}
A CRT of type $X$ is a filling of the tiles of $\mathcal{H}(X)$ with left-arrows and up-arrows according to same rules as the RAT in Definition \ref{def:RAT}. We denote the set of CRT by $\CRT(X)$.
%\begin{enumerate}
%\item[i.] A tile pointed to by an arrow in the same strip must be empty.
%\item[ii.] An empty tile must be pointed to by some up-arrow or some left-arrow.
%\end{enumerate}
\end{defn}

\begin{figure}[!ht]
  \centerline{\includegraphics[width=1.03\linewidth]{CRT_q0_examples.pdf}}
\centering
 \caption{The set $\CRT(X)$ for $X=1220120102$.}\label{fig:fillings}
 \end{figure}

Our main result is the following, illustrated by Figure \ref{fig:fillings}.

\begin{thm}\label{thm:CRT}
Let $X\in\TASEP(k,r,\ell)$ be a state of the 2-TASEP with periodic boundary conditions, with $n:=k+r+\ell$. Then 
$\Pr(X) =\frac{1}{{n \choose k}{n \choose \ell}} |\CRT(X)|$.
\end{thm}

The proof for Theorem \ref{thm:CRT} is a straightforward Matrix Ansatz argument nearly identical to that for Theorem 3.1 in \cite{MV16}. We proceed directly to show $\CRT(X)$ is in bijection with $\MLQ(X)$.

\subsection{Bijections from multiline queues to CRT}\label{sec:bij}

Our bijection is based on a technical condition on the weight vector $(w_1,\ldots,w_{\ell})$ associated to an MLQ via the ball drop of Algorithm \ref{alg:drop}.

%For an MLQ of size $(k,r,\ell)$ we modify the ball-drop algorithm to define weights on its 0-balls as follows.

%To show the ball lift is well-defined, i.e. that there are always $w_i$ unmarked vacancies to the left of $x_i$ with no 1-ball in between, we need a technical condition, the proof of which is obtained directly by following the ball-drop algorithm.

\begin{lem}\label{lem:technical}
Let $X=X_1\ldots X_n\in\TASEP(k,r,\ell)$ with
$X_{x_1}=\cdots=X_{x_{\ell}}=0$. For $i\in[1,\ell]$, define $b_i =
\max\{j<x_i\ :\ X_j=1\}$ to be the locations of the nearest 1's to the
left of each $0$ in $X$. Let $(w_1,\ldots,w_{\ell})$ be the weight vector of $M\in\MLQ(X)$. The conditions on $(w_1,\ldots,w_{\ell})$ are:
\[
 \sum_{j:\ b_i <x_j \leq x_i} w_j+1 \leq x_i-b_i.
\]
for each $i$. In other words, there are enough vacancies left of each $x_i$ so that it can have weight $w_i$. 
\end{lem}

We call a list $(w_1,\ldots,w_{\ell})$ that satisfies the condition in Lemma \ref{lem:technical} an \emph{$X$-consistent list}. Lemma \ref{uniqueness} states that each $X$-consistent list corresponds uniquely to an MLQ in $\MLQ(X)$. By the same principles, it turns out that an $X$-consistent list also corresponds uniquely to a CRT in $\CRT(X)$.

\begin{lem}\label{lem:CRT}
Let $R\in\CRT(X)$ with $a_i$ the number of left-arrows in the $i$'th north-strip of $R$ from right to left. Then $(a_1,\ldots,a_{\ell})$ is an $X$-consistent list. Moreover, for any $X$-consistent list $(a_1,\ldots,a_{\ell})$, there exists a unique filling of $\CRT(X)$ with this property.
\end{lem}

The second statement of Lemma \ref{lem:CRT} is proved by construction: when filling the north-strips from right to left, the left-arrows must be placed in consecutive free tiles from bottom to top (see Prop 3.1 in \cite{M15}). 

\begin{defn}
Let $M\in\MLQ(X)$ have weight vector $(w_1,\ldots,w_{\ell})$. Construct $\Psi_{\CRT}(M)\in\CRT(X)$ so the $i$'th north-strip of $\Psi_{\CRT}(M)$ from right to left has $w_i$ left-arrows for each $i$.
\end{defn}

%%Let $R$ be a CRT of type $X=X_1\ldots X_n\in \TASEP(k,r,\ell)$ for $n:=k+r+\ell$ with canonical tiling $\mathcal{T}_X$. Assume $X_1=1$.
%Let $R$ be a CRT of type $X\in \TASEP(k,r,\ell)$ with canonical tiling $\mathcal{T}_X$. Note that any north-strip that does not have an up-arrow below a 10-tile will necessarily acquire an up-arrow at the 10-tile. Thus there can be no arrows in north-strips above any 10-tiles. In particular, this implies $R$ has all of the left-arrows and up-arrows contained in its $\ell$ $X$-strips above the path $P(X)$ in $\mathcal{H}(X)$. %We order the $\ell$ $X$-strips from right to left, which corresponds to locations of the 0's in $X$ from left to right. 

\begin{figure}[!ht]
  \centerline{\includegraphics[width=0.9\linewidth]{MLQ_CRT_bijection_.pdf}}
\centering
 \caption{The weights of the MLQ $M$ are $(1, 1, 0, 0,2)$, which is also the number of left-arrows in each north-strip from right to left in the CRT $\Psi_{\CRT}(M)$.}\label{bijection_example}
 \end{figure}

See Figure \ref{bijection_example} for an example of the map $\Psi_{\CRT}$. It is similarly easy to define the inverse of $\Psi_{\CRT}$ by Lemmas \ref{lem:CRT} and \ref{uniqueness} and reversing Algorithm \ref{alg:drop}, thus establishing that $\Psi_{\CRT}:\MLQ(X)\rightarrow\CRT(X)$ is indeed a bijection.


%\begin{lem}
% Suppose the north-strips of $R$ are at locations $x_1<\cdots<x_{\ell}$, with strip $x_i$ containing $a_i$ left-arrows for each $i$. Then $(a_1,\ldots,a_{\ell})$ is an $X$-consistent list, and thus there exists a unique MLQ of type $X$ with weights $(a_1,\ldots,a_{\ell})$.
%\end{lem}
%
%Recall that a free 20-tile is one that does not have a left-arrow to its right in the same west-strip or an up-arrow below in the same north-strip.
%
%\begin{proof}
%Our proof will show that there is a natural map between the number of left-arrows in north-strip $x_i$ in $R$ and the weight $w_i$ of the 0-ball at location $x_i$ in $\zeta(R)$. %Recall that  $w_i$ is the number of unmarked vacancies marked by the drop of a top row ball to a 0-ball at location $x_i$ in $mlq(R)$.
%
%If a north-strip at location $x_i$ contains $a_i$ left-arrows, then it must have at least $a_i$ free 20-tiles below its first 10-tile. Let $b_i$ be the index of the diagonal strip containing the nearest 10-tile in strip $x_i$. Since diagonal strips cannot intersect, $b_i$ is the index of the nearest diagonal edge to the right of $x_i$ in $P(X)$. In other words, $b_i = \max\{y\ :\ y<x_i,\ X_y=1\}$.\footnote{We note here that this definition of $b_i$ is precisely the location of the first 10-tile only when the particular tiling $\mathcal{T}_X$ is used. That is because the order of the 2- and 1-edges in $P(X)$ matches the order of the 20- and 10-tiles in the $x_i$ north-strip.} Then we have the following conditions on the $a_i$'s.
%For each $i$,
%\[
% \sum_{j:\ a_i <x_j \leq x_i} a_j+1 \leq x_i-b_i.
%\]
%Observe that the conditions on the list $(a_1,\ldots,a_{\ell})$ make it an $X$-consistent list. Thus by Lemma \ref{uniqueness}, there exists a unique MLQ $M(R)$ of type $X$ with weights $(a_1,\ldots,a_{\ell})$, obtained by performing ball lifts sequentially for $x_1,\ldots,x_{\ell}$. This completes our proof.
%\end{proof}
%
%
%
%
%
%
%
%\subsubsection{Nested path map from MLQ to CRT}\label{sec_paths}
\begin{remark}
Using nested lattice paths, one obtains a bijection from MLQs to CRT that is different from $\Psi_{\CRT}$. A multiline queue naturally has an interpretation in terms of weighted lattice paths, where each row of the MLQ is mapped to a path on a triangular lattice. At $q=0$, fillings of RAT are in bijection with weighted nested lattice paths \cite{M16}, and indeed one can show this property is preserved in the case of the CRT using the canonical lattice path bijection of Catalan paths and Catalan tableaux (see \cite{M15,V07}).
\end{remark}

%\begin{figure}[!ht]
%  \centerline{\includegraphics[height=3in]{../ToricRat/TRATsource/Tfig15.jpeg}}
%\centering
% \caption{The map from a MLQ to a nested pair of lattice paths, which then maps to a CRT via the canonical lattice path bijection. The second map is from the MLQ $M$ to the CRT $\Psi_{\CRT}(M)$. Notice that the two resulting CRT are not the same.}\label{path_to_CRT}
% \end{figure}
%
%
%\begin{defn}
%A \emph{2-TASEP compatible} pair of lattice paths is a pair of paths composed of south, west, and southwest edges that coincide at their endpoints, such that the space between the two paths can be completely tiled by squares.
%\end{defn}
%
%We construct a pair of lattice paths from an MLQ as follows: the first path, $P_1$, is obtained by reading the bottom row of the MLQ and drawing a south edge for every vacancy, a west edge for every 0-ball, and a southwest edge for every 1-ball. The second path, $P_2$, is obtained by reading the top row of the MLQ and drawing a southwest edge for a vacancy directly above a bottom row 1-ball, a south edge for a vacancy otherwise, and a west edge for a ball.
%
%%\begin{proof}
%%We consider an interval of vacancies and 0-balls between any two 1-balls at locations $a$ and $b$ in the bottom row of $M$. At each location $a<j\leq b$, there must be at least as many top row balls as there are bottom row 0-balls between locations $a$ and $j$; otherwise, there will be an unoccupied 0-ball, which is a contradiction. Moreover, between $a$ and $b$, there must be exactly the same number of top row balls as there are bottom row 0-balls. The latter implies $P_2$ and $P_1$ coincide at every diagonal edge. Hence for each $a<j\leq b$, $P_1$ takes at least as many steps south as does $P_2$ between edges $a$ and $j$, and thus $P_2$ lies weakly above $P_1$.
%%\end{proof}
%
%%To establish our bijection, we make two observations which are straightforward to prove.
%\begin{lem} 
%\begin{enumerate}
%\item[(i.)]$P_2$ is weakly above $P_1$, and the two are 2-TASEP compatible paths.
%\item[(ii.)]2-TASEP compatible paths of type $X$ are in bijection with an $X$-consistent list.
%\end{enumerate}
%\end{lem}
%
%It is easy to see that a pair of 2-TASEP compatible lattice paths corresponds to a unique MLQ and vice versa. In the following algorithm, given a CRT with path $P(X)$, we construct a path $P_2$ which is weakly above $P(X)$.
%%A path weakly above the path $P(X)$ for a CRT of shape $\mathcal{H}(X)$ is constructed as follows.
%
%\begin{alg}\label{alg:toPath}
%Suppose $X$ has its type 1 particles at locations $b_1=1,\ldots,b_r$, and let $R\in\CRT(X)$. We construct the edges of $P_2$ from right to left by reading the north-strips of $R$. Set $P_2$ to have its diagonal edges at locations $b_1,\ldots,b_r$. For each north-strip of $R$ from right to left, the path $P_2$ takes $j$ vertical steps down and one horizontal step left, where $j$ is the total number of left-arrows in the 20-tiles of that 0-strip. Once $P_2$ has reached the left border of $\mathcal{H}(X)$, it takes vertical steps down until it reaches the left endpoint of $P(X)$. See Figure \ref{CRT_to_path} for an example.
%\end{alg}

%\begin{figure}[!ht]
%  \centerline{\includegraphics[height=1in]{../ToricRat/TRATsource/Tfig14.jpeg}}
%\centering
% \caption{The canonical map from a CRT to a pair of nested lattice paths.}\label{CRT_to_path}
% \end{figure}


%The reverse map to Algorithm \ref{alg:toPath} is as follows: begin with a pair of 2-ASEP compatible nested paths $P(X)$ and $P_2$, assuming $X$ begins with a type 1 particle. Starting from right to left, let each 0-strip of the filling of $\mathcal{H}(X)$ contain $j$ left-arrows in its 20-boxes, followed by an up-arrow, where $j$ is the number of down-steps in $P_2$ preceding the horizontal step corresponding to the given 0-strip. There is a unique way of filling this 0-strip in such a way: the left-arrows must be in the lowest tiles possible, immediately followed by the up-arrow. See an example in Figure \ref{path_to_CRT}.


\section{Inhomogeneous 2-TASEP}\label{sec:inhomog}
\setlength{\abovedisplayshortskip}{-2pt}
\setlength{\belowdisplayshortskip}{-2pt} 
We define the transitions on the inhomogeneous 2-TASEP with periodic boundary conditions as follows: for arbitrary words $X,Y\in\{2,1,0\}$, 
\[X20Y \mathrel{\mathop{\rightarrow}^{\mathrm{1}}} X02Y,\qquad\qquad X21Y \mathrel{\mathop{\rightarrow}^{\mathrm{x_2}}} X12Y,\qquad\qquad
X10Y \mathrel{\mathop{\rightarrow}^{\mathrm{x_1}}} X01Y
\]
where $0 \leq x_2,x_1 \leq 1$ are parameters describing the hopping
rates. When $x_2=x_1=1$, we recover the usual 2-TASEP. When
$x_1=1$, we recover the inhomogeneous 2-TASEP in \cite{AL14} (our solution specializes to the latter after some manipulation). 

%Define $\weight(X)$ to be the unnormalized steady state probability of state $X$. We will show it is a polynomial in $t,d,e$ with coefficients in $\mathbb{Z}^+$ by expressing it as a sum over the weighted tableaux.
We introduce a weight on the CRT, which is a monomial in $x_2$, $x_1$ to give a formula for the probabilities of the inhomogeneous 2-TASEP with periodic boundary conditions.%, and is denoted by $\wt(R)$ for $R\in\CRT_{\mathcal{T}}(X)$ for some tiling $\mathcal{T}$, and set $\weight(X)=\sum_{R\in\CRT_{\mathcal{T}}(X)}\wt(R)$. 


\begin{defn}
Let $X\in\TASEP(k,r,\ell)$ and $R\in\CRT(X)$. The \emph{weight} $\wt(R)$ is defined as 
\[
\wt(R)=x_2^{k-\Left(R)}x_1^{\ell-\Up(R)},\] 
where $\Left(R)$ is the number of 20-tiles in $R$ containing a left-arrow and $\Up(R)$ is the number of 20-tiles in $R$ containing an up-arrow. Set $\weight(X)=\sum_{R\in\CRT(X)}\wt(R)$.
\end{defn}

\begin{example}
The CRTs in Figure \ref{fig:fillings} have respective weights $x_2x_1^3$, $x_2^2x_1^2$, $x_2^2x_1^2$, $x_2^3x_1$, $x_2^4x_1$.
\end{example}

A straightforward Matrix Ansatz argument gives the following result.

\begin{thm}\label{thm:inhomog}
Let $X\in\TASEP(k,r,\ell)$ be a state of the inhomogeneous 2-TASEP with periodic boundary conditions. Then $\Pr(X)=\frac{1}{\mathcal{Z}_{k,r,\ell}}\weight(X)$, where $\mathcal{Z}_{k,r,\ell}=\sum_{X\in\TASEP(k,r,\ell)}\weight(X)$.
\end{thm}


Using $\Psi_{\CRT}$, one can define statistics $\umv$ and $\rest$ on MLQs that correspond to $\Left$ and $\Up$ respectively on CRT, the former being a natural statistic, but the latter slightly cumbersome.

\begin{defn}
For $M\in\MLQ$, let $\umv$ denote the number of unmarked vacancies in the bottom row of $M$ after Algorithm \ref{alg:drop}. We call a \emph{restricted 0-ball} a 0-ball such that at the time it is hit during Algorithm \ref{alg:drop}, between it and the nearest 1-ball to its left, there are zero unmarked vacancies. Let $\rest(M)$ denote the number of such restricted 0-balls.
\end{defn}

\begin{example} In Figure \ref{fig:MLQ}, the 2nd and 5th 0-balls from the left are restricted, since after they are hit, there are no unmarked vacancies to their left with no 1-ball in between. At termination there are no unmarked vacancies, so $\umv(M)=0$ and $\rest(M)=2$.
\end{example}

\begin{lem}\label{lem:mv}
For $M\in\MLQ$, $\umv(M)=\Left(\Psi_{\CRT}(M))$ and $\rest(M)=\Up(\Psi_{\CRT}(M))$.%Thus $\weight(X)=\sum_{M\in\MLQ(X)}x_2^{\mv(M)}$ at $x_1=1$.
\end{lem}

Thus by applying Lemma \ref{lem:mv} to Theorem \ref{thm:inhomog}, we obtain the following corollary, which is equivalent to the solution of \cite{AL14} for the inhomogeneous 2-TASEP at $x_1=1$.

\begin{cor}[\cite{AL14}]\label{thm:AL}
Let $X\in\TASEP(k,r,\ell)$ be a state of the inhomogeneous 2-TASEP with periodic boundary conditions. Then $\Pr(X)$ is proportional to 
$\sum_{M\in\MLQ(X)}x_2^{-\umv(M)}$.
\end{cor}



\subsection{Inhomogeneous 2-TASEP with open boundaries and acyclic multiline queues}\label{sec:AMLQ}

A nice consequence of our CRT-MLQ bijection is that we can apply the same methods to obtain analogous results for the inhomogeneous 2-TASEP with open boundaries. In this generalization, $\alpha$ and $\beta$ dictate the rates of entry and exit of class 2 particles at the left and right boundaries of the lattice, while $1$, $x_2$, $x_1$ dictate the rates at which the respective transitions $20\rightarrow 02$, $21\rightarrow 12$, and $10\rightarrow 01$ occur.

In the expected way, to obtain probabilities for the inhomogeneous process, we modify the weight of a RAT by counting its tiles of different types that contain arrows.
\begin{defn}
For $R\in\RAT(n,r)$, set 
\[
\wt_M(R)=x_2^{-\Left(R)}x_1^{-\Up(R)}\alpha^{n-r-\ufree(R)}\beta^{n-r-\lfree(R)}\] 
where $\Left(R)$ and $\Up(R)$ are statistics carried over from the CRT.
\end{defn}
Using a Matrix Ansatz argument, we obtain that the stationary probability of a state $X\in\TASEP(n,r)$ of the inhomogeneous 2-TASEP is proportional to $\sum_{R\in\RAT_{\mathcal{T}}(X)}\wt_M(R)$. 

Observe that we can obtain a simple bijection $c:\CRT(1X1)\rightarrow
\RAT_{\mathcal{T}_X}(X)$ by simply taking the restriction of
$T\in\CRT(1X1)$ to the region corresponding to $\Gamma(X)$ above the path
$P(1X1)$ and appending the necessary 10-tiles and up-arrows in a
deterministic way, as in Figure \ref{amlq_bij}. (Here $\mathcal{T}_X$ the
restriction of the canonical tiling of $\mathcal{H}(X)$ to $\Gamma(X)$.)
Consequently, in the next section we use $\Psi_{\CRT}$ to introduce a new
object, the \emph{acyclic multiline queue}, which is derived from the usual MLQ, and is in bijection with the RAT. %Furthermore, we generalize the 2-TASEP with open boundaries to an inhomogeneous process similar to the inhomogeneous 2-TASEP with periodic boundary conditions of Section \ref{sec:inhomog}, and likewise generalize the RAT and the AMLQ to solve the inhomogeneous model. 

\subsection{Acyclic multiline queues}\label{sec_amlq}

%The connection between rhombic tableaux and multiline queues naturally extends to the open boundary case of the 2-TASEP. Following the idea of the CRT-MLQ bijection of Section \ref{sec:bij}, we define \emph{acyclic multiline queues}, which we also call AMLQs.

\begin{defn}
 An \emph{acyclic MLQ} (AMLQ) of type $X\in\TASEP(n,r)$ is an MLQ of size $(k,r,\ell)$ for any $0\leq k\leq n-r$ that is \emph{not} on a cylinder, with the following restriction: for each $1\leq i\leq \ell$, the $i$'th top row ball (from the left) has at least $i$ bottom row balls weakly to its right. We denote the set of AMLQs of type $X$ by $\AMLQ(X)$, and by $\AMLQ(n,r)$ the set of acyclic MLQs of size $(n,r)$.
% \[\AMLQ(n,r)=\bigcup_{X\in\TASEP(n,r)}\AMLQ(X).\]
\end{defn}

In other words, an AMLQ is an MLQ configuration in which every top row ball occupies a bottom row ball to its right without wrapping. See Figure \ref{not_amlq} for an example. %This is due to the following lemmas, which are illustrated by Figure \ref{amlq_bij}.

\begin{figure}[!ht]
  \centerline{\includegraphics[width=\linewidth]{MLQ_111.pdf}}
\centering
 \caption{The acyclic MLQs of size $(3,1)$ are shown. The final marked configuration is not an AMLQ since the top row ball must wrap around to occupy the bottom row.}\label{not_amlq}
 \end{figure}
 
Let $A\in\AMLQ(X)$. Construct $e(A)$ by appending a column containing a vacancy in the top row and a 1-ball in the bottom row to the left and right of $A$. The leftmost column of $e(A)$ trivially contains a 1-ball, and since every top row ball in $A$ occupies some ball weakly to its right without wrapping around, the bottom row ball at the rightmost location of the $e(A)$ must be a 1-ball; thus $e(A)\in\MLQ(1X1)$ and is moreover a bijection. Now set $\Psi_{\RAT}=c\circ \Psi_{\CRT} \circ e$. See Figure \ref{amlq_bij}.

%Let $A$ be an AMLQ. %Define $\urest(A)$ to be the number of unrestricted 0-balls in $A$, $\mv(A)$ the number of marked vacancies, 
%\end{defn}

\begin{defn}\label{wt_AMLQ}
The \emph{weight} of an AMLQ $A\in AMLQ(n,r)$ is 
\[\wt_M(A) = \alpha^{n-r-\ufree(A)}\beta^{n-r-\lfree(A)}x_2^{\lfree(A)-\umv(A)}x_1^{\ufree(A)-\rest(A)}\]
where $\ufree(A)$ is the number of restricted 0-balls to the left of the leftmost 1-ball in $A$, and $\lfree(A)$ is the number of unmarked vacancies to the right of the rightmost 1-ball.
\end{defn}

\begin{lem}\label{lem:amlq}
The maps $\tilde\Psi_{\CRT}:\AMLQ(X)\rightarrow \RAT(X)$ is a weight-preserving bijection with the following properties: (i.) $\ufree(A)=\ufree(\Psi_{\RAT}(A))$, (ii.) $\lfree(A)=\lfree(\Psi_{\RAT}(A))$, (iii.) $\umv(A)=\Left(\Psi_{\RAT}(A))$, (iv.) $\rest(A)=\Up(\Psi_{\RAT}(A))$, and finally (v.) $\wt_M(A)=\wt_m(\Psi_{\RAT}(A))$.
\end{lem}

%\begin{proof}
%Let $A\in\AMLQ(X)$. Let $A_M$ be an MLQ obtained by appending a column to the left and right of $A$, containing a vacancy in the top row and a 1-ball in the bottom row. The leftmost column of $A_M$ trivially contains a 1-ball, and since every top row ball in $A$ occupies some ball weakly to its right without wrapping around, the bottom row ball at the rightmost location of the $A_M$ must remain unoccupied; thus $A_M\in\MLQ(1X1)$. On the other hand, let $A_M\in\MLQ(1X1)$ be cyclically shifted so that its type read from left to right is $1X1$. The right-most 1-ball must remain unoccupied, so all top row balls must occupy bottom row balls without wrapping around. By chopping off the leftmost and rightmost columns of $A_M$, we get back $A\in\AMLQ(X)$.    
%\end{proof}

%We fix some definitions to simplify notation.
% \begin{defn}

Combining Lemma \ref{lem:amlq} and the usual Matrix Ansatz proof, we obtain our final result.

\begin{thm}\label{amlq_main}
 Let $X$ be a state of the inhomogeneous 2-TASEP of size $(n,r)$. Then 
 $\Pr(X)$ is proportional to 
 \[
 \sum_{A \in \AMLQ(X)} \wt_M(A)=\sum_{R \in \RAT_{\mathcal{T}}(X)} \wt_M(R).
 \]
\end{thm}

%In Figure \ref{not_amlq}, the $\alpha,\beta$ weights of all AMLQs of size $(3,1)$ are given (after setting the other variables to equal 1).

%The proof of our theorem is through a weight-preserving bijection of acyclic MLQs with RAT. Let us denote the set of fillings of $\Gamma(X)$ with tiling $\mathcal{T}$ by $\RAT_{\mathcal{T}}(X)$. 

\begin{figure}[!ht]
  \centerline{\includegraphics[width=\linewidth]{AMLQ_RAT_bijection.pdf}}
\centering
 \caption{Let $X=2200120200$. We have: $A\in\AMLQ(X) \longleftrightarrow e(A)\in\MLQ(1X1) \longleftrightarrow \Psi_{\CRT}(e(A))\in\CRT_{\mathcal{T}_X}(1X1) \longleftrightarrow \Psi_{\RAT}(A)=c(\Psi_{\CRT}(e(A)))\in\RAT(X)$. The highlighted columns in $e(A)$ correspond to the highlighted diagonal strips in $\Psi_{\CRT}(e(A))$.}\label{amlq_bij}
 \end{figure}
%\begin{proof}
%Let $A\in\AMLQ(X)$ for $X\in\TASEP(n,r)$, and let $X'=1X1\in \TASEP(n+2,r+2)$. Let $A_M\in\MLQ(1X1)$ be the MLQ obtained by appending a column containing a 1-ball in the bottom row to the left and right of $A$. Let $T=\gamma(A_M)$ be the CRT obtained by applying the ball drop algorithm to $A_M$. Now apply flips to the tiling of $T$ until the rightmost (resp.~leftmost) diagonal strip consists of a row of $\ell$ adjacent 10-tiles (resp.~$k$ adjacent 21-tiles), obtaining tiling $\mathcal{T}$ in which the leftmost and rightmost diagonal strips are aligned with the north and west boundaries of $T$.
%
%We define $T_U$ to be the rhombic tableau obtained by taking the region of $T$ northwest of $P(X)$. $T_U$ satisfies the rules of Definition \ref{def:RAT}, and so $T_U\in\RAT_\mathcal{T}(1X1)$. We claim that the region of $T$ southeast of the path $P(X)$ contains no arrows. Suppose a north-strip of $T$ has its top-most tile, which is a 10-tile contained in the rightmost diagonal strip, free. Then that 10-tile will necessarily contain an up-arrow. Similarly, suppose a west-strip of $T$ has its left-most tile, which is a 21-tile contained in the leftmost diagonal strip, free. Then that 21-tile will necessarily contain a left-arrow. Thus every arrow in $T$ is contained in $T_U$, and so a CRT $T\in \CRT_{\mathcal{T}_X}(1X1)$ can be uniquely recreated from a rhombic tableau $T_U\in \RAT(1X1)$. Consequently, this map is a bijection.
%
%Now define $R$ to be the tableau obtained by chopping off the rightmost and leftmost diagonal strips of $T_U$: recall that with the tiling $\mathcal{T}$, these strips are bordering the northwest boundary of $T_U$, so chopping them off results in a proper rhombic diagram of type $X$ with a filling with up-arrows and left-arrows that still satisfy Definition \ref{def:RAT}; thus $R\in\RAT_{\mathcal{T}}(X)$. Moreover, $T_U$ can be recreated from $R$ by re-attaching the external diagonal strips and placing a up-arrow in the topmost tile of every north-strip that is free of an up-arrow, and a left-arrow in the leftmost tile of every west-strip that is free of a left-arrow. We call $\gamma(A)=R$. Thus 
%\[
%\gamma: \AMLQ(X) \rightarrow \RAT_\mathcal{T}(X)
%\] 
%is a bijection. 

%Define $\ufree(R)$ to be the number of north-strips that are free of up-arrows and $\lfree(R)$ to be the number of west-strips that are free of left-arrows. Then 
%\begin{align*}
%\wt(R)&=\alpha^k\beta^{\ell}\alpha^{\#\ \mbox{up-arrows}}\beta^{\#\ \mbox{left-arrows}}\\
%&=\alpha^{n-r-\ufree(R)}\beta^{n-r-\lfree(R)}.
%\end{align*}
%
%By our construction, $\ufree(R)$ (resp.~$\lfree(R)$) is the number of tiles containing an up-arrow in the rightmost diagonal strip (resp.~left-arrow in the leftmost diagonal strip) of $R$. By following the ball drop algorithm, we see that an up-arrow in the rightmost diagonal strip precisely corresponds to the unmarked vacancies left of the leftmost 1-ball in $A$, and a left-arrow in the leftmost diagonal strip precisely corresponds to the restricted 0-balls right of the rightmost 1-ball in $A$. Thus $\ufree(R)=\ufree(A)$ and $\lfree(R)=\lfree(A)$ from Definition \ref{wt_AMLQ}.
%
%For $X\in\TASEP(n,r)$, let $A\in\AMLQ(X)$ and $R=\gamma(A)\in\RAT(X)$. By the above $\wt(R)=\wt(A)$, and so with Theorem \ref{RAT_thm}, we obtain
%\[\Pr(X)=\frac{1}{\mathcal{Z}_{n,r}}\sum_{R\in\RAT_{\mathcal{T}}(X)} \wt(R) = \frac{1}{\mathcal{Z}_{n,r}}\sum_{A\in\AMLQ(X)} \wt(A),\]
%as desired, where $\mathcal{Z}_{n,r}=\sum_{A\in\AMLQ(n,r)}\wt(A)$.
%\end{proof}



%The \emph{inhomogeneous TASEP}, in which different classes of particles hop with different rates, is related to a study of a Markov chain on permutations of Lam and Williams, in which they conjectured that steady state probabilities are 

\section{Conclusion}

Although tableaux are limited to the 2-species context, their capacity for containing much structure makes the connection with TASEP more transparent than that of the MLQs. For instance the intuitive tableaux solution for the inhomogeneous process is superior to the MLQ solution; it is also much more natural to define a Markov chain that projects to the TASEP on the tableaux rather than on the MLQs. Moreover, in the open boundary case we get solutions for generalizations of the 2-TASEP with larger numbers of parameters (see \cite{MV16, CMW15}). Multiline queues, on the other hand, generalize well to a $k$-TASEP on a ring \cite{AM13}, but are thus far limited to the $q=0$ case. Thus by linking these two families of objects in the 2-TASEP context, we hope to both generalize the MLQs to obtain solutions for the $k$-ASEP with additional parameters, as well as to generalize the tableaux method for more species of particles.


%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography

%\begin{thebibliography}{99}
%
%\setlength{\parskip}{0.1cm}
%
%\bibitem{ALS09} Ayyer, A.~ and Leibowitz, J.~L.~ and Speer, E.~R. On the two species asymmetric exclusion process with semi-permeable boundaries, J. Stat. Phys. 135, no. 5-6, 1009--1037 (2009).
%
%\bibitem{AM13} Arita, C.~ and Mallick, K. Matrix product solution to an inhomogeneous multi-species TASEP, J. Phys. A: Math. Theor. 46 085002 (2013).
%
%\bibitem{AL14} Ayyer, A.~ and Linusson, S. An inhomogeneous multispecies TASEP on a ring, Advances in Applied Mathematics 57, 21-43 (2014).
%
%\bibitem{CMW15} Corteel, S.~ and Mandelshtam, O.~ and Williams, L. Combinatorics of the two-species ASEP and Koornwinder moments. Adv. Math. 321, 160?204 (2017).
%
%\bibitem{CW07} Corteel, S.~ and Williams, L. Tableaux combinatorics for the asymmetric exclusion process, Advances in Applied Mathematics, Volume 39, Issue 3, 293--310 (2007).
%
%\bibitem{CW11} Corteel, S.~ and Williams, L. Tableaux combinatorics for the asymmetric exclusion process and Askey-Wilson polynomials. Duke Math. J., 159: 385--415, (2011).
%
%\bibitem{FM09} Ferrari, P.~ and Martin, J. Stationary distributions of multi-type totally asymmetric exclusion
%processes, Ann.~Prob.~35, 807 (2009).
%
%\bibitem{LW12}  Lam, T.~ and Williams, L. A Markov chain on the symmetric group which is Schubert positive?,
%Experimental Mathematics, 21, no 2, 189 (2012).
%
%\bibitem{M15} Mandelshtam, O. A Determinantal Formula for Catalan Tableaux and TASEP Probabilities, J.~Combin.~Theory Ser.~A (2015).
%
%\bibitem{M16} Mandelshtam, O. Multi-Catalan Tableaux and the Two-Species TASEP, Annales de l'Institut Henri Poincar\'e D, Issue 3 (2016).
%
%%\bibitem{MV_FPSAC16} O.~Mandelshtam and X.~Viennot, Rhombic alternative tableaux and assembl\'ees of permutations, FPSAC2016 proceedings, arXiv: 1609.07638 [math.CO] (2016).
%
%\bibitem{MV16} Mandelshtam, O.~ and Viennot, X. Tableaux combinatorics for the two-species PASEP, J.~Combin.~Theory Ser.~A (to appear), (2016).
%
%\bibitem{V08} Viennot, X. Alternative tableaux, permutations and partially asymmetric exclusion process. slides available at: \url{http://sms.cam.ac.uk/media/1004} (2008). 
%
%\bibitem{V07} Viennot, X. Canopy of binary trees, Catalan tableaux and the asymmetric exclusion process, FPSAC 2007, Formal Power Series and Algebraic Combinatorics (2007).
%
%
%\end{thebibliography}


\end{document}


