18
$\begingroup$

It is a famous result of Aldous and Diaconis1 that

seven shuffles are necessary and suffice to approximately randomize 52 cards.2

Here the shuffles are the standard riffle shuffle, where the deck of cards is cut approximately in half and then the two halves "riffled" (interleaved) together. The randomization is measured by the total variation distance to the uniform distribution. (References below.)

I was exploring a rough model of soil erosion that can be viewed (with some distortion) as a 3D riffle shuffle. Let me explain it in 2D.

Rather than a linear deck of $n$ cards, suppose the cards are arranged in a square $\sqrt{n} \times \sqrt{n}$ matrix $M$. Below I show a $6 \times 6$ matrix of cards/numbers. The matrix is cut into two halves $A$ and $B$, and then reassembled by randomly selecting items from matrix entries on either side of the cut interface. Note that here there is a (perhaps significant?) difference from riffle shuffling, which selects from the top of both halves, rather than selecting from either side of the cut.

Just as in the Aldous/Diaconis work, the probability of taking from $A$ is $|A|/(|A|+|B|)$, and similarly from $B$. The "interface" from which an entry might be selected drills down the columns, i.e., any entry that is exposed above might be selected. The process is illustrated below in several snapshots, leading to a reassembled matrix $M'$.
      Shuffle2D
One might view the "cards" in the matrix as units of soil or rock, and the halving cut as a fissure through which water carries away the soil and deposits in a new matrix $M'$.

My question is simple:

Q. Does this 2D shuffle, or its 3D analog, mix the $n$ elements faster than a riffle shuffle of $n$ items in a linear deck of cards?

In 3D, the $n$ items in are in a $(n^{\frac{1}{3}})^3$ cube. My hunch answer to Q is Yes, because the interface from which the items are drawn is "larger" in some sense. But given the complexity of the Aldous/Diaconis analysis, I do not trust my intuition. Thanks for insights or references!


(Detail added for clarity.) The matrix $M'$ is filled row-by-row, left-to-right. Here is an accounting of the above example.

  1. $B$ is chosen. Among $(19,20,21,22,23,24)$, $24$ is selected and placed in the $(1,1)$ cell of $M'$.
  2. $A$ is chosen. Among $(13,14,15,16,17,18)$, $16$ is selected and placed in the $(1,2)$ cell of $M'$.
  3. $A$ is chosen. Among $(13,14,15,10,17,18)$, $17$ is selected and placed in the $(1,3)$ cell of $M'$.
  4. $A$ is chosen. Among $(13,14,15,10,11,18)$, $10$ is selected and placed in the $(1,4)$ cell of $M'$.
  5. $A$ is chosen. Among $(13,14,15,4,11,18)$, $15$ is selected and placed in the $(1,5)$ cell of $M'$.
  6. $B$ is chosen. Among $(19,20,21,22,23,30)$, $19$ is selected and placed in the $(1,6)$ cell of $M'$.
  7. Etc., next filling the $(2,1)$ cell of $M'$ with $20$, and so on.


1 David Aldous and Persi Diaconis, "Shuffling cards and stopping times." American Mathematical Monthly 93, 1986, 333-48. (JSTOR link)

2 David Austin, "How Many Times Do I Have to Shuffle This Deck?" MAA Feature Column. (MAA link)

$\endgroup$
2
  • $\begingroup$ Could you tell us more about 1) How the entries are selected for removal from the round $n$ matrix and insertion into the round $n+1$ matrix; and 2) When things are removed from the round $n$ matrix, in which way are they inserted into the round $n+1$ matrix? $\endgroup$ Mar 17, 2013 at 3:19
  • $\begingroup$ @Anthony: Sorry for the poor description! I tried to clarify now with an added section. $\endgroup$ Mar 17, 2013 at 13:20

1 Answer 1

6
$\begingroup$

I didn't understand the exact details of the shuffling method, so I cannot completely answer the question. However, it seems like the entropy you introduce in each shuffle is linear in $n$ (as in riffle shuffle). Since the entropy of a uniform permutation is $\Theta(n \log(n))$, you need at least $\Theta(\log(n))$ shuffles, so the mixing cannot be faster then riffle shuffle by more than a multiplicative constant.

$\endgroup$
3
  • $\begingroup$ @Ori: Thanks for the illuminating high-level viewpoint! Could you expand a bit on why the entropy introduced in each shuffle (of the riffle, to avoid the complexities of my situation) is linear in $n$? I don't doubt you; I just don't know enough to appreciate this perspective. It makes sense that the order of growth is the same, but perhaps the multiplicative constant is smaller. $\endgroup$ Mar 16, 2013 at 21:17
  • 1
    $\begingroup$ I think the rough idea is this: if there are $K$ different outcomes in each round of shuffling, then since there are $n!$ possible orders of the deck, it must take at least $\log n!/\log K\approx n\log n/\log K$ steps before there is any chance that the deck is shuffled. The entropy is the $\log K$, and can be thought of as a measure of the amount of randomness that's introduced. $\endgroup$ Mar 17, 2013 at 5:41
  • $\begingroup$ @Anthony Quas: But $K\approx2\sqrt n$ so the lower bound is just two shuffles. Right? $\endgroup$
    – Charles
    Mar 17, 2013 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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