Come calcolare le informazioni entropia in una decisione in due fasi?

Question

Ho una domanda che credo comporta "entropia condizionale" nel campo della teoria dell'informazione. Sto cercando di avvolgere la mia testa intorno ad esso, ma potrebbe usare un certo aiuto. Si consideri un esempio in cui abbiamo quattro case. Nella prima casa ci sono otto persone, quattro persone vivono nella seconda casa, e ci sono due persone in terza casa, e due persone nella quarta casa. Così, quattro case e sedici persone. Se ho semplicemente scegliere una di queste persone a caso, allora che la scelta è una selezione tra i sedici persone, ottenendo un entropia informazioni di 4 bit per questa scelta.

Ma ora consideriamo una selezione in due fasi, in cui prima ho scelto una casa a caso, e poi scelgo una delle persone in casa selezionata. Quindi il primo passo, quella di raccogliere una casa dai quattro case disponibili, genera due bit di informazione entropia. Ma ora, nel 25% del tempo che prendo la prima casa, il secondo passo aggiunge altri tre bit nella scelta di una persona tra le otto persone nella prima casa. In un altro 25% dei casi, devo solo altri due bit per selezionare una persona da quattro che vivono nella seconda casa. E, infine, in una buona metà dei casi, ho bisogno solo di un singolo bit di scegliere una persona dalla coppia che vive sia la terza o la quarta casa.

In qualche modo, mi sembra, che la media ponderata del bit-conti per l'approccio in due fasi dovrebbe generare la stessa di quattro bit totale che il metodo single-step richiede. Ma non riesco a ottenere le cifre per aggiungere fino, così chiaramente c'è di più per la matematica di quanto sto considerando. Mi aspettavo che si dovrebbe semplicemente essere in grado di sommare le probabilità in questo modo:

(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)]

Ma questo produce un risultato di 3,75 bit, e non i 4 bit che mi aspetto. Ecco un po 'di pitone che ho usato per valutare questo.

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

Quindi, manca qualcosa dai miei personaggi. Qualcuno mi può punto nella giusta direzione?

Answer 1

Se si sceglie una casa a caso (con probabilità uniforme, UP in breve), quindi scegliere un residente a caso (UP), sei non di scegliere uno su 16 UP - si avere una distribuzione alquanto asimmetrica, che produce sorprende inferiore entropia (UP massimizza entropia). Otto persone vengono selezionati con una probabilità di 1/32 ciascuno, quattro vengono selezionate con una probabilità di 1/16 ciascuno, e gli altri quattro con una probabilità di 1/8 ciascuna. Questa distribuzione ha un entropia di 3,75 bit, proprio come si calcolata con il metodo differente.