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)$.
From: Ivan Feng [view email]
[v1]
Fri, 15 May 2026 17:49:11 UTC (21 KB)
[v2]
Sat, 22 Aug 2026 03:12:48 UTC (32 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。