The partially asymmetric exclusion process (PASEP) is an important model from
statistical mechanics which describes a system of interacting particles hopping
left and right on a one-dimensional lattice of N sites. It is partially
asymmetric in the sense that the probability of hopping left is $q$ times the
probability of hopping right. Additionally, particles may enter from the left
with probability $\alpha$ and exit from the right with probability $\beta.$ It
has been observed that the (unique) stationary distribution of the PASEP has
remarkable connections to combinatorics -- see for example the papers of
Derrida, and Duchi and Schaeffer. We prove that in fact the (normalized)
probability of being in a particular state of the PASEP can be viewed as a
certain weight generating function for permutation tableaux of a fixed shape.
(This result implies the previous combinatorial results.) This proof relies on
the matrix ansatz of Derrida et al, and hence does not give an intuitive
explanation of why one should expect the steady state distribution of the PASEP
to involve such nice combinatorics. Therefore we also define a Markov chain --
which we call the PT chain -- on the set of permutation tableaux which projects
to the PASEP in a very strong sense. This gives a new proof of the previous
result which bypasses the matrix ansatz altogether. Furthermore, via the
bijection from permutation tableaux to permutations, the PT chain can also be
viewed as a Markov chain on the symmetric group. Another nice feature of the PT
chain is that it possesses a certain symmetry which extends the "particle-hole
symmetry" of the PASEP. More specifically, this is a graph-automorphism on the
state diagram of the PT chain which is an involution; this has a simple
description in terms of permutations.

This is joint work with Lauren Williams (Harvard)