Вычислить цепь Маркова по заданному стационарному вектору - PullRequest
Новая
       78

Вычислить цепь Маркова по заданному стационарному вектору

0 голосов
/ 23 марта 2019

Я делаю домашнее задание по курсу Монте-Карло, и меня просят найти матрицу цепи Маркова с 6 состояниями, а именно 0, 1, 2, 3, 4, 5, такую, что после достаточно длительного периода времени мы потратиливремя, пропорциональное числам 5, 10, 5, 10, 25, 60 в каждом из состояний.

Я вижу, что это стационарный вектор, который мы получаем, если имеем матрицу переходов.Я должен использовать алгоритм Метрополиса, но все объяснения и примеры, которые я нахожу, основаны на алгоритме Метрополиса-Хастинга.

Псевдокод моего алгоритма: 

select x
 Loop over repetitions t=1,2...
 select y from Nx using density Gx
 put h=min(1, f(y)/f(x))
 if U ~ U(0, 1) < h then x <- y
end loop

Я ищупошаговое объяснение, как реализовать алгоритм для данной задачи, желательно на python!

1 Ответ

1 голос
/ 25 марта 2019

Алгоритмический подход

Стандартный подход к вычислению стационарного распределения цепи Маркова - это решение линейных уравнений, например, как описано здесь https://stephens999.github.io/fiveMinuteStats/stationary_distribution.html. Решение вашей проблемы такое же, как внаоборот - решите те же уравнения, за исключением того, что в вашем случае у вас есть стационарное распределение, но у вас нет вероятностей / скоростей перехода.

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

Пример примитива

Рассмотрим стационарное распределение Pi = (x = 1/3, y = 1/3, z = 1/3)

Постройте свою систему линейных уравнений как 

Pi(x) = 1/3 =  Pr(y,x) * Pi(y)
Pi(y) = 1/3 =  Pr(z,y) * Pi(z)
Pi(z) = 1/3 =  Pr(x,z) * Pi(x)

В этом случаерешение Pr (y, x) = Pr (z, y) = Pr (x, z) = 1 и полученная цепь Маркова просто скучно зацикливается от x до z до y и обратно до x с вероятностью 1. Обратите внимание, что число подходящих решений может быть бесконечным (даже для приведенной системы линейных уравнений, как показано в примере), например, в этом случае вероятности / скорости могут принимать любое положительное значение, пока онивсе равны.

Итак, пошаговое решение

  1. Построим систему линейных уравнений как описано.
  2. Решим построенную систему линейных уравненийУшные уравнения
  3. Решение вашей построенной системы линейных уравнений описывает искомую цепочку Маркова.Тривиально восстановить всю матрицу перехода, если вы хотите.
...