Функция Хартли

Функция Хартли — это мера неопределенности , введенная Ральфом Хартли в 1928 году. Если выборка из конечного множества A выбирается равномерно случайным образом, то информация, раскрываемая после того, как результат становится известен, определяется функцией Хартли.

${\displaystyle H_{0}(A):=\mathrm {log} _{b}\vert A\vert ,}$

где | A | обозначает мощность A .

Если основание логарифма равно 2, то единицей неопределенности является шеннон ( более известный как бит ). Если это натуральный логарифм , то единицей является нат . Хартли использовал логарифм с основанием 10 , и с этим основанием единица информации называется хартли (он же бан или дит ) в его честь. Она также известна как энтропия Хартли или макс-энтропия.

Функция Хартли, энтропия Шеннона и энтропия Реньи

Функция Хартли совпадает с энтропией Шеннона (а также с энтропиями Реньи всех порядков) в случае равномерного распределения вероятностей. Она является частным случаем энтропии Реньи, поскольку:

${\displaystyle H_{0}(X)={\frac {1}{1-0}}\log \sum _{i=1}^{|{\mathcal {X}}|}p_{i}^{0}=\log |{\mathcal {X}}|.}$

Но ее также можно рассматривать как примитивную конструкцию, поскольку, как подчеркивали Колмогоров и Реньи, функцию Хартли можно определить без введения каких-либо понятий вероятности (см. «Неопределенность и информация» Джорджа Дж. Клира, стр. 423).

Характеристика функции Хартли

Функция Хартли зависит только от количества элементов в наборе, и, следовательно, может рассматриваться как функция натуральных чисел. Реньи показал, что функция Хартли в двоичной системе счисления является единственной функцией, отображающей натуральные числа в действительные числа, которая удовлетворяет

1. ${\displaystyle H(mn)=H(m)+H(n)}$(аддитивность)
2. ${\displaystyle H(m)\leq H(m+1)}$(монотонность)
3. ${\displaystyle H(2)=1}$(нормализация)

Условие 1 гласит, что неопределенность декартова произведения двух конечных множеств A и B равна сумме неопределенностей A и B. Условие 2 гласит, что большее множество имеет большую неопределенность.

Вывод функции Хартли

Мы хотим показать, что функция Хартли, log ₂ ( n ), является единственной функцией, отображающей натуральные числа в действительные числа, которая удовлетворяет условию

1. ${\displaystyle H(mn)=H(m)+H(n)\,}$(аддитивность)
2. ${\displaystyle H(m)\leq H(m+1)\,}$(монотонность)
3. ${\displaystyle H(2)=1\,}$(нормализация)

Пусть f — функция положительных целых чисел, удовлетворяющая трем вышеуказанным свойствам. Из аддитивного свойства мы можем показать, что для любого целого числа n и k ,

${\displaystyle f(n^{k})=kf(n).\,}$

Пусть a , b и t будут любыми положительными целыми числами. Существует уникальное целое число s, определяемое

${\displaystyle a^{s}\leq b^{t}\leq a^{s+1}.\qquad (1)}$

Поэтому,

${\displaystyle s\log _{2}a\leq t\log _{2}b\leq (s+1)\log _{2}a\,}$

и

${\displaystyle {\frac {s}{t}}\leq {\frac {\log _{2}b}{\log _{2}a}}\leq {\frac {s+1}{t}}.}$

С другой стороны, по монотонности,

${\displaystyle f(a^{s})\leq f(b^{t})\leq f(a^{s+1}).\,}$

Используя уравнение (1), получаем

${\displaystyle sf(a)\leq tf(b)\leq (s+1)f(a),\,}$

и

${\displaystyle {\frac {s}{t}}\leq {\frac {f(b)}{f(a)}}\leq {\frac {s+1}{t}}.}$

Следовательно,

${\displaystyle \left\vert {\frac {f(b)}{f(a)}}-{\frac {\log _{2}(b)}{\log _{2}(a)}}\right\vert \leq {\frac {1}{t}}.}$

Поскольку t может быть сколь угодно большим, разность в левой части приведенного выше неравенства должна быть равна нулю,

${\displaystyle {\frac {f(b)}{f(a)}}={\frac {\log _{2}(b)}{\log _{2}(a)}}.}$

Так,

${\displaystyle f(a)=\mu \log _{2}(a)\,}$

для некоторой константы μ , которая по свойству нормализации должна быть равна 1.

Смотрите также

• энтропия Реньи
• Мин-энтропия

Ссылки

• В данной статье использованы материалы из функции Хартли на PlanetMath , лицензированные по лицензии Creative Commons Attribution/Share-Alike License .
• В данной статье использованы материалы из книги «Вывод функции Хартли» на сайте PlanetMath , которая распространяется по лицензии Creative Commons Attribution/Share-Alike License .