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'$.
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.
- $B$ is chosen. Among $(19,20,21,22,23,24)$, $24$ is selected and placed in the $(1,1)$ cell of $M'$.
- $A$ is chosen. Among $(13,14,15,16,17,18)$, $16$ is selected and placed in the $(1,2)$ cell of $M'$.
- $A$ is chosen. Among $(13,14,15,10,17,18)$, $17$ is selected and placed in the $(1,3)$ cell of $M'$.
- $A$ is chosen. Among $(13,14,15,10,11,18)$, $10$ is selected and placed in the $(1,4)$ cell of $M'$.
- $A$ is chosen. Among $(13,14,15,4,11,18)$, $15$ is selected and placed in the $(1,5)$ cell of $M'$.
- $B$ is chosen. Among $(19,20,21,22,23,30)$, $19$ is selected and placed in the $(1,6)$ cell of $M'$.
- 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)