Markov Chain Mixing with Applications

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

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.