  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, Duchi and Schaeffer, and Corteel. Most recently we proved 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.) However,
our proof relied on the matrix ansatz of Derrida et al, and hence did not give
an intuitive explanation of why one should expect the steady state distribution
of the PASEP to involve such nice combinatorics.
  In this paper we 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 our 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.
