Por que é impossível produzir números verdadeiramente aleatórios?

Eu estava tentando resolver um problema de hobby que exigia a geração de um milhão de números aleatórios. Mas rapidamente percebi que está se tornando difícil torná-los únicos. Peguei o Algorithm Design Manual para ler sobre geração de números aleatórios.

Ele tem o parágrafo a seguir que eu não sou totalmente capaz de entender.

Infelizmente, gerar números aleatórios parece muito mais fácil do que realmente é. De fato, é fundamentalmente impossível produzir números verdadeiramente aleatórios em qualquer dispositivo determinístico. Von Neumann [Neu63] disse o melhor: “Qualquer um que considere métodos aritméticos de produção de dígitos aleatórios está, é claro, em um estado de pecado.” O melhor que podemos esperar são números pseudo-aleatórios, um fluxo de números que aparece como se eles foram gerados aleatoriamente.

Por que é impossível produzir números verdadeiramente aleatórios em qualquer dispositivo determinístico? O que está frase significa?

Deve-se procurar um gerador de números pseudo-aleatórios criptograficamente seguro . A maioria dos PRNG são geradores de congruência linear (também next numberé uma função linear de previous number), portanto, se você plotar next numbervs, previous numberobterá um gráfico de linhas paralelas. Um CSPRNG não fará isso. A desvantagem é que eles são lentos.

Eu agrupo geradores de números aleatórios em 3 categorias :

1. Bom o suficiente para trabalhos de casa.
2. Bom o suficiente para apostar em sua empresa.
3. Bom o suficiente para apostar no seu país.

Por que é impossível produzir números verdadeiramente aleatórios em qualquer dispositivo determinístico?

Um dispositivo determinístico sempre produzirá a mesma saída quando recebidas as mesmas condições e entradas de partida - é isso que significa ser deterministic. "Número verdadeiramente aleatório" é mais um ponto de vista filosófico, pois o que significa ser randomo cerne do olhar filosófico do umbigo (as pessoas nem têm certeza se a decadência atômica é aleatória ou segue algum padrão que simplesmente não conseguimos descobrir. ainda). Um gerador de números aleatórios criptograficamente seguro precisará de uma fonte externa de entropia para tornar o dispositivo não determinístico.

A verdadeira aleatoriedade implica não-determinismo. Se é determinístico, pode ser previsto com precisão (é isso que determinismo significa); se pode ser previsto, não é aleatório.

A melhor coisa que você pode obter de um gerador de números pseudo-aleatórios determinísticos é um fluxo de números que possui um ciclo muito longo (não é possível repetir a menos que seu dispositivo RNG tenha armazenamento ilimitado) que, durante o ciclo, produz um números de fluxo que atendem a todas as outras propriedades de uma sequência aleatória (uma distribuição uniforme de valores sendo a mais interessante).

Para resolver esse problema, muitos UNIXes modernos e similares ao Unix têm RNGs de kernel que usam fontes de ruído físico para gerar uma verdadeira aleatoriedade.

Outra abordagem comum é considerar o tempo atual como a semente de um RNG determinístico ( srand(time(NULL));em C); criptograficamente falando, isso não vale nada, já que o tempo atual não é segredo, mas para coisas como simulações físicas ou videogames, é bom o suficiente.

O segundo capítulo do livro Simulação de Eventos Discretos: Um Primeiro Curso de Lawrence Leemis fornece uma introdução fantástica aos geradores de números aleatórios (ou, mais precisamente, aos geradores de números aleatórios psuedo).

Um trecho de seu livro explica bem na minha opinião:

Historicamente, três tipos de geradores de números aleatórios têm sido defendidos para aplicações computacionais: (a) geradores de consulta de tabela no estilo dos anos 50, como, por exemplo, a tabela corporativa da RAND com um milhão de dígitos aleatórios; (b) geradores de hardware como, por exemplo, dispositivos térmicos de "ruído branco"; e (c) geradores algorítmicos (de software). Desses três tipos, apenas geradores algorítmicos alcançaram ampla aceitação. A razão para isso é que apenas geradores algorítmicos têm o potencial de satisfazer todos os seguintes critérios de geração de números aleatórios geralmente bem aceitos. Um gerador deve ser:

• random - capaz de produzir resultados que passam em todos os testes estatísticos razoáveis ​​de aleatoriedade;
• controlável - capaz de reproduzir sua saída, se desejado;
• portátil - capaz de produzir a mesma saída em uma ampla variedade de sistemas de computador;
• eficiente - rápido, com requisitos mínimos de recursos do computador;
• documentado - teoricamente analisado e extensivamente testado.

Portanto, embora seja possível usar um gerador de ruído branco para obter números aleatórios "melhores", eles não obtiveram aceitação porque não seguem a maioria dos critérios acima.

Eu recomendaria que você pusesse as mãos em uma cópia desse livro (ou em algo semelhante). Entender exatamente como o trabalho do PRNG definitivamente o ajudará em seus esforços.

Porque você precisa escrever um código para gerar os números aleatórios e o código NÃO é aleatório. (É determinista)

Então você começa com um "Valor inicial (es)" escolhido em "Aleatório" (geralmente o horário atual) e o usa em um algoritmo para começar a gerar números. Mas todo o conjunto é baseado no valor original da Semente!

Portanto, se você executar seu código novamente com os mesmos valores de semente, obterá exatamente o mesmo conjunto de números! Como alguém razoavelmente pode chamar isso de aleatório? Mas com certeza faz OLHE aleatória.

Em relação a torná-los únicos, depois de gerar um número, basta verificar se você já tem esse número, se tiver, jogue-o fora e gere um novo.

Como você está gerando números aleatórios, você deve esperar que os valores gerados sejam não exclusivos. Essa é uma propriedade da aleatoriedade - você não pode dizer que uma sequência de números verdadeiramente aleatórios (ou mesmo pseudo-aleatórios) é única, porque esse requisito permitiria a previsão do valor final no intervalo, além de alterar a probabilidade de todos os números não escolhidos cada vez que um novo é selecionado.

Eu tenho uma definição muito simples de Pseudo Random :

Muitas variáveis ​​desconhecidas para prever.

Eu também tenho uma definição simples de True Random :

Variáveis ​​desconhecidas infinitas.

O problema com um computador é que ele sempre conhece TODAS as variáveis. O número aleatório é simplesmente uma função matemática de algum valor inicial .
O melhor que podemos fazer é fornecer ao computador um valor de semente pseudo-aleatório, que geralmente é baseado em uma variável que não podemos prever (como tempo exato).

Mesmo que um computador seja absolutamente incapaz de criar um número aleatório, é bom introduzir muitas variáveis ​​para prever!

Na verdade, não é possível gerar números verdadeiramente aleatórios no software , como outros já apontaram, mas é possível com o hardware construir um dispositivo que possa gerar números verdadeiramente aleatórios *. Existem muitos exemplos disso na Internet, e há uma variedade de métodos usados, desde a leitura do tempo entre os carrapatos no contador Geiger até a amostragem do ruído branco (principalmente a radiação de fundo do universo) de um receptor não sintonizado. Eu mesmo construí alguns usando alguns dos métodos disponíveis.

* Qualquer bom geek da física indicará que, dada a maneira como o universo opera, nada disso é hiper-tecnicamente verdadeiramente aleatório, mas não há uma maneira razoável de prever os resultados, portanto, para o bem dessa discussão, eles são suficientes.

Não há como você produzir um número aleatório sem um hardware especial. No meu primeiro ano, alguns colegas de classe e eu propusemos um gerador de números aleatórios que tivesse basicamente um receptor AM e sintonizado em 4 canais diferentes, coloque a entrada em um conversor A para D e adicione todos eles (module seu número máximo). Como a combinação de entrada analógica de qualquer número arbitrário de estações é aleatória e poderíamos produzir um grande número de números aleatórios a partir do conversor A2D, propusemos que este poderia ser um bom gerador. Certamente, mesmo isso não é verdadeiramente aleatório em um sentido filosófico, embora, para a maioria dos propósitos práticos, isso possa funcionar.

O determinismo é essencialmente uma função. Lembre-se de Álgebra que uma função é uma correspondência entre um domínio e um intervalo, de modo que cada membro do domínio corresponda exatamente a um membro do intervalo.

Portanto, se f (x) = z, f (x)! = Y, a menos que y seja z. Essa é uma função. Imagine JavaScript:

function Add(A, B) {
      return A + B;
}

var addedNumber = Add(2,3);//returns 5
addedNumber = Add(2,3);//still 5

Não importa quantas vezes você chame, Add(2,3)ele sempre retornará 5. Em outras palavras, Add () é uma função determinística.

Fatores externos podem fazer o Add se comportar de maneira não determinística. Por exemplo, se você introduzir multithreading na equação. A contribuição humana também causa não determinismo.

Agora, é aqui que as coisas ficam interessantes.

"Qualquer um que considere métodos aritméticos de produzir dígitos aleatórios está, é claro, em estado de pecado."

Nota Von Neumann afirma, "métodos aritméticos de produção [...]". Não se trata de dados humanos, simultaneidade, velocidade de amostra de vento lida por um instrumento preciso ou outras formas não algorítmicas de produzir dados aleatórios para uma função determinística.

Isso simplesmente afirma que uma função ou sistema de funções não se tornará subitamente determinístico. Em outras palavras, Add (2,3) não retornará, de alguma forma, 6 ou nada além de 5, com as mesmas entradas . Isso é impossível.

O autor da citação dá um passo adiante.

O melhor que podemos esperar são números pseudo-aleatórios, um fluxo de números que aparecem como se fossem gerados aleatoriamente.

O contexto é definido anteriormente como "em qualquer dispositivo determinístico". Eu poderia terminar a discussão aqui. Mas, e se mudarmos o contexto, introduzindo um novo elemento no sistema? Um elemento não determinístico adicionado como entrada torna o sistema um sistema não determinístico. Embora, removendo o elemento não determinístico, reduzamos de volta a um sistema determinístico. Se, de alguma forma, podemos rastrear ou reproduzir as entradas, podemos reproduzir um resultado. Mas este parágrafo inteiro é tangencial ao que o autor está dizendo. Lembre-se do contexto.

Pode-se discutir sobre o significado do não-determinismo. Mais uma vez, tangencial. Lembre-se do contexto.

Então ele está correto. Em qualquer dispositivo determinístico , é impossível para um sistema determinístico produzir um verdadeiro resultado aleatório.