Criticality in random transposition random walk

With Dominic Yeo (Technion, Haifa)

Criticality in 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 rightarrowinfty. 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.

Add to your calendar or Include in your list

How can mathematics help us to understand the behaviour of ants? Read more about the fanscinating work being carri… https://t.co/iCODvvxqE6 View on Twitter