## Speaker:

Girish Varma
School of Technology and Computer Science
Tata Institute of Fundamental Research
Homi Bhabha Road
<br

## Time:

Friday, 23 October 2009 (All day)

## Venue:

- A-212 (STCS Seminar Room)

Markov chain Monte Carlo (MCMC) methods (which include random walk Monte Carlo methods), are a class of algorithms for sampling from probability distributions based on constructing a Markov chain that has the desired distribution as its equilibrium distribution. The state of the chain after a large number of steps is then used as a sample from the desired distribution. The quality of the sample improves as a function of the number of steps. We will use such a thing for generating a random perfect matching.

Reference :

Approximating the permanent M Jerrum, A Sinclair - SIAM journal on computing, 1989 - link.aip.org

How hard is it to marry at random? AZ Broder - Proceedings of the eighteenth annual ACM symposium â€¦, 1986 - portal.acm.org