MIXING TIME OF THE CARD-CYCLIC-TO-RANDOM SHUFFLE

被引：6

作者：

Morris, Ben ^{[1
]}

Ning, Weiyang ^{[2
]}

Peres, Yuval ^{[3
]}

机构：

[1] Univ Calif Davis, Dept Math, Davis, CA 95616 USA

[2] Univ Washington, Dept Math, Seattle, WA 98195 USA

[3] Microsoft Res, Redmond, WA 98052 USA

来源：

ANNALS OF APPLIED PROBABILITY | 2014年 / 24卷 / 05期

基金：

美国国家科学基金会;

关键词：

Markov chain; mixing time; RANDOM TRANSPOSITIONS; MARKOV-CHAINS;

D O I：

10.1214/13-AAP964

中图分类号：

O21 [概率论与数理统计]; C8 [统计学];

学科分类号：

020208 ; 070103 ; 0714 ;

摘要：

The card-cyclic-to-random shuffle on n cards is defined as follows: at time t remove the card with label t mod n and randomly reinsert it back into the deck. Pinsky [Probabilistic and combinatorial aspects of the card-cyclic-to-random shuffle (2011). Unpublished manuscript] Introduced this shuffle and asked how many steps are needed to mix the deck. He showed n steps do not suffice. Here we show that the mixing time is on the order of Theta (n log n).

引用

页码：1835 / 1849

页数：15

共 12 条

[1]

[Anonymous], 2009, AM MATH SOC PROVIDEN

[2] Path coupling: A technique for proving rapid mixing in Markov chains [J].