Como calcular a entropia de informações em uma decisão de duas etapas?

Question

Tenho uma pergunta que acho que envolve "entropia condicional" no campo da teoria da informação. Estou tentando envolver minha cabeça, mas poderia usar alguma ajuda. Considere um exemplo no qual temos quatro casas. Na primeira casa, há oito pessoas, quatro pessoas moram na segunda casa, e há duas pessoas na terceira casa e duas pessoas na quarta casa. Então, quatro casas e dezesseis pessoas. Se eu simplesmente escolher uma dessas pessoas aleatoriamente, essa escolha é uma seleção dentre dezesseis pessoas, produzindo uma entropia de informações de 4 bits para essa escolha.

Mas agora considere uma seleção de duas etapas na qual primeiro eu escolho uma casa aleatoriamente e depois escolho uma das pessoas na casa selecionada. Portanto, a primeira etapa, a de escolher uma casa nas quatro casas disponíveis, gera dois bits de entropia de informações. Mas agora, nos 25% do tempo em que escolho a primeira casa, o segundo passo adiciona mais três bits na escolha de uma pessoa dentre as oito pessoas da primeira casa. Em outros 25% dos casos, preciso de apenas outros dois bits para selecionar uma pessoa entre os quatro que moram na segunda casa. E, finalmente, em metade da metade dos casos, preciso de apenas um bit para escolher uma pessoa do par que vive na terceira ou na quarta casa.

De alguma forma, parece-me que a média ponderada de contagens de bits para a abordagem de duas etapas deve gerar o mesmo total de quatro bits que o método de uma etapa exige. Mas não consigo obter os números para somar, então claramente há mais nas contas do que estou considerando. Eu esperava que você fosse simplesmente capaz de adicionar as probabilidades assim:

(picking a house) + (picking a person in that house) ==

log(4) + [(1/4)*log(8) + (1/4)*log(4) + (1/4)*log(2) + (1/4)*log(2)]

Mas isso produz um resultado de 3,75 bits, e não os 4 bits que estou esperando. Aqui está um pouco de Python que eu costumava avaliar isso.

from math import log
def log2(x):
    return log(x,2)
x = log2(4) + ((1.0/4)*log2(8) + (1.0/4)*log2(4) + (1.0/4)*log2(2) + (1.0/4)*log2(2))
print x

Então, algo está faltando nas minhas figuras. Alguém pode me apontar na direção certa?

Answer 1

Se você escolher uma casa aleatoriamente (com probabilidade uniforme, para abreviar), escolha um residente aleatoriamente (up), você está não Escolher um em cada 16 - você tem uma distribuição um pouco distorcida, que sem surpresa produz entropia inferior (UP maximiza a entropia). Oito pessoas estão sendo selecionadas com uma probabilidade de 1/32 cada, quatro estão sendo selecionadas com uma probabilidade de 1/16 cada, e as outras quatro com uma probabilidade de 1/8 cada. este A distribuição possui uma entropia de 3,75 bits, assim como você calculou com sua abordagem diferente.