TY - JOUR

T1 - Mixing times of the biased card shuffling and the asymmetric exclusion process

AU - Benjamini, Itai

AU - Berger, Noam

AU - Hoffman, Christopher

AU - Mossel, Elchanan

PY - 2005/8

Y1 - 2005/8

N2 - Consider the following method of card shuffling. Start with a deck of N cards numbered 1 through N. Fix a parameter p between 0 and 1. In this model a "shuffle" consists of uniformly selecting a pair of adjacent cards and then flipping a coin that is heads with probability p. If the coin comes up heads, then we arrange the two cards so that the lower-numbered card comes before the higher-numbered card. If the coin comes up tails, then we arrange the cards with the higher-numbered card first. In this paper we prove that for all p ≠ 1/2, the mixing time of this card shuffling is O(N 2), as conjectured by Diaconis and Ram (2000). Our result is a rare case of an exact estimate for the convergence rate of the Metropolis algorithm. A novel feature of our proof is that the analysis of an infinite (asymmetric exclusion) process plays an essential role in bounding the mixing time of a finite process.

AB - Consider the following method of card shuffling. Start with a deck of N cards numbered 1 through N. Fix a parameter p between 0 and 1. In this model a "shuffle" consists of uniformly selecting a pair of adjacent cards and then flipping a coin that is heads with probability p. If the coin comes up heads, then we arrange the two cards so that the lower-numbered card comes before the higher-numbered card. If the coin comes up tails, then we arrange the cards with the higher-numbered card first. In this paper we prove that for all p ≠ 1/2, the mixing time of this card shuffling is O(N 2), as conjectured by Diaconis and Ram (2000). Our result is a rare case of an exact estimate for the convergence rate of the Metropolis algorithm. A novel feature of our proof is that the analysis of an infinite (asymmetric exclusion) process plays an essential role in bounding the mixing time of a finite process.

UR - http://www.scopus.com/inward/record.url?scp=23244454079&partnerID=8YFLogxK

U2 - 10.1090/S0002-9947-05-03610-X

DO - 10.1090/S0002-9947-05-03610-X

M3 - Article

AN - SCOPUS:23244454079

SN - 0002-9947

VL - 357

SP - 3013

EP - 3029

JO - Transactions of the American Mathematical Society

JF - Transactions of the American Mathematical Society

IS - 8

ER -