Цепи Маркова: Математическое моделирование случайных процессов
Как математически смоделировать систему, которая меняет свои состояния случайным образом? Как предсказать погоду на завтра, вероятность отказа сервера или следующее слово, которое пользователь наберет на клавиатуре телефона? В дискретной математике и теории вероятностей для решения таких задач используется мощный инструмент прогнозирования — Марковские цепи, названные в честь русского математика Андрея Андреевича Маркова.
Цепь Маркова — это последовательность случайных событий (состояний системы) с конечным или счетным числом исходов. Ее главная, фундаментальная особенность называется "марковским свойством" (отсутствием памяти): будущее состояние системы зависит только от ее текущего состояния и совершенно не зависит от того, как именно система пришла в это текущее состояние в прошлом.
Чтобы задать цепь Маркова, необходимы две вещи:
- Множество всех возможных состояний системы (например: "Солнечно", "Облачно", "Дождь").
- Матрица переходных вероятностей. Это таблица, где на пересечении строки i и столбца j записана вероятность того, что система, находясь в состоянии i, на следующем шаге перейдет в состояние j. Сумма вероятностей в каждой строке матрицы всегда строго равна 1 (100%).
Динамику такой системы очень удобно визуализировать с помощью ориентированного взвешенного графа, где узлы — это состояния, а стрелки показывают вероятности переходов.
Математический аппарат позволяет вычислять вероятность нахождения системы в любом конкретном состоянии через n шагов, путем возведения переходной матрицы в n-ую степень. Более того, для эргодических (сильно связных и непериодических) цепей Маркова существует стационарное распределение. Оно означает, что при достаточно долгом наблюдении система приходит к устойчивому балансу, и вероятности нахождения в различных состояниях перестают меняться со временем, независимо от того, с какого состояния мы начали.
Применение цепей Маркова в IT безгранично. Простейшие генераторы текста и предиктивный ввод T9 в старых телефонах — это цепи Маркова на основе частотности пар слов. Теория массового обслуживания (расчет пропускной способности каналов и очередей маршрутизаторов) полностью базируется на марковских процессах. И, пожалуй, самое известное применение: алгоритм PageRank, который сделал Google мировой монополией поиска. Он представляет интернет как гигантскую цепь Маркова, где состояния — это веб-страницы, а вероятности переходов зависят от гиперссылок. PageRank вычисляет стационарное распределение случайного веб-серфера, тем самым определяя авторитетность каждой страницы в сети.
