algorithm - fisher - ¿Qué distribución obtienes de este aleatorio cambio aleatorio?

fisher-yates

Question

El famoso algoritmo aleatorio Fisher-Yates se puede usar para permutar aleatoriamente una matriz A de longitud N:

For k = 1 to N
    Pick a random integer j from k to N
    Swap A[k] and A[j]

Un error común que me han dicho una y otra vez que no debo hacer es esto:

For k = 1 to N
    Pick a random integer j from 1 to N
    Swap A[k] and A[j]

Es decir, en lugar de elegir un número entero aleatorio de k a N, eliges un entero aleatorio de 1 a N.

¿Qué pasa si cometes este error? Sé que la permutación resultante no está distribuida uniformemente, pero no sé qué garantías hay de cuál será la distribución resultante. En particular, ¿alguien tiene una expresión para las distribuciones de probabilidad sobre las posiciones finales de los elementos?

Answer 1

¡Qué hermosa pregunta! Ojalá tuviera una respuesta completa.

Fisher-Yates es agradable de analizar porque una vez que decide sobre el primer elemento, lo deja en paz. El prejuiciado puede intercambiar un elemento repetidamente dentro y fuera de cualquier lugar.

Podemos analizar esto de la misma manera que lo haríamos con una cadena de Markov, describiendo las acciones como matrices de transición estocásticas que actúan de forma lineal en las distribuciones de probabilidad. La mayoría de los elementos se dejan solos, la diagonal suele ser (n-1) / n. En el pase k, cuando no se dejan solos, se intercambian con el elemento k (o un elemento aleatorio si son elemento k). Esto es 1 / (n-1) en cualquier fila o columna k. El elemento tanto en la fila como en la columna k también es 1 / (n-1). Es bastante fácil multiplicar estas matrices juntas para k yendo de 1 a n.

Sabemos que el elemento en último lugar tendrá la misma probabilidad de haber estado originalmente en alguna parte porque el último pase cambia el último lugar igual de probable con cualquier otro. Del mismo modo, el primer elemento tendrá la misma probabilidad de colocarse en cualquier lugar. Esta simetría se debe a que la transposición invierte el orden de la multiplicación de la matriz. De hecho, la matriz es simétrica en el sentido de que la fila i es la misma que la columna (n + 1 - i). Más allá de eso, los números no muestran un patrón aparente. Estas soluciones exactas muestran acuerdo con las simulaciones ejecutadas por belisarius: en la ranura i, la probabilidad de obtener j disminuye a medida que j sube a i, alcanzando su valor más bajo en i-1, y luego saltando a su valor más alto en i, y disminuyendo hasta que j llegue a n.

En Mathematica genere cada paso con

 step[k_, n_] := Normal[SparseArray[{{k, i_} -> 1/n, 
                      {j_, k} -> 1/n, {i_, i_} -> (n - 1)/n} , {n, n}]]

(No he encontrado documentado en ninguna parte, pero se usa la primera regla de coincidencia). La matriz de transición final se puede calcular con:

Fold[Dot, IdentityMatrix[n], Table[step[m, n], {m, s}]]

ListDensityPlot es una herramienta de visualización útil.

Editar (por belisarius)

Solo una confirmación. El siguiente código da la misma matriz que en la respuesta de @ Eelvex:

step[k_, n_] := Normal[SparseArray[{{k, i_} -> (1/n), 
                      {j_, k} -> (1/n), {i_, i_} -> ((n - 1)/n)}, {n, n}]];
r[n_, s_] := Fold[Dot, IdentityMatrix[n], Table[step[m, n], {m, s}]];
Last@Table[r[4, i], {i, 1, 4}] // MatrixForm

Answer 2

Digamos

• a = 1/N
• b = 1-a
• B _i (k) es la matriz de probabilidad después de que canjee por el k ésimo elemento. es decir, la respuesta a la pregunta "¿dónde está k después de que canjee?". Por ejemplo B ₀ (3) = (0 0 1 0 ... 0) y B ₁ (3) = (a 0 b 0 ... 0) . Lo que quiere es B _N (k) para cada k.
• K _i es una matriz NxN con 1s en la columna i-ésima y la fila i-ésima, ceros en cualquier otro lugar, por ejemplo:

• I _i es la matriz de identidad pero con el elemento x = y = i en cero. Por ejemplo, para i = 2:

• A _i es

Entonces,

Pero como B _N (k = 1..N) forma la matriz de identidad, la probabilidad de que cualquier elemento dado i esté al final en la posición j viene dada por el elemento de matriz (i, j) de la matriz:

Por ejemplo, para N = 4:

Como diagrama para N = 500 (los niveles de color son 100 * probabilidad):

El patrón es el mismo para todos N> 2:

• La posición final más probable para el elemento k-ésimo es k-1 .
• La posición final menos probable es k para k <N * ln (2) , posición 1 de lo contrario

Answer 3

El "error común" que mencionas es el barajado por transposiciones aleatorias. Este problema fue estudiado en detalle por Diaconis y Shahshahani en Generación de una permutación aleatoria con transposiciones aleatorias (1981) . Hacen un análisis completo de los tiempos de parada y la convergencia a la uniformidad. Si no puede obtener un enlace al documento, envíeme un correo electrónico y le enviaré una copia. En realidad, es una lectura divertida (como la mayoría de los documentos de Persi Diaconis).

Si la matriz tiene entradas repetidas, entonces el problema es ligeramente diferente. Como un enchufe desvergonzado, este problema más general es abordado por mí mismo, Diaconis y Soundararajan en el Apéndice B de Una Regla de oro para Riffle Shuffling (2011) .

Answer 4

Esta pregunta está pidiendo un análisis interactivo del diagrama de matriz visual de la mezcla aleatoria mencionada. Tal herramienta está en la página Will It Shuffle? - Por qué los comparadores aleatorios son malos por Mike Bostock.

Bostock ha creado una excelente herramienta que analiza comparadores aleatorios. En el menú desplegable de esa página, elija un intercambio ingenuo (aleatorio ↦ aleatorio) para ver el algoritmo roto y el patrón que produce.

Su página es informativa ya que le permite a uno ver los efectos inmediatos que un cambio en la lógica tiene en los datos mezclados. Por ejemplo:

Este diagrama matricial que utiliza una mezcla aleatoria no uniforme y muy sesgada se produce utilizando un intercambio ingenuo (elegimos de "1 a N") con un código como este:

function shuffle(array) {
    var n = array.length, i = -1, j;
    while (++i < n) {
        j = Math.floor(Math.random() * n);
        t = array[j];
        array[j] = array[i];
        array[i] = t;
    }
}

Pero si implementamos una mezcla aleatoria no sesgada, donde elegimos de "k a N" deberíamos ver un diagrama como este:

donde la distribución es uniforme, y se produce a partir de un código como:

function FisherYatesDurstenfeldKnuthshuffle( array ) {
    var pickIndex, arrayPosition = array.length;
    while( --arrayPosition ) {
        pickIndex = Math.floor( Math.random() * ( arrayPosition + 1 ) );
        array[ pickIndex ] = [ array[ arrayPosition ], array[ arrayPosition ] = array[ pickIndex ] ][ 0 ];
    }
}

Answer 5

He investigado esto más a fondo, y resulta que esta distribución se ha estudiado detenidamente. La razón de su interés es porque este algoritmo "roto" es (o fue) utilizado en el sistema de chips RSA.

En Shuffling por transposiciones semialeatorias, Elchanan Mossel, Yuval Peres y Alistair Sinclair estudian esto y una clase más general de baraja. El resultado de ese documento parece ser que toma log(n) mezclas rotas para lograr una distribución casi aleatoria.

En The bias of three pseudorandom shuffles ( Aequationes Mathematicae , 22, 1981, 268-292), Ethan Bolker y David Robbins analizan esta mezcla y determinan que la distancia de variación total a la uniformidad después de un pase único es 1, lo que indica que no es muy al azar en absoluto. También dan análisis asympotic.

Finalmente, Laurent Saloff-Coste y Jessica Zuniga encontraron un buen límite superior en su estudio de cadenas de Markov no homogéneas.

Answer 6

Las excelentes respuestas dadas hasta ahora se concentran en la distribución, pero usted también ha preguntado "¿Qué sucede si comete este error?" - que es lo que no he visto respondido todavía, entonces voy a dar una explicación sobre esto:

El algoritmo aleatorio de Knuth-Fisher-Yates selecciona 1 de n elementos, luego 1 de n-1 elementos restantes y así sucesivamente.

Puede implementarlo con dos matrices a1 y a2 donde elimina un elemento de a1 e insertalo en a2, pero el algoritmo lo hace en su lugar (lo que significa que solo necesita una matriz), como se explica here (Google: " Mezclar Algoritmos Fisher-Yates DataGenetics ") muy bien.

Si no eliminas los elementos, pueden elegirse aleatoriamente de nuevo, lo que produce la aleatoriedad sesgada. Esto es exactamente lo que hace el segundo ejemplo que estás describiendo. El primer ejemplo, el algoritmo Knuth-Fisher-Yates, utiliza una variable de cursor que va de k a N, que recuerda qué elementos ya se han tomado, evitando así elegir elementos más de una vez.

Answer 7

Puede calcular la distribución utilizando matrices estocásticas . Deje que la matriz A (i, j) describa la probabilidad de que la tarjeta originalmente en la posición i termine en la posición j. Entonces el k-swap tiene una matriz Ak dada por Ak(i,j) = 1/N si i == k o j == k , (la carta en la posición k puede terminar en cualquier lado y cualquier carta puede terminar en la posición k con la misma probabilidad), Ak(i,i) = (N - 1)/N para todo i != k (cada otra carta permanecerá en el mismo lugar con probabilidad (N-1) / N) y todos los demás elementos serán cero .

El resultado de la mezcla completa viene dado por el producto de las matrices AN ... A1 .

Espero que estés buscando una descripción algebraica de las probabilidades; puede obtener uno expandiendo el producto matriz anterior, pero imagino que será bastante complejo.

ACTUALIZACIÓN: ¡Acabo de descubrir la respuesta equivalente de wnoise anterior! Uy ...

Answer 8

Sabía que había visto esta pregunta antes ...

" ¿por qué este algoritmo aleatorio simple produce resultados parciales? ¿qué es una razón simple? " tiene muchas cosas buenas en las respuestas, especialmente un enlace a un blog de Jeff Atwood sobre Coding Horror .

Como ya habrás adivinado, según la respuesta de @belisarius, la distribución exacta depende en gran medida de la cantidad de elementos que se barajan. Aquí está la trama de Atwood para una baraja de 6 elementos:

Answer 9

La página de Wikipedia sobre la mezcla aleatoria de Fisher-Yates tiene una descripción y un ejemplo de lo que sucederá exactamente en ese caso.

Answer 10

Un enfoque empírico.

Implementemos el algoritmo erróneo en Mathematica:

p = 10; (* Range *)
s = {}
For[l = 1, l <= 30000, l++, (*Iterations*)
   a = Range[p];
   For[k = 1, k <= p, k++, 
     i = RandomInteger[{1, p}];
     temp = a[[k]];
     a[[k]] = a[[i]];
     a[[i]] = temp
   ];
   AppendTo[s, a];
]  

Ahora obtenga el número de veces que cada entero está en cada posición:

r = SortBy[#, #[[1]] &] & /@ Tally /@ Transpose[s]  

Tomemos tres posiciones en las matrices resultantes y graficamos la distribución de frecuencias para cada entero en esa posición:

Para la posición 1, la distribución de frecuencia es:

Para la posición 5 (centro)

Y para el puesto 10 (último):

y aquí tienes la distribución para todas las posiciones trazadas juntas:

Aquí tienes mejores estadísticas sobre 8 posiciones:

Algunas observaciones:

• Para todas las posiciones, la probabilidad de "1" es la misma (1 / n).
• La matriz de probabilidad es simétrica con respecto a la gran diagonal
• Entonces, la probabilidad para cualquier número en la última posición también es uniforme (1 / n)

Puede visualizar aquellas propiedades que miren el inicio de todas las líneas desde el mismo punto (primera propiedad) y la última línea horizontal (tercera propiedad).

La segunda propiedad se puede ver en el siguiente ejemplo de representación de matriz, donde las filas son las posiciones, las columnas son el número de ocupante, y el color representa la probabilidad experimental:

Para una matriz 100x100:

Editar

Solo por diversión, calculé la fórmula exacta para el segundo elemento diagonal (el primero es 1 / n). El resto se puede hacer, pero es mucho trabajo.

h[n_] := (n-1)/n^2 + (n-1)^(n-2) n^(-n)

Valores verificados de n = 3 a 6 ({8/27, 57/256, 564/3125, 7105/46656})

Editar

Resolviendo un poco el cálculo general explícito en la respuesta de @wnoise, podemos obtener un poco más de información.

Sustituyendo 1 / n por p [n], para que los cálculos se mantengan sin evaluar, obtenemos por ejemplo para la primera parte de la matriz con n = 7 (haga clic para ver una imagen más grande):

Que, después de comparar con los resultados de otros valores de n, identifiquemos algunas secuencias enteras conocidas en la matriz:

{{  1/n,    1/n      , ...},
 {... .., A007318, ....},
 {... .., ... ..., ..},
 ... ....,
 {A129687, ... ... ... ... ... ... ..},
 {A131084, A028326 ... ... ... ... ..},
 {A028326, A131084 , A129687 ... ....}}

Puede encontrar esas secuencias (en algunos casos con diferentes signos) en el maravilloso http://oeis.org/

Resolver el problema general es más difícil, pero espero que esto sea un comienzo