\documentclass[finalversion]{FPSAC2024} \articlenumber{55} \newtheorem{thm}{Theorem} \newtheorem{prop}{Proposition} \newtheorem{lem}{Lemma} \newtheorem{cor}{Corollary} \theoremstyle{definition} \newtheorem{defn}{Definition} \newtheorem{ex}{Example} \newtheorem{remark}{Remark} \usepackage{tikz} \usetikzlibrary{arrows,calc,intersections,matrix,positioning,through} \usepackage{tikz-cd} \usepackage{ytableau} \usepgflibrary{shapes.geometric} \usetikzlibrary{shapes.geometric} \DeclareMathOperator{\DASEP}{DASEP} \DeclareMathOperator{\CBP}{CBP} \DeclareMathOperator{\ASEP}{ASEP} \DeclareMathOperator{\wt}{wt} \DeclareMathOperator{\DSSEP}{DSSEP} \DeclareMathOperator{\RRG}{RRG} \newcommand{\R}{\mathbb R} \newcommand{\Q}{\mathbb Q} \newcommand{\Z}{\mathbb Z} \renewcommand\labelenumi{(\theenumi)} %opening \title[The doubly asymmetric simple exclusion process]{The doubly asymmetric simple exclusion process, the colored Boolean process, and the restricted random growth model} \author{Yuhan Jiang\thanks{\href{yjiang@math.harvard.edu}{yjiang@math.harvard.edu}}\addressmark{1}} \address{\addressmark{1}Department of Mathematics, Harvard University, MA, USA} \received{\today} \abstract{The multispecies asymmetric simple exclusion process (mASEP) is a Markov chain in which particles of different species hop along a one-dimensional lattice. This paper studies the doubly asymmetric simple exclusion process $\DASEP(n,p,q)$ in which $q$ particles with species $1, \dots, p$ hop along a circular lattice with $n$ sites, but also the particles are allowed to spontaneously change from one species to another. In this paper, we introduce two related Markov chains called the colored Boolean process and the restricted random growth model, and we show that the DASEP lumps to the colored Boolean process, and the colored Boolean process lumps to the restricted random growth model. This allows us to generalize a theorem of David Ash on the relations between sums of steady state probabilities. We also give explicit formulas for the stationary distribution of $\DASEP(n,2,2)$.} \keywords{Asymmetric simple exclusion process, Markov chain} \usepackage[backend=bibtex]{biblatex} \addbibresource{dasep.bib} \begin{document} \maketitle \section{Introduction} The asymmetric simple exclusion process (ASEP) is a model from statistical mechanics introduced by Macdonald-Gibbs-Pipkin \cite{MGP} and Spitzer \cite{Spitzer1970InteractionOM}, which describes a Markov chain for particles hopping left or right along a one-dimensional lattice such that each site contains at most one particle. It can be used to model traffic flow or translation in protein synthesis. There are many variations of the ASEP: the lattice can have open, half open, closed, or periodic boundaries, and there can be reservoirs (see Liggett \cite{Liggett1975ErgodicTF,Liggett1985InteractingParticleSystems}). Particles can exhibit different species, and this variation is called the multispecies ASEP (mASEP). The asymmetry can be partial, so that particles are allowed to hop both left and right, but one side is $t$ times more probable, and this is called the partially asymmetric exclusion process (PASEP). The ASEP is closely related to a growth model defined by Kardar-Parizi-Zhang \cite{Kardar1986DynamicSO}, and various methods have been invented to study the ASEP, such as the matrix ansatz introduced by Derrida et al. in \cite{Derrida_1993}. The combinatorics of the ASEP was studied by many people, see \cite{Blythe2004DyckPM, Brak2012SimpleAE, Corteel2018FromMQ,FerrariMartin,Martin2020}. Let $\lambda = (\lambda_1, \dots, \lambda_n)$ be a partition with $\lambda_1 \geq \cdots \lambda_n \geq 0$, $|\lambda|$ be the sum of all parts of $\lambda$, and $m_i = m_i(\lambda): = \# \{j: \lambda_j = i\}$ be the number of parts of $\lambda$ that equal $i$. We also denote $\lambda$ by $1^{m_1}2^{m_2}\cdots$. Let $\ell(\lambda) = \sum_i m_i(\lambda)$ denote the length of $\lambda$. We write $S_n(\lambda)$ as the set of all weak compositions obtained from permuting the parts of $\lambda$. The mASEP can be thought of a Markov chain on $S_n(\lambda)$ \cite[Definition 1.2]{Corteel2018FromMQ}, or a coupling of multiple ASEP \cite{Martin2020}. The stationary distribution of the mASEP is related to Macdonald polynomials \cite{Corteel2018FromMQ} and multiline queues \cite{FerrariMartin}. Let $n$ be the number of sites on the lattice, $p$ be number of types of species, and $q$ be the number of particles. David Ash~\cite{ash2023introducing} defined the \emph{doubly asymmetric simple exclusion process} $\DASEP(n,p,q)$. The DASEP is a variant of the mASEP but also allows particles to spontaneously change species. This might be applied to biology models involving evolutions, or traffic flow problem that also tracks the gears of the cars. If $p=1$, $\DASEP(n,1,q)$ is the usual 1-species PASEP on a ring. \begin{defn}\cite{ash2023introducing} Let $n,p,q$ be positive integers with $n > q$, and let $u,t \in [0,1)$ be constants. The \emph{doubly asymmetric simple exclusion process} $\DASEP(n,p,q)$ is a Markov chain on the set of words (or weak compositions) of length $n$ in $0, \dots, p$ with $n-q$ zeros: $$\Gamma^{p,q}_n = \bigcup_{\substack{\lambda_1 \leq p, \\ \ell(\lambda) = q}} S_n(\lambda) = \bigcup_{m_1+\cdots+m_p=q} S_n(1^{m_1}\cdots p^{m_p}).$$ The transition probability $P(\mu,\nu)$ on two states $\mu$ and $\nu$ is as follows: \begin{itemize} \item If $\mu = A ij B$ and $\nu = A ji B$ (where $A$ and $B$ are words in $0, \dots, p$) with $i \neq j$, then $P(\mu,\nu) = \frac{t}{3n}$ if $i>j$ and $P(\mu,\nu) = \frac{1}{3n}$ if $j>i$. \item If $\mu = i A j$ and $\nu = j A i$ with $i \neq j$, then $P(\mu,\nu) = \frac{t}{3n}$ if $j>i$ and $P(\mu,\nu) = \frac{1}{3n}$ if $i>j$. \item If $\mu = AiB$ and $\nu = A(i+1)B$ with $i\leq p-1$, then $P(\mu,\nu)=\frac{u}{3n}$. \item If $\mu = A(i+1)B$ and $\nu = AiB$ with $i\geq1$, then $P(\mu,\nu)=\frac{1}{3n}$. \item Otherwise $P(\mu,\nu)=0$ for $\mu \neq \nu$ and $P(\mu,\mu) = 1 - \sum_{\nu \neq \mu} P(\mu,\nu)$. \end{itemize} \end{defn} \begin{remark} There is an inherent cyclic symmetry in the definition, so that a state has the same dynamic under any cyclic permutation. \end{remark} This Markov chain is irreducible and aperiodic, so it has a unique stationary distribution $\pi$ given by rational functions in $u, t$, which satisfies the global balance equations $\pi(\mu) \sum_{\nu \neq \mu} P(\mu, \nu) = \sum_{\nu \neq \mu} \pi(\nu) P(\nu, \mu)$ for any state $\mu$. For convenience, we clear the denominators and obtain the ``unnormalized steady state probabilities" $\pi_{\DASEP}$ which are proportional to the stationary distribution by a factor of the \emph{partition function} $Z^{p,q}_n = \sum_{\mu \in \Gamma^{p,q}_n} \pi_{\DASEP}(\mu)$. We require the unnormalized steady state probabilities to be coprime so they are uniquely defined. \begin{figure} \centering \begin{tikzpicture}[scale=1.5] \draw (-1,1) node {01}; \draw[line width = .5mm, densely dotted, ->] (-.8,1.1) -- (.8,1.1); \draw (0,1.3) node {$\frac16$}; \draw[line width = .5mm, <-] (-.8,.9) -- (.8,.9); \draw (0,.7) node {$\frac{t}{6}$}; \draw[line width = 1mm, ->] (-1.1,.8) -- (-1.1,-0.8); \draw (-1.3,0) node {$\frac{u}{6}$}; \draw[dotted, line width = 1mm, <-] (-.9,.8) -- (-.9,-0.8); \draw (-.7,0) node {$\frac16$}; \draw (1,1) node {10}; \draw (-1,-1) node {02}; \draw (1,-1) node {20}; \draw[line width = 1mm, ->] (1.1,.8) -- (1.1,-0.8); \draw (1.3,0) node {$\frac{u}{6}$}; \draw[dotted,line width = 1mm, <-] (.9,.8) -- (.9,-0.8); \draw (.7,0) node {$\frac16$}; \draw[line width = .5mm, densely dotted, ->] (-.8,-1.1) -- (.8,-1.1); \draw (0,-1.3) node {$\frac16$}; \draw[line width = .5mm, <-] (-.8,-.9) -- (.8,-.9); \draw (0,-.7) node {$\frac{t}{6}$}; \end{tikzpicture} \hspace{3cm} \begin{tikzpicture}[scale = 2] \draw (-1,.5) node (bbw) {110}; \draw (0,.75) node (bwb) {101}; \draw (1,.5) node (wbb) {011}; \draw[<->] (bbw) -- (bwb); \draw[<->] (bwb) -- (wbb); \draw[<->] (bbw) -- (wbb); \draw (0,0) node (21bwb) {102}; \draw (0,-1) node (12bwb) {201}; \draw (-1.5, -.2) node (21bbw) {210}; \draw (-1.5, -.85) node (12bbw) {120}; \draw (1.5, -.2) node (21wbb) {021}; \draw (1.5, -.8) node (12wbb) {012}; \draw[<->] (21bbw) -- (12bbw); \draw[<->] (21bwb) -- (12bwb); \draw[<->] (21wbb) -- (12wbb); \draw[<->] (12bbw) -- (21bwb); \draw[<->] (21bbw) -- (12bwb); \draw[<->] (21bwb) -- (12wbb); \draw[<->] (12bwb) -- (21wbb); \draw[<->] (21bbw) -- (12wbb); \draw[<->] (12bbw) -- (21wbb); \draw (-1,-1.5) node (22bbw) {220}; \draw (0, -1.75) node (22bwb) {202}; \draw (1, -1.5) node (22wbb) {022}; \draw[<->] (22bbw) -- (22bwb); \draw[<->] (22bwb) -- (22wbb); \draw[<->] (22bbw) -- (22wbb); \draw[line width = .5mm, <->] (bbw) -- (21bbw); \draw[line width = .5mm, <->] (bbw) to [bend right=50] (12bbw); \draw[line width = .5mm, <->] (wbb) -- (21wbb); \draw[line width = .5mm, <->] (wbb) to [bend left=50] (12wbb); \draw[line width = .5mm, <->] (bwb) -- (21bwb); \draw[line width = .5mm, <->] (bwb) to [bend right=40] (12bwb); \draw[line width = .5mm, <->] (22bbw) -- (12bbw); \draw[line width = .5mm, <->] (22bbw) to [bend left=50] (21bbw); \draw[line width = .5mm, <->] (22bwb) -- (12bwb); \draw[line width = .5mm, <->] (22bwb) to [bend right=40] (21bwb); \draw[line width = .5mm, <->] (22wbb) -- (12wbb); \draw[line width = .5mm, <->] (22wbb) to [bend right=50] (21wbb); \end{tikzpicture} \caption{The state diagram of $\DASEP(2,2,1)$ and $\DASEP(3,2,2)$. Bold edges denote changes in species, while regular edges denote exchanges of particles of different species or between particles and holes.} \label{fig:dasep221322} \end{figure} Our first main result concerns the ratio between the sums of certain sets of $\pi_{\DASEP}(\mu)$. For each partition $\lambda$ with length $q$ and each binary word $w = (w_1, \dots, w_n)$ with $q$ ones and $n-q$ zeros, define $$S_n^w(\lambda) := \{ \mu \in S_n(\lambda)| \mu_i \neq 0 \text{ if and only if } w_i \neq 0 \}$$ as the equivalence class of weak compositions $\mu$ obtained from permuting $\lambda$ whose support is equal to $w$. Then we have $|S_n(1^{m_1}\cdots p^{m_p})| = \binom{n}{n-q,m_1, \dots, m_p}$ and $|S_n^w(1^{m_1}\cdots p^{m_p})| = \binom{q}{m_1, m_2, \dots, m_p}$. \begin{thm}\label{thm:main} Consider $\DASEP(n,p,q)$ for any positive integers $n,p,q$ with $n >q$. \begin{enumerate} \item For any two binary words $w, w' \in \binom{[n]}{q}$, we have $\pi_{\DASEP}(w) = \pi_{\DASEP}(w')$. \item For any binary word $w \in \binom{[n]}{q}$ and partition $\lambda=1^{m_1} 2^{m_2} \cdots p^{m_p}$ with $m_1 + \cdots + m_p = q$, we have $$ \sum_{\mu \in S_n^w(\lambda)} \pi_{\DASEP}(\mu) = u^{|\lambda|-q} \binom{q}{m_1, m_2, \dots, m_p} \pi_{\DASEP}(w).$$ \end{enumerate} \end{thm} In other words, the average of steady state probabilities over orbits of $S_q$-action on the particles are all equal up to a power of $u$. This is a polynomial generalization of a combinatorial phenomenon called \emph{homomesy} defined by Propp and Roby, see\cite{ProppRoby}. \begin{remark}\label{rmk:cyclic} In the special case of $\DASEP(3,p,2)$, \cref{thm:main} was proved by David Ash \cite[Theorem 5.2]{ash2023introducing}. \end{remark} \begin{ex} For the partition $\lambda = (2,1,0)$ with $|\lambda| = 2+1 = 3$, we have $S_3^{011}((2,1,0)) = \{012, 021\}$ and $|S^{011}_3((2,1,0))| = \binom{2}{1,1} = 2$; also $S_3((2,1,0)) = \{012,021,102,201,120,210\}$ and $|S_3((2,1,0))| = \binom{3}{1,1,1} = 6$. \end{ex} The following are direct corollaries of \cref{thm:main}. \begin{cor}\label{cor:restricted} For the $\DASEP(n,p,q)$ defined by positive integers $n,p,q, n > q$, and $\lambda, \mu$ two partitions with $\lambda_1 \leq p, \mu_1 \leq p, \ell(\lambda) = \ell(\mu) = q$, we have $$\frac{\sum_{\nu\in S_n(\lambda)} \pi_{\DASEP}(\nu)}{\sum_{\nu \in S_n(\mu)} \pi_{\DASEP}(\nu)} = \frac{|S_n(\lambda)|}{|S_n(\mu)|} u^{|\lambda|-|\mu|}.$$ \end{cor} Let $t=1$, then our model is symmetric, dubbed the ``doubly symmetric simple exclusion process (DSSEP)". It is a generalization of the model considered by Salez in \cite{salez2023}, which is an exclusion process on a graph (a circle in our case) with a reservoir of particles at each vertex. Recall that $[p+1]_u = 1+u+\cdots+u^p$ denotes the $u$ analog of the integer $p+1$. For DSSEP, it follows from \cref{thm:main} that \begin{cor}\label{cor:dsep} The partition function of $\DSSEP(n,p,q)$ is $$\binom{n}{q}(1+u+\cdots+u^p)^q = \binom{n}{q}([p+1]_u)^q.$$ \end{cor} \begin{table} \centering \begin{tabular}{|c|c|} \hline $\mu$ & $\pi_{\DASEP}(\mu)$ \\ \hline 011 & $u+3t+4$ \\ \hline 012 & $u(u+4t+3)$ \\ \hline 021 & $u(u+2t+5)$ \\ \hline 022 & $u^2(u+3t+4)$ \\ \hline \end{tabular} \hspace{3cm} \begin{tabular}{|c|c|} \hline $\mu$ & $\pi_{\DASEP}(\mu)$ \\ \hline 0011 & $u+2t+3$ \\ \hline 0101 & $u+2t+3$ \\ \hline 0022 & $u^2(u+2t+3)$ \\ \hline 0202 & $u^2(u+2t+3)$ \\ \hline 0012 & $u(u+3t+2)$ \\ \hline 0102 & $u(u+2t+3)$ \\ \hline 0021 & $u(u+t+4)$ \\ \hline \end{tabular} \caption{The unnormalized steady state probabilities of $\DASEP(3,2,2)$ and $\DASEP(4,2,2)$. We present all states up to cyclic symmetry.} \label{tab:3&4} \end{table} \begin{ex} For $\DASEP(3,2,2)$, by \cref{thm:main}, we have $\pi_{\DASEP}(012) + \pi_{\DASEP}(021) = 2u \pi_{\DASEP}(011)$ and $\pi_{\DASEP}(022) = u^2 \pi_{\DASEP}(011)$ which can be seen from \cref{tab:3&4}. Similarly, for $\DASEP(4,2,2)$, \cref{thm:main} asserts that $\pi_{\DASEP}(0011) = \pi_{\DASEP}(0101)$, $\pi_{\DASEP}(0012) + \pi_{\DASEP}(0021) = 2u \pi_{\DASEP}(0011)$ and $\pi_{\DASEP}(0102) + \pi_{\DASEP}(0201) = 2u \pi_{\DASEP}(0011)$. Since $0201$ is a cyclic permutation of $0102$, their steady state probabilities are equal by \cref{rmk:cyclic}, and \cref{tab:3&4} shows that it is equal to $u \pi_{\DASEP}(0101)$. \end{ex} To prove \cref{thm:main}, we introduce a new Markov chain that we call \emph{colored Boolean process} (see \cref{def:cBp}), and we show that DASEP \emph{lumps} is a colored Boolean process. This gives a relationship between the stationary distribution of the colored Boolean process and the DASEP; see \cref{thm:relationship}. In \cref{thm:n22}, we give explicit formulas for the stationary distributions of the infinite family $\DASEP(n,2,2), n \geq 3$ which depend on whether $n$ is odd or even. Both are described by polynomial sequences given by a second-order homogeneous recurrence relation (see \cref{thm:n22}). The polynomials sequences are generating functions of matchings of certain graphs (see \cref{C3} and \cref{L3}). When specialized to $u=t=1$, the polynomial sequences specialize to trinomial transform of Lucas number \href{https://oeis.org/A082762}{A082762} and binomial transform of the denominators of continued fraction convergents to $\sqrt{5}$ \href{https://oeis.org/A084326}{A084326} \cite{oeis}. \acknowledgements{We thank Lauren Williams for suggesting the problem and helping me better understand ASEP. We thank Evita Nestoridi and Sylvie Corteel for helpful discussions.} \section{The DASEP lumps to the colored Boolean process} In this section, we define the \emph{colored Boolean process}, and we show that the DASEP \emph{lumps} to the \emph{colored Boolean process}. We compute the ratios between steady states probabilities in the colored Boolean process, leading us to understand the ratios between sums of steady state probabilities of the DASEP. \begin{defn}\label{def:cBp} The \emph{colored Boolean process} is a Markov chain dependent on three positive integers $n,p,q$ with $n>q$ on the set of pairs of binary words and partition in a $q\times p$ rectangle $$\Omega^{p,q}_n = \{(w, \lambda) | w \in \binom{[n]}{q}, \lambda_1 \leq p, \ell(\lambda) = q \} $$ with the following transition probabilities: \begin{itemize} \item $Q((w,\lambda),(w,\lambda')) = \frac{m_i(\lambda)u}{3n}$ if $\lambda'$ is obtained from $\lambda$ by changing a part equal to $i < p$ to a part equal to $i+1$, denoted by $\lambda \nearrow_i \lambda'$. \item $Q((w,\lambda),(w,\lambda')) = \frac{m_i(\lambda)}{3n}$ if $\lambda'$ is obtained from $\lambda$ by changing a part equal to $i > 1$ to a part equal to $i-1$, denoted by $\lambda \searrow_i \lambda'$. \item $Q((w,\lambda),(w',\lambda)) = \frac{1}{3n}$ if $w'$ is obtained from $w$ by $01 \to 10$ in a unique position, allowing wrap-around at the end. \item $Q((w,\lambda),(w',\lambda)) = \frac{t}{3n}$ if $w'$ is obtained from $w$ by $10 \to 01$ at a unique position, allowing wrap-around at the end. \item If none of the above applies but $w \neq w'$ or $\lambda \neq \lambda'$, then $Q((w,\lambda),(w',\lambda')) = 0$. Otherwise $Q((w,\lambda),(w,\lambda)) = 1-\sum_{(w',\lambda') \neq (w,\lambda)} Q((w,\lambda),(w',\lambda')).$ \end{itemize} \end{defn} We denote the stationary distribution of $\Omega^{p,q}_n$ by $\pi_{\CBP}$. We think of parts of different sizes as particles of different colors, or species; hence the name. The relation between the colored Boolean process and the DASEP is captured by the following notion. \begin{defn}\cite[Section 6.3]{kemeny}\label{def:lumping} Let $\{X_t\}$ be a Markov chain on state space $\Omega_X$ with transition matrix $P$, and let $f: \Omega_X \to \Omega_Y$ be a surjective map. Suppose there is an $|\Omega_Y| \times |\Omega_Y|$ matrix $Q$ such that for all $y_0, y_1 \in \Omega_Y$, if $f(x_0) = y_0$, then $$ \sum_{x: f(x) = y_1} P(x_0, x) = Q(y_0, y_1). $$ Then $\{f(X_t)\}$ is a Markov chain on $\Omega_Y$ with transition matrix $Q$. We say that $\{f(X_t)\}$ is a \emph{lumping} of $\{X_t\}$. \end{defn} We may use the stationary distribution of $\{X_t\}$ to compute that of its lumping. \begin{prop}\cite[Section 6.3]{kemeny}\label{prop:lumping} Suppose $p$ is a stationary distribution for $\{X_t\}$, and let $\pi$ be the measure on $\Omega_Y$ defined by $\pi(y) = \sum_{x: f(x)=y} p(x)$. Then $\pi$ is a stationary distribution for $\{f(X_t)\}$. \end{prop} \iffalse \begin{figure} \centering \begin{tikzpicture} \draw (0,0) node (bwb) {101}; \draw (-2,0) node (bbw) {110}; \draw (2,0) node (wbb) {011}; \draw (0,-2) node (21bwb) {102,201}; \draw (-2,-2) node (21bbw) {210,120}; \draw (2,-2) node (21wbb){021,012}; \draw (0,-4) node (22bwb) {202}; \draw (-2,-4) node (22bbw) {220}; \draw (2,-4) node (22wbb){022}; \draw[line width = 0.5mm, <->] (bbw) -- (21bbw); \draw[<->] (bbw) -- (bwb); \draw[line width = 0.5mm, <->] (bwb) -- (21bwb); \draw[<->] (bwb) -- (wbb); \path[<->] (bbw) edge[bend left] node [left] {} (wbb); \draw[line width = 0.5mm, <->] (wbb) -- (21wbb); \draw[<->] (21bwb) -- (21bbw); \draw[<->] (21bwb) -- (21wbb); \path[<->] (21bbw) edge[bend left] node [left] {} (21wbb); \draw[line width = 0.5mm, <->] (22bbw) -- (21bbw); \draw[<->] (22bbw) -- (22bwb); \draw[line width = 0.5mm, <->] (22bwb) -- (21bwb); \draw[<->] (22bwb) -- (22wbb); \draw[line width = 0.5mm, <->] (21wbb) -- (22wbb); \path[<->] (22bbw) edge[bend right] node [left] {} (22wbb); \end{tikzpicture} \caption{Transition diagram of $\Omega^{2,2}_3$, as a lumping of $\DASEP(3,2,2)$ as shown on the right hand side in \cref{fig:dasep221322}. The bold edges denote the changes of species, while the regular edges denote the exchanges between particles of different species or between particles and holes.} \label{fig:omega322} \end{figure} \fi \begin{figure} \centering \includegraphics[scale=.7]{cBp322.pdf} \caption{Transition diagram of $\Omega^{2,2}_3$, as a lumping of $\DASEP(3,2,2)$ as shown on the right hand side in \cref{fig:dasep221322}. The bold edges denote the changes of species, while the regular edges denote the exchanges between particles of different species or between particles and holes.} \label{fig:omega322} \end{figure} \begin{thm}\label{thm:relationship} The projection map on state spaces $f: \Gamma^{p,q}_n \to \Omega^{p,q}_n$ sending each $\mu$ to $(w,\lambda)$ if $\mu \in S_n^w(\lambda)$ is a lumping of $\DASEP(n,p,q)$ onto the colored Boolean process $\Omega^{p,q}_n$. \end{thm} It follows from \cref{prop:lumping} that the unnormalized steady state probabilities of the colored Boolean process are proportional to the sums of the unnormalized steady state probabilities of the DASEP as follow: $$\pi_{\CBP}(w,\lambda) \propto \sum_{\mu \in S_n^w(\lambda)} \pi_{\DASEP}(\mu).$$ \begin{proof} Fix $(w_0,\lambda_0)$ and $(w_1, \lambda_1)$, we want to show that for any $\mu_0 \in S_n^{w_0}(\lambda_0)$, the quantity $ \sum_{\mu: \mu \in S_n^{w_1}(\lambda_1)} P(\mu_0, \mu) $ is independent of the choice of $\mu_0$ and equal to $Q((w_0,\lambda_0),(w_1,\lambda_1))$. We may assume $(w_0, \lambda_0) \neq (w_1, \lambda_1)$. Note that this quantity is nonzero only in the following cases: \begin{itemize} \item If $w_0 = w_1$ and there exists a unique $i < p$ such that $\lambda_0 \nearrow_i \lambda_1$, we increase the species of a particle from $i$ to $i+1$, and there are $m_i$ ways to do it. For each $\mu \in S_n^{w_1}(\lambda_1)$, we have $P(\mu_0, \mu) = \frac{u}{3n}$, so their sum is equal to $\frac{m_i u}{3n}$. \item If $w_0 = w_1$ and there exists a unique $i > 1$ such that $\lambda_0 \searrow_i \lambda_1$, we decrease the species of a particle from $i$ to $i-1$, and there are $m_i$ ways to do it, so the quantity is equal to $\frac{m_i}{3n}$. \item If $\lambda_0 = \lambda_1$ and $w_1$ is obtained from $w_0$ by $01 \to 10$ or $10 \to 01$ at a unique position (allow wraparound). This quantity is equal to $\frac{1}{3n}$ or $\frac{t}{3n}$ respectively. \end{itemize} \end{proof} \begin{thm}\label{thm:equal} Consider the colored Boolean process $\Omega^{p,q}_n$. \begin{enumerate} \item The steady state probabilities of all binary words with the trivial partition are equal, i.e., $$\pi_{\CBP}(w, 0^{n-q} 1^q) = \pi_{\CBP}(w', 0^{n-q} 1^q), \quad \text{for all } w, w' \in \binom{[n]}{q}.$$ \item The steady state probability of an arbitrary state $(w,\lambda)$ can be expressed in terms of the steady state probability of the corresponding state $(w, 0^{n-q} 1^q)$ with the trivial partition $0^{n-q} 1^q$ as follows: \begin{equation}\label{eq:thmequal} \pi_{\CBP}(w,\lambda) = u^{|\lambda|-q} \binom{q}{m_1, \dots, m_p} \pi_{\CBP}(w, 0^{n-q} 1^q). \end{equation} \end{enumerate} \end{thm} \begin{proof} Since the colored Boolean process is irreducible, it suffices to verify the global balance equations. For simplicity of notation, denote $\pi_{\CBP}(w,\lambda)$ by $p_{w,\lambda}$. Let $b_w$ be the number of blocks of consecutive $1$'s in $w$ (allowing wrap-around). We first check it for the states given by a binary word and the trivial partition $\lambda_0 = 0^{n-q} 1^q$. Notice that any occurrence of $01$ in $w$ must begin a block, and any occurrence of $10$ must signify the end of a block. The balance equation at $(w, 0^{n-q} 1^q)$ is \begin{equation}\label{balance} (qu + b_w + b_w t) p_{w,\lambda_0} = q p_{w, 1^{q-1}2} + b_w t \sum_{\underset{10\to01}{w' \to w}} p_{w',\lambda_0} + b_w \sum_{\underset{01 \to 10}{w'' \to w}} p_{w'',\lambda_0}. \end{equation} Since $\binom{q}{q-1,1} = 1$, we are left with $$b_w(1 + t) p_w = b_w t \sum_{\underset{10\to01}{w' \to w}} p_{w'} + b_w \sum_{\underset{01 \to 10}{w'' \to w}} p_{w''} $$ which will be satisfied if we set all $p_w$'s to be equal. For arbitrary partition $\lambda = 1^{m_1}2^{m_2}\cdots p^{m_p}$, the left hand side of the balance equation at $(w,\lambda)$ is $$ ((m_1 + \cdots + m_{p-1})u + m_2 + \cdots + m_p + b_w + b_w t) p_{w,\lambda} $$ These account for all the states that $(w,\lambda)$ can transition to. The right hand side of the balance equation at $(w,\lambda)$ is $$\sum_{i < p, \lambda \nearrow_i \lambda'} (m_{i+1} + 1) p_{w, \lambda'} + \sum_{i > 1, \lambda \searrow_i \lambda''} (m_{i-1}+1)u p_{w, \lambda''} + b_w t \sum_{\underset{10\to01}{w' \to w}} p_{w',\lambda} + b_w \sum_{\underset{01 \to 10}{w'' \to w}} p_{w'',\lambda} $$ These account for all the states that can transition into $(w, \lambda)$. Using \cref{eq:thmequal}, the multinomial coefficients give \begin{align*} \frac{p_{w, \lambda'}}{p_{w, \lambda}} &= \frac{m_iu}{m_{i+1}+1} ~~,~ \lambda \nearrow_i \lambda' \implies m_i(\lambda') = m_i-1, m_{i+1}(\lambda') = m_{i+1}+1, \forall i

1. \end{align*} Then we have a term by term equality for each $i$ where $a$ corresponds to the first summation and $b$ corresponds to the second. \end{proof} \begin{proof}[Proof of \cref{thm:main}] This follows directly from \cref{thm:relationship} and \cref{thm:equal}. \end{proof} \section{The colored Boolean process lumps to the restricted random growth model} In this section, we define the \emph{restricted random growth model}, which is a Markov chain on the set of Young diagrams inside a rectangle. We show that the colored Boolean process lumps to the restricted random growth model. \iffalse \begin{defn}\cite{stanley_1999} For partitions $\mu$ and $\lambda$, the \emph{reverse lexicographic order} is a partial order such that $\nu \leq \lambda$ if either $\nu = \lambda$ or for some $j$, $$\nu_1 = \lambda_1, \dots, \nu_{j-1} = \lambda_{j-1}, \nu_j < \lambda_j.$$ We say that \emph{$\lambda$ covers $\nu$ at $i$} if there exists a unique $j$ such that $\lambda_j = \nu_j + 1 = i$ and for all $k \neq j$ we have $\lambda_k = \nu_k$, in which case we write $\lambda \gtrdot_i \nu$. We say that \emph{$\nu$ is covered by $\lambda$ at $i$} if there exists a unique $j$ such that $\nu_j = \lambda_j - 1 = i$ and for all $k \neq j$ we have $\nu_k = \lambda_k$, in which case we write $\nu \lessdot_i \lambda$. In both cases, we have $m_i(\nu) = m_i(\lambda)+1$ where $m_i(\nu)$ is the number of parts of $\nu$ equal to $i$. \end{defn} \fi \begin{defn} Define the \emph{restricted random growth model} on the the set $\chi^{p,q} = \{\lambda: \lambda_1 \leq p, \ell(\lambda) = q\}$ of all partitions that fit inside a $q \times p$ rectangle but do not fit inside a shorter rectangle, with transition probabilities as follows: \begin{itemize} \item If $\nu \nearrow_i \lambda$, then $\Pr(\nu, \lambda) = \frac{m_i(\nu) u}{3n}$. \item If $\nu \searrow_i \lambda$, then $\Pr(\nu, \lambda) = \frac{m_i(\nu)}{3n}$. \item Otherwise if $\nu \neq \lambda$, then $\Pr(\nu, \lambda) = 0$ and $\Pr(\lambda, \lambda) = 1-\sum_{\nu : \nu \neq \lambda} \Pr(\nu,\lambda)$. \end{itemize} \end{defn} We denote the unnormalized steady state probability of the restricted random growth model by $\pi_{\RRG}$. \begin{figure} \centering \begin{tikzpicture} \draw (0,1.5) node (11) {{\tiny \ydiagram{1,1}}}; \draw (0,0) node (21) {{\tiny\ydiagram{2,1}}}; \draw (0,-1.5) node (21) {\tiny{\ydiagram{2,2}}}; \draw[line width = .5mm, ->] (-0.2, 1) -- (-.2,.5); \draw (-.5, .75) node {$2u$}; \draw[<-] (.2, 1) -- (.2, .5); \draw (.4, .75) node {$1$}; \draw[line width = .5mm, ->] (-0.2, -.5) -- (-.2,-1); \draw (-.4, -.75) node {$u$}; \draw[<-] (.2, -.5) -- (.2, -1); \draw (.4, -.75) node {$2$}; \end{tikzpicture} \hspace{2cm} \begin{tikzpicture} \draw (0,1.5) node (11) {{\tiny \ydiagram{1,1}}}; \draw (-1,0) node (21) {{\tiny \ydiagram{2,1}}}; \draw (0,0) node {$\cong$}; \draw (1,0) node (12) {{\tiny \ydiagram{1,2}}}; \draw (0,-1.5) node (22) {{\tiny \ydiagram{2,2}}}; \draw[line width = .5mm, ->] (-.4, 1) -- (-1.4,.5); \draw[line width = .5mm, ->] (.4, 1) -- (1.4,.5); \draw (-1, .9) node {$u$}; \draw (1, .9) node {$u$}; \draw[<-] (-.1, 1) -- (-1.1,.5); \draw[<-] (.1, 1) -- (1.1,.5); \draw (-.4, .5) node {$1$}; \draw (.4, .5) node {$1$}; \draw[line width = .5mm, ->] (-1.4, -.5) -- (-.4,-1); \draw[line width = .5mm, ->] (1.4, -.5) -- (.4,-1); \draw (-1, -.9) node {$u$}; \draw (1, -.9) node {$u$}; \draw[<-] (-1.1, -.5) -- (-.1, -1); \draw[<-] (1.1, -.5) -- (.1, -1); \draw (-.4, -.5) node {$1$}; \draw (.4, -.5) node {$1$}; \end{tikzpicture} \caption{Transition diagram of the restricted random growth model on $\chi^{2,2}$. The Markov chain on the left can be viewed as a lumping of the Markov chain on the right by rearranging boxes into weakly decreasing order.} \label{fig:restricted} \end{figure} For two partitions $\lambda$ and $\lambda'$, if $\lambda \nearrow_i \lambda'$, then the Young diagram of $\lambda'$ is obtained from the Young diagram of $\lambda$ by adding a corner box to the topmost row of length $i$. If $\lambda \searrow_i \lambda'$, then we remove the corner box from the topmost row of length $i$. In other words, the restricted random growth model either adds or removes a box from a uniformly chosen part of the Young diagram of the partition (conditioned on staying in the $q \times p$ rectangle) as shown on the right hand side of \cref{fig:restricted}, then rearrange the parts in weakly decreasing order as shown on the left hand side of \cref{fig:restricted}. Random growth models are of independent interests and have been studied by many people \cite{Ferrari2010RandomGM}. \begin{thm}\label{2ndlumping} The projection map on state spaces $ \Omega^{p,q}_n \to \chi^{p,q}$ sending $(w,\lambda)$ to $\lambda$ (forgetting the positions of 0's) is a lumping of the colored Boolean process to the restricted random growth. \end{thm} It follows from \cref{prop:lumping} that $$\pi_{\RRG}(\lambda) \propto \sum_{w \in \binom{[n]}{q}} \pi_{\CBP}(w,\lambda).$$ \begin{proof} By \cref{def:lumping}, we need to show that for any $\nu \neq \lambda$ and binary word $w$ the following equation holds: $$\Pr(\nu,\lambda) = \sum_{w'} Q((w,\nu),(w',\lambda)).$$ Then $Q((w,\nu),(w',\lambda)) \neq 0$ only if $w = w'$ by \cref{def:cBp}, and this quantity is either $\frac{m_i(\nu) u}{3n}$ when $\nu \nearrow_i \lambda$ or $\frac{m_i(\nu)}{3n}$ when $\nu \searrow_i \lambda$. \end{proof} \begin{thm}\label{thm:multinomial} The steady state probabilities of the restricted random growth satisfy the following relations for all partitions $\nu, \lambda \in \chi^{p,q}$: $$\frac{\pi_{\RRG}(\lambda)}{\pi_{\RRG}(\nu)} = \frac{|S_n(\lambda)|}{|S_n(\nu)|} u^{|\lambda|-|\nu|}.$$ \end{thm} \begin{proof} This follows from \cref{2ndlumping} and \cref{thm:equal} and a computation on multinomial coefficients. \end{proof} \begin{proof}[Proof of \cref{cor:restricted}] This follows from \cref{2ndlumping} and \cref{thm:multinomial}. \end{proof} \begin{proof}[Proof of \cref{cor:dsep}] When $t=1$, for any partition $\lambda$ and for any two weak compositions $\mu, \nu \in S_n(\lambda)$, we have $\pi_{\DASEP}(\mu) = \pi_{\DASEP}(\nu)$. By \cref{thm:multinomial} and the requirement for unnormalized steady state probabilities to be coprime, we see that the partition function of DSSEP is {\small $$\sum_{\substack{\lambda_1 \leq p, \\ \ell(\lambda) = q}} u^{|\lambda|} |S_n(\lambda)| = \binom{n}{q} \sum_{m_1+\cdots+m_p=q} u^{m_1+2m_2\cdots pm_p} \binom{q}{m_1,\dots,m_p} = \binom{n}{q} (1+u+\cdots+u^p)^q.$$ } \end{proof} \iffalse \section{Other infinite families} \begin{ex} The infinite family $\DASEP(n,2,n-1)$ gives $1,4,11,26$ (\href{https://oeis.org/A000295}{OEIS: A000295}) as degrees of $u$. \end{ex} \begin{conj} The degree of $u$ in $p_{01^{n-1}}$ in $\DASEP(n,2,n-1)$ is the $n$th Eulerian number. \end{conj} \begin{ex} The infinite family $\DASEP(3,p,2)$ gives $3,6,9,14,19$ (\href{https://oeis.org/A061925}{OEIS: A061925}) as degrees of $u$. \end{ex} \begin{conj} The degree of $u$ in $p_{110}$ $\DASEP(3,p,2)$ is $\lceil \frac{n^2}{2} \rceil + 1$. \end{conj} \begin{ex} In $\DASEP(n,3,2)$, {\small $$ \begin{array}{cc} n & p_{0^{n-2}11} \\ 3 & (2 u + 3 t + 5) \cdot (u^{2} + 6 u t + 9 t^{2} + 7 u + 24 t + 16) \\ 4 & 2 \cdot (u + t + 2) \cdot (u^{2} + 4 u t + 4 t^{2} + 5 u + 12 t + 9) \end{array} $$ } \end{ex} \begin{conj}\label{conj:n32} In the infinite family $\DASEP(n,3,2)$, let $\mu$ be the state $0^{n-2}11$, then $p_\mu$ can be factored as the product of polynomials $p_1, p_2$ where $$\deg p_1 = \lfloor \frac{n-1}{2} \rfloor, p_2 = (p_1-u-1)^2-u.$$ \end{conj} {\small $$ \begin{array}{cc} n & p_1(n) \\ 3 & 3 \, t + 2 \, u + 5 \\ 4 & 2 (t + u + 2) \\ 5 & 5 t^{2} + 10 t u + 4 u^{2} + 20 t + 18 u + 19 \\ 6 & (3t+2u+5)(t+2u+3) \\ 7 & 4(t^2+4tu+2u^2+6t+8u+7)(t+u+2) \end{array}$$ } \begin{ex} When $n$ is odd, evaluation of $p_1$ at $u=t=1$ is the sequence 10, 76, 568 (\href{https://oeis.org/A107903}{OEIS: A107903}), which are a generalized NSW numbers counting total area under elevated Schroeder paths of length $2n+2$, where horizontal steps can choose from two colors (NOT THREE, OEIS ERROR), which also counts the set of all unrestricted lattice paths that run from $(0,0)$ to $x=2n+1$ that use steps $(1,1), (1,-1)$ and $(2,0)$ (which is bicolored) and that do not end with a rise step (Pergola-Pinzani 1999). When $n$ is even evaluation of $p_1$ at $u=t=1$ is the sequence 8, 60, 448 (\href{https://oeis.org/A099156}{OEIS: A099156}), which is related to the Chebyshev polynomials. They both satisfy the recurrence relation $a(n) = 8a(n-1) - 4a(n-2)$. \end{ex} \begin{conj} $p_1$ for different $n$'s satisfy the recurrence relation $$p_1(n)=2(u+t+2)p_1(n-1)-(t+1)^2p_1(n-2).$$ \end{conj} \begin{ex} In $\DASEP(n,4,2)$, {\small $$ \begin{array}{cc} n & p_{0^{n-2}11} \\ 3 & (u + 3 t + 4) \cdot (2 u + 3 t + 5) \cdot (u^{2} + 6 u t + 9 t^{2} + 6 u + 24 t + 16) \cdot (4 u^{2} + 12 u t + 9 t^{2} + 18 u + 30 t + 25) \\ 4 & (u + 2 t + 3) \cdot (2u + 2t + 4) \cdot (u^{2} + 4 u t + 4 t^{2} + 4 u + 12 t + 9) \cdot (4 u^{2} + 8 u t + 4 t^{2} + 14 u + 16 t + 16) \end{array} $$ } \end{ex} \begin{conj} In $\DASEP(n,4,2)$, let $\mu$ be the state $0^{n-2}11$, then $p_\mu$ can be factored as the product of $p,q,(p^2-2u)$, and $(q^2-2u)$. Here $p = p_1(n)$ appearing in $\DASEP(n,3,2)$, and $q$ is $p_\mu(n)$ in $\DASEP(n,2,2)$. \end{conj} \begin{ex} The infinite family $\DASEP(n,2,3)$ gives $4,8,12,20$ as degrees of $u$ and $2,4,6,10$ as $\log_2$ of the coefficients of the highest order term of $u$. \end{ex} \begin{conj} The degree of $u$ in $p_{1110^{n-3}}$ in $\DASEP(n,2,3)$ is $4F_{n-1}$ for $F_{n-1}$ the $(n-1)$th Fibonacci number (\href{https://oeis.org/A000045}{OEIS: A000045}). The coefficient of $u$ in $p_{1110^{n-3}}$ in $\DASEP(n,2,3)$ is $2^{2F_{n-1}}$. \end{conj} \fi \section{The stationary distribution of DASEP(n,2,2)} In this section, we give a complete description of the stationary distributions when there are two particles and two species, while the number of sites can be arbitrary. \begin{figure}[ht!] \centering \includegraphics{funfacts1.pdf} \vspace{-.7cm} \caption{$a_1 = u+3t+4$} \label{C3} \end{figure} \begin{figure}[ht!] \centering \includegraphics{funfacts2.pdf} \vspace{-.7cm} \caption{$b_1 = u+2t+3$} \label{L3} \end{figure} \begin{table}[ht!] \centering $$\begin{array}{|c|c|c|} \hline \mu & \pi_{\DASEP(2k+1,2,2)}(\mu) \\ \hline S_n((1,1,0,\dots,0)) & a_k \\ \hline 0\dots010^m 20\dots0 & ua_k + u(t-1)(t+1)^m a_{k-m-1}, (0\leq m