Início / unix / Perguntas / 528343
Accepted
cprn
Asked: 2019-07-05 01:10:13 +0800 CST

Por que estou obtendo resultados de distribuição desigual ao usar $RANDOM?

  • 772

Eu li sobre RNGs na Wikipedia e $RANDOMfunciono 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 eu mudo o módulo máximo, eles estão quase igualmente distribuídos por todos os 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
random

2 respostas

  1. Best Answer

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

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

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

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

    Isso ajuda a visualizar como isso mapeia para valores possíveis:

    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

    Então, na sua fórmula, a probabilidade de 0, 1, 2 é o dobro de 4, 5. E a probabilidade de 3 é ligeiramente maior que 4, 5 também. Daí seu resultado com 0, 1, 2 como vencedores e 4, 5 como perdedores.

    Ao mudar para 9*3600, fica assim:

    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-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, então o módulo é 6, não 3600 ou até mesmo um número mais louco, não faz sentido). Essa simplificação por si só 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 do viés, você precisa rolar novamente (por exemplo) quando $RANDOMfor menor que 32768 % 6(eliminar os estados que não mapeiam 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 viés perceptível (ordens de magnitude maiores que apenas 32.768 valores possíveis). Mas implementar uma lógica de re-rolagem de qualquer maneira não faz mal (mesmo que provavelmente nunca aconteça).

    • 37

  2. Este é o viés 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, então o A polarização 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ê conhecer a semente. Veja intrand32em variables.c.

    • 23

relate perguntas