Amanda Priestley

Glauber Dynamics on the Set of Parking Functions

The set of parking functions of length n, PF_n, is a generalization of the symmetric group on n elements, first introduced by Konheim and Weiss in 1966. While much is known about these objects from an enumerative combinatorics perspective, far less is known from a probabilistic perspective. In this work, we give definitions of fast and slow single site dynamics for sampling uniformly from the set of parking functions, and compare the mixing times of these processes to the analogous process on the full space [n]^n. As far as we are aware, these are the first Markov chains to be defined that act directly on PF_n, rather than sampling by way of a bijection. Moreover, as the set of parking functions is a monotone subset of [n]^n, determining the mixing time of these processes has interesting implications for the theory of Markov chain mixing, and more specifically, the cutoff phenomenon.