algorithm - fisher - ¿Por qué este simple algoritmo de reproducción aleatoria produce resultados sesgados? ¿Qué es una razón simple?

shuffle array javascript (12)

Parece que este simple algoritmo de reproducción aleatoria producirá resultados sesgados:

# suppose $arr is filled with 1 to 52 for ($i < 0; $i < 52; $i++) { $j = rand(0, 51); # swap the items $tmp = $arr[j]; $arr[j] = $arr[i]; $arr[i] = $tmp; }

puede intentarlo ... en lugar de usar 52, use 3 (suponga que solo se usan 3 tarjetas), y ejecútelo 10,000 veces y cuente los resultados, verá que los resultados están sesgados hacia ciertos patrones ...

la pregunta es ... ¿qué es una explicación simple de que sucederá?

La solución correcta es usar algo como

for ($i < 0; $i < 51; $i++) { # last card need not swap $j = rand($i, 51); # don''t touch the cards that already "settled" # swap the items $tmp = $arr[j]; $arr[j] = $arr[i]; $arr[i] = $tmp; }

pero la pregunta es ... ¿por qué el primer método, aparentemente también totalmente aleatorio, hará que los resultados sean sesgados?

Actualización 1: gracias por la gente que señala que necesita ser rand ($ i, 51) para que funcione correctamente.

Aquí está el árbol de probabilidad completo para estos reemplazos.

Supongamos que comienza con la secuencia 123, y luego enumeraremos todas las diversas formas de producir resultados aleatorios con el código en cuestión.

Ahora, la cuarta columna de números, la anterior a la información de intercambio, contiene el resultado final, con 27 resultados posibles.

Vamos a contar cuántas veces ocurre cada patrón:

123 - 4 times 132 - 5 times 213 - 5 times 231 - 5 times 312 - 4 times 321 - 4 times ============= 27 times total

Si ejecuta el código que se intercambia aleatoriamente un número infinito de veces, los patrones 132, 213 y 231 se producirán con mayor frecuencia que los patrones 123, 312 y 321, simplemente porque la forma en que se intercambian los códigos hace que sea más probable que ocurran. .

Ahora, por supuesto, puede decir que si ejecuta el código 30 veces (27 + 3), podría terminar con todos los patrones que ocurren 5 veces, pero cuando se trata de estadísticas, debe observar la tendencia a largo plazo.

Aquí está el código C # que explora la aleatoriedad para uno de cada patrón posible:

class Program { static void Main(string[] args) { Dictionary<String, Int32> occurances = new Dictionary<String, Int32> { { "123", 0 }, { "132", 0 }, { "213", 0 }, { "231", 0 }, { "312", 0 }, { "321", 0 } }; Char[] digits = new[] { ''1'', ''2'', ''3'' }; Func<Char[], Int32, Int32, Char[]> swap = delegate(Char[] input, Int32 pos1, Int32 pos2) { Char[] result = new Char[] { input[0], input[1], input[2] }; Char temp = result[pos1]; result[pos1] = result[pos2]; result[pos2] = temp; return result; }; for (Int32 index1 = 0; index1 < 3; index1++) { Char[] level1 = swap(digits, 0, index1); for (Int32 index2 = 0; index2 < 3; index2++) { Char[] level2 = swap(level1, 1, index2); for (Int32 index3 = 0; index3 < 3; index3++) { Char[] level3 = swap(level2, 2, index3); String output = new String(level3); occurances[output]++; } } } foreach (var kvp in occurances) { Console.Out.WriteLine(kvp.Key + ": " + kvp.Value); } } }

Esto produce:

123: 4 132: 5 213: 5 231: 5 312: 4 321: 4

Entonces, si bien esta respuesta sí cuenta, no es una respuesta puramente matemática, solo tiene que evaluar todas las formas posibles en que puede ir la función aleatoria y observar los resultados finales.

Aquí hay otra intuición: el intercambio aleatorio único no puede crear simetría en la probabilidad de ocupar una posición a menos que ya exista al menos una simetría bidireccional. Llame a las tres posiciones A, B y C. Ahora, a sea la probabilidad de que la tarjeta 2 esté en la posición A, b la probabilidad de que la tarjeta 2 esté en la posición B, yc la probabilidad de que esté en la posición C, antes a un movimiento de intercambio. Supongamos que no hay dos probabilidades iguales: a! = B, b! = C, c! = A. Ahora calcule las probabilidades a '', b'' yc ''de la tarjeta que está en estas tres posiciones después de un intercambio. Digamos que este movimiento de intercambio consiste en que la posición C se intercambia con una de las tres posiciones al azar. Entonces:

a'' = a*2/3 + c*1/3 b'' = b*2/3 + c*1/3 c'' = 1/3.

Es decir, la probabilidad de que la tarjeta termine en la posición A es la probabilidad de que ya estuvo allí por 2/3 de las veces que la posición A no está involucrada en el intercambio, más la probabilidad de que esté en la posición C por la 1 / 3 probabilidad de que C cambie con A, etc. Ahora, al restar las dos primeras ecuaciones, obtenemos:

a'' - b'' = (a - b)*2/3

lo que significa que debido a que asumimos a! = b, entonces a ''! = b'' (aunque la diferencia se acercará a 0 con el tiempo, dado suficientes swaps). Pero como a ''+ b'' + c ''= 1, si a''! = B '', ninguno de los dos puede ser igual a c'', que es 1/3. Entonces, si las tres probabilidades comienzan diferentes antes de un intercambio, también serán diferentes después de un intercambio. Y esto se mantendría sin importar qué posición se intercambió, simplemente intercambiamos los roles de las variables de lo anterior.

Ahora, el primer intercambio comenzó intercambiando la tarjeta 1 en la posición A con una de las otras. En este caso, hubo simetría bidireccional antes del intercambio, porque la probabilidad de que la tarjeta 1 en la posición B = probabilidad de la tarjeta 1 en la posición C = 0. Entonces, de hecho, la tarjeta 1 puede terminar con probabilidades simétricas y termina en cada una de las tres posiciones con igual probabilidad. Esto sigue siendo cierto para todos los swaps posteriores. Pero la tarjeta 2 termina en las tres posiciones después del primer intercambio con probabilidad (1/3, 2/3, 0), y de igual modo la tarjeta 3 se enrolla en las tres posiciones con probabilidad (1/3, 0, 2/3) . Así que no importa cuántos swaps posteriores hagamos, nunca terminaremos con la tarjeta 2 o 3 teniendo exactamente la misma probabilidad de ocupar las tres posiciones.

Aquí hay un gran análisis de una tarjeta que baraja cadenas de Markov . Oh, espera, eso es todo matemática. Lo siento. :)

El algoritmo ingenuo elige los valores de n así:

n = rand (3)

3 ^ 3 combinaciones posibles de n

1,1,1, 1,1,2 .... 3,3,2 3,3,3 (27 combinaciones) La respuesta de lassevk muestra la distribución entre las tarjetas de estas combinaciones.

el mejor algoritmo hace:

n = rand (3)

n = rand (2)

¡norte! posibles combinaciones de n

1,1, 1,2, 2,1 2,2 3,1 3,2 (6 combinaciones, todas con un resultado diferente)

Como se mencionó en las otras respuestas, si realiza 27 intentos para obtener 6 resultados, posiblemente no pueda obtener los 6 resultados con una distribución uniforme, ya que 27 no es divisible por 6. Coloque 27 canicas en 6 cubos y no importa lo que haga, algunos Los cubos tendrán más canicas que otros, lo mejor que puede hacer es 4,4,4,5,5,5 canicas para los cubos del 1 al 6.

El problema fundamental con la barajada ingenua es que intercambia demasiadas veces, para barajar 3 cartas por completo, solo necesitas hacer 2 swaps, y la segunda swaps solo debe estar entre las dos primeras, ya que la 3ra carta ya tenía un 1/3. posibilidad de ser cambiado. si continúas intercambiando cartas, tendrás más posibilidades de que una determinada tarjeta sea intercambiada, y estas posibilidades solo se igualarán a 1/3, 1/3, 1/3 si tu combinación de swap total es divisible por 6.

La mejor explicación que he visto para este efecto fue la de Jeff Atwood en su blog CodingHorror ( The Danger of Naïveté ).

Usando este código para simular una mezcla aleatoria de 3 cartas ...

for (int i = 0; i < cards.Length; i++) { int n = rand.Next(cards.Length); Swap(ref cards[i], ref cards[n]); }

... obtienes esta distribución.

El código de orden aleatorio (arriba) da como resultado 3 ^ 3 (27) posibles combinaciones de mazo. ¡Pero las matemáticas nos dicen que en realidad solo hay 3! o 6 combinaciones posibles de un mazo de 3 cartas. Así que algunas de las combinaciones están sobre representadas.

Necesitaría usar un barajar de Fisher-Yates para barajar correctamente (al azar) un mazo de cartas.

La respuesta más clara para mostrar que el primer algoritmo falla es ver el algoritmo en cuestión como una cadena de Markov de n pasos en la gráfica de n. Vértices de toda la permutación de n números naturales. El algoritmo salta de un vértice a otro con una probabilidad de transición. El primer algoritmo da la probabilidad de transición de 1/n para cada salto. Hay n ^ n caminos cuya probabilidad es de 1/n^n . Supongamos que la probabilidad final de aterrizar en cada vértice es 1/n! que es una fracción reducida. Para lograr eso, debe haber m trayectorias con el mismo vértice final de modo que m/n^n=1/n! o n^n = mn! para algún número natural m , o que n^n es divisible por n! . Pero eso es imposible. De lo contrario, n tiene que ser divisible por n-1 que solo es posible cuando n=2 . Tenemos contradicción.

La respuesta simple es que hay 52 ^ 52 formas posibles para que se ejecute este algoritmo, ¡pero solo hay 52! Posibles arreglos de 52 cartas. Para que el algoritmo sea justo, debe producir cada uno de estos acuerdos con la misma probabilidad. 52 ^ 52 no es un múltiplo entero de 52 !. Por lo tanto, algunos arreglos deben ser más probables que otros.

Mira esto:
El peligro de la naïveté (Codificación del horror)

Veamos su mazo de tres cartas como ejemplo. Al usar un mazo de 3 cartas, solo hay 6 órdenes posibles para el mazo después de una orden aleatoria: 123, 132, 213, 231, 312, 321.

Con su primer algoritmo, hay 27 rutas posibles (resultados) para el código, dependiendo de los resultados de la función rand() en diferentes puntos. Cada uno de estos resultados es igualmente probable (imparcial). Cada uno de estos resultados se asignará al mismo resultado individual de la lista de 6 posibles resultados aleatorios "reales" de arriba. Ahora tenemos 27 artículos y 6 cubos para ponerlos. Ya que 27 no es divisible por 6, algunas de esas 6 combinaciones deben estar sobre representadas.

Con el 2º algoritmo, hay 6 resultados posibles que se asignan exactamente a los 6 posibles resultados aleatorios "reales", y todos deberían representarse de manera equitativa en el tiempo.

Esto es importante porque los grupos que están sobre representados en el primer algoritmo no son aleatorios. Los cubos seleccionados para el sesgo son repetibles y predecibles. Entonces, si estás construyendo un juego de póquer en línea y utilizas el primer algoritmo, un pirata informático podría descubrir que usaste el tipo ingenuo y, a partir de ese trabajo, es más probable que ocurran ciertos arreglos de mazo que otros. Entonces pueden hacer apuestas en consecuencia. Perderán un poco, pero ganarán mucho más de lo que pierden y te sacarán del negocio rápidamente.

No es que se necesite otra respuesta, pero me pareció que valía la pena intentar averiguar exactamente por qué Fisher-Yates es uniforme.

Si estamos hablando de un mazo con N elementos, entonces esta pregunta es: ¿cómo podemos mostrar eso?

Pr(Item i ends up in slot j) = 1/N?

Al descomponerlo con probabilidades condicionales, Pr(item i ends up at slot j) es igual a

Pr(item i ends up at slot j | item i was not chosen in the first j-1 draws) * Pr(item i was not chosen in the first j-1 draws).

y desde allí se expande recursivamente al primer sorteo.

Ahora, la probabilidad de que el elemento i no haya sido dibujado en el primer sorteo es N-1 / N Y la probabilidad de que no se dibujó en el segundo sorteo condicional al hecho de que no se dibujó en el primer sorteo es N-2 / N-1 y así sucesivamente.

Entonces, obtenemos la probabilidad de que el elemento i no haya sido dibujado en los primeros sorteos j-1 :

(N-1 / N) * (N-2 / N-1) * ... * (N-j / N-j+1)

y, por supuesto, sabemos que la probabilidad de que se dibuje en la ronda j condicional a no haber sido dibujado anteriormente es de 1 / Nj .

Observe que en el primer término, todos los numeradores cancelan los denominadores posteriores (es decir, N-1 cancela, N-2 cancela, hasta N-j+1 cancela, dejando solo Nj / N ).

Entonces, la probabilidad general de que el elemento i aparezca en la ranura j es:

[(N-1 / N) * (N-2 / N-1) * ... * (N-j / N-j+1)] * (1 / N-j) = 1/N

como se esperaba.

Para obtener más información general sobre la "barajada simple", la propiedad particular de la que carece se denomina exchangeability . Debido a la "dependencia de ruta" de la forma en que se crea la orden aleatoria (es decir, a cuál de las 27 rutas se sigue para crear la salida), no puede tratar las diferentes variables aleatorias en cuanto a componentes como si pudieran aparecer en cualquier orden . De hecho, este es quizás el ejemplo motivador de por qué la intercambiabilidad es importante en el muestreo aleatorio.

Por sus comentarios sobre las otras respuestas, parece que está buscando no solo una explicación de por qué la distribución no es la distribución uniforme (para la cual la respuesta de divisibilidad es simple) sino también una explicación "intuitiva" de por qué es en realidad lejos de ser uniforme .

Aquí hay una forma de verlo. Supongamos que comienza con la matriz inicial [1, 2, ..., n] (donde n puede ser 3, o 52, o lo que sea) y aplica uno de los dos algoritmos. Si todas las permutaciones son uniformemente probables, entonces la probabilidad de que 1 permanezca en la primera posición debería ser 1/n . Y de hecho, en el segundo algoritmo (correcto), es 1/n , ya que 1 permanece en su lugar si y solo si no se intercambia la primera vez, es decir, si la llamada inicial a rand(0,n-1) devuelve 0.
Sin embargo, en el primer algoritmo (incorrecto), 1 permanece intacto solo si no se intercambia la primera vez ni en ningún otro momento, es decir, solo si el primer rand devuelve 0 y ninguno de los otros rand s devuelve 0, la probabilidad de que es (1 / n) * (1-1 / n) ^ (n-1) ≈ 1 / (ne) ≈ 0.37 / n, no 1 / n.

Y esa es la explicación "intuitiva": en su primer algoritmo, es más probable que los elementos anteriores se intercambien fuera de lugar que los elementos posteriores, por lo que las permutaciones que obtiene están sesgadas hacia patrones en los que los elementos anteriores no están en sus lugares originales.

(Es un poco más sutil que eso, por ejemplo, se puede cambiar a una posición posterior y aún así terminar cambiando de nuevo en su lugar a través de una serie complicada de intercambios, pero esas probabilidades son relativamente menos significativas).

Un enfoque ilustrativo podría ser este:

1) Considera solo 3 cartas.

2) para que el algoritmo brinde resultados distribuidos uniformemente, la probabilidad de que "1" termine como [0] debe ser 1/3, y la probabilidad de que "2" termine en [1] también debe ser 1/3 , Etcétera.

3) Así que si nos fijamos en el segundo algoritmo:

probabilidad de que "1" termine en un [0]: cuando 0 es el número aleatorio generado, por lo que 1 caso de (0,1,2), por lo tanto, es 1 de 3 = 1/3
probabilidad de que "2" termine en a [1]: cuando no se cambió a [0] la primera vez, y no se cambió a [2] la segunda vez: 2/3 * 1 / 2 = 1/3
probabilidad de que "3" termine en a [2]: cuando no se cambió a [0] la primera vez, y no se cambió a [1] la segunda vez: 2/3 * 1 / 2 = 1/3
todos son perfectamente 1/3, y no vemos ningún error aquí.

4) si intentamos calcular la probabilidad de que "1" termine como [0] en el primer algoritmo, el cálculo será un poco largo, pero como muestra la ilustración en la respuesta de lassevk, es 9/27 = 1 / 3, pero "2" que termina como [1] tiene una probabilidad de 8/27, y "3" que termina como [2] tiene una probabilidad de 9/27 = 1/3.

como resultado, "2" que termina como un [1] no es 1/3 y, por lo tanto, el algoritmo producirá un resultado bastante sesgado (aproximadamente un 3,7% de error, a diferencia de cualquier caso insignificante, como 3/10000000000000 = 0.00000000003%)

5) la prueba que Joel Coehoorn tiene, en realidad puede probar que algunos casos estarán sobre representados. Creo que la explicación de por qué es n ^ n es la siguiente: en cada iteración, hay n posibilidades de que el número aleatorio pueda ser, por lo que después de n iteraciones, puede haber n ^ n casos = 27. Este número no se divide el número de permeaciones (n! = 3! = 6) uniformemente en el caso de n = 3, por lo que algunos resultados están sobre representados. están sobre representadas de una manera que en lugar de aparecer 4 veces, aparece 5 veces, por lo que si barajas las tarjetas millones de veces desde el orden inicial de 1 a 52, el caso sobre representado se mostrará 5 millones veces frente a 4 millones de veces, que es una diferencia bastante grande.

6) creo que se muestra la representación excesiva, pero "¿por qué" ocurrirá la representación excesiva?

7) una prueba definitiva para que el algoritmo sea correcto es que cualquier número tiene una probabilidad de 1 / n para terminar en cualquier posición.

Vea la publicación Coding Horror The Danger of Naïveté .

Básicamente (suponiendo 3 cartas):

La combinación aleatoria da como resultado 33 (27) posibles combinaciones de mazo. Eso es extraño, ¡porque las matemáticas nos dicen que en realidad solo hay 3! o 6 combinaciones posibles de un mazo de 3 cartas. En el orden aleatorio KFY, comenzamos con un pedido inicial, cambiamos de la tercera posición con cualquiera de las tres cartas, luego intercambiamos nuevamente desde la segunda posición con las dos cartas restantes.