Random Sampling and Approximate Counting with Markov Chains

in an exponential sized space and sampling from them arise
quite often. We shall first look at some examples, some of
which arise in Physics. Then we look at the "equivalence"
of approximate counting and sampling.

A common approach for random sampling is via Markov Chains.
An important algorithmic issue is the mixing time of the
chain. Two main techniques - Conductance and Coupling- for
bounding the mixing rates will be discussed, with their
applications.