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?
binomial
random-generation
uniform
vítreo
fonte
fonte
Respostas:
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 pk n n−k p
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 - kk n−k
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=∑nk=0(nk) 28=256 k n
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(1−p)n−k P(success)=P(fail)=p=0.5 P(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(1−p)n−k ∑nk=0(nk)pk(1−p)n−k=1 , no entanto, este é apenas um problema dos coeficientes binomiais: .1=1n=(p+1−p)n=∑nk=0(nk)pk(1−p)n−k
fonte
10001000
e10000001
como números bastante diferentes.O aparente paradoxo pode ser resumido em duas proposições, que podem parecer contraditórias:
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:00000000 s2:01010101 28
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 ".e1 70 e2
Essas proposições são verdadeiras. Porque o evento inclui muitas sequências.e1
fonte
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.28 28
fonte
EXEMPLO com 3 bits (geralmente um exemplo é mais ilustrativo)
Escreverei os números naturais de 0 a 7 como:
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.18 38 38 18
fonte
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.
fonte
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ão∑8i=12i−1Xi Xi ith 28=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.∑8i=120Xi C(8,∑8i=1Xi) ∑8i=1Xi C(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.
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)−1 n 0 69 256−9=247
fonte
00000000
00000001
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.fonte
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.
fonte
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.
fonte
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.61 60 60
Como apontam @Sycorax e @Blacksteel, essa diferença realmente se resume à questão da ordem.
fonte
Cada bit que você escolhe é independente um do outro. Se você considerar o primeiro bit, há uma
e
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)8 1256
fonte