Граф Состояний (дискретная цепь Маркова)

[Наташа-дельфин]

Здравствуйте!
Можно ли мне спросить?

У меня вот такая задача:
Дан размеченный граф состояния системы S момент Т=0 система находится в состоянии S1 Составить матрицу переходных вероятностей,найти распределение вероятностей состояний для перпвых 5-ти шагов (на рисунке: четыре квадрата (S1,S2,S3 и S4) и стрелочки их соединяющие:
из S2 в S4
из S3 в S4
S1 и S3 "туда-обратно"
S1 и S2 "туда-обратно"
А над стрелочками даны численные значения р13 р31 р12 р21 р34 р24

И я никак не пойму:
Что такое "первые 5 шагов" ?
И что значит "найти РАСПРЕДЕЛЕНИЕ вероятностей" ? (вероятность - это ведь функция от времени и в учебнике написано как написать систему уравнений для моей системы но....дальше я не знаю что делать: вот я ее написала....а что с ней делать?!)

Помогите пожалуйста! (хотя бы скажите что это означает)
Спасибо....

[незваный гость]

Если я правильно понимаю, речь идет о том, что в начальный момент система находится в состоянии $S_1$. При очередном шаге, система может перейти из состояния $S_k$ в $S_m$ с вероятностью $p_{k,m}$, если есть дуга, идущая из $S_k$ в $S_m$. Очевидно, после первого шага, система будет либо в $S_2$ (с вероятностью $p_{1,2}$), либо в $S_3$ (с вероятностью $p_{1,3}$). Найти рапределение - подсчитать вероятности нахождения системы в каждом из пяти состояний после заданного числа шагов.

Матрица переходных вероятностей - матрица, элементами которой являются вероятности перехода $p_{k,m}$ из состояния $S_k$ в $S_m$. Очевидно, что если дуга отсутствует, то переход невозможен, и его вероятность равна 0.

Наташа-дельфин писал(а):

Что такое "первые 5 шагов" ? ... (вероятность - это ведь функция от времени

Вы имеете дело с дискретным временем. Номер шага - это и есть время. То есть, Т=0 - начальное состояние, Т=1 - после первого шага, Т=2 - после второго, и так далее.

Задачи этого типа изучаются в теории Марковских процессов.

Счастливо кувыркаться в волнах, и вкусной рыбы

[Наташа-дельфин]

А это точно то что p31, p21, p12 и т д - вероятности?
Просто тогда - а для какого времени они раз это вероятности? Ведь даны их численные значения (например р31=0.1)

[Наташа-дельфин]

В учебнике я нашла похожий рисунок но там над стрелочками подписана "лямда12", "лямда21" и т д - и они называют эту величину "плотностью потока" - так может и в моей задаче это плотность? (только другими буквами обозначенные)

[PAV]

В Вашей задаче нет понятия времени, есть понятие "шаг". Один шаг, два и т.д. Ваши числа - это вероятности за один шаг.

[PAV]

Наташа-дельфин писал(а):

В учебнике я нашла похожий рисунок но там над стрелочками подписана "лямда12", "лямда21" и т д - и они называют эту величину "плотностью потока" - так может и в моей задаче это плотность? (только другими буквами обозначенные)

Нет, плотность потока - это из другой области. Плотности потока могут быть произвольными положительными числами (в том числе и >1), а Вы имеете дело с вероятностями.

[Наташа-дельфин]

PAV писал(а):

В Вашей задаче нет понятия времени, есть понятие "шаг". Один шаг, два и т.д. Ваши числа - это вероятности за один шаг.

То есть раз мне дано р31=0.1 значит это тождественно р31(t)=p31(1)=0.1 и следовательно p31(2)=0.2 ???? неужели в задаче требуют такие элементарные действия??

[Someone]

Наташа-дельфин писал(а):

PAV писал(а):

В Вашей задаче нет понятия времени, есть понятие "шаг". Один шаг, два и т.д. Ваши числа - это вероятности за один шаг.

То есть раз мне дано р31=0.1 значит это тождественно р31(t)=p31(1)=0.1 и следовательно p31(2)=0.2 ???? неужели в задаче требуют такие элементарные действия??

Это задача на цепи Маркова. Смотрите там.

[незваный гость]

Наташа-дельфин писал(а):

То есть раз мне дано р31=0.1 значит это тождественно р31(t)=p31(1)=0.1 и следовательно p31(2)=0.2 ???? неужели в задаче требуют такие элементарные действия??

Нет, после шага 1 Вы уже с вероятностью p31(1)=0.1 не в состоянии S1, а в состоянии S3. p - это вероятности перехода, они от шагов не зависят. Вам же нужно подсчитать вероятности нахождения в том или ином состоянии.

[Наташа-дельфин]

А как находятся?
У меня 9 учебников и только в одном что-то похожее - с плотностью потока - но PAV сказал это совсем из другой в области а в местах где пишут про цепи маркова вообще ничего похожего........[/quote]

[PAV]

Наташа-дельфин писал(а):

То есть раз мне дано р31=0.1 значит это тождественно р31(t)=p31(1)=0.1 и следовательно p31(2)=0.2 ???? неужели в задаче требуют такие элементарные действия??

Конечно же, нет. Если рассуждать так, что через 15 шагов вероятность была бы равна 1.5, чего быть не может никак.

Смотрите. Вероятность за 1 шаг перейти из состояния 1 в 2 равна p12, а из 2 в 3 - p23. Может так случиться, что система именно такие переходы и сделает последовательно: 1-2-3. Вероятность именно такой системы переходов равна произведению p12 на p23, так как по определнию марковской цепи данные события независимы. Это пример того, как можно за 2 шага перейти из состояния 1 в 3.

Но это не единственный способ осуществить переход из 1 в 3 за два шага, так как промежуточное состояние может быть любым. Таким образом, необходимо: перебрать все имеющиеся состояния k и просуммировать вероятности переходов 1-k-3, которые вычисляются так, как показано выше. В том числе k может быть и 1, и 3, так как вообще говоря могут быть тождественные переходы (т.е. с вероятностью pkk система за 1 шаг остается в состоянии k). Это уже будет в точности вероятность перейти из 1 в 3 за два шага.

Если Вы запишете матрицу переходных вероятностей, в которой в первой строке стоят вероятности перехода из первого состояния (p11, p12, p13,..), во второй - из второго и т.д., и умножите эту матрицу саму на себя по стандартному правилу умножения матриц, то увидите (сопоставив формулы умножения с тем, что написано выше), что полученная матрица состоит из вероятностей перехода за 2 шага.

В вашей задаче требуется найти вероятности перехода за 5 шагов, т.е. найти произведение матриц A*A*A*A*A, где A - матрица перехода за 1 шаг.

[один Холодный Дельфин]

ps
Решила зарегистрироваться у вас - понравилось (на всякий случай - я - это автор топика то есть наташа-дельфин)
И по делу:

Цитата:

Смотрите. Вероятность за 1 шаг перейти из состояния 1 в 2 равна p12, а из 2 в 3 - p23. Может так случиться, что система именно такие переходы и сделает последовательно: 1-2-3. Вероятность именно такой системы переходов равна произведению p12 на p23,

то есть р12 х р23 = р123 ?
где р123 - это вероятность второго шага ?

Цитата:

Но это не единственный способ осуществить переход из 1 в 3 за два шага, так как промежуточное состояние может быть любым

Да ? А каким? Если учесть что в расм.примере система состоит из состояний 1,2, и 3 и стрелочки только в направлении 1>2>3 ? Или вы говорите с учетом и других возможных стрелочек?
[/quote]

[PAV]

Да, можно обозначить р123 = р12 х р23. Тогда p123 будет вероятностью события, которое словами произносится так: "Вероятность того, что система, которая при T=0 была в состоянии 1, при T=1 окажется в состоянии 2, а при T=2 окажется в состоянии 3".

Если же мы хотим найти вероятность перехода за два шага, которую можно обозначить p1*3 (хотя более общепринятое обозначение $p_{13}^{(2)}$), то эта величина словами произносится так:"Вероятность того, что система, которая при T=0 была в состоянии 1, при T=2 окажется в состоянии 3". Обратите внимание на отличие от предыдущей фразы: состояние при T=1 не указывается, оно может быть любым.

Соответственно, p1*3 складывается из: p113, p123, p133, p143,..., p1n3, где n - общее число всех состояний. Если некоторые из этих переходов на графе не указаны, то это означает, что соответствующая вероятность равна нулю.