Задачи занятия:

• Научиться среди предложенных событий выбирать неопределенные;
• Установить соответствие между вероятностью события и его неопределенностью;
• Научиться подсчитывать энтропию события по формуле Хартли;
• Отработать метод половинного деления для решения задач на угадывание;
• Разобрать алгоритм решения задач на угадывание с применением понятия энтропии.

 

Способы измерения информации

Понятие количества информации естественно возникает, к примеру, в следующих типовых случаях:

1. Равенство вещественных переменных а = b, заключает в себе информацию о том, что а равно b. Про равенство а² = b² можно сказать, что оно несет меньшую информацию, чем первое, т.к. из первого следует второе, но не наоборот. Равенство а³ = b³ несет в себе информацию по объему такую же, как и первое;

2. Пусть происходят некоторые измерения с некоторой погрешностью. Тогда чем больше будет проведено измерений, тем больше информации об измеряемой сущности будет получено;

3. М.о. некоторой сл. в. содержит в себе информацию о самой сл. в. Важно заметить, что для сл.в., распределœенной по нормальному закону, с известной дисперсией знание м.о. дает полную информацию о сл.в.;

4. Рассмотрим схему передачи информации. Пусть передатчик описывается ел. в. X, тогда из-за помех в канале связи на приемник будет приходить сл.в. Y = X + Z, где Z — это сл.в., описывающая помехи. В этой схеме можно говорить о количестве информации, содержащейся в сл.в. Y, относительно X. Чем ниже уровень помех (дисперсия Z мала), тем больше информации можно получить из Y. При отсутствии помех Y содержит в себе всю информацию об X.

В 1865 ᴦ. немецкий физик Рудольф Клаузиус ввел в статистическую физику понятие энтропии или меры уравновешенности системы.

В 1921 ᴦ. основатель большей части математической статистики, англичанин Роналд Фишер впервые ввел термин “информация” в математику, но полученные им формулы носят очень специальный характер.

В 1948 ᴦ. Клод Шеннон в своих работах по теории связи выписывает формулы для вычисления количества информация и энтропии. Термин “энтропия” используется Шенноном по совету патриарха компьютерной эры фон Неймана, отметившего, что полученные Шенноном для теории связи формулы для ее расчета совпали с соответствующими формулами статистической физики, а также то, что “точно никто не знает” что же такое энтропия.

В основе теории информации лежит предложенный Шенноном способ измерения количества информации, содержащейся в одной сл. в. относительно другой сл. в. Этот способ приводит к выражению количества информации числом.

Для д.с.в. X и Y, заданных законами распределœения P(X = X_i) = p_i, P(Y = Y_j) = q_j и совместным распределœением P(X = X_i,Y = Y_j) = p_ij, количество информации, содержащейся в X относительно Y, равно

Стоит сказать, что для непрерывных сл. в. X и Y, заданных плотностями распределœения вероятностей p_X(t₁), p _Y (t₂) и P _X Y (t₁,t₂), аналогичная формула имеет вид

Очевидно, что

и, следовательно,

Энтропия д. с. в. X в теории информации определяется формулой

Свойства меры информации и энтропии:

1) Логарифмированием из очевидного для всœех х неравенства (равенство устанавливается только при х = 1) получается неравенство 

ᴛ.ᴇ. I(X, Y) = 0 только при p_ij = p_iq_j для всœех i и j, ᴛ.ᴇ. при независимости X и Y. В случае если X и Y независимы, то p_ij = p_iq_j и, следовательно, аргументы логарифмов равны 1 и, следовательно, сами логарифмы равны 0, что означает, что I(X, Y) = 0;

2) Следует из симметричности формул относительно аргументов;

3) В случае если НХ = 0, то всœе члены суммы, определяющей НХ, должны быть нули, что возможно только тогда и только тогда, когда X — константа;

4) Из четырех очевидных соотношений

получается

5) Нужно доказать

^или 

^но 

а значит аргументы у всœех логарифмов не больше 1 и, следовательно, значения логарифмов не больше 0, а это и значит, что вся сумма не больше 0.

В случае если HX = I(X,X) = I(X,Y), то для каждого i p_ij равно либо q_j, либо 0. Но из p_ij = P(X = X_i,Y = Y_j) = P(X = X_i/Y = Y_j)P(Y = Y_j)∈ {q_j,0} следует P(X = X_i/Y = Y_j) ∈ {0,1}, что возможно только в случае, когда X — функция от Y.

При независимости сл. в. X и Y одна из них ничем не описывает другую, что и отражается в том, что для таких сл. в. I(X, Y) = 0.

Рассмотрим пример измерения количества информации при подбрасывании двух игральных костей.

Пусть заданы д. с. в. X₁, X₂ и Y. X₁ и X₂ — количества очков, выпавших соответственно на 1-й и 2-й игральной кости, а Y = X₁ +X₂. Найти I(Y,X₁), I(X₁,X₁), I(Y, Y).

Законы распределœения вероятностей для д. с. в. X₁ и X₂ совпадают, т.к. кости одинаковые и без изъянов.

Закон распределœения вероятностей для д. с. в. Y,

вследствие того, что Х₁ Х₂ — независимы и в связи с этим

будет

Таблицы, определяющие Y:

Закон совместного распределœения вероятностей д. с. в. Х₁ и Y будет

к примеру,

В общем случае получится

Тогда

Здесь

что соответствует свойствам информации.

Подчеркнутый член в расчете I(X₁,Y) соответствует информации о двух случаях из 36, когда Y = 2 и Y =12, которые однозначно определяют Х₁. Шесть случаев, когда Y = 7, не несут никакой информации об X₁, что соответствует подчеркнутому члену .

Расчеты можно проводить, используя 4-е свойство информации, через энтропию.

Расчет количества информации с использованием 4-го свойства, а не определœения, обычно требует меньше вычислений.

Рассмотрим более простой пример. Пусть д. с. в. X равна количеству очков, выпавших на игральной кости, а д. с. в. Y равна 0, если выпавшее количество очков нечетно, и 1, если выпавшее количество очков четно. Найти I(X, Y) и /(Y, Y).

Составим законы распределœения вероятностей д. с. в. X и Y.

Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, при i = 1…6 p_i = Р(Х = i) = 1/6 и, соответственно, при j = 0…1 q_j = P(Y = j) = 1/2.

Составим также закон совместного распределœения вероятностей этих д. с. в.

Точное количество выпавших очков дает точную информацию о четности, ᴛ.ᴇ. 1 бит. Из I(X, Y) = I(Y,Y) = 1бит/сим и 3-го свойства информации следует, что информация об X полностью определяет Y, но не наоборот, т.к. I(X,Y) ¹ I(X,X) =1 + log₂3 » 2.58 бит/сим. Действительно, Y функционально зависит от X, а X от Y функционально не зависит.

Расчеты через энтропию будут следующими