Цепи Маркова в теории вероятности и их приложения
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 с которой эта книга выбирается. Таким образом, чем чаще берется та или иная книга, тем с большей вероятностью она будет находиться сверху.