论文标题
在CA组上的通勤链的混合时间
Mixing Times for the Commuting Chain on CA Groups
论文作者
论文摘要
令$ g $为有限的组。 $ g $上的通勤链从元素$ x $移动到$ y $，通过在使用$ x $的$ y $中选择$ y $。该连锁店的$ T $步骤过渡概率汇总到$ g $的连同类别上的分销统一。我们为在CA组（具有“良好”通勤结构的组）上的混合时间提供上限和下限，并表明许多这些链不会发生截止。我们还为该链的过渡矩阵的特征多项式提供了一个公式。我们将一般结果应用于多个组序列，例如一般线性组，海森贝格组和二面体组。 通勤链是一个更普遍的链条家族的特定情况，称为伯恩赛德工艺。 Burnside过程的实例很少可以仔细分析混合。我们介绍了未完全指定状态空间（即不适合特定组）的Burnside过程的一些第一个结果。我们的上限显示我们的链条迅速混合，这是伯恩赛德过程感兴趣的话题。
Let $G$ be a finite group. The commuting chain on $G$ moves from an element $x$ to $y$ by selecting $y$ uniformly amongst those which commute with $x$. The $t$ step transition probabilities of this chain converge to a distribution uniform on the conjugacy classes of $G$. We provide upper and lower bounds for the mixing time of this chain on a CA group (groups with a "nice" commuting structure) and show that cutoff does not occur for many of these chains. We also provide a formula for the characteristic polynomial of the transition matrix of this chain. We apply our general results to explicitly study the chain on several sequences of groups, such as general linear groups, Heisenberg groups, and dihedral groups. The commuting chain is a specific case of a more general family of chains known as Burnside processes. Few instances of the Burnside processes have permitted careful analysis of mixing. We present some of the first results on mixing for the Burnside process where the state space is not fully specified (i.e not for a particular group). Our upper bound shows our chain is rapidly mixing, a topic of interest for Burnside processes.
