Analysis of a twisted Bose-Einstein Markov chain with applications to sampling Catalan structures

Abstract

We analyze a twisted Bose-Einstein Markov chain on $[k{]}^n$ arising from the Diaconis-Zhong twisted Burnside process. We derive explicit formulas for the transition kernel and stationary distribution of both the original chain and its lumped process, and we identify this chain as a special case of Crane's cut-and-paste process. We establish bounds on the mixing time and determine the second-largest eigenvalue of the original chain and its lumped process. Complementing the fixed-$k$ cutoff theorem of Crane and Lalley, our bounds show that both chains mix in $\Theta (\log n)$ steps when $k$ grows as a fixed positive power of $n$. For the non-twisted Bose-Einstein Markov chain, this resolves a conjecture of Diaconis. As an application, we study the Burnside processes on parking functions and labeled Dyck paths, which give novel Markov chain Monte Carlo algorithms for sampling an increasing parking function and a Dyck path, respectively, approximately uniformly at random. We show that these chains are rapidly mixing, with mixing times of $\Theta (\log n)$.

29 pages, 2 figures. This version extends the results to the twisted Bose-Einstein chain. Comments welcome