2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

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



Начать новую тему Ответить на тему
 
 Граф Состояний (дискретная цепь Маркова)
Сообщение15.11.2005, 19:15 
Здравствуйте!
Можно ли мне спросить?

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

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

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

  
                  
 
 Re: Граф Состояний (не пойму чего хотят :( )
Сообщение15.11.2005, 20:04 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Если я правильно понимаю, речь идет о том, что в начальный момент система находится в состоянии $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 - после второго, и так далее.

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

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

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

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

  
                  
 
 
Сообщение16.11.2005, 00:26 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
В Вашей задаче нет понятия времени, есть понятие "шаг". Один шаг, два и т.д. Ваши числа - это вероятности за один шаг.

 Профиль  
                  
 
 
Сообщение16.11.2005, 00:28 
Супермодератор
Аватара пользователя


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


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

 Профиль  
                  
 
 
Сообщение16.11.2005, 00:56 
PAV писал(а):
В Вашей задаче нет понятия времени, есть понятие "шаг". Один шаг, два и т.д. Ваши числа - это вероятности за один шаг.


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

  
                  
 
 
Сообщение16.11.2005, 01:12 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
Наташа-дельфин писал(а):
PAV писал(а):
В Вашей задаче нет понятия времени, есть понятие "шаг". Один шаг, два и т.д. Ваши числа - это вероятности за один шаг.


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


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

 Профиль  
                  
 
 
Сообщение16.11.2005, 01:24 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Наташа-дельфин писал(а):
То есть раз мне дано р31=0.1 значит это тождественно р31(t)=p31(1)=0.1 и следовательно p31(2)=0.2 ???? неужели в задаче требуют такие элементарные действия?? :shock:


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

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

  
                  
 
 
Сообщение16.11.2005, 09:44 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Наташа-дельфин писал(а):
То есть раз мне дано р31=0.1 значит это тождественно р31(t)=p31(1)=0.1 и следовательно p31(2)=0.2 ???? неужели в задаче требуют такие элементарные действия?? :shock:


Конечно же, нет. Если рассуждать так, что через 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 шаг.

 Профиль  
                  
 
 
Сообщение17.11.2005, 00:09 


16/11/05
1
Москва
ps
Решила зарегистрироваться у вас :) - понравилось :P (на всякий случай - я - это автор топика то есть наташа-дельфин)
И по делу:
Цитата:
Смотрите. Вероятность за 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]

 Профиль  
                  
 
 
Сообщение17.11.2005, 00:27 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Да, можно обозначить р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 - общее число всех состояний. Если некоторые из этих переходов на графе не указаны, то это означает, что соответствующая вероятность равна нулю.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group