Теория информации для миллионов

В издательстве Альпина нон-фикшн вышел перевод книги Бена Орлина «Математические игры с дурацкими рисунками: 75¼ простых, но требующих сообразительности игр, в которые можно играть где угодно». IQ.HSE публикует из неё фрагмент, посвящённый информационным играм — с его помощью можно легко и весело объяснить теорию информации даже младшему школьнику!

В детстве я жил по соседству с Клодом Шенноном — его дом был в километре от моего. Мы никогда не виделись (виной тому разница в возрасте, ведь я на 61 год младше), а жаль, потому что его жилище было прямо-таки музеем чудных изобретений. Целый парк одноколесных велосипедов. Музыкальная труба-огнемёт. Робот-жонглёр. Калькулятор с римскими цифрами. Больше всего мне нравится «Абсолютно бесполезная машина»: если повернуть тумблер на коробке в положение ВКЛ, оттуда высунется механическая рука и меланхолично повернет его обратно в положение ВЫКЛ — своего рода кнопка экзистенциального энергосбережения.

Вы можете полюбоваться на величайшее изобретение Клода, если просто введёте в поисковую строку название его статьи 1948 года «Математическая теория связи». Эта статья революционным образом изменила электронные сообщения и превратила нечёткое понятие «информация» в точную, измеримую величину.

Эта статья дала начало теории информации.

Теории информации безразлично, что именно она передаёт, как и линейке всё равно, что именно она измеряет. Клод объяснял: «“Значение” сообщения, как правило, несущественно». Мы воспринимаем каждое сообщение как одно из возможных. Чем больше возможностей для выбора, тем больше информации передаётся, когда выбор сделан. Информация в сообщении определяется тем, что вы могли бы сказать, но не сказали.

Это не так безумно, как кажется. Если ваша подруга Темнила всегда говорит: «У меня всё хорошо», как бы она себя ни чувствовала на самом деле, то её высказывание не содержит никакой информации. И наоборот, если ваша подруга Честнова всегда говорит правду, её фраза «У меня всё хорошо» передаёт информацию, потому что она выбрала именно это утверждение из всех возможных.

Таким образом, одно и то же сообщение может передавать разный объем информации в зависимости от контекста. Если вы скажете: «Мне нравятся черепахи» — в ответ на мой вопрос: «Тебе нравятся черепахи?», я узнаю о вас не слишком много в том смысле, что альтернатива тут всего одна — признаться в нелюбви к черепахам. А вот фраза «Мне нравятся черепахи» в ответ на вопрос: «Расскажите о себе», гораздо более информативна. Ведь вы могли сказать что угодно.

Как перейти от интуитивного понимания к количественной оценке? Для начала пронумеруем все возможные сообщения, используя двоичное исчисление. По сути, мы превращаем сообщение в код из нулей и единиц. Если сообщений не очень много, можно обойтись короткими кодами. Таким образом, чем меньше требуется цифр, тем меньше информации передается.

И наоборот: если вариантов сообщений много, потребуются длинные коды. Таким образом, чем больше требуется цифр, тем больше информации передается.

Так появилась основная единица информации в теории Клода: цифра в двоичной записи, или «бит».

Чтобы увидеть биты в действии, давайте посмотрим, как они накапливаются, когда мы играем в классическую игру со скрытой информацией — «Виселица». Я воспользуюсь словарём для игры в скрабл Collins Scrabble. В нём около 280 000 слов. Чтобы их пронумеровать, нужны 18‑значные двоичные коды (и несколько 19‑значных кодов). Таким образом, с точки зрения Клода, угадать слово — значит получить примерно 18,09 бита информации. Для сравнения: это примерно в миллион раз меньше, чем «весит» цифровая фотография в хорошем разрешении.

Теперь предположим, что противник загадал слово из семи букв. Это сужает область поиска: таких слов около 34 000. Мы можем пронумеровать их с помощью 15‑значных кодов (плюс несколько 16‑значных), поэтому нам осталось собрать 15,2 бита информации.

Это означает, что информация, которую мы только что получили (количество букв в слове), составляет чуть меньше трех битов.

А теперь давайте угадаем первую букву. Мне нравится начинать с E. Ого, хорошие новости!

Поле поисков сузилось до менее чем 10 000 слов, что нам ещё 1,8 бита информации. Мы отсеяли уже больше 95% слов. Однако с точки зрения накопления битов всё только началось. Похоже, нужна еще одна гласная. Как насчет А? Увы, плохие новости.

Хотя мы теперь на один шаг ближе к поражению, нам всё-таки удалось добыть информацию и отсеять 3500 слов. Это даёт 0,6 бита.

Возможно, последняя буква — D? Оказывается, нет.

Тем не менее прогресс есть. Мы сузили поле поисков ещё на 2600 слов, что даёт 0,8 бита. Я снова подбираю букву. Как насчёт S? Ого, вы только посмотрите!

Мои ожидания не вполне оправдались, но результат хороший. Мы получили 2,8 бита информации — лучший ход на данный момент. Но нам нужна ещё одна гласная. Как насчет I?

Ай да я! Угадал.

Мы получили ещё 2,8 бита информации. Осталось всего несколько десятков возможных слов.

Похоже, нам опять нужна гласная. Как насчет О? Увы, нет!

Мы допустили третью ошибку и добыли всего лишь 0,6 бита. Попробуем другую гласную. U? В точку!

Мы заработали ещё 1,8 бита, а количество возможных вариантов сузилось до 15 слов. Теперь можно снова сосредоточиться на последней букве. Может N? А вот и нет.

Мы отсекли всего три слова, и это принесло скудные 0,3 бита информации. Попробуем ещё раз. Как насчёт R? Ого, повезло!

Таким образом, количество вариантов сократилось с дюжины до трёх, и мы получили ровно 2 бита информации. Как насчёт P? Нет, плохая попытка.

Поскольку слова surpier не существует, мы никуда не продвинулись и получили 0 битов информации. Будем осторожнее. Как насчёт F? Вновь неудача.

Тем не менее мы получили 0,6 бита информации, так как отсеяли один из трёх вариантов. Осталось два. Нам не хватает 1 бита информации. Попробуем L? Ура! Мы победили.

Ладно, на сегодня всё с играми в слова. Возвращаемся к математическим играм. Каждый раз для победы в них требуется получить верную информацию. В каждом случае один игрок стремится скрыть как можно больше информации, а другой — урвать как можно больше битов.

Информационные игры — интрига в чистом виде. Это детективные романы, действие которых разворачивается в реальном времени.

Что подумал бы мой бывший сосед Клод, если бы узнал, что его великая теория используется в таких легкомысленных целях? Уверен, ему бы понравилось. «История науки показала, что простое любопытство часто имеет ценные последствия», — однажды сказал он. Кому это знать, как не Клоду. Работая в Bell Labs, он проводил целые дни в рекреации за настольными играми. Его шеф сказал, что Клод «заслужил право быть непродуктивным».
IQ