Математика EN

Тренажёры · Глава 50

Энтропия, коды и цепи

Сколько информации в исходе, энтропия Шеннона, средняя длина кода и код Хаффмана, доля времени, которую цепь Маркова проводит в каждом состоянии.

Как решать

Чем неожиданнее исход, тем больше информации он несёт: исход с вероятностью $\frac{1}{8}$ — это $3$ бита, как три ответа «да/нет». Энтропия — средняя информация на исход, и она же — нижняя граница средней длины любого кода: короче сжать без потерь нельзя.

По шагам

  1. Информация исхода с вероятностью $p$: $\log_2 \frac{1}{p}$ бит.
  2. Энтропия — среднее с весами: $H = \sum p_i \log_2 \frac{1}{p_i}$.
  3. Средняя длина кода — $\sum p_i \ell_i$, где $\ell_i$ — длина кода буквы.
  4. Код Хаффмана: два самых редких символа объединяйте в один с суммарной вероятностью, пока не останется один. Длина кода символа — сколько раз он участвовал в объединениях.
  5. Цепь Маркова: в равновесии поток из каждого состояния равен потоку в него.
Вероятности исходов, в сумме $1$. Пример: $\left(\frac{1}{4}, \frac{1}{4}, \frac{1}{4}, \frac{1}{8}, \frac{1}{8}\right)$: $3 \cdot \frac{1}{4} \cdot 2 + 2 \cdot \frac{1}{8} \cdot 3 = \frac{3}{2} + \frac{3}{4} = \frac{9}{4}$ бита.

Где ошибаются

  • Берут $\log_2 p$ без минуса или без перевёрнутой дроби — энтропия не бывает отрицательной.
  • В средней длине кода складывают длины без весов: частые буквы считаются чаще.
  • В Хаффмане объединяют самые частые символы, а не самые редкие.
  • В цепи Маркова путают вероятность перехода и долю времени в состоянии.

Пример

Математика

Главы курса

Вступление

  1. 0 Что такое математика

I Числа

  1. 1 Счёт
  2. 2 Ноль и минус
  3. 3 Простые числа
  4. 4 Делимость
  5. 5 Дроби
  6. 6 Корень из двух

II Алгебра

  1. 7 Буквы
  2. 8 Уравнения
  3. 9 Функции и графики
  4. 10 Квадратные уравнения
  5. 11 Системы и неравенства
  6. 12 Степени и логарифмы
  7. 13 Последовательности
  8. 14 Многочлены
  9. 15 Комплексные числа

III Геометрия

  1. 16 Начала Евклида
  2. 17 Треугольник
  3. 18 Теорема Пифагора
  4. 19 Окружность и π
  5. 20 Площадь и объём
  6. 21 Тригонометрия
  7. 22 Векторы
  8. 23 Симметрия
  9. 24 Конические сечения

IV Анализ

  1. 25 Пределы
  2. 26 Производная
  3. 27 Экстремумы
  4. 28 Интеграл
  5. 29 Число e
  6. 30 Ряды
  7. 31 Дифференциальные уравнения
  8. 32 Многие переменные
  9. 33 Ряды Фурье
  10. 34 Комплексный анализ

V Линейная алгебра

  1. 35 Матрицы
  2. 36 Метод Гаусса
  3. 37 Векторные пространства
  4. 38 Собственные векторы
  5. 39 МНК и SVD

VI Структуры

  1. 40 Группы
  2. 41 Остатки и шифры
  3. 42 Кольца и поля
  4. 43 Теория Галуа
  5. 44 Дзета и кривые

VII Случай и данные

  1. 45 Комбинаторика
  2. 46 Графы
  3. 47 Вероятность
  4. 48 Случайные величины
  5. 49 Статистика
  6. 50 Марков и информация

VIII Основания

  1. 51 Логика и множества
  2. 52 Бесконечности
  3. 53 Строгий анализ
  4. 54 Мера и интеграл
  5. 55 Функциональный анализ
  6. 56 Гёдель и Тьюринг

IX Горизонты

  1. 57 Топология
  2. 58 Неевклидовы геометрии
  3. 59 Хаос и фракталы
  4. 60 Передний край