Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Цепи Маркова

Читайте также:
  1. Доверительный интервал для параметров регрессионной модели.
  2. Дополнительная
  3. Лекция 2
  4. Общие сведения и экономико-географическое положение
  5. Показатели систем качества
  6. Понятие о случайном процессе.
  7. Состоятельность и несмещенность МНК-оценок
  8. Эффективность оценок МНК. Теорема Гаусса-Маркова



Марковский процесс - протекающий в системе случайный процесс, который обладает свойством: для каждого момента времени t0 вероятность любого состояния системы в будущем (при t>t0) зависит только от ее состояния в настоящем (при t= t0) и не зависит от того, когда и каким образом система пришла в это состояние (т.е. как развивался процесс в прошлом).

На практике часто встречаются случайные процессы, которые с той или иной степенью приближения можно считать Марковскими.

Любой марковский процесс описывают с помощью вероятностей состояний и переходных вероятностей.

Вероятности состояний Pk(t) марковского процесса – это вероятности того, что случайный процесс (система) в момент времени t находится в состоянии Sk:

 

Переходные вероятности марковского процесса – это вероятности перехода процесса (системы) из одного состояния в другое:

 

 

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

Наиболее простым процессом является цепь Маркова – марковский случайный процесс с дискретным временем и дискретным конечным множеством состояний.

При анализе цепи Маркова составляют граф состояний, на котором отмечают все состояния цепи (системы) и ненулевые вероятности за один шаг.

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

Переходные вероятности цепи Маркова за один шаг записывают в виде матрицы P=||Pij||, которую называют матрицей вероятностей перехода или просто переходной матрицей.

Пример: множество состояний студентов специальности следующие:

S1 – первокурсник;

S2 – второкурсник …;

S5 – студент 5 курса;

S6 –специалист, окончивший вуз;

S7 – человек, обучавшийся в вузе, но не окончивший его.

Из состояния S1 за год возможны переходы в состояние S2 с вероятностью r1; S1 с вероятностью q1 и S7 с вероятностью p1, причем:

r1+q1+p1=1.

Построим граф состояний данной цепи Маркова и разметим его переходными вероятностями (отличными от нуля).

 

 

Составим матрицу вероятностей переходов:

 

Переходные матрицы обладают свойством:

- все их элементы неотрицательны;

- их суммы по строкам равны единице.

Матрицы с таким свойством называют стохастическими.

Матрицы переходов позволяют вычислить вероятность любой траектории цепи Маркова с помощью теоремы умножения вероятностей.

Для однородных цепей Маркова матрицы переходов не зависят от времени.



При изучении цепей Маркова наибольший интерес представляют:

- вероятности перехода за m шагов;

- распределение по состояниям на шаге m→∞;

- среднее время пребывания в определенном состоянии;

- среднее время возвращения в это состояние.

Рассмотрим однородную цепь Маркова с n состояниями. Для получения вероятности перехода из состояния Si в состояние Sj за m шагов в соответствии с формулой полной вероятности следует просуммировать произведения вероятности перехода из состояния Siв промежуточное состояние Sk за l шагов на вероятность перехода из Sk в Sj за оставшиеся m-l шагов, т.е.

 

 

Это соотношение для всех i=1, …, n; j=1, …,n можно представить как произведение матриц:

P(m)=P(l)*P(m-l).

Таким образом, имеем:

P(2)=P(1)*P(1)=P2

P(3)=P(2)*P(1)=P(1)*P(2)=P3 и т.д.

P(m)=P(m-1)*P(1)=P(1)*P(M-1)=Pm,

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

Пример: Погода в некотором регионе через длительные периоды времени становится то дождливой, то сухой. Если идет дождь, то с вероятностью 0,7 он будет идти на следующий день; если в какой-то день сухая погода, то с вероятностью 0,6 она сохраниться и на следующий день. Известно, что в среду погода была дождливая. Какова вероятность того, что она будет дождливой в ближайшую пятницу?

Запишем все состояния цепи Маркова в данной задаче: Д – дождливая погода, С – сухая погода.

Построим граф состояний:

 

Составим матрицу вероятностей перехода:

 

Ответ: р11=р(Дпятср) =0,61.

 

Пределы вероятностей р1(m), р2(m),…, рn(m) при m→∞, если они существуют, называются предельными вероятностями состояний.

Можно доказать следующую теорему: если в цепи Маркова из +каждого состояния можно перейти (за то или иное число шагов) в каждое другое, то предельные вероятности состояний существуют и не зависят от начального состояния системы.

Таким образом, при m→∞ в системе устанавливается некоторый предельный стационарный режим, при котором каждое из состояний осуществляется с некоторой постоянной вероятностью.

Вектор р, составленный из предельных вероятностей, должен удовлетворять соотношению: р=p*P.

Среднее время пребывания в состоянии Si за время T равно pi*T, где pi -предельная вероятность состояния Si . Среднее время возвращения в состояние Si равно .

Пример.

Для многих экономических задач необходимо знать чередование годов с определенными значениями годовых стоков рек. Конечно, это чередование не может быть определено абсолютно точно. Для определения вероятностей чередования (перехода) разделим стоки, введя четыре градации (состояния системы): первую (самый низкий сток), вторую, третью, четвертую (самый высокий сток). Будем для определенности считать, что за первой градацией никогда не следует четвертая, а за четвертой – первая из-за накопления влаги (в земле, водохранилище и т.д.). Наблюдения показали, что в некоторой области остальные переходы возможны, и:

а) из первой градации можно переходить в каждую из средних вдвое чаще, чем опять в первую, т.е.

p11=0,2; p12=0,4; p13=0,4; p14=0;

б) из четвертой градации переходы во вторую и третью градации бывают в четыре и пять раз чаще, чем возвращениеекак д во вторую, т.е.

твертую, т.е.

в четвертую, т.е.

p41=0; p42=0,4; p43=0,5; p44=0,1;

в) из второй в другие градации могут быть только реже: в первую - в два раза, в третью на 25%, в четвертую - в четыре раза реже, чем переход во вторую, т.е.

p21=0,2;p22 =0,4; p23=0,3; p24=0,1;

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

p31=0,1; p32=0,4; p33=0,4; p34=0,1;

 

Построим граф:

Составим матрицу вероятностей перехода:

 

P=

Найдем среднее время между засухами и полноводными годами. Для этого нужно найти предельное распределение. Оно существует, т.к. условие теоремы выполняется (матрица Р2 не содержит нулевых элементов, т.е. за два шага можно перейти из любого состояния системы в любое другое).

Используем соотношение: p=p*P.

Запишем его в виде системы:

=*

или

Это однородная система линейных алгебраических уравнений. Ее можно решить, например, методом Гаусса. Для этого необходимо привести матрицу системы к треугольному виду:

вычтем из 3 вторую сложим вторую с

первой *2 сложим 2 и 3 и эту сумму прибавим к 4

вычтем из 3-ей вторую, умноженную на 9

Система приведена к треугольному виду. Но мы имеем 3 уравнения и 4 неизвестных. Добавим условие p1+p2+p3+p4=1, т.к. система обязательно находится в одном из своих состояний.

Получим:

П

Откуда p4 =0.08; p3=; p2=; p1=0.15

Периодичность возвращения в состояние Si равна .

Следовательно, периодичность засушливых лет в среднем равна 6.85, т.е. 6-7 лет, а дождливых 12 лет.

 

 





Дата добавления: 2014-01-05; Просмотров: 1468; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:



studopedia.su - Студопедия (2013 - 2017) год. Не является автором материалов, а предоставляет студентам возможность бесплатного обучения и использования! Последнее добавление ip: 54.81.44.140
Генерация страницы за: 0.009 сек.