show/hide this revision's text 3 Rollback to Revision 1 - Rolled back to pose the variation in a new question

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 $M$ 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? (Edit the answer is no, see David Speyer answer). If yes, how many shuffles are necessary, or sufficient, to achieve that ? If not, at what speed can the distribution approach uniform?

There are plenty of measures of uniformity, among which the total variation distance to uniform distribution and the value of the entropy of the distribution (which is maximal for the uniform distribution), but let's consider the following. Call a random permutation $\sigma$ of $\{1,\ldots,M\}$ $r$-uniform if the law of $(\sigma(a_1),\ldots, \sigma(a_r))$ is uniform for all tuples $(a_1,\ldots,a_r)$ of $\{1,\ldots,M\}$. Then, natural questions are: what is the maximal such $r$? Given a $r$, how many shuffles are needed to achieve

The case $r$-uniformity?

Note that this measure of uniformity makes sense for Race for the galaxy, since some subsets of cards play well together, and one wants to break the artificial weight given when playing a game to the event that such cards are closek=2$ seems already interesting.
show/hide this revision's text 2 Rephrased the question consequently to D.Speyer's answer.

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$ M$ 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? (Edit the answer is no, see David Speyer answer). If yes, how many shuffles are necessary, or sufficient, to achieve that ?

The case If not, at what speed can the distribution approach uniform?

There are plenty of measures of uniformity, among which the total variation distance to uniform distribution and the value of the entropy of the distribution (which is maximal for the uniform distribution), but let's consider the following. Call a random permutation $k=2$ seems already interesting\sigma$ of $\{1,\ldots,M\}$ $r$-uniform if the law of $(\sigma(a_1),\ldots, \sigma(a_r))$ is uniform for all tuples $(a_1,\ldots,a_r)$ of $\{1,\ldots,M\}$. Then, natural questions are: what is the maximal such $r$? Given a $r$, how many shuffles are needed to achieve $r$-uniformity?

Note that this measure of uniformity makes sense for Race for the galaxy, since some subsets of cards play well together, and one wants to break the artificial weight given when playing a game to the event that such cards are close.
show/hide this revision's text 1

How to shuffle a deck by parts?

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.