Pregunta Comprender la "aleatoriedad"


No puedo entender esto, ¿qué es más aleatorio?

rand()

O

rand() * rand()

Lo estoy encontrando un verdadero desafío para la mente, ¿podría ayudarme?

EDITAR:

Intuitivamente, sé que la respuesta matemática será que son igualmente aleatorios, pero no puedo evitar pensar que si "ejecutas el algoritmo de números aleatorios" dos veces al multiplicar los dos, crearás algo más aleatorio que solo hacer una vez


822
2017-10-18 03:40


origen


Respuestas:


Solo una aclaración

Aunque las respuestas anteriores son correctas cada vez que intenta detectar la aleatoriedad de una variable pseudoaleatoria o su multiplicación, debe tener en cuenta que, aunque Aleatorio() usualmente se distribuye uniformemente, Aleatorio () * Aleatorio () no es.

Ejemplo

Esto es un muestra uniforme de distribución aleatoria simulado a través de una variable pseudoaleatoria:

Histogram of Random() 

        BarChart[BinCounts[RandomReal[{0, 1}, 50000], 0.01]]

Si bien esta es la distribución que obtiene después de multiplicar dos variables aleatorias:

Histogram of Random() * Random() 

        BarChart[BinCounts[Table[RandomReal[{0, 1}, 50000] * 
                                 RandomReal[{0, 1}, 50000], {50000}], 0.01]]

Entonces, ambos son "aleatorios", pero su distribución es muy diferente.

Otro ejemplo

Mientras 2 * Aleatorio () está distribuido uniformemente:

Histogram of 2 * Random()

        BarChart[BinCounts[2 * RandomReal[{0, 1}, 50000], 0.01]]

Random () + Random () no lo es!

Histogram of Random() + Random()

        BarChart[BinCounts[Table[RandomReal[{0, 1}, 50000] + 
                                 RandomReal[{0, 1}, 50000], {50000}], 0.01]]

El teorema del límite central

los Teorema del límite central afirma que la suma de Aleatorio() tiende a una distribución normal a medida que los términos aumentan.

Con solo cuatro términos, obtienes:

Histogram of Random() + Random() + Random() + Random()

BarChart[BinCounts[Table[RandomReal[{0, 1}, 50000] + RandomReal[{0, 1}, 50000] +
                   Table[RandomReal[{0, 1}, 50000] + RandomReal[{0, 1}, 50000],
                   {50000}],
         0.01]]  

Y aquí puede ver el camino desde un uniforme hasta una distribución normal sumando 1, 2, 4, 6, 10 y 20 variables aleatorias uniformemente distribuidas:

Histogram of different numbers of random variables added

Editar

Algunos créditos

Gracias a Thomas Ahle para señalar en los comentarios que las distribuciones de probabilidad que se muestran en las dos últimas imágenes se conocen como Distribución de Irwin-Hall 

Gracias a Heike para ella maravillosa función rasgada []


1464
2017-10-18 04:03



Supongo que ambos métodos son tan aleatorios aunque mi palabrería diría que rand() * rand() es menos aleatorio porque sembraría más ceros. Tan pronto como uno rand() es 0, el total se convierte 0 


151
2017-10-18 03:45



Tampoco es "más aleatorio".

rand() genera un conjunto predecible de números basado en una semilla psuedo aleatoria (generalmente basada en la hora actual, que siempre está cambiando). Multiplicar dos números consecutivos en la secuencia genera una secuencia de números diferente, pero igualmente predecible.

Al abordar si esto reducirá las colisiones, la respuesta es no. Aumentará las colisiones debido al efecto de multiplicar dos números donde 0 < n < 1. El resultado será una fracción más pequeña, causando un sesgo en el resultado hacia el extremo inferior del espectro.

Algunas explicaciones adicionales. En lo que sigue, "impredecible" y "aleatorio" se refieren a la capacidad de alguien para adivinar cuál será el siguiente número basado en números anteriores, es decir. un oráculo

Dado semilla x que genera la siguiente lista de valores:

0.3, 0.6, 0.2, 0.4, 0.8, 0.1, 0.7, 0.3, ...

rand() generará la lista anterior, y rand() * rand() Generará:

0.18, 0.08, 0.08, 0.21, ...

Ambos métodos siempre producirán la misma lista de números para la misma semilla, y por lo tanto son igualmente predecibles por un oráculo. Pero si miras los resultados para multiplicar las dos llamadas, verás que están todas bajo 0.3a pesar de una distribución decente en la secuencia original. Los números son parciales debido al efecto de multiplicar dos fracciones. El número resultante siempre es más pequeño, por lo tanto, es mucho más probable que sea una colisión a pesar de ser igual de impredecible.


81
2017-10-20 22:43



Simplificación excesiva para ilustrar un punto. 

Asuma que su función aleatoria solo produce 0 o 1.

random() es uno de (0,1), pero random()*random() es uno de (0,0,0,1) 

Puedes ver claramente que las posibilidades de obtener un 0 en el segundo caso no son en absoluto iguales a aquellos para obtener un 1.


La primera vez que publiqué esta respuesta quise mantenerla lo más corta posible para que la persona que la leyera entendiera de un vistazo la diferencia entre random() y random()*random(), pero no puedo evitar contestar la pregunta original de ad litteram:

¿Cuál es más aleatorio?


78
2017-10-18 15:31



Aquí hay una respuesta simple. Considera Monopoly. Lanzas dos dados de seis caras (o 2d6 para aquellos de ustedes que prefieren la notación de juego) y toman su suma. El resultado más común es 7 porque hay 6 formas posibles en las que puedes sacar un 7 (1,6 2,5 3,4 4,3 5,2 y 6,1). Mientras que un 2 solo se puede rodar en 1,1. Es fácil ver que rodar 2d6 es diferente a rodar 1d12, incluso si el rango es el mismo (ignorando que puedes obtener un 1 en 1d12, el punto sigue siendo el mismo). Multiplicar los resultados en lugar de agregarlos los sesgará de manera similar, y la mayoría de los resultados aparecerán en el medio del rango. Si intenta reducir los valores atípicos, este es un buen método, pero no ayudará a hacer una distribución pareja.

(Y por extraño que parezca, también aumentará las tiradas bajas. Suponiendo que tu aleatoriedad comience en 0, verás un pico en 0 porque convertirá lo que la otra tirada en 0. Considera dos números aleatorios entre 0 y 1 (inclusive) ) y multiplicando. Si cualquiera de los resultados es un 0, todo se convierte en un 0 sin importar el otro resultado. La única forma de obtener un 1 es que ambos roles sean un 1. En la práctica, esto probablemente no importaría pero lo convierte en un gráfico extraño).


67
2017-10-18 20:25



El obligatorio xkcd ...
return 4; // chosen by fair dice roll, guaranteed to be random.


51
2017-10-18 04:03



Puede ayudar pensar en esto en números más discretos. Considere querer generar números aleatorios entre 1 y 36, por lo que decide que la forma más fácil es tirar dos dados de 6 caras. Obtienes esto:

     1    2    3    4    5    6
  -----------------------------
1|   1    2    3    4    5    6
2|   2    4    6    8   10   12
3|   3    6    9   12   15   18
4|   4    8   12   16   20   24   
5|   5   10   15   20   25   30
6|   6   12   18   24   30   36

Entonces tenemos 36 números, pero no todos están representados de manera justa, y algunos no aparecen en absoluto. Los números cerca de la diagonal central (esquina inferior izquierda a esquina superior derecha) ocurrirán con la frecuencia más alta.

Los mismos principios que describen la distribución injusta entre los dados se aplican igualmente a los números de punto flotante entre 0.0 y 1.0.


34
2017-10-18 03:45



Algunas cosas sobre "aleatoriedad" son contraintuitivas.

Suponiendo una distribución plana de rand(), el siguiente obtendrá distribuciones no planas:

  • alto sesgo: sqrt(rand(range^2))
  • parcialidad en el medio: (rand(range) + rand(range))/2
  • bajo: parcialidad: range - sqrt(rand(range^2))

Hay muchas otras maneras de crear curvas de sesgo específicas. Hice una prueba rápida de rand() * rand()y te da una distribución muy no lineal.


26
2017-10-18 04:10



"aleatorio" vs. "más aleatorio" es un poco como preguntar qué Zero es más cero.

En este caso, rand es un PRNG, por lo que no es totalmente aleatorio. (de hecho, bastante predecible si se conoce la semilla). Multiplicarlo por otro valor lo hace no más o menos aleatorio.

Un verdadero RNG criptográfico será aleatorio. Y ejecutar valores a través de cualquier tipo de función no puede agregarle más entropía, y es muy probable que elimine la entropía, haciendo que no sea más aleatoria.


23
2017-10-18 19:01



La mayoría de las implementaciones de rand () tienen algún período. Es decir. después de una enorme cantidad de llamadas, la secuencia se repite. La secuencia de resultados de rand() * rand() se repite en la mitad del tiempo, por lo que es "menos aleatorio" en ese sentido.

Además, sin una construcción cuidadosa, la realización de la aritmética en valores aleatorios tiende a causar menos aleatoriedad. Un cartel arriba citado "rand() + rand() + rand() ... "(k veces, por ejemplo) que de hecho tenderá a k multiplicado por el valor medio del rango de valores rand() devoluciones. (Es una caminata aleatoria con pasos simétricos sobre eso).

Supongamos que su función rand () devuelve un número real aleatorio distribuido uniformemente en el rango [0,1). (Sí, este ejemplo permite una precisión infinita. Esto no cambiará el resultado). No seleccionó un idioma en particular y diferentes idiomas pueden hacer cosas diferentes, pero el siguiente análisis se mantiene con modificaciones para cualquier implementación no perversa de rand ( ) El producto rand() * rand() también está en el rango [0,1) pero ya no está uniformemente distribuido. De hecho, es probable que el producto esté en el intervalo [0,1 / 4) como en el intervalo [1 / 4,1). Más multiplicaciones sesgarán el resultado aún más hacia cero. Esto hace que el resultado sea más predecible. A grandes rasgos, más predecible == menos aleatorio.

Prácticamente cualquier secuencia de operaciones con entradas uniformemente aleatorias será no uniformemente aleatoria, lo que conducirá a una mayor previsibilidad. Con cuidado, uno puede superar esta propiedad, pero habría sido más fácil generar un número aleatorio distribuido uniformemente en el rango que realmente quería en lugar de perder el tiempo con la aritmética.


23
2017-10-19 12:02



El concepto que estás buscando es "entropía", el "grado" de desorden de una cuerda de bits. La idea es más fácil de entender en términos del concepto de "máxima entropía".

Una definición aproximada de una cadena de bits con máxima entropía es que no se puede expresar exactamente en términos de una cadena de bits más corta (es decir, usando algún algoritmo para expanda la cadena más pequeña de regreso a la cadena original).

La relevancia de la máxima entropía para la aleatoriedad proviene del hecho de que si eliges un número "al azar", es casi seguro que elijas un número cuya cadena de bits está cerca de tener máxima entropía, es decir, no se puede comprimir. Esta es nuestra mejor comprensión de lo que caracteriza a un número "aleatorio".

Por lo tanto, si desea hacer un número aleatorio de dos muestras aleatorias que es "dos veces" como al azar, tu concatenar las dos cadenas de bits juntas. Prácticamente, solo hubieras rellena las muestras en las mitades alta y baja de una palabra de doble longitud.

En una nota más práctica, si te sientes cargado con un rand rappy (), puede a veces ayuda a xor un par de muestras juntas --- aunque, si está realmente roto, incluso ese procedimiento no ayudará.


19
2017-10-18 21:25