Вернуться на страницу <Методические разработки>
В начало | Л.р.1 | Л.р.2 | Л.р.3 | Л.р.4 | Л.р.5 | Л.р.6 | Л.р.7

| Л.р.8 | Л.р.9 | Л.р.10 |  Л.р.12 | Л.р.13 | Л.р.14 | Л.р.15

Лабораторная работа 11
Однородные цепи Маркова

цепь Маркова ~ матрица перехода ~ однородные цепи Маркова ~ теорема о предельных вероятностях ~ эргодические цепи ~ стационарное распределение

Пусть { , , ..., ,...} - множество возможных состояний некоторой физической системы. В любой момент времени система может находитьcя только в одном состоянии. С течением времени система переходит последовательно из одного состояния в другое. Каждый такой переход называется шагом процесса.

Для описания эволюции этой системы введем последовательность дискретных случайных величин , ,..., ,... Индекс n играет роль времени. Если в момент времени n система находилась в состоянии , то мы будем считать, что =j. Таким образом, случайные величины являются номерами состояний системы.

Последовательность , ,..., ,... образует цепь Маркова, если для любого n и любых , , ...,

P( =j| = , ..., =i)=P( =j| =i).

Для цепей Маркова вероятность в момент времени n попасть в состояние , если известна вся предыдущая история изучаемого процесса, зависит только от того, в каком состоянии находился процесс в момент n-1; короче: при фиксированном "настоящем" "будущее" не зависит от "прошлого". Свойство независимости "будущего" от "прошлого" при фиксированном "настоящем" называется марковским свойством.

Вероятности ( =j| =i), i, j=1,2,..., r называются матрицами перехода из состояния в состояние за один шаг.

Цепь Маркова называется однородной, если вероятности перехода не зависят от n, т.е. если вероятности перехода не зависят от номера шага, а зависят только от того, из какого состояния и в какое осуществляется переход. Для однородных цепей Маркова вместо будем писать .

Вероятности перехода удобно располагать в виде квадратной матрицы

Матрица P называется матрицей вероятностей перехода однородной цепи Маркова за один шаг. Она обладает следующими свойствами:

а) ;

б) для всех i =1.

Квадратные матрицы, для которых выполняются условия а) и б), называются стохастическими.

Вектор , где =P( ), i=1,2...,r, называется вектором начальных вероятностей.

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

Можно показать, что матрица вероятностей перехода цепи Маркова за n шагов равняется n-ой степени матрицы P вероятностей перехода за один шаг.

Для однородной цепи Маркова при любом m выполняется равенство

P( | )=P( | ).

Но последняя вероятность есть вероятность перехода из состояния в состояние за n шагов.

Теорема о предельных вероятностях . Если при некотором все элементы матрицы =[ ] положительны, то существуют пределы

= , i,j=1,2,...,r.

Предельные вероятности не зависят от начального состояния и являются единственным решением системы уравнений

=1,

= , j=1, 2, ..., r.

Физический смысл этой теоремы заключается в том, что вероятности нахождения системы в состоянии практически не зависит от того, в каком состоянии она находилась в далеком прошлом.

Цепь Маркова, для которой существуют пределы , называется эргодической.

Решение ( , ,..., ) написанной выше системы называется стационарным распределением вероятностей для марковской цепи с матрицей перехода P=[ ].

Если из состояния система может перейти в состояние с положительной вероятностью за конечное число шагов, то говорят, что достижимо из .

Состояние называется существенным, если для каждого состояния , достижимого из , достижимо из . Если же для хотя бы одного j достижимо из , а не достижимо из , то - несущественное состояние.

(См. задачи в Чистяков В. П. Курс теории вероятностей: Учеб.-3-е изд., испр.-М.: Наука. Гл. ред. физ.-мат. лит.- 1987.)

Задача 1 . Матрица вероятностей перехода цепи Маркова имеет вид

. Распределение по состояниям в момент времени t=0 определяется вектором . Найти:

1) распределение по состояниям в момент t=2;

2) вероятность того, что в моменты t=0, 1, 2, 3 состяниями цепи будут соответственно 1, 3, 3, 2;

3) стационарное распределение.

Решение. Зададим матрицу P, вектор начальных вероятностей q и найдем матрицу P2 вероятностей перехода за два шага как :

> P:=array([[0.1, 0.5, 0.4], [.6, .2, .2], [.3, .4, .3]]);q:=array([.7,.2,.1]);P2:=linalg[multiply](P,P);

2) Найдем распределение по состояниям в момент t=2

> q2:=linalg[multiply](q,P2);

Найдем распределение по состояниям в момент t=1

> q1:=linalg[multiply](q,P);

Найдем распределение по состояниям в момент t=3

> P3:=linalg[multiply](P,P,P):q3:=linalg[multiply](q,P3);

Тогда искомую вероятность найдем так

> P:=q[1]*q1[3]*q2[3]*q3[2];

Здесь мы перемножили первую координату вектора q (вероятность того, что система в начальный момент времени находилась в состоянии 1), третью координату вектора q1 (вероятность того, что система в момент времени t=1 находилась в состоянии 3), третью координату вектора q2 (вероятность того, что система в момент времени t=2 находилась в состоянии 3), вторую координату вектора q3 (вероятность того, что система в момент времени t=3 находилась в состоянии 2).

3) Найдем стационарное распределение цепи Маркова. Для этого транспонируем матрицу P

> P:=linalg[matrix]([[0.1, 0.5, 0.4], [.6, .2, .2], [.3, .4, .3]]);Pt:=linalg[transpose](P);

Для нахождения собственного собственного вектора транспонированной матрицы, сумма координат которого равняется 1, составим систему линейных уравнений

> syst:={sum(Pt[1,k]*v[k],k=1..3)=v[1],sum(Pt[2,k]*v[k],k=1..3)=v[2],sum(Pt[3,k]*v[k],k=1..3)=v[3],sum(v[k],k=1..3)=1};

Решим эту систему

> solve(syst);

Таким образом, вектор v определяет стационарное распределение цепи Маркова.

Задача 2 . Пусть - номер состояния в цепи Маркова в момент времени t, P( )=1 и матрица вероятностей перехода за единицу времени равна ; , если и , если . Показать, что последовательность является цепью Маркова. Найти соответствующую ей матрицу вероятностей перехода.

Задача 3 . Игральная кость все время перекладывается случайным образом с одной грани равновероятно на любую другую из четырех соседних граней независимо от предыдущего. К какому пределу стремится при t стремящемся к бесконечности вероятность того, что в момент времени t кость лежит на грани "6", если в момент t=0 она находилась в этом же положении (t=0, 1, 2, 3, ...)?

Задача 4 . Матрица вероятностей перехода P и вектор q начального распределения по состояниям имеют вид: , .

Найти:

а) несущественные состояния;

б) математическое ожидание - времени выхода из несущественных состояний;

в) вероятности , попадания в множества состояний , , если начальным состоянием является i из {1, 2};

г) предельное при распределение по состояниям, т.е. величины .

Задача 4 . Матрица вероятностей перехода P=|| || цепи Маркова определяется формулами , , , . Доказать, что

.

Найти стационарные вероятности.

Указание. Для доказательства формулы примените метод математической индукции.

В начало | Л.р.1 | Л.р.2 | Л.р.3 | Л.р.4 | Л.р.5 | Л.р.6 | Л.р.7

| Л.р.8 | Л.р.9 | Л.р.10 | Л.р.12 | Л.р.13 | Л.р.14 | Л.р.15
Вернуться на страницу <Методические разработки>