¿Aleatorio es apenas aleatorio en absoluto?

Hice 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

Intenté unas 10 veces más y el mejor resultado que obtuve fueron 121 iteraciones antes de un repetidor. ¿Es este el mejor tipo de resultado que puede obtener de la biblioteca estándar?

La paradoja del cumpleaños, o por qué los PRNG producen duplicados con más frecuencia de lo que cree.

Hay un par de cuestiones en juego en el problema del OP. Una es la paradoja del cumpleaños como se mencionó anteriormente y la segunda es la naturaleza de lo que está generando, que no garantiza de manera inherente que un número determinado no se repita.

La paradoja del cumpleaños se aplica cuando un valor dado puede ocurrir más de una vez durante el período del generador y, por lo tanto, pueden ocurrir duplicados en una muestra de valores. El efecto de la paradoja del cumpleaños es que la probabilidad real de obtener tales duplicados es bastante significativa y el período promedio entre ellos es menor de lo que uno podría haber pensado. Esta disonancia entre las probabilidades percibidas y reales hace que la paradoja del cumpleaños sea un buen ejemplo de sesgo cognitivo , donde una estimación intuitiva ingenua es probable que sea tremendamente errónea.

Una introducción rápida a los generadores de números pseudoaleatorios (PRNG)

La primera parte de su problema es que está tomando el valor expuesto de un generador de números aleatorios y convirtiéndolo en un número mucho más pequeño, por lo que el espacio de valores posibles se reduce. Aunque algunos generadores de números pseudoaleatorios no repiten valores durante su período, esta transformación cambia el dominio a uno mucho más pequeño. El dominio más pequeño invalida la condición 'sin repeticiones', por lo que puede esperar una probabilidad significativa de repeticiones.

Algunos algoritmos, como el PRNG ( A'=AX|M) congruencial lineal , garantizan la unicidad para todo el período. En una LCG, el valor generado contiene todo el estado del acumulador y no se mantiene ningún estado adicional. El generador es determinista y no puede repetir un número dentro del período; cualquier valor de acumulador dado puede implicar solo un valor sucesivo posible. Por lo tanto, cada valor solo puede ocurrir una vez dentro del período del generador. Sin embargo, el período de dicho PRNG es relativamente pequeño, 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 del OP, el algoritmo Mersenne Twister (utilizado en el módulo aleatorio de Python ) tiene un período muy largo, mucho mayor que 2 ^ 32. A diferencia de un PRNG congruencial lineal, el resultado no es simplemente una función del valor de salida anterior, ya que el acumulador contiene un estado adicional. Con una salida de entero de 32 bits y un período de ~ 2 ^ 19937, no es posible que proporcione tal garantía.

El Mersenne Twister es un algoritmo popular para PRNG 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.

• Las buenas propiedades estadísticas significan que los números generados por el algoritmo se distribuyen uniformemente sin números que tengan una probabilidad de aparecer significativamente mayor que otros. Las propiedades estadísticas deficientes podrían producir una distorsión no deseada en los resultados.

• Las buenas propiedades geométricas significan que los conjuntos de N números no se encuentran en un hiperplano en el espacio N-dimensional. Las malas propiedades geométricas pueden generar correlaciones falsas en un modelo de simulación y distorsionar los resultados.

• Un período largo significa que puede generar muchos números antes de que la secuencia llegue al comienzo. Si un modelo necesita una gran cantidad de iteraciones o tiene que ejecutarse desde varias semillas, entonces los 2 ^ 30 o más números discretos disponibles de una implementación típica de 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 producido por un PRNG MT19337 posiblemente no puede representar suficientes valores discretos para evitar que se repita durante un período tan grande. En este caso, es probable que se produzcan valores duplicados e inevitables con una muestra lo suficientemente grande.

La paradoja del cumpleaños en pocas palabras

Este problema se define originalmente como la probabilidad de que dos personas en la habitación compartan el mismo cumpleaños. El punto clave es que dos personas en la sala podrían compartir un cumpleaños. La gente tiende a malinterpretar ingenuamente el problema como la probabilidad de que alguien en la habitación comparta un cumpleaños con un individuo específico, que es la fuente del sesgo cognitivo que a menudo hace que las personas subestimen la probabilidad. Esta es la suposición incorrecta: no es necesario que la coincidencia sea para un individuo específico y dos individuos podrían coincidir.

La probabilidad de que ocurra una coincidencia entre dos individuos es mucho mayor que la probabilidad de una coincidencia con un individuo específico, ya que la coincidencia no tiene que ser para una fecha específica. Más bien, solo tiene que encontrar dos personas que compartan 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 solo necesitamos 23 personas en la sala para que haya un 50% de posibilidades de encontrar dos que coincidan de esta manera.

De la entrada de Wikipedia sobre el tema podemos obtener un buen resumen. En el problema de OP, tenemos 4.500 posibles 'cumpleaños', en lugar de 365. Para un número dado de valores aleatorios generados (que equivalen a 'personas') queremos saber la probabilidad de que aparezcan dos valores idénticos cualesquiera dentro de la secuencia.

Calcular el efecto probable de la paradoja del cumpleaños en el problema del OP

Para una secuencia de 100 números, tenemos pares (consulte Comprensión del problema ) que podrían coincidir (es decir, el primero podría coincidir con el segundo, el tercero, etc., el segundo podría coincidir con el tercero, el cuarto, etc., etc.), por lo que la cantidad de combinaciones que potencialmente podrían coincidir es bastante más de 100.

Al calcular 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 ocurra 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 de apariencia razonable de p = 0,669 para una coincidencia que ocurre dentro de 100 números muestreados de una población de 4500 valores posibles. (Tal vez alguien pueda verificar esto y publicar un comentario si está mal). A partir de esto, podemos ver que las longitudes de las corridas entre los números coincidentes observados por el OP parecen ser bastante razonables.

Nota a pie de página: usar la mezcla para obtener una secuencia única de números pseudoaleatorios

Consulte esta respuesta a continuación de S. Mark para conocer un medio de obtener un conjunto único garantizado de números aleatorios. La técnica a la que se refiere el póster toma una serie de números (que usted proporciona, para que pueda hacerlos únicos) y los mezcla en un orden aleatorio. Sacar los números en secuencia de la matriz mezclada le dará una secuencia de números pseudoaleatorios que están garantizados para no repetirse.

Nota al pie: PRNG criptográficamente seguros

El algoritmo MT no es criptográficamente seguro ya que es relativamente fácil inferir el estado interno del generador observando una secuencia de números. Otros algoritmos como Blum Blum Shub se utilizan para aplicaciones criptográficas, pero pueden no ser adecuados para aplicaciones de simulación o números aleatorios generales. Los PRNG criptográficamente seguros pueden ser costosos (quizás requieran cálculos bignum) o pueden no tener buenas propiedades geométricas. En el caso de este tipo de algoritmo, el requisito principal es que sea computacionalmente inviable inferir el estado interno del generador observando una secuencia de valores.

Antes de culpar a Python, debería repasar un poco la teoría de la probabilidad y la estadística. Empiece por leer sobre la paradoja del cumpleaños

Por cierto, el randommódulo en Python usa el Mersenne twister PRNG, que se considera muy bueno, tiene un período enorme y fue probado exhaustivamente. Así que tenga la seguridad de que está en buenas manos.

Si no desea uno repetitivo, genere una matriz secuencial y use random.shuffle

Como respuesta a la respuesta de Nimbuz:

http://xkcd.com/221/

La verdadera aleatoriedad definitivamente incluye la repetición de valores antes de que se agote todo el conjunto de valores posibles. De lo contrario, no sería aleatorio, ya que podría predecir durante cuánto tiempo no se repetirá un valor.

Si alguna vez tiraste dados, seguramente sacaste 3 seises seguidos con bastante frecuencia ...

La implementación aleatoria de Python es en realidad bastante avanzada:

• http://en.wikipedia.org/wiki/Mersenne_twister
• http://docs.python.org/library/random.html

Eso no es un repetidor. Un repetidor es cuando repites la misma secuencia . No solo un número.

Estás generando 4500números aleatorios a partir de un rango 500 <= x <= 5000. Luego, verifica para ver cada número si se ha generado antes. El problema del cumpleaños nos dice cuál es la probabilidad de que dos de esos números coincidan con los nintentos dados fuera de un rango d.

También puede invertir la fórmula para calcular cuántos números tiene que generar hasta que la probabilidad de generar un duplicado sea mayor que 50%. En este caso, tiene la >50%posibilidad de encontrar un número duplicado después de las 79iteraciones.

Ha definido un espacio aleatorio de 4501 valores (500-5000) y está iterando 4500 veces. Básicamente, está garantizado que obtendrá una colisión en la prueba que escribió.

Para pensarlo de otra manera:

• Cuando la matriz de resultados está vacía P (duplicado) = 0
• 1 valor en Array P (duplicado) = 1/4500
• 2 valores en Array P (duplicado) = 2/4500
• etc.

Entonces, para cuando llegue a 45/4500, esa inserción tiene un 1% de probabilidad de ser un duplicado, y esa probabilidad sigue aumentando con cada inserción subsiguiente.

Para crear una prueba que realmente pruebe las capacidades de la función aleatoria, aumente el universo de posibles valores aleatorios (por ejemplo: 500-500000). Puede obtener o no una víctima. Pero obtendrás muchas más iteraciones en promedio.

Para cualquier otra persona con este problema, usé uuid.uuid4 () y funciona como un encanto.

Existe la paradoja del cumpleaños. Teniendo esto en cuenta, te das cuenta de que lo que estás diciendo es que encontrar "764, 3875, 4290, 4378, 764" o algo así no es muy aleatorio porque un número en esa secuencia se repite. La verdadera forma de hacerlo es comparar secuencias entre sí. Escribí un script de 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)