Энтропия и короткие сообщения
Предположим, у нас есть система Х, которая с одинаковой вероятностью может находиться в любом из 8 возможных состояний:
X1,X2,X3,X4,X5,X6,X7,X8
Есть такая экстраординарно распространенная мера, — в физике, математике и даже биологии — называется она «энтропия». И энтропия Х составляет 3 бита. Это значит, что для выяснения состояния Х нам в среднем понадобиться 3 да/нет вопроса. Например, кто-то может нам рассказать о значении Х с помощью такого кода:
(X1:001)(X2:010)(X3:011)(X4:100)
(X5:101)(X6:110)(X7:111)(X8:000)
Так что если я спросил бы «Первый символ — 1?» и получил бы ответ «Да»; «Второй символ — 1?» и услышал бы «Нет»; «Третий символ — 1?» — «Нет»; то я бы знал, что Х находится в состоянии 4.
Теперь предположим, что у системы Y есть четыре возможных состояния с таким распределением вероятностей:
Y1:1/2(0,5)
Y2:1/4(0,25)
Y3:1/8(0,125)
Y4:1/8(0,125)
Тогда энтропия Y будет равна 1,75 бит, что значит нам понадобится 1,75 вопросов в среднем, чтобы узнать значение Y.
В каком смысле можно задать один и три-четвертых вопроса? Представьте, что мы используем следующий код для описания состояния Y:
(Y1:1)(Y2:01)(Y3:001)(Y4:000)
Сначала вы спросите «Первый символ — 1?», и если ответ «Да», то задача решена: Y находится в состоянии 1. И такое происходит в половине случаев — состояние Y можно вычислить с помощью одного вопроса.
Предположим, что вы получили ответ «Нет». Тогда вы спрашиваете: «Второй символ — 1?». Если ответ «Да», то вы закончили: Y находится в состоянии 2. И это происходит с вероятностью в 1/4, и каждый раз, когда Y в состоянии 2, мы можем узнать это с помощью двух да/нет вопросов — в 25% случаев понадобится два вопроса для определения состояния Y.
Если же вы получили ответ «нет» два раза подряд, и, спросив «Третий символ — 1?», получили ответ «Да», то задача решена и Y в состоянии 3; если нет, то Y в состоянии 4. В 1/8 случаев Y в состоянии 3 и понадобится три вопроса. И в 1/8 случаев Y в состоянии 4 и понадобится три вопроса.
(1/2⋅1)+(1/4⋅2)+(1/8⋅3)+(1/8⋅3)=0,5+0,5+0,375+0,375=1,75.
Общая формула определения энтропии системы S это сумма всех Si: −p(Si)⋅log2p(Si).
Например, log2 числа 1/8 — это −3. Получается −(1/8⋅−3)=0,375 — часть энтропии состояния 4 от всей энтропии системы Y — три вопроса.
Закодировать любую систему идеальным кодом получится не всегда, но если вам потребуется передать кому-то сообщение о состоянии случайного количества копий S за один раз, вы можете приблизиться к идеальному коду на случайную величину. (Гуглите «арифметическое кодирование»).