(#023) Markov Chain Monte Carlo (MCMC) - Athreya C
Date/Time: 13-02-2021, 1930 - 2100 IST
Abstract
There are some interesting problems like finding the volume of a convex body or the permanent of a matrix that are known to be hard (#P-Complete for Complexity enthusiasts). So naturally we want to approximate these quantities. It turns out that if you had the ability to sample from weird sets (like the set of perfect matchings of a graph) you can come up with some nice approximation schemes. In fact, sampling from some really weird sets have interesting applications. For example: sampling from the set of bipartite graphs with specified degrees for each vertex is very useful in constructing "Low Density Parity Check Codes". In this seminar I'll introduce a powerful hammer called Markov Chain Monte Carlo (MCMC) to approximately sample. I'll also talk about a technique to analyze these MCMC samplers called Coupling.
Prerequisites
Basic Probability Theory