A Markov chain on the symmetric group and Jack symmetric functions

Abstract

Diaconis and Shahshahani studied a Markov chain W[function of (italic small f)](1) whose states are the elements of the symmetric group S[function of (italic small f)]. In W[function of (italic small f)](1), you move from a permutation [pi] to any permutation of the form [pi](i, j) with equal probability. In this paper we study a deformation W[function of (italic small f)]([alpha]) of this Markov chain which is obtained by applying the Metropolis algorithm to W[function of (italic small f)](1). The stable distribution of W[function of (italic small f)]([alpha]) is [alpha][function of (italic small f)]-c([pi]) where c([pi]) denotes the number of cycles of [pi]. Our main result is that the eigenvectors of the transition matrix of W[function of (italic small f)]([alpha]) are the Jack symmetric functions. We use facts about the Jack symmetric functions due to Macdonald and Stanley to obtain precise estimates for the rate of convergence of W[function of (italic small f)]([alpha]) to its stable distribution.