Андрей Марков и «Евгений Онегин».

В 1906 году Андрей Марков взял первые 20 000 букв «Евгения Онегина» и начал считать1. Сколько гласных. Сколько согласных. И главное — как они чередуются.

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

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

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

Марковское свойство: будущее зависит только от настоящего. P(Xₙ₊₁ | X₀, X₁, …, Xₙ) = P(Xₙ₊₁ | Xₙ). Вся история — не важна. Только текущее состояние.

В «Евгении Онегине» это работает так: вероятность следующей буквы быть гласной зависит от того гласная ли текущая — но не от того что было раньше. Марков посчитал эти вероятности вручную. Первые 20 000 букв. Без компьютера.

Результат: переходная матрица. Гласная → гласная: 0.128. Гласная → согласная: 0.872. Согласная → гласная: 0.663. Согласная → согласная: 0.337.

Стационарное распределение: ~43% гласных. В русском языке — около 43%. Совпадение подтвердило теорию. Из этой задачи выросла вся теория марковских цепей. Случайные процессы с памятью длиной 1.

Марковские цепи описывают: погоду (сегодняшняя погода → завтрашняя), очереди (текущая длина → следующая), броуновское движение (текущая позиция → следующая), цены активов (текущая цена → следующая).

PageRank3 — марковская цепь на миллиардах страниц. Ларри Пейдж в 1998 году построил граф интернета. Страницы — состояния. Ссылки — переходы. Случайный серфер кликает по ссылкам. PageRank страницы = вероятность оказаться на ней в стационарном распределении. Google стоит $2 трлн. В основе — матрица переходов.

MCMC — Markov Chain Monte Carlo4. Как сэмплировать из сложного вероятностного распределения? Построить марковскую цепь со нужным стационарным распределением. Запустить цепь. Записывать состояния. Алгоритм Метрополиса-Гастингса 1953 года — изобретён в Лос-Аламосе для ядерных расчётов. Сегодня MCMC — основа байесовской статистики и обучения языковых моделей.

Скрытые марковские модели (HMM): состояния скрыты, наблюдаем только выходы. Голосовые помощники. Распознавание речи. Биоинформатика. Финансовые аномалии.

«Я прошу причислить меня к отлучённым — как закоренелого безбожника.» — Андрей Марков, письмо в Синод, 1912

Марков умер в 1922 году. Он не знал про PageRank и языковые модели. Но когда в 1913 году церковь отлучила Льва Толстого, Марков — атеист — попросил отлучить и его. Спор с Некрасовым имел и религиозный подтекст: Некрасов использовал независимость событий как аргумент для свободы воли. Марков опровергал и математику и теологию одновременно.

Цепь Маркова — математический объект. Но история её создания — вполне человеческая. Спор об идеях. Упрямство. Поэзия. 20 000 букв посчитанных вручную.