The cutoff phenomenon for randomized riffle shuffles

被引：3

作者：

Chen, Guan-Yu ^{[2
]}

Saloff-Coste, Laurent ^{[1
]}

机构：

[1] Cornell Univ, Dept Math, Ithaca, NY 14853 USA

[2] Natl Tsing Hua Univ, Natl Ctr Theoret Sci, Div Math, Hsinchu 300, Taiwan

来源：

RANDOM STRUCTURES & ALGORITHMS | 2008年 / 32卷 / 03期

关键词：

cutoff phenomenon; riffle shuffle;

D O I：

10.1002/rsa.20195

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We study the cutoff phenomenon for generalized riffle shuffles where, at each step, the deck of cards is cut into a random number of packs of multinomial sizes which are then riffled together. (c) 2007 Wiley Periodicals, Inc.

引用

页码：346 / 374

页数：29

共 19 条

[1] SHUFFLING CARDS AND STOPPING-TIMES [J].

ALDOUS, D ;

DIACONIS, P .

AMERICAN MATHEMATICAL MONTHLY, 1986, 93 (05) :333-348

[2] STRONG UNIFORM TIMES AND FINITE RANDOM-WALKS [J].

ALDOUS, D ;

DIACONIS, P .

ADVANCES IN APPLIED MATHEMATICS, 1987, 8 (01) :69-97

[3]

ALDOUS D, 1983, LECT NOTES MATH, V986, P243

[4]

[Anonymous], 1992, Combinatorics, Probability Computing

[5]

[Anonymous], 2003, GROUPS COMBINATORICS

[6]

Bayer D., 1992, Ann. Appl. Probab, V2, P294, DOI DOI 10.1214/AOAP/1177005705

[7] A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements [J].

Bidigare, P ;

Hanlon, P ;

Rockmore, D .

DUKE MATHEMATICAL JOURNAL, 1999, 99 (01) :135-174

[8]

Brown KS, 1998, ANN PROBAB, V26, P1813

[9]

CHEN GY, THESIS CORNELL U ITH

[10] The cutoff phenomenon in finite Markov chains [J].

Diaconis, P .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 1996, 93 (04) :1659-1664

← 1 2 →