##
Convex Combinations of Markov Chains

Ivona Bezakova

Department of Computer Science

Rochester Institute of Technology

### ABSTRACT

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.