Improved mixing time bounds for the Thorp shuffle and \(L\)-reversal chain (Q1019085): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Changed an Item
ReferenceBot (talk | contribs)
Changed an Item
Property / cites work
 
Property / cites work: Trailing the dovetail shuffle to its lair / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5836212 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Relaxation time of \(L\)-reversal chains and other chromosome shuffles / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4023085 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Comparison theorems for reversible Markov chains / rank
 
Normal rank
Property / cites work
 
Property / cites work: Generating a random permutation with random transpositions / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3059475 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Shuffling chromosomes / rank
 
Normal rank
Property / cites work
 
Property / cites work: On discrete inhomogeneous exit problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Mathematical Aspects of Mixing Times in Markov Chains / rank
 
Normal rank
Property / cites work
 
Property / cites work: The mixing time of the thorp shuffle / rank
 
Normal rank
Property / cites work
 
Property / cites work: Mixing times of lozenge tiling and card shuffling Markov chains / rank
 
Normal rank

Revision as of 13:58, 1 July 2024

scientific article
Language Label Description Also known as
English
Improved mixing time bounds for the Thorp shuffle and \(L\)-reversal chain
scientific article

    Statements

    Improved mixing time bounds for the Thorp shuffle and \(L\)-reversal chain (English)
    0 references
    0 references
    27 May 2009
    0 references
    The author proves a theorem that reduces bounding the mixing time of a card shuffle to verifying a condition that involves only pairs of cards. It is then used to obtain improved bounds for two previously studied models. The first one was introduced by \textit{E. O. Thorp} [J. Am. Stat. Assoc. 68, 842--847 (1973; Zbl 0274.90086)] as follows. Suppose the number of cards \(n\) is even. Cut the deck into two equal piles. Drop the first card from the left pile or from the right pile according to the outcome of a fair coin flip. Then drop from the other pile. Continue this way until both piles are empty. The present author obtains a mixing time bound of \(O\left( \log ^{4}n\right) \). Previously, the best known bound was \(O\left( \log ^{29}n\right) \) and previous proofs were only valid for \(n\) a power of \(2\). The second model, called the \(L\)-\textit{reversal chain},was introduced by \textit{R. Durrett} [J. Theor. Probab. 16, No. 3, 725--750 (2003; Zbl 1047.92020)]. There are \(n\) cards arrayed in a circle. Each step, an interval of cards of length at most \(L\) is chosen uniformly at random and its order is reversed. Durrett has conjectured that the mixing time if \(O\left( \max \left( n,~\displaystyle \frac{n^{3}}{_{L^{3}}}\right) \log n\right) .\) The present author obtains a bound that is within a factor \(O\left( \log ^{2}n\right) \) of this, the first bound within a poly log factor of the conjecture.
    0 references
    Markov chain
    0 references
    mixing time
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references