Combinatorics, Probability and Computing



Paper

Blocking Conductance and Mixing in Random Walks


R. KANNAN a1 1 , L. LOVÁSZ a2 and R. MONTENEGRO a3 2
a1 Department of Computer Science, Yale University, New Haven, CT 06520, USA (e-mail: kannan@cs.yale.edu)
a2 Microsoft Research, One Microsoft Way, Redmond, WA 98052, USA (e-mail: lovasz@microsoft.com)
a3 School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332-0160, USA (email: monteneg@math.gatech.edu)

Article author query
kannan r   [Google Scholar] 
lovasz l   [Google Scholar] 
montenegro r   [Google Scholar] 
 

Abstract

The notion of conductance introduced by Jerrum and Sinclair [8] has been widely used to prove rapid mixing of Markov chains. Here we introduce a bound that extends this in two directions. First, instead of measuring the conductance of the worst subset of states, we bound the mixing time by a formula that can be thought of as a weighted average of the Jerrum–Sinclair bound (where the average is taken over subsets of states with different sizes). Furthermore, instead of just the conductance, which in graph theory terms measures edge expansion, we also take into account node expansion. Our bound is related to the logarithmic Sobolev inequalities, but it appears to be more flexible and easier to compute.

In the case of random walks in convex bodies, we show that this new bound is better than the known bounds for the worst case. This saves a factor of $O(n)$ in the mixing time bound, which is incurred in all proofs as a ‘penalty’ for a ‘bad start’. We show that in a convex body in $\mathbb{R}^n$, with diameter $D$, random walk with steps in a ball with radius $\delta$ mixes in $O^*(nD^2/\delta^2)$ time (if idle steps at the boundary are not counted). This gives an $O^*(n^3)$ sampling algorithm after appropriate preprocessing, improving the previous bound of $O^*(n^4)$.

The application of the general conductance bound in the geometric setting depends on an improved isoperimetric inequality for convex bodies.

(Published Online June 7 2006)
(Received January 13 2004)
(Revised April 29 2004)



Footnotes

1 Research partially supported by NSF grant CCR-0310805.

2 Research partially supported by VIGRE grants at Yale University and the Georgia Institute of Technology.