Event Type:

Graduate Student Summer Seminar

Date/Time:

Wednesday, July 20, 2016 - 14:30 to 15:30

Location:

Kidder 364

Abstract:

Common uses of Markov chains include sampling complex combinatorial structures and providing random algorithms in computer science. Oftentimes an NP hard problem may be approximately solved by a random algorithm in polynomial time, or an intractable combinatorial set may be sampled from by a Markov chain simulation. So it is of interest to characterize how long the Markov chain must run to provide an approximate solution - this is the chain's mixing time.

In this talk we will discuss some common tools that are currently employed for determining mixing time asymptotics. Then we will discuss a new method relying on some classical probability theory which solves the mixing time problem for a collection of Markov chains. The collection we have in mind are chains on the integers whose probability transitions have a nice limit as the system size grows.