Al azar es casi al azar en absoluto?
https://stackoverflow.com/questions/2145510
-
23-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Me hizo esto para probar la aleatoriedad de randint:
>>> from random import randint
>>>
>>> uniques = []
>>> for i in range(4500): # You can see I was optimistic.
... x = randint(500, 5000)
... if x in uniques:
... raise Exception('We duped %d at iteration number %d' % (x, i))
... uniques.append(x)
...
Traceback (most recent call last):
File "<stdin>", line 4, in <module>
Exception: We duped 887 at iteration number 7
Me trató sobre 10 veces más y el mejor resultado que obtuve fue de 121 iteraciones antes de un repetidor. Es este el mejor tipo de resultado que puede obtener de la biblioteca estándar?
Solución
La paradoja del cumpleaños, o por qué PRNG producen duplicados con más frecuencia de lo que parece.
Hay un par de cuestiones en juego en el problema de la OP. Una de ellas es la cumpleaños paradoja como se mencionó anteriormente, y la segunda es la naturaleza de lo que se está generando, que no inherentemente garantiza que un número dado no se repetirá.
La paradoja del cumpleaños se aplica cuando valor dado puede ocurrir más de una vez durante el período del generador - y por lo tanto duplicados puede ocurrir dentro de una muestra de valores. El efecto de la paradoja del cumpleaños es que la probabilidad real de conseguir esas copias es muy importante y el período promedio entre ellos es menor de lo que cabría haber pensado lo contrario. Esta disonancia entre las probabilidades percibidas y reales hace que la paradoja del cumpleaños es un buen ejemplo de un sesgo cognitivo , donde una estimación intuitiva ingenua es probable que sea tremendamente mal.
Una cartilla rápida en los generadores de números aleatorios (Pseudo PRNG)
La primera parte de su problema es que usted está tomando el valor expuesto de un generador de números aleatorios y convertirlo en un número mucho menor, por lo que se reduce el espacio de posibles valores. Aunque algunos pseudo-aleatorio generadores de números hacen valores no repetidos durante el período de esta transformación cambia el dominio de uno mucho más pequeño. El dominio más pequeño invalida la condición de '' no se repite lo que puede esperar de una alta probabilidad de repeticiones.
Algunos algoritmos, como la lineal congruente PRNG (A'=AX|M) hacer singularidad garantía para todo el período. En una LCG el valor generado contiene todo el estado del acumulador y se lleva a cabo ningún estado adicional. El generador es determinista y no puede repetir un número dentro del período - cualquier valor del acumulador dado puede implicar sólo una posible valor sucesivo. Por lo tanto, cada valor sólo puede ocurrir una vez dentro del período del generador. Sin embargo, el período de un PRNG tal es relativamente pequeña - alrededor de 2 ^ 30 para implementaciones típicas del algoritmo LCG -. Y no puede ser mayor que el número de valores distintos
No todos los algoritmos PRNG comparten esta característica; algunos pueden repetir un valor dado dentro del período. En el problema de la OP, el Mersenne Twister algoritmo (utilizado en módulo aleatorio) tiene un período muy largo - mucho mayor que 2 ^ 32. A diferencia de un Linear congruential PRNG, el resultado no es puramente una función del valor de salida anterior como el acumulador contiene el estado adicional. Con salida de número entero de 32 bits y un periodo de ~ 2 ^ 19 937, no puede posiblemente proporcionar un tal garantía.
El Mersenne Twister es un algoritmo popular para PRNGs porque tiene buenas propiedades estadísticas y geométricas y un período muy largo - características deseables para un PRNG utilizado en modelos de simulación.
-
propiedades estadísticas hacían que los números generados por el algoritmo se distribuyen de manera uniforme con ningún número que tiene una probabilidad significativamente mayor de aparecer que otros. propiedades estadísticas pobres podrían producir skew no deseado en los resultados.
-
geométrica Properies significa que conjuntos deN números no se encuentran sobre un hiperplano en el espacio N-dimensional. propiedades geométricas pobres pueden generar correlaciones espurias en un modelo de simulación y distorsionar los resultados.
-
Un largo periodo de medios que puede generar una gran cantidad de números antes de la secuencia se envuelve alrededor de la salida. Si un modelo necesita un gran número de iteraciones o tiene que ser ejecutado desde varias semillas entonces los números discretos 2 ^ 30 o así disponibles a partir de una implementación típica LCG pueden no ser suficientes. El algoritmo MT19337 tiene un período muy largo - 2 ^ 19337-1, o aproximadamente 10 ^ 5821. En comparación, el número total de átomos en el universo se estima en aproximadamente 10 ^ 80.
El entero de 32 bits producida por un MT19337 PRNG no puede representar posiblemente suficientes valores discretos para evitar repetir durante un período tan grande. En este caso, los valores duplicados es probable que ocurran e inevitable con una muestra lo suficientemente grande.
La paradoja del cumpleaños en pocas palabras
Este problema se definió originalmente como la probabilidad de que cualquiera de las dos personas en la habitación que comparten el mismo cumpleaños. El punto clave es que cualquiera de los dos personas en la habitación podría compartir un cumpleaños. La gente tiende a malinterpretar ingenuamente el problema, ya que la probabilidad de que alguien en la habitación que comparten un cumpleaños con una persona específica, que es la fuente de la cognitiva sesgo que a menudo hace que la gente subestima la probabilidad. Esta es la suposición incorrecta - no hay ningún requisito para el partido sea a un individuo específico y dos individuos cualquiera podía igualar.
La probabilidad de un partido que se produce entre dos individuos es mucho mayor que la probabilidad de una coincidencia para un determinado individuo como el partido no tiene que ser a una fecha específica. Más bien, es suficiente para encontrar dos personas que comparten el mismo cumpleaños. A partir de este gráfico (que se puede encontrar en la página de Wikipedia sobre el tema), podemos ver que sólo necesitamos 23 personas en la sala para que haya una probabilidad del 50% de encontrar dos que partido de esta manera.
A partir de la entrada de Wikipedia sobre el tema podemos conseguir un buen resumen En el problema de la OP, tenemos 4.500 posibles 'cumpleaños', en lugar de 365. Para un número dado de valores aleatorios generados (lo que equivale a 'gente') queremos saber la probabilidad de ningún dos valores idénticos que aparecen dentro de la secuencia.
Cómo calcular el efecto probable de la paradoja del cumpleaños en el problema de la OP
Para una secuencia de 100 números, tenemos 
pares (ver Entendiendo el problema ) que potencialmente podrían coincidir con (es decir, la primera podría coincidir con el segundo, tercero, etc., el segundo podría coincidir con la tercera, cuarta, etc., y así sucesivamente), por lo que el número de combinaciones que potencialmente podría partido es bastante más que 100.
Desde cálculo de la probabilidad obtenemos una expresión de 
. El siguiente fragmento de código Python a continuación hace una evaluación ingenua de la probabilidad de que se produzca un par coincidente.
# === birthday.py ===========================================
#
from math import log10, factorial
PV=4500 # Number of possible values
SS=100 # Sample size
# These intermediate results are exceedingly large numbers;
# Python automatically starts using bignums behind the scenes.
#
numerator = factorial (PV)
denominator = (PV ** SS) * factorial (PV - SS)
# Now we need to get from bignums to floats without intermediate
# values too large to cast into a double. Taking the logs and
# subtracting them is equivalent to division.
#
log_prob_no_pair = log10 (numerator) - log10 (denominator)
# We've just calculated the log of the probability that *NO*
# two matching pairs occur in the sample. The probability
# of at least one collision is 1.0 - the probability that no
# matching pairs exist.
#
print 1.0 - (10 ** log_prob_no_pair)
Esto produce un resultado que mira sensible de p = 0,669 para un partido que ocurren dentro de los 100 números de la muestra de una población de 4500 valores posibles. (Tal vez alguien podría verificar esto y publicar un comentario si está mal). De esto podemos ver que las longitudes de carreras entre los números que coinciden observados por la OP parecen ser bastante razonable.
Nota: el uso de barajar para obtener una secuencia única de números pseudo-aleatorios
esta respuesta por debajo de S. Marcos por unos medios de conseguir un conjunto único garantizado de números aleatorios. La técnica del cartel se refiere a toma una matriz de números (que usted proporciona, por lo que puede que sean únicos) y baraja en un orden aleatorio. Dibujo los números en secuencia a partir de la matriz de barajado le dará una secuencia de números pseudo-aleatorios que están garantizados para no repetir.
Nota al pie: criptográficamente seguros PRNGs
El algoritmo MT no es criptográficamente seguro ya que es relativamente fácil inferir el estado interno del generador mediante la observación de una secuencia de números. Otros algoritmos tales como Blum Blum Shub se utilizan para aplicaciones criptográficas, pero puede no ser adecuado para la simulación o general aplicaciones de números aleatorios. Criptográficamente PRNGs seguras pueden ser costosos (tal vez requieran cálculos bignum) o no puede tener buenas propiedades geométricas. En el caso de este tipo de algoritmo, el requisito principal es que debe ser computacionalmente imposible inferir el estado interno del generador mediante la observación de una secuencia de valores.
Otros consejos
Antes de culpar Python, que realmente debería repasar alguna probabilidad y estadísticas teoría. Comience por leer acerca de la paradoja del cumpleaños href="http://en.wikipedia.org/wiki/Birthday_paradox" rel="noreferrer">
Por cierto, el módulo random en Python utiliza el Mersenne Twister PRNG, que se considera muy buena, tiene un enorme periodo y fue ampliamente probado. Así que estar seguro de que está en buenas manos.
Si no desea que uno repetitiva, generar gama secuencial y utilizar azar. aleatoria
La verdadera aleatoriedad definitivamente incluye la repetición de los valores antes de que se agote todo el conjunto de valores posibles. No sería de otra manera aleatoria, ya que sería capaz de predecir por cuánto tiempo no se repita un valor.
Si alguna vez dados los productos laminados, que seguramente tiene 3 seises en la fila muy a menudo ...
aplicación aleatoria de Python es en realidad bastante estado de la técnica:
Esto no es un repetidor. Un repetidor es cuando se repite el mismo secuencia . No sólo un número.
Estás generando números aleatorios 4500 de una gama 500 <= x <= 5000. A continuación, comprobar para ver si para cada número se ha generado antes. El cumpleaños problema nos dice cuál es la probabilidad de dos de esos números para que coincida con n dada pone a prueba de un d gama.
También puede invertir la fórmula para calcular la cantidad de números que tiene que generar hasta la posibilidad de generar un duplicado es más que 50%. En este caso, usted tiene la oportunidad de encontrar >50% un número duplicado después de iteraciones 79.
Ha definido un espacio aleatoria de valores 4501 (500-5000), y que está iterando 4500 veces. Que son básicamente garantizado para conseguir una colisión en la prueba que escribió.
Para pensar de otra manera:
- Cuando la matriz resultado es P vacía (dupe) = 0
- 1 valor en Array P (dupe) = 1/4500
- 2 valores en Array P (dupe) = 2/4500
- etc.
Así que por el momento de llegar a 45/4500, que inserto tiene una probabilidad de 1% de ser un duplicado, y que la probabilidad sigue aumentando con cada inserción posterior.
Para crear una prueba de que realmente pone a prueba las capacidades de la función aleatoria, aumentar el universo de posibles valores aleatorios (por ejemplo: 500-500000) Usted puede, o no puede obtener un duplicado. Pero obtendrá mucho más iteraciones por término medio.
Para cualquier otra persona con este problema, utiliza uuid.uuid4 () y funciona como un encanto.
No es la paradoja del cumpleaños. Teniendo esto en cuenta se da cuenta de que lo que está diciendo es que la búsqueda de "764, 3875, 4290, 4378, 764" o algo por el estilo no es muy aleatorio debido a que un número en esa secuencia se repite. La verdadera manera de hacerlo es comparar las secuencias entre sí. Escribí un script en Python para hacer esto.
from random import randint
y = 21533456
uniques = []
for i in range(y):
x1 = str(randint(500, 5000))
x2 = str(randint(500, 5000))
x3 = str(randint(500, 5000))
x4 = str(randint(500, 5000))
x = (x1 + ", " + x2 + ", " + x3 + ", " + x4)
if x in uniques:
raise Exception('We duped the sequence %d at iteration number %d' % (x, i))
else:
raise Exception('Couldn\'t find a repeating sequence in %d iterations' % (y))
uniques.append(x)
