MIT Combinatorics Seminar

Permutation tableaux and the partially asymmetric exclusion process

Sylvie Corteel (CNRS and Universite Paris-Sud)

Friday, November 17, 2006   4:15 pm    Room 2-136


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)