The critical window for random transposition random walk
The random walk on the permutations of [N] generated by the transpositions was shown by Diaconis and Shahshahani to mix with sharp cutoff around N log N /2 steps. However, Schramm showed that the distribution of the sizes of the largest cycles concentrates (after rescaling) on the Poisson-Dirichlet distribution PD(0,1) considerably earlier, after (1+\epsilon)N/2 steps. We show that this behaviour in fact emerges precisely during the critical window of (1+\lambda N^{-1/3}) N/2 steps, as \lambda \rightarrow\infty. Our methods are rather different, and involve an analogy with the classical Erdos-Renyi random graph process, the metric scaling limits of a uniformly-chosen connected graph with a fixed finite number of surplus edges, and analysing the directed cycle structure of large 3-regular graphs. Joint work with Christina Goldschmidt.
Date: 13 May 2019, 12:00 (Monday, 3rd week, Trinity 2019)
Venue: Mathematical Institute, Woodstock Road OX2 6GG
Speaker: Dominic Yeo (University of Oxford)
Organising department: Department of Statistics
Part of: Probability seminar
Booking required?: Not required
Audience: Public
Editors: Christina Goldschmidt, James Martin