Coupling of Markov Chains

Add to your list(s) Download to your calendar using vCal

• Lucas Sonnabend, Churchill College
• Wednesday 19 November 2014, 19:40-20:30
• Wolfson Hall, Churchill College.

If you have a question about this talk, please contact Jasper Lee.

We can model random processes such as shuffling cards using Markov chains. For a certain class of them we can find a stationary distribution to which the process will converge.

I will explain how coupling of Markov Chains is used to estimate the time needed to get close to this stationary distribution. For example, how often do you have to shuffle a deck of cards until you are fairly sure that they are distributed uniformly?

In terms of applications, I will describe a polynomial time probabilistic algorithm for graph colouring, and I will explain a magic trick!

This talk is part of the Churchill CompSci Talks series.

This talk is included in these lists:

• Churchill CompSci Talks
• Wolfson Hall, Churchill College
• computer science
• se393's list

Note that ex-directory lists are not shown.