BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:On the mixing time of random conjugacy walks - Nathanael Berestyck
 i (Cambridge).
DTSTART:20090126T140000Z
DTEND:20090126T150000Z
UID:TALK16831@talks.cam.ac.uk
CONTACT:HoD Secretary\, DPMMS
DESCRIPTION:Let G be a finite graph and consider a random walk on this gra
 ph. How long does it take for this walk to be well mixed\, i.e.\, to be cl
 ose to its equilibrium distribution? A striking phenomenon\, discovered in
  the early 80's by Aldous and Diaconis independently\, is that convergence
  to equilibrium often occurs abruptly: this is known as the cutoff phenome
 non. In this talk we shall consider the classical example of random transp
 ositions over the symmetric group. In this case\, Diaconis and Shahshahani
  used representation theory to prove that such a cutoff occurs at time (1/
 2) n log n. We present a new\, probabilistic proof of this result\, which 
 extends readily to other walks where the step distribution is uniform over
  a given conjugacy class. This proves a conjecture of Roichman (1996) that
  the mixing time of this process is (1/C) n log n\, where C is the size of
  the conjugacy class. This is joint work with Oded Schramm and Ofer Zeitou
 ni
LOCATION:MR12\, CMS\, Wilberforce Road\, Cambridge\, CB3 0WB
END:VEVENT
END:VCALENDAR