Ентропія

Ця стаття відноситься до групи довідкових статей для студентів ФІН.

Вперше введена: Shannon, 1948, "A Mathematical Theory of Communication", тому інколи називають "Shannon's entropy".

За означенням:

$H(\xi) = - \sum_{i=1}^n p_i*\log_{b}p_i$

де p_i - розподіл випадкової величини ξ.

Ентропія є математичним сподіванням інформаційної ємності, взятим з протилежним знаком; залежить тільки від розподілу ймовірності. Ентропія показує невизначеність випадкової величини. При отриманні інформації невизначеність зменшується. Коли невизначеності нема - ентропія нульова: отримана інформація не є новою.

$H(\xi) \ge 0; H(\xi) = 0 \Leftrightarrow \exists i: p_i = 1$

При рівномірному розподілі приймає значення log_bn.

Одне з використань: як характеристика алгоритмів стискання інформації.

Сумісна ентропія

ξ − x_i

η − y_i

p_ij = p(ξ = x_i,η = y_j) = p(ξ = x_i / η = y_j) * p(η = y_j)

$H(\xi, \eta) = - \sum_{i,j}^n p_{ij}*\log p_{ij} \,\!$ $= - \sum_{i,j}^n p(x_i / y_j)p(y_j)(\log p(x_i / y_j) + \log p(y_j))$ $= - \sum_{i,j}^n p(x_i / y_j) p(y_j) \log p(x_i / y_j) - \sum_{i,j}^n p(x_i / y_j) p(y_j) \log p(y_j)$ $= H_{\eta}(\xi) - \sum_{j}^n \sum_{i}^n p(x_i / y_j) p(y_j) \log p(y_j)$ $= \vert \sum_{i=1}^n p(x_i / y_j) = 1 \vert = H_{\eta}(\xi) + H(\eta)$

Якщо ξ,η незалежні: H(ξ,η) = H(ξ) + H(η)

Умовна ентропія

$H_{\eta}(\xi) = - \sum_{i,j}^n p(x_i / y_j) p(y_j) \log p(x_i / y_j)$

H_ξ(η) ≤ H(η)

Застосувати нерівність Йенсена з такими значеннями:

y = − x * log₂x

λ_i = p(x_i)

x_i = p(y_j / x_i)

Тоді $\forall j \in [1,n]:$

$\sum_{i=1}^n p(x_i) (-p(y_j / x_i) \log_2 p(y_j / x_i)) \le -\sum_{i=1}^n p(x_i) p(y_j / x_i) * \log_2 \sum_{i=1}^n p(x_i) p(y_j / x_i)$

$\sum_{i=1}^n p(x_i) (-p(y_j / x_i) \log_2 p(y_j / x_i)) \le -\sum_{i=1}^n p(x_i, y_j) * \log_2 \sum_{i=1}^n p(x_i, y_j)$

$\sum_{i=1}^n p(x_i) (-p(y_j / x_i) \log_2 p(y_j / x_i)) \le -q_j * \log_2 q_j$

Просумуємо всі нерівності по j:

$\sum_{j=1}^n \sum_{i=1}^n p(x_i) (-p(y_j / x_i) \log_2 p(y_j / x_i)) \le -\sum_{j=1}^n q_j * \log_2 q_j$

$H_{\xi}(\eta) \le H(\eta)$

Назва

Термін “ентропія” був використаний Шенноном за аналогією з ентропією в статистичній термодинаміці, де ентропія є функцією всіх можливих станів термодинамічної системи. За формулою Больцмана ентропія має вигляд:

S = − k	∑	PilnPi
	i

k - стала Больцмана, P_i - розподіл ймовірностей перебування системи у стані i. Різниця: ентропія Больцмана вводиться для термодинамічних систем, ентропія Шеннона - для будь-якої випадкової величини.

Landauer principle

each erasure of a bit, or other logical 2:1 mapping of the state of a physical computer, increases the entropy of its environment by klog2