Gerador de Números Aleatórios Sem Viés

De onde vêm os números

Os sorteios usam crypto.getRandomValues, o gerador criptograficamente seguro do navegador, que é alimentado com entropia coletada pelo sistema operacional e projetado para que observar a saída não diga nada útil sobre o que vem a seguir.

A alternativa óbvia, Math.random, é outra coisa. É um gerador pseudoaleatório rápido - normalmente xorshift128+ - feito para velocidade, iniciado a partir de algo como o estado do relógio e com estado interno pequeno o bastante para que um punhado de saídas possa ser suficiente para recuperá-lo e prever o resto. A especificação ECMAScript diz com todas as letras que ele não deve ser usado para fins criptográficos.

Para escolher o ganhador de uma rifa a diferença raramente importa. Ela é usada aqui mesmo assim porque não custa nada, e porque um gerador que só às vezes é confiável é mais difícil de avaliar do que um que sempre é.

Viés do módulo

O jeito simples de encaixar um valor aleatório num intervalo é tirar o resto da divisão pelo tamanho do intervalo, e isso fica sutilmente errado sempre que o intervalo não divide exatamente a faixa do gerador.

Pegue um byte aleatório, de 0 a 255, e peça um número de 1 a 10. Há 256 bytes possíveis e 10 respostas possíveis, e 256 não é múltiplo de 10. Seis das dez respostas recebem 26 bytes cada e as outras quatro recebem 25, então as seis primeiras saem cerca de quatro por cento mais vezes que as demais. Num intervalo de 1 a 100 a distorção é maior; de 1 a 200, maior ainda.

A correção é a amostragem por rejeição: calcule quantos valores no topo da faixa do gerador causariam o desequilíbrio, descarte qualquer sorteio que caia ali e tente de novo. Aqui, isso significa que valores acima do maior múltiplo exato do intervalo são jogados fora em vez de dobrados para dentro. Custa um sorteio extra de vez em quando e deixa todo número do intervalo com exatamente a mesma probabilidade. A mesma rotina está por trás dos geradores de senha e de UUID deste site.

Sorteando sem repetição

O modo sem repetição faz amostragem sem reposição, que é o que você quer para números de loteria, sorteios de prêmios e para escolher um subconjunto aleatório de uma lista. Depois que um valor sai, ele é retirado do conjunto, então nenhum número aparece duas vezes num mesmo resultado.

Isso exige que o intervalo tenha pelo menos tantos valores quanto você pediu - seis números únicos não podem sair de um intervalo de quatro -, e a ferramenta avisa isso em vez de ficar em loop para sempre. Repare que isso restringe o conjunto, não a ordem: os números continuam sendo sorteados numa sequência aleatória, então o resultado é um embaralhamento de um subconjunto aleatório, e não uma amostra ordenada. A ordenação está disponível separadamente quando você quer o resultado em ordem.

Para o que isto não serve

É uma boa ferramenta para rifas, dados, dados de teste, escolher qual tarefa fazer primeiro e qualquer uma das cem pequenas decisões que as pessoas deixam para o acaso.

Não é a ferramenta para gerar uma chave, uma senha ou um token - não porque a aleatoriedade seja insuficiente, mas porque essas coisas precisam de comprimento e alfabeto específicos; use o gerador de senhas para isso. Também não serve para um sorteio público em que os participantes precisam confiar no resultado: um número que aparece numa página não prova nada para quem não o viu aparecer, e um sorteio verificável precisa de uma semente publicada e de um compromisso feito antes do sorteio, o que é um projeto totalmente diferente.

Pseudoaleatório, criptográfico e verdadeiramente aleatório

Um gerador pseudoaleatório é uma função determinística: dado o mesmo estado inicial, ele produz a mesma sequência para sempre. Isso é uma vantagem em simulações, em que a reprodutibilidade importa, e um risco onde alguém possa tentar prever o próximo valor. O Math.random do JavaScript costuma ser xorshift128+, rápido e com um estado interno pequeno que pode ser reconstruído a partir de um punhado de saídas.

Um gerador criptograficamente seguro é construído de modo que observar qualquer quantidade de saída não revele nada de útil sobre o restante. Ele é semeado com a entropia que o sistema operacional coleta - variações de tempo, padrões de interrupção, instruções de hardware como RDRAND - e é ressemeado periodicamente. crypto.getRandomValues no navegador e /dev/urandom no Unix são as interfaces usuais, e ambas são rápidas o bastante para que a segurança saia praticamente de graça.

A aleatoriedade verdadeira, vinda de uma fonte física como ruído térmico ou decaimento radioativo, existe em módulos de hardware e em serviços como o random.org. Para quase todo propósito ela é desnecessária: um gerador criptográfico bem semeado é indistinguível dela em qualquer teste que alguém consiga rodar.

Embaralhar uma lista sem enviesá-la

O embaralhamento intuitivo - ordenar com um comparador aleatório - está errado, e errado de um jeito que passa por uma inspeção superficial. Ordenações por comparação pressupõem uma ordem consistente, então um comparador aleatório produz distribuições que favorecem pesadamente algumas permutações, e o resultado muda conforme a implementação da ordenação. Parece embaralhado e não está.

O algoritmo correto é o Fisher-Yates: percorra a lista de trás para frente e, para cada posição, sorteie um índice entre zero e essa posição, inclusive, e troque os dois elementos. Toda permutação fica igualmente provável e o custo é linear. Quase toda biblioteca padrão de linguagem traz uma implementação correta; onde não traz, o laço ocupa quatro linhas.

Selecionar um subconjunto é a mesma operação interrompida cedo: embaralhe as primeiras k posições e fique com elas. Sortear índices aleatórios e descartar os repetidos também funciona, mas degrada muito quando k se aproxima do tamanho da lista, que é justamente o ponto em que a maioria das implementações improvisadas começa a girar em falso por um tempo perceptível.

Como uma sequência aleatória realmente se parece

As pessoas julgam mal a aleatoriedade, e o erro vai sempre na mesma direção: dados realmente aleatórios contêm muito mais aglomerações do que a intuição admite. Em cem lançamentos de moeda, uma sequência de seis ou sete caras é provável, não suspeita, e é a sequência sem nenhuma corrida longa que provavelmente foi inventada.

É por isso que o modo aleatório dos serviços de streaming de música quase nunca é aleatório de fato. Um embaralhamento verdadeiro toca o mesmo artista três vezes seguidas com frequência suficiente para que os usuários relatem isso como defeito, então os algoritmos espalham os artistas de propósito - menos aleatório, mais parecido com o que as pessoas querem dizer com embaralhar.

Vale resistir a duas intuições relacionadas: a falácia do apostador, que espera que um resultado esteja na hora de sair depois de uma sequência do resultado oposto, e o efeito aniversário, que torna coincidências muito mais prováveis do que se imagina - com vinte e três pessoas, a chance de duas fazerem aniversário no mesmo dia já é de cinquenta por cento. As duas vêm do mesmo erro de avaliação sobre o quanto o acaso se agrupa.

Quando você quer os mesmos números toda vez

Simulações, conteúdo gerado proceduralmente e trabalho estatístico precisam de reprodutibilidade: a mesma semente produzindo a mesma sequência, para que um resultado possa ser reexaminado e um bug, reconstruído. Um gerador criptográfico é exatamente a ferramenta errada aí, porque não é possível semeá-lo de propósito.

A abordagem usual é um gerador pseudoaleatório pequeno e bem testado - PCG, xoshiro ou o Mersenne Twister em código mais antigo - semeado explicitamente e registrado em log. Em testes, imprimir a semente quando algo falha transforma uma falha intermitente em uma falha reproduzível, que é a diferença entre um bug que é corrigido e um teste que alguém desativa.

Mantenha os dois geradores separados e nunca deixe um gerador semeado vazar para código sensível à segurança. O padrão que causa problema é uma função utilitária usada tanto para embaralhar dados de teste quanto para gerar tokens; a partir daí, uma sequência determinística passa a proteger algo que não deveria.

Um sorteio que as pessoas aceitem como justo

A justiça tem duas partes: o mecanismo e a evidência. O mecanismo aqui é sólido - uma fonte criptográfica com amostragem por rejeição, de modo que todo valor do intervalo é igualmente provável. A evidência é o que uma página não consegue fornecer, porque um número aparecendo numa tela não prova nada para quem não estava olhando.

Quando há dinheiro ou obrigações em jogo, a construção padrão é o commit-and-reveal: publique um hash da lista de participantes e da semente antes de as inscrições fecharem, faça o sorteio depois por um método público e divulgue a semente para que qualquer pessoa possa recalcular o resultado. Isso troca a confiança no organizador por uma conta que qualquer um pode conferir.

Para os casos do dia a dia - quem apresenta primeiro, por qual tarefa começar, quem fica com o último ingresso - nada disso é necessário. A justiça que importa aí é que todo mundo na sala veja o mesmo resultado surgir ao mesmo tempo, e é por isso que um sorteio visível vale mais do que um número que alguém lê na própria tela.