We will discuss the use of Markov chains for sampling and counting combinatorial objects that belong to potentially exponentially large sets. Examples include coloring the vertices of a graph with k colors, perfect matchings of graphs, etc. For many of these applications it is sufficient to know how to sample these objects - then we can use sampling to (approximately - that is within (1+epsilon) factor) count all the objects. Often the fastest way to do this is through a so-called simulated annealing technique where we use a sequence of Markov chains to estimate certain probabilities and the product of these gives us the desired result. These Markov chains can be phrased as convex combinations of two other Markov chains; and for the technique to be applied successfully, each of the intermediate Markov chains must be mixing rapidly (that is, it must get to a random sample within a polynomial number of steps). We will study conditions under which convex combinations of Markov chains mix rapidly and we will prove both positive and negative results - it is possible that the two "parent" Markov chains mix rapidly but their convex combination does not; and there are conditions under which the convex combination always mixes rapidly.
This is joint work with Daniel Stefankovic.
Colloquia Series page.