Emergence of Giant Cycles and Slowdown Transition in Random Transpositions and k-Cycles
Emergence of Giant Cycles and Slowdown Transition in Random Transpositions and k-Cycles
复制标题
随机换位和 k 循环中巨循环的出现和减速转变
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
N. Berestycki
中科院分区：
文献类型：
--
作者：
N. Berestycki
当阶跃分布在给定的共轭类上是均匀分布时，考虑置换群上的随机游动。结果表明，有一个临界时间，在这两个相变同时发生。一方面，随机游走突然减慢：加速度（即，距离的二阶时间导数）此时从$0$下降到$-\infty$为$n\to\infty$。另一方面，最大的周期大小从微观到巨。证明这最后一个结果是相当简单，并持有更普遍的比以前的结果奥德施拉姆随机换位。结果表明，在随机$k$-循环的情况下，这个临界时间与$1/[k（k-1）]$成比例，而混合时间已知与$1/k$成比例。
Consider the random walk on the permutation group obtained when the step distribution is uniform on a given conjugacy class. It is shown that there is a critical time at which two phase transitions occur simultaneously. On the one hand, the random walk slows down abruptly: the acceleration (i.e., the second time derivative of the distance) drops from $0$ to $-\infty$ at this time as $n\to\infty$. On the other hand, the largest cycle size changes from microscopic to giant. The proof of this last result is considerably simpler and holds more generally than in a previous result of Oded Schramm for random transpositions. It turns out that in the case of random $k$-cycles, this critical time is proportional to $1/[k(k-1)]$, whereas the mixing time is known to be proportional to $1/k$.
随机 k 循环和聚结断裂链的混合时间
DOI：
10.1214/10-aop634
发表时间：
2011
期刊：
The Annals of Probability
影响因子：
--
作者：
Berestycki N
通讯作者：
Berestycki N