University of Cambridge > > Churchill CompSci Talks > Coupling of Markov Chains

Coupling of Markov Chains

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

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2024, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity