книги / Математическая теория энтропии

GIAN-CARLO ROTA, Editor

ENCYCLOPEDIA OF MATHEMATICS AND ITS APPLICATIONS

Volume 12

Section: R-eal Variables

James K. Brooks, Section Editor

Mathematical Theory of

Entropy

1981

Addison-Wesley Publishing Company

Advanced Book Program

Reading, Massachusetts

London • Amsterdam • Don Mills, Ontario'Sydney «Tokyo

>К 22.171 М29

[К 519.24

Мартин Н., Ингленд Дж.

9 Математическая теория энтропии: Пер. с англ.— М.: Мир, 1988. — 350 с., ил.

ISBN 5-03-000005-4

Последовательное и полное изложение математической теории энтропии, на­ писанное известными американскими математиками. Краткое содержание: введе­ ние, энтропия и информация, теорема Шеннона, связь с динамическими системами, применения в топологической динамике и в статистической механике. Книга удачно дополняет имеющуюся на русском языке литературу по данной тематике.

Для математиков-прикладников, физиков-теоретиков, аспирантов и студентов математических специальностей.

Редакция литературы по математическим наукам

©перевод на русский язык,

сдополнениями, «Мир», 1988

ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА

Создание математической теории энтропии — одно из замеча­ тельных достижений математики нашего века. Точные понятия энтропии и информации, появившиеся в конце 40-х годов и утвердившиеся вначале в прикладных областяях, а именно в теории связи (К. Шеннон) и кибернетике (Н. Винер), сразу же подверглись тщательной математической проработке и получили развитие в нескольких новых областях математики. Быстрое, почти мгновенное проникновение этих понятий в различные раз­ делы математики было обусловлено тем, что соответствующий математический аппарат для их анализа был уже подготовлен, и, главное, имелись задачи, словно ожидавшие понятия энтропии в той или иной форме и решенные вскоре с его помощью.

Предлагаемая читателю монография Мартина и Ингленда является достаточно полным и последовательным изложением тех разделов математической теории энтропии, которые связаны с кодированием, динамическими системами, инвариантной мерой, топологической динамикой и др. или коротко — с энтропийной теорией динамических систем. Книга восполняет пробел в оте­ чественной литературе: хотя, как хорошо известно, именно со­ ветским математикам принадлежит заслуга создания и разра­ ботки собственно математической теории энтропии в различных ее аспектах, и хотя в разное время ими опубликованы глубокие

Математическая теория энтропии, в основу которой легли фундаментальные работы Клода Шеннона, была создана тру­ дами выдающихся современных математиков, в первую очередь А. Н. Колмогорова (см. Колмогоров [1987]), а также А. Я. Хинчина, И. М. Гельфанда и их последователей. Эта теория дает замечательный пример плодотворного воздействия прикладных областей на фундаментальные направления математики. В са­ мой же математике она сыграла объединяющую. роль и дала толчок развитию того, что следовало бы назвать «энтропийным

6 Предисловие редактора перевода

мышлением», пронизывающим многие области нашей науки. Под этим мы имеем в виду исследование характеристик и инва­ риантов экспоненциального роста — в самых различных ситуа­ циях. Разумеется, в математике и ранее было немало наблюде­ ний и фактов, свойственных такому мышлению, и даже понятие энтропии лишь с натяжкой можно было считать новым, однако нет сомнений, что именно работы К. Шеннона и А. Н. Колмого­ рова и их продолжателей сформировали единый энтропийный подход к различным задачам.

В качестве примеров широкого последующего распростра­ нения понятия энтропии можно привести циклы работ: по е-эн- тропии компактов в функциональных пространствах и связан­ ные с этим работы по аппроксимации, табулированию, суперпо­ зициям функций, поперечникам и т. д. (А. Н. Колмогоров^ В. И. Арнольд, А. Г. Витушкин, В. И. Тихомиров и др.), по теории информации (А. Н. Колмогоров, И. М. Гельфанд, А. М. Яглом, Р. Л. Добрушин, М. С. Пинскер и др.), по энтро­ пии в теории сложности и логической теории информации (А: Н. Колмогоров, В. А. Успенский, П. Мартин-Лёф, Л. А. Ле­ вин, А. К. Звонкин и др.), и, может быть, наиболее сущест­ венный— цикл по энтропийной теории динамических систем, чему в основном посвящена настоящая книга и о чем мы скажем далее чуть подробнее (А. Н. Колмогоров, В. А. Рох­ лин, Я. Г. Синай, Д. Орнстейн и др.). В последнее время отчет­ ливо видно, как «энтропийное мышление» проникает в тополо­ гическую динамику, общую алгебру, теорию представлений, ком­ бинаторную математику, теорию сложности, статистическую и квантовую физику и др.

Следует также заметить, что сама энтропийная теория клас­ сических систем к настоящему времени тесно переплелась с другими мощными теориями, появившимися почти одновремен­ но— КАМ-теорией, гиперболической теорией Аносова — Смейла и вместе с ними полностью изменила лицо всейклассической динамики, поставив ее на одно из центральных мест в современ­ ной математике.

В теорию динамических систем энтропия вошла как метри­ ческий инвариант преобразований, сохраняющих меру, опреде­ ленный в основополагающей работе Колмогорова [1958]. В од­ ном из предшествующих обзоров, характеризуя работы К. Шен­ нона, А. Н. Колмогоров писал [1956а]: «Во всяком крупном открытии имеются элементы неожиданности. Этим крупное от­ крытие и отличается от постепенного накапливания результатов текущей научной работы. Подчеркну... качественно новое и не­ ожиданное, что содержится... в теории информации. 1. По перво­ начальному замыслу «информация» не есть скалярная величина. Различные виды информации могут быть чрезвычайно разно­

образны,... было совершенно неясно, можно ли качественно раз­ личные информации... считать эквивалентными... Оказалось, что такая «правильная» по преимуществу мера количества инфор­ мации существует и позволяет решить до конца широкий класс задач...». Хотя это высказывание относилось к шенноновской теории передачи информации, оно едва ли не в большей степени применимо к колмогоровскому понятию энтропии динамической системы, появившемуся годом позже. В самом деле, в начале 30-х годов в фундаментальных работах Купмана и фон Неймана были построены основы спектральной теории динамических систем и определены спектральные инварианты — объекты весь­ ма тонкие, неустойчивые, сложно вычисляемые. После 25 лет успешного развития спектральной теории было трудно предполо­ жить, что появится грубый числовой инвариант, позволяющий столь радикально переустроить всю теорию. Именно таким ин­ вариантом оказалась энтропия. Отметим, что после работ Шен­ нона идея введения энтропии динамических систем высказыва­ лась некоторыми авторами (фон Нейманом по свидетельству С. Какутани, студентом Д. 3. Аровым — см. работу А. Н. Кол­ могорова [69]), однако для проведения ее в жизнь требовался развитый аппарат, который им не был известен и который фактически был использован Колмогоровым. Речь идет о теории измеримых разбиений, разработанной В. А.Рохлиным в 40-х го­ дах. Дело в том, что основным инструментом энтропийной тео­ рии является условная энтропия относительно некоторого раз­ биения, а также последовательности измеримых разбиений; на этом понятии в значительной степени основан технический аппа­ рат и вычисления энтропии. Вообще, как неоднократно подчер­ кивалось, понятие условной энтропии, или количества информа­ ции в одном объекте о другом, важнее, чем понятия безусловной энтропии и информации. Поэтому использование аппарата условных мер здесь неизбежно.

В первой работе Колмогорова [1958] содержалась неболь­ шая неточность, указанная Рохлиным и относящаяся как раз к вычислению энтропии; она оказалась в конце концов несущест­ венной в силу теорем об образующих, доказанных позже, однако во второй работе Колмогорова [69] определение было по необ­ ходимости изменено. Наиболее употребительная форма опреде­ ления энтропии динамических систем была тут же предложена Я. Г. Синаем [142]. Последовавшие затем работы (В. А. Рох­ лин, Я. Г. Синай, Л. М. Абрамов, М. С. Пинскер и др.) были посвящены свойствам энтропии автоморфизмов и потоков, фор­ мулам для энтропии конкретных автоморфизмов и конструк­ ций, аксиоматике энтропии, связям со спектральной теорией

идр. В работах Я. Г. Синая энтропийная теория применялась

кпроблеме слабого изоморфизма, к классической и статиста-

ческой механике, теории геодезических потоков и т. д. В обзо­ рах Рохлина [1960, 1967], Синая [1963а] был подведен итог первому этапу развития энтропийной теории. Читатель может обратиться к более поздним обзЬрам Вершика — Юзвинского [1969], Катка — Синая — Стёпина [1976], книге Перри (Parry [1969]), где можно найти сведения о многих результатах, полу­ ченных позже; большая часть из них вошла в настоящую книгу.

Очень скоро стало лонятно, что важна не только сама по себе энтропия динамической системы, а классы автоморфизмов, выделяемые ею. В частности, после работ Пинскера [117], Рох­ лина— Синая [128] выяснилось, что класс преобразований, для которых энтропия любого нетривиального факторпреобразования‘Положительна, совпадает с классом /(-автоморфизмов (квазирегулярных, как их назвал Колмогоров, или колмогоровских по нынешней терминологии). Сформировавшееся разделение ди­ намических систем на /(-системы й на преобразования с нуле­ вой энтропией отражает в инвариантной форме популярное, но расплывчатое разделение на «стохастические» и «детерминиро­ ванные» системы, принятое в приложениях к механике, физике и др.

Спектральные инварианты не могли различить сдвиги, по­ рожденные схемами Бернулли, поскольку все они имеют один и тот же счетнократный лебеговский спектр; Колмогоров доказал, что энтропия схемы Бернулли равна энтропии соответствующего сдвига и потому является инвариантом динамической системы. Это было первым успешным применением понятия энтропии к давно стоявшей проблеме. Тогда же было понято, что сама по себе проблема метрического изоморфизма динамических систем может рассматриваться как проблема кодирования (вообще го­ воря, не являющегося «односторонним», т. е. физически осущест­ вимым). Вскоре Мешалкин [1959], Блюм и Хансон (Blum, Hanson [1963]), Лившиц [1974] построили нетривиальные при­ меры кодирования схем Бернулли; с одинаковой энтропией. Но оставался открытым вопрос о полной метрической классифика­ ции сдвигов Бернулли и их месте в классе /(-систем. Оба во­ проса-были решены в замечательном цикле работ американского математика Д. Орнстейна в начале 70-х годов. С его именем можно связать следующий этап развития метрической теории динамических систем. Этот этап, как и одновременные исследо­ вания ряда авторов по аппроксимации, являлся по преимуществу уже комбинаторным, а не вероятностным, однако без энтропий­ ной теории он был бы неосуществим. Основные результаты Д. Орнстейна и его последователей приведены в данной книге (см. также монографию Орнстейна [1978]). Наиболее важным оказался результат Орнстейна о том, что в классе автоморфиз­ мов Бернулли энтропия является единственным инвариантом;

тем самым получена классическая по простоте и весьма глубо­ кая теорема Колмогорова — Орнстейна: два сдвига Бернулли метрически изоморфны тогда и только тогда, когда их энтропии совпадают. К сожалению, до сих пор не найдено достаточно простой конструкции зтого изоморфизма и нет условий, гаран­ тирующих существование физически осуществимого изомор­ физма.

Следующий результат Орнстейна состоял в инвариантном описании сдвигов Бернулли с помощью понятия «очень слабой бернуллиевости» и так называемой Я-метрики. Класс «очень слабо бернуллиевских» (ОСБ) процессов оказался новым в теории вероятностей1). Он образует инвариантное относительно любых перекодирований множество стационарных процессов, включающее последовательности независимых одинаково рас­ пределенных случайных величин. Иначе говоря, Орнстейном по­ лучено инвариантное описание предмета классической теории вероятностей — схем Бернулли. Уместно заметить, что Я-метрика есть частный случай транспортной метрики: Канторович [1942], Канторович, Рубинштейн [1958] (см. также Канторович, Акилов [1977]), которая была впервые применена в эргодической теории в работах Вершика [1970, 1976] об убывающих последователь­ ностях измеримых разбиений. Эта метрика неоднократно переоткрывалась; ее использование в теории стационарных процес­ сов приводит к нескольким новым понятиям перемешивания; она интенсивно используется в статистике, статистической фи­ зике и др.

Орнстейн доказал также, что бернуллиевские сдвиги далеко не исчерпывают всех /(-автоморфизмов. Соответствующие при­ меры не встречались в теории динамических систем ранее и вна­ чале были довольно искусственными. Позже, однако, Каликов (Kalikow [1982]) нашел естественные примеры такого рода. В настоящее время эти вопросы далеко продвинуты в работах Орнстейна, Рудольфа, Вейса (Ornstein, Rudolph, Weiss [1982]). Логическое развитие этих идей привело к новым классам дина­ мических систем, в частности к LB (loosely Bernoulli)-системам (смГразд. 4.9). Они возникли в результате обобщения рассмо­ трений Орнстейна, в которых ОСБ-системы описывались с по­ мощью метрики Хемминга и построенной по ней метрики Кан­ торовича (т. е. Я-метрики). Если заменить метрику Хемминга на другую, более слабую, то эта программа приведет нас к LB-системам вместо ОСБ-систем. Это сделано в работах Фельд­

1) Этот термин следовало бы заменить более коротким термином «слабая бернуллиевость», поскольку последний, в том смысле как его ввел Орнстейн, излишен: он равнозначен тому, что в теории случайных процессов называют «абсолютной регулярностью» (см. Ибрагимов, Линник [1965], Ибрагимов, Ро­ занов [1970]).

веден в работе Вершика [1970], он использован для классифи­ кации убывающих последовательностей , измеримых разбиений и вытекающего из нее разделения классов автоморфизмов па характеру аппроксимации (см. Вершик. [1973]). Естественный пример автоморфизма* не принадлежащего классу LB, построен у Ратнер (Ratner [1979]) — это квадрат потока орициклов.

Вернемся к развитию энтропийной темы. Наиболее важное направление исследований в 60—70 гг. было связано с вычис­ лениями и явными формулами для энтропии классических близких к ним динамических систем. Эта тема почти не отра­ жена в книге Мартина и Ингленда. Первое замечание было сде­ лано А. Г. Кушниренко [1965], показавшим, что энтропия глад­ кой динамической системы с гладким интегральным инвариан-' том конечна. К тому времени в серии работ Синая, Рохлина,, Арова, Юзвинского был завершен подсчет энтропии алгебраиче­ ских автоморфизмов компактных групп. Особенно важными для всей этой проблематики оказались формулы для энтропии авто­ морфизмов торов, настолько, что хотелось бы о них вкратце здесь упомянуть. Пусть Т п — м-мерный тор, А — его алгебраи­ ческий автоморфизм, тогда энтропия этого автоморфизма как

автоморфизма А, превосходящим по абсолютной величине еди­ ницу. Отсюда следует, что энтропия положительна для всякого гиперболического автоморфизма тора. Долгий путь связывает эту формулу с общим выражением для энтропии диффеоморфиз­ мов через показатели Ляпунова:

(*) h(T) — ^ £ %,(-»c)dm(x),

мо

где Т — гладкий диффеоморфизм компактного многообразия М> пг — гладкая инвариантная мера, %t (х) — характеристические показатели (показатели Ляпунова) диффеоморфизма Т в точке

множества возможных значений показателей составляет в ос­

ный и важный факт гладкой энтропийной теории, она была пред­ ложена Г. А. Маргулисом и в полном объеме доказана Я. Б. Песиным [1977]. Вообще же связь с теорией показателей и геометрией многообразий изучалась многими авторами (Песин [1981], Ка-

tok [1980а], Ledrappier [1984], Ledrappier, Young [1984, 1985], Lyapunov exponents [1986]). Из формул видно, что энтропия служит мерой экспоненциальной скорости сближения (или разбегания траекторий динамической системы. Само по себе это явление было известно давно, но энтропийная теория дала но­ вый количественный и качественный подход к его анализу. Фак­ тическое вычисление энтропии и, в частности, выделение классов диффеоморфизмов, для которых она пбложительна, еще далеко от завершения. Давно известно, что энтропия положительна для гиперболических систем, в частности, для геодезических потоков на многообразиях неположительной кривизны. Менее ясна си­ туация с геодезическими потоками на многообразиях неотрица­ тельной кривизны. Показатели Ляпунова в этом случае в от­ дельных точках могут быть больше нуля, и тем самым тополо­ гическая энтропия может быть положительной (Мэннинг [1981с]). Неизвестно, однако, может ли быть метрическая эн­ тропия положительной (см. Бураго [1988]). В теории биллиард­ ных потоков (геодезические потоки на многообразиях с краем, газ твердых сфер) формулы для энтропии исследовались Си­ наем, Бунимовичем, Черновым (Синай, Чернов [1982,1987]) идр.

Совсем в ином направлении формула для энтропии обобщена в недавно доказанной «гипотезе об энтропии» (речь идет о то­ пологической энтропии диффеоморфизма — см. статьи в сбор­ нике «Гладкие динамические системы». — М.: Мир, 1974). Ее доказал Иомдин (см. Iomdin [1986], Gromov [1987]):

h ( f ) > In rad

где f есть О-отображение компактного многообразия в себя, /» — индуцированный им эндоморфизм вещественных гомологий, rad — спектральный радиус. Основная идея доказательства этой формулы состоит в том, что энтропия диффеоморфизма может быть оценена через е-энтропию графиков итераций диффеомор­ физма. Такой путь возвращает нас к общим истокам различных понятий энтропии.

Имеются связи формул для энтропии с асимптотикой числа периодических точек, с так называемой е-энтропией мер и др. Топологическая энтропия голоморфных отображений римановой сферы вычислена независимо Громовым (Gromov [1980]) и Любичем (Ljubich [1983]).

Энтропия тесно связана с хаусдорфовой размерностью. Уместно напомнить, что еще в 30—40 годах, в период тщатель­ ного изучения понятия топологической размерности были даны определения размерности через е-энтропию (например, см. [20]). В работах Мэннинга, Ледраппье, Юнг, Лесина (Manning [1981с], Ledrappier [1981], Young [1982, 1984], Pesin [1984]) показатели Ляпунова и энтропия связываются с хаусдорфовой