Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This question is mainly a curiosity, but comes from a practical experience (all players of Race for the galaxy, for example, must have ask themselves the question).

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.

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 ?

The case $k=2$ seems already interesting.

share|improve this question
    
You should probably specify: no randomness is allowed in steps 1 (cutting) or 2 (gathering). If one may use randomness in either of these steps one can shuffle exactly without step 3 (shuffling). Eg trivially if one can gather randomly, I'll just cut into $kn$ decks of one card each, and reassemble them in a uniformly random order. If one has to gather deterministically but can cut randomly, it's a bit more complicated but one can still implement a simple exact shuffle (for example, the one that, for i=0 to n-2, moves a card uniformly chosen from the top n-i cards into position n-i). –  James Martin Jul 20 '10 at 13:26
1  
Upon reading just the title of your question, I immediately thought of Race for the Galaxy. –  Richard Dore Jul 20 '10 at 15:02
    
@James Martin: you are right, that is what the "remembering" and "not intertwin nor change order" parts were intended for. –  Benoît Kloeckner Jul 20 '10 at 21:19
1  
Also relevant for Magic: The Gathering :-) –  Greg Friedman Jul 21 '10 at 1:23

3 Answers 3

up vote 14 down vote accepted

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.

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 Trailing the Dovetail Shuffle to its Lair.

share|improve this answer
    
Nice! This reminds me of my favorite proof that the 'naive shuffle' (for i=1..n, set j=rand(1..n) and swap cards i and j) can't possibly give a uniform result: there are n^n equally likely computation paths through the loop (n independent choices of j for each of the n values of i) and this can't possibly divide evenly into n! because of the presence of primes p < n which don't divide n. –  Steven Stadnicki Aug 19 '10 at 17:45

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.

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".

http://www.ece.ucsb.edu/~kastner/ece15b/project1/fft_description_files/image032.jpg

http://github.com/vijendra/Omega-network/raw/master/16X16.png

Parallel shuffle-deal-shuffle algorithm: (for $k \le n$)

  • 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)
  • shuffle: each of the k players uniformly shuffles their sub-deck of n cards
  • 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.
  • shuffle: (as above)

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 anywhere 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:

  • deal: (as above)
  • shuffle: (as above)
  • gather all the sub-decks into one large full deck

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.

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.

share|improve this answer

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.

As David points out, this is necessarily impossible if there exists a prime $p$ for which $n < 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?

share|improve this answer
1  
I would like to point out that David's proof actually settles the question for any real $k>1$ and sufficiently large $n$ (how large depends on $k$), by the generalization of Chebyshev's theorem and the observation in the first sentence of yyour second paragraph. So this new question is only open for $1<k<2$ and small $n$. –  Daniel Litt Jul 20 '10 at 20:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.