Список обозначений

Энтропия

entropy

Пусть $\mathfrak X$ — распределение вероятностей с конечным носителем $X$. Тогда (шенноновской) энтропией $H(\mathfrak X)$ этого распределения называется математическое ожидание случайной величины $x\mapsto-\log\Pr_{\mathfrak X}(x)$ ($x\in X$), взятое по распределению вероятностей $\mathfrak X$ на $X$. Другими словами, \[ H(\mathfrak X)=-\sum_{x\in X}\Pr_{\mathfrak X}(x)\log\Pr_{\mathfrak X}(x). \] Здесь под $\log$ понимается логарифм по произвольному фиксированному основанию, большему $1$. Выбор основания логарифма в данном случае не имеет принципиального значения, так как смена этого основания приводит к умножению энтропии на положительную константу. Следовательно, выбор основания логарифма равносилен выбору единицы измерения энтропии. Часто в качестве основания логарифма в определении энтропии выбирают $2$. В этом случае энтропия измеряется в битах.

Говоря неформально, энтропия является количественной мерой неопределенности распределений вероятностей: чем более неопределенным является распределение, тем больше будет его энтропия.

Определение энтропии естественным образом переносится на случайные величины. А именно, энтропия $H(\widetilde x)$ случайной величины $\widetilde x$ с конечным носителем — это энтропия распределения вероятностей этой случайной величины.

В пионерской работе [1] приводятся следующие важнейшие свойства энтропии.
  • $0\leqslant H(\mathfrak X)\leqslant\log\#X$;
  • $H(\mathfrak X)=0$ тогда и только тогда, когда $\#X=1$ (т. е. распределение $\mathfrak X$ сосредоточено на одном элементе);
  • $H(\mathfrak X)=\log\#X$ тогда и только тогда, когда $\mathfrak X$ — равномерное распределение на $X$;
  • если $\widetilde x$ и $\widetilde y$ — случайные величины с конечными носителями (не обязательно независимые), то $H(\widetilde x,\widetilde y)\leqslant H(\widetilde x)+H(\widetilde y)$, причем равенство здесь имеет место тогда и только тогда, когда $\widetilde x$ и $\widetilde y$ независимы.
Кроме шенноновской, в литературе встречаются и другие виды энтропии (например, минимальная энтропия, энтропия Реньи — см. [2]). Однако в настоящем справочнике рассматривается только шенноновская энтропия.

Литература

  • [1] Shannon, C. E. «A mathematical theory of communication» 1948
  • [2] Luby, M. «Pseudorandomness and cryptographic applications» 1996

Адрес редакции сайта: dialogus@cryptography.ru
© При копировании материалов ссылка на авторов,
© а при их отсутствии — на сайт, обязательна