Цепи Маркова

Цепи Маркова

Пример марковской цепи с двумя состояниями и вероятностями переходов.

Область науки

Теория вероятностей; теория случайных процессов

Становление

1906-1907 годы; дальнейшее развитие в XX веке

Разновидность

Научное понятие

Вид

Модель

Исследователи

Андрей Андреевич Марков

Ключевые публикации

Работы А. А. Маркова 1906, 1907 и 1913 годов

Формулировка

Вероятности следующего состояния определяются текущим состоянием, а не всей предшествующей последовательностью.

Цепи Маркова - класс стохастических моделей, в которых вероятностное распределение следующего состояния системы определяется её текущим состоянием. Они получили имя русского математика Андрея Андреевича Маркова, который в начале XX века начал систематически исследовать последовательности зависимых случайных величин и показал, что статистическая закономерность не требует полной независимости отдельных испытаний.

Андрей Андреевич Марков. Фотография 1886 года.

История цепей Маркова важна далеко за пределами одной математической конструкции. Она показывает, как менялось само понимание случайности. Классическая теория вероятностей XVII-XIX веков особенно успешно работала с независимыми испытаниями - бросками монеты и игральной кости, извлечением шаров из урны, повторением одного и того же опыта. Марков поставил другой вопрос: что происходит, если случайные события связаны между собой? Можно ли обнаружить устойчивую закономерность там, где каждый следующий результат зависит от предыдущего?

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

Одним из самых знаменитых ранних примеров Марков сделал сам. В 1913 году он исследовал последовательность из 20 000 букв пушкинского «Евгения Онегина», разделяя буквы на гласные и согласные и измеряя зависимость следующего элемента от предыдущего. Весь подсчёт производился задолго до компьютеров. Литературный текст стал для математика массивом наблюдений, на котором можно было показать работу теории зависимых испытаний.

Почему работы Маркова оказались столь важны

Историческое значение работ Маркова выходит далеко за пределы названного его именем частного математического объекта.

До Маркова важнейшие предельные результаты теории вероятностей формулировались прежде всего для независимых случайных величин. Независимость была чрезвычайно удобным условием: прошлый результат не изменял вероятность будущего. В такой модели отдельные события случайны, но при большом числе повторений появляется устойчивая статистическая закономерность.

Марков показал принципиально более широкую возможность. Зависимость между случайными событиями сама по себе не уничтожает статистической закономерности. Можно построить последовательность, в которой результат очередного шага зависит от предыдущего, и всё же получить закон больших чисел и другие устойчивые свойства. Историки теории вероятностей связывают его исследования цепной зависимости в том числе с полемикой вокруг утверждений Павла Некрасова о необходимости независимости для закона больших чисел.

Это меняло саму границу предмета теории вероятностей. Случайность переставала быть почти синонимом независимости.

Второе значение состояло в переходе от исследования отдельного события к исследованию случайного процесса. Классический вопрос звучал: «Какова вероятность такого-то исхода?» В марковской постановке появляется другой вопрос: «Как вероятностная система изменяется во времени?»

Объектом исследования становилась последовательность состояний:

состояние 1 → состояние 2 → состояние 3 → состояние 4 → …

Система могла менять состояние случайным образом, но вероятности переходов подчинялись определённым правилам.

Третье значение связано с понятием состояния. Если текущее состояние системы содержит всю информацию, необходимую для вероятностного описания следующего шага, более раннюю историю можно не учитывать непосредственно. В современной терминологии это называют марковским свойством. Encyclopedia of Mathematics формулирует его как условную независимость будущего и прошлого при известном настоящем.

Такой подход оказался чрезвычайно продуктивен в моделировании. Вместо попытки хранить всю историю сложной системы можно выделить набор состояний и определить вероятности перехода между ними.

Четвёртое значение стало особенно очевидным позднее. Работы Маркова оказались одним из исходных пунктов общей теории случайных процессов. В 1920-1930-е годы вероятностную динамику развивали Норберт Винер, Андрей Колмогоров и другие математики. Возникли теория непрерывных марковских процессов, уравнения Колмогорова, строгие модели диффузии и современная стохастика.

Наконец, марковская идея стала одним из важнейших инструментов вычислительной эпохи. Она вошла в теорию информации, моделирование языка, скрытые марковские модели, методы Монте-Карло, ранжирование сетей и множество алгоритмов.

Историческое значение Маркова можно свести к нескольким изменениям:

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

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

Предыстория: случайность и закономерность

Истоки задачи уходят в XVII-XVIII века, когда формировалась классическая теория вероятностей. Блез Паскаль, Пьер Ферма, Христиан Гюйгенс, Якоб Бернулли и другие исследователи создавали математический язык для описания случайных событий, прежде всего на материале азартных игр.

Якоб Бернулли. Портрет 1687 года.

Особое значение имела книга Якоба Бернулли Ars Conjectandi - «Искусство предположений», опубликованная посмертно в Базеле в 1713 году. В ней содержался результат, ставший одним из истоков закона больших чисел.

Страница Ars Conjectandi Якоба Бернулли, 1713 год.

Его смысл можно показать на простом примере. Один бросок правильной монеты непредсказуем: выпадет орёл или решка. Но если бросить монету тысячи раз, доля выпадений орла обычно оказывается близка к $\frac{1}{2}$. Чем больше число независимых испытаний, тем устойчивее относительная частота результата.

Так возник один из фундаментальных принципов вероятностного мышления:

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

Для XVIII века это было глубокое открытие. Теория вероятностей показывала, что случайность не означает отсутствия математического порядка.

От игр к обществу

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

Особую роль сыграл бельгийский астроном и статистик Адольф Кетле. В 1830-е годы он развивал концепцию «социальной физики» и идею «среднего человека». Для Кетле устойчивость массовой статистики означала возможность обнаруживать закономерности даже в области человеческого поведения.

Так возникал философский вопрос: если отдельные люди действуют по собственной воле, почему их совокупное поведение обнаруживает статистическую устойчивость?

Для истории цепей Маркова эта дискуссия важна потому, что в конце XIX - начале XX века к ней обратился русский математик Павел Алексеевич Некрасов. Юджин Сенета показал, что Некрасов переработал идеи Кетле и придал социальной независимости особое значение как причине статистической регулярности.

Петербургская школа теории вероятностей

Работы Маркова возникли внутри сильной математической традиции Санкт-Петербургского университета.

Пафнутий Львович Чебышёв - учитель Маркова и центральная фигура Петербургской математической школы.

Центральной фигурой этой школы был Пафнутий Львович Чебышёв. Его исследования охватывали теорию чисел, анализ, механику и вероятность. В теории вероятностей Чебышёв разрабатывал методы доказательства предельных теорем и стремился получать строгие результаты при возможно менее жёстких предположениях.

Именно этот стиль - искать минимальные условия, при которых сохраняется общая закономерность, - непосредственно предшествовал работе Маркова.

Марков поступил в Петербургский университет в 1874 году. Среди его преподавателей были Чебышёв, Александр Коркин и Егор Золотарёв. После окончания университета в 1878 году его оставили для подготовки к академической деятельности. После ухода Чебышёва из университета в 1883 году Марков принял чтение его курса теории вероятностей и продолжал преподавать этот предмет много лет.

К Петербургской школе принадлежал и Александр Михайлович Ляпунов. В области вероятностей он работал над центральной предельной теоремой; в других областях математики стал одним из создателей современной теории устойчивости.

Работы Чебышёва, Маркова и Ляпунова превратили Петербург в один из международно значимых центров теории вероятностей. Encyclopedia of Mathematics характеризует Маркова и Ляпунова как главных продолжателей вероятностной школы Чебышёва и подчёркивает их роль в утверждении вероятности как точной математической науки.

Андрей Марков до цепей Маркова

Андрей Андреевич Марков родился в 1856 году в Рязани. Его ранняя научная работа была связана далеко не только с вероятностью. Он занимался теорией чисел, непрерывными дробями, приближением функций и методом моментов.

Докторская диссертация Маркова была посвящена приложениям алгебраических непрерывных дробей. Его избрали адъюнктом Петербургской Академии наук в 1886 году по предложению Чебышёва; в 1890 году он стал экстраординарным академиком, а в 1896 году - ординарным академиком.

В 1900 году вышло первое издание его книги «Исчисление вероятностей». Последующие редакции заметно расширялись. Источники по-разному датируют третье издание 1912 или 1913 годом в зависимости от библиографического описания; оно было связано с двухсотлетием закона больших чисел Бернулли.

Для Маркова исследования зависимых величин были частью более широкой программы развития предельных теорем и методов Чебышёва.

Павел Некрасов и спор о независимости

Особое место в предыстории цепей Маркова занимает Павел Алексеевич Некрасов - профессор Московского университета и представитель Московской математической школы.

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

Его интересовала устойчивость массовых общественных явлений. Продолжая линию, восходящую к Кетле, Некрасов придавал особое значение независимости отдельных человеческих действий. В 1902 году он трактовал социальную независимость как одну из причин статистической регулярности и связывал вопрос с человеческой свободой воли.

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

Полемика была частью более широкого конфликта двух научных традиций и двух темпераментов. Но сводить её к столкновению «атеиста» и «религиозного математика» было бы слишком грубо. Главным оставался математический вопрос:

является ли независимость необходимым условием устойчивой вероятностной закономерности?

Ответ Маркова был отрицательным.

Encyclopedia of Mathematics прямо связывает один из споров Маркова с Некрасовым с появлением концепции цепной зависимости. Казанская работа 1906 года была написана в противовес утверждению Некрасова о необходимости попарной независимости для слабого закона больших чисел.

1906-1907 годы: рождение цепной зависимости

В 1906 году Марков опубликовал работу о распространении закона больших чисел на величины, зависящие друг от друга. В ней впервые появляется направление, из которого позднее выросла теория цепей Маркова.

В 1907 году он продолжил исследование в работе «Исследование замечательного случая зависимых испытаний». Encyclopedia of Mathematics датирует формальное начало изучения последовательностей зависимых испытаний именно 1907 годом.

Здесь полезно различать два близких утверждения. В 1906 году Марков уже формулирует идею цепной зависимости и применяет её для опровержения тезиса о необходимости независимости. В 1907 году появляется более разработанное исследование специального случая зависимых испытаний, которое в современной историографии часто считается отправной точкой собственно теории цепей Маркова.

Классическая схема предполагала независимые испытания. Марков рассматривал последовательность, в которой вероятностный закон очередного результата зависел от предыдущего.

Для простейшего современного примера представим два возможных состояния - А и Б.

Если система сейчас находится в А, вероятности следующего состояния могут быть:

$\text{А}\to \text{А}=\mathrm{0,7}$

$\text{А}\to \text{Б}=\mathrm{0,3}$

Если система находится в Б:

$\text{Б}\to \text{А}=\mathrm{0,4}$

$\text{Б}\to \text{Б}=\mathrm{0,6}$

Следующий результат уже зависит от текущего. Но последовательность остаётся доступной строгому математическому анализу. Именно это было принципиальным расширением классической постановки: устойчивость больших совокупностей не требует, чтобы каждый элемент был совершенно независим от соседних. Encyclopedia of Mathematics отмечает, что Марков доказал закон больших чисел для цепей при условиях, обеспечивающих ослабление зависимости удалённых друг от друга состояний.

Что такое цепь Маркова

В современном языке цепь Маркова - это последовательность случайных состояний, удовлетворяющая марковскому свойству. Если состояния обозначить как $X_0,X_1,X_2,\dots$, то для цепи первого порядка распределение следующего состояния $X_{n+1}$ при известном $X_n$ не зависит дополнительно от $X_{n-1}$, $X_{n-2}$ и более ранней истории. Условно это можно записать:

$$P(X_{n+1}\mid X_n,X_{n-1},\dots ,X_0)=P(X_{n+1}\mid X_n).$$

Эту идею часто пересказывают словами:

«будущее зависит от настоящего, но при известном настоящем не требует знания всего прошлого».

Фраза «цепь не имеет памяти» удобна, но способна вводить в заблуждение. Прошлое может полностью сформировать текущее состояние. Марковское свойство утверждает другое: если настоящее состояние уже известно, дополнительная информация о более ранней истории не меняет вероятностного закона следующего шага.

Состояния и переходы

Чтобы задать конечную цепь Маркова, необходимо определить:

• набор возможных состояний;
• начальное распределение;
• вероятности переходов между состояниями.

Вероятности переходов удобно записывать в матрицу переходов.

Например:

Текущее состояние	Следующее А	Следующее Б
А	0,7	0,3
Б	0,4	0,6

Сумма элементов каждой строки равна единице.

Графически ту же систему можно представить вершинами-состояниями и стрелками, показывающими возможные переходы.

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

Марковское свойство и правильный выбор состояния

Марковское свойство - не обязательно утверждение о природе системы как таковой. Часто оно зависит от того, как исследователь определил состояние.

Представим автомобиль. Если состоянием считать только его координату, для прогноза следующего положения информации может оказаться недостаточно: важна ещё скорость. Если в состояние включить координату и скорость, модель становится существенно ближе к марковской.

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

найти такое описание настоящего, которое содержит всю информацию, необходимую для вероятностного описания следующего шага.

Именно поэтому марковость в реальных исследованиях часто является не абсолютным свойством объекта, а свойством выбранного способа описания.

Стационарное распределение

Для многих цепей важным оказывается долгосрочное поведение.

Пусть система много раз переходит между состояниями. Начальное положение может сильно влиять на первые несколько шагов, но затем его влияние ослабевает.

При определённых условиях распределение вероятностей стремится к устойчивому состоянию, которое после очередного применения матрицы переходов не меняется. Такое распределение называется стационарным. Если $\pi$ - строка вероятностей состояний, а $P$ - матрица переходов, стационарность можно записать:

$$\pi P=\pi .$$

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

Здесь вновь появляется исходный мотив всей истории: отдельные переходы случайны, но в большой временной перспективе возникает закономерность.

«Евгений Онегин» как математический эксперимент

В 1913 году Марков сделал шаг, благодаря которому абстрактная теория зависимых испытаний получила один из самых запоминающихся примеров в истории математики: он обратился к пушкинскому «Евгению Онегину». 23 января результаты были представлены физико-математическому отделению Императорской Академии наук, а затем опубликованы в «Известиях Императорской Академии наук», VI серия, том 7, № 3, на страницах 153-162.

Александр Пушкин. Портрет Ореста Кипренского, 1827 год.

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

Ручной корпус из 20 000 букв

Марков взял подряд 20 000 русских букв - всю первую главу «Евгения Онегина» и шестнадцать строф второй. Твёрдый и мягкий знаки он исключил из рассматриваемого алфавита; пробелы и знаки препинания отдельными состояниями не считались. Все остальные буквы были сведены к двум категориям - гласным и согласным.

Титульный лист полного издания «Евгения Онегина», Санкт-Петербург, 1833 год.

По реконструкции Дэвида Линка, 20 000 букв Марков разделил на 200 групп по 100 знаков и каждую сотню располагал в квадрате 10 × 10. Подсчёты по строкам и столбцам позволяли видеть не только итоговую частоту гласных, но и её колебания в отдельных участках текста, а затем сравнивать группы, в которых непосредственное соседство букв постепенно разрушалось.

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

Зависимость соседних букв

В исследованной последовательности оказалось 8638 гласных и 11 362 согласные. Общая доля гласных составляла приблизительно 0,432, согласных - 0,568. Если бы тип следующей буквы не зависел от предыдущей, вероятность гласной должна была бы оставаться примерно одинаковой после любого знака. Подсчёт 19 999 соседних пар показал противоположное:

Пара	Число случаев	Условная вероятность
гласная → гласная	1104	0,128
гласная → согласная	7534	0,872
согласная → гласная	7534	0,663
согласная → согласная	3827	0,337

После гласной согласная появлялась примерно в 87 % случаев, тогда как после согласной вероятность гласной возрастала примерно до 66 %. Русский текст демонстрировал сильную тенденцию к чередованию двух классов букв. Общая доля гласных сообщала, как часто они встречаются во всём массиве; цепная модель показывала больше - вероятность следующего элемента менялась вместе с текущим состоянием последовательности.

Пары были только первым приближением

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

Позднейшее изложение его данных показывает, что совпадение было лишь частичным. Для последовательности «согласная - согласная - согласная» простая модель давала относительную частоту около 0,065, тогда как наблюдалось около 0,025; для «гласная - согласная - гласная» ожидалось около 0,250, а наблюдалось около 0,211. В других сочетаниях расхождение было существенно меньше.

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

От Пушкина к Аксакову

Вскоре после пушкинского опыта Марков применил сходный подход к тексту С. Т. Аксакова «Детские годы Багрова-внука». На этот раз объём последовательности составлял уже 100 000 букв - в пять раз больше пушкинского массива. В самом приложении Марков писал, что таблицы должны показать, как и в какой мере на реальном тексте проявляются предельные теоремы теории вероятностей. По реконструкции Дэвида Линка, результаты уже были включены в приложение к третьему русскому изданию «Исчисления вероятностей» 1913 года; версия, воспроизведённая позднее на страницах 577-581 посмертного издания 1924 года, стала источником современного английского перевода.

Переход от 20 000 к 100 000 букв показывает, что литературный текст был для Маркова не случайной эффектной иллюстрацией. Он превращался в экспериментальный материал для исследования больших зависимых последовательностей.

Пушкин как данные

Теория цепной зависимости возникла у Маркова раньше, в 1906-1907 годах; «Евгений Онегин» не был моментом её изобретения. Значение опыта 1913 года состояло в другом: абстрактная теория была впервые применена к большому эмпирическому материалу - тексту.

Для литературоведа «Евгений Онегин» остаётся художественным произведением. Для Маркова в этом опыте он становился последовательностью дискретных наблюдений. Учёный сознательно отбрасывал почти всё, что составляет роман для читателя, и сохранял лишь одну характеристику каждой буквы. Именно радикальное упрощение позволяло выделить вероятностный механизм.

Через несколько десятилетий Клод Шеннон будет показывать, как учёт всё более длинных зависимостей между буквами и словами делает искусственно построенные последовательности всё более похожими на естественный язык. Прямую линию от опыта Маркова к современным нейросетевым языковым моделям проводить нельзя, но исследование 1913 года находится в начале важной традиции: язык рассматривается не только как носитель смысла, но и как последовательность, статистическую структуру которой можно измерять.

1913 год и двухсотлетие закона больших чисел

1913 год символически соединял начало и продолжение одной большой истории.

В 1713 году было опубликовано Ars Conjectandi Якоба Бернулли. Через двести лет в Петербурге отмечали юбилей теоремы Бернулли. Исследователь истории вероятности Юджин Сенета показал, что организацией петербургского празднования занимался Марков и что юбилей непосредственно связан с его работами о законе больших чисел.

Историческая последовательность выглядит особенно ясно:

• 1713 - Бернулли публикует один из основополагающих результатов о статистической устойчивости независимых испытаний;
• XIX век - Чебышёв развивает строгие методы предельной теории;
• 1906-1907 - Марков распространяет исследование на зависимые величины;
• 1913 - Марков демонстрирует цепную зависимость на тексте «Евгения Онегина» и участвует в юбилее Бернулли.

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

Марков как участник научных и общественных конфликтов

Характер Маркова сыграл заметную роль в его научной биографии.

Он был известен резкими полемиками и крайне серьёзным отношением к логической точности аргумента.

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

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

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

В случае Некрасова такой ответ привёл к исследованию зависимых испытаний.

От цепей к случайным процессам

Первоначальные работы Маркова рассматривали сравнительно специальный класс дискретных последовательностей.

Но сама идея оказалась значительно шире.

В XX веке математика всё чаще исследовала системы, состояние которых случайным образом изменяется со временем. Так сформировалась общая теория случайных процессов.

Дискретная цепь Маркова изменяется шаг за шагом.

Но можно рассматривать и процессы, протекающие непрерывно во времени.

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

Если будущее такого процесса при известном текущем состоянии не зависит дополнительно от более далёкого прошлого, процесс называют марковским.

Броуновское движение и Норберт Винер

К важнейшим объектам новой теории относилось броуновское движение.

В 1827 году ботаник Роберт Броун наблюдал беспорядочное движение микроскопических частиц в жидкости. В начале XX века физические основы этого явления исследовали Альберт Эйнштейн и Мариан Смолуховский.

В 1923 году Норберт Винер дал строгую математическую конструкцию процесса, который позднее стал называться винеровским. Encyclopedia of Mathematics отмечает Винера как одного из исследователей, давших математическое обоснование непрерывному марковскому процессу на примере броуновского движения.

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

Колмогоров и общая теория

Огромный следующий шаг сделал Андрей Николаевич Колмогоров.

В 1931 году он опубликовал работу Über die analytischen Methoden in der Wahrscheinlichkeitsrechnung, в которой систематически исследовал непрерывные марковские процессы и получил уравнения для вероятностей перехода. Encyclopedia of Mathematics называет Колмогорова одним из создателей общей теории непрерывновременных марковских процессов.

Через два года, в 1933 году, вышли «Основные понятия теории вероятностей», где Колмогоров дал аксиоматическое построение дисциплины на языке теории меры. Между Марковым и Колмогоровым существует важная линия преемственности. Марков показал, что зависимые случайные величины могут образовывать закономерную последовательность. Колмогоров включил марковские процессы в значительно более общую математическую теорию.

Уравнение Чепмена - Колмогорова

Для марковских процессов фундаментально соотношение, связывающее переход за большой промежуток времени с переходами через промежуточное состояние. Пусть система переходит из состояния $x$ в состояние $z$, проходя через возможные промежуточные состояния $y$. Тогда вероятность общего перехода получается суммированием или интегрированием по всем возможным промежуточным состояниям. В дискретной матричной форме тот же принцип особенно прост: матрица вероятностей перехода за два шага получается умножением одношаговой матрицы саму на себя:

$$P^2=P\cdot P.$$

За $n$ шагов:

$$P^n.$$

Так матричная алгебра позволяет исследовать поведение цепи через большое число переходов. Соотношение получило имя Сидни Чепмена и Андрея Колмогорова.

Случайные блуждания

Одним из простейших и важнейших типов марковских моделей является случайное блуждание.

Представим частицу на числовой прямой. На каждом шаге она с определённой вероятностью перемещается на единицу вправо или влево.

Новое положение зависит от нынешнего положения и случайного выбора направления.

Несмотря на простоту, из этой модели вырастает огромный класс задач.

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

Клод Шеннон и возвращение к языку

Через несколько десятилетий после пушкинского эксперимента Маркова математическая теория снова встретилась с языком. В 1948 году американский математик и инженер Клод Шеннон опубликовал статью A Mathematical Theory of Communication, ставшую основанием современной теории информации. Шеннон рассматривал язык как источник сообщений и показывал, как постепенно учитывать его статистическую структуру. На нулевом уровне символы выбираются независимо и с одинаковой вероятностью - получается почти чистый шум. На следующем уровне символы остаются независимыми, но используются реальные частоты английских букв.

Далее учитываются частоты пар букв, а затем триграмм. После этого Шеннон переходит к словам и вероятностям переходов между словами. С увеличением учитываемой структуры искусственно построенные последовательности начинают всё сильнее напоминать настоящий английский текст.

Здесь возникает выразительная историческая симметрия.

Марков в 1913 году шёл от текста к вероятностной структуре:

реальный текст → последовательность → статистические зависимости.

Шеннон в 1948 году демонстрировал обратное движение:

статистические зависимости → вероятностная генерация → текстоподобная последовательность.

Это не означает, что Шеннон просто продолжил эксперимент Маркова или что между ними существует единственная прямая линия влияния. Но оба эпизода принадлежат одной большой истории математического исследования последовательностей.

Скрытые марковские модели

Следующим важным развитием стали скрытые марковские модели.

В обычной цепи состояние непосредственно известно.

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

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

Во второй половине XX века скрытые марковские модели стали одним из важнейших инструментов автоматического распознавания речи. Позднее они широко применялись в биоинформатике, распознавании образов и анализе последовательностей.

Марковские цепи и компьютерные сети

В конце XX века марковские идеи получили новое применение в анализе сетей. Веб можно представить как граф. Каждая страница - состояние. Гиперссылка - возможность перехода из одного состояния в другое.

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

Это задача о стационарном распределении марковской цепи.

На близкой идее построен PageRank, разработанный Ларри Пейджем и Сергеем Брином при создании Google. Конкретный алгоритм содержит дополнительный механизм случайного перехода на произвольную страницу, позволяющий избежать некоторых проблем структуры графа.

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

Методы Монте-Карло на цепях Маркова

Ещё одно чрезвычайно важное направление - методы Монте-Карло с использованием цепей Маркова, обычно обозначаемые MCMC. Идея состоит в том, чтобы построить цепь Маркова, стационарное распределение которой совпадает с распределением, интересующим исследователя. Затем компьютер генерирует длинную последовательность состояний этой цепи. После переходного периода полученные состояния можно использовать как выборку из сложного распределения, которое трудно исследовать прямым способом. На этом принципе основаны алгоритм Метрополиса - Гастингса, сэмплер Гиббса и множество современных байесовских вычислительных методов. Здесь цепь Маркова превращается уже не только в объект исследования, но и в вычислительный инструмент.

Физика и химия

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

В физике это могут быть:

• столкновения и перемещения частиц;
• диффузионные процессы;
• изменение микросостояний;
• случайное движение на решётках;
• распады и переходы между энергетическими состояниями.

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

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

Марковская модель позволяет связывать эти уровни описания.

Биология и генетика

Последовательности биологических объектов также естественным образом допускают вероятностное моделирование. В генетике состояниями могут быть нуклеотиды, кодоны или более сложные характеристики последовательности. Вероятности переходов используют в моделях мутаций и эволюционных изменений. Скрытые марковские модели особенно активно применялись в биоинформатике конца XX века - например, при распознавании генов и сравнении биологических последовательностей. В популяционной биологии марковские процессы используют для описания рождения, смерти, миграции и изменений численности групп.

Экономика и социальные процессы

Марковские модели применяют и к социально-экономическим системам.

Возможными состояниями могут быть:

• занятость и безработица;
• категории дохода;
• кредитные рейтинги;
• состояния рынка;
• демографические категории;
• миграционные состояния.

При этом важно помнить ограничение модели: реальный социальный процесс вовсе не обязан быть марковским.

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

Здесь возникает любопытная историческая ирония. Цепи Маркова выросли отчасти из критики слишком свободного переноса математических представлений о независимости в область социальных рассуждений. Их современные социальные приложения поэтому особенно требуют проверки предположений модели.

Теория массового обслуживания

Теория массового обслуживания исследует очереди и системы, в которые случайным образом поступают заявки. Это могут быть покупатели, телефонные звонки, пакеты данных, запросы к серверу, автомобили или производственные заказы. Система может находиться в состояниях «0 заявок», «1 заявка», «2 заявки» и так далее. При определённых предположениях переходы между такими состояниями образуют марковский процесс. Эта область стала одним из классических практических применений вероятностной динамики в XX веке.

Цепи Маркова и современные языковые модели

Эксперимент Маркова с «Евгением Онегиным» выглядит поразительно современно. Он исследовал вероятность следующего элемента текста в зависимости от предыдущего.

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

Ограничения марковского подхода

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

• расширить определение состояния;
• использовать цепь более высокого порядка;
• перейти к скрытой марковской модели;
• использовать немарковский процесс;
• применить иной статистический или вычислительный метод.

Таким образом, вопрос «является ли система марковской?» часто невозможно отделить от вопроса «как именно мы описываем её состояние?»

Это принципиально отличает математическую модель от утверждения о буквальном устройстве реальности.

Что изменилось после Маркова

Если рассматривать историю в долгой перспективе, вклад Маркова можно увидеть как один из нескольких крупных переходов в развитии вероятностного мышления. Первый переход совершили математики XVII-XVIII веков: от бытовой неопределённости к вычислимой вероятности. Бернулли показал, как в массе независимых случайных событий возникает устойчивость. Чебышёв и его школа создали более строгие методы исследования предельных закономерностей. Марков сделал следующий шаг: показал, что строгая вероятность способна работать с зависимостью. После него исследование развивающихся во времени случайных систем стало одной из центральных областей математики XX века. Винер связал вероятностные процессы с непрерывным случайным движением. Колмогоров сформировал общую аналитическую и аксиоматическую основу. Шеннон применил вероятностные последовательности к информации и языку. Компьютерная эпоха превратила марковские методы в массовый вычислительный инструмент.

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

Хронология

Год	Событие
1650-е	Паскаль и Ферма обсуждают задачи азартных игр, ставшие одним из истоков математической теории вероятностей.
1713	Посмертно выходит Ars Conjectandi Якоба Бернулли.
1830-е	Адольф Кетле развивает «социальную физику» и исследует устойчивость массовой статистики.
1874	Андрей Марков поступает в Петербургский университет.
1883	Марков принимает университетский курс теории вероятностей после ухода Чебышёва.
1886	Марков избран адъюнктом Петербургской Академии наук.
1896	Марков становится ординарным академиком.
1900	Выходит первое издание «Исчисления вероятностей».
1906	Марков публикует работу о распространении закона больших чисел на зависимые величины.
1907	Публикуется «Исследование замечательного случая зависимых испытаний».
1913	Марков исследует 20 000 букв «Евгения Онегина»; в Петербурге отмечается двухсотлетие теоремы Бернулли.
1913	Результаты исследования 100 000 букв текста Аксакова включены в приложение к третьему русскому изданию «Исчисления вероятностей»; позднее текст воспроизведён в издании 1924 года.
1923	Норберт Винер создаёт строгую математическую конструкцию броуновского движения.
1931	Колмогоров публикует фундаментальную работу об аналитических методах теории вероятностей и марковских процессах.
1933	Выходят «Основные понятия теории вероятностей» Колмогорова.
1948	Клод Шеннон использует последовательные статистические приближения языка в теории информации.
Вторая половина XX века	Развиваются скрытые марковские модели, распознавание речи, биоинформатика и MCMC.
Конец XX века	Марковские идеи широко применяются в анализе сетей и поисковых алгоритмах.

Основные понятия

Закон больших чисел

Совокупность предельных результатов о том, как средние или частоты случайных величин приобретают устойчивость при росте числа наблюдений.

Марковское свойство

Условие, при котором вероятностное будущее при известном текущем состоянии не требует дополнительного знания более ранней истории.

Матрица переходов

Таблица вероятностей перехода из каждого состояния в каждое другое состояние.

Стационарное распределение

Распределение вероятностей состояний, которое сохраняется после очередного шага цепи.

Случайный процесс

Математический объект, описывающий эволюцию случайной системы во времени.

Скрытая марковская модель

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

Наследие

Сегодня фамилия Маркова присутствует во множестве математических терминов: цепи Маркова, марковские процессы, марковское свойство, марковские модели, марковские поля, марковские процессы принятия решений, методы Монте-Карло на цепях Маркова.

Не все эти конструкции были созданы самим Марковым в современной форме. Многие появились значительно позднее.

Тем важнее различать исторический вклад и дальнейшее развитие.

Марков не построил сразу универсальную теорию всех стохастических процессов. Он решал значительно более конкретную задачу - исследовал последовательности зависимых случайных величин и доказывал, что зависимость не исключает предельной закономерности.

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

Наиболее наглядным символом перехода остаётся «Евгений Онегин». Там, где обычный читатель видит строки Пушкина, Марков увидел последовательность зависимых состояний - и показал, что зависимость можно измерить.

Источники и литература

• Марков А. А. «Распространение закона больших чисел на величины, зависящие друг от друга». 1906.
• Марков А. А. «Исследование замечательного случая зависимых испытаний». 1907.
• Марков А. А. «Пример статистического исследования над текстом „Евгения Онегина“, иллюстрирующий связь испытаний в цепь». 1913.
• Марков А. А. «Исчисление вероятностей». Санкт-Петербург, 1900; последующие издания.
• Bernoulli J. Ars Conjectandi. Basileae, 1713.
• Kolmogorov A. N. Über die analytischen Methoden in der Wahrscheinlichkeitsrechnung. 1931.
• Kolmogorov A. N. Grundbegriffe der Wahrscheinlichkeitsrechnung. 1933.
• Shannon C. E. A Mathematical Theory of Communication. 1948.
• Seneta E. Markov and the Birth of Chain Dependence Theory // International Statistical Review. 1996. Vol. 64, № 3. P. 255-263.
• Seneta E. Statistical Regularity and Free Will: L. A. J. Quetelet and P. A. Nekrasov // International Statistical Review. 2003. Vol. 71, № 2. P. 319-334.
• Seneta E. On the Bicentenary in St. Petersburg of Jacob Bernoulli's Theorem // International Statistical Review. 2014. Vol. 82, № 1. P. 17-26.