论文标题
三个步骤混合在高立方体上进行一般随机步行的混合
Three steps mixing for general random walks on the hypercube at criticality
论文作者
论文摘要
我们在$ n $ hypercube上介绍了一般的随机步行类，在混合时间进行研究截止，并为过渡概率提供了几种类型的表示。我们观察到，对于具有远距离的这些过程的子类（即非本地），存在范围的临界值，该范围允许在最多三个步骤中进行“几乎完美”的混合。换句话说，三个步骤过渡与固定分布之间的总变化距离以$ n $的几何降低，这是超立方体的尺寸。在某些情况下，步行几乎完美地分为两个步骤。请注意，Diaconis和Shahshahani（1986）中的众所周知的结果（定理1）表明，在Abelian群体（例如HyperCube）上没有随机步行，它可以完全在两个步骤中完美混合。
We introduce a general class of random walks on the $N$-hypercube, study cut-off for the mixing time, and provide several types of representation for the transition probabilities. We observe that for a sub-class of these processes with long range (i.e. non-local) there exists a critical value of the range that allows an "almost-perfect" mixing in at most three steps. In other words, the total variation distance between the three steps transition and the stationary distribution decreases geometrically in $N$, which is the dimension of the hypercube. In some cases, the walk mixes almost-perfectly in exactly two steps. Notice that a well-known result (Theorem 1 in Diaconis and Shahshahani (1986)) shows that there exist no random walk on Abelian groups (such as the hypercube) which mixes perfectly in exactly two steps.
