Формула Шеннона

[Legioner93]

Для задачи типа "В коробке имеется 4 красных шара, 4 синих, 8 зеленых. Сколько бит информации содержит в себе каждый шар?" применима формула Шеннона, где $P_{i}$ - отношение числа шаров $i$-ого цвета к числу всех шаров (или, по-другому, вероятность достать шар $i$-ого цвета).
$K=-\sum\limits_{i}P_{i} \log_{2}P_{i}$.
Но известно, что если дано n одинаковых шаров, то каждый шар содержит $\log_{2}n$ бит информации. Нет ли тут противоречия с формулой Шеннона? Спасибо.

[Профессор Снэйп]

Объясните, как шар может содержать биты информации. Они на нём, что ли, нарисованы?

Я этой теорией не владею, но чувствую, что задача сформулирована не совсем корректно. Может, кто-то подскажет корректную формулировку? Или укажет мне, что я не прав.

[ИСН]

"Пилите, Шура, они содержат информацию".

[PAV]

Немного коряво сформулировано.

Фраза "шар содержит столько-то информации" плохая. Величина $K$, которую Вы посчитали, это энтропия данной системы, и она обозначает следующее. Допустим, что из указанной урны извлекаем случайный шар, записываем его цвет. Кладем обратно, перемешиваем, извлекаем второй. И так далее. Получаем длинную последовательность исходов независимых экспериментов. Так вот, при оптимальном кодировании этой последовательности на каждый символ в среднем нужно затратить $K$ бит. В этом смысле можно говорить, что каждое случайное извлечение шара действительно дает нам $K$ бит информации.

А второе утверждение неверно. Если шары одинаковы, то они не несут никакой информации, так как энтропия (неопределенность) данной системы равна нулю. Результат извлечения случайного шара однозначно предсказуем. А вот если $n$ шаров различимы (пронумерованы), тогда действительно энтропия равна $\log_2 n$.

[Профессор Снэйп]

PAV в сообщении #292616 писал(а):

Фраза "шар содержит столько-то информации" плохая. Величина $K$, которую Вы посчитали, это энтропия данной системы, и она обозначает следующее. Допустим, что из указанной урны извлекаем случайный шар, записываем его цвет. Кладем обратно, перемешиваем, извлекаем второй. И так далее. Получаем длинную последовательность исходов независимых экспериментов. Так вот, при оптимальном кодировании этой последовательности на каждый символ в среднем нужно затратить $K$ бит. В этом смысле можно говорить, что каждое случайное извлечение шара действительно дает нам $K$ бит информации.

То есть, если у нас всего три цвета, то нужно $\log_2 3$ бита для записи каждого цвета. И это есть энтропия системы?

Или тут так, что зелёные шары встречаются в половине случаев, и на них можно тратить $1$ бит, а на каждый из остальных по $2$ бита, при многочисленных экспериментах получится $1$ бит в половине случаев и $2$ бита в оставшейся половине, в среднем полтора бита и энтропия системы равна $3/2 < \log_2 3 \approx 1.585$?

(Оффтоп)

Извиняюсь за наивные вопросы, для меня эта теория --- terra incognita.

-- Пт фев 26, 2010 20:12:46 --

Кстати, упомянутая топикстартером "формула Шеннона" даёт

$$ -\left( \frac{1}{4} \log_2 \frac{1}{4} + \frac{1}{4} \log_2 \frac{1}{4} + \frac{1}{2} \log_2 \frac{1}{2} \right) = \left( \frac{1}{4} \cdot (-2) + \frac{1}{4} \cdot (-2) + \frac{1}{2} \cdot (-1) \right) = \frac{3}{2} $$

[PAV]

Профессор Снэйп в сообщении #292620 писал(а):

То есть, если у нас всего три цвета, то нужно $\log_2 3$ бита для записи каждого цвета. И это есть энтропия системы?

Или тут так, что зелёные шары встречаются в половине случаев, и на них можно тратить $1$ бит, а на каждый из остальных по $2$ бита, при многочисленных экспериментах получится $1$ бит в половине случаев и $2$ бита в оставшейся половине, в среднем полтора бита и энтропия системы равна $3/2 < \log_2 3 \approx 1.585$?

Ну да, примерно так. Для достижения оптимального кодирования (за исключения явно специально подобранных случаев) нужно кодировать последовательность достаточно длинными блоками (ну и при этом оптимально строить код, разумеется). В пределе будет как раз в среднем столько бит на символ, какова энтропия.

[Профессор Снэйп]

PAV в сообщении #292646 писал(а):

Для достижения оптимального кодирования (за исключения явно специально подобранных случаев) нужно кодировать последовательность достаточно длинными блоками (ну и при этом оптимально строить код, разумеется).

А что значит "оптимально строить код"?

Вот, к примеру, в урне $2$ зелёных шара и $1$ синий. Мы их вытаскиваем наугад и пишем в двоичном коде результаты вытаскиваний. Как именно надо кодировать, чтобы получалось в среднем

$$ -\left( \frac{2}{3} \log_2 \frac{2}{3} + \frac{1}{3} \log_2 \frac{1}{3} \right) = \log_2 3 - \frac{2}{3} \approx 0.918 $$

бит на результат каждого вытаскивания? Как это вообще возможно: менее одного бита на результат?

[meduza]

Профессор Снэйп в сообщении #292758 писал(а):

Как это вообще возможно: менее одного бита на результат?

Можно. Например последовательность бит, в которой, скажем, на каждый нулевой бит приходится в среднем сто единичных можно "сжать" довольно здорово, передавая её в виде <бит><число штук><бит><число штук>...

[Xaositect]

Профессор Снэйп в сообщении #292758 писал(а):

бит на результат каждого вытаскивания? Как это вообще возможно: менее одного бита на результат?

Берем и кодируем тройки вытаскиваний: ззз = 00, ззс = 10, зсз = 010, сзз = 011, зсс = 1100, сзс = 1101, ссз = 1110, ссс = 1111.
Получается $\approx 2.814$ на 3 результата, $\approx 0.938$ бита на один.

[PAV]

Пусть имеется $n$ возможных сообщений, которые мы будем кодировать. $n$ может быть любым, если исходная последовательность двоичная, то для увеличения этого числа можно составить блоки из нескольких символов. Пусть $p_1,\ldots,p_n$ - вероятности сообщений, предполагаем их независимыми.

Энтропия системы задается формулой $H=-\sum p_i\log_2 p_i$.

Оптимальный кодирующий префиксный код строится явным алгоритмом Хаффмана.

Вообще количество информации, которое мы получаем при наблюдении $i$-го сообщения равно $-\log_2 p_i$. (Легко увидеть, что энтропия - это на самом деле математические ожидание этой случайной величины). Это число равно числу бит, которое нужно затратить на кодирование этого сообщения. Если все эти логарифмы оказываются целыми числами - тогда можно так и кодировать, это будет оптимальный код, на котором достигается $H$ бит на символ. Если же не целые, тогда можно взять от каждого целую часть сверху. Полученные числа будут удовлетворять необходимому условию существования префиксного кода с такими длинами. Этот код не обязательно будет оптимальным, но в нем по крайней мере число бит на сообщение оценивается сверху величиной $H+1$.

[Профессор Снэйп]

Кажется, начинает доходить! Спасибо

[Legioner93]

Спасибо всем, я разобрался. Действительно,номера 8 белых шаров можно заменить на цвета (что, по сути, одно и тоже) и по формуле Шеннона получается $log_2{8}=3$.

[Профессор Снэйп]

Legioner93 в сообщении #293065 писал(а):

Действительно,номера 8 белых шаров можно заменить на цвета...

Заменить на белый цвет? Или имеются в виду цвета не этих шаров?

[PAV]

Я надеюсь, что имелось в виду "заменить на восемь различных цветов". Хотя номера удобнее.