Обратная задача теории цепей Маркова

[G^a]

Здравствуйте!

Стоит задача определить элементы матрицы $P$ - переходных вероятностей стационарной (однородной) конечномерной цепи Маркова. Задано:

1) некоторые элементы $P_{i,j}\equiv 0$, и они известны;

2) количество элементов $P_{i,j}=0$ превосходит количество элементов $P_{i,j}>0$;

3) известен $\mathbf{p}^*$ - вектор предельных абсолютных вероятностей состояния цепи, причём $p^*_i>0$, для любого i;

4) для любого $\mathbf{p}^o$ - вектора исходных абсолютных вероятностей состояния цепи, справедливо отношение:

$\mathbf{p}^*=(P^T)^\infty\,\mathbf{p}^o$.

Вопрос, как решается подобная задача и где можно почитать о путях её решения?


С уважением,
G^a.

[Евгений Машеров]

Как-нибудь через разложения по собственным векторам не получится? Зная, что у нас уже есть один с.в. (1, 1, 1...1), соответствующий с.з. $\lambda=1$

-- 30 мар 2012, 13:33 --

Что-то отсюда, в смысле...
http://www.sernam.ru/book_matrix.php?id=97

[Евгений Машеров]

Вот тут
http://narod.ru/disk/44704672001.be9819 ... x.pdf.html
ничего полезного нет?

[G^a]

Здравстуйте!

Евгений Машеров в сообщении #553759 писал(а):

Как-нибудь через разложения по собственным векторам не получится? Зная, что у нас уже есть один с.в. (1, 1, 1...1), соответствующий с.з. $\lambda=1$

-- 30 мар 2012, 13:33 --

Что-то отсюда, в смысле...
http://www.sernam.ru/book_matrix.php?id=97

Евгений Машеров в сообщении #553906 писал(а):

Вот тут
http://narod.ru/disk/44704672001.be9819 ... x.pdf.html
ничего полезного нет?

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

С уважением,
G^a.

[Евгений Машеров]

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

[G^a]

Здравствуйте!

Евгений Машеров в сообщении #554261 писал(а):

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

Впечатление верное, но с размерностью задачи всё в порядке. Есть доп. ограничения, в том числе по симметриям процесса, которые понижают количество неизвестных в матрице $P$ с $N^2$, до $N$. Я их изначально не привёл, чтобы не загромождать постановку задачи (и так понятно, что недоопределённые системы точного решения не имеют).

С уважением,
G^a.

[vajsaforutube]

На первый (наивный) взгляд ответ такой: ваш вектор $p^*$ - это главный собственный вектор вашей матрицы, который отвечает собственному значению 1 (если матрица стохастическая). Ведь после бесконечного числа умножений на матрицу любой входной вектор должен в него свалиться, т.к. главное собственное значение в степени n, где n->$\infty$ гораздо больше, чем любое другое собственное значение, меньшее его по модулю. (Я правильно понимаю, что левый собственный вектор, отвечающий собственному значению 1 - это просто [1,1,...1], а правый - это то, что вы наблюдали, $p^*$?)

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

[G^a]

Здравствуйте!

vajsaforutube в сообщении #564376 писал(а):

На первый (наивный) взгляд ответ такой: ваш вектор $p^*$ - это главный собственный вектор вашей матрицы, который отвечает собственному значению 1 (если матрица стохастическая).

Матрица стохастическая по определению.

vajsaforutube в сообщении #564376 писал(а):

Ведь после бесконечного числа умножений на матрицу любой входной вектор должен в него свалиться, т.к. главное собственное значение в степени n, где n->$\infty$ гораздо больше, чем любое другое собственное значение, меньшее его по модулю.

Согласен!

vajsaforutube в сообщении #564376 писал(а):

(Я правильно понимаю, что левый собственный вектор, отвечающий собственному значению 1 - это просто [1,1,...1], а правый - это то, что вы наблюдали, $p^*$?)

Не совсем понял это предложение. Я наблюдаю оба вектора: $\mathbf{p}^o$ -- вектор исходных абсолютных вероятностей состояния цепи и $\mathbf{p}^*$ -- вектор предельных абсолютных вероятностей состояния цепи (после $n\to\infty$ шагов). Известно также, что $\mathbf{p}^*$ получается из произвольного $\mathbf{p}^o$. Причём обязательно $p^*_i>0$, ну и $\sum p^*_i=1$, $\sum p^o_i=1$.

vajsaforutube в сообщении #564376 писал(а):

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

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

P.S.
Извините что долго молчал.

С уважением,
G^a.