Стационарное распределение: к чему сходится цепь и когда

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

Как думаешь, всякая ли цепь успокаивается

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

Попробуй угадать до чтения, к чему сойдётся распределение через много шагов: к 0,5 и 0,5? Ни к чему. После чётного числа шагов цепь наверняка в первом состоянии, после нечётного - во втором, и так будет всегда. При этом распределение 0,5, 0,5 у неё есть, и оно при шаге не меняется. «Существует равновесие» и «цепь к нему приходит» - разные утверждения.

На что это похоже

Город с несколькими районами, жители которого каждый день переезжают по заданным вероятностям. В равновесии население районов постоянно: из центра ежедневно уезжает столько же людей, сколько приезжает. Люди при этом не стоят на месте - постоянны только количества.

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

Механизм: уравнения равновесия и два условия

Стационарное распределение - строка π, для которой π · P = π. Распишем это для одного состояния j: слева - вероятность оказаться в j после шага, то есть всё, что в него пришло; справа - то, что в нём было.

π[j] = сумма по всем i:  π[i] · P[i][j]

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

Для сервера из прошлого урока, с состояниями 0, 1, 2:

«тормозит»:   приток  π₀ · 0,08                 отток  π₁ · (0,30 + 0,20)       →  π₁ = 0,16 · π₀
«лежит»:      приток  π₀ · 0,02 + π₁ · 0,20     отток  π₂ · 0,50                →  π₂ = 0,104 · π₀
сумма равна 1:  π₀ · (1 + 0,16 + 0,104) = 1                                     →  π₀ = 0,7911

Получается 0,7911, 0,1266, 0,0823 - та самая строка, к которой сошлась программа. Уравнений равновесия n, но одно из них следует из остальных: если сложить все n уравнений, слева и справа получится одно и то же - вся вероятность. Поэтому одно уравнение заменяют условием «сумма равна единице».

Когда на это можно полагаться.

Существование. У цепи с конечным числом состояний стационарное распределение есть всегда.

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

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

В неприводимой цепи проще всего убедиться в апериодичности, найдя состояние, которое с ненулевой вероятностью остаётся на месте: петля разрушает любой ритм. Отсюда стандартный приём - ленивая цепь: на каждом шаге с вероятностью 1/2 стоять, иначе делать обычный переход. Стационарное распределение не меняется - половина π остаётся на месте, вторая половина после обычного шага снова даёт половину π, - а периодичность исчезает.

У стационарного распределения есть второй смысл. В неприводимой цепи среднее время между двумя посещениями состояния i равно 1 / π[i]: если состояние занимает одну двадцатую всех шагов длинной траектории, то посещается оно в среднем на каждом двадцатом шаге.

Правило

Стационарное распределение π удовлетворяет π · P = π и сумма π[i] = 1; для каждого состояния приток вероятности равен оттоку. У конечной цепи оно существует; оно единственно, если цепь неприводима; распределение цепи сходится к нему с любого начала, если цепь неприводима и апериодична. У неприводимой цепи π[i] - доля времени в состоянии i, 1 / π[i] - среднее время возвращения. Для цепи из двух состояний с вероятностями перехода a из первого во второе и b обратно, не равными нулю одновременно: π = (b / (a + b), a / (a + b)).

Разбор: маятник, ленивый маятник и два острова

Три цепи из двух состояний. «Маятник» всегда переходит в другое состояние. «Ленивый» - с вероятностью 1/2 остаётся. «Два острова» - никогда не переходит.

def shag(r, p):
    n = len(p)
    novoe = [0] * n
    for i in range(n):
        for j in range(n):
            novoe[j] = novoe[j] + r[i] * p[i][j]
    return novoe

def okruglit(r):
    otvet = []
    for x in r:
        otvet.append(round(x, 3))
    return otvet

mayatnik = [[0, 1], [1, 0]]
lenivyj = [[0.5, 0.5], [0.5, 0.5]]
dva_ostrova = [[1, 0], [0, 1]]

r = [1, 0]
for t in range(11):
    r = shag(r, mayatnik)
print(okruglit(r), okruglit(shag(r, mayatnik)))

r = [1, 0]
for t in range(11):
    r = shag(r, lenivyj)
print(okruglit(r))
print(okruglit(shag([1, 0], dva_ostrova)), okruglit(shag([0.3, 0.7], dva_ostrova)))

[0, 1] [1, 0]
[0.5, 0.5]
[1, 0] [0.3, 0.7]

Первая строка: после одиннадцати шагов маятник наверняка во втором состоянии, после двенадцати - в первом. Распределение не сходится. Стационарное распределение у него есть - 0,5, 0,5, - и оно единственное, но прийти к нему цепь может, только если с него начала. Нарушено второе условие: в каждое состояние возвращаются только через чётное число шагов.

Вторая строка: ленивый маятник сошёлся к 0,5, 0,5 сразу.

Третья строка: у «двух островов» любое распределение стационарно - 1, 0 остаётся собой, и 0,3, 0,7 тоже. Нарушено первое условие: из одного состояния в другое не попасть, и цепь вечно помнит, как началась.

Разбор: ранжирование пяти страниц

Читатель на каждом шаге либо переходит по случайной ссылке с текущей страницы, либо - с вероятностью 1 − d = 0,15 - бросает всё и открывает случайную страницу из всех. Ранг страницы - стационарная вероятность этой цепи. Ссылки: страница 0 ссылается на 1 и 2, страница 1 на 2, страница 2 на 0, страница 3 на 0 и 2, страница 4 на 3. Программа делает шестьдесят шагов умножения, начиная с равных рангов.

ssylki = [[1, 2], [2], [0], [0, 2], [3]]
n = len(ssylki)
d = 0.85

rang = [1 / n] * n
for krug in range(60):
    novyj = [(1 - d) / n] * n
    for stranica in range(n):
        dolya = d * rang[stranica] / len(ssylki[stranica])
        for kuda in ssylki[stranica]:
            novyj[kuda] = novyj[kuda] + dolya
    rang = novyj

okruglyonnye = []
for x in rang:
    okruglyonnye.append(round(x, 3))
print(okruglyonnye, round(sum(rang), 6))

[0.364, 0.185, 0.365, 0.056, 0.03] 1.0

Страница 4, на которую никто не ссылается, получила 0,15 / 5 = 0,03: читатель попадает на неё только случайным прыжком. Страница 3, на которую ссылается одна она, - 0,056. Страницы 0 и 2 ссылаются друг на друга по кругу и собирают по 36% времени читателя; страница 1 получает половину того, что раздаёт страница 0.

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

Случайный прыжок здесь - не украшение, а то, что обеспечивает оба условия. Без него цепь по ссылкам не обязана быть неприводимой: со страницы без исходящих ссылок некуда идти, а группа страниц, ссылающихся только друг на друга, собрала бы весь ранг и не отдала. Прыжок соединяет каждую страницу с каждой и заодно разрушает периодичность. Страницу без исходящих ссылок обрабатывают отдельно: с неё читатель прыгает на случайную страницу всегда. В программе выше у каждой страницы ссылки есть, и этой ветки в ней нет. Граница модели видна тут же: число 0,85 - параметр, а не закон, и ранги от него зависят.

Что ломается без этого

Шаги цепи считают до «сошлось», а цепь периодична. Итерация не остановится или остановится на случайном шаге цикла. Нужна ленивая цепь или прямое решение уравнений.

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

Стационарное распределение читают как прогноз на завтра. π описывает далёкое будущее и средние доли времени. Вероятность лежать через минуту у сервера, который сейчас лежит, - 50%, а не 8%.

Среднее время возвращения путают с временем пребывания. 1 / π[i] - сколько шагов между началом одного посещения и началом следующего в среднем по всем шагам, а не сколько шагов цепь проводит в состоянии подряд.

Зачем это в работе

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

Доступность и очереди. Доля времени, когда система в состоянии «отказ», - это π соответствующего состояния; среднее время между попаданиями в него - 1 / π. В простейшей модели очереди с одним обработчиком состояния - число ожидающих запросов, и из уравнений равновесия получается, что вероятность длинной очереди убывает геометрически, пока обработчик в среднем быстрее потока.

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

Теперь сам

1. Цепь из двух состояний: из A в B с вероятностью 0,2, из B в A с вероятностью 0,6. Найди стационарное распределение.
2. Проверь ответ: умножь найденную строку на матрицу.
3. Чему равно среднее время возвращения в состояние B для этой цепи?
4. Цепь из трёх состояний ходит по кругу: 0 → 1 → 2 → 0, каждый переход наверняка. Каково её стационарное распределение и сходится ли к нему цепь, начатая в состоянии 0?
5. В сети из 1000 страниц на некоторую страницу не ведёт ни одна ссылка. Каков её ранг при d = 0,85?