¿Cuán asintóticamente malo es el ingenuo barajado?

33

Es bien sabido que este algoritmo 'ingenuo' para barajar una matriz intercambiando cada elemento con otro elegido al azar no funciona correctamente:

for (i=0..n-1)
  swap(A[i], A[random(n)]);

Específicamente, dado que en cada una de las iteraciones, se realiza una de las elecciones (con probabilidad uniforme), hay posibles 'caminos' a través del cálculo; porque el número de posibles permutacionesno se divide equitativamente en el número de rutas , ¡es imposible que este algoritmo produzca cada una de laspermutaciones con igual probabilidad. (En cambio, uno debería usar el llamado shuffle de Fischer-Yates , que esencialmente cambia la llamada para elegir un número aleatorio de [0..n) con una llamada para elegir un número aleatorio de [i..n); eso es discutible para mi pregunta, sin embargo).n n ! n n n !nnnnn!nnn!

Lo que me pregunto es, ¿qué tan 'malo' puede ser el shuffle ingenuo? Más específicamente, dejando que sea ​​el conjunto de todas las permutaciones y sea ​​el número de caminos a través del algoritmo ingenuo que produce la permutación resultante , ¿cuál es el comportamiento asintótico de la funcionesC ( ρ ) ρ P ( n )P(n)C(ρ)ρP(n)

M(n)=n!nnmaxρP(n)C(ρ)

y

m(n)=n!nnminρP(n)C(ρ) ?

El factor principal es 'normalizar' estos valores: si la combinación ingenua es 'asintóticamente buena', entonces

limnM(n)=limnm(n)=1 .

Sospecho (en base a algunas simulaciones por computadora que he visto) que los valores reales están delimitados por 1, pero incluso se sabe si limM(n) es finito, o si limm(n) está delimitado por 0? ¿Qué se sabe sobre el comportamiento de estas cantidades?

Steven Stadnicki
fuente
8
Buena pregunta. No sé cuál es el mejor lugar para esta pregunta. A menos que esté claro que otro foro es mejor para él, creo que debería dejarlo aquí durante una semana más o menos, y si no obtiene una respuesta satisfactoria, pregúntelo en uno de los otros foros (y ponga enlaces en ambas preguntas) )
Peter Shor
44
@vzn "¿Por qué hacer un análisis exhaustivo de un algoritmo defectuoso conocido?" Debido a que las matemáticas son interesantes y nunca se sabe dónde pueden surgir otras aplicaciones, vea el análisis de Knuth sobre Bubble Sort, por ejemplo. Los gráficos de Atwood ofrecen un análisis cualitativo aproximado de la falta de homogeneidad, pero eso está muy lejos de un análisis matemáticamente cuantitativo. (Y hay varias formulaciones equivalentes diferentes de la mezcla de Fischer-Yates, la que menciono funciona bien)
Steven Stadnicki,
44
Para el registro, la secuencia OEIS A192053 es max y no enumera una forma cerrada. Además, las notas para esa entrada sugieren que min puede ser , lo que implica que . C ( ρ ) 2 n - 1 m ( n ) 0C(ρ)C(ρ)2n1m(n)0
mhum
2
@vzn ¿Qué hay de malo con las preguntas abiertas?
Yuval Filmus
1
@vzn No está de acuerdo con su última oración, hay muchos análisis de barajaduras "imperfectas". Por ejemplo, si hacemos transposiciones aleatorias, se sabe que el umbral de aleatoriedad es aproximadamente . La pregunta actual puede ser difícil, pero a priori es difícil decir si es "muy difícil". Una respuesta como la de mhum ya es muy satisfactoria, ya que muestra que la pregunta era apropiada para el foro y no presentaba una barrera insuperable (se dejan de lado las pruebas formales). (1/2)nlogn
Yuval Filmus el

Respuestas:

13

por inducción que la permutación es un ejemplo con . Si este es el peor de los casos, como lo es para los primeros (vea las notas para la secuencia OEIS A192053 ), entonces . Entonces, el mínimo normalizado, como el máximo normalizado, es 'exponencialmente malo'.ρn=(2,3,4,,n,1) n m ( n ) ( 2 / e ) nC(ρn)=2n1nm(n)(2/e)n

El caso base es fácil. Para el paso de inducción, necesitamos un lema:

Lema: En cualquier ruta de a , el primer movimiento intercambia las posiciones y , o el último movimiento intercambia las posiciones y .( 1 , 2 , 3 , , n ) 1 n 1 n(2,3,4,,n,1)(1,2,3,,n)1n1n

Bosquejo de prueba: supongamos que no. Considere el primer movimiento que implica la -ésima posición. Asumo que es la -ésima movimiento, y . Este movimiento debe colocar el elemento en el lugar . Ahora considere el siguiente movimiento que toca el elemento . Suponga que este movimiento es el 'ésimo movimiento. Este movimiento debe intercambiar y , moviendo el elemento al lugar , con . Un argumento similar dice que el elemento solo se puede mover posteriormente a la derecha. Pero el artículoi i 1 i n 1 i 1 j i j 1 j i < j 1 1 nii1in1i1jij1ji<j11necesita terminar en primer lugar, una contradicción.

Ahora bien, si los primeros swaps mover las posiciones y , los restantes mueve deben tomar la permutación a . Si los movimientos restantes no tocan la primera posición, entonces esta es la permutación en las posiciones , y sabemos por inducción que hay caminos que hacen esto. Un argumento similar a la prueba del Lema dice que no hay camino que toque la primera posición, ya que el elemento debe terminar en la posición incorrecta.n ( 1 , 3 , 4 , 5 , , n , 2 ) ( 1 , 2 , 3 , 4 , , n ) ρ n - 1 2 n C ( ρ n - 1 ) = 2 n - 2 11n(1,3,4,5,,n,2)(1,2,3,4,,n)ρn12nC(ρn1)=2n21

Si las permutas último movimiento las posiciones y , el primer se mueve deben tomar la permutación a la permutación . Nuevamente, si estos movimientos no tocan la última posición, entonces esta es la permutación , y por inducción hay caminos que lo hagas Y nuevamente, si uno de los primeros movimientos aquí toca la última posición, el elemento nunca puede terminar en el lugar correcto.n n - 1 ( 2 , 3 , 4 , , n , 1 ) ( n , 2 , 3 , 4 , , n - 1 , 1 ) ρ n - 1 C ( ρ n - 1 ) = 2 n - 2 n - 1 11nn1(2,3,4,,n,1)(n,2,3,4,,n1,1)ρn1C(ρn1)=2n2n11

Por lo tanto, .C(ρn)=2C(ρn1)=2n1

Peter Shor
fuente
Perfecto: el argumento detrás del lema se parece mucho al que tenía para que las involuciones fueran la única forma de obtener la permutación de identidad, pero me había perdido la estructura recursiva en el intercambio explícito. ¡Gracias!
Steven Stadnicki
10

Después de investigar un poco gracias al puntero de mhum a OEIS, finalmente encontré un excelente análisis y un buen argumento (relativamente) elemental (debido, por lo que puedo decir, a Goldstein y Moews [1]) que crece superexponencialmente rápido en :M(n)n

Cualquier involución de corresponde a una ejecución del algoritmo de barajado 'ingenuo' que produce la permutación de identidad como resultado, ya que el algoritmo intercambiará con y posteriormente intercambiará con , dejando ambos sin cambios. Esto significa que el número de ejecuciones del algoritmo que producen la permutación de identidad es al menos el número de involuciones (de hecho, un poco de pensamiento muestra que la correspondencia es 1-1 y, por lo tanto, es exactamente ) , y entonces el máximo en está limitado desde abajo por .{ 1 n } k ι ( k ) ι ( k ) k Q ( n ) Q ( n ) M ( n ) Q ( n )ι{1n}kι(k)ι(k)kQ(n)Q(n)M(n)Q(n)

Q(n) aparentemente tiene varios nombres, incluidos los números de teléfono : consulte http://oeis.org/A000085 y http://en.wikipedia.org/wiki/Telephone_number_%28mathematics%29 . Las asintóticas son bien conocidas, y resulta que ; a partir de la relación de recurrencia se puede demostrar inductivamente que la relación satisface y de allí el análisis básico obtiene el término en los asintóticos, aunque el otro los términos requieren un esfuerzo más cuidadoso. Desde el 'factor de escala'Q(n)C(ne)n/2enQ(n)=Q(n1)+(n1)Q(n2)R(n)=Q(n)Q(n1)n<R(n)<n+1nn/2n!nn en la definición de trata solo de , el término principal de domina y produce (asintóticamente) .M(n)CnenQ(n)M(n)Cn(n+1)/2e3n/2+n

De hecho, Goldstein y Moews continúan mostrando en [1] que la permutación de identidad es la más probable para grande , por lo que es de hecho a y el comportamiento de está completamente establecido. Esto todavía deja abierta la cuestión del comportamiento de ; No me sorprendería demasiado si eso también se rindiera al análisis en su artículo, pero aún no he tenido la oportunidad de leerlo lo suficientemente de cerca para comprender realmente sus métodos, solo lo suficiente para asimilar el resultado básico.nM(n)m(n)

[1] Goldstein, D. y Moews, D .: "La identidad es el cambio aleatorio más probable para la n grande", http://arxiv.org/abs/math/0010066

Steven Stadnicki
fuente
1
No es demasiado difícil demostrar que la permutación es un ejemplo con . Si este es el peor de los casos, como lo es para los primeros , entonces . C ( ρ ) = 2 n - 1 n m ( n ) ( 2 / e ) n(2,3,4,,n,1)C(ρ)=2n1nm(n)(2/e)n
Peter Shor
@PeterShor ¿Puedes dar el argumento básico? Siento que me falta alguna versión simple del argumento de las involuciones que funcionaría, pero no lo entiendo del todo. Creo que incluso si eso no es mínimo, sería lo suficientemente bueno; el recuento mínimo parece poco probable que sea subexponencial en y solo saber que el máximo y el mínimo normalizados son 'exponencialmente malos' es una respuesta bastante satisfactoria. n
Steven Stadnicki
Agregué una respuesta con el argumento ... es demasiado largo para un comentario.
Peter Shor