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

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

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

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

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

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

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

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

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

Характеристика функции Хартли [ править ]

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

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

Условие 1 говорит о том , что неопределенность декартово произведение двух конечных множеств 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\,}$ (нормализация)

Пусть ƒ - функция на натуральных числах, удовлетворяющая трем указанным выше свойствам. Из аддитивного свойства мы можем показать, что для любых целых 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 .
• Эта статья включает материал из функции Derivation of Hartley на PlanetMath , которая находится под лицензией Creative Commons Attribution / Share-Alike License .