2: $m\leftarrow\textup{BATCHSIZE}$ {Pre-set Batch size}

3: $\mathbf{\mu}\leftarrow\frac{1}{n}\sum_{i=1}^{n}\mathbf{Y}_{i,\cdot}$
{Compute the mean of $\mathbf{Y}$}

4: $\mathbf{Y}_{\text{centered}}\leftarrow\mathbf{Y}-\mathbf{\mu}$ {Center the
data}

5: $\mathbf{\Sigma}\leftarrow\mathbf{0}_{d\times d}$ {Initialize the
covariance matrix}

6: for $i=0$ to $n$ step $m$ do

7: $j\leftarrow\min(i+m,n)$

8: $\mathbf{B}\leftarrow\mathbf{Y}_{\text{centered}}[i:j,\cdot]$

9: $\mathbf{\Sigma}\leftarrow\mathbf{\Sigma}+\mathbf{B}^{\top}\mathbf{B}$
{Update the covariance matrix}

10: end for

11: $\mathbf{\Sigma}\leftarrow\frac{\mathbf{\Sigma}}{n-1}$ {Normalize the
covariance matrix}

12: $\mathbf{V}\leftarrow\text{eigenvectors of }\mathbf{\Sigma}\text{
corresponding to the largest }k\text{ eigenvalues}$

13: $\mathbf{Y}_{\text{reduced}}\leftarrow\mathbf{0}_{n\times k}$ {Initialize
the reduced data matrix}

14: for $i=0$ to $n$ step $m$ do

15: $j\leftarrow\min(i+m,n)$

16: $\mathbf{B}\leftarrow\mathbf{Y}_{\text{centered}}[i:j,\cdot]$

17: $\mathbf{Y}_{\text{reduced}}[i:j,\cdot]\leftarrow\mathbf{B}\mathbf{V}$

18: end for

19: return $\mathbf{Y}_{\text{reduced}}$

Then we prove that the batch PCA we utilized here is exactly same to the
standard PCA.

###### Proof.

To prove that the Batch PCA algorithm achieves the same result as the standard
PCA, we need to show that the covariance matrix and the reduced data matrix
computed by the Batch PCA are equivalent to those computed by the standard
PCA.

First, let’s show that the covariance matrix $\mathbf{\Sigma}$ computed in the
Batch PCA is equivalent to the covariance matrix $\mathbf{C}$ in the standard
PCA.

In the standard PCA, the covariance matrix is computed as:

$\mathbf{C}=\frac{1}{n-1}\mathbf{Y}_{\text{centered}}^{T}\mathbf{Y}_{\text{centered}}$

In the Batch PCA, the covariance matrix is computed as:

$\displaystyle\mathbf{\Sigma}$
$\displaystyle=\frac{1}{n-1}\sum_{i=0}^{n-1}\mathbf{B}_{i}^{T}\mathbf{B}_{i}$
$\displaystyle=\frac{1}{n-1}\left(\mathbf{B}_{0}^{T}\mathbf{B}_{0}+\mathbf{B}_{1}^{T}\mathbf{B}_{1}+\ldots+\mathbf{B}_{b-1}^{T}\mathbf{B}_{b-1}\right)$
$\displaystyle=\frac{1}{n-1}\mathbf{Y}_{\text{centered}}^{T}\mathbf{Y}_{\text{centered}}$

where $\mathbf{B}_{i}$ is the $i$-th batch of the centered data matrix
$\mathbf{Y}_{\text{centered}}$, and $b$ is the number of batches.

Therefore, the covariance matrix computed by the Batch PCA is equivalent to
the covariance matrix computed by the standard PCA.

Next, let’s show that the reduced data matrix $\mathbf{Y}_{\text{reduced}}$
computed in the Batch PCA is equivalent to the one computed in the standard
PCA.

In the standard PCA, the reduced data matrix is computed as:

$\mathbf{Y}_{\text{reduced}}=\mathbf{Y}_{\text{centered}}\mathbf{W}$

where $\mathbf{W}$ is the matrix of the top $k$ eigenvectors of the covariance
matrix.

In the Batch PCA, the reduced data matrix is computed as:

$\displaystyle\mathbf{Y}_{\text{reduced}}$
$\displaystyle=\left[\begin{array}[]{c}\mathbf{B}_{0}\mathbf{V}\\\
\mathbf{B}_{1}\mathbf{V}\\\ \vdots\\\
\mathbf{B}_{b-1}\mathbf{V}\end{array}\right]$
$\displaystyle=\left[\begin{array}[]{c}\mathbf{Y}_{\text{centered}}[0:m,\cdot]\\\
\mathbf{Y}_{\text{centered}}[m:2m,\cdot]\\\ \vdots\\\
\mathbf{Y}_{\text{centered}}[(b-1)m:n,\cdot]\end{array}\right]\mathbf{V}$
$\displaystyle=\mathbf{Y}_{\text{centered}}\mathbf{V}$

where $\mathbf{V}$ is the matrix of the top $k$ eigenvectors of the covariance
matrix $\mathbf{\Sigma}$, and $m$ is the batch size.

Since we have shown that the covariance matrices $\mathbf{C}$ and
$\mathbf{\Sigma}$ are equivalent, their eigenvectors $\mathbf{W}$ and
$\mathbf{V}$ are also equivalent. Therefore, the reduced data matrix computed
by the Batch PCA is equivalent to the one computed by the standard PCA.

In conclusion, we have proven that the Batch PCA algorithm achieves the same
result as the standard PCA by showing that the covariance matrix and the
reduced data matrix computed by the Batch PCA are equivalent to those computed
by the standard PCA. ∎

##  Appendix O Analyze the Practical Data Augmentations

Figure 5:  A scenario of similar views targeting different targets. In some
cases, we may randomly crop two similar views from the original images as
augmentations and input them into the machine learning model. This can lead to
confusion in the model due to the differing targets assigned by humans or
generated autonomously.

Here we presents a rigorous mathematical proof demonstrating that higher data
augmentation intensity leads to increased overlap between samples from
different classes. By modeling the sample distributions and augmentation
process, we show that the variance of the augmented distributions increases
with augmentation strength, resulting in wider and more overlapping
distributions. We provide an exact calculation of the intersection point and
approximate the overlap area using the cumulative distribution function of the
standard normal distribution. Our theoretical analysis confirms the positive
correlation between data augmentation intensity and inter-class overlap rate.

###  O.1 Assumptions and Definitions

###### Assumption 1

There are two classes $C_{1}$ and $C_{2}$, with samples drawn from probability
distributions $P_{1}$ and $P_{2}$, respectively. The data augmentation
intensity is denoted by $\alpha$.

######  Definition 10 (Data Distribution and Augmentation)

The samples are satisfied $X_{1}\sim P_{1}$, $X_{2}\sim P_{2}$. The augmented
samples are represented as $X_{1}^{\prime}=X_{1}+\epsilon$ and
$X_{2}^{\prime}=X_{2}+\epsilon$, where $\epsilon$ denotes the augmentation
perturbation following the distribution $Q_{\alpha}$. The variance of
$Q_{\alpha}$ is proportional to $\alpha$.

###  O.2 Augmented Distributions

Let $P_{1,\alpha}$ and $P_{2,\alpha}$ denote the augmented sample
distributions:

$\displaystyle P_{1,\alpha}(x^{\prime})$
$\displaystyle=(P_{1}*Q_{\alpha})(x^{\prime})$ (56) $\displaystyle
P_{2,\alpha}(x^{\prime})$ $\displaystyle=(P_{2}*Q_{\alpha})(x^{\prime})$ (57)

where $*$ represents the convolution operation.

####  O.2.1 Variance of Augmented Distributions

Let $\sigma_{\alpha}^{2}$ be the variance of $Q_{\alpha}$, with
$\sigma_{\alpha}^{2}=k\alpha$, where $k$ is a constant. The variances of the
augmented distributions are:

$\displaystyle\sigma_{P_{1,\alpha}}^{2}$
$\displaystyle=\sigma_{P_{1}}^{2}+\sigma_{\alpha}^{2}=\sigma_{P_{1}}^{2}+k\alpha$
(58) $\displaystyle\sigma_{P_{2,\alpha}}^{2}$
$\displaystyle=\sigma_{P_{2}}^{2}+\sigma_{\alpha}^{2}=\sigma_{P_{2}}^{2}+k\alpha$
(59)

####  O.2.2 Overlap Rate Definition

Let $R$ denote the overlap region. The overlap rate $O(\alpha)$ is defined as:

$O(\alpha)=\int_{R}P_{1,\alpha}(x^{\prime})\,dx^{\prime}+\int_{R}P_{2,\alpha}(x^{\prime})\,dx^{\prime}$
(60)

###  O.3 Increased Variance Leads to Increased Overlap

As $\alpha$ increases, $\sigma_{\alpha}^{2}$ increases, resulting in larger
variances of $P_{1,\alpha}$ and $P_{2,\alpha}$. This makes the distributions
wider and more dispersed, increasing the overlap region.

####  O.3.1 Specific Derivation for One-Dimensional Gaussian Distributions

Assume $P_{1}$ and $P_{2}$ are two Gaussian distributions:

$\displaystyle P_{1}(x)$
$\displaystyle=\mathcal{N}(\mu_{1},\sigma_{P_{1}}^{2})$ (61) $\displaystyle
P_{2}(x)$ $\displaystyle=\mathcal{N}(\mu_{2},\sigma_{P_{2}}^{2})$ (62)

The augmented distributions are:

$\displaystyle P_{1,\alpha}(x^{\prime})$
$\displaystyle=\mathcal{N}(\mu_{1},\sigma_{P_{1}}^{2}+k\alpha)$ (63)
$\displaystyle P_{2,\alpha}(x^{\prime})$
$\displaystyle=\mathcal{N}(\mu_{2},\sigma_{P_{2}}^{2}+k\alpha)$ (64)

##### Exact Calculation of Intersection Point

Equating the two Gaussian probability density functions and solving for $x$:

$\frac{1}{\sqrt{2\pi(\sigma_{P_{1}}^{2}+k\alpha)}}\exp\left(-\frac{(x-\mu_{1})^{2}}{2(\sigma_{P_{1}}^{2}+k\alpha)}\right)=\frac{1}{\sqrt{2\pi(\sigma_{P_{2}}^{2}+k\alpha)}}\exp\left(-\frac{(x-\mu_{2})^{2}}{2(\sigma_{P_{2}}^{2}+k\alpha)}\right)$
(65)

Simplifying the equation yields an analytical solution for the intersection
point. To simplify the analysis, we assume
$\sigma_{P_{1}}^{2}=\sigma_{P_{2}}^{2}$, in which case the intersection point
is $(\mu_{1}+\mu_{2})/2$.

##### Area of Overlap Region

Let $\Delta\mu=|\mu_{1}-\mu_{2}|$. The overlap region can be represented using
the cumulative distribution function (CDF) of the standard normal
distribution, denoted as $\Phi(z)$:

$\Phi(z)=\frac{1}{2}\left[1+\text{erf}\left(\frac{z}{\sqrt{2}}\right)\right]$
(66)

The variance of the augmented distributions is
$\sigma_{\alpha}^{2}=\sigma_{P_{1}}^{2}+k\alpha$. Therefore, the approximate
area of the overlap region is:

$O(\alpha)\approx
2\Phi\left(\frac{\Delta\mu}{\sqrt{2(\sigma_{P_{1}}^{2}+k\alpha)}}\right)-1$
(67)

###  O.4 Conclusion

###### Theorem 6

As the data augmentation intensity $\alpha$ increases, the overlap rate
$O(\alpha)$ between samples from different classes increases.

###### Proof.

Increasing $\alpha$ leads to an increase in the variance of the sample
distributions, making them wider and more likely to overlap.

Specifically, increasing $\alpha$ increases $\sigma_{P_{1}}^{2}+k\alpha$ in
the denominator, thereby decreasing the argument of $\Phi(\cdot)$. Since
$\Phi(z)$ increases as $z$ decreases for $z>0$, $O(\alpha)$ increases as
$\alpha$ increases. ∎

In summary, we have rigorously proven the positive correlation between data
augmentation intensity and inter-class overlap rate from a statistical and
probabilistic perspective.

(a) Setting Minscale = $0.02$

(b) Setting Minscale = $0.04$

(c) Setting Minscale = $0.08$

(d) Setting Minscale = $0.2$

(e) Setting Minscale = $0.5$

(f) Without using Augmentation

Figure 6:  Visualization of samples with varying levels of data augmentation
intensity. We visualize the samples of 2 classes from CIFAR-10 in
2-dimensional space, respectively setting minscale in RandomResizeCrop as
$\\{0.02,0.04,0.08,0.2,0.5\\}$ and without data augmentation.

(a) Setting Minscale = $0.02$

(b) Setting Minscale = $0.04$

(c) Setting Minscale = $0.08$

(d) Setting Minscale = $0.2$

(e) Setting Minscale = $0.5$

(f) Without using Augmentation

Figure 7:  Visualization of samples with varying levels of data augmentation
intensity. We visualize the samples of 2 classes from CIFAR-100 in
2-dimensional space, respectively setting minscale in RandomResizeCrop as
$\\{0.02,0.04,0.08,0.2,0.5\\}$ and without data augmentation.

(a) Setting Minscale = $0.02$

(b) Setting Minscale = $0.04$

(c) Setting Minscale = $0.08$

(d) Setting Minscale = $0.2$

(e) Setting Minscale = $0.5$

(f) Without using Augmentation

Figure 8:  Visualization of samples with varying levels of data augmentation
intensity. We visualize the samples of 2 classes from Tiny-ImageNet in
2-dimensional space, respectively setting minscale in RandomResizeCrop as
$\\{0.02,0.04,0.08,0.2,0.5\\}$ and without data augmentation.

(a) Setting Minscale = $0.02$

(b) Setting Minscale = $0.04$

(c) Setting Minscale = $0.08$

(d) Setting Minscale = $0.2$

(e) Setting Minscale = $0.5$

(f) Without using Augmentation

Figure 9:  Visualization of samples with varying levels of data augmentation
intensity. We visualize the samples of 2 classes from ImageNet-1K in
2-dimensional space, respectively setting minscale in RandomResizeCrop as
$\\{0.02,0.04,0.08,0.2,0.5\\}$ and without data augmentation.

###  O.5 Empirical Analysis for Real-world Datasets

Beyond the theoretical analysis for a simple case, we also provide empirical
analysis for four real-world datasets under different intensities of data
augmentation. We utilize TSNE [60] to visualize the (augmented) samples in
Figure 7; 7; 8; 9. All the results demonstrate that:

  1. 1.

as minscale increases from 0.02 to 0.5, the data points gradually change from
being tightly clustered to more dispersed. This indicates that higher data
augmentation intensity expands the range of sample distribution;

  2. 2.

when minscale=0.02, the data points of the two classes exhibit significant
overlap, and the boundary becomes blurred. In contrast, larger minscale values
such as 0.2 and 0.5 allow for better separation between classes;

  3. 3.

when data augmentation is not used (the last figure), there is a clear gap
between the two classes, and the data points within each class are very
compact. This suggests that the feature distribution of the original samples
is relatively concentrated.


The asymmetric simple exclusion process (ASEP)
is a model for translation in protein synthesis and traffic flow;
it can be defined as a Markov chain
describing particles hopping on a one-dimensional lattice.

In this article
I give an overview of some of the connections of
the stationary distribution of the ASEP
to combinatorics (tableaux and multiline queues)
and special functions (Askey-Wilson polynomials,
Macdonald polynomials, and Schubert polynomials).  I also make some general
observations about  positivity in Markov chains.

The combinatorics of hopping particles and positivity in Markov chains]The combinatorics of hopping particles and positivity in Markov chains

Lauren K. Williams
Department of Mathematics, 1 Oxford Street, Cambridge,
MA 02138

§ INTRODUCTION

The goal of this article is to illustrate some of the elegant connections
between combinatorics and probability that arise when one studies Markov chains.
We will focus in particular on several variations of the
asymmetric simple exclusion process, illustrating combinatorial
formulas for its stationary distribution and connections to special functions.
The last section of this article  makes some general observations about
positivity in Markov chains, in the context of the
Markov Chain Tree Theorem.

The asymmetric simple exclusion process (or ASEP)
is a model for
particles hopping on a one-dimensional lattice
(e.g. a line or a ring) such that
each site contains at most one particle.

The ASEP was introduced independently
in biology
by Macdonald–Gibbs–Pipkin [52]
and in mathematics by Spitzer [57] around 1970, see also
It exhibits boundary-induced phase transitions,
and has been cited as a model for translation in
protein synthesis,

sequence alignment, the nuclear pore complex, and traffic flow.

The ASEP has remarkable connections to a number of topics,
including the XXZ model [56],  vertex models  [11, 12],
the Tracy-Widom distribution [41, 60],
and the KPZ equation [9, 26, 24, 18].
The ASEP is often viewed as a prototypical example of a random growth model from the
so-called KPZ universality class in $(1+1)$-dimensions, see
[43, 21, 55].

in this article we restrict our attention to the ASEP's relations

to combinatorics
staircase tableaux and multiline queues), as well as
to special functions
(including Askey-Wilson polynomials,
Macdonald polynomials,
and Schubert polynomials).
Much of this article is based on
joint works with Sylvie Corteel [28, 27, 29, 30],
as well as Olya Mandelshtam [20],
and Donghun Kim [45].

§ THE OPEN BOUNDARY ASEP

In the ASEP with open boundaries (see Figure 1),
we have a one-dimensional
lattice of $n$ sites such that each site is either empty or occupied by
a particle.  At most one particle may occupy a
given site.
We can describe it informally as follows.
During each infinitesimal time interval $\mathit{dt}$, each particle at a site
$1\leq i \leq n-1$
has a probability $\mathit{dt}$ of jumping to the next
site on its right,
provided it is empty, and each particle at a site $2\leq i \leq n$
a probability $q \mathit{dt}$ of jumping to the next site on its left,
it is empty.  Furthermore, a particle
is added at site $i=1$ with probability $\alpha \mathit{dt}$ if site $1$
is empty and a particle is removed from site $n$ with probability
$\beta \mathit{dt}$ if this site is occupied.

More formally, we define this model as a
discrete-time Markov chain.

[color=black,fill=white] (0,0) circle (3pt);
[color=black,fill=black] (.35,0) circle (3pt);
[color=black,fill=white] (.7,0) circle (3pt);
[color=black,fill=black] (1.05,0) circle (3pt);
[color=black,fill=black] (1.4,0) circle (3pt);
[color=black,fill=white] (1.75,0) circle (3pt);
[color=black,fill=black] (2.1,0) circle (3pt);
(-.15,.4) node $\alpha$;

(-.15,.2) node $\curvearrowright$;
(.85,.2) node $\curvearrowleft$;
(.9,.42) node $q$;
(1.6,.2) node $\curvearrowright$;
(1.6,.42) node $1$;
(2.25,.2) node $\curvearrowright$;
(2.3,.42) node $\beta$;

The (three-parameter) open boundary ASEP.

Let $\alpha$, $\beta$, and $q$ be constants  between $0$ and $1$.

Let $B_n$ be the set of all $2^n$ words of length $n$ in
$\{\circ, \bullet\}$.
The open boundary ASEP is the Markov chain on $B_n$ with
transition probabilities:

* If $\tau = A{\bullet}{\circ} B$ and
$\sigma = A {\circ}{ \bullet} B$ (where $A$ and $ B$ are words
in $\{\circ,\bullet\}$), then we have that
$\Pr(\tau\to \sigma) = \frac{1}{n+1}$
$\Pr(\sigma\to \tau) = \frac{q}{n+1}$ (particle hops right or left).

* If $\tau = \circ B$ and $\sigma = \bullet B$
then $\Pr(\tau\to \sigma) = \frac{\alpha}{n+1}$ (particle enters the lattice from left).

* If $\tau = B \bullet$ and $\sigma = B \circ$
then $\Pr(\tau\to \sigma) = \frac{\beta}{n+1}$ (particle exits the lattice to the right).

* Otherwise $\Pr(\tau\to \sigma) = 0$ for $\sigma \neq \tau$
and $\Pr(\tau\to \tau) = 1 - \sum_{\sigma \neq \tau} \Pr(\tau\to \sigma)$.

In the long time limit, the system reaches a steady state where all
the probabilities ${\pi}(\ttt)$ of finding
the system in configuration $\ttt$ are
stationary, i.e. satisfy

$	\frac{d}{dt} {\pi}(\tau) = 0.$

Moreover, the stationary distribution is unique.  We can compute it
by solving for the left eigenvector of the transition
matrix with eigenvalue $1$, or equivalently, by solving the
global balance equations: for all states $\tau\in B_n$, we have

\begin{equation*}
\pi(\tau) \sum_{\sigma\neq \tau} \Pr(\tau\to \sigma) =
\sum_{\sigma\neq \tau} \pi(\sigma) \Pr(\sigma\to \tau),
\end{equation*}

where both sums are over all states $\sigma\neq \tau$.

The steady state probabilities are rational expressions in
$\alpha, \beta$ and $q$.  For convenience, we clear denominators,
obtaining “unnormalized probabilities” $\Psi(\tau)$
which are equal to the $\pi(\tau)$ up to a constant: that is,
$\pi(\tau)=\frac{\Psi(\tau)}{Z_n}$, where $Z_n=Z_n(\alpha, \beta, q)$
is the partition function $\sum_{\tau\in B_n} \Psi(\tau)$.

(0,0) node (bw) $\bullet \circ$;
(-2,-1) node (ww) $\circ \circ$;
(-2.1,-.9) node (ww+) ;
(-2.1,-1.1) node (ww-) ;
(2,-1) node (bb) $\bullet \bullet$;
(2.1,-.9) node (bb+) ;
(2.1,-1.1) node (bb-) ;
(0,-2) node (wb) $\circ \bullet$;
(.1,-2) node (wb+) ;
(-.1,-2) node (wb-) ;
(.1,-.0) node (bw+) ;
(-.1,-.0) node (bw-) ;
(1.3, 0) node $\frac{\beta}{3}$;
(-1.3, 0) node $\frac{\alpha}{3}$;
(1.3, -2) node $\frac{\alpha}{3}$;
(-1.3, -2) node $\frac{\beta}{3}$;
(.5, -1) node $\frac{1}{3}$;
(-.6, -1) node $\frac{q}{3}$;

[thick, >=stealth, ->] (ww.north) .. controls +(up:7mm) and +(left:7mm) .. (bw.west);

[thick, >=stealth, ->] (bw+.south) to [out=300, in=60] (wb+.north);
[thick, >=stealth, ->] (wb-.north) to [out=120, in=240] (bw-.south);
[thick, >=stealth, ->] (bw+.north) to [out=60, in=120, looseness=6] (bw-.north);
[thick, >=stealth, ->] (wb+.south) to [out=-60, in=-120, looseness=6] (wb-.south);
[thick, >=stealth, ->] (bb+.east) to [out=45, in=-45, looseness=6] (bb-.east);
[thick, >=stealth, ->] (ww+.west) to [out=125, in=-125, looseness=6] (ww-.west);
[thick, >=stealth, ->] (bb.north) .. controls +(up:7mm) and +(right:7mm) .. (bw.east);
[thick, >=stealth, ->] (wb.west) .. controls +(left:7mm) and +(down:7mm) .. (ww.south);
[thick, >=stealth, ->] (wb.east) .. controls +(right:7mm) and +(down:7mm) .. (bb.south);

The state diagram of the open-boundary
ASEP on a lattice of $2$ sites.

shows the state diagram of the open-boundary
ASEP when $n=2$,
and <ref> gives the
corresponding unnormalized probabilities.
Therefore we have
$\pi(\bullet \bullet) = \frac{\alpha^2}{Z_2}$,
$\pi(\bullet \circ) = \frac{\alpha \beta(\alpha+\beta+q)}{Z_2}$,
$\pi(\circ \bullet) = \frac{\alpha \beta}{Z_2}$, and
$\pi(\circ \circ) = \frac{\beta^2}{Z_2}$, where
$Z_2 = \alpha^2+\alpha \beta(\alpha+\beta+q) + \alpha \beta + \beta^2$.

State $\tau$     Unnormalized probability $\Psi(\tau)$

$\bullet \bullet$     $\alpha^2$

$\bullet \circ$      $\alpha \beta(\alpha+\beta+q)$

$\circ \bullet$      $\alpha \beta$

$\circ \circ$     $\beta^2$

Probabilities for the open-boundary
ASEP on a lattice of $2$ sites.

For $n=3$,

if we again write
each probability $\pi(\tau)=\frac{\Psi(\tau)}{Z_3}$,
we find that
$Z_3(\alpha,\beta,q)$ is a polynomial which is
manifestly positive – that it, it has
only positive coefficients.  Also, $Z_3$ has
$24$ terms (counted with multiplicity):
$Z_3(1, 1, 1) = 24$.
Computing more examples quickly leads to the conjecture
that the partition function
$Z_n=Z_n(\alpha,\beta,q)$ is a (manifestly) positive polynomial with
$(n-1)$! terms.

In algebraic combinatorics,  if a quantity of interest is known or believed
to be a positive integer or a polynomial with positive coefficients,  one seeks an
interpretation of this quantity as counting some combinatorial objects.  For example,
one seeks to express such a polynomial as a generating function for certain
tableaux or graphs or permutations, etc.
A prototypical example is the Schur polynomial $s_{\lambda}(x_1,\dots,x_n)$ [58]: there are several
formulas for it, including the bialternant formula and the Jacobi-Trudi formula, but both of
these involve determinants and neither
makes it obvious that the Schur polynomial has positive coefficients.  However, one can express
the Schur polynomial as the generating function for semistandard tableaux of shape $\lambda$,
and this formula makes manifest the positivity of coefficients [58].

Given the above, and
our observations on the positivity of the partition function $Z_n(\alpha,\beta,q)$,
the natural question is:

can we express each probability
as a (manifestly positive) sum over some set of combinatorial objects?
We will explain how to answer this question using (a special case of)
the staircase
tableaux of [30].

§.§ The open-boundary ASEP and $\alpha \beta$-staircase tableaux

In what follows,
we will depict Young diagrams
in Russian notation (with the corner at the bottom).

An  $\alpha \beta$-staircase tableau $T$ of size $n$ is a
Young diagram of shape $(n, n-1, \dots, 2, 1)$
(drawn in Russian notation)
such that each box is either empty
or contains an $\alpha$ or $\beta$, such that:

* no box in the top row is empty

* each box southeast of a $\beta$ and in the same diagonal
as that $\beta$ is empty.

* each box southwest of an $\alpha$ and in the same diagonal
as that $\alpha$ is empty.

See Figure 3.

It is an exercise to verify that
there are  $(n+1)!$ $\alpha \beta$-staircase tableaux
of size $n$.

(0,.4) node $\circ$;
(.4,.4) node $\bullet$;
(.8,.4) node $\circ$;
(1.2,.4) node $\bullet$;
(1.6,.4) node $\bullet$;
(2,.4) node $\circ$;
(2.4,.4) node $\bullet$;
(0,0) node $\beta$;
(.4,0) node $\alpha$;

(.8,0) node $\beta$;
(1.2,0) node $\alpha$;
(1.2,-.8) node $\alpha$;
(1.6,0) node $\alpha$;

(1.8,-.2) node $\beta$;
(2,0) node $\beta$;
(2.4,0) node $\alpha$;

(0,0) node $\beta$;
(.4,0) node $\alpha$;
(.6,-.2) node $q$;
(.8,0) node $\beta$;
(1.2,0) node $\alpha$;
(1.2,-.8) node $\alpha$;
(1.6,0) node $\alpha$;
(1.6,-.4) node $q$;
(1.8,-.2) node $\beta$;
(2,0) node $\beta$;
(2.4,0) node $\alpha$;

At left: an $\alpha\beta$-staircase tableau $T$
of type $(\circ \bullet \circ \bullet \bullet
\circ \bullet)$. At right: $T$
with a $q$ in each unrestricted box.
We have $\wt(T)=\alpha^5 \beta^4 q^2$.

Some boxes in a tableau
are forced to be empty because of conditions (2) or (3) above;
we refer

to all other empty boxes as unrestricted.  (The
boxes are  those whose nearest neighbors on the diagonals
to the northwest and northeast, respectively, are an $\alpha$ and $\beta$.)

After placing a $q$
in each unrestricted box, we define the
weight $\wt(T)$ of $T$ to be
$\alpha^i \beta^j q^k$ where $i, j$ and $k$ are the
numbers of $\alpha$'s, $\beta$'s, and $q$'s in $T$.

The type of $T$ is the word
obtained by reading the letters in the top row of $T$
and replacing each $\alpha$ by $\bullet$ and $\beta$ by
see Figure 3.

The following result [28, 27, 30]
gives a combinatorial formula for the steady state
probabilities of the ASEP.  (Note that [28, 27] used
permutation tableaux, which are in bijection with staircase tableaux,
and are closely connected to the positive Grassmannian.)
The $q=0$ case was previously
studied by Duchi–Schaeffer in [36].

Consider the ASEP with open boundaries on a lattice of $n$ sites.
Let $\tau=(\tau_1,\dots, \tau_n)\in \{\bullet,\circ\}^n$ be
a state.  Then the
unnormalized steady state probability $\Psi(\tau)$ is equal to
$\sum_T \wt(T)$, where the sum is over the
$\alpha \beta$-staircase tableaux of type $\tau$.

Equivalently, if
we let $\mathcal{T}_n$ be the set of $\alpha \beta$-staircase
tableaux of size $n$, and  $Z_n:= \sum_{T\in \mathcal{T}_n} \wt(T)$
be the weight generating function for these tableaux, then
the	steady state probability $\pi(\tau)$
is $\frac{\sum_T \wt(T)}{Z_n}$, where the sum is over the
$\alpha \beta$-staircase tableaux of type $\tau$.

In the case $n=2$, there are six tableaux of size
$2$, shown in Figure 4 and arranged by type.   Computing the weights
of the tableaux of the various types reproduces the
results from <ref>.

(0,.4) node $\bullet$;
(.4,.4) node $\bullet$;
(0,0) node $\alpha$;
(.4,0) node $\alpha$;

(0,.4) node $\bullet$;
(.4,.4) node $\circ$;
(0,0) node $\alpha$;
(.2,-.2) node $\alpha$;
(.4,0) node $\beta$;

(0,.4) node $\bullet$;
(.4,.4) node $\circ$;
(0,0) node $\alpha$;
(.2,-.2) node $\beta$;
(.4,0) node $\beta$;

(0,.4) node $\bullet$;
(.4,.4) node $\circ$;
(0,0) node $\alpha$;
(.2,-.2) node $q$;
(.4,0) node $\beta$;

(0,.4) node $\circ$;
(.4,.4) node $\bullet$;
(0,0) node $\beta$;
(.4,0) node $\alpha$;

(0,.4) node $\circ$;
(.4,.4) node $\circ$;
(0,0) node $\beta$;
(.4,0) node $\beta$;

The six $\alpha\beta$-staircase tableau $T$
of size $2$.

§.§ Lumping of Markov chains

Given  a combinatorial formula such as <ref>, how can we prove it?
One option is to realize the ASEP as a lumping (or projection) of
a Markov chain on tableaux [27].
(See also [36] for the case $q=0$.)

Recall that
we have a surjection
$f:\mathcal{T}_n \to B_n$, which maps an
$\alpha \beta$-staircase tableau
to its type.

We'd like to construct a Markov chain

on tableaux whose projection via $f$ recovers the ASEP.

If we can do so, and moreover show that
the steady state probability $\pi(T)$

is proportional to $\wt(T)$, then
we will have proved <ref>.

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

\begin{equation} \label{eq:lumping}
\sum_{x: f(x)=y_1} P(x_0,x) = Q(y_0, y_1).
\end{equation}

Then $\{f(X_t)\}$  is a Markov chain on
$\Omega_Y$ with transition matrix $Q$.

We say that $\{f(X_t)\}$ is a
(strong) lumping

of $\{X_t\}$ and
$\{X_t\}$ is a
(strong) lift of $\{f(X_t)\}$.

Suppose	$\pi$ is a stationary distribution
for $\{X_t\}$, and
let $\pi_f$ be the measure on $\Omega_Y$ defined by
$\pi_f(y) = \sum_{x: f(x)=y} \pi(x)$. Then $\pi_f$
is a stationary distribution for $\{f(X_t)\}$.

See [44, 53] for a thorough discussion of

The ASEP can be lifted to a Markov chain on $\alpha \beta$-staircase
tableaux [27], see Figure 5.
In each diagram, the grey boxes
represent boxes that must be empty.  Note
that the
remaining empty boxes on the left and right side of a “$\mapsto$”
are in bijection with each other; they must be filled the
same way.
The lifted chain has the
particularly nice property that the left hand side of (<ref>)
always has at most one nonzero term.

(.2,-.2) node [draw,scale=.7,diamond,fill=gray!30];
(.4,-.4) node [draw,scale=.7,diamond,fill=gray!30];
(.6,-.6) node [draw,scale=.7,diamond,fill=gray!30];
(.8,-.8) node [draw,scale=.7,diamond,fill=gray!30];
(1,-1) node [draw,scale=.7,diamond,fill=gray!30];
(1.2,-1.2) node [draw,scale=.7,diamond,fill=gray!30];
(0,.4) node $\circ$;
(.4,.4) node $\bullet$;
(.8,.4) node $\bullet$;
(1.2,.4) node $\bullet$;
(1.6,.4) node $\circ$;
(-.2,.6) node $\curvearrowright$;
(0,0) node $\beta$;
(.4,0) node $\alpha$;
(.8,0) node $\alpha$;
(1.2,0) node $\alpha$;
(1.6,0) node $\beta$;
(2.2,.4) node $\cdots$;
(2.8,-.7) node $\alpha$;
(2.8,-.9) node $\mapsto$;

(.6,-.6) node [draw,scale=.7,diamond,fill=gray!30];
(.8,-.4) node [draw,scale=.7,diamond,fill=gray!30];
(1,-.2) node [draw,scale=.7,diamond,fill=gray!30];
(1.6,-.4) node [draw,scale=.7,diamond,fill=gray!30];
(1.8,-.6) node [draw,scale=.7,diamond,fill=gray!30];
(0,.4) node $\bullet$;
(.4,.4) node $\bullet$;
(.8,.4) node $\bullet$;
(1.2,.4) node $\bullet$;
(1.6,.4) node $\circ$;
(0,0) node $\alpha$;
(.4,0) node $\alpha$;
(.8,0) node $\alpha$;
(1.2,0) node $\alpha$;
(1.4,-.2) node $\beta$;
(1.6,0) node $\beta$;
(2.2,.4) node $\cdots$;

(.6,-.6) node [draw,scale=.7,diamond,fill=gray!30];
(.8,-.4) node [draw,scale=.7,diamond,fill=gray!30];
(1.4,-.2) node [draw,scale=.7,diamond,fill=gray!30];
(1.6,-.4) node [draw,scale=.7,diamond,fill=gray!30];
(1.8,-.6) node [draw,scale=.7,diamond,fill=gray!30];
(0,.4) node $\bullet$;
(.4,.4) node $\circ$;

(1,.6) node $\curvearrowright$;
(.8,.4) node $\bullet$;
(1.2,.4) node $\circ$;

(1.8,.4) node $\cdots$;

(0,0) node $\alpha$;
(.4,0) node $\beta$;
(.8,0) node $\alpha$;
(1,-.2) node $\alpha$;
(1.2,0) node $\beta$;

(2.8,-.7) node $1$;
(2.8,-.9) node $\mapsto$;

(.6,-.2) node [draw,scale=.7,diamond,fill=gray!30];
(.8,-.4) node [draw,scale=.7,diamond,fill=gray!30];
(1,-.6) node [draw,scale=.7,diamond,fill=gray!30];
(1.2,-.8) node [draw,scale=.7,diamond,fill=gray!30];
(1.4,-1) node [draw,scale=.7,diamond,fill=gray!30];

(0,.4) node $\bullet$;
(.4,.4) node $\circ$;
(.8,.4) node $\circ$;
(1.2,.4) node $\bullet$;

(1.8,.4) node $\cdots$;
(0,0) node $\alpha$;
(.2,-.2) node $\alpha$;
(.4,0) node $\beta$;
(.8,0) node $\beta$;

(1.2,0) node $\alpha$;

(1.2,-1.2) node [draw,scale=.7,diamond,fill=gray!30];
(1.4,-1) node [draw,scale=.7,diamond,fill=gray!30];
(1.6,-.8) node [draw,scale=.7,diamond,fill=gray!30];
(1.8,-.6) node [draw,scale=.7,diamond,fill=gray!30];
(2,-.4) node [draw,scale=.7,diamond,fill=gray!30];
(2.2,-.2) node [draw,scale=.7,diamond,fill=gray!30];
(.2,.4) node $\cdots$;

(.8,.4) node $\bullet$;
(1.2,.4) node $\circ$;
(1.6,.4) node $\circ$;
(2,.4) node $\circ$;
(2.4,.4) node $\bullet$;
(2.6,.6) node $\curvearrowright$;
(.8,0) node $\alpha$;

(1.2,0) node $\beta$;
(1.6,0) node $\beta$;
(2,0) node $\beta$;
(2.4,0) node $\alpha$;
(-.2,.6) node ;
(2.85,-.65) node $\beta$;
(2.8,-.9) node $\mapsto$;

(.6,-.6) node [draw,scale=.7,diamond,fill=gray!30];
(.8,-.4) node [draw,scale=.7,diamond,fill=gray!30];
(1.4,-.2) node [draw,scale=.7,diamond,fill=gray!30];
(1.6,-.4) node [draw,scale=.7,diamond,fill=gray!30];
(1.8,-.6) node [draw,scale=.7,diamond,fill=gray!30];

(.2,.4) node $\cdots$;
(.8,.4) node $\bullet$;
(1.2,.4) node $\circ$;
(1.6,.4) node $\circ$;
(2,.4) node $\circ$;
(2.4,.4) node $\circ$;
(.8,0) node $\alpha$;
(1,-.2) node $\alpha$;
(1.2,0) node $\beta$;
(1.6,0) node $\beta$;
(2,0) node $\beta$;
(2.4,0) node $\beta$;

(.4,-.4) node [draw,scale=.7,diamond,fill=gray!30];
(.6,-.2) node [draw,scale=.7,diamond,fill=gray!30];
(1.2,-.4) node [draw,scale=.7,diamond,fill=gray!30];
(1.4,-.6) node [draw,scale=.7,diamond,fill=gray!30];
(1.6,-.8) node [draw,scale=.7,diamond,fill=gray!30];

(.2,.4) node $\cdots$;
(1,.6) node $\curvearrowright$;
(.8,.4) node $\bullet$;
(1.2,.4) node $\circ$;
(1.6,.4) node $\bullet$;
(2,.4) node $\circ$;

(.8,0) node $\alpha$;
(1,-.2) node $\beta$;
(1.2,0) node $\beta$;
(1.6,0) node $\alpha$;
(2,0) node $\beta$;

(2.8,-.7) node $1$;
(2.8,-.9) node $\mapsto$;

(.8,-.8) node [draw,scale=.7,diamond,fill=gray!30];
(1,-.6) node [draw,scale=.7,diamond,fill=gray!30];
(1.2,-.4) node [draw,scale=.7,diamond,fill=gray!30];
(2,-.4) node [draw,scale=.7,diamond,fill=gray!30];
(1.4,-.2) node [draw,scale=.7,diamond,fill=gray!30];
(.2,.4) node $\cdots$;

(.8,.4) node $\circ$;
(1.2,.4) node $\bullet$;

(1.6,.4) node $\bullet$;
(2,.4) node $\circ$;
(.8,0) node $\beta$;

(1.2,0) node $\alpha$;
(1.6,0) node $\alpha$;
(1.8,-.2) node $\beta$;
(2,0) node $\beta$;

(.6,-.6) node [draw,scale=.7,diamond,fill=gray!30];
(.8,-.4) node [draw,scale=.7,diamond,fill=gray!30];
(1,-.2) node [draw,scale=.7,diamond,fill=gray!30];
(1.2,-.4) node [draw,scale=.7,diamond,fill=gray!30];
(1.4,-.6) node [draw,scale=.7,diamond,fill=gray!30];
(1.6,-.8) node [draw,scale=.7,diamond,fill=gray!30];

(.2,.4) node $\cdots$;

(1,.6) node $\curvearrowleft$;
(.8,.4) node $\circ$;
(1.2,.4) node $\bullet$;

(2,.4) node $\cdots$;

(.8,0) node $\beta$;

(1.2,0) node $\alpha$;

(2.8,-.7) node $q$;
(-.2,.6) node ;
(2.8,-.9) node $\mapsto$;

(.4,-.4) node [draw,scale=.7,diamond,fill=gray!30];
(.6,-.2) node [draw,scale=.7,diamond,fill=gray!30];
(1.4,-.2) node [draw,scale=.7,diamond,fill=gray!30];
(1.6,-.4) node [draw,scale=.7,diamond,fill=gray!30];
(1.8,-.6) node [draw,scale=.7,diamond,fill=gray!30];

(.2,.4) node $\cdots$;
(.8,.4) node $\bullet$;
(1.2,.4) node $\circ$;

(2,.4) node $\cdots$;

(.8,0) node $\alpha$;
(1,-.2) node $q$;
(1.2,0) node $\beta$;

(.4,-.4) node [draw,scale=.7,diamond,fill=gray!30];
(.6,-.2) node [draw,scale=.7,diamond,fill=gray!30];
(1.4,-.2) node [draw,scale=.7,diamond,fill=gray!30];
(1.6,-.4) node [draw,scale=.7,diamond,fill=gray!30];
(1.8,-.6) node [draw,scale=.7,diamond,fill=gray!30];

(.2,.4) node $\cdots$;
(1,.6) node $\curvearrowright$;
(.8,.4) node $\bullet$;
(1.2,.4) node $\circ$;

(2,.4) node $\cdots$;

(.8,0) node $\alpha$;
(1,-.2) node $q$;
(1.2,0) node $\beta$;
(2.8,-.7) node $1$;
(2.8,-.9) node $\mapsto$;

(.6,-.6) node [draw,scale=.7,diamond,fill=gray!30];
(.8,-.4) node [draw,scale=.7,diamond,fill=gray!30];
(1,-.2) node [draw,scale=.7,diamond,fill=gray!30];
(1.2,-.4) node [draw,scale=.7,diamond,fill=gray!30];
(1.4,-.6) node [draw,scale=.7,diamond,fill=gray!30];
(1.6,-.8) node [draw,scale=.7,diamond,fill=gray!30];

(.2,.4) node $\cdots$;

(.8,.4) node $\circ$;
(1.2,.4) node $\bullet$;

(2,.4) node $\cdots$;

(.8,0) node $\beta$;

(1.2,0) node $\alpha$;

Transitions in the Markov chain on tableaux.

If we identify $\alpha$'s and $\beta$'s inside the tableaux
with particles and holes, then
the chain on tableaux reveals a circulation of particles and holes
in the second row of the tableaux; this is similar to a phenomenon
observed in [36].

§.§ The Matrix Ansatz

One can also  prove <ref> using

the following Matrix Ansatz, first introduced by
Derrida, Evans, Hakim and Pasquier [32].[[32]
stated this result with $c=1$, but we will use
a representation with $c=\alpha \beta$ in order to
prove <ref>.]

Consider the ASEP with open boundaries
on a lattice of $n$ sites.
Suppose that $D$ and $E$ are matrices,  $|V\rangle$ is a column vector,
$\langle W|$ is a row vector, and $c$ is a constant,
such that:

\begin{align}
& DE - qED = c(D+E) \label{eq:1} \\
& \beta D|V\rangle =  c |V\rangle \label{eq:2} \\
%\hspace{.3cm} \text{ and }
& \alpha \langle W|E =  c \langle W| \label{eq:3}
\end{align}

If we identify $\tau = (\tau_1,\dots,\tau_n)\in \{0,1\}^n$ with a state
(by mapping $1$ and $0$ to $\bullet$ and $\circ$, respectively), then
the steady state probability $\pi(\tau)$ is equal to

\begin{equation*}
{\pi}(\ttt) = \frac{\langle W|(\prod_{i=1}^n (\ttt_i D + (1-\ttt_i)E))|V\rangle}{\langle W|(D+E)^n|V\rangle}.
\end{equation*}

For example,  the steady state probability of
state $\circ \bullet \circ \bullet \bullet \circ \bullet$ is
$\frac{\langle W|EDEDDED|V\rangle}{\langle W|(D+E)^7|V\rangle}$.

We note that <ref>  does not
imply that a solution $D, E, |V\rangle, \langle W|$ exists nor that it is unique.
Indeed there are multiple solutions, which in general involve
infinite-dimensional matrices.

To prove <ref> using the Matrix Ansatz, we let

$D_1=(d_{ij})$ be the
(infinite) upper-triangular matrix with rows and columns
indexed by $\mathbb{Z}^+$,

defined by

$	d_{i,i+1} =\alpha$ and  $d_{ij}=0 \text{ for }j\neq i+1.$
$E_1=(e_{ij})$ be the (infinite) lower-triangular matrix defined by
$e_{ij}=0$ for $j>i$ and

\begin{equation*}
e_{ij}=\beta^{i-j+1}(q^{j-1} {i-1 \choose j-1} + \alpha \sum_{r=0}^{j-2} {i-j+r \choose r} q^r)
\text{ for }j\leq i.
\end{equation*}

That is,

\begin{equation*}
D_1=\left( \begin{array}{ccccc}
0 & \alpha & 0 & 0 & \dots \\
0 & 0 & \alpha & 0 & \dots \\
0 & 0 & 0 & \alpha & \dots \\
0 & 0 & 0 & 0 & \dots \\
\vdots & \vdots & \vdots & \vdots &
\end{array} \right)
\text{ and }
E_1 =  \left( \begin{array}{ccccc}
\beta & 0 & 0 &   \dots \\
\beta^2 & \beta(\alpha+q) & 0 &  \dots \\
\beta^3 & \beta^2(\alpha+2 q) &  \beta (\alpha+\alpha q+ q^2) &
\dots \\
\beta^4  & \beta^3 (\alpha +3 q) &
\beta^2(\alpha+2\alpha q+3 q^2)  &  \dots \\
\vdots & \vdots & \vdots &
\end{array} \right).
\end{equation*}

We also define the (infinite) row and column vectors
$\langle W_1|=(1,0,0,\dots )$ and  $|V_1 \rangle= (1,1,1,\dots )^t$.
Then one can check that
$D_1, E_1, \langle W_1|, |V_1\rangle$ satisfy
(<ref>), (<ref>), and (<ref>),
with $c = \alpha \beta$.
One can also show
$D_1$ and $E_1$ are transfer matrices whose products enumerate
$\alpha \beta$-staircase tableaux.
For example,
$\langle W_1|E_1D_1E_1D_1D_1E_1D_1|V_1\rangle$  enumerates the staircase tableaux
of type
$\circ \bullet \circ \bullet \bullet \circ \bullet$.
Now <ref> implies <ref>.

§.§ Generalization to the five-parameter open boundary ASEP

More generally, we would like to understand a generalized ASEP
in which particles can both enter and exit the lattice at the left
(at rates $\alpha$, $\gamma$), and exit and enter the lattice
at the right (at rates $\beta$, $\delta$).  There is a version of the
Matrix Ansatz for this setting [32], as well as suitable tableaux filled with
$\alpha, \beta, \gamma$ and $\delta$'s
(which we will simply call staircase tableaux)

[color=black,fill=white] (0,0) circle (3pt);
[color=black,fill=black] (.35,0) circle (3pt);
[color=black,fill=white] (.7,0) circle (3pt);
[color=black,fill=black] (1.05,0) circle (3pt);
[color=black,fill=black] (1.4,0) circle (3pt);
[color=black,fill=white] (1.75,0) circle (3pt);
[color=black,fill=black] (2.1,0) circle (3pt);
(-.15,.4) node $\alpha$;
(-.15,-.65) node $\gamma$;
(-.15,-.4) node $\swingleft$;
(-.15,.2) node $\curvearrowright$;
(.85,.2) node $\curvearrowleft$;
(.9,.42) node $q$;
(1.6,.2) node $\curvearrowright$;
(1.6,.42) node $1$;
(2.25,.2) node $\curvearrowright$;
(2.25,-.4) node $\swingleft$;
(2.3,.42) node $\beta$;
(2.3,-.65) node $\delta$;

The (five-parameter) open boundary ASEP.

staircase tableau

$T$ of size $n$ is a
Young diagram of shape $(n, n-1, \dots, 2, 1)$
such that each box is either empty
or contains an $\alpha$, $\beta$, $\gamma$, or $\delta$ such that:

* no box in the top row is empty

* each box southeast of a $\beta$ or $\delta$ and in the same diagonal
as that $\beta$ or $\delta$ is empty.

* each box southwest of an $\alpha$ or $\gamma$ and in the same diagonal
as that $\alpha$ or $\gamma$ is empty.

(0,.4) node $\circ$;
(.4,.4) node $\bullet$;
(.8,.4) node $\circ$;
(1.2,.4) node $\bullet$;
(1.6,.4) node $\bullet$;
(2,.4) node $\circ$;
(2.4,.4) node $\bullet$;
(0,0) node $\gamma$;
(.4,0) node $\alpha$;

(.8,0) node $\beta$;
(.8,-.4) node $\gamma$;
(1.2,0) node $\delta$;
(1.2,-.8) node $\delta$;

(1.6,0) node $\alpha$;

(2,0) node $\beta$;
(2,-.4) node $\alpha$;
(2.4,0) node $\delta$;

(0,0) node $\gamma$;
(.4,0) node $\alpha$;
(.4,-.4) node $q$;
(.6,-.2) node $q$;
(.6,-.6) node $q$;

(.8,0) node $\beta$;
(.8,-.4) node $\gamma$;
(1.2,0) node $\delta$;
(1.4,-.2) node $q$;
(1.6,-.4) node $q$;
(1.8,-.6) node $q$;
(1.2,-.8) node $\delta$;
(1.4,-1) node $q$;

(1.6,0) node $\alpha$;
(1.8,-.2) node $q$;

(2,0) node $\beta$;
(2,-.4) node $\alpha$;
(2.4,0) node $\delta$;

At left: a staircase tableau $T$
of type $(\circ \bullet \circ \bullet \bullet
\circ \bullet)$. At right: $T$
with a $q$ in the appropriate boxes.
We have $\wt(T)=\alpha^3 \beta^2
\gamma^2 \delta^3 q^8$.

See Figure 7 for an example.
It is an exercise to verify that there are exactly $4^n n!$ staircase tableaux
of size $n$.

We call an empty box of a staircase tableau $T$
distinguished  if either:

$\bullet$ its nearest neighbor on the diagonal to the northwest
is a $\delta$, or

$\bullet$ its nearest neighbor on the diagonal to the northwest
is an $\alpha$ or $\gamma$, and its nearest neighbor
on the diagonal to the northeast is a $\beta$ or $\gamma$.

After placing a $q$ in each distinguished box,
we define the
weight $\wt(T)$ of $T$ to be the product of all
letters in the boxes of $T$.

The type of $T$ is the word
obtained by reading the letters in the top row of $T$
and replacing each $\alpha$ or $\delta$
by $\bullet$, and each $\beta$ or $\gamma$ by
see Figure 7.

The following result from [29, 30]
subsumes <ref>.  It can be proved using
a suitable generalization
of the Matrix Ansatz.

Consider the ASEP with open boundaries on a lattice of $n$ sites
as in Figure 6.

Let $\tau\in \{\bullet,\circ\}^n$ be
a state.  Then the
unnormalized steady state probability $\Psi(\tau)$ is equal to

$\sum_T \wt(T)$, where the sum is over the
staircase tableaux of type $\tau$.

Remarkably, there is another solution to the Matrix Ansatz,
found earlier by Uchiyama, Sasamoto, and Wadati [61], which makes
use of orthogonal polynomials.  More specifically, one can find a
solution where $D$ and $E$ are tridiagonal matrices, such that the  rows of
$D+E$ encode
the three-term recurrence relation characterizing the
Askey-Wilson polynomials;
are a family of orthogonal polynomials
$p_n(x; a, b, c, d|q)$ which are at the top of the hierarchy of
classical one-variable orthogonal polynomials (including
the others as special or limiting cases)

The connection of Askey-Wilson polynomials with the ASEP via [61]
leads to applications on both sides.  On the one hand,

it facilitates the
computation of physical quantities in the ASEP
such as the  phase diagram [61];
it also leads to a relation between the ASEP
and the Askey-Wilson stochastic process [13].
On the other hand, this connection has applications to the
combinatorics of Askey-Wilson
moments.  Since the 1980's there has been a great deal of
work on the combinatorics
of classical orthogonal polynomials (e.g. Hermite, Charlier, Laguerre)

[62, 40, 19];
the connection of staircase tableaux to ASEP, and of ASEP to Askey-Wilson polynomials, led
to the first combinatorial formula for moments of Askey-Wilson polynomials [30, 25].

Even more generally, one can study a version of the ASEP
with open boundaries in which there are different species
of particles.  This version is closely connected
[15, 31, 17]
Koornwinder polynomials  [42],
a family of multivariate orthogonal polynomials
which generalize Askey-Wilson polynomials.

§ THE (MULTISPECIES) ASEP ON A RING

It is also natural to consider the ASEP on

a lattice of
sites arranged in a ring, of which some sites

are occupied by a particle.  Each particle in the system can
jump to the next site either clockwise or counterclockwise,
provided that this site is empty.
In this model,

the resulting stationary distribution
is always the uniform distribution.   This motivates
considering a multispecies generalization of the ASEP,
in which particles come with different weights, which in
turn influence the hopping rates.

§.§ The multispecies ASEP, multiline queues,  and Macdonald polynomials

[->,main node/.style=circle,draw=black, thick, fill=white,font=]
[very thick] (0,0) circle (1.25cm);
[draw=none, minimum size=2.5cm, regular polygon, regular polygon sides=6] (s) ;
[draw=none, minimum size=3.3cm, regular polygon, regular polygon sides=24] (b) ;
[draw=none, minimum size=4.2cm, regular polygon, regular polygon sides=72] (outer) ;
[shift=(outer.corner 2)] $1$;
[shift=(outer.corner 13)] $t$;
[shift=(outer.corner 25)] $1$;
[shift=(outer.corner 38)] $1$;
[shift=(outer.corner 49)] $t$;
[shift=(outer.corner 60)] $1$;
[main node][shift=(s.corner 1)]
[main node][shift=(s.corner 2)] $1$;
[main node][shift=(s.corner 3)] $5$;
[main node][shift=(s.corner 4)] $3$;
[main node][shift=(s.corner 5)] $2$;
[main node][shift=(s.corner 6)] $6$;
[thick, >=stealth, <->](b.corner 24) to [out=90, in=90] (b.corner 3);
[thick, >=stealth, <->](b.corner 4) to [out=150, in=150] (b.corner 7);
[thick, >=stealth, <->](b.corner 8) to [out=210, in=210] (b.corner 11);
[thick, >=stealth, <->](b.corner 12) to [out=270, in=270] (b.corner 15);
[thick, >=stealth, <->](b.corner 16) to [out=330, in=330] (b.corner 19);
[thick, >=stealth, <->](b.corner 20) to [out=30, in=30] (b.corner 23);

[main node/.style=circle,draw=black, very thick, fill=white,font=]
(0,0) node $\cdot$;
(0,.8) node $\cdot$;
(0,1.6) node $\cdot$;
[circle,draw, thick] at (0,2.4)$6$;
(0,3.2) node $\cdot$;
[circle,draw, thick] at (1,0)$4$;
[circle,draw, thick] at (1,.8)$4$;
[circle,draw, thick] at (1,1.6)$4$;
(1,2.4) node $\cdot$;
(1,3.2) node $\cdot$;
[circle,draw, thick] at (2,0)$6$;
[circle,draw, thick] at (2,.8)$6$;
[circle,draw, thick] at (2,1.6)$6$;
[circle,draw, thick] at (2,2.4)$5$;
(2,3.2) node $\cdot$;
[circle,draw, thick] at (3,0)$2$;
(3,.8) node $\cdot$;
[circle,draw, thick] at (3,1.6)$5$;
(3,2.4) node $\cdot$;
[circle,draw, thick] at (3,3.2)$6$;
[circle,draw, thick] at (4,0)$3$;
[circle,draw, thick] at (4,.8)$3$;
(4,1.6) node $\cdot$;
(4,2.4) node $\cdot$;
(4,3.2) node $\cdot$;
[circle,draw, thick] at (5,0)$5$;
[circle,draw, thick] at (5,.8)$5$;
(5,1.6) node $\cdot$;
(5,2.4) node $\cdot$;
(5,3.2) node $\cdot$;
[black,very thick](1,1.1)–(1,1.3);
(0,-.7) node ;
[black,very thick](1,.3)–(1,.5);
[black,very thick](2,1.1)–(2,1.3);
[black,very thick](2,.3)–(2,.5);
[black,very thick](5,.3)–(5,.5);
[black,very thick](4,.3)–(4,.5);
[thick, >=stealth](.3,2.4) to [out=0, in=120] (1.7,1.6);
[very thick, >=stealth](2.3,2.4) to [out=-30, in=140] (2.7,1.6);
[very thick, >=stealth](3.3,1.6) to [out=0, in=120] (4.7,.8);
[very thick, >=stealth](3.3,3.2) to [out=0, in=150] (5,2.9);
[very thick, >=stealth](-.7,2.6) to [out=-30, in=150] (-.3,2.4);

The mASEP on a ring
with $\lambda = (6,5,4,3,2,1)$, and a multiline queue of
type $(1,4,6,2,3,5)$.

In the multispecies ASEP (mASEP) on a ring, two neighboring
particles exchange places at rates $1$ or $t$, depending
on whether the heavier particle is clockwise or
counterclockwise from the lighter one.

Let $t$ be a constant such that $0 \leq t \leq 1$, and
let $\lambda = \lambda_1 \geq \lambda_2 \geq \dots
\geq \lambda_n \geq 0$
be a partition.
Let $B_n(\lambda)$
be the set of all words of length $n$
obtained by permuting the parts of $\lambda$.

The multispecies ASEP

on a ring
is the Markov chain on $B_n(\lambda)$
with transition probabilities:

* If $\mu = (\mu_1,\dots,\mu_n)$ and $\nu$ are in $B_n(\lambda)$,
and $\nu$ is obtained from $\mu$ by swapping
$\mu_i$ and $\mu_{i+1}$ for some $i$ (indices considered modulo $n$),
$\Pr(\mu \to \nu) = \frac{t}{n}$ if $\mu_i>\mu_{i+1}$ and
$\Pr(\mu \to \nu) = \frac{1}{n}$ if $\mu_i<\mu_{i+1}$.

* Otherwise $\Pr(\mu \to \nu) = 0$ for $\nu \neq \mu$ and
$\Pr(\mu \to \mu) = 1-\sum_{\nu \neq \mu} \Pr(\mu \to \nu)$.

We think of the parts of $\lambda$
as representing various types of
particles of different weights.

As before, one would like to find an expression for each steady
state probability  as a manifestly positive
sum over some set of combinatorial objects.
One may give such a
formula in terms of Ferrari-Martin's
multiline queues shown in Figure 8,
see [51, 20].

One fascinating aspect

of the multispecies
ASEP on a ring is its close relation [16]
to Macdonald polynomials $P_{\lambda}(x_1,\dots,x_n; q,t)$ [50],
a remarkable family of polynomials that generalize
Schur polynomials, Hall-Littlewood polynomials, and Jack
polynomials.   The next result
follows  from [16] and [20].

Let $\mu \in B_n(\lambda)$ be a state of the
mASEP on a ring.  Then the steady state probability

where $\Psi({\mu})$
is obtained from a permuted basement
Macdonald polynomial and
is obtained from the Macdonald polynomial
$P_{\lambda}$ by specializing
$q=1$ and $x_1=x_2=\dots=x_n=1$.

The following table shows the  probabilities of the mASEP when
$\lambda=(4,3,2,1)$.  Note that because of the circular symmetry in the mASEP,
e.g. $\pi(1,2,3,4)=\pi(2,3,4,1)=\pi(3,4,1,2)=\pi(4,1,2,3)$, it suffices to list
the probabilities for the states $w$ with $w_1=1$.

State $w$     Unnormalized probability $\Psi(w)$

1234     $9t^3+7t^2+7t+1$

1243     $3(t^3+3t^2+3t+1)$

1324     $3t^3+11t^2+5t+5$

1342     $3(t^3+3t^2+3t+1)$

1423     $5t^3+5t^2+11t+3$

1432     $t^3+7t^2+7t+9$

Probabilities for the
mASEP when $\lambda=(4,3,2,1)$.

In light of
<ref> and the connection to multiline queues,
it is natural to ask if one can give a formula for Macdonald
polynomials in terms of multiline queues.   This is indeed possible,
see [20] for details.

We remark that there is a family of
Macdonald polynomials associated to any affine root system;
the “ordinary” Macdonald polynomials discussed in this section
are those of type $\tilde{A}$.  It is interesting that they
are related to particles hopping on a ring (which
an affine $A$ Dynkin diagram).  Meanwhile, the Koornwinder
polynomials from the previous section
are the
polynomials attached to the non-reduced affine root system
of type
It is interesting that they are related to particles hopping
on a line with open boundaries (which

resembles a Dynkin diagram of type

We note that there
are other connections between probability and Macdonald polynomials, including
Macdonald processes [8], and
a Markov chain on partitions whose
eigenfunctions are coefficients of Macdonald polynomials [35].
There is also a variation of the exclusion process called the
multispecies zero range process, whose stationary distribution
is related to
modified Macdonald polynomials

§.§ The inhomogeneous TASEP, multiline queues,
and Schubert polynomials

multispecies generalization
of the exclusion process
on a ring is the inhomogeneous totally asymmetric exclusion
process (TASEP).  In this model, two adjacent particles with weights
$i$ and $j$ with $i<j$
can swap places only if the heavier one is clockwise
of the lighter one, and in this case, they exchange places at
rate $x_i-y_j$,
see Figure 9.

[->,main node/.style=circle,draw=black, thick, fill=white,font=]
[very thick] (0,0) circle (1.25cm);
[draw=none, minimum size=2.5cm, regular polygon, regular polygon sides=6] (s) ;
[draw=none, minimum size=3.3cm, regular polygon, regular polygon sides=24] (b) ;
[draw=none, minimum size=4.2cm, regular polygon, regular polygon sides=72] (outer) ;
[shift=(outer.corner 2)] $x_1-y_4$;
[shift=(outer.corner 25)] $x_3-y_5$;
[shift=(outer.corner 38)] $x_2-y_3$;
[shift=(outer.corner 60)] $x_4-y_6$;
[main node][shift=(s.corner 1)]
[main node][shift=(s.corner 2)] $1$;
[main node][shift=(s.corner 3)] $5$;
[main node][shift=(s.corner 4)] $3$;
[main node][shift=(s.corner 5)] $2$;
[main node][shift=(s.corner 6)] $6$;
[thick, >=stealth, <->](b.corner 24) to [out=90, in=90] (b.corner 3);

[thick, >=stealth, <->](b.corner 8) to [out=210, in=210] (b.corner 11);
[thick, >=stealth, <->](b.corner 12) to [out=270, in=270] (b.corner 15);

[thick, >=stealth, <->](b.corner 20) to [out=30, in=30] (b.corner 23);

inhomogeneous multispecies TASEP on a ring,
with $\lambda = (6,5,4,3,2,1)$.

Let $x_1,\dots,x_n$ and $y_1,\dots,y_n$ be constants
such that $0<x_i-y_j\leq 1$ for all $i,j$,
and let $\lambda = \lambda_1 \geq \lambda_2 \geq \dots
\geq \lambda_n \geq 0$
be a partition.
Let ${B}_n(\lambda)$
be the set of all words of length $n$
obtained by permuting the parts of $\lambda$.

The inhomogeneous TASEP
on a ring
is the Markov chain on ${B}_n(\lambda)$
with transition probabilities:

* If $\mu = (\mu_1,\dots,\mu_n)$ and $\nu$
are in ${B}_n(\lambda)$,

and $\nu$ is obtained from $\mu$ by swapping
$\mu_i$ and $\mu_{i+1}$ for some $i$
(indices considered mod $n$),
$\Pr(\mu \to \nu) = \frac{x_{\mu_i}-y_{\mu_j}}{n}$ if $\mu_i<\mu_{i+1}$.

* Otherwise $\Pr(\mu \to \nu) = 0$ for $\nu \neq \mu$ and
$\Pr(\mu \to \mu) = 1-\sum_{\nu \neq \mu} \Pr(\mu \to \nu)$.

When $y_i=0$ for all $i$, there is a
formula for the stationary distribution of the
inhomogeneous TASEP in terms of multiline queues; this can
be proved using a version of the Matrix Ansatz

Recall that the mASEP on a ring is closely connected to
Macdonald polynomials.  Curiously, when $y_i=0$ the inhomogeneous TASEP on a ring
is related to Schubert polynomials, a family of polynomials which give
polynomial representatives for the Schubert classes in the
cohomology ring of  the
complete flag variety.  For example, many (unnormalized) steady
state probabilities are equal to products of Schubert polynomials
[14, 45], and all of them are conjecturally
positive sums of Schubert polynomials [49].

Given $w=(w_1,\dots,w_n)$ a permutation in the symmetric group $S_n$ and $p=(p_1,\dots,p_m)\in S_m$ with $m<n$, we say that $w$ contains $p$ if $w$ has a
subsequence of length $m$ whose letters are in the same relative order as those of $p$.
For example, the permutation $({\mathbf{3}}, 2, \mathbf{6}, 5, \mathbf{1} , \mathbf{4})$ contains the pattern
$(2,4,1,3)$ because its letters $3,6,1,4$ have the same relative
order as those of $(2,4,1,3)$.
If $w$ does not contain $p$ we say that $w$ avoids $p$.
We say that $w\in S_n$ is evil-avoiding if $w$ avoids the patterns
$(2,4,1,3), (4,1,3,2), (4,2,1,3)$ and $(3,2,1,4)$.[We call these permutations evil-avoiding because if one
replaces $i$ by $1$, $e$ by $2$, $l$ by $3$, and $v$ by $4$,
then evil and its anagrams vile, veil and leiv become the four patterns $2413, 4132, 4213$ and $3214$.  (Leiv is a name of Norwegian origin meaning “heir.”)]

We have the following result, see [45] for details.

Let $\lambda=(n,n-1,\dots,1)$ so that the inhomogeneous TASEP can be viewed
as a Markov chain on the $n!$ permutations of the set $\{1,2,\dots,n\}$.
Let $w\in S_n$ be a permutation with $w_1=1$ which is evil-avoiding, and let
$k$ be the number of descents of $w^{-1}$.
Then the steady state probability $\pi(w)$

$$\pi(w) = \frac{\Psi(w)}{Z_n},$$

where $\Psi(w)$ is a monomial in $x_1,\dots,x_{n-1}$
times a product of $k$ Schubert polynomials,
and $Z_n = \prod_{i=1}^n h_{n-i}(x_1,x_2,\dots,x_{i-1},x_i,x_i)$
with $h_i$ the complete homogeneous symmetric polynomial.

The following table shows the  probabilities of the inhomogeneous
TASEP when

State $w$     Unnormalized probability $\Psi(w)$

1234     $x_1^3  x_2$

1243     $x_1^2(x_1 x_2 + x_1 x_3+x_2 x_3) = x_1^2 \Sym_{1342}$

1324     $x_1(x_1^2 x_2 + x_1 x_2^2+x_1^2 x_3 + x_1 x_2 x_3 + x_2^2 x_3) =                  x_1 \Sym_{1432}$

1342     $x_1 x_2 (x_1^2+x_1 x_2 + x_2^2) = x_1 x_2 \Sym_{1423}$

1423     $x_1^2 x_2 (x_1+x_2+x_3) = x_1^2  x_2 \Sym_{1243}$

1432     $(x_1^2+x_1 x_2+x_2^2)(x_1 x_2+x_1 x_3+x_2 x_3) = \Sym_{1423} \Sym_{1342}$

Probabilities for the
inhomogeneous TASEP when $\lambda=(4,3,2,1)$.

For general $y_i$, there is a version of <ref>
involving double Schubert polynomials [45].

Very often, beautiful combinatorial properties
go hand-in-hand with integrability of a model.
While this topic goes beyond the scope of
this article, the reader can learn about
integrability and the exclusion process from [14, 22],

or more generally
about integrable probability from [10].

§ POSITIVITY IN MARKOV CHAINS

The reader may at this point wonder how general is the phenomenon of positivity in
Markov chains?
That is, how often can one express the steady state probabilities of a Markov chain
in terms of polynomials with all coefficients positive
(ideally as a sum over combinatorial objects)?

In some sense, the answer to this question is all the time:
the Markov Chain Tree Theorem gives a formula for the stationary
distribution of a finite-state irreducible Markov chain as a positive
sum indexed by rooted trees
of the state diagram.  However, the number of terms of this formula grows fast
very quickly! (By Cayley's formula,
the complete graph on $n$ vertices has $n^{n-2}$ spanning trees.)
Moreover, for many Markov chains, there is a
common factor which can be removed from the above formula for the
stationary distribution, resulting in a more
compact formula.  Sometimes the more compact formula involves polynomials
with negative coefficients.

Let $G$ be the state diagram of a finite-state irreducible Markov chain whose
set of states is $V$.
That is, $G$ is a weighted directed graph with vertices $V$,  with an edge $e$ from
$i$ and $j$  weighted $\Pr(e):=\Pr(i,j)$ whenever the probability $\Pr(i,j)$ of going
from state $i$ to $j$ is positive.
We call a connected subgraph $T$ a spanning tree rooted at $r$
if $T$ includes every vertex of $V$, $T$ has no cycle, and all edges of $T$
point towards the root $r$.  (Irreducibility of the Markov chain implies that for
each vertex $r$, there is a spanning tree rooted at $r$.)
Given a spanning tree $T$, we define its weight as
$\wt(T):=\prod_{e\in T} \Pr(e).$

The stationary distribution of a finite-state irreducible Markov chain is proportional
to the measure that assigns the state $\tau$ the
“unnormalized probability”

$$\Psi(\tau):= \sum_{\rt(T)=\tau} \wt(T).$$

That is, the steady state probability $\pi(\tau)$ equals
$\pi(\tau) = \frac{\Psi(\tau)}{\mathbf{Z}},$
where $\mathbf{Z} = \sum_{\tau} \Psi(\tau)$.

<ref> first appeared in [39]
and was proved for general Markov chains in [48].
It has by now many proofs, one of which involves lifting the Markov chain to a chain on the trees
themselves; the result then follows from

Kirchhoff's Matrix Tree Theorem.

and references therein.

Consider the Markov chain with five states $1,\dots,5$,
whose transition matrix is as follows:

\begin{equation}
\begin{bmatrix}
\frac{2-q}{3} & 0 & \frac{1}{3} & \frac{q}{3} & 0\\
0 & \frac{2}{3} & 0 & 0 & \frac{1}{3}\\
\frac{q}{3} & \frac{1}{3} & \frac{1-q}{3} & 0 & \frac{1}{3}\\
\frac{1}{3} & \frac{q}{3} & 0 & \frac{2-2q}{3} & \frac{q}{3} \\
0 & 0 & \frac{q}{3} & \frac{1}{3} & \frac{2-q}{3}
\end{bmatrix}
\end{equation}

The state diagram  is shown in Figure 10.
(We have omitted the factors of $\frac{1}{3}$
from each
transition probability
as they do not affect
the eigenvector of the transition matrix).
We also omitted the loops
at each state.

[main node/.style=circle,draw=black, thick, fill=white,font=]

[circle,draw, thick] at (1,1.6)$1$;
[circle,draw, thick] at (1,0)$4$;
[circle,draw, thick] at (2,.8)$5$;
[circle,draw, thick] at (3,0)$2$;
[circle,draw, thick] at (3,1.6)$3$;
[>=stealth, ->,black,thick](3, 1.3)–(3,0.4);
(3.2,.85) node $1$;
[>=stealth, ->,black,thick](1.3,0)–(2.6,0);
(1.95,-.2) node $q$;
[>=stealth, ->,black,thick](2.7,.3)–(2.3,.6);
(2.6,.55) node $1$;
[>=stealth, ->, black, thick](2.7,1.4) to [out=240, in=30] (2.3,1);
(2.6,1.1) node $1$;
[>=stealth, ->, black, thick](2.25,1.05) to [out=90, in=200] (2.65,1.45);
(2.25,1.3) node $q$;
[>=stealth, ->, black, thick](1.7,0.6) to [out=240, in=30] (1.3,.2);
(1.6,.3) node $1$;
[>=stealth, ->, black, thick](1.25,0.25) to [out=90, in=200] (1.65,0.65);
(1.35,.6) node $q$;
[>=stealth, ->, black, thick](.95,0.3) to [out=100, in=250] (.95,1.3);
(.8,.8) node $1$;
[>=stealth, ->, black, thick](1.05,1.3) to [out=-70, in=80] (1.05,.3);
(1.2,.8) node $q$;
[>=stealth, ->, black, thick](1.3,1.6) to [out=-20, in=190] (2.6,1.6);
(2,1.4) node $1$;
[>=stealth, ->, black, thick](2.6,1.7) to [out=170, in=10] (1.3,1.7);
(2,1.9) node $q$;

[main node/.style=circle,draw=black, thick, fill=white,font=]
[circle,draw, thick] at (1,1.6)$1$;
[circle,draw, thick] at (1,0)$4$;
[circle,draw, thick] at (2,.8)$5$;
[circle,draw, thick] at (3,0)$2$;
[circle,draw, thick] at (3,1.6)$3$;

[>=stealth, ->,black,thick](2.7,.3)–(2.3,.6);
(2.6,.55) node $1$;

[>=stealth, ->, black, thick](2.25,1.05) to [out=90, in=200] (2.65,1.45);
(2.25,1.3) node $q$;

[>=stealth, ->, black, thick](1.25,0.25) to [out=90, in=200] (1.65,0.65);
(1.35,.6) node $q$;

[>=stealth, ->, black, thick](2.6,1.7) to [out=170, in=10] (1.3,1.7);
(2,1.9) node $q$;

The state diagram
from <ref>, plus a spanning tree rooted at $1$ with weight $q^3$.

If one applies <ref>, one finds e.g. that there are
six spanning trees rooted at state $1$, with weights
$q^3, q^3, q^2, q, 1,$ and $1$.  Adding up these contributions gives
$\Psi(1) = 2q^3+q^2+q+2$.  Computing the spanning trees
rooted at the other states gives rise to the
unnormalized probabilities $\Psi(\tau)$ for the
stationary distribution shown in <ref>.

State $\tau$     Unnormalized probability $\Psi(\tau)$

$1$     $2q^3+q^2+q+2$

$2$     $q^4+3q^3+4q^2+3q+1$

$3$      $2q^3+2q^2+q+1$

$4$      $q^3+q^2+2q+2$

$5$     $2q^3+4q^2+4q+2$

Unnormalized probabilities for the Markov
chain from <ref> as given by the Markov Chain Tree Theorem.

Note that the unnormalized probabilities from <ref> share a common factor of $(q+1)$.
Dividing by this common factor gives the  (more compact)
unnormalized probabilities $\overline{\Psi}(\tau)$ shown in

State $\tau$     Unnormalized probability $\overline{\Psi}(\tau)$

$1$     $2q^2-q+2$

$2$     $q^3+2q^2+2q+1$

$3$      $2q^2+1$

$4$      $q^2+2$

$5$     $2q^2+2q+2$

Unnormalized probabilities from
after dividing by the joint
common factor $(q+1)$.

We see that when we write the stationary distribution in
“lowest terms,” we obtain a vector of polynomials which do not have
only nonnegative coefficients.

This example motivates the following definitions.

Consider a measure
on the
set $\{1,2,\dots,n\}$ in which each component
$\Psi_i(q_1,\dots,q_N)$ is a
polynomial in $\Z[q_1,\dots,q_N]$.[We don't require
that $\sum_i \Psi_i = 1$; to obtain a probability distribution
we can just divide each term by $Z:=\sum_i \Psi_i$.]
We say  the formula
is manifestly positive if
all coefficients
$\Psi_i$ are positive for all $i$.
And we say
is compact
if there is no polynomial $\phi(q_1,\dots,q_N)\neq 1$ which divides  all the

<ref> shows that every finite-state Markov chain has
a manifestly positive formula for the stationary distribution.
Meanwhile, <ref> shows that in general this formula
is not compact, and

there are Markov chains whose
compact formula for the stationary distribution  is
not manifestly positive.

In light of <ref>,
it is interesting to revisit

e.g. the stationary distribution

the open boundary ASEP

with parameters
$\alpha$, $\beta$, and $q$.
One can use <ref> to express the components
$\Psi_{\tab}(\tau)$ of the stationary measure
as a sum over the tableaux of type $\tau$.
On the other hand, one can use <ref>
to express the components $\Psi_{\tree}(\tau)$ of the stationary measure
as a sum over spanning trees rooted at $\tau$
of the state diagram.
Both $\Psi_{\tab}(\tau)$ and $\Psi_{\tree}(\tau)$ are polynomials
in $\alpha, \beta, q$ with positive coefficients; however,
the former is compact, and has many fewer terms than the latter.
Because the stationary measure is unique (up to an overall scalar),
for each $n$ there
is a polynomial $Q_n(\alpha,\beta,q)$ such that
$\frac{\Psi_{\tree}(\tau)}{\Psi_{\tab}(\tau)}=Q_n(\alpha, \beta,q)$
for all $\tau\in \{0,1\}^n$.  The number of terms in $Q_n$ appears in

$n$     $Q_n(1, 1, 1)$

$2$     $1$

$3$     $4$

$2285015040 $

$11335132600511975880768000 $

The ratio of the numbers of terms between the Markov Chain Tree theorem
formula and the staircase tableaux formula for the stationary
distribution of the (three-parameter) open boundary ASEP on
a lattice of $n$ sites.

It would be interesting to reprove e.g. <ref>

using the Markov Chain Tree Theorem.

We note that the analysis of the ASEP and its variants would be easier
if these Markov chains were reversible; in general
they are not (except for special cases of the parameters).  Nevertheless
there has been progress on the mixing time of the ASEP,
see [37] and references therein.

Besides the ASEP,
there are other interesting Markov chains
arising in statistical mechanics whose stationary distributions admit

positive formulas as sums over combinatorial objects
(which are often compact).

These include
the Razumov-Stroganov

[33, 34, 23],
the Tsetlin library
[59, 38],
and many
other models of interacting particles [1, 4], see also

§.§ Acknowledgements

I am grateful to
Sylvie Corteel, Olya Mandelshtam, and Donghyun Kim for some very
stimulating and enjoyable collaborations.
I would also like to thank
Arvind Ayyer, Alexei Borodin, Ivan Corwin, Jim Pitman, and Jim Propp for
their comments on earlier drafts of this manuscript, which greatly
improved the exposition.
This work was partially supported by the National Science Foundation

No. DMS-1854316 and No. DMS-1854512.

$'$ $'$

[1]
Arvind Ayyer and Kirone Mallick.
Exact results for an asymmetric annihilation process with open
J. Phys. A, 43(4):045003, 22, 2010.

[2]
Chikashi Arita and Kirone Mallick.
Matrix product solution of an inhomogeneous multi-species TASEP.
J. Phys. A, 46(8):085002, 11, 2013.

[3]
Arvind Ayyer, Olya Mandelshtam, and James Martin.
Modified Macdonald polynomials and the multispecies zero range
process: I, 2020.
Preprint, .

[4]
Arvind Ayyer and Philippe Nadeau.
Combinatorics of a disordered two-species asep on a torus, 2021.
Preprint, .

[5]
Venkat Anantharam and Pantelis Tsoucas.
Stochastic concavity of throughput in series of queues with finite
Adv. in Appl. Probab., 22(3):761–763, 1990.

[6]
Richard Askey and James Wilson.
Some basic hypergeometric orthogonal polynomials that generalize
Jacobi polynomials.
Mem. Amer. Math. Soc., 54(319):iv+55, 1985.

[7]
Arvind Ayyer.
Interacting particle systems and symmetric functions, 2022.
Talk at FPSAC, .

[8]
A. Borodin and I. Corwin.
Macdonald processes.
In XVIIth International Congress on Mathematical
Physics, pages 292–316. World Sci. Publ., Hackensack, NJ, 2014.

[9]
Lorenzo Bertini and Giambattista Giacomin.
Stochastic Burgers and KPZ equations from particle systems.
Comm. Math. Phys., 183(3):571–607, 1997.

[10]
Alexei Borodin and Vadim Gorin.
Lectures on integrable probability.
In Probability and statistical physics in St. Petersburg,
volume 91 of Proc. Sympos. Pure Math., pages 155–214. Amer. Math.
Soc., Providence, RI, 2016.

[11]
Alexei Borodin and Leonid Petrov.
Higher spin six vertex model and symmetric rational functions.
Selecta Math. (N.S.), 24(2):751–874, 2018.

[12]
Alexei Borodin and Michael Wheeler.
Colored stochastic vertex models and their spectral theory, 2018.
Preprint, .

[13]
Wł odek Bryc and Jacek Wesoł owski.
Asymmetric simple exclusion process with open boundaries and
quadratic harnesses.
J. Stat. Phys., 167(2):383–415, 2017.

[14]
Luigi Cantini.
Inhomogenous multispecies TASEP on a ring with spectral parameters,

[15]
L. Cantini.
Asymmetric simple exclusion process with open boundaries and
Koornwinder polynomials.
Ann. Henri Poincaré, 18(4):1121–1151, 2017.

[16]
Luigi Cantini, Jan de Gier, and Michael Wheeler.
Matrix product formula for Macdonald polynomials.
J. Phys. A, 48(38):384001, 25, 2015.

[17]
Luigi Cantini, Alexandr Garbali, Jan de Gier, and Michael Wheeler.
Koornwinder polynomials and the stationary multi-species asymmetric
exclusion process with open boundaries.
J. Phys. A, 49(44):444002, 23, 2016.

[18]
Ivan Corwin and Alisa Knizel.
Stationary measure for the open KPZ equation, 2021.
Preprint, .

[19]
Sylvie Corteel, Jang Soo Kim, and Dennis Stanton.
Moments of orthogonal polynomials and combinatorics.
In Recent trends in combinatorics, volume 159 of IMA Vol.
Math. Appl., pages 545–578. Springer, [Cham], 2016.

[20]
Sylvie Corteel, Olya Mandelshtam, and Lauren Williams.
From multiline queues to Macdonald polynomials via the exclusion
process, 2022.
to appear in Amer. J. Math.

[21]
Ivan Corwin.
The Kardar-Parisi-Zhang equation and universality class.
Random Matrices Theory Appl., 1(1):1130001, 76, 2012.

[22]
N. Crampe, E. Ragoucy, and M. Vanicat.
Integrable approach to simple exclusion processes with boundaries.
Review and progress.
J. Stat. Mech. Theory Exp., (11):P11032, 42, 2014.

[23]
Luigi Cantini and Andrea Sportiello.
A one-parameter refinement of the Razumov-Stroganov
J. Combin. Theory Ser. A, 127:400–440, 2014.

[24]
Ivan Corwin and Hao Shen.
Open ASEP in the weakly asymmetric regime.
Comm. Pure Appl. Math., 71(10):2065–2128, 2018.

[25]
S. Corteel, R. Stanley, D. Stanton, and L. Williams.
Formulae for Askey-Wilson moments and enumeration of staircase
Trans. Amer. Math. Soc., 364(11):6009–6037, 2012.

[26]
Ivan Corwin, Hao Shen, and Li-Cheng Tsai.
${\rm ASEP}(q,j)$ converges to the KPZ equation.
Ann. Inst. Henri Poincaré Probab. Stat., 54(2):995–1012,

[27]
Sylvie Corteel and Lauren Williams.
A Markov chain on permutations which projects to the PASEP.
Int. Math. Res. Not. IMRN, (17):Art. ID rnm055, 27, 2007.

[28]
Sylvie Corteel and Lauren Williams.
Tableaux combinatorics for the asymmetric exclusion process.
Adv. in Appl. Math., 39(3):293–310, 2007.

[29]
Sylvie Corteel and Lauren K. Williams.
Staircase tableaux, the asymmetric exclusion process, and
Askey-Wilson polynomials.
Proc. Natl. Acad. Sci. USA, 107(15):6726–6730, 2010.

[30]
Sylvie Corteel and Lauren K. Williams.
Tableaux combinatorics for the asymmetric exclusion process and
Askey-Wilson polynomials.
Duke Math. J., 159(3):385–415, 2011.

[31]
Sylvie Corteel and Lauren K. Williams.
Macdonald-Koornwinder moments and the two-species exclusion
Selecta Math. (N.S.), 24(3):2275–2317, 2018.

[32]
B. Derrida, M. R. Evans, V. Hakim, and V. Pasquier.
Exact solution of a $1$D asymmetric exclusion model using a
matrix formulation.
J. Phys. A, 26(7):1493–1517, 1993.

[33]
P. Di Francesco.
A refined Razumov-Stroganov conjecture.
J. Stat. Mech. Theory Exp., (8):009, 16, 2004.

[34]
Jan de Gier and Vladimir Rittenberg.
Refined Razumov-Stroganov conjectures for open boundaries.
J. Stat. Mech. Theory Exp., (9):009, 14, 2004.

[35]
Persi Diaconis and Arun Ram.
A probabilistic interpretation of the Macdonald polynomials.
Ann. Probab., 40(5):1861–1896, 2012.

[36]
Enrica Duchi and Gilles Schaeffer.
A combinatorial approach to jumping particles.
J. Combin. Theory Ser. A, 110(1):1–29, 2005.

[37]
Nina Gantert, Evita Nestoridi, and Dominik Schmid.
Mixing times for the simple exclusion process with open boundaries,
Preprint, .

[38]
W. J. Hendricks.
The stationary distribution of an interesting Markov chain.
J. Appl. Probability, 9:231–233, 1972.

[39]
T.L. Hill.
Studies in irreversible thermodynamics iv. diagrammatic
representation of steady state fluxes for uni-molercular systems.
J. Theoret. Biol., 10:442–459, 1966.

[40]
Mourad E. H. Ismail, Dennis Stanton, and Gérard Viennot.
The combinatorics of $q$-Hermite polynomials and the
Askey-Wilson integral.
European J. Combin., 8(4):379–392, 1987.

[41]
Kurt Johansson.
Shape fluctuations and random matrices.
Comm. Math. Phys., 209(2):437–476, 2000.

[42]
Tom H. Koornwinder.
Askey-Wilson polynomials for root systems of type $BC$.
In Hypergeometric functions on domains of positivity, Jack
polynomials, and applications (Tampa, FL, 1991), volume 138 of Contemp. Math., pages 189–204. Amer. Math. Soc., Providence, RI, 1992.

[43]
M. Kardar, G. Parisi, and Y. Zhang.
Dynamic scaling of growing interfaces.
Phys. Rev., (56), 1986.

[44]
John G. Kemeny and J. Laurie Snell.
Finite Markov chains.
The University Series in Undergraduate Mathematics. D. Van Nostrand
Co., Inc., Princeton, N.J.-Toronto-London-New York, 1960.

[45]
Donghyun Kim and Lauren Williams.
Schubert polynomials, the inhomogeneous TASEP, and evil-avoiding
permutations, 2021.

[46]
Thomas M. Liggett.
Interacting particle systems, volume 276 of Grundlehren
der mathematischen Wissenschaften [Fundamental Principles of Mathematical
Springer-Verlag, New York, 1985.

[47]
Russell Lyons and Yuval Peres.
Probability on trees and networks, volume 42 of Cambridge
Series in Statistical and Probabilistic Mathematics.
Cambridge University Press, New York, 2016.

[48]
Frank Thomson Leighton and Ronald L. Rivest.
Estimating a probability using finite memory.
In Foundations of computation theory (Borgholm, 1983), volume
158 of Lecture Notes in Comput. Sci., pages 255–269. Springer, Berlin,

[49]
Thomas Lam and Lauren Williams.
A Markov chain on the symmetric group that is Schubert positive?
Exp. Math., 21(2):189–192, 2012.

[50]
I. G. Macdonald.
Symmetric functions and Hall polynomials.
Oxford Mathematical Monographs. The Clarendon Press, Oxford
University Press, New York, second edition, 1995.

[51]
James B. Martin.
Stationary distributions of the multi-type ASEP.
Electron. J. Probab., 25:Paper No. 43, 41, 2020.

[52]
J. Macdonald, J. Gibbs, and A. Pipkin.
Kinetics of biopolymerization on nucleic acid templates.
Biopolymers, 6, 1968.

[53]
C. Y. Amy Pang.
Lumpings of algebraic Markov chains arise from subquotients.
J. Theoret. Probab., 32(4):1804–1844, 2019.

[54]
Jim Pitman and Wenpin Tang.
Tree formulas, mean first passage times and Kemeny's constant of a
Markov chain.
Bernoulli, 24(3):1942–1972, 2018.

[55]
Jeremy Quastel.
Introduction to KPZ.
In Current developments in mathematics, 2011, pages 125–194.
Int. Press, Somerville, MA, 2012.

[56]
S. Sandow.
Partially asymmetric exclusion process with open boundaries.
Phys. Rev., (E50), 1994.

[57]
Frank Spitzer.
Interaction of Markov processes.
Advances in Math., 5:246–290, 1970.

[58]
Richard P. Stanley.
Enumerative combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics.
Cambridge University Press, Cambridge, 1999.
With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin.

[59]
M.L. Tsetlin.
Finite automata and models of simple forms of behavior.
Russian Mathematical Surveys, 18:1–28, 1963.

[60]
Craig A. Tracy and Harold Widom.
Asymptotics in ASEP with step initial condition.
Comm. Math. Phys., 290(1):129–154, 2009.

[61]
Masaru Uchiyama, Tomohiro Sasamoto, and Miki Wadati.
Asymmetric simple exclusion process with open boundaries and
Askey-Wilson polynomials.
J. Phys. A, 37(18):4985–5002, 2004.

[62]
Gérard Viennot.
A combinatorial theory for general orthogonal polynomials with
extensions and applications.
In Orthogonal polynomials and applications (Bar-le-Duc,
1984), volume 1171 of Lecture Notes in Math., pages 139–157.
Springer, Berlin, 1985.

Lauren K. Williams

Lauren K. Williams is the Robinson Professor of Mathematics at Harvard University and the Seaver Professor at the Radcliffe Institute.  Her main research interests are in algebraic combinatorics, but
she gets considerable inspiration from mathematical physics.  Lauren grew up in California, the oldest of four girls; she now lives in Cambridge
with her spouse and children.

[5] V. Anantharam, P. Tsoucas,
A proof of the Markov chain tree theorem,
Stat. Prob. Letters 8 (1989), 189–192.

[2] C. Arita, K. Mallick,
Matrix product solution of an
inhomogeneous multi-species TASEP,
J. Phys. A 46 (2013).

[10] A. Borodin, V. Gorin, Lectures on integrable
probability, Probability and statistical physics
in St. Petersburg, 155–214, Proc. Sympos. Pure Math.
91 Amer. Math. Soc., Providence, RI, 2016.

[14] L. Cantini,
Inhomogeneous multispecies TASEP on a ring with spectral
Preprint 2016, arXiv:1602.07921.

[16] L. Cantini, J. de Gier, M. Wheeler,
Matrix product formula for Macdonald polynomials,
J. Phys. A 48 (2015).

[15] L. Cantini,
Asymmetric simple exclusion process with open
boundaries and Koornwinder polynomials,
Ann. Henri Poincaré, 18 (2017),

[20] S. Corteel, O. Mandelshtam, L. Williams,
From multiline queues to Macdonald polynomials
via the exclusion process, to appear in Amer. J. Math.

[28] S. Corteel, L. Williams,
Tableaux combinatorics for the asymmetric exclusion process,
Adv. Appl. Math. 39 (2007) 293–310.

[27] S. Corteel, L. Williams,
A Markov chain on permutations which projects to the PASEP (with Sylvie Corteel),
Inter. Math. Res. Not. 2007, no 17, 27pp.

[30] S. Corteel, L. Williams,
Tableaux combinatorics for the asymmetric exclusion process
and Askey-Wilson polynomials,
Duke Math. J. 159 (2011) 385–415.

[31] S. Corteel, L. Williams,
Macdonald- Koornwinder moments and the two-species exclusion
process, Selecta Math.,  24 (2018),
[8] A. Borodin, I. Corwin,
Macdonald processes, Prob. Theory Related Fields,
158 (2014),225–400.

[63] P. Diaconis, A. Ram,
A probabilistic interpretation of the Macdonald
polynomials, Ann. Prob. (2012), 1861–1896.

[32] B. Derrida, M. Evans, V. Hakim, V. Pasquier,
Exact solution of a 1D asymmetric exclusion model
using a matrix formulation, J. Phys. A (1993),

[45] D. Kim, L. Williams, Schubert polynomials,
the inhomogeneous TASEP, and evil-avoiding permutations,
Preprint 2021, arXiv:2106.13378.

[49] T. Lam, L. Williams, A Markov chain on the symmetric group
that is Schubert positive?, Exp. Math, 21 (2012), 189–192.

[47] R. Lyons, Y. Peres, Probability on trees and networks,
Cambridge Series in Statistical and Probabilistic Mathematics
42, Cambridge University Press, New York, 2016.

[52] J. MacDonald, J. Gibbs, A. Pipkin,
Kinetics of biopolymerization on nucleric acid templates,
Biopolymers, 6 (1968).

[51] J. Martin, Stationary distributions of the
multi-type ASEPs, Preprint 2018,
[54] J. Pitman, W. Tang, Tree formulas,
mean first passage times and Kemeny's constant
of a Markov chain, Bernoulli 24 (2018), 1942–1972.

[57] F. Spitzer, Interaction of Markov
processes, Adv. Math. 5 1970, 246–290.

[61] M. Uchiyama, T. Sasamoto, M. Wadati,
Asymmetric simple exclusion process with open
boundaries and Askey-Wilson polynomials,
J. Phys. A 37 (2004).