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

Question

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

se puede probar ... en lugar de usar 52, utilizar 3 (supongamos que sólo se usan las tarjetas 3), y ejecutarlo 10.000 veces y cuente los resultados, verá que los resultados están sesgados hacia ciertos patrones ...

la pregunta es ... ¿cuál es la 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 al azar, hará que los resultados sesgados?

Actualización 1: gracias a la gente de aquí señalando que necesita ser rand ($ i, 51) para que se mezcle correctamente.

Answer 1

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

Supongamos que comienza 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, el que contempla el intercambio de información, contiene el resultado final, con 27 resultados posibles.

Vamos a contar el número de veces que 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 intercambia de forma aleatoria para un número infinito de veces, los patrones 132, 213 y 231 se producirán con más frecuencia que los patrones 123, 312 y 321, simplemente porque la forma en que el código cambia 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 mirar el largo tendencia de término

Aquí es código C# que explora la aleatoriedad para uno de cada patrón sea 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); 
     } 
    } 
} 

Este salidas:

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

Así, mientras que esta respuesta en el recuento de hecho, no es una respuesta puramente matemática , solo tiene que evaluar todas las formas posibles en que puede funcionar la función aleatoria y observar los resultados finales.

Answer 2

ver esto:
The Danger of Naïveté (Coding Horror)

Veamos su cubierta de tres cartas como ejemplo. El uso de una cubierta 3 de la tarjeta, sólo hay 6 posibles pedidos de la cubierta después de una reproducción aleatoria: 123, 132, 213, 231, 312, 321.

Con su primera algoritmo hay 27 posibles caminos (resultados) para el código, en función 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 de manera uniforme por 6, algunas de las 6 combinaciones deben estar sobrerrepresentadas.

Con el 2º algoritmo, hay 6 resultados posibles que se corresponden exactamente con los 6 posibles resultados de mezcla "real", y todos deben representarse con el tiempo.

Esto es importante porque las cubetas que están sobrerrepresentadas en el primer algoritmo no son aleatorias. Los segmentos seleccionados para el sesgo son repetibles y predecibles. Así que si estás construyendo un juego de póquer en línea y usas el primer algoritmo, un hacker podría descubrir que usaste el tipo ingenuo y de ahí que ciertos arreglos de mazos son mucho más probables 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.

Answer 3

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

Utilizando este código para simular una reproducción aleatoria al azar 3-tarjeta ...

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

... se obtiene esta distribución.

El código shuffle (arriba) da como resultado 3^3 (27) posibles combinaciones de cubierta. ¡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.

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

Answer 4

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

Básicamente (suposing 3 tarjetas):

Los resultados de reproducción aleatoria ingenuas en 33 (27) posibles combinaciones de cubierta. Eso es impar, porque las matemáticas nos dicen que realmente solo hay 3! o 6 combinaciones posibles de una cubierta de 3 tarjetas . En la reproducción aleatoria KFY, comenzamos con un pedido inicial, intercambiamos desde la tercera posición con cualquiera de las tres tarjetas , luego intercambiamos de nuevo desde la segunda posición con las dos tarjetas restantes.

Answer 5

He aquí 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 los vientos de la tarjeta para arriba en la posición A es la probabilidad de que ya estaba allí veces el 2/3 del tiempo de la posición A no está involucrado en el intercambio, más la probabilidad que era en la posición veces C la tercera probabilidad de que C intercambia con a, etc. Ahora restando 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 una de las otras. 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.

Answer 6

De sus comentarios sobre las otras respuestas, parece que usted está buscando no solo una explicación de por qué la distribución no es distribución uniforme (para la cual la respuesta de divisibilidad es simple) sino también "intuitiva" "explicación de por qué es realmente lejos de 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), que es 1/n, como 1 permanece en su lugar si y sólo si no se cambia la primera vez, es decir, si y sólo si la llamada inicial a rand(0,n-1) devuelve 0.
Sin embargo, en la primera (mal) algoritmo, 1 sólo permanece intacta si es ni intercambió primera vez ni cualquier otro momento - es decir, si los primeros rand devuelve 0 y ninguno del otro rand s devuelve 0, el probabilidad de que sea (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, los elementos anteriores son mucho más propensos a ser cambiados de lugar que los artículos posteriores, por lo que las permutaciones que recibe están sesgados hacia modelos en los que los primeros artículos son no en sus lugares originales.

(Es un poco más sutil que, por ejemplo 1 puede swapeada en una posición más tarde y todavía terminan conseguir intercambiado nuevamente en su lugar a través de una complicada serie de permutas, pero esas probabilidades son relativamente menos importantes.)

Answer 7

Aquí hay un gran análisis de un card shuffling Markov chains. Oh, espera, eso es todo matemática. Lo siento.:)

Answer 8

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.

Answer 9

un enfoque ilustrativo podría ser la siguiente:

1) consideran sólo 3 cartas.

2) para que el algoritmo proporcione resultados uniformemente distribuidos, 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, y así sucesivamente.

3) por lo que si nos fijamos en el segundo algoritmo:

probabilidad de que "1" termina en a [0]: cuando 0 se genera el número aleatorio, tan 1 caso de (0,1,2), por lo tanto, es 1 de 3 = 1/3

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

probabilidad de que "3" termina en un [2]: cuando de no haber intercambiado a a [0] el primera vez, y de no haber intercambiado a una [1] la segunda time: 2/3 * 1/2 = 1/3

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

4) si tratamos de calcular la probabilidad de "1" para terminar como [0] en el primer algoritmo, el cálculo será un poco largo, pero a medida que la representación de espectáculos de la respuesta de lassevk, se 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" terminando como un [1] no es 1/3 y por lo tanto el algoritmo producirá un resultado bastante sesgado (aproximadamente 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 definitiva para que el algoritmo sea correcto es que cualquier número tiene una probabilidad de 1/n para terminar en cualquier ranura.

Answer 10

El algoritmo Naive recoge 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) Lassevk responde que muestra la distribución entre las tarjetas de estas combinaciones .

el mejor algoritmo hace:

n = rand (3)

n = rand (2)

n! posibles combinaciones de n

1,1, 1,2, 2,1 2,2 3,1 3,2 (6 combinaciones, todos ellos dando un resultado diferente)

Como se menciona en las otras respuestas , si realiza 27 intentos para obtener 6 resultados, posiblemente no podrá obtener los 6 resultados con distribución equitativa, ya que 27 no es divisible entre 6. Ponga 27 canicas en 6 canastas y no importa lo que haga, algunas canastas tendrán más canicas que otros, lo mejor que puede hacer es 4,4,4,5,5,5 mármoles para cubos del 1 al 6.

el problema fundamental con la mezcla ingenua es que se intercambia demasiadas veces, para mezclar 3 cartas completamente, solo necesita hacer 2 intercambios, y el segundo intercambio solo debe estar entre los las primeras dos cartas, ya que la tercera carta ya tenía una probabilidad de 1/3 de ser canjeada. continuar intercambiando cartas le dará más posibilidades de que una determinada carta se canjee, y estas posibilidades solo igualarán a 1/3, 1/3, 1/3 si el total de combinaciones de swap es divisible por 6.

Answer 11

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 una cubierta con N elementos, entonces esta pregunta es: ¿Cómo podemos mostrar que

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

Descomponiéndola 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 con la condición de que no se haya dibujado en el primer sorteo es N-2/N-1 y así sucesivamente.

Así, obtenemos la probabilidad de que el elemento i no se ha elaborado en el primer j-1 dibuja:

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

y por supuesto sabemos que la probabilidad de que se dibuja en ronda jcondicionada a no tener ha dibujado anteriormente es solo 1/N-j.

en cuenta que en el primer término, los numeradores todos cancelan los denominadores posteriores (es decir N-1 cancela, N-2 cancela, todo el camino a N-j+1 cancela, dejando sólo N-j/N).

lo tanto la probabilidad global de i elemento que aparece 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 "combinación simple", la propiedad particular que le falta se llama exchangeability. 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, esto es quizás el ejemplo motivador de por qué la intercambiabilidad es importante en el muestreo aleatorio.