The doubly asymmetric simple exclusion process, the colored Boolean process, and the restricted random growth model

Yuhan Jiang Harvard University
Dept. of Mathematics
1 Oxford St
Cambridge
MA 02138 (USA) [email protected]

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 $\operatorname{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 $\operatorname{DASEP}(n,2,2)$ .

Key words and phrases:

Asymmetric exclusion process, Markov chain

1991 Mathematics Subject Classification:

05E99, 60J10

1. Introduction

The asymmetric simple exclusion process (ASEP) is a Markov chain for particles hopping on a one-dimensional lattice such that each site contains at most one particle. The ASEP was introduced independently in biology by Macdonald-Gibbs-Pipkin [13], and in mathematics by Spitzer [20]. There are many versions of the ASEP: the lattice can have open boundaries, or be a ring, not necessarily finite (see Liggett [11],[12]). Particles can have 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 [9], and various methods have been invented to study the ASEP, such as the matrix ansatz introduced by Derrida et al. in [6]. The combinatorics of the ASEP was studied by many people, see [7][3][4][14][5].

A partition $\lambda$ is a weakly decreasing sequence of $n$ nonnegative integers $\lambda=(\lambda_{1}\geq\lambda_{2}\geq\dots\geq\lambda_{n}\geq 0)$ . We denote the sum of all parts by $|\lambda|=\lambda_{1}+\cdots+\lambda_{n}$ . We will write a partition as an $n$ -tuple $\lambda=(\lambda_{1},\lambda_{2},\dots,\lambda_{n})$ . Let $m_{i}=m_{i}(\lambda)$ be the number of parts of $\lambda$ that equal $i$ . As in [21, Section 7.2], we also denote a partition by $\lambda=\langle 1^{m_{1}}2^{m_{2}}\cdots\rangle$ . Let $\ell(\lambda)$ denote the number of nonzero (positive) parts of $\lambda$ , or the length of $\lambda$ . We have $\ell(\lambda)=\sum_{i}m_{i}(\lambda)$ . We write $S_{n}(\lambda)$ as the set of all permutations of $(\lambda_{1},\dots,\lambda_{n})$ . The mASEP can be thought of a Markov chain on $S_{n}(\lambda)$ .

Let $n$ be the number of positions on the lattice, $p$ be number of types of species, and $q$ be the number of particles. David Ash [2] defined the doubly asymmetric simple exclusion process $\operatorname{DASEP}(n,p,q)$ . The DASEP is a variant of the mASEP but also allows particles to change from one species to another. If $p=1$ , $\operatorname{DASEP}(n,1,q)$ is the usual 1-species PASEP on a ring.

Definition 1.1.

[2] For all positive integers $n,p,q$ with $n>q$ , the doubly asymmetric simple exclusion process $\operatorname{DASEP}(n,p,q)$ is a Markov process on the following set

\Gamma^{p,q}_{n}=\bigcup_{\begin{subarray}{c}\lambda_{1}\leq p,\\ \ell(\lambda)=q\end{subarray}}S_{n}(\lambda).

Let $0\leq t,u\leq 1$ be constants. The transition probability $P(\mu,\nu)$ on two permutations $\mu$ and $\nu$ is as follows:

•

If $\mu=(\mu_{1},\dots,\mu_{k},i,j,\mu_{k+2},\dots,\mu_{n})$ and $\nu=(\mu_{1},\dots,\mu_{k},j,i,\mu_{k+2},\dots,\mu_{n})$ with $i\neq j$ , then $P(\mu,\nu)=\frac{t}{3n}$ if $i>j$ and $P(\mu,\nu)=\frac{1}{3n}$ if $j>i$ .
•

If $\mu=(i,\mu_{2},\mu_{3},\dots,\mu_{n-1},j)$ and $\nu=(j,\mu_{2},\mu_{3},\dots,\mu_{n-1},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$ .
•

If $\mu=(\mu_{1},\dots,\mu_{k},i,\mu_{k+2},\dots,\mu_{n})$ and $\nu=(\mu_{1},\dots,\mu_{k},i+1,\mu_{k+2},\dots,\mu_{n})$ with $i\leq p-1$ , then $P(\mu,\nu)=\frac{u}{3n}$ .
•

If $\mu=(\mu_{1},\dots,\mu_{k},i+1,\mu_{k+2},\dots,\mu_{n})$ and $\nu=(\mu_{1},\dots,\mu_{k},i,\mu_{k+2},\dots,\mu_{n})$ with $i\geq 1$ , then $P(\mu,\nu)=\frac{1}{3n}$ .
•

If none of the above conditions apply but $\nu\neq\mu$ then $P(\mu,\nu)=0$ . If $\nu=\mu$ then $P(\mu,\mu)=1-\sum_{\nu\neq\mu}P(\mu,\nu)$ .

As we are interested in the stationary distribution of DASEP, we denote the un-normalised stationary distribution by $\{\pi_{\operatorname{DASEP}}(\mu):\mu\in S_{n}(\lambda)\}$ , which is uniquely defined if we require the $p_{\mu}$ to be polynomials with greatest common divisor equal to 1.

Remark 1.2.

There is an inherent cyclic symmetry in the definition of DASEP.

Figure 1. The state diagram of

\operatorname{DASEP}(2,2,1)

and

\operatorname{DASEP}(3,2,2)

. We omit loops at each state. Bold edges denote changes in species, while regular edges denote exchanges of particles of different species or between particles and holes.

Our first main result is about the ratio between the sums of certain groups of $p_{\mu}$ . For each partition $\lambda$ and each binary word $w=(w_{1},\dots,w_{n})\in S_{n}(1^{q}0^{n-q})$ , 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 set of all permutations of $\lambda$ whose zeros are aligned with the binary word $w$ . Then if $\lambda_{1}\leq p$ and $\ell(\lambda)=q$ , we have $|S_{n}(\lambda)|=\binom{n}{n-q,m_{1},\dots,m_{p}}$ and $|S_{n}^{w}(\lambda)|=\binom{q}{m_{1},m_{2},\dots,m_{p}}$ .

Example 1.3.

For the partition $\lambda=(2,1)$ , we have $|\lambda|=2+1=3$ . For $n=3$ , we have $|S_{3}^{011}((2,1))|=\binom{2}{1,1}=2$ . For $n=4$ , we have $|S_{4}((2,1))|=\binom{4}{2,1,1}=12$ .

Theorem 1.4.

Consider $\operatorname{DASEP}(n,p,q)$ for any positive integers $n,p,q$ with $n>q$ .

(1)

For any two binary words $w,w^{\prime}\in S_{n}(1^{q}0^{n-q})$ , we have $\pi_{\operatorname{DASEP}}(w)=\pi_{\operatorname{DASEP}}(w^{\prime})$ .

(2)

For any binary word $w\in S_{n}(1^{q}0^{n-q})$ and partition $\lambda=\langle 1^{m_{1}}2^{m_{2}}\cdots p^{m_{p}}\rangle$ such that

m_{1}+\cdots+m_{p}=q,

we have

	$\displaystyle\sum_{\mu\in S_{n}^{w}(\lambda)}\pi_{\operatorname{DASEP}}(\mu)$	$\displaystyle=u^{\|\lambda\|-q}\|S_{n}^{w}(\lambda)\|\pi_{\operatorname{DASEP}}(w)$
		$\displaystyle=u^{\|\lambda\|-q}\binom{q}{m_{1},m_{2},\dots,m_{p}}\pi_{\operatorname{DASEP}}(w).$

In other words, the sum of steady state probabilities of states within one equivalence class is proportional to each other and the ratio only depends on the sum of all parts and the multiplicities in the partition; all steady state probabilities with respect to binary words are equal.

Remark 1.5.

In the special case of $\operatorname{DASEP}(3,p,2)$ , 1.4 was proved by David Ash [2, Theorem 5.2].

$\mu$	$\pi_{\operatorname{DASEP}}(\mu)$
011	$u+3t+4$
012	$u(u+4t+3)$
021	$u(u+2t+5)$
022	$u^{2}(u+3t+4)$

$\mu$	$\pi_{\operatorname{DASEP}}(\mu)$
0011	$u+2t+3$
0101	$u+2t+3$
0022	$u^{2}(u+2t+3)$
0202	$u^{2}(u+2t+3)$
0012	$u(u+3t+2)$
0102	$u(u+2t+3)$
0021	$u(u+t+4)$

Table 1. Unnormalized steady state probabilities of

\operatorname{DASEP}(3,2,2)

and

\operatorname{DASEP}(4,2,2)

. We present all states up to cyclic symmetry. The shaded rows on the left belong to

S_{3}^{011}((2,1))

, and on the right belong to

S_{4}^{0011}((2,1))

Example 1.6.

In $\operatorname{DASEP}(3,2,2)$ , we compute the steady state probabilities for the binary word $w=011$ and permutations of $(1,1,0),(2,1,0),(2,2,0)$ aligned with $w$ as shown in Table 1. By 1.4, we have $\pi_{\operatorname{DASEP}}(012)+\pi_{\operatorname{DASEP}}(021)=2u\pi_{\operatorname{DASEP}}(011)$ and $\pi_{\operatorname{DASEP}}(022)=u^{2}\pi_{\operatorname{DASEP}}(011)$ , which can be seen from Table 1.

Similarly, in $\operatorname{DASEP}(4,2,2)$ , we compute the steady state probabilities for binary words $0011$ and $0101$ in Table 1. We have $\pi_{\operatorname{DASEP}}(0011)=\pi_{\operatorname{DASEP}}(0101)$ and $\pi_{\operatorname{DASEP}}(0012)+\pi_{\operatorname{DASEP}}(0021)=2u\pi_{\operatorname{DASEP}}(0011)$ . Since $0201$ is a cyclic permutation of $0102$ , by 1.2, we have $\pi_{\operatorname{DASEP}}(0201)=\pi_{\operatorname{DASEP}}(0102)$ . Therefore, we can see from Table 1 that $\pi_{\operatorname{DASEP}}(0102)+\pi_{\operatorname{DASEP}}(0201)=2u\pi_{\operatorname{DASEP}}(0101)$ as asserted by 1.4.

To prove 1.4, we also introduce a new Markov chain that we call the colored Boolean process (see 2.1), and we show that the DASEP lumps to the colored Boolean process. This gives a relationship between the stationary distribution of colored Boolean process and the DASEP, see 2.3.

Corollary 1.7.

For the $\operatorname{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_{\operatorname{DASEP}}(\nu)}{\sum_{\nu\in S_{n}(\mu)}\pi_{\operatorname{DASEP}}(\nu)}=\frac{|S_{n}(\lambda)|}{|S_{n}(\mu)|}u^{|\lambda|-|\mu|}.

In 4.1, we also give explicit formulas for the stationary distributions of the infinite family $\operatorname{DASEP}(n,2,2)$ for any $n\geq 3$ . The formulas depend on whether $n$ is odd or even. Both are described by polynomial sequences given by a second-order homogeneous recurrence relation (see 4.1).

When we specialize to $u=t=1$ , the polynomial sequences specialize to the trinomial transform of Lucas number A082762 or the binomial transform of the denominators of continued fraction convergents to $\sqrt{5}$ A084326 [19].

The structure of this paper is as follows. In Section 2, we define the colored Boolean process, and we show that the DASEP lumps to the colored Boolean process. In Section 3, we define the restricted random growth model, which is a Markov chain on Young diagrams, and we show that the colored Boolean process lumps to the restricted random growth model. In Section 4, we give explicit formulas for the stationary distributions of the infinite family $\operatorname{DASEP}(n,2,2)$ .

Acknowledgements

We thank Lauren Williams for suggesting the problem and helping me better understand ASEP.

2. The DASEP lumps to the colored Boolean process

In this section, we define the colored Boolean process, and we show that the DASEP lumps to the colored Boolean process. We compute the ratios between steady states probabilities in the colored Boolean process, leading us to prove 1.4.

Definition 2.1.

The colored Boolean process is a Markov chain dependent on three positive integers $n,p,q$ with $n>q$ on states space

\Omega^{p,q}_{n}=\{(w,\lambda)|w\in S_{n}(1^{q}0^{n-q}),\lambda_{1}\leq p,\ell(\lambda)=q\}

with the following transition probabilities:

•

$Q((w,\lambda),(w,\lambda^{\prime}))=\frac{m_{i}u}{3n}$ if $\lambda$ contains $m_{i}\geq 1$ parts equal to $i$ and $\lambda^{\prime}$ is obtained from $\lambda$ by changing a part equal to $i$ to a part equal to $i+1$ .
•

$Q((w,\lambda),(w,\lambda^{\prime}))=\frac{m_{i}}{3n}$ if $\lambda$ contains $m_{i}\geq 1$ parts equal to $i$ and $\lambda^{\prime}$ is obtained from $\lambda$ by changing a part equal to $i$ to a part equal to $i-1$ .
•

$Q((w,\lambda),(w^{\prime},\lambda))=\frac{1}{3n}$ if $w^{\prime}$ is obtained from $w$ by $01\to 10$ at a unique position (allowing wrap-around at the end).
•

$Q((w,\lambda),(w^{\prime},\lambda))=\frac{t}{3n}$ if $w^{\prime}$ is obtained from $w$ by $10\to 01$ at a unique position (allowing wrap-around at the end).
•

If none of the above conditions apply but $w\neq w^{\prime}$ or $\lambda\neq\lambda^{\prime}$ , then $Q((w,\lambda),(w^{\prime},\lambda^{\prime}))=0$ .
•

$Q((w,\lambda),(w,\lambda))=1-\sum_{(w^{\prime},\lambda^{\prime})\neq(w,\lambda)}Q((w,\lambda),(w^{\prime},\lambda^{\prime})).$

We denote the stationary distribution of $\Omega^{p,q}_{n}$ by $\pi_{\operatorname{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.

Definition 2.2.

[10, Section 6.3][15, Definition 2.5, Theorem 2.6] 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 lumping of $\{X_{t}\}$ and $\{X_{t}\}$ is a lift of $\{f(X_{t})\}$ .

Refer to caption — Figure 2. The state diagram of $\Omega^{2,2}_{3}$ , as a lumping of $\operatorname{DASEP}(3,2,2)$ as in Figure 1. 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.

Theorem 2.3.

The projection map $f:\Gamma^{p,q}_{n}\to\Omega^{p,q}_{n}$ sending each $\mu\in S_{n}^{w}(\lambda)$ to $(w,\lambda)$ is a lumping of $\operatorname{DASEP}(n,p,q)$ onto the colored Boolean process $\Omega^{p,q}_{n}$ .

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:f(\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})$ , because the probabilities add up to 1.

This quantity is nonzero only in the following cases:

•

$w_{0}=w_{1}$ and if $\lambda_{0}=1^{m_{1}}2^{m_{2}}\cdots p^{m_{p}}$ there exists a unique $i\in[1,p-1]$ with $m_{i}\geq 1$ such that $\lambda_{1}=\cdots i^{m_{i}-1}(i+1)^{m_{i+1}+1}\cdots$ . We upgrade the species of a particle from $i$ to $i+1$ , and there are again $m_{i}$ ways to do it, where each transition probability $P(\mu_{0},\mu)=\frac{u}{3n}$ , so the quantity is equal to $\frac{m_{i}u}{3n}$ .
•

$w_{0}=w_{1}$ and if $\lambda_{0}=1^{m_{1}}2^{m_{2}}\cdots p^{m_{p}}$ there exists a unique $i\in[2,p]$ with $m_{i}\geq 1$ such that $\lambda_{1}=\cdots(i-1)^{m_{i-1}+1}i^{m_{i}-1}\cdots$ . We downgrade the species of a particle from $i$ to $i-1$ , and there are $m_{i}$ ways to do it, so there are $m_{i}$ number of $\mu$ ’s in $S_{n}^{w_{1}}(\lambda_{1})$ with nonzero $P(\mu_{0},\mu)=\frac{1}{3n}$ , so the quantity is equal to $\frac{m_{i}}{3n}$ .
•

$\lambda_{0}=\lambda_{1}$ and $w_{1}$ is obtained from $w_{0}$ by $01\to 10$ at a unique position (allowing wrap-around at the end). This quantity is equal to $\frac{1}{3n}$ .
•

$\lambda_{0}=\lambda_{1}$ and $w_{1}$ is obtained from $w_{0}$ by $10\to 01$ at a unique position (allowing wrap-around at the end). This quantity is equal to $\frac{t}{3n}$ .

The nonzero transition probabilities of $\Omega$ in each of the four cases above is the same as we defined. ∎

We may use the stationary distribution of $\{X_{t}\}$ to compute that of its lumping.

Proposition 2.4.

[10, Section 6.3] 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})\}$ .

Thus, we may use the stationary distribution of $\Omega^{p,q}_{n}$ to study that of $\Gamma_{n}^{p,q}$ . We have the following corollary due to 2.4 and 2.3.

Corollary 2.5.

The unnormalized steady state probabilities $\{\pi_{\operatorname{CBP}}(w,\lambda)|(w,\lambda)\in\Omega^{p,q}_{n}\}$ of the colored Boolean process and the unnormalized steady state probabilities $\{\pi_{\operatorname{DASEP}}(\mu)|\mu\in\Gamma^{p,q}_{n}\}$ of the DASEP are related as follows:

\pi_{\operatorname{CBP}}(w,\lambda)\propto\sum_{\mu\in S_{n}^{w}(\lambda)}\pi_{\operatorname{DASEP}}(\mu).

Theorem 2.6.

Consider the colored Boolean process $\Omega^{p,q}_{n}$ .

(1)

The steady state probabilities of all binary words are equal, i.e.,

$\pi_{\operatorname{CBP}}(w,1^{q}0^{n-q})=\pi_{\operatorname{CBP}}(w^{\prime},1^{q}0^{n-q})$

for any $w,w^{\prime}\in S_{n}(1^{q}0^{n-q})$ .
(2)

The steady state probability $\pi_{\operatorname{CBP}}(w,\lambda)$ of an arbitrary state $(w,\lambda)$ can be expressed in terms of the steady state probability $\pi_{\operatorname{CBP}}(w,1^{q}0^{n-q})$ (of the corresponding state $(w,1^{q}0^{n-q})$ with the trivial partition $(1^{q}0^{n-q})$ ) as follows:

(1) $\pi_{\operatorname{CBP}}(w,\lambda)=u^{|\lambda|-q}\binom{q}{m_{1},\dots,m_{p}}\pi_{\operatorname{CBP}}(w,1^{q}0^{n-q}).$

Proof.

The colored Boolean process is again an ergodic markov chain, so we only need to show that the above relations satisfy the balance equations given by the transition matrix of $\Omega$ .

Let us first check it for $\lambda=1^{q}0^{n-q}$ . For any binary word $w$ , denote $\pi_{\operatorname{CBP}}(w,1^{q}0^{n-q})$ by $p_{w}$ . Let $b_{w}$ be the number of blocks of consecutive $1$ ’s in $w$ (allowing wrap-around). Notice that any occurrence of $01$ in $w$ must begin a block, and any occurrence of $10$ must signify the end of a block. We have

(2)

(qu+b_{w}+b_{w}t)p_{w}=q\pi_{\operatorname{CBP}}(w,1^{q-1}2)+b_{w}t\sum_{\underset{10\to 01}{w^{\prime}\to w}}p_{w^{\prime}}+b_{w}\sum_{\underset{01\to 10}{w^{\prime\prime}\to w}}p_{w^{\prime\prime}}.

Expanding the multinomial coefficient, we are left with

b_{w}(1+t)p_{w}=b_{w}t\sum_{\underset{10\to 01}{w^{\prime}\to w}}p_{w^{\prime}}+b_{w}\sum_{\underset{01\to 10}{w^{\prime\prime}\to w}}p_{w^{\prime\prime}}

which will be satisfied if we set all $p_{w}$ ’s to be equal.

For a generic $\lambda=\langle 1^{m_{1}}2^{m_{2}}\cdots p^{m_{p}}\rangle$ , Equation 2 is modified on the left hand side such that $qu$ becomes $au+b$ where $a=m_{1}+\cdots+m_{p-1}$ and $b=m_{2}+\cdots+m_{p}$ . On the right hand side pf Equation 2, we change the first term to

\sum_{i<p}(m_{i+1}+1)\pi_{\operatorname{CBP}}(w,\cdots i^{m_{i}-1}(i+1)^{m_{i+1}+1}\cdots)+\sum_{i>1}(m_{i-1}+1)u\pi_{\operatorname{CBP}}(w,\cdots(i-1)^{m_{i-1}+1}i^{m_{i}-1}\cdots).

Expand this using Equation 1, the multinomial coefficients gives the ratios

	$\displaystyle\frac{\pi_{\operatorname{CBP}}(w,\cdots i^{m_{i}-1}(i+1)^{m_{i+1}+1}\cdots)}{\pi_{\operatorname{CBP}}(w,1^{m_{1}}2^{m_{2}}\cdots p^{m_{p}})}$	$\displaystyle=\frac{m_{i}u}{m_{i+1}+1}$
	$\displaystyle\frac{\pi_{\operatorname{CBP}}(w,\cdots(i-1)^{m_{i-1}+1}i^{m_{i}-1}\cdots)}{\pi_{\operatorname{CBP}}(w,1^{m_{1}}2^{m_{2}}\cdots p^{m_{p}})}$	$\displaystyle=\frac{m_{i}}{(m_{i-1}+1)u}$

for all $i$ . Then we have a term by term equality for each $i$ where $a$ corresponds to the first summation and $b$ corresponds to the second. ∎

Proof of 1.4.

This follows directly from 2.4, 2.3 and 2.6. ∎

3. The colored Boolean process lumps to the restricted random growth model

In this section, we define the restricted random growth model, which is a Markov chain on the set of Young diagrams fitting inside a rectangle, and we show it to be a lumping of the colored Boolean process.

For partitions $\nu$ and $\lambda$ , we write $\lambda\gtrdot_{i}\nu$ 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}$ . We write $\nu\lessdot_{i}\lambda$ 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 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$ .

Example 3.1.

$(2,{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}2},1,0,0)\gtrdot_{2}(2,1,1,0,0)$ and $(2,{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}1},1,0,0)\lessdot_{1}(2,2,1,0,0)$ .

Definition 3.2.

Define the restricted random growth model on the the state space $\chi^{p,q}=\{\lambda:\lambda_{1}\leq p,\ell(\lambda)=q\}$ which includes all partitions that fit inside a $q\times p$ rectangle but do not fit inside a shorter rectangle, with transition probabilities $d^{(n)}_{\nu,\lambda}$ as follows:

•

If $\nu\lessdot_{i}\lambda$ , then $d^{(n)}_{\nu,\lambda}=\frac{m_{i}(\nu)u}{3n}$ .
•

If $\nu\gtrdot_{i}\lambda$ , then $d^{(n)}_{\nu,\lambda}=\frac{m_{i}(\nu)}{3n}$ .
•

In all other cases where $\nu\neq\lambda$ , $d^{(n)}_{\nu,\lambda}=0$ .
•

$d^{(n)}_{\lambda,\lambda}=1-\sum_{\nu:\nu\neq\lambda}d^{(n)}_{\nu,\lambda}$ .

Recall that we also denote the number of parts of the partition $\nu$ that equal to $i$ by $m_{i}(\nu)$ . We denote the unnormalized steady state probabilities of the restricted random growth model by $\pi_{\operatorname{RRG}}$ .

Figure 3. The state 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 in which we do not rearrange the parts in weakly decreasing order.

Remark 3.3.

In other words, the transitions randomly add or remove a box from the right of a random chosen row of the Young diagram of the partition (conditioned on rightly fitting in the $q\times p$ rectangle) as shown on the right hand side of Figure 3, then rearrange the parts in weakly decreasing order as shown on the left hand side of Figure 3.

The 1d random growth model [8] is a growth model on diagrams not necessarily arranged in weakly decreasing order. The diagrams do not need to fit in a rectangle, and the times between arrivals are independent i.i.d..

Theorem 3.4.

The projection map on state spaces $g:\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 $\Omega^{p,q}_{n}$ to the restricted random growth $\chi^{p,q}$ .

Proof.

By 2.2, we need to show that for any $\nu,\lambda$ and binary word $w$ the following equation holds:

d^{(n)}_{\nu,\lambda}=\sum_{w^{\prime}}Q((w,\nu),(w^{\prime},\lambda)).

It suffices to check this for all $\nu\neq\lambda$ . Then $Q((w,\nu),(w^{\prime},\lambda))\neq 0$ only if $w=w^{\prime}$ by 2.1, and this quantity is either $\frac{m_{i}(\nu)u}{3n}$ when $\nu\lessdot_{i}\lambda$ or $\frac{m_{i}(\nu)}{3n}$ when $\nu\gtrdot_{i}\lambda$ . ∎

Corollary 3.5.

The steady state probabilities $\{\pi_{\operatorname{RRG}}(\lambda)|\lambda\in\chi^{p,q}\}$ of the restricted random growth and the unnormalized steady state probabilities $\{\pi_{\operatorname{CBP}}(w,\lambda)|(w,\lambda)\in\Omega^{p,q}_{n}\}$ of the colored Boolean process are related as follows:

\pi_{\operatorname{RRG}}(\lambda)\propto\sum_{w\in S_{n}(1^{q}0^{n-q})}\pi_{\operatorname{CBP}}(w,\lambda).

Theorem 3.6.

The steady state probabilities $\{\pi_{\operatorname{RRG}}(\lambda)|\lambda\in\chi^{p,q}\}$ of the restricted random growth model satisfy the following relations for all partitions $\mu,\lambda\in\chi^{p,q}$ :

\frac{\pi_{\operatorname{RRG}}(\lambda)}{\pi_{\operatorname{RRG}}(\mu)}=\frac{|S_{n}(\lambda)|}{|S_{n}(\mu)|}u^{|\lambda|-|\mu|}.

Proof.

This follows from 3.4 and 2.6 and a computation on multinomial coefficients. ∎

Proof of 1.7.

This follows from 2.4, 3.4 and 3.6. ∎

4. The stationary distribution of DASEP(n,2,2)

If there were only one species of particle, i.e. $p=1$ , the stationary distribution of $\operatorname{DASEP}(n,1,q)$ is uniform. If there were only one particle, i.e., $q=1$ , then the unnormalized steady state probabilities of $\operatorname{DASEP}(n,p,1)$ are given by powers of $u$ , not involving $t$ due to cyclic symmetry. We now study the first nontrivial case of $\operatorname{DASEP}(n,p,q)$ in more detail, namely $\operatorname{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.

Theorem 4.1.

Let $(a_{k})_{k\geq 0}$ and $(b_{k})_{k\geq-1}$ be polynomial sequences in $u,t$ satisfying the recurrence relation

(3)		$\displaystyle a_{k}$	$\displaystyle=(u+2t+3)a_{k-1}-(t+1)^{2}a_{k-2}$
(4)		$\displaystyle b_{k}$	$\displaystyle=(u+2t+3)b_{k-1}-(t+1)^{2}b_{k-2}.$

with initial conditions $b_{-1}=0,a_{0}=b_{0}=1,a_{1}=u+3t+4$ .

We can fully describe the unnormalized steady state probabilities of the infinite family $\operatorname{DASEP}(n,2,2)$ as follows. When $n=2k+1$ is odd,

\begin{array}[]{|c|c|c|}\hline\cr\mu&\pi_{\operatorname{DASEP}}(\mu)\\ \hline\cr S_{n}((1,1,0,\dots,0))&a_{k}\\ \hline\cr 0\dots 010^{m}20\dots 0&ua_{k}+u(t-1)(t+1)^{m}a_{k-m-1},(0\leq m<k)\\ \hline\cr 0\dots 020^{m}10\dots 0&ua_{k}-u(t-1)(t+1)^{m}a_{k-m-1},(0\leq m<k)\\ \hline\cr S_{n}((2,2,0,\dots,0))&u^{2}a_{k}\\ \hline\cr\end{array}

When $n=2k+2$ is even,

\begin{array}[]{|c|c|c|}\hline\cr\mu&\pi_{\operatorname{DASEP}}(\mu)\\ \hline\cr S_{n}((1,1,0,\dots,0))&b_{k}\\ \hline\cr 0\dots 010^{m}20\dots 0&ub_{k}+u(t-1)(t+1)^{m}b_{k-m-1},(0\leq m\leq k)\\ \hline\cr 0\dots 020^{m}10\dots 0&ub_{k}-u(t-1)(t+1)^{m}b_{k-m-1},(0\leq m\leq k)\\ \hline\cr S_{n}((2,2,0,\dots,0))&u^{2}b_{k}\\ \hline\cr\end{array}

Proof.

We will denote $\pi_{\operatorname{DASEP}}(\mu)$ by $p_{\mu}$ for simplicity in the proof. We need to show that these formulae satisfy balance equation at each state. Let $p_{w}$ for any binary word $w$ be $x$ , then $p_{\mu}$ for $\mu\in S_{n}((2,2,0,\dots,0))$ would be equal to $u^{2}x$ by 2.6. Let $p_{\dots 10^{m}2\dots}$ be $q^{+}_{m}$ and $p_{\dots 20^{m}1\dots}$ be $q^{-}_{m}$ for $m\in[0,k]$ or $[0,k)$ . The following equations hold.

(5)	$\displaystyle(2u+t+1)x$	$\displaystyle=(t+1)x+q^{+}_{1}+q^{-}_{1}$
(6)	$\displaystyle(u+2t+2)q^{-}_{0}$	$\displaystyle=(t+1)q^{-}_{1}+(u+u^{2})x+q^{+}_{0}$
(7)	$\displaystyle(u+2t+3)q^{-}_{m}$	$\displaystyle=(t+1)q^{-}_{m+1}+(u+u^{2})x+(t+1)q^{-}_{m-1}$
(8)	$\displaystyle(t+3)u^{2}x$	$\displaystyle=(t+1)u^{2}x+u(q^{+}_{0}+q^{-}_{0})$

When $n$ is odd, Equation 7 is true for $m\in[1,k-2]$ , and we have an additional equation

(9)

\displaystyle(u+2t+3)q^{-}_{k-1}

\displaystyle=(t+1)(q^{-}_{k-2}+q^{+}_{k-1})+(u+u^{2})x.

When $n$ is even, Equation 7 is true for $m\in[1,k-1]$ , and we have an additional equation

(10)

\displaystyle(u+2t+3)q^{-}_{k}

\displaystyle=(t+1)(q^{-}_{k-1}+q^{+}_{k-1})+(u+u^{2})x.

By 1.4, we have $q^{+}_{i}+q^{-}_{i}=2ux$ for all $i$ . Applying this to Equation 5, Equation 8, and Equation 10, we see that all of them hold trivially.

To show Equation 6, we may assume $n$ is odd, since the even case would be the same. Deduce $u(u+t+3)x$ from both sides then divide both sides by $u(t-1)$ , we are left with

x-(u+2t+2)a_{k-1}=-(t+1)^{2}a_{k-2}+a_{k-1}

which is the same as

x=(u+2t+3)a_{k-1}-(t+1)^{2}a_{k-2}.

Since $x=a_{k}$ , this is true by Equation 3.

To show Equation 7, we rewrite the recurrence relations Equation 3 and Equation 4 into

(t+1)(q^{-}_{m-1}-ux)=(u+2t+3)(q^{-}_{m}-ux)-(t+1)(q^{-}_{m+1}-ux),

eliminating $x$ out of the equations, hence proving Equation 7.

To show Equation 9, we deduce $u(u+2t+3)x$ from both sides then divide both sides by $u(t-1)(t+1)^{m-1}$ so that we are left with

-(u+2t+3)=-a_{1}+t+1

which is true since $a_{1}=u+3t+4$ . ∎

Remark 4.2.

A matching in a graph is a set of pairwise non-adjacent edges. Consider matchings $M$ in the cycle graph $C_{2k+1}$ or line graph $L_{2k+1}$ with $(2k+1)$ vertices. Assign each matching $M$ a weight of $(t+1)^{|M|}(u+1)^{k-|M|}$ . Then $a_{k}$ is the sum of weights over all matchings of the cycle $C_{2k+1}$ , i.e.,

(11)

a_{k}=\sum_{M:C_{2k+1}}(t+1)^{|M|}(u+1)^{k-|M|}

and $b_{k}$ is that of the line $L_{2k+1}$ , i.e.

(12)

b_{k}=\sum_{M:L_{2k+1}}(t+1)^{|M|}(u+1)^{k-|M|}.

These can be seen via induction. The base cases can be seen in Figure 4, and Figure 5 which equal to the first rows of Table 1.

Proof.

We prove that the right hand side of Equation 11 satisfies the recurrence relation Equation 3 and the right hand side of Equation 12 satisfies Equation 4.

For the line graph $L_{2k+1}$ , we label the edges by $[2k]:=\{1,2,\dots,2k\}$ from left to right. Take a matching $M$ in the first $[2k-2]$ edges (or, in the $L_{2k-1}$ subgraph), then $M,M\cup\{2k\}$ are both matchings in $L_{2k+1}$ . However, $M\cup\{2k-1\}$ is only a matching if $2k-2\notin M$ , and if $2k-2\in M$ , then $M\setminus\{2k-2\}$ is a matching in $[2k-4]$ (or, on the $L_{2k-3}$ subgraph) because $2k-2\in M$ implies that $2k-3\notin M$ . Therefore, $[(u+1)+2(t+1)]b_{k-1}$ counts $M,M\cup\{2k-1\},M\cup\{2k\}$ for all matchings $M$ in $L_{2k-1}$ , and $(t+1)^{2}b_{k-2}$ counts the those set of edges given by $M\cup\{2k-1\}$ that are not matchings.

For the cycle graph $C_{2k+1}$ , we label the edges by $[2k+1]$ . The argument is very similar, but we have to subtract another copy of $(t+1)^{2}a_{k-2}$ which comes from the possible non-matchings given by $M\cup\{2k+1\}$ . However, if we take a matching $N$ on $\{1,\dots,2k-3\}$ , then $N\cup\{2k-1,2k+1\}$ is a matching in $C_{2k+1}$ , which is counted by $(t+1)^{2}a_{k-2}$ and added back. ∎

5. Homomesy

1.4 can be viewed as a statement about taking average of some statistic over the orbit of a group acting on the particles, which is an instance of a phenomenon called homomesy by Propp and Roby [17]. This phenomenon was first noticed by Panyushev [16] in 2007 in the context of the rowmotion action on the set of antichains of a root poset; Armstrong, Stump, and Thomas [1] proved Panyushev’s conjecture in 2011.

Definition 5.1 ([17]).

Given a set $S$ , an invertible map $\tau:S\to S$ such that each $\tau$ -orbit is finite, and a function (or “statistic”) $f:S\to K$ taking values in some field $K$ of characteristic zero, we say the triple $(S,\tau,K)$ exhibits homomesy if there exists a constant $c\in K$ such that for every $\tau$ -orbit $O\subset S$

\frac{1}{\#O}\sum_{x\in O}f(x)=c.

In this situation we say that $f$ is homomesic under the action of $\tau$ on $S$ , or more specifically $c$ -mesic.

Although the original definition concerns the action of the cyclic group generated by a single map $\tau$ , this can be generalized to the action of any finite group, as pointed out in [18, Section 2.1]. We can also generalize the definition such that the statistic $f$ takes value in a ring of polynomials (or even Laurent polynomials) over some field of characteristic zero, and the average of this statistic is equal up to a monic monomial. We make the generalized definition more precise as follows.

Definition 5.2.

Given a set $S$ , a finite group $G$ acting on $S$ with finite orbits, and a function $f:S\to R=K[x_{1},\dots,x_{n}]$ for a field $K$ of characteristic zero, we say the triple $(S,G,R)$ exhibits homomesy if there exists a polynomial $c\in R$ such that for every $G$ -orbit $O\subset S$ , there exist nonnegative integers $e^{O}_{i}\in\mathbb{Z}_{\geq 0}$ for $i=1,\dots,n$ such that

\frac{1}{\#O}\sum_{x\in O}f(x)=\prod x_{i}^{e^{O}_{i}}c.

Corollary 5.3.

Let the symmetric group $S_{q}$ acts on the states of $\operatorname{DASEP}(n,p,q)$ by permuting the $q$ positive parts (the particles). Then the triple $(\Gamma^{p,q}_{n},S_{q},\mathbb{Q}[u,t])$ exhibits homomesy with statistic $\pi_{\operatorname{DASEP}}$ in the more general sense defined above.

Proof.

The orbits of $S_{q}$ action on $\Gamma^{p,q}_{n}$ are $S_{n}^{w}(\lambda)$ for $(w,\lambda)\in\Omega^{p,q}_{n}$ . The orbit size is 1 when $\lambda=\langle 1^{q}0^{n-q}\rangle$ . Let $c=\pi_{\operatorname{DASEP}}(w)$ for any binary word $w\in S_{n}(1^{q}0^{n-q})$ and $c$ does not depend on the choice of binary word $w$ by (1) of 1.4. By (2) of 1.4, we have

\frac{1}{|S_{n}^{w}(\lambda)|}\sum_{\mu\in S_{n}^{w}(\lambda)}\pi_{\operatorname{DASEP}}=u^{|\lambda|-q}c.

∎

Corollary 5.4.

Let the symmetric group $S_{n}$ acts on the states of $\operatorname{DASEP}(n,p,q)$ by permuting the $n$ sites. Then the triple $(\Gamma^{p,q}_{n},S_{n},\mathbb{Q}[u,t])$ exhibits homomesy with statistic $\pi_{\operatorname{DASEP}}$ .

Proof.

The orbit of $S_{n}$ action are $S_{n}(\lambda)$ for $\lambda\in\chi^{p,q}$ . Let $c=\pi_{\operatorname{DASEP}}(w)$ for any binary word $w$ , and $c$ does not depend on the choice of $w$ by (1) of 1.4. Then for $\lambda=\langle 1^{q}0^{n-q}\rangle$ , we have

\frac{1}{|S_{n}(1^{q}0^{n-q})|}\sum_{w}\pi_{\operatorname{DASEP}}(w)=c

by definition of $c$ . Taking $\mu=\langle 1^{q}0^{n-q}\rangle$ , by 1.7, we have

\frac{1}{|S_{n}(\lambda)|}\sum_{\nu\in S_{n}(\lambda)}\pi_{\operatorname{DASEP}}(\nu)=u^{|\lambda|-q}c.

∎

References

[1] Drew Armstrong, Christian Stump and Hugh Thomas “A uniform bijection between nonnesting and noncrossing partitions” In Trans. Amer. Math. Soc. 365.8, 2013, pp. 4121–4151 DOI: 10.1090/S0002-9947-2013-05729-7
[2] David W. Ash “Introducing DASEP: the doubly asymmetric simple exclusion process”, 2023 arXiv:2201.00040 [math.CO]
[3] R. A. Blythe, W. Janke, D. A. Johnston and R. Kenna “The grand-canonical asymmetric exclusion process and the one-transit walk” In J. Stat. Mech. Theory Exp., 2004, pp. 001, 10
[4] R. Brak and J. W. Essam “Simple asymmetric exclusion model and lattice paths: bijections and involutions” In J. Phys. A 45.49, 2012, pp. 494007, 22 DOI: 10.1088/1751-8113/45/49/494007
[5] Sylvie Corteel, Olya Mandelshtam and Lauren Williams “From multiline queues to Macdonald polynomials via the exclusion process” In Amer. J. Math. 144.2, 2022, pp. 395–436 DOI: 10.1353/ajm.2022.0007
[6] B Derrida, M R Evans, V Hakim and V Pasquier “Exact solution of a 1D asymmetric exclusion model using a matrix formulation” In Journal of Physics A: Mathematical and General 26.7, 1993, pp. 1493 DOI: 10.1088/0305-4470/26/7/011
[7] Enrica Duchi and Gilles Schaeffer “A combinatorial approach to jumping particles: the parallel TASEP” In Random Structures Algorithms 33.4, 2008, pp. 434–451 DOI: 10.1002/rsa.20229
[8] P. L. Ferrari and H. Spohn “Random growth models” In The Oxford handbook of random matrix theory Oxford Univ. Press, Oxford, 2011, pp. 782–801
[9] Mehran Kardar, Giorgio Parisi and Yi-Cheng Zhang “Dynamic Scaling of Growing Interfaces” In Phys. Rev. Lett. 56 American Physical Society, 1986, pp. 889–892 DOI: 10.1103/PhysRevLett.56.889
[10] John G. Kemeny and J. Laurie Snell “Finite Markov chains” Reprinting of the 1960 original, Undergraduate Texts in Mathematics Springer-Verlag, New York-Heidelberg, 1976, pp. ix+210
[11] Thomas M. Liggett “Ergodic theorems for the asymmetric simple exclusion process” In Trans. Amer. Math. Soc. 213, 1975, pp. 237–261 DOI: 10.2307/1998046
[12] Thomas M. Liggett “Interacting particle systems” 276, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] Springer-Verlag, New York, 1985, pp. xv+488 DOI: 10.1007/978-1-4613-8542-4
[13] Carolyn T. MacDonald, Julian H. Gibbs and Allen C. Pipkin “Kinetics of biopolymerization on nucleic acid templates” In Biopolymers 6.1, 1968, pp. 1–25 DOI: https://doi.org/10.1002/bip.1968.360060102
[14] James B. Martin “Stationary distributions of the multi-type ASEP” In Electron. J. Probab. 25, 2020, pp. Paper No. 43, 41 DOI: 10.1214/20-ejp421
[15] C. Y. Amy Pang “Lumpings of algebraic Markov chains arise from subquotients” In J. Theoret. Probab. 32.4, 2019, pp. 1804–1844 DOI: 10.1007/s10959-018-0834-0
[16] Dmitri I. Panyushev “On orbits of antichains of positive roots” In European J. Combin. 30.2, 2009, pp. 586–594 DOI: 10.1016/j.ejc.2008.03.009
[17] James Propp and Tom Roby “Homomesy in products of two chains” In Electron. J. Combin. 22.3, 2015, pp. Paper 3.4, 29 DOI: 10.37236/3579
[18] Tom Roby “Dynamical algebraic combinatorics and the homomesy phenomenon” In Recent trends in combinatorics 159, IMA Vol. Math. Appl. Springer, [Cham], 2016, pp. 619–652 DOI: 10.1007/978-3-319-24298-9“˙25
[19] Neil J. A. Sloane and The OEIS Foundation Inc. “The on-line encyclopedia of integer sequences”, 2020 URL: http://oeis.org/?language=english
[20] Frank Spitzer “Interaction of Markov processes” In Advances in Math. 5, 1970, pp. 246–290 DOI: 10.1016/0001-8708(70)90034-4
[21] Richard P. Stanley “Enumerative combinatorics. Vol. 2” With an appendix by Sergey Fomin 208, Cambridge Studies in Advanced Mathematics Cambridge University Press, Cambridge, [2024] ©2024, pp. xvi+783