Isso introduzirá um viés no que deve ser um número aleatório?

Suponha um arquivo de dados com mais de 80 milhões de zeros e zeros, gerado aleatoriamente.

A partir desse arquivo, queremos criar uma lista de números inteiros decimais aleatórios.

Este é o plano para fazer essa conversão.

Divida os 80 milhões de dígitos em agrupamentos de 4 dígitos binários.
Converta cada binário de 4 dígitos em decimal.
Descarte todos os valores decimais maiores que 9.

Isso deve resultar em uma sequência de números inteiros aleatórios de 0 a 9

Aqui está a preocupação. Os 24 dígitos binários que compreendem os 6 agrupamentos de 4 dígitos binários que correspondem aos valores 10 a 15 contêm 17 dígitos e apenas 7 zeros. Esse desequilíbrio afetará a distribuição de números pares x ímpares ou comprometerá a aleatoriedade da sequência final de dígitos decimais de alguma forma?

Atualização: a partir das respostas postadas, parece que o método enumerado acima é consistente. Eu concordo com essa conclusão. No entanto, ainda não entendo por que remover mais do que o dobro de zeros da cadeia binária não influencia o resultado em menos números ímpares. Eu procuro explicações.

monte-carlo random-generation randomness Joel W.
fonte

Existem métodos mais eficientes. Por exemplo, você pode particionar a sequência de bits em grupos de 10, convertê-los em suas representações de três dígitos na base 10 e descartar qualquer um com valores 1000 ou mais. Isso utilizaria 97,6% dos bits, em vez de apenas 62,5% deles. Você não pode fazer muito melhor que isso. (Você pode usar grupos de 681 e convertê-los para 205 dígitos de base-10 cordas, utilizando, assim, quase 99,7% dos bits.)

whuber

Respostas:

Vamos contar e ver. Pela construção do arquivo, todas as seqüências de 4 bits são igualmente prováveis. Existem 16 dessas strings. Aqui estão eles:

Seu procedimento lança as seqüências 10 a 15. Portanto, nos casos em que você realmente usa, você escolhe 0 a 9, cada um dos quais é igualmente provável, conforme desejado. E sabemos que os dígitos decimais gerados são independentes um do outro, porque cada um usa uma sequência separada de 4 bits e todos os bits são independentes. Seu procedimento constitui um tipo simples de amostragem por rejeição .

Kodiologist
fonte

Eu vejo essa lógica claramente. No entanto, estou preocupado em descartar mais 1s binários do que 0s. Por que esse desequilíbrio não tem nenhum impacto?

Joel W.

@ JoelW Acho que não vejo seu argumento. A distribuição final refere-se a dígitos decimais, não a bits, portanto a distribuição de bits é irrelevante.

Kodiologist

Isso está correto, mas aborda apenas parcialmente a questão. Para abordar a parte "comprometer a aleatoriedade ... de qualquer forma" da questão, é preciso também estabelecer que os dígitos decimais resultantes sejam, para uma excelente aproximação, independentes . Por uma questão de exaustividade, vale a pena dedicar uma frase de explicação a esse resultado (óbvio).

whuber

Joel, vejo de onde você vem. Pode haver uma percepção equivocada aqui: você não pode reverter o processo. Se você quisesse reconstruir um fluxo de bits a partir do fluxo de dígitos decimais, seria necessário excluir todos os 8 e 9 e converter os dígitos restantes em triplos binários. Isso restaurará o equilíbrio. De fato, é fácil ver que essa "ida e volta" equivale a dividir o fluxo original em nybbles de quatro bits e a descartar os bits mais significativos, deixando uma boa sequência uniformemente distribuída de 60 milhões de bits.

whuber

@whuber Fair bastante; adicionado.

Kodiologist

Não há viés, pois você simula alguns valores descartados e todos os valores, incluindo aqueles mantidos, são gerados com a mesma probabilidade:

O código R para o gráfico acima é

generza=matrix(sample(0:1,4*1e6,rep=TRUE),ncol=4)
uniz=generza[,1]+2*generza[,2]+4*generza[,3]+8*generza[,4]
barplot(hist(uniz[uniz<10],breaks=seq(-0.5,9.5,le=11))$counts,col="steelblue")

Xi'an
fonte