Title: Sharp thresholds for the mixing time of random permutation
Speaker: Ofer Zeitouni
Speaker Info: University of Minnesota and Weizmann Institute
Starting with the identity permutation on n elements, and applying successive random transpositions, it takes n log n/2 steps to reach equilibrium (in variation distance), and the transition between "far from equilibrium" and "close to equilibrium" occurs in a window of width O(n). This fact has been proved by Diaconis and Shashahani using representation theoretic methods, that do not extend easily to other type of shuffles (e.g., one that uses random k-cycles). I will discuss this background and then will describe a different, probabilistic approach, based on certain couplings, to address such questions. This approach has its origin in the study of certain fragmentation-coagulation processes.Date: Wednesday, March 3, 2010
This is joint work with Nathanael Berestycki and the late Oded Schramm.