期刊
ANNALS OF APPLIED PROBABILITY
卷 14, 期 1, 页码 274-325出版社
INST MATHEMATICAL STATISTICS
DOI: 10.1214/aoap/1075828054
关键词
random walk; mixing time; card shuffling; lozenge tiling; linear extension; exclusion process; lattice path; cutoff phenomenon
We show how to combine Fourier analysis with coupling arguments to bound the mixing times of a variety of Markov chains. The mixing time is the number of steps a Markov chain takes to approach its equilibrium distribution. One application is to a class of Markov chains introduced by Luby, Randall and Sinclair to generate random tilings of regions by lozenges. For an l x l region we bound the mixing time by O(l(4) log l), which improves on the previous bound of O(l(7)), and we show the new bound to be essentially tight. In another application we resolve a few questions raised by Diaconis and Saloff-Coste by lower bounding the mixing time of various card-shuffling Markov chains. Our lower bounds are within a constant factor of their upper bounds. When we use our methods to modify a path-coupling analysis of Bubley and Dyer, we obtain an O(n(3) log n) upper bound on the mixing time of the Karzanov-Khachiyan Markov chain for linear extensions.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据