Теория информации

Claude Shannon дал такое определение информации:

Случайный источник

Концепция неограниченного источника "экспериментов"; тоже вероятностное пространство.

Энтропия Шеннона

Единственная формула для количества информации.

Пусть - случайный источник - энтропия

( - random sources, все корректные распределения вероятности в случайных источниках)

Рассмотрим частный случай для
Определим для него

Тогда свойства энтропии Шеннона:

1. - монотонность энтропии
2. Рассмотрим вер. пр-во:
   
   
   
   Тогда число элементарных исходов
   
   
   Пусть у случайного источника "сломался дисплей" и он выдаёт только первый компонент пары. Тогда этот "сломанный" случайный источник эквивалентен случайному источнику с распределением вероятности . Количество информации -
   Теперь "открываем" вторую компоненту. Тогда количество информации полученное на втором шаге:
   Теперь проведём эксперимент "разом", получив информации Это называется аддитивностью энтропии.
3. Для фиксированного , - непрерывная как функция

Теорема

Лемма 1

Доказательство

Зафиксируем константу

Лемма 2

Лемма 1

Лемма 3

Рассмотрим

❗

Докажем Теорему для

- бит

Что если перенести количество информации со случайного источника на что-то детерминированное?

1. Это не корректный перенос
2. Если перенести на данные похожие на случайные, будет что-то содержательное

Пусть
- кол-во в

Проводим экспериментов и результаты записываем в строку:

Вспомним арифметическое кодирование:

- длина арифметического кодирования

Теорема

Длина кода который получается для строки после арифметического кодирования не превышает энтропии Шеннона для случайного источника с частотами равными долям вхождения в строку.

Хуже всего сжимаются случайные строки Арифметическое кодирование оптимально если можно учитывать только количество вхождений символов

Нижняя оценка для сортировки

Утверждение - из 1 сравнений 1 бита информации