On the rate of mixing for p-shuffles

• 成果类型: Article
• 署名作者: Lalley, SP
• 署名单位: University of Chicago
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• 发表日期: 2000
• 页码: 1302-1321
• 关键词: random-walks; hyperplane arrangements

摘要

The p-shuffle is a natural generalization of the dovetail shuffle. It is defined as follows. First, the deck is cut into a top stack and a bottom stack so that the distribution of the size of the top stack is Binomial (N, p), where N is the total number of cards in the deck Then, conditional on the outcome of the cut, the two stacks are riffled in such a way that all possible riffles (interleavings) of these two stacks are equally likely The main result of the paper is an asymptotic (N --> infinity) bound on the number of repetitions needed to randomize the deck.