Aleatório é quase aleatório?

Question

Fiz isso para testar a aleatoriedade do 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

Tentei cerca de 10 vezes mais e o melhor resultado que obtive foram 121 iterações antes de um repetidor.Este é o melhor tipo de resultado que você pode obter na biblioteca padrão?

Answer 1

O paradoxo do aniversário, ou por que os PRNGs produzem duplicatas com mais frequência do que você imagina.

Existem algumas questões em jogo no problema do OP.Um é o paradoxo do aniversário conforme mencionado acima e a segunda é a natureza do que você está gerando, o que não garante inerentemente que um determinado número não se repetirá.

O Paradoxo do Aniversário se aplica onde um determinado valor pode ocorrer mais de uma vez durante o período do gerador - e, portanto, duplicatas podem acontecer dentro de uma amostra de valores.O efeito do Paradoxo do Aniversário é que a probabilidade real de obter tais duplicatas é bastante significativa e o período médio entre elas é menor do que se poderia imaginar.Esta dissonância entre as probabilidades percebidas e reais faz do Paradoxo do Aniversário um bom exemplo de viés cognitivo, onde uma estimativa intuitiva ingênua provavelmente estará totalmente errada.

Uma introdução rápida sobre geradores de números pseudo-aleatórios (PRNGs)

A primeira parte do seu problema é que você está pegando o valor exposto de um gerador de números aleatórios e convertendo-o em um número muito menor, de modo que o espaço de valores possíveis é reduzido.Apesar de alguns geradores de números pseudo-aleatórios não repita valores durante o período, esta transformação altera o domínio para um muito menor.O domínio menor invalida a condição “sem repetições”, portanto você pode esperar uma probabilidade significativa de repetições.

Alguns algoritmos, como o PRNG linear congruente (A'=AX|M) fazer garantir exclusividade para todo o período.Num LCG o valor gerado contém todo o estado do acumulador e nenhum estado adicional é mantido.O gerador é determinístico e não pode repetir um número dentro do período - qualquer valor acumulado do acumulador pode implicar apenas um valor sucessivo possível.Portanto, cada valor só pode ocorrer uma vez dentro do período do gerador.No entanto, o período de tal PRNG é relativamente pequeno - cerca de 2^30 para implementações típicas do algoritmo LCG - e não pode ser maior que o número de valores distintos.

Nem todos os algoritmos PRNG compartilham esta característica;alguns podem repetir um determinado valor dentro do período.No problema do OP, o Mersenne Twister algoritmo (usado em Python aleatório módulo) tem um período muito longo - muito maior que 2 ^ 32.Ao contrário de um PRNG Linear Congruente, o resultado não é puramente uma função do valor de saída anterior, pois o acumulador contém estado adicional.Com saída inteira de 32 bits e um período de ~2^19937, não é possível fornecer tal garantia.

O Mersenne Twister é um algoritmo popular para PRNGs porque possui boas propriedades estatísticas e geométricas e um período muito longo - características desejáveis ​​para um PRNG usado em modelos de simulação.

• Bom propriedades estatísticas significa que os números gerados pelo algoritmo são distribuídos uniformemente, sem que nenhum número tenha uma probabilidade significativamente maior de aparecer do que outros.Propriedades estatísticas deficientes podem produzir distorções indesejadas nos resultados.

• Bom propriedades geométricas significa que conjuntos de N números não estão em um hiperplano no espaço N-dimensional.Propriedades geométricas ruins podem gerar correlações espúrias em um modelo de simulação e distorcer os resultados.

• Um longo período significa que você pode gerar muitos números antes que a sequência chegue ao início.Se um modelo precisar de um grande número de iterações ou tiver que ser executado a partir de várias sementes, então os cerca de 2 ^ 30 números discretos disponíveis em uma implementação típica de LCG podem não ser suficientes.O algoritmo MT19337 tem um período muito longo - 2^19337-1, ou cerca de 10^5821.Em comparação, o número total de átomos no universo é estimado em cerca de 10^80.

O número inteiro de 32 bits produzido por um PRNG MT19337 não pode representar valores discretos suficientes para evitar a repetição durante um período tão grande.Nesse caso, é provável que ocorram valores duplicados e inevitáveis ​​com uma amostra grande o suficiente.

O paradoxo do aniversário em poucas palavras

Este problema é originalmente definido como a probabilidade de duas pessoas na sala fazerem aniversário no mesmo dia.O ponto chave é que quaisquer dois as pessoas na sala poderiam compartilhar um aniversário.As pessoas tendem a interpretar ingenuamente mal o problema como a probabilidade de alguém na sala partilhar o aniversário com um indivíduo específico, o que é a fonte do problema. viés cognitivo isso muitas vezes faz com que as pessoas subestimem a probabilidade.Esta é uma suposição incorreta - não há exigência de que a correspondência seja com um indivíduo específico e quaisquer dois indivíduos podem corresponder.

A probabilidade de ocorrer uma correspondência entre dois indivíduos quaisquer é muito maior do que a probabilidade de uma correspondência com um indivíduo específico, uma vez que a correspondência não precisa ser em uma data específica.Em vez disso, você só precisa encontrar duas pessoas que façam aniversário no mesmo dia.A partir deste gráfico (que pode ser encontrado na página da Wikipedia sobre o assunto), podemos ver que precisamos apenas de 23 pessoas na sala para que haja 50% de chance de encontrar duas que correspondam desta forma.

De Entrada da Wikipedia sobre o assunto podemos conseguir um belo resumo. No problema do OP, temos 4.500 “aniversários” possíveis, em vez de 365.Para um determinado número de valores aleatórios gerados (equivalentes a 'pessoas'), queremos saber a probabilidade de qualquer dois valores idênticos aparecendo na sequência.

Calculando o efeito provável do Paradoxo do Aniversário no problema do OP

Para uma sequência de 100 números, temos pares (ver Compreendendo o problema) que poderia potencialmente corresponder (ou seja,o primeiro poderia corresponder ao segundo, terceiro etc., o segundo poderia corresponder ao terceiro, quarto etc.e assim por diante), então o número de combinações que poderia potencialmente corresponder é um pouco mais do que apenas 100.

De Calculando a probabilidade obtemos uma expressão de .O seguinte trecho de código Python abaixo faz uma avaliação ingênua da probabilidade de ocorrência de um par correspondente.

# === 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)

Isto produz um resultado de aparência sensata de p=0,669 para uma correspondência que ocorre dentro de 100 números amostrados de uma população de 4.500 valores possíveis.(Talvez alguém possa verificar isso e postar um comentário se estiver errado).A partir disso, podemos ver que a duração das execuções entre os números correspondentes observados pelo OP parece ser bastante razoável.

Nota de rodapé:usando embaralhamento para obter uma sequência única de números pseudo-aleatórios

Ver esta resposta abaixo de S.Marca como um meio de obter um conjunto único garantido de números aleatórios.A técnica à qual o pôster se refere pega uma série de números (que você fornece, para que possa torná-los únicos) e os embaralha em uma ordem aleatória.Desenhar os números em sequência da matriz embaralhada fornecerá uma sequência de números pseudo-aleatórios que certamente não serão repetidos.

Nota de rodapé:PRNGs criptograficamente seguros

O algoritmo MT não é criptograficamente seguro pois é relativamente fácil inferir o estado interno do gerador observando uma sequência de números.Outros algoritmos como Blum Blum Shub são usados ​​para aplicações criptográficas, mas podem ser inadequados para simulação ou aplicações gerais de números aleatórios.PRNGs criptograficamente seguros podem ser caros (talvez exijam cálculos de bignum) ou podem não ter boas propriedades geométricas.No caso deste tipo de algoritmo, o requisito principal é que seja computacionalmente inviável inferir o estado interno do gerador observando uma sequência de valores.

Answer 2

Antes de culpar o Python, você realmente deve aprimorar alguma teoria de probabilidade e estatística. Comece lendo sobre o Paradoxo de aniversário

A propósito, o random módulo em python usa o Mersenne Twister O PRNG, que é considerado muito bom, tem um período enorme e foi extensivamente testado. Então tenha certeza de que você está em boas mãos.

Answer 3

Se você não quer um repetitivo, gere matriz seqüencial e use Random.Shuffle

Answer 4

Como resposta para a resposta de Nimbuz:

http://xkcd.com/221/

Answer 5

A verdadeira aleatoriedade definitivamente inclui a repetição de valores antes que todo o conjunto de valores possíveis seja esgotado. Não seria aleatório de outra forma, pois você seria capaz de prever por quanto tempo um valor não seria repetido.

Se você já rolou dados, certamente tem 3 seis na fila com bastante frequência ...

Answer 6

A implementação aleatória de Python é na verdade bastante estado da arte:

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

Answer 7

Isso não é um repetidor. Um repetidor é quando você repetiu o mesmo seqüência. Não apenas um número.

Answer 8

Você está gerando 4500 números aleatórios de um intervalo 500 <= x <= 5000. Você então verifica para ver cada número se ele já foi gerado antes. o Problema de aniversário nos diz qual é a probabilidade de dois desses números combinar n tenta fora de um intervalo d.

Você também pode inverter a fórmula para calcular quantos números você deve gerar até que a chance de gerar uma duplicata seja mais do que 50%. Nesse caso, você tem um >50% chance de encontrar um número duplicado depois 79 iterações.

Answer 9

Você definiu um espaço aleatório de 4501 valores (500-5000) e está iterando 4500 vezes. Você é basicamente garantido para obter uma colisão no teste que escreveu.

Para pensar sobre isso de outra maneira:

• Quando a matriz de resultados está vazia p (dupe) = 0
• 1 valor na matriz p (dupe) = 1/4500
• 2 valores na matriz P (dupe) = 2/4500
• etc.

Então, quando você chegar a 45/4500, essa inserção tem 1% de chance de ser uma duplicata, e essa probabilidade continua aumentando a cada inserção subsequente.

Para criar um teste que realmente testa as habilidades da função aleatória, aumente o universo de possíveis valores aleatórios (por exemplo: 500-500000), você pode ou não obter um idiota. Mas você terá muito mais iterações em média.

Answer 10

Para qualquer outra pessoa com esse problema, usei uuid.uuid4 () e funciona como um charme.

Answer 11

Há o paradoxo de aniversário. Levando isso em consideração, você percebe que o que está dizendo é que encontrar "764, 3875, 4290, 4378, 764" ou algo assim não é muito aleatório, porque um número nessa sequência se repete. A verdadeira maneira de fazer isso é comparar sequências entre si. Eu escrevi um script python para fazer isso.

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)