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

Условно будем говорить о некоторой физической системе, шаг за шагом меняющей свое фазовое состояние. Будем считать, что имеется лишь конечное или счетное число различных фазовых состояний е₁, е₂, ... Обозначим о (п) состояние системы через п шагов. Будем предполагать, что цепочка последовательных переходов

о(0) > о (1) …

зависит от вмешательства случая, причем соблюдается следующая закономерность: если на каком-либо шаге п система находится в состоянии е_i, то, независимо от предшествующих обстоятельств, она на следующем шаге с вероятностью p_ij переходит в состояние е_j

p_ij = Р{ о (n+1) = е_i/ о (п) = е_j }, i, j =1, 2, ... (2.1)

Описанная выше модель называется однородной цепью Маркова, а вероятности р_ij называются переходными вероятностями этой цепи. Кроме них, еше задается начальное распределение вероятностей

p^o_i = P{о (0) = е_i}, i=1, 2, ... (2.2)

Какова вероятность того, что система через п шагов будет находиться в состоянии е_j?

Обозначим эту вероятность p_j (n)^:

p_j (n) = Р {о(n) = е_j}. (2.3)

Через п -- 1 шагов система обязательно будет находиться в одном из состояний е_k, k = 1, 2, ..., причем в е_k она будет с вероятностью, обозначенной р_к(п -- 1). При условии, что через п--1 шагов система будет находиться в состоянии е_k, вероятность оказаться через п шагов в состоянии е_j равна вероятности р_kj перехода из е_k в е_j. Используя формулу полной вероятности, получаем, что

Это дает следующие рекуррентные соотношения для вероятностей р_j(п), j=1, 2, ...:

(n=1, 2, …).

Если в начальный момент система находится в определенном состоянии е_i, то начальное распределение вероятностей таково, что р⁰_i= 1, p⁰_k= 0 для k ? i а вероятность p_i(n) совпадает с вероятностью p_ij(n) того, что система из состояния е_i за п шагов перейдет в состояние е_j.

p_ij(n) = Р{о(п) = е_j/о(0) =е_i}, i, j = 1, 2, ... (2.6)

При начальном распределении вида р⁰_i =1, р⁰_k = 0 для k ? i формула (2.5) дает следующие соотношения между переходными вероятностями p_ij(n); i,j =1, 2,... :

(n=1, 2, …)

Удобно ввести матрицу Р(п) = { p_ij(n)}. Согласно формуле (2.7)

Р(0)= I, Р(1) = Р, Р(2) =Р(1) Р = P², ...,

где I -- единичная матрица, Р = {p_ij} ? матрица переходных вероятностей. Видно, что имеет место следующее равенство:

P(n) = Pⁿ (n = 1, 2, …) (2.8)

Рассмотрим несколько примеров

Задача о стопке книг. На письменном столе лежит стопка из m книг. Если обозначить каждую книгу соответствующим номером, то порядок их расположения сверху вниз можно описать перестановкой из т чисел (i₁, i₂, … … i_m), где i₁ -- номер книги, лежащей сверху, i₂ -- номер следующей книги, ..., i_т--номер последней книги, лежащей в самом низу. Предположим, что каждая книга, берется с определенной вероятностью, скажем, книга с номером k берется с вероятностью р_k (к=1, ..., m), причем при возвращении она кладется сверху.

Возьмем произвольное состояние (i₁, i₂, …, i_m). На следующем шаге оно либо остается неизменным, что происходит с вероятностью при выборе лежащей сверху книги с номером i₁ либо меняется на одно из m -- 1 состояний вида (i_k, i₁, ...), что происходит с вероятностью при выборе книги с номером i_k. Перед нами цепь Маркова с состояниями, каждое из которых описывается соответствующей перестановкой (i₁, i₂, … … i_m), и указанными переходными вероятностями.

Остановимся на случае т = 2. Тогда имеется лишь два состояния: е₁=(1,2) и е₂ = (2, 1). Переходные вероятности имеют вид:

p₁₁=p₂₁=p_1, p₁₂=p₂₂=p₂

и матрица переходных вероятностей есть

Вероятности перехода за два шага суть

p₁₁(2)=p₂₁(2)=p₁p₁+p₂p₁=p₁(p₁+p₂)=p_1,

p₁₂(2)=p₂₂(2)= p₁p₂+p₂p₂=p₂(p₁+p₂)=p₂.

Видно, что Р² = Р и вообще Рⁿ = Р. При любом начальном распределении вероятностей имеем (n =1, 2, ...)

p₁(n)= p₁₁(n)+p₂₁(n)=p₁(+)=p_1,

p₂(n)= p₁₂(n)+p₂(n)=p₂(+)=p₂.

Задача о наилучшем выборе. Положим о₀(0)=1 и обозначим: о(1) -- порядковый номер первого предмета, оказавшегося наилучшим среди всех осмотренных ранее; о(2)--порядковый номер следующего наилучшего среди всех осмотренных до него предметов и т. д. Цепочка о(0)>о(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, а p_{m+1, m+1}=1. Подсчитаем вероятности p_ij при 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.

Переходные вероятности p_{i, m} фактически были подсчитаны

, i=1, …, m.

Случайные блуждания. Рассмотрим случайное блуждание, связанное с неограниченными испытаниями Бернулли, когда частица блуждает по целочисленным точкам действительной прямой таким образом, что, находясь в точке i она с вероятностью р переходит на следующем шаге в соседнюю точку i + 1, а с вероятностью q=1--р -- в соседнюю точку i-1. Если обозначить о(n) положение частицы после п шагов, то последовательность о(0) >о(1)>о(2)... будет цепью Маркова с переходными вероятностями вида

Рассмотрим случайное блуждание другого типа. Частица блуждает лишь по целым неотрицательным точкам, причем из точки i она с вероятностью р_i переходит на следующем шаге в соседнюю точку i+1, а с вероятностью q_i=1 - p_i возвращается в нулевое положение. Соответствующие переходные вероятности суть