Есть несколько хитростей с марковскими моделями для подобных вопросов.
В вашем случае я предполагаю, что вы хотите ожидаемое количество посещений определенного ребра i, j при
- матрица вероятностей перехода P ,
- все цепочки начинаются с x и
- все цепи имеют длину L
Я буду игнорировать любую специальную форму, такую как ваша P, которая может еще больше улучшить скорость. Общая идея (которая может быть распространена на другие вопросы о системе Маркова) заключается в следующем:
Сначала мы понимаем, что если бы мы знали фактическое число посещений состояния, из которого начинается ребро, мы можем использовать матрицу перехода P , чтобы вывести фактические значения определенного ребра.
Пример: скажем, в цепочках длиной 50 мы знаем, что в среднем 10 раз мы находимся в состоянии 1. А в P шанс выпрыгнуть из 1 -> 2 составляет 50%. Затем в цепочках длиной 50 + 1 мы находим, что 10 * 50% = 5 всех ребер в среднем равны 1 -> 2. (Обратите внимание на разницу между государственными посещениями и посещениями ребер!)
К счастью, ожидание нахождения в состоянии можно записать в виде геометрического ряда матрицы перехода. Вы можете использовать обычный трюк для геометрического ряда, если знаменатель можно перевернуть, что, к сожалению, не относится к матрице переходов. По крайней мере, не тривиально, но это можно решить.
Позвольте мне записать число посещений штатов с использованием LaTeX
E_c{x_0,L} = \sum_{i=0}^{L-1} P^i x_0 = (\sum_{i=0}^{L-1} P^i) x_0
где x_0 - вектор, дающий начальное распределение в вашем случае ноль везде, но одно состояние по вашему выбору.
Обратите внимание, что сумма перед x_0 является матрицей, которая содержит все подсчеты состояний для всех возможных начальных состояний. Теперь для вычисления этой матрицы. Используя геометрический ряд, получаем
\sum_{i=0}^{L-1} P^i = \frac{P^L - Id}{P - Id}
с Id единичной матрицей. Знаменатель единственного числа, поэтому у нас есть проблема. К счастью, числитель имеет ту же проблему , поэтому мы можем это исправить. Использовать разложение по собственным значениям и переписать P, используя матрицы левого и правого собственных векторов и диагональную матрицу собственных значений evD
P = evR evD evL
\sum_{i=0}^{L-1} P^i = \sum_{i=0}^{L-1} (evR evD evL)^i
= evR (\sum_{i=0}^{L-1} evD^i ) evL
Теперь у нас остались простые геометрические ряды для каждого собственного значения. Одно собственное значение равно 1, и это вызывает проблемы. Но в этом случае мы просто подводим итоги. От 0 до L-1 сумма 1 равна просто L. Другие геометрические ряды четко определены.
Pro: теперь вы можете мгновенно вычислить ребра для любого выбора x_0 или L.
Con: Вы всегда должны делать собственное разложение, которое является проблемой, если у вас большие матрицы.
* * Пример тысяча сорок-девять:
Простая четная симметричная матрица
P = {{0.8, 0.15, 0.05},
{0.075, 0.85, 0.075},
{0.05, 0.15, 0.8}}
мы выбрали L = 51 (50 переходов) и x_0 = {1, 0, 0}
evD = {{1., 0., 0.}, {0., 0.75, 0.}, {0., 0., 0.7}}
evR = {{-0.612372, -0.707107, 0.612372}, {-0.612372, 0, -0.612372}, {-0.612372, 0.707107, 0.612372}}
evL = {{-0.408248, -0.816497, -0.408248}, {-0.707107, 0, 0.707107}, {0.408248, -0.816497, 0.408248}}
GeometricSeries(evD,50) = {{50., 0., 0.}, {0., 4., 0.}, {0., 0., 3.33333}}
E_c(x_0 = 1) = evR GeometricSeries(evD,50) evL {1, 0, 0}
= {15.3333, 11.6667, 11.3333}
Для перехода 1 -> 2 (15%) получаем 15,3333 * 15% = 2,3