Что общего у ядерных бомб, поиска Google и пасьянса?
Они возникли из ожесточённой вражды между двумя российскими математиками более 100 лет назад. Андрей Марков и Павел Некрасов столкнулись не только в академическом плане — их конфликт был идеологическим и даже политическим.
Если вы немного разбираетесь в математике, вы уже можете догадаться, кто победил: Марков. Их противостояние привело к появлению одного из самых мощных инструментов современной науки — цепи Маркова.
Закон больших чисел
Если вспомнить школьные уроки вероятности, есть одно фундаментальное допущение: если повторять независимые события (это важно), средний результат сходится к ожидаемому значению. Например, подбрасывание монеты. Если монета «честная», она выпадет орлом 50 % времени и решкой 50 %.
Здесь работает закон больших чисел, доказанный Бернулли в 1713 году.
В 1905 году Россия разрывалась между царистами и социалистами, и именно этот принцип стал полем битвы.
Павел Некрасов (царист и глубоко верующий) утверждал, что статистическое совпадение социальных данных, таких как браки или преступность, доказывает, что решения людей независимы, а значит, являются актами свободной воли.
Марков был социалистом и атеистом и утверждал, что Некрасов неправильно использует принцип и всю математику. Он поставил цель доказать, что зависимые события тоже могут подчиняться закону больших чисел.
Прорыв Маркова: моделирование языка
Марков использовал литературу, чтобы доказать свою точку зрения.
Он проанализировал 20 000 букв из «Евгения Онегина» Пушкина и посчитал частоту гласных и согласных. Затем он проверил, как часто одна буква следует за другой.
Результаты показали явную зависимость: определённые пары букв встречались гораздо чаще, чем предсказывала случайность.
Но когда он моделировал последовательности с учётом этих зависимостей, общий баланс гласных и согласных всё равно сходился.
Это было революционно.
Марков построил зависимую систему, которая подчинялась закону больших чисел. Он назвал её цепью Маркова.
Цепь Маркова — это модель, где следующее состояние зависит только от текущего, а не от всей истории.
С этим он доказал Некрасову: для вероятности не нужна ни свобода воли, ни независимость событий.
Метод Монте-Карло
Цепь Маркова была мощным инструментом, но некоторое время забыта.
Лишь в 1946 году математик Станислав Улам вернулся к ней. В то время он выздоравливал после болезни и для развлечения играл в пасьянс в постели.
Он задался вопросом: каковы шансы выиграть случайно перетасованную партию?
Проблема была слишком сложной для аналитического решения. Но что если просто сыграть сотни партий и посчитать выигрыши?
Эта идея, называемая случайной выборкой, стала основой метода Монте-Карло.
Вернувшись к работе, Улам и Джон фон Нейман применили метод для моделирования поведения нейтронов в ядерных реакциях.
Нейтроны, в отличие от карт в пасьянсе, не ведут себя независимо. Их действия зависят от предыдущих состояний.
Именно поэтому они использовали цепи Маркова для моделирования этих взаимодействий на ENIAC, первом электронном компьютере.
Это позволило оценить, сколько урана нужно для бомбы, без решения почти невозможных уравнений.
Цепи Маркова в интернете
Но цепи Маркова нужны не только для ядерных бомб. В 1990-х интернет взорвался. Поисковики вроде Yahoo ранжировали страницы по частоте ключевых слов. Этот подход легко обходили, так как алгоритм не учитывал качество.
В Стэнфорде Ларри Пейдж и Сергей Брин поняли, что ссылки в интернете можно рассматривать как рекомендации. Они смоделировали веб как цепь Маркова, где каждая страница — это состояние, а каждая ссылка — переход.
Их алгоритм PageRank рассчитывал важность страницы, исходя из того, как часто случайный пользователь попадёт на неё. Он оказался устойчив к манипуляциям и стал основой Google.
Предсказание текста
Позже Клод Шеннон применил цепи Маркова для предсказания текста. Он показал, что, анализируя предыдущие буквы или слова, можно с высокой точностью предсказать следующие.
Современные LLM (большие языковые модели), например автозаполнение Gmail или ChatGPT, используют усовершенствованные версии цепей Маркова.
Сила «безпамятности»
Цепи Маркова работают потому, что не зависят от памяти.
Им важно только текущее состояние. Это делает их идеальными для моделирования сложных систем: погоды, распространения болезней или тасовки карт.
Интересный факт: для случайного перемешивания колоды из 52 карт требуется семь тасовок. Это пример цепи Маркова в действии.
От вражды к фундаменту
Стремление Маркова опровергнуть Некрасова привело к инструменту, который сегодня используется в поисковых системах, ядерных симуляциях, ИИ и многом другом.
Как написано в одной статье:
«Решение проблемы часто сводится к созданию подходящей цепи Маркова».