Analysis of top to bottom-\(k\) shuffles (Q2494572): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
RedirectionBot (talk | contribs)
Removed claim: reviewed by (P1447): Item:Q591057
Property / reviewed by
 
Property / reviewed by: Nicko G. Gamkrelidze / rank
Normal 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
    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

    Identifiers