Цепи Маркова в теории вероятности и их приложения
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
» (i1, i2, … … im), где i1 - номер книги, лежащей сверху, i2 - номер следующей книги, ..., iт-номер последней книги, лежащей в самом низу. Предположим, что каждая книга, берется с определенной вероятностью, скажем, книга с номером k берется с вероятностью рk (к=1, ..., m), причем при возвращении она кладется сверху.
Возьмем произвольное состояние (i1, i2, …, im). На следующем шаге оно либо остается неизменным, что происходит с вероятностью при выборе лежащей сверху книги с номером i1 либо меняется на одно из m - 1 состояний вида (ik, i1, ...), что происходит с вероятностью при выборе книги с номером ik. Перед нами цепь Маркова с состояниями, каждое из которых описывается соответствующей перестановкой (i1, i2, … … im), и указанными переходными вероятностями.
Остановимся на случае т = 2. Тогда имеется лишь два состояния: ?1=(1,2) и ?2 = (2, 1). Переходные вероятности имеют вид:
p11=p21=p1, p12=p22=p2
и матрица переходных вероятностей есть
Вероятности перехода за два шага суть
11(2)=p21(2)=p1p1+p2p1=p1(p1+p2)=p1,12(2)=p22(2)= p1p2+p2p2=p2(p1+p2)=p2.
Видно, что Р2 = Р и вообще Рn = Р. При любом начальном распределении вероятностей имеем (n =1, 2, ...)
1(n)= p11(n)+p21(n)=p1(+)=p1,2(n)= p12(n)+p2(n)=p2(+)=p2.
Задача о наилучшем выборе. Положим ?0(0)=1 и обозначим: ?(1) - порядковый номер первого предмета, оказавшегося наилучшим среди всех осмотренных ранее; ?(2)-порядковый номер следующего наилучшего среди всех осмотренных до него предметов и т. д. Цепочка ?(0)>?(1)>?(2)... обрывается на некотором ?-м шаге, если предмет с порядковым номером ?(?) оказывается абсолютно наилучшим, так что и среди не осмотренных еще предметов нет лучшего. Число ? является случайным, поскольку случайным является сам порядок осмотра. Введем состояния ?1, ?2, …?m, ?m+1, охарактеризовав их следующим образом: ?i при i=1, …, т означает, что предмет с порядковым номером i (т. е. i-й по счету осмотренный предмет) является наилучшим среди всех ранее осмотренных; ?m+1 означает, что уже осмотрен абсолютно наилучший предмет. Если положить ?(n) = ?m+1, при всех п>?, то последовательность ?(0)>?(1)>?(2)... образует цепь Маркова.
Найдем соответствующие переходные вероятности рij Очевидно, рij=0 при i?j, j?m, а pm+1, m+1=1. Подсчитаем вероятности pij при i<j?m. Обозначим ?i событие, состоящее в том, что при случайном порядке осмотра j предметов наилучшим среди них является последний j-й предмет. Очевидно, переходные вероятности рij согласно общей формуле () совпадают с условными вероятностями
, i<j?m.
Очевидно, вероятность события ?j совпадает с вероятностью того, что среди всех перестановок из j предметов будет выбрана та, при которой на последнем месте стоит наилучший предмет. Всего различных перестановок имеется j! а тех, при которых на последнем месте оказывается один и тот же фиксированный элемент, имеется (j-1)! Следовательно,
, j=1, …, m.
Вероятность события ?i?j совпадает с вероятностью того, что на последнем месте стоит наилучший предмет, а на i-м месте стоит также вполне определенный предмет - второй по качеству среди всех j предметов. Всего имеется (j - 2)! Таких перестановок и, следовательно,
, i<j?m.
Таким образом, переходные вероятности рij суть
, i<j?m.
Переходные вероятности pi, m фактически были подсчитаны
, i=1, …, m.
Случайные блуждания. Рассмотрим случайное блуждание, связанное с неограниченными испытаниями Бернулли, когда частица блуждает по целочисленным точкам действительной прямой таким образом, что, находясь в точке i она с вероятностью р переходит на следующем шаге в соседнюю точку i + 1, а с вероятностью q=1-р - в соседнюю точку i-1. Если обозначить ?(n) положение частицы после п шагов, то последовательность ?(0) >?(1)>?(2)... будет цепью Маркова с переходными вероятностями вида
Рассмотрим случайное блуждание другого типа. Частица блуждает лишь по целым неотрицательным точкам, причем из точки i она с вероятностью рi переходит на следующем шаге в соседнюю точку i+1, а с вероятностью qi=1 - pi возвращается в нулевое положение. Соответствующие переходные вероятности суть
2. Возвратные и невозвратные состояния
Рассмотрим цепь Маркова с состояниями ?1, ?2, … и переходными вероятностями рij, i, j=1, 2, … Пусть в начальный момент система находится в состоянии ?i. Временно положим un=pij(n) и обозначим ?n вероятность того, что через п шагов система впервые вернется в исходное состояние ?i. Имеет место следующее равенство:
ип = u0 ?n + u1?n-1 + … + un-1?1 + un?0, n=1, 2, …,
где дополнительно введены u0= 1 и ?0 = 0.
Оно является следствием общей формулы полной вероятности. Именно, если ввести события Вk-"система через k шагов впервые возвращается в исходное состояние ?i", k = 1, …, п, и событие Вп+1-"система ни разу не побывает в состоянии ?i в течение первых п шагов", то В1, ..., Bn+1 будет полной системой событий, и вероятность события А - "система через п шагов будет находиться в исходном состоянии ?i" - по формуле полной вероятности есть
,
где
(Bk)=?k; P(A|Bk)=un-k, k=1, …, n; P(A|Bn+1)=0.
Если обратиться к производящим функциям
, , |z|?1,
то отношение (8.8), справедливое при всех п= 1, 2,... , можно записать в виде
, u0=1,
,
Значение
есть вероятность того, что система рано или поздно попадет в исходное состояние ?i, иначе ? есть вероятность возвращения в ?i. Состояние ?i называется возвратным, если вероятность возвращения в него равна 1, и невозврат