IMPROVED MIXING TIME BOUNDS FOR THE THORP SHUFFLE AND L-REVERSAL CHAIN
成果类型：
Article
署名作者：
Morris, Ben
署名单位：
University of California System; University of California Davis
刊物名称：
ANNALS OF PROBABILITY
ISSN/ISSBN：
0091-1798
DOI：
10.1214/08-AOP409
发表日期：
2009
页码：
453-477
关键词：
摘要：
We prove a theorem that reduces bounding the mixing time of a card shuffle to verifying a condition that involves only pairs of cards, then We use it to obtain improved bounds for two previously studied models. E. Thorp introduced the following card shuffling model in 1973: Suppose the number of cards n is even. Cut the deck into two equal piles. Drop the first card from the left pile or from the right pile according to the outcome of a fair coin flip. Then drop from the other pile. Continue this way until both piles are empty. We obtain a mixing time bound of O (log(4)n). Previously, the best known bound was O (log(29)n) and previous proofs were only valid for n a power of 2. We also analyze the following model, called the L-reversal chain, introduced by Durrett: There are n cards arrayed in a circle. Each step, an interval of cards of length at most L is chosen uniformly at random and its order is reversed . Durrett has conjectured that the mixing time is O (max(n, n(3)/L-3) log n). We obtain a bound that is within a factor O (log(2)n) of this, the first bound within a poly log factor of the conjecture.