论文标题
在设定分区上的伯恩赛德进程马尔可夫链的混合时间
Mixing times of a Burnside process Markov chain on set partitions
论文作者
论文摘要
令$ x $为有限套件，让$ g $是在$ x $上作用的有限组。小组操作将$ x $拆分为不连接轨道。 Burnside工艺是$ x $的马尔可夫链，当链条集成到轨道时，它具有均匀的固定分布。我们认为$ x = [k]^n $带有$ k \ geq n $和$ g = s_k $是$ [k] $上的对称组，因此$ g $通过在$ x $上执行每个协调的值来代替$ x $。由此产生的伯恩赛进程提供了一种新颖的算法，用于随机对$ [n] $采样的设定分区。我们在混合时间上获得边界，并表明链条正在迅速混合。
Let $X$ be a finite set and let $G$ be a finite group acting on $X$. The group action splits $X$ into disjoint orbits. The Burnside process is a Markov chain on $X$ which has a uniform stationary distribution when the chain is lumped to orbits. We consider the case where $X = [k]^n$ with $k \geq n$ and $G = S_k$ is the symmetric group on $[k]$, such that $G$ acts on $X$ by permuting the value of each coordinate. The resulting Burnside process gives a novel algorithm for sampling a set partition of $[n]$ uniformly at random. We obtain bounds on the mixing time and show that the chain is rapidly mixing.
