O que é realmente a aleatoriedade

Sou estudante de Ciência da Computação e atualmente estou matriculado no curso de Simulação e Modelagem de Sistemas. Envolve lidar com os sistemas cotidianos ao nosso redor e simulá-los em diferentes cenários, gerando números aleatórios em diferentes curvas distributivas, como IID, Gaussian etc., por exemplo. Eu estive trabalhando no projeto boids e uma pergunta me ocorreu: o que exatamente "aleatório" realmente é? Quero dizer, por exemplo, todo número aleatório que geramos, mesmo em nossas linguagens de programação, como o Math.random()método em Java, é gerado essencialmente seguindo um "algoritmo".

Como sabemos realmente que uma sequência de números que produzimos é de fato aleatória e nos ajudaria a simular um determinado modelo com a maior precisão possível?

A resposta curta é que ninguém sabe o que é a aleatoriedade real ou se existe algo assim. Se você deseja quantificar ou medir a aleatoriedade de um objeto discreto, normalmente recorre à complexidade de Kolmogorov . Antes da complexidade de Kolmogorov, não tínhamos como quantificar a aleatoriedade, digamos uma sequência de números, sem considerar o processo que a gerou.

Aqui está um exemplo intuitivo que realmente incomodava as pessoas naquela época. Considere uma sequência de lançamentos de moedas. O resultado de um sorteio é cara ( ) ou coroa ( ). Digamos que façamos dois experimentos, onde jogamos uma moeda 10 vezes. A primeira experiência dá-nos . A segunda experiência nos dá . Depois de ver o resultado, você pode ficar tentado a afirmar que havia algo errado com a moeda em , ou pelo menos por algum motivo estranho, o que você obteve não é aleatório. Mas se você presumir que e são tão prováveis ​​(a moeda é justa), a probabilidade de obterT E 1 H , H , H , H , H , H , H , H , H , H E 2 T , T , H , T , H , T , T , H , T , H E 1 H T E 1 E 2 ( 1 / 2 ) 10 E 2 $H$$T$$E_1$$H,H,H,H,H,H,H,H,H,H$$E_2$$T,T,H,T,H,T,T,H,T,H$$E_1$$H$$T$$E_1$ ou é igual a . De fato, obter qualquer sequência específica é tão provável quanto qualquer outra! Ainda assim, parece aleatório e não.$E_2$$(1/2)^{10}$$E_2$ $E_1$

Em geral, como a complexidade de Kolmogorov não é computável, não se pode calcular o quão aleatória é uma sequência de números, independentemente do tipo de processo "totalmente aleatório" alegado que a gerou.

No caso de Java (ou linguagens similares), conhecemos o algoritmo usado para criar os números aleatórios. Se começar com uma única semente, os números não são aleatórios, ou seja, se conhecermos na sequência , conheceremos ou declarados como probabilidade condicional: a 0 , … , a n a i + 1 ∀ k , l , i : P ( a i + 1 = k ∣ a i = l ) ∈ { 0 , 1 $a_i$$a_0,\dots,a_n$$a_{i+1}$

No entanto, essas séries podem preencher propriedades (ver, por exemplo, WP: Autocorrelação ) que números aleatórios atendem e essas propriedades costumam ser suficientes para realizar tarefas, nas quais gostaríamos de usar números aleatórios "reais" (por exemplo, gerados por algum processo físico), mas podem ' Não os esforce.

É impossível saber com certeza se uma determinada sequência é aleatória ou não. No entanto, é possível examinar as características (ou parâmetros) de uma sequência e calcular a probabilidade de uma sequência, dada a distribuição de interesse.

Se você puder gerar uma sequência infinitamente longa usando seu gerador aleatório, ele deverá ter os mesmos parâmetros que a distribuição aleatória. Por exemplo, se você estiver usando a distribuição gaussiana padrão , sua sequência deverá se aproximar da média de 0 e do desvio padrão de . Portanto, uma maneira preliminar de verificar seu gerador é gerar uma sequência realmente longa e verificar se está se aproximando da distribuição aleatória desejada.$(\mu=0,\sigma=1)$$1$

Você pode adicionar momentos adicionais da distribuição (como assimetria) de interesse para validação adicional. Para números de IDI, você também pode tentar treinar um algoritmo de aprendizado de máquina para prever os próximos elementos da sequência e, em seguida, testar a hipótese nula de que o histórico melhora o desempenho. Nenhum desses métodos, no entanto, pode provar que uma sequência é verdadeiramente aleatória e, na melhor das hipóteses, pode reconhecer quando as seqüências NÃO são aleatórias (com algum grau de certeza).

A teoria moderna da resposta da computação é "uma fonte aleatória é uma fonte que parece aleatória para sua classe favorita de algoritmos". Esta é uma perspectiva utilitária: se uma fonte de aleatoriedade se parece com verdadeira aleatoriedade para todos os algoritmos com os quais você se preocupa, nada mais importa. Você pode analisar seus algoritmos como se eles recebessem sorteios aleatórios de moedas, e sua análise fornecerá as respostas corretas.

Para ser um pouco mais preciso, digamos que você se preocupe com todos os algoritmos de uma classe . pode ser$\mathcal{A}$$\mathcal{A}$

• todas as máquinas de Turing que sempre param
• todas as famílias de circuitos de tamanho polinomial
• todas as máquinas de Turing de tempo polinomial
• todas as máquinas de Turing de espaço de log

A classe será os "distinguidores". Então, uma sequência de variáveis ​​aleatórias que obtém valores em é -pseudorandom contra se, para todos os , que é uma variável aleatória distribuída uniformemente em .$\mathcal{A}$$(X_n)$$X_n$$\{0, 1\}^n$$\epsilon$$\mathcal{A}$$A \in \mathcal{A}$

Essa idéia está por trás de qualquer noção formal moderna de pseudo-aleatoriedade.

Aqui estão mais dois centavos.

Uma maneira de pensar em algoritmos aleatórios é imaginar uma caixa que receba alguma entrada, faça coisas misteriosas nessa entrada e produza alguma saída ("imprevisível").

Mas, em vez disso, pode ser útil pensar neles como algoritmos determinísticos que recebem duas entradas: a entrada "verdadeira" e algumas entradas "aleatórias" que obtemos de funções como Math.Random().

Agora, quando se analisa o algoritmo, podemos fazer afirmações como esta: " Se nossos entradas aleatórias são uniformes e independente sobre , em seguida, com alta probabilidade nossos algoritmo roda em tempo " ou "com grande probabilidade do resposta está correta ".$[0,1]$$n \log n$

Este é um fato verdadeiro sobre o nosso algoritmo. Agora, uma segunda pergunta é se as entradas aleatórias realmente correspondem a esse tipo de suposição. Gosto do tipo de visão bayesiana que diz o seguinte: suponha que, no melhor de meus conhecimentos e crenças , a aleatoriedade de minhas informações seja uniforme e independente em . Então, o fato que provamos acima me diz em que acreditar sobre a saída do meu algoritmo (a saber, que é muito provável que funcione no tempo ou esteja correto ou assim por diante).n log $[0,1]$$n \log n$

Como Jonathan e Frafl mencionam, existem maneiras de verificar se uma fonte aleatória está se comportando "aleatoriamente". Mas tudo o que eles farão é influenciar o que você acredita sobre informações futuras provenientes dessa fonte aleatória. Se você acha que é provável que cada bit seja zero ou um, independentemente dos bits anteriores, com o melhor de seus conhecimentos e crenças, essa fonte é aleatória uniforme e independentemente e, portanto, com o melhor de seus conhecimentos e crenças, ele será executado rapidamente ou estará correto ou assim por diante. Essa é a minha opinião filosófica, de qualquer maneira.

Não podemos gerar números verdadeiramente aleatórios. Existem métodos diferentes para geração de números pseudo-aleatórios usando uma equação especificada e um valor de semente específico. Portanto, a sequência aleatória de números depende do valor da semente. Uma vez que sabemos o valor da semente, podemos prever qual será a sequência. Além disso, existem outros métodos para gerar números aleatórios. As pessoas agora estão usando alguns métodos para gerar números aleatórios verdadeiros, como o tempo de movimento da cabeça do disco e outros métodos físicos que podem ser incorporados ao computador. Consulte: http://en.wikipedia.org/wiki/Random_number_generation#Generation_methods

pelo método fornecido, como você disse
Math.random () em Java
Randomize; Aleatório (n); em Delphi

você pode implementar sua própria estrutura e lógica para gerar números aleatórios,
onde esse "algoritmo" pode ser executado de acordo com as especificações fornecidas para obter melhores resultados aleatórios.
e construir sobre isso a lógica.

Obrigado.

outras respostas são boas, aqui estão alguns outros ângulos sobre essa questão muito importante / involuntariamente profunda. cientistas da computação estudam a aleatoriedade há décadas e provavelmente continuarão a estudá-la. ele tem muitas conexões profundas e as principais questões em aberto restantes em todo o campo. Aqui estão algumas dicas.

• "aleatoriedade verdadeira / real" ocorre com processos físicos de baixo nível e "ruído", como em diodos zener, mecânica quântica etc., que podem ser aproveitados em RNGs baseados em hardware

• outros números gerados no domínio do computador é o que é conhecido como "pseudo-aleatório", que é simulado e nunca pode corresponder à "verdadeira aleatoriedade". estes são os chamados PRNGs

• existe um sentido importante de "dureza criptográfica de geradores de números aleatórios" que, em certo sentido, mede sua "qualidade" ou "segurança", ver, por exemplo, PRNG criptograficamente seguro . basicamente, um gerador "fraco" não tem tanta complexidade computacional quanto um gerador "rígido" e um gerador "fraco" é mais fácil de quebrar.

• outro sentido um tanto relacionado é a "dureza das provas". imagine uma prova para provar que um RNG é um tempo linear . essa prova parece ser mais simples do que a necessária para provar que é quadrática e assim por diante. esse conceito ainda está em processo de formalização / pesquisa, mas na verdade colide com questões profundas, como P NP, em um artigo famoso chamado Natural Proofs . aproximadamente, os autores mostram que uma prova de P NP deve ter uma certa "complexidade"; caso contrário, a mesma técnica de análise pode ser usada para quebrar PRNGs e, além disso, surpreendentemente, a maioria ou talvez todas as separações / técnicas de classes de complexidade conhecidas nessa data ( ou possivelmente atéS ( n 2 ) ? =$O(n)$$O(n^2)$$\stackrel{?}{=}$$\neq$até o momento ) não têm complexidade suficiente.

• Um importante tópico de pesquisa no TCS são algoritmos aleatórios e desa randômicos . a idéia é, grosso modo, estudar o quanto o algoritmo é alterado substituindo a "aleatoriedade verdadeira" por um PRNG e existem vários teoremas profundos sobre o assunto. aqui está uma questão cstheory.se de alto nível que dá uma amostra da pesquisa nesta área: algoritmos aleatórios eficientes e simples, nos quais o determinismo é difícil

• Outro tópico importante relacionado ao TCS é a entropia da informação - originalmente introduzida na física há muito tempo - que estuda um conceito intimamente relacionado de "desorganização da informação" e, como outros conceitos importantes no (T) CS, parece ser uma das idéias principais que atravessam No limite entre a análise aplicada e a teoria, até algumas das fórmulas são iguais .

• mais uma vez atestando o status da pesquisa ativa, há outras questões de alto nível no cstheory.se que se relacionam a essa questão. aqui está um close, quase o mesmo: é um gerador de números verdadeiramente aleatório Turing computável