¿La erosión se mezcla más rápido que un riffle shuffle?

Question

Es un famoso resultado de Aldous y Diaconis 1 que

siete barajadas son necesarias y suficientes para app aleatorizar 52 cartas. 2

Aquí los barajados son el barajado de riffle estándar, donde la baraja de cartas se corta aproximadamente por la mitad y luego las dos mitades se "barajan" (intercalan) juntas. La aleatoriedad se mide por el distancia de variación total a la distribución uniforme. (Referencias más abajo.)

Estaba explorando un modelo aproximado de erosión del suelo que puede ser visto (con alguna distorsión) como un riffle shuffle en 3D. Permítanme explicarlo en 2D.

En lugar de una baraja lineal de $n$ cartas, supongamos que las cartas están dispuestas en un cuadrado $\sqrt{n} \times \sqrt{n}$ matriz $M$ . A continuación muestro un $6 \times 6$ matriz de tarjetas/números. La matriz se corta en dos mitades $A$ y $B$ , y luego se reensamblan seleccionando aleatoriamente elementos de las entradas de la matriz a ambos lados de la interfaz cortada. Obsérvese que aquí hay una diferencia (¿quizá significativa?) de la barajadura de riffle, que selecciona de la parte superior de ambas mitades, en lugar de seleccionar de cada lado del corte.

Al igual que en el trabajo de Aldous/Diaconis, la probabilidad de tomar de $A$ es $|A|/(|A|+|B|)$ y análogamente de $B$ . La "interfaz" desde la que se puede seleccionar una entrada perfora hacia abajo en las columnas, es decir, se puede seleccionar cualquier entrada ser seleccionada. El proceso se ilustra a continuación en varias instantáneas, que conducen a una matriz reensamblada $M'$ .
     
Se podría considerar que las "cartas" de la matriz son unidades de suelo o roca, y el corte por la mitad como una fisura a través de la cual el agua arrastra el suelo y lo deposita en una nueva matriz $M'$ .

Mi pregunta es sencilla:

Q . ¿Este barajado 2D, o su análogo 3D, mezcla el $n$ e más rápido que una barajada de $n$ elementos de una baraja lineal?

En 3D, el $n$ artículos en están en un $(n^{\frac{1}{3}})^3$ cubo. Mi corazonada responde a Q es Sí porque la interfaz de de la que se extraen los elementos es "más grande" en cierto sentido. Pero dada la complejidad del análisis Aldous/Diaconis, no me fío de mi intuición. Gracias por las ideas o las referencias.

---

( Detalle añadido para mayor claridad. ) La matriz $M'$ se rellena fila por fila, de izquierda a derecha. Aquí una explicación del ejemplo anterior.

1. $B$ se elige. En $(19,20,21,22,23,24)$ , $24$ se selecciona y se coloca en el $(1,1)$ célula de $M'$ .
2. $A$ se elige. En $(13,14,15,16,17,18)$ , $16$ se selecciona y se coloca en el $(1,2)$ célula de $M'$ .
3. $A$ se elige. En $(13,14,15,10,17,18)$ , $17$ se selecciona y se coloca en el $(1,3)$ célula de $M'$ .
4. $A$ se elige. En $(13,14,15,10,11,18)$ , $10$ se selecciona y se coloca en el $(1,4)$ célula de $M'$ .
5. $A$ se elige. En $(13,14,15,4,11,18)$ , $15$ se selecciona y se coloca en el $(1,5)$ célula de $M'$ .
6. $B$ se elige. En $(19,20,21,22,23,30)$ , $19$ se selecciona y se coloca en el $(1,6)$ célula de $M'$ .
7. Etc., rellenando a continuación el $(2,1)$ célula de $M'$ con $20$ etc.

---

1 David Aldous y Persi Diaconis, "Barajando cartas y parando tiempos". American Mathematical Monthly 93, 1986, 333-48. ( Enlace JSTOR )

2 David Austin, "¿Cuántas veces tengo que barajar este mazo?" Columna MAA . ( Enlace MAA )

Answer 1

No entendí los detalles exactos del método de barajado, así que no puedo responder completamente a la pregunta. Sin embargo, parece que la entropía que introduces en cada barajada es lineal en $n$ (como en riffle shuffle). Dado que la entropía de una permutación uniforme es $\Theta(n \log(n))$ necesita al menos $\Theta(\log(n))$ barajadas, por lo que la mezcla no puede ser más rápida que la barajada riffle por más de una constante multiplicativa.