Уровни жидкости в марковском процессе = PageRank
Этот пост — компактная версия того, что произошло в соседнем чате. Извините новичков, которые уже прочитали это — и добро пожаловать!
Первые две картинки принадлежат студенту, который задавался вопросом, почему мы вдруг поставили нули в правой части уравнений. Студент был совершенно дезориентирован, потому что они называли это «нормализацией».
Вот идея.
Стационарная ситуация – это ситуация, в которой ничего не меняется во времени, т. е. все производные по времени равны нулю. Итак, похоже, что у нас есть четыре уравнения с четырьмя неизвестными, и мы можем их просто решить. Еще нет.
Если исходной задачей является марковский процесс с интенсивностью/вероятностью перехода, вы можете прочитать его как физическую модель:
🫙четыре баночки (состояния),
🚰трубочки между ними (направленные края),
💨 поток через каждую трубку пропорционален «давлению» в банке-источнике (так что да, странная вязкая игрушечная модель).
Физическая интуиция: система расслабляется. Через некоторое время уровни перестают меняться — для каждой банки приток равен оттоку. Эти «асимптотические вероятности» и есть стационарное распределение.
Теперь самое важное: жидкость не может ни появиться, ни исчезнуть. Общая сумма сохраняется. В связи с этим уравнения баланса линейно зависимы: одно из них избыточно. Поэтому вы вычеркиваете одно уравнение и заменяете его законом сохранения:
р₀ + р₁ + р₂ + р₃ = 1
Это и есть «нормализация». Это не какой-то мистический трюк — это просто «всего жидкости 1 м³».
На третьем рисунке показан результат численного моделирования для различных начальных состояний. Хорошо видна стадия релаксации, а затем сходимость к одному и тому же устойчивому решению (пунктирные линии).
И тут приходит приятное историческое эхо. Примерно 30 лет назад Ларри Пейдж и Сергей Брин решили, по сути, одну и ту же проблему стационарного потока на веб-графе: ссылки стали вероятностями перехода, а стационарное распределение стало показателем ранжирования страниц. Этот подход называется PageRank — не из-за «страниц», а из-за фамилии Ларри.
Это работало удивительно хорошо для раннего Интернета (когда фраза «ссылка — это голос» была ближе к истине) и помогла Google взлететь. Это уже не вся история ранжирования, но, будучи первой масштабируемой идеей, она изменила правила игры.