Emergence of Giant Cycles and Slowdown Transition in Random Transpositions and k-Cycles
By Nathanaël Berestycki. 2010
50 citations recorded by the source corpus.
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$.
Subfields: Artificial Intelligence, Mathematical Physics, Statistics and Probability
View Paper: https://www.semanticscholar.org/paper/b232214effe926c86c7f15e2bc45dd62959f6e61
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
In Mathematical Physics
In Statistics and Probability
Citations in the corpus
- On the Cycle Structure of Mallows Permutations (2016, background): “Schramm’s work focuses on the case that t > 1 2 and proves that macroscopic cycles emerge in this regime (see also Berestycki [3] for a later simpler argument).”