Bounding Fastest Mixing

Open Access

1 January 2005

journal article
Published by Institute of Mathematical Statistics in Electronic Communications in Probability

Vol. 10 (none) , 282-296
https://doi.org/10.1214/ecp.v10-1169

Abstract

In a recent work, Boyd, Diaconis and Xiao introduced a semidefinite programming approach for computing the fastest mixing Markov chain on a graph of allowed transitions, given a target stationary distribution. In this paper, we show that standard mixing time analysis techniques—variational characterizations, conductance, canonical paths—can be used to give simple, nontrivial lower and upper bounds on the fastest mixing time. To test the applicability of this idea, we consider several detailed examples including the Glauber dynamics of the Ising model.

Keywords

This publication has 12 references indexed in Scilit:

The Fastest Mixing Markov Process on a Graph and a Connection to a Maximum Variance Unfolding Problem
SIAM Review, 2006
Symmetry Analysis of Reversible Markov Chains
Internet Mathematics, 2005
Glauber dynamics on trees and hyperbolic graphs
Probability Theory and Related Fields, 2004
Convex Optimization
Published by Cambridge University Press (CUP) ,2004
Fastest Mixing Markov Chain on a Graph
SIAM Review, 2004
Broadcasting on trees and the Ising model
The Annals of Applied Probability, 2000
Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
Combinatorics, Probability and Computing, 1992
Geometric Bounds for Eigenvalues of Markov Chains
The Annals of Applied Probability, 1991
Approximating the Permanent
SIAM Journal on Computing, 1989
Matrix Analysis
Published by Cambridge University Press (CUP) ,1985