Марковский процесс: скорость выхода и баланс времени

Если отличаешь интенсивность от вероятности перехода и можешь найти доли времени двух чередующихся состояний, переходи к «Теперь сам».

Как думаешь, половина посещений означает половину времени

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

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

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

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

Марковское свойство означает, что текущее состояние содержит всё, что нужно для закона будущего. Если время ожидания зависело бы от возраста уже идущей работы, пришлось бы добавить этот возраст в состояние. Экспоненциальное ожидание позволяет обойтись одним номером текущего состояния.

Механизм: часы и матрица интенсивностей

Пусть qᵢⱼ≥0 при i≠j - интенсивность перехода i→j. Полная интенсивность выхода qᵢ=Σⱼ≠ᵢqᵢⱼ. При qᵢ>0 процесс ждёт Exp(qᵢ), затем выбирает j с вероятностью qᵢⱼ/qᵢ. При qᵢ=0 состояние поглощающее: выхода из него нет. Выбор часов и направления в этой конструкции независимы.

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

Генератор Q содержит qᵢⱼ вне диагонали и Qᵢᵢ=−qᵢ на диагонали. Сумма каждой строки равна 0. Это не вероятностная матрица: диагональ отрицательна, а интенсивности могут быть больше 1. За маленькое h переход i→j имеет вероятность qᵢⱼh+o(h), оставаться в i - 1−qᵢh+o(h). Именно после умножения на время получается безразмерная вероятность.

Правило

Стационарные доли времени удовлетворяют Σᵢ≠ⱼπᵢqᵢⱼ=πⱼqⱼ, πᵢ≥0, Σπᵢ=1. Краткая запись - πQ=0. Входящий поток вероятности каждого состояния равен выходящему. Попарный баланс πᵢqᵢⱼ=πⱼqⱼᵢ достаточен, но в общем случае не обязателен.

Уравнения получаются из сохранения вероятности на малом шаге: масса в j меняется на входы Σᵢ≠ⱼπᵢqᵢⱼh минус выход πⱼqⱼh, с остатком o(h). Стационарность означает нулевое изменение; делим на h и получаем баланс. После решения проверяем неотрицательность и нормировку. Для бесконечного набора состояний формальные веса могут не суммироваться в 1.

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

Для переходов 0→1 интенсивности a и 1→0 интенсивности b имеем π₀a=π₁b, π₀+π₁=1. Отсюда π₀=b/(a+b), π₁=a/(a+b). При a=1,b=3 получаем 3/4 и 1/4. Средние времена пребывания 1 и 1/3 дают тот же результат после нормировки суммарного времени одного цикла.

Во встроенной последовательности посещения строго чередуются, поэтому доли равны 1/2 и 1/2. Общая связь такая: если стационарные доли посещений равны αᵢ, то доли времени пропорциональны αᵢ/qᵢ, когда эта нормировка определена. Число посещений умножается на среднее время одного посещения. Это объясняет, почему нельзя решать одну таблицу вероятностей и выдавать результат за равновесие непрерывного времени.

from fractions import Fraction

for a, b in [(1, 3), (1, 1), (4, 1)]:
    p0 = Fraction(b, a + b)
    p1 = 1 - p0
    print("скорости", a, b, "доли времени", p0, p1)
    print("поток 0->1", p0 * a, "поток 1->0", p1 * b)
print("доли посещений двух состояний:", Fraction(1, 2))
rates = [1, 2, 4]
weights = [Fraction(1, r) for r in rates]
pi = [w / sum(weights) for w in weights]
print("цикл 0->1->2->0, доли:", [str(p) for p in pi])
print("потоки по циклу:", [str(p * r) for p, r in zip(pi, rates)])

скорости 1 3 доли времени 3/4 1/4
поток 0->1 3/4 поток 1->0 3/4
скорости 1 1 доли времени 1/2 1/2
поток 0->1 1/2 поток 1->0 1/2
скорости 4 1 доли времени 1/5 4/5
поток 0->1 4/5 поток 1->0 4/5
доли посещений двух состояний: 1/2
цикл 0->1->2->0, доли: ['4/7', '2/7', '1/7']
потоки по циклу: ['4/7', '4/7', '4/7']

В первых строках равны потоки 0→1 и 1→0, хотя доли времени обычно различаются. В последней части программа рассматривает однонаправленный цикл из трёх состояний с разными скоростями выхода. Их средние времена пребывания 1,1/2,1/4 нормируются в 4/7,2/7,1/7.

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

В цикле 0→1→2→0 с интенсивностями 1,2,4 на каждом ребре стационарный поток равен 4/7. В каждое состояние столько же входит, сколько выходит, поэтому глобальный баланс выполнен. Но у ребра 0→1 обратная интенсивность равна нулю: попарное равенство требовало бы 4/7=0. Оно здесь не выполняется.

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

В бесконечной модели дополнительно исключают накопление бесконечного числа скачков за конечное время. Экспоненциальная конструкция сама не запрещает его: в примере обратной связи суммы Exp(n^p) при p>1 как раз сходились. Для конечного пространства все интенсивности ограничены, и такой взрыв невозможен. В очередях следующего урока за конечное время приходит конечное число заявок, а уходов не больше начального числа плюс пришедшие: это тоже исключает взрыв.

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

Принимают qᵢⱼ за вероятность и пытаются заставить каждую строку в сумме давать 1. Сумма строк генератора должна давать 0: его диагональ учитывает уходящую массу. Вероятностная таблица скачков получается делением недиагональных интенсивностей на qᵢ.

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

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

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

Теперь сам

Два состояния чередуются с интенсивностями 0→1, равной 4, и 1→0, равной 1. Найди стационарную вероятность состояния 1. Можно ли получить её подсчётом доли посещений?