Czumaj, Artur and Vöcking, Berthold (2014) Thorp shuffling, butterflies, and non-Markovian couplings. In: Esparza, Javier and Fraigniaud, Pierre and Husfeldt, Thore and Koutsoupias, Elias, (eds.) Automata, Languages, and Programming. Lecture Notes in Computer Science, Volume 8572 . Springer Berlin Heidelberg, pp. 344-355. ISBN 9783662439470

Research output not available from this repository.

Request-a-Copy directly from author or use local Library Get it For Me service.

Request Changes to record.

Abstract

Thorp shuffle is a simple model for a random riffle shuffle that for many years has eluded good analysis. In Thorp shuffle, one first cuts a deck of cards in half, and then starts dropping the cards from the left or right hand as with an ordinary shuffle, so that at each time, one chooses the left or right card with probability 12 and drops it, and then drops the card from the opposite hand. Then one continues this inductively until all cards have been dropped. The question is how many times one has to repeat this process to randomly shuffle a deck of n cards. Despite its rather simple description and wide interest in understanding its behavior, Thorp shuffle has been very difficult to analyze and only very recently, Morris showed that Thorp shuffle mixes in a polylogarithmic number of rounds.
In our main result, we show that if Thorp shuffle mixes sequences consisting of n − k distinct elements together with k identical elements (so-called k-partial n-permutations) with k = Θ(n), then O(log2n) rounds are sufficient to randomly mix the input elements. In other words, O(log2n) Thorp shuffles with n input elements randomly permutes any set of c n elements with any c < 1, or, equivalently, is almost cn-wise independent. The key technical part of our proof is a novel analysis of the shuffling process that uses non-Markovian coupling. While non-Markovian coupling is known to be more powerful than the Markovian coupling, our treatment is one of only a few examples where strictly non-Markovian coupling can be used to formally prove a strong mixing time. Our non-Markovian coupling is used to reduce the problem to the analysis of some random process in networks (in particular, when n is a power of two then this is in a butterfly network), which we solve using combinatorial and probabilistic arguments.
Our result can be used to randomly permute any number of elements using Thorp shuffle: If the input deck has N cards, then add another set of 0.01 N “empty” cards and run O(log2N) Thorp shuffles. Then, if we remove the empty cards, the obtained deck will have the original N cards randomly permuted.
We also analyze a related shuffling process that we call Perfect shuffle. We cut a deck of n cards into two halves, randomly permute each half, and then perform one step of Thorp shuffle. Apart from being interesting on its own, our motivation to study this process is that a single Perfect shuffle is very similar to O(logn) Thorp shuffles, and thus understanding of Perfect shuffle can shed some light on the performance of Thorp shuffle. We apply coupling to show that Perfect shuffle mixes in O(loglogn) steps, which we conjecture to be asymptotically tight.

Item Type:	Book Item
Divisions:	Faculty of Science, Engineering and Medicine > Science > Computer Science
Series Name:	Lecture Notes in Computer Science
Publisher:	Springer Berlin Heidelberg
ISBN:	9783662439470
ISSN:	0302-9743
Book Title:	Automata, Languages, and Programming
Editor:	Esparza, Javier and Fraigniaud, Pierre and Husfeldt, Thore and Koutsoupias, Elias
Official Date:	2014
Dates:	Date Event 2014 Published
Volume:	Volume 8572
Page Range:	pp. 344-355
DOI:	10.1007/978-3-662-43948-7_29
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Date of first compliant deposit:	4 March 2016

Request changes or add full text files to a record

Repository staff actions (login required)

View Item