## Improved bounds for mixing rates of Markov chains and
multicommodity flow

**Alistair Sinclair**
*Abstract:* The paper is concerned with tools for the
quantitative analysis of finite Markov chains whose states are
combinatorial structures. Chains of this kind have algorithmic
applications in many areas, including random sampling, approximate
counting, statistical physics and combinatorial optimisation. The
efficiency of the resulting algorithms depends crucially on the
mixing rate of the chain, i.e., the time taken for it to reach its
stationary or equilibrium distribution.

The paper presents a new upper bound on the mixing rate, based
on the solution to a multicommodity flow problem in the Markov
chain viewed as a graph. The bound gives sharper estimates for the
mixing rate of several important complex Markov chains. As a
result, improved bounds are obtained for the runtimes of randomised
approximation algorithms for various problems, including computing
the permanent of a 0-1 matrix, counting matchings in graphs, and
computing the partition function of a ferromagnetic Ising system.
Moreover, solutions to the multicommodity flow problem are shown to
capture the mixing rate quite closely: thus, under fairly general
conditions, a Markov chain is rapidly mixing if and only if it
supports a flow of low cost.

*LFCS report ECS-LFCS-91-178*

This report was published in *Combinatorics, Probability and
Computing*, February 1993.

This report is available in the following formats:

Previous |

Index |

Next