Марковская цепь: состояния, матрица переходов и распределение через t шагов

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

Как думаешь, важно ли, с чего начать

Сервер каждую минуту находится в одном из трёх состояний: в строю, тормозит, лежит. Из строя он с вероятностью 8% начинает тормозить и с вероятностью 2% падает; тормозящий с вероятностью 30% приходит в норму и с вероятностью 20% падает; лежащий с вероятностью 50% поднимается.

Ответь себе до чтения: чтобы сказать, с какой вероятностью сервер лежит через час, нужно ли знать, в каком состоянии он сейчас? Через минуту - конечно. Через час - уже нет: ответ 0,0823 с точностью до четвёртого знака, поднят сервер сейчас или лежит.

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

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

Игра, в которой есть правило «если ты был на красной клетке дважды, пропускаешь ход», таким свойством не обладает: клетки мало, нужно помнить историю. Но её можно исправить, включив нужную часть истории в само состояние: «клетка плюс число посещений красной».

Механизм: матрица и умножение на неё

Марковская цепь - последовательность случайных состояний X₀, X₁, X₂, …, в которой распределение следующего состояния зависит только от текущего. Это марковское свойство, или отсутствие памяти.

Пусть состояний n. Матрица переходов P - таблица n × n: число P[i][j] - вероятность на следующем шаге оказаться в состоянии j, если сейчас цепь в состоянии i. Каждая строка - распределение вероятностей: числа неотрицательны и в сумме дают единицу.

                в строю   тормозит   лежит
в строю           0,90      0,08      0,02
тормозит          0,30      0,50      0,20
лежит             0,50      0,00      0,50

Теперь пусть известно не точное состояние, а распределение: строка r, где r[i] - вероятность находиться в состоянии i. Каким оно станет через шаг? В состояние j можно прийти из любого i: для этого нужно быть в i и сделать переход i → j. Пути через разные i несовместны, поэтому вероятности складываются:

новое[j] = r[0] · P[0][j] + r[1] · P[1][j] + … + r[n−1] · P[n−1][j]

Это правило умножения строки на матрицу. Сложение стоит потому, что перебираются взаимоисключающие предыдущие состояния; умножение - потому, что переход из i в j не зависит от того, как цепь оказалась в i. Марковское свойство здесь используется ровно один раз - чтобы перемножить.

Через два шага распределение - это r, умноженное на P дважды, через t шагов - t раз. Вероятности переходов за t шагов образуют матрицу P, возведённую в степень t.

Если цепь нарисовать, получится ориентированный граф: вершины - состояния, ребро i → j проведено, когда P[i][j] > 0, и подписано вероятностью. Цепь - это случайное блуждание по такому графу.

Правило

Марковская цепь задаётся матрицей переходов P: P[i][j] - вероятность перейти из i в j, строки неотрицательны и дают в сумме единицу. Если r - распределение по состояниям, то через один шаг оно равно r · P, через t шагов - r · Pᵗ. Следующее состояние зависит только от текущего; всё, что нужно помнить о прошлом, должно входить в состояние.

Разбор: два начала и одно будущее

Функция shag умножает строку на матрицу. Два распределения - «сейчас в строю» и «сейчас лежит» - пропускаются через одни и те же шаги.

perehody = [[0.90, 0.08, 0.02], [0.30, 0.50, 0.20], [0.50, 0.00, 0.50]]

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

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

iz_stroya = [1, 0, 0]
iz_otkaza = [0, 0, 1]
otmetki = [1, 2, 5, 20, 60]
t = 0
for otmetka in otmetki:
    while t < otmetka:
        iz_stroya = shag(iz_stroya, perehody)
        iz_otkaza = shag(iz_otkaza, perehody)
        t = t + 1
    print(t, okruglit(iz_stroya), okruglit(iz_otkaza))

1 [0.9, 0.08, 0.02] [0.5, 0.0, 0.5]
2 [0.844, 0.112, 0.044] [0.7, 0.04, 0.26]
5 [0.7952, 0.1276, 0.0772] [0.7975, 0.1134, 0.0891]
20 [0.7911, 0.1266, 0.0823] [0.7911, 0.1266, 0.0823]
60 [0.7911, 0.1266, 0.0823] [0.7911, 0.1266, 0.0823]

После первого шага распределения - просто первая и третья строки матрицы. Второй шаг для сервера, который был в строю, считается руками: в строю он окажется с вероятностью 0,9 · 0,9 + 0,08 · 0,3 + 0,02 · 0,5 = 0,844.

К пятому шагу два распределения отличаются уже во втором знаке, к двадцатому совпадают до четвёртого и дальше не меняются. Цепь забыла, с чего началась. Предельная строка - 0,7911, 0,1266, 0,0823 - не зависит от начала и не меняется при умножении на матрицу; следующий урок - о ней.

Разбор: одна длинная траектория и граница модели

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

import random

perehody = [[0.90, 0.08, 0.02], [0.30, 0.50, 0.20], [0.50, 0.00, 0.50]]

def sleduyushchee(sostoyanie):
    u = random.random()
    nakopleno = 0
    for j in range(3):
        nakopleno = nakopleno + perehody[sostoyanie][j]
        if u < nakopleno:
            return j
    return 2

random.seed(71)
shagov = 20000
byl = [0, 0, 0]
sostoyanie = 2
for t in range(shagov):
    sostoyanie = sleduyushchee(sostoyanie)
    byl[sostoyanie] = byl[sostoyanie] + 1
doli = []
for b in byl:
    doli.append(round(b / shagov, 4))
print(doli)

[0.7971, 0.1243, 0.0786]

Доли времени, проведённого в каждом состоянии, - 79,7%, 12,4% и 7,9% - близки к предельной строке 79,1%, 12,7%, 8,2%. Одно и то же число отвечает на два вопроса: «с какой вероятностью сервер лежит в далёкий момент» и «какую долю времени он лежит». Так бывает у цепей, в которых из любого состояния достижимо любое: длинная траектория проходит через состояния в тех же пропорциях; точные условия - в следующем уроке. Расхождение в третьем знаке - шум опыта: соседние минуты зависимы, и двадцать тысяч шагов дают меньше сведений, чем двадцать тысяч независимых наблюдений.

Граница модели - само марковское свойство. В матрице сказано: лежащий сервер поднимается с вероятностью 50% каждую минуту, сколько бы он ни лежал. Если на деле перезапуск занимает ровно три минуты, это неправда: вероятность подняться зависит от того, сколько минут сервер уже лежит, а этого в состоянии нет. Цепь будет считать уверенно и неверно. Лечится расширением состояния - «лежит первую минуту», «лежит вторую», «лежит третью», - после чего свойство восстанавливается, а матрица вырастает до пяти состояний.

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

Состояние не содержит того, от чего зависит будущее. «Пользователь на странице корзины» - недостаточное состояние, если вероятность покупки зависит от того, пришёл он из поиска или с рекламы. Модель с таким состоянием даёт ровные и неверные числа.

Столбцы вместо строк. В матрице переходов единице равна сумма по строке: из состояния куда-то надо уйти. Сумма по столбцу - сколько вероятности в состояние приходит, и она может быть любой. Матрица, записанная наоборот, даёт «распределения» с суммой, отличной от единицы.

Вероятности за разные промежутки. Матрица за минуту и матрица за час - разные матрицы; вторая равна первой в шестидесятой степени. Умножать минутную вероятность отказа на шестьдесят нельзя.

Моделирование там, где можно посчитать. Чтобы узнать долю времени в состоянии «лежит», не нужно прогонять миллион шагов со случайными числами: умножение строки на матрицу даёт её с любой нужной точностью, а уравнения из следующего урока - точно.

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

Надёжность и ёмкость. Состояния - сколько узлов кластера исправно, сколько запросов в очереди, сколько соединений занято. Матрица переходов строится из интенсивностей отказов и восстановлений, а из неё считаются доля времени простоя и вероятность переполнения очереди.

Тексты и последовательности. Состояние - последнее слово или последние несколько символов, переход - следующее слово. Подсказки при наборе, простые генераторы текста, модели для сжатия данных из раздела про строки - всё это цепи, где «память» ограничена состоянием по построению.

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

Теперь сам

1. По матрице из урока: сервер тормозит. С какой вероятностью через одну минуту он лежит?
2. По той же матрице: сервер лежит. С какой вероятностью через две минуты он в строю?
3. Цепь из двух состояний: из A с вероятностью 0,2 переходит в B, из B с вероятностью 0,6 - в A. Запиши матрицу переходов.
4. В матрице строка состояния «лежит» записана как 0,5, 0,1, 0,5. Что не так?
5. Игра: фишка ходит по клеткам по броску кубика, но после трёх шестёрок подряд возвращается на старт. Является ли «номер клетки» достаточным состоянием? Если нет, что добавить?