Цепи Маркова в теории вероятности и их приложения

курсовая работа

5. Примеры решения задач

Задача о стопке книг. Очевидно, если каждая книга выбирается с положительной вероятностью, т. е. pi>0 при всех i=1,..., т, то любое состояние достижимо из каждого другого состояния. Всего имеется т! различных состояний (i1, …, im) и все они будут возвратными. Если pi = 0 при некотором i то все состояния вида(i1, …, im), где i1=i (книга с номером i лежит на самом верху), являются невозвратными, так как после первого же шага выбирается некоторая книга с номером j, отличным от i, и книга с номером i, никогда не вынимаемая из стопки, опускается ниже.

Задача о наилучшем выборе. Очевидно, через некоторое число шагов, не больше т (т -- число всех имеющихся предметов), система попадает в состояние еm+1, в котором остается навсегда. Таким образом, все состояния, кроме еm+1, являются невозвратными.

Случайные блуждания. Рассмотрим случайное блуждание, при котором частица из каждой целочисленной точки i на следующем шаге с вероятностью р переходит в соседнюю точку j=i - 1, а с вероятностью q -- в точку j=i - 1. Ясно, что каждое состояние достижимо из любого другого состояния и (см. формулу (6.0))

Используя формулу Стирлинга, при п>? получаем

где

причем знак равенства имеет место лишь при р = q=. Таким образом, при п>?

,

откуда следует, что ряды

и

сходятся или расходятся одновременно. При р ? q, когда 4pq<1, ряд сходится, и следовательно, каждое состояние i является невозвратным. Интуитивно ясно, что, например, при р>q блуждающая частица постепенно будет уходить все дальше и дальше в положительном направлении, рано или поздно навсегда покидая любое фиксированное состояние i. При неограниченно продолжающемся симметричном случайном блуждании, когда р = q=, частица бесконечное число раз возвращается в каждое из состояний.

Рассмотрим теперь случайное блуждание, при котором частица из неотрицательной целой точки i на следующем шаге с вероятностью рi смещается в соседнюю точку j = i + 1, а с вероятностью qi = 1--рi переходит в нулевую точку j = 0. Очевидно, если все вероятности рi таковы, что 0<pi<1, то все состояния являются достижимыми одно из другого. Все они будут возвратными или невозвратными.

Предположим, что система находится в состоянии i=0. Вероятность того, что за последующие п шагов она ни разу не вернется в исходное положение i = 0, равна произведению p0p1 …pn-1 -- вероятности того, что система последовательно пробегает цепочку состояний 0>1>...>п. Легко видеть, что вероятность за бесконечное число шагов ни разу не вернуться в исходное состояние i = 0 равна бесконечному произведению

.

Если это бесконечное произведение сходится к нулю: lim p0р1 ...рп = 0, то состояние i = 0 (а вместе с ним и все остальные) является возвратным. В противном случае вероятность возвращения есть

и состояние i=0 (а вместе с ними все остальные) является невозвратным.

К этому результату можно прийти и другим путем, непосредственно рассматривая вероятности хk впервые вернуться в исходное состояние 0 ровно через k шагов. Очевидно, частица впервые возвращается в состояние 0 на k-м шаге, если она на первых k -- 1 шагах последовательно переходит из состояния i--1 в i (с вероятностями рi-1, i=1, ..., k -- 1), и потому

, ; k= 2, 3, ...

Вероятность возвращения в исходное состояние 0 по определению равна суммеесть

.

Рассмотрим цепь Маркова с конечным числом состояний е1, е2, …, еm, каждое из которых достижимо из любого другого состояния. Более того, предположим, что существует такое N. что за N шагов система с положительной вероятностью может перейти из каждого состояния еi в любое

Теорема. Вероятности pj (п), с которыми через п шагов система будет находиться в соответствующих состояниях еj, j = 1, …, т, при п>? имеют предельные значения

.

Указанные финальные вероятности j= 1, …, т, не зависят от начального распределения и, более того,

,

где С и D -- некоторые положительные постоянные.

Доказательство. Положим

, .

Имеем

Таким образом, получаем следующую цепочку неравенств:

Для любых состояний еб и ев

где означает суммирование по всем тем k, при которых разность рбk(N)--рвk(N) является положительной, а --суммирование по всем тем k, при которых разность рбk(N)--рвk(N) является отрицательной. Очевидно, в силу условия (8.12)

Используя полученные соотношения, оценим разность . Имеем

Отсюда, вытекает, что

, k=1, 2, ...

Последовательность rj(n), n=1, 2, ..., монотонно возрастает, а последовательность rj(n), n =1, 2, ..., монотонно убывает, причем . Полученная выше оценка разности показывает, что эти последовательности имеют один и тот же предел :

Очевидно,

При любом начальном распределении , i=1,..., m, имеем

Полученные оценки, конечно, можно переписать в виде(8.14) соответствующих постоянных С и D, полагая

,

Теорема доказана.

Финальные вероятности , j = 1, ..., т, являются решением следующей системы линейных уравнений:

j =1, … ,т. (8.15)

Эти уравнения получаются, если в формуле (8.4), согласно которой

перейти к пределу при n>?.

Рассмотрим произвольную цепь Маркова с состояниями е1, е2, … и числа , i=1, 2..., такие, что

,

j=1, 2, …

Взяв , i=1, 2, ..., в качестве начального распределения вероятностей, будем иметь следующие вероятности pj(п) для нахождения системы в соответствующих состояниях еj через п шагов:

Видно, что вероятности рj (п) остаются неизменными:

, j = 1, 2, .... (8.18)

каково бы ни было i=1, 2, ...

Цепь Маркова называется стационарной, если вероятности , j = 1, 2, .... остаются неизменными при всех n = 0, 1, ...; стационарным называется и соответствующее распределение вероятностей , j = 1, 2, .... Согласно формуле (8.4) распределение вероятностей , j=1, 2, ..., является стационарным тогда и только тогда, когда оно удовлетворяет системе уравнений (8.17).

Если при любом начальном, распределении существуют одни и те же финальные вероятности , то стационарное распределение единственно: , j=1, 2, … Полученные выше результаты могут быть соединены в следующую теорему.

Теорема. При условии (8.12) финальные вероятности j=1, ..., m , являются единственным решением системы линейных уравнений (8.15), удовлетворяющим дополнительному требованию вида , и образуют стационарное распределение вероятностей.

Остановимся на рассмотренных ранее примерах.

Задача о стопке книг. Как показывают проведенные ранее расчеты, для т = 2 стационарное распределение вероятностей возникает уже на первом шаге:

,

при всех n=1, 2, ... и любом начальном распределении вероятностей.

Рассмотрим случай произвольного т. Обозначим , вероятность перехода из состояния в состояние . Как было показано,

где перестановка получается из выбором некоторого и перестановкой его на первое место.

Финальные вероятности являются решением следующей системы линейных уравнений:

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

Вероятность того, что сверху лежит книга с номером i, есть, очевидно,

,

где берется сумма по всем состояниям, в которых на первом месте стоит i.

Из уравнений для финальных вероятностей получаем, что

, i=1, …, m.

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

Делись добром ;)