How to shuffle a deck by parts? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T16:32:48Z http://mathoverflow.net/feeds/question/32626 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/32626/how-to-shuffle-a-deck-by-parts How to shuffle a deck by parts? Benoît Kloeckner 2010-07-20T12:34:18Z 2010-08-19T10:34:32Z <p>This question is mainly a curiosity, but comes from a practical experience (all players of <em>Race for the galaxy</em>, for example, must have ask themselves the question).</p> <p>Assume I have a deck of cards that I would like to shuffle. Unfortunately, the deck is so big that I cannot hold it entirely in my hands. Let's say that the deck contains $kn$ cards, and that the operation I can perform are: 1. cut a deck into any number of sub-decks, without looking at the cards but remembering for all $i$ where the $i$-th card from top of the original deck has been put; 2. gather several decks into one deck in any order (but assume that we do not intertwin the various decks, nor change the order inside any of them); 3. shuffle any deck of at most $n$ cards. Assume moreover that such a shuffle consist in applying an unknown random permutation drawn uniformly.</p> <p>Here is the question: is it possible to design a finite number of such operations so that the resulting deck has uniform law among all possible permutations of the original deck? If yes, how many shuffles are necessary, or sufficient, to achieve that ?</p> <p>The case $k=2$ seems already interesting.</p> http://mathoverflow.net/questions/32626/how-to-shuffle-a-deck-by-parts/32631#32631 Answer by David Speyer for How to shuffle a deck by parts? David Speyer 2010-07-20T13:03:40Z 2010-07-20T13:55:14Z <p>A truly uniform distribution, no. (Well, your question is not completely well posed, but I will argue this for most ways of making it so.) There are $(kn)!$ factorial ways to shuffle a deck of $kn$ cards. So you want each permutation to occur with probability $1/(kn)!$. In particular, for every prime $p \leq kn$, you want $p$ to occur in the denominator of the probability that each permutation occurs. Let's look at your operations: Reordering $i$ decks can only introduce primes $\leq i$. Perfectly shuffling an $n$ card deck can only introduce primes $\leq n$. Cutting depends on what mathematical model you use for cutting; if all cut points are equally likely, you only get primes dividing $n(n-1)\ldots (n-i+1)$. I imagine other models of cutting will cause similar problems.</p> <p>The more commonly studied question is how to get a probability distribution that is extremely close to random. There are lots of good results on this; see <a href="http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.aoap/1177005705" rel="nofollow">Trailing the Dovetail Shuffle to its Lair</a>.</p> http://mathoverflow.net/questions/32626/how-to-shuffle-a-deck-by-parts/32683#32683 Answer by Jim Belk for How to shuffle a deck by parts? Jim Belk 2010-07-20T19:42:56Z 2010-07-20T19:42:56Z <p>Though David's answer settles the original question, there is no reason to restrict to the case where the total number of cards is a multiple of $n$. In general, we can ask whether it is possible to completely shuffle a deck with $M$ cards if only $n$-card subdecks are directly shuffleable.</p> <p>As David points out, this is necessarily impossible if there exists a prime $p$ for which $n &lt; p \leq M$. This means that the smallest case that's still open is $n=3$ and $M=4$. That is, is it possible to completely randomize a 4-card deck if only 2 or 3 cards may be shuffled at a time?</p> http://mathoverflow.net/questions/32626/how-to-shuffle-a-deck-by-parts/32871#32871 Answer by davidcary for How to shuffle a deck by parts? davidcary 2010-07-22T00:15:16Z 2010-07-22T00:15:16Z <p>Assuming you want a practical answer to "I have too many cards to hold in my hands at once; how do I shuffle them reasonably well in a relatively short amount of time?", you might want to consider a "parallel shuffle", distributing the work over several players in hopes that we can get an adequately shuffled deck in less wall-clock minutes than a single-person shuffle, even if it requires more total operations and player-minutes than a single-person shuffle.</p> <p>I am reminded of the "FFT butterfly diagram" used in digital signal processing and the "Omega Network" used in some computer clusters, based on the "perfect shuffle interconnection".</p> <p><a href="http://www.ece.ucsb.edu/~kastner/ece15b/project1/fft_description_files/image032.jpg" rel="nofollow">http://www.ece.ucsb.edu/~kastner/ece15b/project1/fft_description_files/image032.jpg</a></p> <p><a href="http://github.com/vijendra/Omega-network/raw/master/16X16.png" rel="nofollow">http://github.com/vijendra/Omega-network/raw/master/16X16.png</a></p> <p>Parallel shuffle-deal-shuffle algorithm: (for $k \le n$)</p> <ul> <li>somehow give k players n cards each (either grab a block of n cards off the top for each player, or evenly deal the cards to the k players)</li> <li>shuffle: each of the k players uniformly shuffles their sub-deck of n cards</li> <li>deal: each of the k players evenly deals -- face down -- her sub-deck to the k other players (including herself). Equivalently, each player breaks her sub-deck into k equal sub-sub-decks, and distributes one sub-sub-deck to each player (including herself). After all the players have dealt, each player gathers her cards (a few from each player, including herself) into one sub-deck of n cards.</li> <li>shuffle: (as above)</li> </ul> <p>By this stage (1 round), we have done the equivalent to randomizing each row of a matrix, then each column. Any particular single card could be <em>anywhere</em> after one round of shuffle-deal-shuffle, with equal probability. Alas, at this stage, there are still a few permutations that have probability zero. For example, the possible permutations equivalent to a rotation by shear (RBS) ("how do I rotate a bitmap?") require 3 shears. The closest that a single round of shuffle-deal-shuffle can produce is 2 shears, which is not enough to produce those permutations. So we continue with the second round:</p> <ul> <li>deal: (as above)</li> <li>shuffle: (as above)</li> <li>gather all the sub-decks into one large full deck</li> </ul> <p>The full 2-round shuffle-deal-shuffle-deal-shuffle algorithm can produce any possible permutation, but each permutation does not have exactly the same probability.</p> <p>Each of the two "deal" steps mixes at least as well as a single riffle shuffle of the entire kn cards. The paper -- by Dave Bayer and Persi Diaconis -- that David Speyer mentioned proves that $m = \frac{3}{2} \log_2 (kn) + \theta$ riffle shuffles are sufficient.</p>