Как вычислить информационную энтропию в двухэтапном решении?

Question

У меня есть вопрос, который, я думаю, связан с «условной энтропией» в области теории информации. Я пытаюсь обвести вокруг себя голову, но могу использовать некоторую помощь. Рассмотрим пример, в котором у нас есть четыре дома. В первом доме восемь человек, четыре человека живут во втором доме, а в третьем доме два человека и два человека в четвертом доме. Итак, четыре дома и шестнадцать человек. Если я просто выбираю одного из этих людей наугад, то этот выбор - это выбор из числа шестнадцати человек, что дает информационную энтропию из 4 бит для этого выбора.

Теперь рассмотрим двухэтапный отбор, в котором сначала я выбираю один дом наугад, а затем выбираю одного из людей в выбранном доме. Итак, первый шаг - выбор одного дома из четырех доступных домов, генерирует два бита информационной энтропии. Но теперь, в 25% случаев, когда я выбираю первый дом, второй шаг добавляет еще три бита в выборе одного человека из числа восьми человек в первом доме. В других 25% случаев мне нужно всего еще два бита, чтобы выбрать одного человека из четырех, которые живут во втором доме. И, наконец, в полной половине случаев мне нужен только один бит, чтобы выбрать одного человека из пары, которая живет либо в третьем, либо в четвертом доме.

Как-то мне кажется, что средневзвешенное значение битов для двухэтапного подхода должно генерировать те же четыре бит, что и одноэтапный метод. Но я не могу заставить цифры сложить, так ясно, что математика больше, чем я рассматриваю. Я ожидал, что вы должны просто быть в состоянии сложить вероятности следующим образом:

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

Но это дает результат 3,75 бит, а не 4 бита, что я ожидал. Вот немного питона, который я использовал для оценки этого.

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 

Итак, что-то не хватает на моих рисунках. Может кто-то указать мне верное направление?

Answer 1

Если вы выбираете дом в случайном порядке (с равномерной вероятностью, UP для краткости), то выбирайте резидента в случайном порядке (UP), вы не выбирая один из 16 UP - у вас есть несколько перекошенное распределение, что неудивительно дает более низкую энтропию (UP максимизирует энтропию). Восемь человек выбираются с вероятностью 1/32 каждый, четыре выбираются с вероятностью 1/16 каждый, а остальные четыре с вероятностью 1/8 каждый. Это распределение имеет энтропию 3,75 бит, так же, как вы вычисляли с помощью вашего другого подхода.