Markov Chain Mixing with Applications

Research Horizons Seminar
Tuesday, February 23, 2010 - 12:00pm for 1 hour (actually 50 minutes)
Skiles 255
Prasad Tetali – Professor, School of Mathematics and School of Computer Science
Huy Huynh

Please Note: Hosted by: Huy Huynh and Yao Li

Sampling from and approximately counting the size of a large set of combinatorial structures has contributed to a renaissance in research in finite Markov chains in the last two decades. Applications are wide-ranging from sophisticated card shuffles, deciphering simple substitution ciphers (of prison inmates in the California state prison), estimating the volume of a high-dimensional convex body, and to understanding the speed of Gibbs sampling heuristics in statistical physics. More recent applications include rigorous estimates on J.M. Pollard's (1979) classical Rho and Kangaroo algorithms for the discrete logarithm problem in finite cyclic groups. The lecture will be a brief (mostly self-contained) introduction to the Markov Chain Monte Carlo (MCMC) methodology and applications, and will include some open problems.