Por que estou obtendo resultados desiguais ao usar $ RANDOM?

14

Eu li sobre RNGs na Wikipedia e $RANDOMfunção no TLDP, mas isso realmente não explica esse resultado:

$ max=$((6*3600))
$ for f in {1..100000}; do echo $(($RANDOM%max/3600)); done | sort | uniq -c
  21787 0
  22114 1
  21933 2
  12157 3
  10938 4
  11071 5

Por que os valores acima são cerca de 2x mais inclinados a serem 0, 1, 2 do que 3, 4, 5, mas quando altero o módulo máximo, eles estão quase igualmente distribuídos pelos 10 valores?

$ max=$((9*3600))
$ for f in {1..100000}; do echo $(($RANDOM%max/3600)); done | sort | uniq -c
  11940 0
  11199 1
  10898 2
  10945 3
  11239 4
  10928 5
  10875 6
  10759 7
  11217 8
cprn
fonte
9
A resposta usual para isso é rolar novamente (descartar o número que você recebeu e escolher outro) se você estiver entre o valor máximo de RANDOM e o valor mais alto possível que pode ser dividido uniformemente em seu módulo. Isso não é usual para RANDOM, é comum usar domínio de módulo para restringir-RNG em todos os idiomas / ferramentas / etc. implementação de RNGs desse tipo.
Charles Duffy
7
Veja meu artigo 2013, sobre a origem deste viés se você quiser alguns bons gráficos de quão ruim ele fica: ericlippert.com/2013/12/16/...
Eric Lippert
1
"A geração de números aleatórios é importante demais para ser deixada ao acaso". Robert Coveyou. FYI embora: a maioria dos programas são incapazes de gerar números verdadeiramente aleatórios
jesse_b
@ Eric Lippert obrigado, vou ler com prazer!
Cprn 06/07/19
1
Observe que, mesmo tendo problemas devido ao viés do módulo, a $RANDOMvariável não usa um bom PRNG internamente.
forest

Respostas:

36

Para expandir o tópico de desvio de módulo, sua fórmula é:

max=$((6*3600))
$(($RANDOM%max/3600))

E nesta fórmula, $RANDOMé um valor aleatório no intervalo de 0 a 32767.

   RANDOM Each time this parameter is referenced, a random integer between
          0 and 32767 is generated.

Ajuda a visualizar como isso é mapeado para possíveis valores:

0 = 0-3599
1 = 3600-7199
2 = 7200-10799
3 = 10800-14399
4 = 14400-17999
5 = 18000-21599
0 = 21600-25199
1 = 25200-28799
2 = 28800-32399
3 = 32400-32767

Portanto, em sua fórmula, a probabilidade de 0, 1, 2 é duas vezes a de 4, 5. E a probabilidade de 3 também é um pouco maior que 4, 5. Daí o seu resultado com 0, 1, 2 como vencedores e 4, 5 como perdedores.

Ao mudar para 9*3600, acontece como:

0 = 0-3599
1 = 3600-7199
2 = 7200-10799
3 = 10800-14399
4 = 14400-17999
5 = 18000-21599
6 = 21600-25199
7 = 25200-28799
8 = 28800-32399
0 = 32400-32767

1 a 8 têm a mesma probabilidade, mas ainda há um leve viés para 0 e, portanto, 0 ainda foi o vencedor em seu teste com 100'000 iterações.

Para corrigir o viés do módulo, você deve primeiro simplificar a fórmula (se você quiser apenas 0-5, o módulo é 6, não 3600 ou número ainda mais louco, não faz sentido). Somente essa simplificação reduzirá muito seu viés (32766 mapeia para 0, 32767 para 1, dando um pequeno viés para esses dois números).

Para se livrar completamente da polarização, é necessário relançar (por exemplo) quando $RANDOMfor menor que 32768 % 6(eliminar os estados que não são mapeados perfeitamente para o intervalo aleatório disponível).

max=6
for f in {1..100000}
do
    r=$RANDOM
    while [ $r -lt $((32768 % $max)) ]; do r=$RANDOM; done
    echo $(($r%max))
done | sort | uniq -c | sort -n

Resultado do teste:

  16425 5
  16515 1
  16720 0
  16769 2
  16776 4
  16795 3

A alternativa seria usar uma fonte aleatória diferente que não tenha um viés perceptível (ordens de magnitude maiores que apenas 32768 valores possíveis). Mas implementar uma lógica de relançamento de qualquer maneira não é prejudicial (mesmo que provavelmente nunca aconteça).

frostschutz
fonte
Sua resposta está amplamente correta, exceto: "você precisa relançar quando $ RANDOM for menor que 32768% 6" deve ser "igual ou maior que o piso ((RANDMAX + 1) / 6) * 6" (ex. 32766 ) e corrija o código do shell associado abaixo disso.
Nayuki 6/07/19
@Nayuki, se você puder apontar um erro específico (que se aplica dentro do contexto especificado), será um prazer corrigi-lo. Minha solução é apenas um exemplo, existem diferentes maneiras de fazer isso. Você pode remover o viés do intervalo inicial ou final, ou em algum lugar no meio, não faz diferença. Você pode calculá-lo melhor (e não fazer um módulo em todas as iterações). Você pode lidar com casos especiais, como módulos arbitrários e valores de randmax, também manipular RANDMAX = INTMAX, onde RANDMAX + 1 não existe, mas esse não era o foco aqui.
frostschutz 6/07/19
Sua resposta é significativamente pior que sua postagem. Antes de tudo, apontei especificamente qual frase sua está factualmente errada. Observe que "32768% 6" == 2, então você deseja rolar novamente toda vez que $ RANDOM <2? Com relação ao viés no início / fim / meio do intervalo, toda a postagem é sobre como remover o viés no final do intervalo, e minha resposta também é exatamente isso. Terceiro, você fala sobre como manipular RANDMAX = INTMAX, mas em sua resposta mencionou o valor 32768 (= 32767 + 1) várias vezes, o que implica que você está confortável com a computação RANDMAX + 1.
Nayuki 06/07/19
1
@Nayuki meu código remove 0 e 1, o seu remove 32766 e 32767 e eu gostaria que você elaborasse: que diferença faz? Eu sou apenas humano, eu cometo erros, mas tudo o que você disse até agora é "está errado" sem explicar ou mostrar o porquê. Obrigado.
Frostschutz 06/07/19
1
Não importa, descobri. Desculpe pelo alarme falso.
Nayuki 6/07/19
23

Isso é parcialidade do módulo. Se RANDOMfor bem construído, cada valor entre 0 e 32767 é produzido com igual probabilidade. Ao usar o módulo, você altera as probabilidades: as probabilidades de todos os valores acima do módulo são adicionadas aos valores para os quais são mapeados.

No seu exemplo, 6 × 3600 é aproximadamente dois terços do intervalo de valores. As probabilidades do terço superior são, portanto, adicionadas às do terço inferior, o que significa que valores de 0 a 2 (aproximadamente) são duas vezes mais prováveis ​​de serem produzidos do que valores de 3 a 5. 9 × 3600 é quase 32767, portanto, o o viés do módulo é muito menor e afeta apenas valores de 32400 a 32767.

Para responder à sua pergunta principal, pelo menos no Bash, a sequência aleatória é totalmente previsível se você conhece a semente. Veja intrand32em variables.c.

Stephen Kitt
fonte