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

Deve-se procurar um gerador de números pseudo-aleatórios criptograficamente seguro . A maioria dos PRNGs são geradores de congruência linear (então next number é uma função linear de previous number ), então se você traçar next number vs previous number você obterá um gráfico de linhas paralelas. Um CSPRNG não fará isso. O trade-off é que eles são lentos.

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

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

Why is it impossible to produce truly random numbers in any deterministic device ?

Um dispositivo determinístico sempre produzirá a mesma saída quando receber as mesmas condições iniciais e entradas - é isso que significa ser deterministic . "Número verdadeiramente aleatório" é mais um ponto de vista filosófico, como o que significa ser random é o ponto crucial do olhar filosófico do umbigo (as pessoas não têm certeza se o decaimento atômico é aleatório ou segue algum padrão que simplesmente podemos " t descobrir ainda). Um gerador de números aleatórios criptograficamente seguro vai precisar de alguma fonte externa de entropia para tornar o dispositivo não-determinístico.

Verdadeira aleatoriedade implica não-determinismo. Se é determinista, pode ser previsto com precisão (isso é o que significa determinismo); 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 tem um ciclo muito longo (não é possível repetir, a menos que seu dispositivo RNG possua armazenamento ilimitado) que, durante a duração do ciclo , produz um número de fluxo que atende a todas as outras propriedades de uma seqüência aleatória (uma distribuição uniforme de valores sendo a mais interessante).

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

Outra abordagem comum é tomar o tempo atual como a semente para um RNG determinístico ( srand(time(NULL)); em C); criptograficamente falando, isso é inútil, 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 Evento Discreto: Um Primeiro Curso de Lawrence Leemis oferece uma fantástica introdução aos geradores de números aleatórios (ou, mais precisamente, geradores de números aleatórios).

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

Historically three types of random number generators have been advocated for computational applications: (a) 1950's-style table look-up generators like, for example, the RAND corporation table of a million random digits; (b) hardware generators like, for example, thermal "white noise" devices; and (c) algorithmic (software) generators. Of these three types, only algorithmic generators have achieved widespread acceptance. The reason for this is that only algorithmic generators have the potential to satisfy all of the following generally well-accepted random number generation criteria. A generator should be:

• random - able to produce output that passes all reasonable statistical tests of randomness;
• controllable - able to reproduce its output, if desired;
• portable - able to produce the same output on a wide variety of computer systems;
• efficient - fast, with minimal computer resource requirements;
• documented - theoretically analyzed and extensively tested.

Assim, 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 similar). Entender exatamente como o trabalho do PRNG definitivamente o ajudará em seus esforços.

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

Então você acaba começando com um "valor de semente (s)" que é escolhido em "Aleatório" (normalmente o registro de data e hora atual) e então o utiliza em um algoritmo para começar a gerar números. Mas todo o conjunto é baseado no valor original da Semente!

Então, se você executar seu código novamente com o mesmo (s) mesmo (s) valor (es), você obterá o mesmo conjunto de números EXATOS! Como qualquer pessoa razoavelmente pode chamar isso de aleatório? Mas com certeza faz LOOK random.

Em relação a torná-los únicos, depois de gerar um número, basta verificar se você já tem esse número, se fizer isso, 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. Esta é uma propriedade de aleatoriedade - não se pode dizer que uma sequência de números verdadeiramente aleatórios (ou mesmo pseudo-aleatórios) seja única, porque esse requisito permitiria que o valor final no intervalo fosse previsto, assim como a probabilidade de todos os números não escolhidos sempre que um novo for 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 :

Infinitas variáveis desconhecidas.

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 de semente .
O melhor que podemos fazer é dar ao computador um valor de semente pseudo-aleatório, que geralmente é baseado em uma variável que não podemos prever (como o tempo exato).

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

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

* Qualquer bom geek da física apontará que, dada a maneira como o universo opera, nenhuma delas é hiper-técnica, verdadeiramente aleatória, mas não existe uma maneira razoável de prever a resulta assim, por causa desta 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 e eu propusemos um gerador de números aleatórios que tinha basicamente um receptor AM e sintonizava 4 canais diferentes, obtém a entrada em um conversor A a D e adiciona todos eles (módulo seu número máximo). Como a combinação da 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 do conversor A2D, propusemos que este poderia ser um bom gerador. Naturalmente, 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 tal forma que cada membro do domínio corresponde a exatamente um membro do intervalo.

Então, 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ê chamar Add(2,3) , ele sempre retornará 5. Em outras palavras, Add () é uma função determinística.

Fatores externos podem fazer com que o Add se comporte de uma maneira não determinista. Por exemplo, se você introduzir multithreading na equação. O input humano também causa o não-determinismo.

Agora, é aqui que as coisas ficam interessantes.

“Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.”

Nota Von Neumann afirma, "métodos aritméticos de produzir [...]". Isso não está falando sobre entrada humana, concorrência, velocidades de vento de amostra lidas a partir de um instrumento preciso ou outras formas não algorítmicas de produzir entrada aleatória para uma função determinística.

Isso simplesmente afirma que uma função ou sistema de funções não se tornará de repente não-determinístico. Em outras palavras, o Add (2,3) não retornará de alguma forma 6 ou qualquer coisa diferente de 5 dadas as mesmas entradas . Isso é impossível.

O autor citante dá um passo adiante.

The best we can hope for are pseudo-random numbers, a stream of numbers that appear as if they were generated randomly.

O contexto é definido anteriormente como "em qualquer dispositivo determinístico". Eu poderia terminar o argumento 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, somos reduzidos a um sistema determinístico. Se pudermos de alguma forma rastrear ou reproduzir as entradas, podemos reproduzir um resultado. Mas este parágrafo inteiro é tangetenial ao que o autor está dizendo. Lembre-se do contexto.

Alguém poderia discutir sobre o significado do não-determinismo. Mais uma vez, tangetenial. Lembre-se do contexto.

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