Версия для печати темы

Автор: steph 13.1.2009, 15:33

Здравствуйте!
Помогите пожалуйста с цепью Маркова.
Цепь Маркова имеет вид
1 0 0 0 0 0
0.25 0.5 0.25 0 0 0
1/16 0.25 0.25 0.25 1/16 1/8
0 0 0.25 0.5 0.25 0
0 0 0 0 1 0
0 0 1 0 0 0

Надо найти вероятность того , что выходя из состояния 2,3,4,6 система завершит эволюцию в состоянии 5.
Подскажите пожалуйста , с чего надо начать?

Автор: malkolm 13.1.2009, 16:08

Дам неоригинальный совет: с определений
Что такое ЦМ, что за матрица тут у Вас нарисована (см. "матрица вероятностей перехода за один шаг"). Какой смысл имеют чиселки в этой матрице. Можно ли, выйдя из состояния 1, оказаться в состоянии 2, можно ли, выйдя из состояния 2, оказаться в состоянии 5 и т.д.

Автор: steph 13.1.2009, 16:31

Матрица вероятностей перехода.
Числа в матрице - нача́лное распределе́ние цепи Маркова. При этом в строке их сумма не может превышать 1. Вероятность выхода из состояния 1 в 2 равна 0.

Вот если
1 0 0 0 0 0
0.25 0.5 0.25 0 0 0
1/16 0.25 0.25 0.25 1/16 1/8
0 0 0.25 0.5 0.25 0
0 0 0 0 1 0
0 0 1 0 0 0
состояние 1, то ведь

1 0 0 0 0 0
0.25 0.5 0.25 0 0 0
1/16 0.25 0.25 0.25 1/16 1/8
0 0 0.25 0.5 0.25 0
0 0 0 0 1 0
0 0 1 0 0 0
*
1 0 0 0 0 0
0.25 0.5 0.25 0 0 0
1/16 0.25 0.25 0.25 1/16 1/8
0 0 0.25 0.5 0.25 0
0 0 0 0 1 0
0 0 1 0 0 0

состояние 2.

Автор: malkolm 13.1.2009, 17:23

Неправильно. Числа в матрице СОВСЕМ не есть первоначальное распределение ЦМ. Первоначальное распределение задаётся вектором вероятностей p(k) того, что X(0)=k: (p(1),...,p(n)), где p(k)=P(X(0)=k).

Ищите, что такое матрица вероятностей ПЕРЕХОДА.

Автор: steph 13.1.2009, 17:30

Матрицы вероятностей перехода являются средством описания поведения марковской цепи. Каждый элемент этой матрицы представляет собой вероятность перехода из заданного состояния (строка) к следущему состоянию (столбец). В этой матрице предусмотрены все возможные переходы данного множества состояний.
s1 s2 s3
p11 p12 p13
P = p21 p22 p23
p31 p32 p33

P - матрица переходных вероятностей, pi,j - вероятность перехода из состояний s1,s2.,s3


То есть вероятность p12 вероятность перехода из s1 в s2

Автор: malkolm 13.1.2009, 17:52

Верно. Вы ещё забыли ключевые слова "за один шаг". Теперь остались ещё два вопроса (см. выше): "Можно ли, выйдя из состояния 1, оказаться в состоянии 2, можно ли, выйдя из состояния 2, оказаться в состоянии 5 и т.д."

Автор: steph 13.1.2009, 17:55

Из состояния 1 в состояние 2 - вероятность перехода = 0
Из 2 в 5 , также равна 0.

Автор: malkolm 13.1.2009, 19:22

Найдите где-нибудь в моём вопросе слова "за один шаг"! Их нет. Снова спрошу: можно ли, выйдя из состояния 1, оказаться в состоянии 2, можно ли, выйдя из состояния 2, оказаться в состоянии 5 и т.д.?

Автор: steph 13.1.2009, 19:41

За n шагов , из 1 во 2 состояние перейти нельзя. А из 2-ого в 5-ое можно.
Тк , для 6 шагов 1 и 5 ая строки остаются неизменными, то есть
1)1 0 0 0 0 0
5)0 0 0 0 1 0

Автор: malkolm 13.1.2009, 20:18

Так, а вернуться можно из 5-го обратно во 2-е?

Автор: steph 13.1.2009, 20:21

Нельзя , тк p(5,2)=0.

Автор: malkolm 13.1.2009, 20:33

А из третьего, 4-го в пятое и назад?

Пора делать выводы.

Автор: steph 13.1.2009, 20:38

Из 3 и 4 в 5-ое можно , а назад нельзя.
Тогда вероятность что за k шагов система из 2,3,4,6 может переместится в 5 будет равна 1????Правильно?

Автор: malkolm 13.1.2009, 20:56

Верно, но не за k, а за бесконечное. Какое бы k мы ни взяли, вероятность всё ещё не попасть в 5 положительна. Но вероятность никогда туда не попасть нулевая, а вероятность когда-нибудь туда попасть единичная.

Смотрите: каждый раз, когда мы попадаем в 2 (или 3,4), есть одна и та же положительная вероятность независимо от предыдущего пути (независимо - т.к. цепь Маркова) попасть в 5 за шаг или два. Например, из двойки в тройку, потом в пятёрку. Тем самым мы имеем независимые испытания (придя в двойку, попадём через два шага в 5, или нет) с одной и той же вероятностью успеха p. И ждём первого успеха. Вероятность того, что он никогда не наступит, равна нулю как предел (1-p)^n при n -> oo.

Автор: steph 13.1.2009, 21:04

Отлично , понял , спасибо большое . Значит теперь надо найти положительную вероятность p????

Автор: malkolm 13.1.2009, 21:05

Зачем её искать? Разве без этого не видно, что она положительна? Вы же ответили "да" на вопрос "можно ли попасть?". Тем самым обосновано, что рано или поздно цепь попадёт в пятёрку и там останется навсегда. Такое состояние ЦМ называется "поглощающим". Т.е. пятёрка - поглощающее состояние. А есть ли тут ещё поглощающие состояния?

Автор: steph 13.1.2009, 21:09

"Надо найти вероятность того , что выходя из состояния 2,3,4,6 система завершит эволюцию в состоянии 5."

То есть надо найти это p.

Автор: malkolm 13.1.2009, 21:12

Вы ничего не поняли. Вернитесь к сообщению, где Вы сделали выводы, и прочтите дальше ещё раз.

Автор: steph 13.1.2009, 21:23

то есть , теперь надо доказать , что матрица перехода будет на к - ом щаге будет иметь вид ( где x -любые числа
1 0 0 0 0 0
x21 x22 x23 x24 x25 x26
x31 x32 x33 x34 x35 x36
x41 x42 x43 x44 x45 x46
0 0 0 0 1 0
x61 x62 x63 x64 x65 x66
Тогда у меня пара вопрос( чтобы лучше разобраться) - P!=1????

Автор: malkolm 13.1.2009, 22:37

Ничего тут доказывать не нужно. Всё доказано выше. Ещё раз: рано или поздно цепь, выйдя из 2,3,4,6, ПРИДЁТ в состояние 5. Какой тогда ответ на вопрос о том, с какой вероятностью цепь "завершит эволюцию в состоянии 5"?

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

Автор: steph 13.1.2009, 23:09

вероятность равна 1.
Граф нарисовал , получилось , что 2 3 4 6 могут переходить из одно в другое . а вот в 1 и 5 они могут только перейти , но не могут вернуться.

Но,
пусть шаг k
1 0 0 0 0 0
x21 x22 x23 x24 x25 x26
x31 x32 x33 x34 x35 x36
x41 x42 x43 x44 x45 x46
0 0 0 0 1 0
x61 x62 x63 x64 x65 x66


вероятность перехода из 2 в 5 равна x25.


То есть я хочу сказать , что безусловно из состояний 2 3 4 6 когда-нибудь перейдут в 5 . Но вот например на k-ом шаге надо будет посчитать Pk из 2х в 5
1 0 0 0 0 0
x21 x22 x23 x24 x25 x26
x31 x32 x33 x34 x35 x36
x41 x42 x43 x44 x45 x46
0 0 0 0 1 0
x61 x62 x63 x64 x65 x66

которое будет равно x25 , может есть закономерность между x25 на k-ом шаге и x25 на k+n. Тогда x25(k+n)=x25(k)/n например.

Автор: malkolm 14.1.2009, 9:19

Слушайте, я балда. Про состояние 1-то мы совсем забыли, а ведь туда тоже можно уйти и там навсегда остаться, при этом в 5 мы ни в жисть не попадём... Поглощающих состояний не одно, а два, и они не сообщаются, что сильно меняет дело: в том рассуждении выше про "успех когда-нибудь наступит" успехом будет не уход в 5, а уход в 5 или 1.

Тогда всё хуже. Состояния 2,3,4,6 являются несущественными (из них когда-нибудь уйдём). Тогда вероятности p_i(5) того, что, выйдя из i=2,3,4,6, цепь в итоге окажется в состоянии 5, есть решение системы уравнений:

p_i(5)=sum(k=2,3,4,6) x_ik*p_k(5) + x_i5

Это просто формула полной вероятности по гипотезам о положении на следующем шаге после выхода из i: выйдя из i прийти в итоге в 5 можно либо сразу за шаг (с вероятностью x_i5), либо сначала попав в k, а из него с вероятностью p_k(5) прийти в итоге в 5.

Решив эту систему, получим нужные вероятности. Для попадания в 1 тоже такая же система.

Автор: malkolm 14.1.2009, 9:34

Это ж надо, давно не приходилось так накалываться Надо начать читать студентам ЦМ, а то навык уходит Спасибо за настойчивость ))

Система уравнений у меня получилась такая, проверьте:
p_2(5)=0.5*p_2(5)+0.25*p_3(5);
p_3(5)=0.25*p_2(5)+0.25*p_3(5)+0.25*p_4(5)+1/8*p_6(5)+1/16;
p_4(5)=0.25*p_3(5)+0.5*p_4(5)+0.25;
p_6(5)=1*p_3(5).

Автор: steph 14.1.2009, 9:51

=) хочу просто до конца разобраться))))

То есть мы здесь не используем 1-ый столбец , тк не нужен переход в 1?

Автор: malkolm 14.1.2009, 9:57

Угу.

Автор: steph 14.1.2009, 10:08

После решения системы получил следующее:
p2=0,5p3
p3=p2+0,25p4+1/16
p4=0,25p3+0,5p4+0,25
p6=p3

p2=0,5p3
0,5p3=0,25p4+1/16
p4=0,25p3+0,5p4+0,25
p6=p3

p2=0,5p3
0,5p3=0,25p4+1/16
p4=0,125p4+1/32+0,5p4+0,25
p6=p3

p2=0,5p3
0,5p3=0,25p4+1/16
p4=0,75
p6=p3

p2=0,25
p3=0,5
p4=0,75
p6=0,5

Тогда получается это и есть ответ?

Автор: malkolm 14.1.2009, 10:15

Да, именно. Можно для развлечения составить такую же систему для ппопадания в единицу, решить и проверить - получаются ли дополнительные вероятности p_2(1)=0,75 и т.д.

Автор: steph 14.1.2009, 10:19

Понятно , так щас и сделаю . Спасибо огромное!

Автор: malkolm 14.1.2009, 10:46

Пожалуйста. И мои извинения за "запудривание мозгов" ночью

Автор: steph 14.1.2009, 17:29

Полная вероятность P(A)=sum{ P(A| B ) P( B ) }
Где B- полный набор событий , A- необходимое событие.
Можете пожалуйста объяснить , откуда получилась p_i(5)=sum(k=2,3,4,6) x_ik*p_k(5) + x_i5 эта формула?

Автор: malkolm 14.1.2009, 17:36

Выше всё объяснено. Перечислите гипотезы, которые выше описаны, событие А тоже там указано.