Introdução a aleatoriedade e números randômicos

O RANDOM.ORG é um verdadeiro gerador de números aleatórios que gera aleatoriedade através de ruído atmosférico. Esta página explica por que é tão difícil (e interessante) fazer um computador gerar números realmente aleatórios.

Números aleatórios são úteis para diversos objetivos, como gerar chaves de criptografia, simular fenômenos complexos e selecionar amostras randômicas a partir de grandes bancos de dados. Também podem ser usados com finalidades estéticas, como em música ou literatura, e são, é claro, bastante difundidos em jogos e apostas.

Quando se trata de números simples, um número aleatório é aquele que é retirado de um conjunto de valores possíveis, sendo cada um igualmente provável – isto é, uma distribuição uniforme. Quando se trata de uma sequência de números randômicos, cada número sorteado deve ser estatisticamente independente dos outros.

Com o advento dos computadores, os programadores reconheceram a necessidade de criar meios de inserir aleatoriedade nos programas.

Contudo, por incrível que pareça, é difícil fazer um computador agir de maneira aleatória. Um computador segue suas instruções cegamente: é, portanto, inteiramente previsível. (Um computador que não segue suas instruções neste sentido está quebrado). Há duas maneiras principais de gerar números randômicos usando computadores: Geradores de Números Pseudoaleatórios (PRNGs) e Verdadeiros Geradores de Números Aleatórios (TRNGs).

Geradores de números pseudoaleatórios (PRNGs)

Como o prefixo “pseudo” sugere, números pseudoaleatórios não são tão randômicos quanto você poderia imaginar, caso esteja acostumado a jogar dados ou na loteria. Essencialmente, PRNGs são algoritmos que usam fórmulas matemáticas, ou simplesmente tabelas pré-calculadas, para produzir sequências de números que parecem ser aleatórios. Um bom exemplo de PRNG é o método congruente linear. Muita pesquisa já foi feita sobre teoria dos números pseudoaleatórios, e os algoritmos atuais para gerá-los são tão bons que os resultados de fato aparentam ser verdadeiramente randômicos.

A principal diferença entre PRNGs e TRNGs é fácil de entender, se você comparar números aleatórios gerados por computador com um lançamento de dados ao acaso. Como os PRNGs geram os números através de fórmulas matemáticas e listas pré-calculadas, usá-los equivale a jogar um dado várias vezes e anotar os resultados. Sempre que você solicitar um lançamento de dado ao programa, ele vai mostrar o próximo número da lista.

Com efeito, os números parecem ser aleatórios, mas na verdade são pré-determinados. Já os TRNGs fazem um computador efetivamente jogar um dado no ar – ou, mais comumente, usar algum fenômeno físico que seja mais facilmente conectável à máquina.

PRNGs são eficientes, no sentido de que podem gerar muitos números em curtos períodos de tempo, e determinísticos, no sentido de que uma certa sequência de números pode ser reproduzida posteriormente, se o ponto inicial for conhecido. Eficiência é uma boa característica se você precisa de muitos números, e determinismo é útil se você precisa reproduzir uma mesma sequência em um momento posterior.

PRNGs também são periódicos, isto é, as sequências eventualmente irão se repetir. Periodicidade não é algo desejável neste caso, mas os PRNGs atuais trabalham com intervalos tão longos que essa característica pode ser ignorada para usos práticos.

Com tais propriedades, os PRNGs são adequados para usos que demandem muitos números, bem como em casos nos quais é útil que uma mesma sequência possa ser repetida com facilidade. Exemplos conhecidos de tais usos são aplicativos de simulações e de criação de modelos. PRNGs não são indicados para casos em que os números precisam ser realmente imprevisíveis, como criptografia de dados ou jogos de azar.

É importante observar que, embora bons algoritmos de PRNG existam, eles não são sempre utilizados – e podem trazer surpresas pouco agradáveis. Tomemos como exemplo a bem difundida linguagem de programação PHP.

Se você usar PHP para GNU/Linux, provavelmente vai ficar plenamente satisfeito com seus números aleatórios. Contudo, se você usar PHP para Microsoft Windows, provavelmente notará que seus números aleatórios não são tão bons, conforme mostrado nesta análise visual de 2008.

Outro exemplo ocorreu em 2002, quando um pesquisador relatou que o PRNG no MacOS não era bom o suficiente para simulações científicas de infecções virais. Ou seja: mesmo se um PRNG for suficiente para as suas necessidades, ainda assim é preciso ter cuidado acerca de qual gerador utilizar.

Verdadeiros Geradores de Números Aleatórios (TRNGs)

Diferente dos PRNGs, os TRNGs extraem aleatoriedade de fenômenos físicos. Você pode imaginar um dado (daqueles utilizados em jogos) conectado a um computador, mas normalmente se usam fenômenos que oferecem maior facilidade para estabelecer uma conexão com a máquina.

Em tese, o fenômeno pode ser bastante simples, como as pequenas variações nos movimentos do mouse ou os intervalos de tempo entre os toques do teclado. Mas é preciso ter cuidado sobre que tipo de fenômeno utilizar.

Por exemplo, pode ser problemático usar toques no teclado com esse objetivo, porque as máquinas com frequência têm buffers, o que significa que muitos toques são absorvidos antes que sejam enviados aos seus programas de destino. Para um programa que esteja aguardando toques no teclado, vai parecer que as teclas foram pressionadas quase simultaneamente – e no fim das contas pode ser que nenhuma aleatoriedade seja gerada.

Contudo, há muitas outras maneiras de se obter verdadeira aleatoriedade utilizando um computador. Um fenômeno físico muito bom para isso é uma fonte radioativa. Os momentos em que uma fonte radioativa enfraquece são completamente imprevisíveis, e podem ser facilmente detectados e inseridos em um computador, evitando a interferência de mecanismos de buffer. O HotBits, da Fourmilab, na Suíca, é um excelente exemplo de gerador de números aleatórios que usa essa técnica. Outro fenômeno físico conveniente é o ruído atmosférico, bastante fácil de ser captado com um rádio comum.

O RANDOM.ORG funciona assim. Ruídos de fundo em ambientes como escritórios ou laboratórios também poderiam ser utilizados, mas nesse caso seria preciso ter cuidado com eventuais padrões. O ventilador do computador, por exemplo, pode contribuir para o ruído de fundo do ambiente – e como se trata de um dispositivo rotativo, provavelmente o som não será tão aleatório quanto o do ruído atmosférico.

Contanto que você seja cuidadoso, as possibilidades são infinitas. Sem dúvidas, o mecanismo com visual mais legal foi o do Lavarand, da Silicon Graphics, que usava lâmpadas de lava para gerar números aleatórios. Infelizmente, o Lavarand não funciona mais em sua forma original, mas um de seus inventores está dando continuidade ao projeto – sem as lâmpadas de lava – no site LavaRnd.

Outro mecanismo é o do Java EntropyPool, que reúne bits randômicos de várias fontes diferentes, incluindo o HotBits e o RANDOM.ORG, mas também de hits de páginas recebidos pelo próprio servidor do EntropyPool.

Independentemente do fenômeno físico utilizado, o processo de geração de verdadeiros números aleatórios identifica mudanças sutis e imprevisíveis nos dados. Por exemplo, o HotBits usa pequenas variações nos intervalos entre ocorrências de enfraquecimento de uma fonte radioativa, enquanto o RANDOM.ORG usa pequenas variações na amplitude do ruído atmosférico.

Comparação entre PRNGs e TRNGs

A tabela abaixo resume as características dos dois tipos de geradores de números aleatórios.

Assim, os TRNGs são adequados para usos como criptografia de dados, jogos e apostas. Por outro lado, como apresentam pouca eficiência e não são determinísticos, os TRNGs não são indicados para simulações ou criação de modelos, que geralmente necessitam de mais dados do que um TRNG pode gerar. A tabela abaixo mostra que tipo de gerador é mais adequado para alguns dos usos mais comuns.

Eventos Quânticos ou Sistemas Caóticos?

Os criadores de TRNGs às vezes discutem se os fenômenos físicos utilizados são fenômenos quânticos ou têm comportamento caótico. Não há consenso sobre se os fenômenos quânticos são melhores ou não, e curiosamente tudo desemboca em nossas convicções sobre como o universo funciona. A questão central é se o universo é determinístico ou não, isto é, se tudo que acontece é essencialmente predeterminado desde o Big Bang.

Determinismo é um assunto difícil, abordado em diversas investigações filosóficas, e o problema está longe de ser tão simples quanto você talvez imagine. Vou tentar explicar aqui, mas também gostaria de observar que o Wikipedia traz uma apresentação concisa do debate.

A mecânica quântica é um braço da física teórica que descreve matematicamente o universo nos níveis atômico e subatômico. Geradores de números aleatórios baseados em física quântica usam o fato de que partículas subatômicas aparentam se comportar de maneira aleatória em certas circunstâncias. Não há qualquer causa conhecida por trás de tais eventos, portanto muitos acreditam que não sejam determinísticos.

Já os sistemas caóticos são aqueles em que pequenas mudanças nas condições iniciais podem resultar em alterações dramáticas no comportamento global do sistema.

Eventos climáticos são um bom exemplo disso – e você já deve ter ouvido falar no efeito borboleta, um experimento mental em que uma borboleta batendo as asas no Brasil pode ser capaz de afetar os ventos de maneira sutil, mas crítica, de modo que acabe causando um tornado no Texas.

Os defensores da hipótese quântica na geração de números aleatórios sustentam que a física quântica é inerentemente não determinística, enquanto os sistemas governados pela física são essencialmente determinísticos.

Particularmente, eu ainda não decidi em que ponto me situo na escala entre determinismo e não determinismo, mas, em nome do debate, vou vestir minha camisa determinística e usar o RANDOM.ORG como exemplo. Você poderia dizer que o ruído atmosférico pode ser compreendido como um sistema caótico, mas determinístico. Sendo assim, se você soubesse o suficiente acerca dos processos que causam o ruído atmosférico, como as trovoadas, você poderia, em tese, prever os números gerados pelo RANDOM.ORG.

No entanto, para fazer isso, você provavelmente precisaria de conhecimentos sobre as posições e velocidades de todas as moléculas do sistema climático planetário. É algo claramente impraticável, e as imprecisões nas previsões do tempo mostram como é difícil fazer uma estimativa do comportamento dos sistemas climáticos.

Por isso, é inviável prever números aleatórios do RANDOM.ORG, mesmo para um determinístico. Uma explicação similar (numa escala diferente) poderia servir para os números aleatórios geradas nas lâmpadas de lava.

Já que existe controvérsia sobre a conveniência de fenômenos caóticos na geração de aleatoriedade, você pode estar se perguntando: por que não ficar logo com a física quântica? Pareceria uma aposta segura. Contudo, geradores quânticos também não estão a salvo de críticas.

Deterministas extremos dirão que o comportamento de uma partícula subatômica é tão predeterminado quanto tudo mais no universo, desde o Big Bang. Nós apenas pensamos que essas partículas específicas se comportam de maneira aleatória porque nenhuma forma de mensuração humana conseguiu encontrar uma explicação.

Nessa perspectiva, os eventos subatômicos têm uma causa, mas nós ainda não a compreendemos, por isso tais eventos parecem aleatórios aos nossos olhos. Para um determinista extremo, física quântica é tão conveniente para gerar números aleatórios quanto ruído atmosférico ou lâmpadas de lava.

Este é apenas um argumento possível, e há muitos outros. No fim das contas, acho que a melhor e mais significativa definição de aleatoriedade reside no que não pode ser previsto por humanos.

Se a aleatoriedade se origina de sistemas climáticos imprevisíveis, lâmpadas de lava ou eventos subatômicos, é algo amplamente acadêmico. Enquanto geradores quânticos de números aleatórios podem certamente gerar números verdadeiramente aleatórios, tenho a impressão de que são equivalentes às abordagens baseadas em sistemas dinâmicos complexos.

Sugestões de Leitura

Algumas referências interessantes sobre aleatoriedade. Se você tiver qualquer sugestão, por favor, mande-nos um email.

Can You Behave Randomly? (Você consegue se comportar aleatoriamente?)

Alguns exercícios formulados pelo Dr. Christopher Wetzel, que têm objetivo de ajudá-lo a compreender melhor a aleatoriedade ao tentar fazer com que você se comporte de maneira aleatória – algo surpreendentemente difícil para os humanos.

Introduction to Probability and Statistics (Introdução a Probabilidade e Estatística)

Uma excelente pequena introdução ao tema por John Walker, altamente recomendado.

Exploring RANDOMNESS (Explorando a Aleatoriedade)

Um livro do Prof. Gregory J. CHaitin sobre teoria da informação algorítimica.