Como funciona a seleção aleatória ponderada

A seleção aleatória ponderada é o que você usa quando as opções não devem ter probabilidades iguais. Os pesos informam com que frequência cada opção deve vencer, em média.

Principais conclusões

Probabilidade = peso dividido pelo peso total.
Os pesos cumulativos transformam as opções em segmentos do intervalo de 0 a 1.
Um valor aleatório seguro escolhe um ponto; o segmento correspondente vence.
Ponderado sem reposição retira o vencedor e renormaliza os pesos restantes.
Teste a imparcialidade comparando as frequências observadas e esperadas em muitos sorteios.

Aleatoriedade igual versus ponderada

Um selecionador aleatório comum trata todas as opções igualmente. Isso é correto para um sorteio em sala de aula onde cada aluno deve ter a mesma chance. Mas muitas decisões reais são deliberadamente desiguais:

Um jogo deseja que o saque comum apareça com frequência e o saque raro apareça raramente.
Um sorteio dá a alguns participantes mais ingressos do que a outros.
Um teste A/B envia 80% dos usuários para a variante de controle e 20% para a nova.
Um professor deseja que as perguntas difíceis apareçam com mais frequência do que as fáceis.

A aleatoriedade ponderada ainda é aleatoriedade. A diferença é que a distribuição de probabilidade é intencional.

Pesos são probabilidades, não contagens

O peso de uma opção não é em si uma probabilidade. É um número relativo. Para obter uma probabilidade, divida o peso pela soma de todos os pesos.

Suponha que as opções sejam:

-A, peso 1.

B, peso 2.
C, peso 7.

O peso total é 10, então as probabilidades são 10%, 20% e 70%. Se empatar 100 vezes, C deverá ganhar cerca de 70 vezes. Se você empatar apenas 10 vezes, C poderá ganhar 4, 6 ou até 0 vezes. Amostras pequenas são barulhentas; os pesos descrevem a expectativa de longo prazo.

A distribuição cumulativa

A distribuição cumulativa transforma esses pesos em segmentos do intervalo de 0 a 1. Com o mesmo exemplo:

A cobre 0,00 a 0,10.
B cobre 0,10 a 0,30.
C abrange 0,30 a 1,00.

A largura de cada segmento é a probabilidade da opção. Os segmentos não se sobrepõem e juntos cobrem todo o intervalo.

É por isso que a seleção ponderada não precisa de uma probabilidade separada para cada opção. Você só precisa dos pesos e do total deles.

Amostragem por transformada inversa

A amostragem por transformada inversa é a maneira padrão de selecionar essa distribuição:

Calcule o peso total.
Escolha um valor aleatório entre 0 e o total.
Percorra as opções, somando cada peso a um total de corrida.
Pare na primeira opção cujo peso cumulativo seja maior ou igual ao valor aleatório.

A opção selecionada é a vencedora. Se o valor aleatório cair no segmento de A, A vence. Se cair no segmento de C, C vence.

O algoritmo leva O(n) tempo por sorteio, onde n é o número de opções. É simples, correto e mais do que rápido o suficiente para uma página com algumas dezenas de opções.

Com e sem reposição

Com reposição, cada sorteio é independente. A mesma opção pode ganhar mais de uma vez. Este é o modelo certo quando cada sorteio deve usar as probabilidades originais.

Sem substituição, uma opção selecionada é removida do conjunto. Os pesos restantes são renormalizados antes do próximo sorteio. Se A for removido, o total restante será menor, então B e C receberão parcelas maiores no próximo sorteio.

Sem reposição não há embaralhamento. Não produz todas as permutações com igual probabilidade. Produz um pedido ponderado: opções com pesos maiores tendem a aparecer mais cedo.

O método alias para seleções de alto volume

Para um grande número de sorteios ou conjuntos de opções muito grandes, existe uma alternativa mais rápida chamada método alias. Ele constrói uma tabela de consulta uma vez e depois responde a cada sorteio em tempo constante.

O método alias é útil em jogos e simulações que precisam de milhões de escolhas. Para uma ferramenta de navegador com uma lista pequena, a amostragem cumulativa por transformada inversa é mais simples e perfeitamente adequada.

Erros comuns

Os pesos são fáceis de errar. Fique atento a estes erros:

Tratar um peso de 70 como 70% quando os demais pesos não são zero. É apenas 70% se os outros pesos somarem 30 ou menos.
Permitir pesos zero ou negativos. Opções de peso zero nunca podem vencer. Pesos negativos tornam a distribuição sem sentido.
Usar Math.random() para um sorteio que precisa ser imprevisível.
Usando um mapeamento tendencioso para transformar valores aleatórios em segmentos.
Julgar a justiça em dez ou vinte empates. Amostras pequenas podem parecer muito diferentes da distribuição esperada.

Outro erro comum é confundir ponderação com embaralhamento. Se você precisar de todas as permutações igualmente prováveis, embaralhe a lista. Se você precisar de uma primeira escolha ponderada, use um sorteio ponderado.

Como verificar um empate ponderado

Compare frequências esperadas e observadas. Com pesos 1, 2 e 7, as probabilidades esperadas são 10%, 20% e 70%. Ao longo de milhares de sorteios, as proporções observadas devem aproximar-se desses números.

Não interprete exageradamente uma pequena amostra. Um empate justo pode produzir uma sequência surpreendente. O que importa é se as frequências observadas convergem à medida que a amostra cresce e se a implementação é documentada.

Para um sorteio público ponderado, registre as opções, pesos e resultado. Isso torna o sorteio auditável mesmo que você nunca publique o código.

Como este site implementa ponderação aleatória

O seletor ponderado neste site usa pesos cumulativos e um valor aleatório criptograficamente seguro. A visualização da probabilidade mostra a distribuição normalizada antes de você desenhar. As opções são selecionadas com amostragem por transformada inversa e sorteios sem substituição removem a opção selecionada e renormalizam os pesos restantes.

Tudo é executado localmente no seu navegador. Suas opções, pesos e resultados não são carregados.

Resultado final

A aleatoriedade ponderada altera as probabilidades, não a fonte da aleatoriedade. Normalize os pesos, use um valor aleatório seguro e selecione o segmento cumulativo correspondente. Isso lhe dá probabilidades desiguais para mesas de saque, sorteios, testes A/B e atividades em sala de aula.