Biased random-to-top shuffling (Q997960): Difference between revisions

This paper investigates a new 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 time step depends on its identity, the so-called move-to-front scheme, and one where it depends on its position. 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 the so-called Wilson technique for complex-valued eigenvalues/ eigenvectors is used. To finde the eigenvalues for the general case of the second class of problems is difficult so the author restrict attention only to two special cases.