Теоретик сложности получил премию Абеля за 2014 год


Премию Абеля иногда называют Нобелевской премией по математике, но также и медалью Филдса. Хорошая новость в этом году заключается в том, что получатель, Яков Г. Синай, известен своей работой в области вычислительной сложности.

Норвежская академия наук и литературы учредила премию Абеля в размере 6 миллионов норвежских крон (около 1 миллиона долларов США) в 2003 году.

В этом году она была присуждена Якову Г. Синаю «за фундаментальный вклад в динамические системы, эргодическую теорию и математическую физику».

Первым вкладом Синая было изучение эргодических систем.

Вас может простить вопрос «какие системы»? Мы часто делаем предположение, что наблюдение чего-либо в одной системе — это то же самое, что наблюдение во многих системах одного и того же типа. Например, если у вас есть физический генератор случайных чисел, вы обычно предполагаете, что его включение и измерение среднего значения данных, которые он производит, даст вам тот же ответ, если вы включили и выключили его много раз и измерили среднее значение. каждой произведенной серии. Вы предполагаете, что генератор случайных чисел является «эргодическим», потому что вы полагаете, что его включение и выключение не влияет на характер его случайности, и, следовательно, измерение одного ряда для среднего значения аналогично измерению множества серий, которые он производит.

Они все одинаковые, так чего волноваться?

Но многие процессы не эргодичны. Например, предположим, что у нас есть два генератора случайных чисел, один из которых производит числа со средним значением 1, а другой — со средним значением -1. Предположим, что то, что мы получим, одинаково вероятно, когда мы включим машину. Теперь вы видите, что у вас больше нет эргодического процесса. Если вы включите и измеряете в течение долгого времени, вы обнаружите, что процесс имеет среднее значение либо 1, либо -1, но если вы включаете и выключаете и измеряете много серий, вы обнаружите, что среднее значение равно нулю (потому что вы получаете -1 и +1 одинаково часто).

Это также различие, которое физики проводят между измерением величины во всех возможных состояниях и измерением ее во времени. Эти двое дают одинаковый ответ, если все возможные состояния появляются в эволюции системы с равной вероятностью.

Например, можете ли вы узнать все, что вам нужно знать о людях, наблюдая за одним человеком на протяжении всей его жизни, или вам нужно наблюдать за всеми людьми? Люди, вероятно, не эргодичны.

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

Эргодические системы — это системы, которые в некотором смысле тщательно перемешаны и как таковые имеют сходство с хаотическими системами.

Еще одна вещь, за которую мы можем поблагодарить Синай, — это игра в бильярд. Если бильярдный шар постоянно катится по столу, является ли система эргодичной?

Обычно ответ отрицательный, потому что обычно существуют периодические решения. То есть вы можете найти начальный угол, который заставляет мяч отскакивать по одному и тому же повторяющемуся пути навсегда — представьте, что вы просто запускаете мяч под прямым углом к подушке, где он вечно отскакивает назад и вперед по одному и тому же пути. Ясно, что это нетипично, и любая статистика, которую вы вычисляете на основе этой части поведения, не будет типичной для всего поведения системы.

Игра в бильярд на Синае отличается тем, что делает ее эргодичной, и это была одна из первых динамических систем, эргодичность которых была доказана. Отличие в том, что в динамическом бильярде в центре стола находится круглый отражатель.

Предоставлено: Г. Stamatiou на основе данных пользователя википедии XaosBits

Теперь попробуйте получить повторяющийся отскок!

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

Связь между эргодическим и хаотическим становится еще сильнее в следующем большом сочинении Синая с Колмогоровым. Вместе им удалось обобщить понятие энтропии для измерения непредсказуемости динамических систем. Энтропия Колмогорова-Синая KS равна нулю, если система совершенно предсказуема, и отлична от нуля для систем, которые становятся все более непредсказуемыми вплоть до хаотических систем. Позже связь между энтропией КШ и «классическим» показателем Ляпунова была доказана теоремой Песина.

Конечно, это всего лишь введение, часть работы, за которую отвечает Синай. Его имя связано с рядом новых концепций и теорем, им опубликовано более 250 статей. Однако более чем вероятно, что его работа будет иметь еще больший эффект после того, как будет доведена до сведения более широкого сообщества.


Добавить комментарий