CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Rapid mixing of dealer shuffles and clumpy shuffles

Johan Jonasson (Institutionen för matematiska vetenskaper, matematik) ; B. Morris
Electronic Communications in Probability (1083-589X). Vol. 20 (2015), p. article no. 20 (11 pp.).
[Artikel, refereegranskad vetenskaplig]

A famous result of Bayer and Diaconis [2] is that the Gilbert-Shannon-Reeds (GSR) model for the riffle shuffle of n cards mixes in 3/2log(2)n steps and that for 52 cards about 7 shuffles suffices to mix the deck. In this paper, we study variants of the GSR shuffle that have been proposed to model more realistically how people actually shuffle a deck of cards. The clumpy riffle shuffle and dealer riffle shuffle differ from the GSR model in that when a card is dropped from one hand, the conditional probability that the next card is dropped from the same hand is higher/lower than for the GSR model. Until now, no nontrivial rigorous results have been known for the clumpy shuffle or dealer shuffle. In this paper we show that the mixing time is O (log(4)n).

Nyckelord: riffle shuffle, entropy technique, collisions, Thorp Shuffle, Time-Bounds



Denna post skapades 2015-04-13. Senast ändrad 2015-05-20.
CPL Pubid: 215159

 

Läs direkt!

Lokal fulltext (fritt tillgänglig)

Länk till annan sajt (kan kräva inloggning)


Institutioner (Chalmers)

Institutionen för matematiska vetenskaper, matematik (2005-2016)

Ämnesområden

Matematik

Chalmers infrastruktur