Biased random-to-top shuffling

DOI10.1214/10505160600000097MaRDI QIDQ997960zbMATHOpenAlexFDO

Authors Johan Jonasson

Publication date 8 August 2007

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0607124

zbMATH Keywords

couplinglower boundmixing timeupper bound

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Combinatorial probability (60C05) Stochastic processes (60G99)

Abstract: Recently Wilson [Ann. Appl. Probab. 14 (2004) 274--325] introduced an important new technique for lower bounding the mixing time of a Markov chain. In this paper we extend Wilson's technique to find lower bounds of the correct order for card shuffling Markov chains where at each time step a random card is picked and put at the top of the deck. Two classes of such shuffles are addressed, one where the probability that a given card is picked at a given time step depends on its identity, the so-called move-to-front scheme, and one where it depends on its position. For the move-to-front scheme, a test function that is a combination of several different eigenvectors of the transition matrix is used. A general method for finding and using such a test function, under a natural negative dependence condition, is introduced. It is shown that the correct order of the mixing time is given by the biased coupon collector's problem corresponding to the move-to-front scheme at hand. For the second class, a version of Wilson's technique for complex-valued eigenvalues/eigenvectors is used. Such variants were presented in [Random Walks and Geometry (2004) 515--532] and [Electron. Comm. Probab. 8 (2003) 77--85]. Here we present another such variant which seems to be the most natural one for this particular class of problems. To find the eigenvalues for the general case of the second class of problems is difficult, so we restrict attention to two special cases. In the first case the card that is moved to the top is picked uniformly at random from the bottom $k=k(n)=o(n)$ cards, and we find the lower bound $(n^3/(4p{i}^{2}k(k-1)))logn$. Via a coupling, an upper bound exceeding this by only a factor 4 is found. This generalizes Wilson's [Electron. Comm. Probab. 8 (2003) 77--85] result on the Rudvalis shuffle and Goel's [Ann. Appl. Probab. 16 (2006) 30--55] result on top-to-bottom shuffles. In the second case the card moved to the top is, with probability 1/2, the bottom card and with probability 1/2, the card at position $n-k$. Here the lower bound is again of order $(n^3/k^2)logn$, but in this case this does not seem to be tight unless $k=O(1)$. What the correct order of mixing is in this case is an open question. We show that when $k=n/2$, it is at least $Theta(n^2)$.

Recommendations

• Mixing times of the biased card shuffling and the asymmetric exclusion process
• How many times are needed for card shuffling?
• Analysis of top to bottom-\(k\) shuffles
• Analysis of Top To Random Shuffles
• The combinatorics of biased riffle shuffles

Cites work

• scientific article; zbMATH DE number 2128202 (Why is no real title available?)
• scientific article; zbMATH DE number 48363 (Why is no real title available?)
• scientific article; zbMATH DE number 837692 (Why is no real title available?)
• Analysis of top to bottom-\(k\) shuffles
• Convergence to stationary state for a Markov move-to-front scheme
• Mixing time of the Rudvalis shuffle
• Mixing times of lozenge tiling and card shuffling Markov chains
• Shuffling Cards and Stopping Times
• The Asymptotic Behavior of the Solutions of a Class of Differential-Difference Equations
• The overhand shuffle mixes in \(\Theta(n^2\log n)\) steps
• Trailing the dovetail shuffle to its lair

Cited in

(8)

• Mixing times of the biased card shuffling and the asymmetric exclusion process
• Mixing of permutations by biased transpositions
• Analysis of top to bottom-\(k\) shuffles
• Card shuffling and Diophantine approximation
• Shuffling large decks of cards and the Bernoulli-Laplace urn model
• Mixing time of the Rudvalis shuffle
• Mixing times of Markov chains for self‐organizing lists and biased permutations
• Analysis of Top To Random Shuffles

This page was built for publication: Biased random-to-top shuffling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q997960)