Por que a geração de 8 bits aleatórios é uniforme em (0, 255)?

35

Estou gerando 8 bits aleatórios (0 ou 1) e concatenando-os juntos para formar um número de 8 bits. Uma simulação simples de Python produz uma distribuição uniforme no conjunto discreto [0, 255].

Estou tentando justificar por que isso faz sentido na minha cabeça. Se eu comparar isso com o lançamento de 8 moedas, o valor esperado não estaria em torno de 4 caras / 4 caudas? Então, para mim, faz sentido que meus resultados reflitam um pico no meio do intervalo. Em outras palavras, por que uma sequência de 8 zeros ou 8 zeros parece ser tão provável quanto uma sequência de 4 e 4, ou 5 e 3, etc.? O que estou perdendo aqui?

vítreo
fonte
17
O valor esperado da distribuição de bits de maneira aleatória uniforme, o intervalo [0,255] também está em torno de 4 1/4 0.
user253751
2
Só porque você atribui um peso igual a cada número de 0 a 255, não significa que o resultado da função "diferença entre contagem de 1s e 0s" também ocorrerá uma vez e apenas uma vez. Eu poderia dar um peso igual a todas as pessoas da minha organização. Não significa que suas idades teriam o mesmo peso. Algumas idades podem ser muito mais comuns que outras. Mas uma pessoa não é mais comum que qualquer outra pessoa.
Brad Thomas
2
Pense desta maneira ... Seu primeiro bit aleatório determinará o valor do bit 7, um 1 vale 128 e um 0 vale 0. Dos 256 números, você tem 50% de chance de o número ser 0-127, se o valor o bit é 0 e 128-255 se o bit for 1. Digamos que seja 0, o próximo bit determina se o resultado será 0-63 ou 64-127. Todos os 8 bits são necessários para formar um dos 256 resultados igualmente prováveis. Você está pensando em adicionar totais como faria com os dados. As probabilidades de obter 4 1s e 4 0s são maiores do que obter 8 1s, mas existem mais maneiras de organizá-las para obter um resultado diferente.
precisa saber é o seguinte
2
Suponha que você jogue um dado de 256 lados com os números de 0 a 255. Você esperaria uma distribuição uniforme. Agora, suponha que você rotule novamente o dado para que um lado diga 0, 8 lados digam 1, 28 lados digam 2 e assim por diante; agora cada lado é rotulado com o número de bits no número que costumava estar naquele lado. Você joga o dado novamente; por que você esperaria obter uma distribuição uniforme dos números de 0 a 8?
Eric Lippert
Se a distribuição funcionasse assim, eu poderia ganhar muito dinheiro apostando na roleta somente depois que 7 vermelhos aparecerem seguidos. 7 e 1 é 8 vezes mais provável que 8 e 0! (ignorando zeros, mas essa inclinação supera em muito a zeros e 0)
Cruncher

Respostas:

61

TL; DR: O nítido contraste entre os bits e as moedas é que, no caso das moedas, você está ignorando a ordem dos resultados. O HHHHTTTT é tratado da mesma forma que o TTTTHHHH (ambos têm 4 cabeças e 4 caudas). Mas em bits, você se preocupa com a ordem (porque você precisa atribuir "pesos" às posições de bits para obter 256 resultados), portanto, 11110000 é diferente de 00001111.


Explicação mais longa: Esses conceitos podem ser mais precisamente unificados se formos um pouco mais formais na estruturação do problema. Considere um experimento como uma sequência de oito tentativas com resultados dicotômicos e probabilidade de "sucesso" 0,5 e "falha" 0,5, e as tentativas são independentes. Em geral, chamarei isso de sucessos, tentativas totais e falhas e a probabilidade de sucesso é .n n - k pknnkp

  • No exemplo da moeda, o resultado " heads, tails" ignora a ordem dos testes (4 cabeças são 4 cabeças, independentemente da ordem de ocorrência), e isso dá origem à sua observação de que 4 cabeças têm mais probabilidade de 0 ou 8 cabeças. Quatro cabeças são mais comuns porque existem muitas maneiras de fazer quatro cabeças (TTHHTTHH, ou HHTTHHTT, etc.) do que existe outro número (oito cabeças tem apenas uma sequência). O teorema binomial fornece o número de maneiras de fazer essas diferentes configurações.n - kknk

  • Por outro lado, a ordem é importante para os bits porque cada local tem um "peso" ou "valor do local" associado. Uma propriedade do coeficiente binomial é que , ou seja, se contarmos todas as diferentes seqüências ordenadas, obteremos . Isso conecta diretamente a idéia de quantas maneiras diferentes existem para fazer cabeças em testes binomiais ao número de diferentes seqüências de bytes.2n=k=0n(nk)28=256kn

  • Além disso, podemos mostrar que os 256 resultados são igualmente prováveis ​​pela propriedade da independência. Os ensaios anteriores não influenciam o próximo, portanto, a probabilidade de uma ordem específica é, em geral, (porque a probabilidade conjunta de eventos independentes é o produto de suas probabilidades). Como as avaliações são justas, , essa expressão se reduz a . Como todas as ordens têm a mesma probabilidade, temos uma distribuição uniforme sobre esses resultados (que por codificação binária podem ser representados como números inteiros em ).pk(1p)nkP(success)=P(fail)=p=0.5P(any ordering)=0.58=1256[0,255]

  • Finalmente, podemos levar esse círculo completo de volta à distribuição do sorteio e do binômio. Sabemos que a ocorrência de 0 cabeças não tem a mesma probabilidade que 4 cabeças, e que isso ocorre porque existem diferentes maneiras de ordenar as ocorrências de 4 cabeças, e que o número de tais ordenações é dado pelo teorema binomial. Portanto, deve ser ponderado de alguma forma, especificamente deve ser ponderado pelo coeficiente binomial. Portanto, isso nos fornece o PMF da distribuição binomial, . Pode ser surpreendente que essa expressão seja um PMF, especificamente porque não é imediatamente óbvio que seja 1. Para verificar, temos que verificar seP(4 heads)P(k successes)=(nk)pk(1p)nkk=0n(nk)pk(1p)nk=1, no entanto, este é apenas um problema dos coeficientes binomiais: .1=1n=(p+1p)n=k=0n(nk)pk(1p)nk

Sycorax diz restabelecer Monica
fonte
Isso faz sentido ... mas não esperamos que 15, 30, 60, 120 e 240 tenham um peso maior na distribuição que 0 ou 255?
vítreo
11
Eu acho que entendo agora. Vou aceitar esta resposta porque acho que a chave aqui é a ordem à qual você chamou atenção. Obrigado
glassy
Mais uma nota - para usar o meu exemplo de moeda, isso é realmente jogar 8 moedas ao mesmo tempo, em oposição a 8 tentativas de jogar uma moeda. Nisso mentiu minha confusão.
Vítreo
2
O conceito de "valor de posição" de "aritmética de grau elementar" é especialmente aplicável aqui; para usar uma analogia decimal, se considera 10001000e 10000001como números bastante diferentes.
JM não é estatístico
17

por que uma sequência de 8 zeros ou 8 zeros parece ser tão provável quanto uma sequência de 4 e 4 ou 5 e 3, etc.

O aparente paradoxo pode ser resumido em duas proposições, que podem parecer contraditórias:

  1. A sequência (oito zeros) é igualmente provável que a sequência (quatro zeros, quatro). (Em geral: todas as sequências têm a mesma probabilidade, independentemente de quantos zeros / zeros eles tenham.)s1:00000000s2:0101010128

  2. O evento " : a sequência teve quatro zeros " é mais provável (de fato, vezes mais provável) do que o evento " : a sequência teve oito zeros ".e170e2

Essas proposições são verdadeiras. Porque o evento inclui muitas sequências.e1

leonbloy
fonte
8

Todas as sequências têm a mesma probabilidade = 1/256. É errado pensar que as seqüências que têm mais perto de um número igual de 0s e 1s são mais prováveis ​​à medida que a pergunta é interpretada. Deve ficar claro que chegamos a 1/256 porque assumimos independência de tentativa para tentativa . É por isso que multiplicamos as probabilidades e o resultado de um estudo não influencia no próximo.2828

Michael R. Chernick
fonte
2
Essa seria uma resposta correta, se curta, se a pergunta não incluísse a palavra "por que". Como é, você simplesmente reitera um dos dados da pergunta, sem nenhuma explicação.
Homem de Lata
11
Na verdade ... Esta resposta está realmente errada, veja a resposta de leonbloy para saber o porquê.
Homem de Lata
3
@Walt não está incorreto. Sutileza da linguagem. Qualquer sequência dada não é mais provável porque tem menos desequilíbrio entre 0s e 1s. Existem simplesmente mais sequências desse tipo .
Hbbs
4
Alguém concorda comigo? Se um 0 tem probabilidade 1/2 e 1 tem probabilidade 1/2 e um termo na sequência é independente do próximo, a probabilidade de uma determinada sequência de comprimento 8 tem probabilidade . e o mesmo acontece com qualquer outra sequência de 8.1/28=1/256
Michael R. Chernick
4
@ Michael Concordo plenamente e tenho o prazer de ver - finalmente! - um apelo explícito ao cerne da questão: independência. Eu ficaria feliz em votar sua resposta se você incluir esse comentário.
whuber
7

EXEMPLO com 3 bits (geralmente um exemplo é mais ilustrativo)

Escreverei os números naturais de 0 a 7 como:

  • Um número na base 10
  • Um número na base 2 (isto é, uma sequência de bits)
  • Uma série de lançamentos de moedas implícitos na representação da base 2 (1 indica um giro de cabeça e 0 indica um giro de coroa).

Base 10Base 2 (with 3 bits)Implied Coin Flip SeriesHeadsTails0000TTT031001TTH122010THT123011THH214100HTT125101HTH216110HHT217111HHH30

Escolher um número natural de 0 a 7 com probabilidade igual equivale a escolher uma das séries de troca de moedas à direita com igual probabilidade.

Portanto, se você escolher um número da distribuição uniforme sobre os números inteiros de 0 a 7, você tem chance de escolher 3 cabeças, chance de escolher 2 cabeças, chance de escolher 1 cabeça e chance de escolher 0 cabeças.18383818

Matthew Gunn
fonte
3

A resposta da Sycorax está correta, mas parece que você não está totalmente claro sobre o porquê. Quando você joga 8 moedas ou gera 8 bits aleatórios, levando em consideração o resultado, será uma das 256 possibilidades igualmente prováveis. No seu caso, cada um desses 256 resultados possíveis é mapeado exclusivamente para um número inteiro, para que você obtenha uma distribuição uniforme como resultado.

Se você não levar em conta a ordem, como considerar quantas caras ou coroas obteve, existem apenas 9 resultados possíveis (0 cabeças / 8 caudas - 8 cabeças / 0 coroas) e elas não são mais igualmente prováveis . A razão para isso é que, dos 256 resultados possíveis, há 1 combinação de movimentos que fornece 8 cabeças / 0 caudas (HHHHHHHHH) e 8 combinações que produzem 7 cabeças / 1 cauda (uma coroa em cada uma das 8 posições em a ordem), mas 8C4 = 70 maneiras de ter 4 cabeças e 4 caudas. No caso de troca de moedas, cada uma dessas 70 combinações é mapeada para 4 cabeças / 4 caudas, mas no problema do número binário, cada uma dessas 70 resultados é mapeada para um número inteiro único.

Blacksteel
fonte
2

O problema, corrigido, é: Por que o número de combinações de 8 dígitos binários aleatórios é tomado como 0 a 8 dígitos selecionados (por exemplo, os 1s) em um momento diferente do número de permutações de 8 dígitos binários aleatórios. No contexto deste documento, a escolha aleatória de 0 e 1 significa que cada dígito é independente de qualquer outro, de modo que os dígitos não estão correlacionados ; .p(0)=p(1)=12

A resposta é: Existem duas codificações diferentes; 1) codificação sem perdas de permutações e 2) codificação com perdas de combinações.

Anúncio 1) Para codificar sem perdas os números para que cada sequência seja única, podemos vê-lo como um número inteiro binário , onde fica à esquerda para a direita dígitos na sequência binária de 0 e 1 aleatórios. O que isso faz é tornar cada permutação única, pois cada dígito aleatório é então codificado em posição. E o número total de permutações é entãoi=182i1XiXiith28=256. Então, por coincidência, é possível converter esses dígitos binários nos números de base 10 de 0 a 255 sem perda de exclusividade, ou, nesse caso, pode-se reescrever esse número usando qualquer outra codificação sem perda (por exemplo, dados compactados sem perda, Hex, Octal). A questão em si, no entanto, é binária. Cada permutação é igualmente provável, pois existe apenas uma maneira de criar uma sequência de codificação única, e assumimos que a aparência de 1 ou 0 é igualmente provável em qualquer lugar dessa cadeia, de modo que cada permutação seja igualmente provável.

Anúncio 2) Quando a codificação sem perdas é abandonada considerando apenas as combinações, temos uma codificação com perdas na qual os resultados são combinados e as informações são perdidas. Estamos vendo a série numérica, wlog como o número 1; , que por sua vez reduz para , o número de combinações de 8 objetos obtidos cada vez, e para esse problema diferente, a probabilidade de exatamente 4 1's é 70 ( ) vezes maior que a obtenção de 8 1's, porque há 70, igualmente provável permutações que podem produzir 4 1's.i=1820XiC(8,i=18Xi)i=18XiC(8,4)

Nota: No momento, a resposta acima é a única que contém uma comparação computacional explícita das duas codificações e a única resposta que menciona o conceito de codificação. Demorou um pouco para acertar, e é por isso que essa resposta foi rebaixada, historicamente. Se houver alguma reclamação pendente, deixe um comentário.

Atualização: Desde a última atualização, fico satisfeito ao ver que o conceito de codificação começou a pegar nas outras respostas. Para mostrar isso explicitamente para o problema atual, anexei o número de permutações codificadas com perdas em cada combinação.insira a descrição da imagem aqui

Observe que o número de bytes de informações perdidas durante cada codificação combinatória é equivalente ao número de permutações para essa combinação menos um [ , onde é o número de 1s], ou seja, para esse problema, de a por combinação ou geral.C(8,n)1n0692569=247

Carl
fonte
2
Usar a maneira convencional de nomear números - omitindo toda referência a zeros anteriores - potencialmente confunde essa explicação. Você não acha que a situação se tornaria muito mais clara escrevendo como , (que você inadvertidamente omitiu) como e assim por diante? 000000000100000001
whuber
16
Francamente, tudo está correto na medida em que vai, mas não aborda a questão . Você fez um bom trabalho ao mostrar como oito bits ordenados podem representar números no intervalo, mas não explicou por que selecionar esses bits aleatoriamente fornece uma distribuição uniforme (algo que é, reconhecidamente, tão simples que explicá-lo claramente leva algum tempo). sutileza).
dmckee
9
Não seria mais simples dizer que 8 bits aleatórios (independentemente) são distribuídos uniformemente em [00000000, 11111111] pela mesma razão que três dígitos aleatórios são uniformemente distribuídos em [000, 999]? O lado queixoso de como / por que os computadores usam o binário e as bases fracionárias é totalmente desnecessário e não relacionado. Quero dizer, o fato de o binário usar apenas os símbolos 0 e 1 é apenas uma propriedade inerente da base 2 ... não há necessidade de explicar isso. Se você quisesse manter esse tipo de explicação, provavelmente seria mais útil explicar como as bases funcionam em geral, mas isso ainda não vem ao caso.
Blackhawk
3
Fico feliz em ver o quanto essa resposta melhorou. No entanto, tenho dificuldade em ver o que as representações da base 10 têm a ver com essa pergunta (a base 3 ou a base 17 não funcionariam tão bem?) E não consigo ver o que pode ser especial nos 8 bits que também não funcionam. generalizar para qualquer número finito de bits. Isso sugere que a maioria das considerações nesta resposta é tangencial ou irrelevante.
whuber
3
E gostaria de agradecer por essa caracterização feliz da confusão expressa na pergunta: codificação "com perdas" e "sem perdas". É memorável, um pouco diferente de outras perspectivas, perspicaz e potencialmente pode esclarecer essa confusão rapidamente.
whuber
1

Eu gostaria de expandir um pouco a idéia de dependência de ordem versus independência.

No problema de calcular o número esperado de caras do lançamento de 8 moedas, estamos somando os valores de 8 distribuições idênticas, cada uma das quais é a distribuição de Bernoulli [; B(1, 0.5) ;](em outras palavras, 50% de chance de 0, 50% de chance de 1) A distribuição da soma é a distribuição binomial [; B(8, 0.5) ;], que tem a forma de corcunda familiar, com a maior parte da probabilidade centrada em torno de 4.

No problema de calcular o valor esperado de um byte composto por 8 bits aleatórios, cada bit tem um valor diferente que contribui para o byte, portanto, estamos somando os valores de 8 distribuições diferentes . A primeira é [; B(1, 0.5) ;], a segunda é [; 2 B(1, 0.5) ;], a terceira é [; 4 B(1, 0.5) ;], assim por diante até a oitava que é [; 128 B(1, 0.5) ;]. A distribuição dessa soma é compreensivelmente bem diferente da primeira.

Se você quiser provar que esta última distribuição é uniforme, acho que você poderia fazê-lo indutivamente - a distribuição do bit mais baixo é uniforme com um intervalo de 1 por suposição, então você gostaria de mostrar que, se a distribuição dos [; n ;]bits mais baixos é uniforme com um intervalo de [; 2^n - 1} ;]então a adição do [; n+1 ;]st bit torna a distribuição dos [; n + 1 ;]bits mais baixos uniforme com um intervalo de [; 2^{n+1} - 1 ;], obtendo uma prova para todos os resultados positivos[; n ;]. Mas a maneira intuitiva é provavelmente exatamente o oposto. Se você começar com o bit mais alto e escolher os valores um de cada vez, até o mais baixo, cada bit dividirá o espaço de possíveis resultados exatamente pela metade e cada metade será escolhida com igual probabilidade; assim, quando chegar ao no fundo, cada valor individual deve ter a mesma probabilidade de ser escolhido.

hobbs
fonte
Não é um uniforme contínuo. O bit é 0 ou 1 e nada no meio.
Michael R. Chernick
@ MichaelChernick, é claro que estamos lidando apenas com distribuições discretas aqui.
hobbs
O OP disse que os bits são apenas 1 ou 0 e nada no meio.
Michael R. Chernick
11
@MichaelChernick correto.
Hbbs
1

Se você fizer uma pesquisa binária comparando cada bit, precisará do mesmo número de etapas para cada número de 8 bits, de 0000 0000 a 1111 1111, ambos com o comprimento 8 bits. Em cada etapa da pesquisa binária, ambos os lados têm uma chance de 50/50 de ocorrer, portanto, no final, porque todo número tem a mesma profundidade e as mesmas probabilidades, sem nenhuma escolha real, cada número deve ter o mesmo peso. Assim, a distribuição deve ser uniforme, mesmo quando cada bit individual é determinado por lançamentos de moedas.

No entanto, o dígito dos números não é uniforme e teria distribuição igual ao lançamento de 8 moedas.

Esperançosamente útil
fonte
1

Existe apenas uma sequência com oito zeros. Existem setenta sequências com quatro zeros e quatro uns.

Portanto, enquanto 0 tem uma probabilidade de 0,39% e 15 [00001111] também tem uma probabilidade de 0,39%, e 23 [00010111] tem uma probabilidade de 0,39% etc., se você somar todas as setenta das probabilidades de 0,39% você recebe 27,3%, que é a probabilidade de ter quatro. A probabilidade de cada resultado individual de quatro e quatro não precisa ser maior que 0,39% para que isso funcione.

Random832
fonte
Isso não muda o fato de que todas as 256 seqüências são igualmente prováveis.
Michael R. Chernick
@MichaelChernick Eu não disse, afirmei explicitamente que todos têm uma probabilidade de 0,39%, estou abordando as suposições da OP.
precisa saber é o seguinte
Você está certo. É outra maneira de dizer o que eu disse na minha resposta. Algumas das outras respostas estão erradas.
Michael R. Chernick
1

Considere dados

Pense em rolar alguns dados, um exemplo comum de distribuição não uniforme. Para fins de matemática, imagine que os dados sejam numerados de 0 a 5 em vez dos tradicionais de 1 a 6. O motivo da distribuição não ser uniforme é que você está olhando para a soma dos lançamentos de dados, em que várias combinações podem produzir o mesmo total como {5, 0}, {0, 5}, {4, 1}, etc. todos gerando 5.

No entanto, se você interpretar o lançamento de dados como um número aleatório de 2 dígitos na base 6, cada combinação possível de dados é única. {5, 0} seria 50 (base 6), que seria 5 * ( ) + 0 * ( ) = 30 (base 10). {0, 5} seria 5 (base 6) que seria 5 * ( ) = 5 (base 10). Então você pode ver, existe um mapeamento de 1 para 1 dos possíveis lançamentos de dados interpretados como números na base 6 versus um mapeamento de muitos para 1 para a soma dos dois dados de cada rolagem.616060

Como apontam @Sycorax e @Blacksteel, essa diferença realmente se resume à questão da ordem.

Falcão
fonte
0

Cada bit que você escolhe é independente um do outro. Se você considerar o primeiro bit, há uma

  • 50% de probabilidade será 1

e

  • 50% de probabilidade será 0.

Isso também se aplica ao segundo, terceiro e assim por diante, para que você acabe com isso para cada combinação possível de bits para criar o seu byte = chance de esse inteiro único de 8 bits ocorrer.(12)81256

Ahemone
fonte
Todas essas afirmações são verdadeiras, mas isso não explica por que os lançamentos de moedas, que também são justos e independentes, têm apenas 9 resultados distintos quando um resultado é definido como o número de caras e coroa.
Sycorax diz Restabelecer Monica
Isso é apenas o resultado da colocação dos resultados em um sistema ordenado após a sua escolha. A mesma distribuição seria alcançada mesmo se os bits aleatórios fossem colocados em posições aleatórias no byte. Você também terá a mesma distribuição nos lançamentos de moedas pela maneira como enquadra a pergunta e encontra a chance de obter uma combinação específica de cara e coroa, como HHTHTTTH. Você terá 1/256 de chance de obter a sequência exata de lançamentos de moedas para os 8 lançamentos de moedas que são executados a cada vez.
Ahemone
Todas essas informações são boas para incluir na própria resposta. Meu comentário não tem problema com o que você disse, mas com a omissão de um endereço direto da fonte de confusão do OP: a relação entre bits e moedas.
Sycorax diz Restabelecer Monica
Devo também dizer que, para chegar ao valor esperado de 4 do OP, eles estão tentando encontrar a probabilidade de n muitos 1 ou n muitos 0 em um determinado byte. Esse enquadramento da questão daria a distribuição binomial que eles esperavam em sua mente, em vez da distribuição uniforme de encontrar a probabilidade de obter um certo valor desses bits aleatórios.
Ahemone