Симплекс ймовірностей
Розподіл ймовірностей над q символами — це точка в (q−1)-вимірному симплексі: множина всіх векторів (p₁, ..., p_q) з pᵢ ≥ 0 та Σ pᵢ = 1.
Для q = 2: симплекс — це відрізок [0,1], параметризований однією ймовірністю p. Для q = 3: симплекс — рівносторонній трикутник у ℝ². Кожен кут — детермінований розподіл (вся ймовірність на одному символі); центр — рівномірний розподіл.
Ентропія H(p) присвоює дійсне число кожній точці симплексу. Геометрія функції визначає багато фундаментальних результатів.
Увігнутість
H є увігнутою на симплексі: для будь-яких двох розподілів p та q і будь-якого λ ∈ [0,1]:
H(λp + (1−λ)q) ≥ λH(p) + (1−λ)H(q)
Суміш двох розподілів має ентропію щонайменше рівну середньозваженому значенню їх індивідуальних ентропій. Інтуїція: змішування двох джерел збільшує невизначеність.
Перевірка увігнутості
Для бінарної ентропії H(p) увігнутість видна на графіку: крива вигинається вгору, ніколи не падаючи нижче жодної хорди, що з'єднує дві точки.
Формальний тест увігнутості: друга похідна H''(p) ≤ 0 всюди.
H(p) = −p log₂(p) − (1−p) log₂(1−p)
H'(p) = −log₂(p) − 1/ln(2) + log₂(1−p) + 1/ln(2) = log₂((1−p)/p)
H''(p) = −1/(p ln(2)) − 1/((1−p) ln(2)) = −1/(p(1−p) ln(2)) < 0 для всіх p ∈ (0,1)
Друга похідна суворо від'ємна всюди всередині: H строго увігнута.
Розподіл, що досягає пропускної спроможності
Пропускна спроможність каналу визначається як максимальна взаємна інформація над усіма розподілами на вході p(x):
C = max_{p(x)} I(X; Y)
де I(X; Y) = H(Y) − H(Y|X) = H(X) − H(X|Y) = H(X) + H(Y) − H(X,Y).
Для бінарного симетричного каналу з ймовірністю помилки Q: розподіл на вході, що досягає пропускної спроможності, — це рівномірний розподіл p(0) = p(1) = 0.5.
Чому: H(Y) максимізується рівномірним розподілом на виході. Із BSC, рівномірний вхід дає рівномірний вихід. Будь-який інший розподіл на вході робить H(Y) менше, зменшуючи I(X;Y).
Геометрично: взаємна інформація I(X;Y) — увігнута функція розподілу на вході p(x) на симплексі. Максимум увігнутої функції на опуклій множині досягається в унікальній точці (центр, для симетричного каналу).
Дивергенція Кульбака-Лейблера
Дивергенція Кульбака-Лейблера (відносна ентропія) від розподілу q до розподілу p:
D(p || q) = Σᵢ pᵢ log₂(pᵢ/qᵢ)
D(p || q) ≥ 0 завжди (нерівність Гіббса). D(p || q) = 0 тоді й тільки тоді, коли p = q.
D не є справжньою відстанню: вона асиметрична (D(p||q) ≠ D(q||p) в загальному) та не задовольняє нерівність трикутника. Але вона діє як міра того, як далеко p від q у просторі ймовірностей.
Дивергенція Кульбака-Лейблера з'являється скрізь в інформаційній теорії:
- Взаємна інформація: I(X;Y) = D(p(x,y) || p(x)p(y)). Взаємна інформація — це дивергенція Кульбака-Лейблера між спільним розподілом та добутком маргіналів — як далеко спільний розподіл від незалежності.
- Нерівність Гіббса: теорема про кодування без шумів випливає прямо з D(p || q) ≥ 0.
- Пропускна спроможність каналу: C = max_{p(x)} I(X;Y) = max_{p(x)} D(p(x,y) || p(x)p(y)).
Обчислення дивергенції Кульбака-Лейблера
Приклад: p = (0.5, 0.5) рівномірний бінарний, q = (0.8, 0.2) зміщений бінарний.
D(p || q) = 0.5 log₂(0.5/0.8) + 0.5 log₂(0.5/0.2)
= 0.5 log₂(0.625) + 0.5 log₂(2.5)
≈ 0.5 × (−0.678) + 0.5 × 1.322 ≈ −0.339 + 0.661 ≈ 0.322 біт
Пропускна спроможність каналу як геометрична відстань
Пропускна спроможність каналу має геометричне тлумачення у просторі розподілів ймовірностей.
Для каналу p(y|x) визначте розподіл на вході, що досягає пропускної спроможності p*(x). Пропускна спроможність задовольняє:
C = D(p*(y) || r(y))
де p(y) = Σ p(x) p(y|x) — розподіл на виході під оптимальним входом, та r(y) = argmin_r max_x D(p(y|x) || r(y)) — розподіл на виході з мінімальною інформацією — точка у просторі розподілів на виході найближча (у дивергенції Кульбака-Лейблера) до всіх умовних розподілів на виході одночасно.
Це інформаційно-геометричний вид: пропускна спроможність каналу — це радіус найменшої кулі дивергенції Кульбака-Лейблера у просторі розподілів на виході, що містить усі умовні розподіли p(y|x=0) та p(y|x=1).
Для BSC: p(y|x=0) = (1−Q, Q) та p(y|x=1) = (Q, 1−Q). За симетрією, розподіл на виході з мінімальною інформацією r(y) = (0.5, 0.5). Пропускна спроможність = D((1−Q, Q) || (0.5, 0.5)) = 1 − H(Q). Формула повертає стандартний результат з геометрії.
Пропускна спроможність з дивергенції Кульбака-Лейблера
Перевірте геометричну формулу: C = D(p(y|x=0) || r(y)) для BSC з Q = 0.1, r(y) = (0.5, 0.5).
p(y|x=0) = (0.9, 0.1) (надіслано 0, отримано 0 з імовірністю 0.9, отримано 1 з імовірністю 0.1).
D((0.9, 0.1) || (0.5, 0.5)) = 0.9 log₂(0.9/0.5) + 0.1 log₂(0.1/0.5)
= 0.9 log₂(1.8) + 0.1 log₂(0.2)
log₂(1.8) ≈ 0.848, log₂(0.2) ≈ −2.322
= 0.9×0.848 + 0.1×(−2.322) ≈ 0.763 − 0.232 ≈ 0.531 біт
Перевірка: C = 1 − H(0.1) ≈ 1 − 0.469 = 0.531 біт ✓
Швидкість-спотворення та межи стиску
Теорія швидкості-спотворення розширює інформаційну теорію на втратний стиск. Замість запитання 'яка мінімальна кількість бітів для точного представлення джерела?' вона запитує: 'дано терпимість до деякого середнього спотворення D, яка мінімальна швидкість R(D) біт на символ?'
Функція швидкості-спотворення R(D) опукла та спадна за D: більша терпимість до спотворення дозволяє нижчі швидкості. При D = 0 (без втрат): R(0) = H(джерело). З ростом D, R(D) → 0.
Геометрично: R(D) проводить криву на площині (швидкість, спотворення). Кожна досяжна пара (R, D) лежить на цій кривій або вище неї. Точки нижче кривої неможливі — ви не можете стискати нижче фундаментальної межи при будь-якому рівні спотворення.
Теорема про швидкість-спотворення (Шеннон, 1959): для будь-якого R > R(D), існують коди, що досягають очікуваного спотворення щонайменше D. Для R < R(D): жоден код не досягає очікуваного спотворення D. Крива — геометрична границя у просторі (швидкість, спотворення).