c# - studio - Número aleatorio en rango con la misma probabilidad

randomize visual basic

Question

Esto podría estar más relacionado con las matemáticas que C #, pero necesito una solución de C #, así que lo estoy poniendo aquí.

Mi pregunta es acerca de la probabilidad de generadores de números aleatorios, más específicamente si cada valor posible se devuelve con la misma probabilidad.

Sé que existe el método Random.Next (int, int) que devuelve un número entre el primer entero y el último (el último es exclusivo).

Random.Next() [sin sobrecargas] devolverá un valor entre 0 e Int32.MaxValue (que es 2147483647) - 1, entonces 2147483646.

Si quiero un valor entre 1 y 10, podría llamar a Random.Next(1, 11) para hacer esto, sin embargo, ¿todos los valores entre 1 y 10 tienen la misma probabilidad de ocurrir?

Por ejemplo, el rango es 10, por lo que 2147483646 no es perfectamente divisible por 10, por lo que los valores 1-6 tienen una probabilidad ligeramente mayor de ocurrir (porque 2147483646 % 10 = 6 ). Por supuesto, esto supone que cada valor dentro de Random.Next() [sin sobrecargas] devuelve un valor entre 0 y 2147483646 con la misma probabilidad.

¿Cómo se puede asegurar que cada número dentro de un rango tenga la misma probabilidad de ocurrir? Digamos que para un sistema de tipo de lotería donde sería injusto para algunas personas tener una mayor capacidad de acción que otras, no estoy diciendo que usaría el RNG integrado de C # para esto, solo lo estaba usando como ejemplo.

Answer 1

El C # construido en RNG es, como se espera, distribuido uniformemente. Cada número tiene la misma probabilidad de ocurrir dado el rango que especifique para Next(min, max) .

Puedes probarlo tú mismo (tengo) tomando, digamos, muestras de 1M y almacenando cuántas veces aparece cada número. Obtendrá una curva de línea casi plana si lo grafica.

También tenga en cuenta que, cada número que tiene la misma probabilidad no significa que cada número se producirá la misma cantidad de veces. Si observa números aleatorios del 1 al 10, en 100 iteraciones, no será una distribución uniforme de 10 veces para cada número. Algunos números pueden ocurrir 8 veces y otros 12 o 13 veces. Sin embargo, con más iteraciones, esto tiende a emparejarse un poco.

Además, como se menciona en los comentarios, agregaré: si quieres algo más fuerte, busca PRNG criptográficos. Mersenne Twister es particularmente bueno por lo que he visto (rápido, barato de calcular, gran período) y tiene implementaciones de código abierto en C #.

Answer 2

Las cenizas y el dtb son incorrectos: tienes razón al sospechar que algunos números tendrían una mayor probabilidad de ocurrir que otros.

Cuando llama .Next(x, y) , hay y - x posibles valores de retorno. La clase Random .NET 4.0 calcula un valor de retorno basado en el valor de retorno de NextDouble() (esta es una descripción ligeramente simplificada).

Obviamente, el conjunto de posibles valores dobles es finito y, como puede ver, puede no ser un múltiplo del tamaño del conjunto de posibles valores de retorno de .Next(x, y) . Por lo tanto, suponiendo que el conjunto de valores de entrada se distribuye uniformemente, algunos valores de salida tendrán una probabilidad ligeramente mayor de ocurrir.

No sé a simple vista cuántos valores dobles numéricos hay (es decir, excluyendo los valores de infinito y NaN), pero ciertamente es mayor que 2 ^ 32. En su caso, si asumimos valores de 2 ^ 32, por el bien del argumento, entonces tenemos que mapear 4294967296 entradas a 10 salidas. Algunos valores tendrían una probabilidad mayor de 429496730/429496729 o 0.00000023283064397913028110629 por ciento mayor. De hecho, dado que el número de estados de entrada es mayor que 2 ^ 32, la diferencia en probabilidad sería aún menor.

Answer 3

Noto que nadie realmente respondió la pregunta carnosa en su publicación:

Por ejemplo, el rango es 10, por lo que 2147483646 no es perfectamente divisible por 10, por lo que los valores 1-6 tienen una probabilidad ligeramente mayor de ocurrir (porque 2147483646% 10 = 6). Por supuesto, esto supone que cada valor dentro de Random.Next () [sin sobrecargas] devuelve un valor entre 0 y 2147483646 con la misma probabilidad.

¿Cómo se puede asegurar que cada número dentro de un rango tenga la misma probabilidad de ocurrir?

Correcto, entonces solo descartas los valores que causan el desequilibrio. Por ejemplo, digamos que tiene un RNG que podría producir una distribución uniforme en { 0, 1, 2, 3, 4 } y que quería usarlo para producir una distribución uniforme sobre { 0, 1 } . La implementación ingenua es: dibujar desde {0, 1, 2, 3, 4} y luego devolver el valor % 2 ; esto, sin embargo, obviamente produciría una muestra sesgada. Esto sucede porque, como nota, 5 (el número de elementos) no es divisible de manera pareja por 2. Entonces, en su lugar, arroje cualquier dibujo que produzca el valor 4 . Por lo tanto, el algoritmo sería

 draw from { 0, 1, 2, 3, 4 }
if the value is 4, throw it out
otherwise, return the value % 2

Puede usar esta idea básica para resolver el problema general.

sin embargo, ¿tiene la misma probabilidad de ocurrir cada valor entre 1 y 10?

Sí, lo hace. Desde MSDN :

Los números pseudoaleatorios se eligen con la misma probabilidad a partir de un conjunto finito de números .

Editar: Aparentemente la documentación NO es consistente con la implementación actual en .NET. La documentación indica que los sorteos son uniformes, pero el código sugiere que no lo es. Sin embargo, eso NO niega el hecho de que este es un problema soluble, y mi enfoque es una forma de resolverlo.

Answer 4

Programa de prueba:

var a = new int[10];
var r = new Random();
for (int i = 0; i < 1000000; i++) a[r.Next(1, 11) - 1]++;
for (int i = 0; i < a.Length; i++) Console.WriteLine("{0,2}{1,10}", i + 1, a[i]);

Salida:

1 99924 2 100199 3 100568 4 100406 5 100114 6 99418 7 99759 8 99573 9 100121 10 99918

Conclusión:

Cada valor se devuelve con la misma probabilidad.