¿Qué tan asintóticamente malo es ingenuo barajando?

Question

Es bien sabido que este algoritmo 'ingenuo' para arrastrar 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 $ n $ iteraciones, se realiza una de las opciones de $ N $ (con probabilidad uniforme), hay $ n^n $ 'rutas' posibles a través del cálculo; Debido a que el número de permutaciones posibles $ N! $ no se divide de manera uniforme en el número de rutas $ n^n $, es imposible que este algoritmo produzca cada una de las permutaciones de $ N! $ con igual probabilidad. (En su lugar, uno debe usar el llamado Fischer-yates Shuffle, 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); Sin embargo, eso es discutible para mi pregunta).

Lo que me pregunto es, ¿qué tan mal "puede ser el ingenuo barato? Más específicamente, dejar que $ P (n) $ sea el conjunto de todas las permutaciones y $ C ( rho) $ ser el número de rutas a través del algoritmo ingenuo que produce la permutación resultante $ rho in p (n) $, qué, qué es el comportamiento asintótico de las funciones

$ qquad displaystyle m (n) = frac {n!} {n^n} max _ { rho in p (n)} c ( rho) $

y

$ qquad displayStyle m (n) = frac {n!} {n^n} min _ { rho in p (n)} c ( rho) $?

El factor principal es "normalizar" estos valores: si la baraja ingenua es "asintóticamente buena", entonces

$ qquad displaystyle lim_ {n a infty} m (n) = lim_ {n a infty} m (n) = 1 $.

Sospecho (según algunas simulaciones de la computadora que he visto) que los valores reales están delimitados de 1, pero incluso se sabe si $ lim m (n) $ es finito, o si $ lim m (n) $ ¿Está limitado de 0? ¿Qué se sabe sobre el comportamiento de estas cantidades?

Answer 1

Mostraremos por inducción que la permutación $ rho_n = (2,3,4, ldots, n, 1) $ es un ejemplo con $ c ( rho_n) = 2^{n-1} $. Si este es el peor de los casos, como es por los primeros $ N $ (consulte las notas para Secuencia de OEIS A192053), entonces $ m (n) aprox (2/e)^{n} $. Entonces, el min normalizado, como el máximo normalizado, es 'exponencialmente malo'.

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

Lema: En cualquier ruta de $ (2,3,4, ldots, n, 1) $ a $ (1,2,3, ldots, n) $, el primer movimiento de swaps posiciona $ 1 $ y $ n $, o o $, o o $, o o $, o o $, o o $, o o $, o o $, o o $, o, o $, o $, o, o $, o $, o $, o $, o $, o $, o $, o $, o. El último movimiento Swaps posiciona $ 1 $ y $ N $.

Boceto de prueba: Supongamos que no. Considere el primer movimiento que implica la posición de $ N $ '. Suponga que es el movimiento de $ i $ ', $ i neq 1 $ y $ i neq n $. Este movimiento debe colocar el artículo $ 1 $ en el lugar de $ i $ '. Ahora considere el próximo movimiento que toca el artículo $ 1 $. Suponga que este movimiento es el movimiento de $ J $ '. Este movimiento debe intercambiar $ i $ y $ j $, moviendo el artículo $ 1 $ en el lugar de $ j $ ', con $ i <j $. Un argumento similar dice que el artículo $ 1 $ solo puede moverse posteriormente a la derecha. Pero el artículo $ 1 $ necesita terminar en primer lugar, una contradicción. $ cuadrado $

Ahora, si el primer movimiento cambia las posiciones $ 1 $ y $ N $, los movimientos restantes deben tomar la permutación $ (1, 3,4,5, ldots, n, 2) $ a $ (1,2,3, 4, ldots, n) $. Si los movimientos restantes no tocan la primera posición, entonces esta es la permutación $ rho_ {n-1} $ en posiciones $ 2 ldots n $, y sabemos por inducción que hay $ c ( rho_ {n- 1}) = 2^{n-2} $ rutas que hacen esto. Un argumento similar a la prueba del lema dice que no hay un camino que toque la primera posición, ya que el artículo $ 1 $ debe terminar en la posición incorrecta.

Si el último movimiento cambia las posiciones $ 1 $ y $ N $, los primeros movimientos de $ N-1 $ deben tomar la permutación $ (2,3,4, ldots, n, 1) $ a la permutación $ (n, 2 , 3,4, ldots, N-1, 1) $. Nuevamente, si estos movimientos no tocan la última posición, entonces esta es la permutación $ rho_ {n-1} $, y por inducción hay $ c ( rho_ {n-1}) = 2^{n- 2} $ rutas que lo hacen. Y nuevamente, si uno de los primeros movimientos $ N-1 $ toca la última posición, el artículo $ 1 $ nunca puede terminar en el lugar correcto.

Por lo tanto, $ c ( rho_n) = 2c ( rho_ {n-1}) = 2^{n-1} $.

Answer 2

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

Cualquier involución $ iota $ de $ {1 ldots n } $ corresponde a una ejecución del algoritmo de barajamiento 'ingenuo' que produce la permutación de identidad como resultado, ya que el algoritmo intercambiará $ K $ con $ iota ( k) $ y posteriormente intercambie $ iota (k) $ con $ k $, 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 involucradas $ Q (n) $ (de hecho, un poco de pensamiento muestra que la correspondencia es 1-1 y, por lo tanto, es exactamente $ Q (( n) $), por lo que el máximo en $ m (n) $ está limitado desde abajo por $ q (n) $.

$ Q (n) $ aparentemente pasa por varios nombres, incluido el números telefónicos : ver http://oeis.org/a000085 y http://en.wikipedia.org/wiki/telephone_number_%28mathematics%29 . Los asíntóticos son bien conocidos, y resulta que $ q (n) aprox c izquierd ( frac {n} {e} right)^{n/2} e^ sqrt {n} $; de la relación de recurrencia $ q (n) = q (n-1)+(n-1) q (n-2) $ se puede demostrar inductivamente que la relación $ r (n) = frac {q (n) } {Q (n-1)} $ satisface $ sqrt {n} lt r (n) lt sqrt {n+1} $ y desde allí el análisis básico obtiene el liderazgo $ n^{n/2} $ término en la asintótica, aunque los otros términos requieren un esfuerzo más cuidadoso. Dado que el 'factor de escala' $ frac {n!} {N^n} $ en la definición de $ m (n) $ es solo alrededor de $ c sqrt {n} e^{-n} $, el término líder de $ q (n) $ domina y produce (asíntóticamente) $ m (n) geq cn^{(n+1)/2} e^{-3n/2+ sqrt {n}} $.

Goldstein y Moews, de hecho, se muestran en [1] que la permutación de identidad es la más probable por $ n $, por lo que el $ geq $ es de hecho un $ aprox $ y el comportamiento de $ m (n) $ está completamente liquidado. Esto todavía deja la cuestión del comportamiento de $ M (n) $ abierto; No me sorprendería demasiado si eso también cediera al análisis en su artículo, pero aún no he tenido la oportunidad de leerlo lo suficiente como para realmente controlar sus métodos, solo lo suficiente como para atribuir el resultado básico.

1] Goldstein, D. y Moews, D.: "La identidad es el cambio de intercambio más probable para N", http://arxiv.org/abs/math/0010066