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:Churchill CompSci Talks
SUMMARY:Coupling of Markov Chains - Lucas Sonnabend\, Chur
chill College
DTSTART;TZID=Europe/London:20141119T194000
DTEND;TZID=Europe/London:20141119T203000
UID:TALK56028AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/56028
DESCRIPTION:We can model random processes such as shuffling ca
rds using Markov chains. For a certain class of th
em we can find a stationary distribution to which
the process will converge.\n\nI will explain how c
oupling of Markov Chains is used to estimate the t
ime needed to get close to this stationary distrib
ution. For example\, how often do you have to shuf
fle a deck of cards until you are fairly sure that
they are distributed uniformly?\n\nIn terms of ap
plications\, I will describe a polynomial time pro
babilistic algorithm for graph colouring\, and I w
ill explain a magic trick!
LOCATION:Wolfson Hall\, Churchill College
CONTACT:Jasper Lee
END:VEVENT
END:VCALENDAR