Analysis of top to bottom-\(k\) shuffles (Q2494572): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: reviewed by (P1447): Item:Q591057 |
||
Property / reviewed by | |||
Property / reviewed by: Nicko G. Gamkrelidze / rank | |||
Revision as of 02:03, 20 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Analysis of top to bottom-\(k\) shuffles |
scientific article |
Statements
Analysis of top to bottom-\(k\) shuffles (English)
0 references
29 June 2006
0 references
The aim of this paper is to analyze a class of walks that generalizes the top to random chain, namely, top to bottom-\(k\) shuffles. These shuffles are generated by moving the top card uniformly at random to any of the bottom \(k_n\) positions of the deck. The author gives upper and lower bounds on the total variation mixing time for this shuffle as \(k_n\) ranges from a constant to \(n\). He also considers a symmetric variant of this shuffle in which at each step either the top card is randomly inserted into the bottom \(k_n\) positions or a random card from the bottom \(k_n\) positions is moved to the top. For this reversible shuffle the author derives bounds on the \(L^2\) mixing time. Finally, he transfers mixing time estimates for the above shuffles to the lazy top to bottom-\(k\) walks that move with probability 1/2 at each step.
0 references
finite Markov chains
0 references
mixing time
0 references
card shuffing
0 references
Rudvalis shuffle
0 references