Цепь маркова

[Chernobrivec]

Доброе время суток.
Пускай дана цепь маркова с конечным числом состояний. Известна матрица переходных вероятностей P и вектор начальных рапспределений q. Как посчитать распределение веротностей количества попаданий цепи в состояние j за k шагов( или,на мой взгляд, более сложный случай - до первого достижения состояния i)?
Заранее спасибо.

[MGM]

Перемножайте начальное распределение на матрицу столько раз, сколько просят.
В чем сложность-то?
В скобках сложно, потому как не понятно, что Вы имеете в виду под "достижением".
Вектор респределения на шаге k примет некое i заданное состояние?

[Chernobrivec]

MGM в сообщении #320205 писал(а):

Перемножайте начальное распределение на матрицу столько раз, сколько просят.
В чем сложность-то?

Не могу понять, о чем вы говорите. Можете привести формулу,пожайлуста?

MGM в сообщении #320205 писал(а):

В скобках сложно, потому как не понятно, что Вы имеете в виду под "достижением".
Вектор респределения на шаге k примет некое i заданное состояние?

Достижение состояния означает первое попадания в него. Возможно то, что это состояние поглощающее чем то облегчит задачу.

[MGM]

Chernobrivec в сообщении #320229 писал(а):

MGM в сообщении #320205 писал(а):

Перемножайте начальное распределение на матрицу столько раз, сколько просят.
В чем сложность-то?

Не могу понять, о чем вы говорите. Можете привести формулу,пожайлуста?

MGM в сообщении #320205 писал(а):

В скобках сложно, потому как не понятно, что Вы имеете в виду под "достижением".
Вектор респределения на шаге k примет некое i заданное состояние?

Достижение состояния означает первое попадания в него. Возможно то, что это состояние поглощающее чем то облегчит задачу.

А Вы, в свою очередь, не могли бы формулой какой сформулировать задачу?
Потому как первое попадание в состояние!!! для меня нонсенс в контексте ТВ.
Простой пример - монетка.
Два состояния.
Известно, что начальное расперделение 0.1 для орла, 0.9 для решки.
Матрица Р - стохастическая с 0.5 для всех четырёх элементов.
и когда, по Вашему мнению, орёл выпадет в ПЕРВЫЙ раз?

[Chernobrivec]

Момент первого попадания в состояние является случайной величиной. Для неприрывных процессов, например винеровского процесса, аналогом есть случайный момент выхода процесса из некоторой области. Именно первый момент выхода винеровского процесса на границу области используется в численных методах для решения задачи Дирихле.

[Хорхе]

Пусть $s^k_{i}(m)$ --- вероятность $m$ раз побывать в состоянии $j$ за $k$ шагов, стартовав из состояния $i$; $p_{i\,j}$ --- переходные вероятности.

При $k\ge 1$, $m\ge 1$ имеем $s^k_{i}(m) = \sum_{l\neq j} p_{i\,l} s^{k-1}_{l}(m) + p_{i\,j} s^{k-1}_{j}(m-1)$; при $m=0$ второе слагаемое отсутствует. То есть имеем некую рекуррентную формулу. Потом $s$ свернуть с $q$ и получить то, что надо.

Есть ли что-то проще? Вряд ли. (Разве что если нужно считать математическое ожидание, вот это действительно просто. Дисперсия посложнее, но тоже считается.)

Можно и так: умножить в матрице $P$ $j$-й столбик на $x$ (получив P_x), в векторе $q$ $j$-ю координату на $x$ (получив $q_x$). Тогда коэффициенты многочлена

$$ f_k(x) = q_x (P_x)^k (1,\dots,1)^{\top} $$

равны в точности искомым вероятностям.

Вероятности для первого достижения посчитать намного проще! Обозначьте через $r_{i}(k)$ вероятность достичь $j$ из $i$ за $k$ шагов и напишите простую рекуррентную формулу, из которой легко находите желаемое (в терминах степеней некоторой матрицы).

[PAV]

В учебный раздел

[MGM]

Chernobrivec в сообщении #320275 писал(а):

Момент первого попадания в состояние является случайной величиной. Для неприрывных процессов, например винеровского процесса, аналогом есть случайный момент выхода процесса из некоторой области. Именно первый момент выхода винеровского процесса на границу области используется в численных методах для решения задачи Дирихле.

Так значит момент. А не попадание.
уже лучше.

[Chernobrivec]

Цитата:

Вероятности для первого достижения посчитать намного проще! Обозначьте через вероятность достичь из за шагов и напишите простую рекуррентную формулу, из которой легко находите желаемое (в терминах степеней некоторой матрицы).

Не совсем понял что вы имеете ввиду. Каким образом в $r_i(k)$ учавствует количество пападаний в какое нибудь состояние, например s?
Если не сложно, можете так же написать источник?

[Хорхе]

Источник -- голова и математическое образование. В книжках о цепях Маркова, думаю, это можно найти.

Да, я изначально неправильно понял Ваш второй вопрос. Теперь понял и вижу, что он посложнее. Тут так же выписываются соотношения очень похожие на те, что я написал, но без $k$. То есть теперь у нас не рекуррентные соотношения, а система уравнений. С которой могут возникнуть проблемы. Скажем, если решение не единственно, то что это в данном случае означает?