BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Probability
SUMMARY:On the mixing time of random conjugacy walks - Nat
hanael Berestycki (Cambridge).
DTSTART;TZID=Europe/London:20090126T140000
DTEND;TZID=Europe/London:20090126T150000
UID:TALK16831AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/16831
DESCRIPTION:Let G be a finite graph and consider a random walk
on this graph. How long does it take for this wal
k to be well mixed\, i.e.\, to be close to its equ
ilibrium distribution? A striking phenomenon\, dis
covered in the early 80's by Aldous and Diaconis i
ndependently\, is that convergence to equilibrium
often occurs abruptly: this is known as the cutoff
phenomenon. In this talk we shall consider the cl
assical example of random transpositions over the
symmetric group. In this case\, Diaconis and Shahs
hahani used representation theory to prove that su
ch a cutoff occurs at time (1/2) n log n. We prese
nt a new\, probabilistic proof of this result\, wh
ich extends readily to other walks where the step
distribution is uniform over a given conjugacy cla
ss. This proves a conjecture of Roichman (1996) th
at the mixing time of this process is (1/C) n log
n\, where C is the size of the conjugacy class. Th
is is joint work with Oded Schramm and Ofer Zeitou
ni
LOCATION:MR12\, CMS\, Wilberforce Road\, Cambridge\, CB3 0W
B
CONTACT:HoD Secretary\, DPMMS
END:VEVENT
END:VCALENDAR