Вероятностный симплекс
Распределение вероятности на 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) максимизируется равномерным выходным распределением. При БСК равномерный вход дает равномерный выход. Любое другое входное распределение делает 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).
Для БСК: 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)) для БСК с 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(source). При D, увеличивающемся, R(D) → 0.
Геометрически: R(D) прочерчивает кривую на плоскости (скорость, искажение). Каждая достижимая пара (R, D) лежит на кривой или выше. Точки ниже кривой невозможны — вы не можете сжать ниже фундаментального предела при любом уровне искажения.
Теорема скорости-искажения (Шеннон, 1959): для любого R > R(D) существуют коды, достигающие ожидаемого искажения максимум D. Для R < R(D): ни один код не достигает ожидаемого искажения D. Кривая — это геометрическая граница в пространстве (скорость, искажение).