¿Por qué este algoritmo aleatorio simple produce resultados sesgados? ¿Cuál es una razón simple?

parece que este algoritmo aleatorio simple 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; } 

puedes intentarlo … en lugar de usar 52, usar 3 (supongamos que solo se usan 3 tarjetas), ejecutarlo 10.000 veces y contar los resultados, verás que los resultados están sesgados hacia ciertos patrones …

la pregunta es … ¿cuál 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, al parecer también totalmente aleatorio, sesgará los resultados?

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

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

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

 123 +- 123 - swap 1 and 1 (these are positions, | +- 213 - swap 2 and 1 not numbers) | | +- 312 - swap 3 and 1 | | +- 231 - swap 3 and 2 | | +- 213 - swap 3 and 3 | +- 123 - swap 2 and 2 | | +- 321 - swap 3 and 1 | | +- 132 - swap 3 and 2 | | +- 123 - swap 3 and 3 | +- 132 - swap 2 and 3 | +- 231 - swap 3 and 1 | +- 123 - swap 3 and 2 | +- 132 - swap 3 and 3 +- 213 - swap 1 and 2 | +- 123 - swap 2 and 1 | | +- 321 - swap 3 and 1 | | +- 132 - swap 3 and 2 | | +- 123 - swap 3 and 3 | +- 213 - swap 2 and 2 | | +- 312 - swap 3 and 1 | | +- 231 - swap 3 and 2 | | +- 213 - swap 3 and 3 | +- 231 - swap 2 and 3 | +- 132 - swap 3 and 1 | +- 213 - swap 3 and 2 | +- 231 - swap 3 and 3 +- 321 - swap 1 and 3 +- 231 - swap 2 and 1 | +- 132 - swap 3 and 1 | +- 213 - swap 3 and 2 | +- 231 - swap 3 and 3 +- 321 - swap 2 and 2 | +- 123 - swap 3 and 1 | +- 312 - swap 3 and 2 | +- 321 - swap 3 and 3 +- 312 - swap 2 and 3 +- 213 - swap 3 and 1 +- 321 - swap 3 and 2 +- 312 - swap 3 and 3 

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 al azar durante un número infinito de veces, los patrones 132, 213 y 231 ocurrirán con más frecuencia que los patrones 123, 312 y 321, simplemente porque la forma en que el cambio de código hace que sea más probable que ocurra .

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

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

 class Program { static void Main(string[] args) { Dictionary occurances = new Dictionary { { "123", 0 }, { "132", 0 }, { "213", 0 }, { "231", 0 }, { "312", 0 }, { "321", 0 } }; Char[] digits = new[] { '1', '2', '3' }; Func 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 cuenta de hecho, no es una respuesta puramente matemática, solo tienes que evaluar todas las formas posibles en que puede funcionar la función aleatoria, y observar los resultados finales.

Mira esto:
El peligro de la ingenuidad (Coding Horror)

Veamos tu mazo de tres cartas como un ejemplo. Usando un mazo de 3 cartas, solo hay 6 órdenes posibles para el mazo después de un barajado: 123, 132, 213, 231, 312, 321.

Con su primer algoritmo, hay 27 posibles caminos (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 correlacionará con el mismo resultado individual de la lista de 6 posibles resultados aleatorios “reales” anteriores. Ahora tenemos 27 elementos y 6 cubos para colocarlos. Como 27 no es divisible por 6, algunas de esas 6 combinaciones deben estar sobrerrepresentadas.

Con el segundo algoritmo, hay 6 resultados posibles que se corresponden exactamente con los 6 posibles resultados de mezcla “real”, y todos deben representarse de forma equitativa a lo largo del tiempo.

Esto es importante porque los segmentos que están sobrerrepresentados en el primer algoritmo no son aleatorios. Los segmentos seleccionados para el sesgo son repetibles y predecibles. Entonces, si estás construyendo un juego de póquer en línea y usas el primer algoritmo, un hacker podría deducir que usaste el tipo ingenuo y, a partir de eso, es más probable que ocurran ciertos arreglos de mazos que otros. Entonces pueden colocar apuestas en consecuencia. Perderán un poco, pero ganarán mucho más de lo que pierden y te sacarán rápidamente del negocio.

De sus comentarios sobre las otras respuestas, parece que usted busca no solo una explicación de por qué la distribución no es la distribución uniforme (para lo 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 podría 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 debe 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) regresa 0.
Sin embargo, en el primer algoritmo (erróneo), 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 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 mucho más probable que los elementos anteriores se intercambien fuera de lugar que los posteriores, por lo que las permutaciones que obtiene están sesgadas hacia patrones en los que los primeros artículos no están en sus lugares originales.

(Es un poco más sutil que eso, por ejemplo, 1 puede cambiarse a una posición posterior y aún así volver a ser reemplazado por una complicada serie de swaps, pero esas probabilidades son relativamente menos significativas).

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

Usando este código para simular un aleatorio aleatorio 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.

Distribución de barajar 3 cartas

El código de mezcla (arriba) da como resultado 3 ^ 3 (27) combinaciones de mazos posibles. ¡Pero las matemáticas nos dicen que realmente solo hay 3! o 6 combinaciones posibles de un mazo de 3 cartas. Entonces, algunas de las combinaciones están sobrerrepresentadas.

Debería usar una combinación aleatoria de Fisher-Yates para mezclar (aleatoriamente) una baraja de cartas.

Aquí hay otra intuición: el intercambio de desplazamiento ú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 sea la probabilidad de que la tarjeta 2 esté en la posición B, y c la probabilidad de que esté en la posición C, previa a un movimiento de intercambio. Supongamos que no hay dos probabilidades iguales: a! = B, b! = C, c! = A. Ahora calcule las probabilidades a ‘, b’ y c ‘de la tarjeta en estas tres posiciones después de un intercambio. Digamos que este movimiento de intercambio consiste en que la posición C se intercambie 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 carta termine en la posición A es la probabilidad de que ya haya estado allí, los 2/3 de la posición de tiempo A no esté involucrada en el intercambio, más la probabilidad de que esté en la posición C por 1 / 3 probabilidad de que C se canjee 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 aproximará a 0 a lo largo del tiempo, dado un intercambio suficiente). Pero como a ‘+ b’ + c ‘= 1, si a’! = B ‘, tampoco puede ser igual a c’, que es 1/3. Entonces, si las tres probabilidades comienzan todas diferentes antes de un intercambio, también serán diferentes después de un intercambio. Y esto se mantendría independientemente de la posición que se intercambiara; simplemente intercambiaremos los roles de las variables en lo anterior.

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

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

Básicamente (suponiendo 3 cartas):

La combinación ingenua da como resultado 33 (27) posibles combinaciones de mazos. ¡Es extraño, porque las matemáticas nos dicen que realmente solo hay 3! o 6 combinaciones posibles de un mazo de 3 cartas. En KFY Shuffle, comenzamos con un orden inicial, intercambiamos desde la tercera posición con cualquiera de las tres cartas, luego intercambiamos nuevamente desde la segunda posición con las otras dos cartas.

La respuesta simple es que hay 52 ^ 52 formas posibles de ejecutar este algoritmo, ¡pero solo hay 52! posibles arreglos de 52 cartas. Para que el algoritmo sea justo, necesita producir cada uno de estos arreglos 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.

un enfoque ilustrativo podría ser este:

1) considera solo 3 cartas.

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

3) entonces si miramos el segundo algoritmo:

probabilidad de que “1” termine en a [0]: cuando 0 es el número aleatorio generado, por lo que 1 caso fuera de (0,1,2), por lo tanto, es 1 de 3 = 1/3

probabilidad de que “2” termine en un [1]: cuando no se cambió a un [0] la primera vez, y no se cambió a un [2] la segunda vez: 2/3 * 1 / 2 = 1/3

probabilidad de que “3” termine en un [2]: cuando no se cambió a un [0] la primera vez, y no se cambió a un [1] la segunda vez: 2/3 * 1 / 2 = 1/3

todos son perfectamente 1/3, y no vemos ningún error aquí.

4) si tratamos de calcular la probabilidad de que “1” termine como un [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” terminando como un [1] tiene una probabilidad de 8/27, y “3” terminando como un [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 de que Joel Coehoorn tiene, en realidad puede demostrar que algunos casos estarán sobrerrepresentados. Creo que la explicación de por qué es n ^ n es esta: en cada iteración, hay n posibilidad de que el número aleatorio pueda ser, así que después de n iteraciones, puede haber n ^ n casos = 27. Este número no se divide el número de permuations (n! = 3! = 6) uniformemente en el caso de n = 3, por lo que algunos resultados están sobrerrepresentados. están sobrerrepresentados de una manera que en lugar de mostrarse 4 veces, aparece 5 veces, por lo que si barajas las cartas millones de veces desde el orden inicial de 1 a 52, el caso sobrerrepresentado aparecerá 5 millones veces en comparación con 4 millones de veces, lo cual es una gran diferencia.

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

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

Aquí hay un gran análisis de una tarjeta barajando las cadenas de Markov . Oh, espera, eso es todo matemática. Lo siento. 🙂

El algoritmo Naive escoge los valores de n así:

n = rand (3)

n = rand (3)

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 cartas de estas combinaciones.

el mejor algoritmo lo 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 ellas dando un resultado diferente)

Como se menciona en las otras respuestas, si lleva 27 bashs para obtener 6 resultados, posiblemente no pueda obtener los 6 resultados con distribución equitativa, ya que 27 no es divisible por 6. Ponga 27 canicas en 6 baldes y no importa lo que haga, algunas los baldes tendrán más canicas que otros, lo mejor que puede hacer es 4,4,4,5,5,5 canicas para los cangilones 1 a 6.

el problema fundamental con la confusión ingenua es que intercambia demasiadas veces, para barajar 3 cartas por completo, solo necesita hacer 2 intercambios, y el segundo intercambio solo necesita estar entre las primeras dos cartas, ya que la tercera carta ya tenía un 1/3 posibilidad de ser intercambiado. continuar intercambiando cartas le dará más posibilidades de que una determinada carta se canjee, y estas posibilidades solo saldrán a 1/3, 1/3, 1/3 si el total de combinaciones de swap es divisible por 6.

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 demostrar que

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

Rompiéndolo 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 hasta el primer sorteo.

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

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

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

y, por supuesto, sabemos que la probabilidad de que se dibuje en la ronda j condición de no haberse dibujado antes es solo 1 / Nj .

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

Entonces la probabilidad total de que el elemento i aparezca en el slot j es:

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

como se esperaba.

Para obtener más general acerca de la “simple mezcla”, la propiedad particular que le falta se llama intercambiabilidad . Debido a la “dependencia de la ruta” de la forma en que se crea la mezcla (es decir, cuál de las 27 rutas se sigue para crear la salida), no es posible tratar las diferentes variables aleatorias de 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.

La respuesta más clara para mostrar que el primer algoritmo falla es ver el algoritmo en cuestión como una cadena de n pasos de Markov en el gráfico 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 proporciona la probabilidad de transición de 1/n para cada salto. Hay n ^ n caminos la probabilidad de cada uno de los cuales es 1/n^n . ¡Supongamos que la probabilidad final de aterrizaje en cada vértice es 1/n! que es una fracción reducida. Para lograr eso, debe haber m rutas con el mismo vértice final tal que m/n^n=1/n! o n^n = mn! para un 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.