Bounding fastest mixing

被引:9
作者
Roch, S [1 ]
机构
[1] Univ Calif Berkeley, Dept Stat, Berkeley, CA 94720 USA
[2] MIT, CSAIL, Cambridge, MA 02139 USA
来源
ELECTRONIC COMMUNICATIONS IN PROBABILITY | 2005年 / 10卷
关键词
rapidly mixing Markov chains; fastest mixing; semidefinite programming; canonical paths; conductance;
D O I
10.1214/ECP.v10-1169
中图分类号
O21 [概率论与数理统计]; C8 [统计学];
学科分类号
020208 ; 070103 ; 0714 ;
摘要
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.
引用
收藏
页码:282 / 296
页数:15
相关论文
共 14 条
  • [1] ALDOUS DJ, 2004, UNPUB REVERSIBLE MAR
  • [2] Glauber dynamics on trees and hyperbolic graphs
    Berger, N
    Kenyon, C
    Mossel, E
    Peres, Y
    [J]. PROBABILITY THEORY AND RELATED FIELDS, 2005, 131 (03) : 311 - 340
  • [3] Fastest mixing Markov chain on a graph
    Boyd, S
    Diaconis, P
    Xiao, L
    [J]. SIAM REVIEW, 2004, 46 (04) : 667 - 689
  • [4] BOYD S, 2005, IN PRESS SIAM ANALCO
  • [5] Boyd S., 2004, CONVEX OPTIMIZATION
  • [6] BOYD S, 2005, IN PRESS AM MATH MON
  • [7] Symmetry Analysis of Reversible Markov Chains
    Boyd, Stephen
    Diaconis, Persi
    Parrilo, Pablo
    Xiao, Lin
    [J]. INTERNET MATHEMATICS, 2005, 2 (01) : 31 - 71
  • [8] Diaconis P., 1991, Ann. Appl. Probab., P36
  • [9] Evans W, 2000, ANN APPL PROBAB, V10, P410
  • [10] Horn R. A., 1986, Matrix analysis