2.5. Марковские цепи

Функционирование многих объектов представляет собой последова­тель­ность переходов их из одного состояния в другое (ЭВМ, каналы передачи информации…).

Система называется системой с дискретными состояниями, если мно­жество ее состояний конечно, а переходы из одного состояния в другое осуществляются скачком.

Последовательность состояний такой системы называется цепью.

Простейшей характеристикой случайного процесса, являющегося цепью, служит набор вероятностей состояний p₁(t), p₂(t),…, p_n(t), где p_i(t) – вероятность того, что в момент t система находится в состоянии i. p₁(t)+p₂(t)+…+ p_n(t)=1

Случайный процесс, протекающий в системе, называется марковским, если для любого момента времени t₀ вероятность любого состояния сис­темы в будущем (при t > t₀) зависит только от ее состояния в настоящем (при t = t₀) и не зависит от того, каким образом система пришла в это состояние.

М

арков (старший) Андрей Андреевич (1856-1922) – русский математик, доктор физико-математических наук, профессор, академик Петербургской академии наук. Работал профессором Петербургского университета, опубликовал около 70 работ по теории чисел, теории приближенных функций, дифференциальных уравнений, теории вероятностей. В цикле работ, опубликованных в 1906-1912 годах, заложил основы одной из общих схем естественных процессов, которая была названа цепями Маркова. А.А. Марков пользовался большим авторитетом у студентов. Был материалистом и убежденным атеистом.

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

Поток событий является ординарным, если события происходят поодиночке (нет двух одновременных событий). Поток называется стационарным, если его вероятностные характеристики не изменяются во времени. Чаще всего применяются пуассоновские потоки событий, то есть имеющие неизменную интенсивность (плотность) – среднее число событий в единицу времени постоянна.  = const.

Дискретные марковские цепи

Рассмотрим случайный марковский процесс с дискретными состояниями и дискретным временем. Такой процесс описывает систему S с конечным числом состояний, причем переходы возможны только в фиксированные моменты времени t₁, t₂,…, t_K. Процесс функционирования представим в виде цепи S₀ (0)  S_i (1)  S_j (2)  …  S_m (K).

Случайная последовательность является дискретной марковской цепью, если для каждого шага вероятность перехода из любого состояния S_i в любое состояние S_j (i, j = 1, 2, … N) не зависит от того, как система пришла в состояние S_i (принцип отсутствия последействия)

Каждому переходу системы из состояния S_i в состояние S_j в момент времени t_k соответствует переходная вероятность p_ij (t_k). Это условная вероятность p_ij (t_k) = P(S_j(t_k) | S_i(t_k-1)). Очевидно, для каждого номера шага k возможные переходы образуют полную группу событий, т.е. . Следует обратить внимание, что .

Дискретная марковская цепь называется однородной, если переходные вероятности не зависят от номера шага: p_ij (t_k) = p_ij.

Полным описанием однородной марковской цепи могут служить квадратная матрица переходных вероятностей P_П:

P_П=

и вектор вероятностей всех начальных состояний P(0)

P(0) = [p_i(0)] = [p₁(0), p₂(0)… p_N(0)]

Переходные вероятности, соответствующие невозможным переходам, равны нулю, вероятности, расположенные на главной диагонали, соответствуют тому факту, что система не изменила своего состояния.

Для однородной марковской цепи найдем вектор вероятностей всех состояний для любого k-го шага. В соответствии с формулой полной вероятности вероятность i-го состояния на первом шаге равна:

, , или в матричной форме: P(1) = P(0)∙P_П.

Аналогично, для второго шага: P(2) = P(1)∙P_П= P(0)∙P_П∙P_П

Соответственно, для k-го шага:

Обозначим элемент матрицы таким образом: p_ij(k).

Если возможен переход из состояния S_i в состояние S_j за k шагов, то p_ij(k)>0. Если при этом возможен и обратный переход за произвольное число шагов, то состояния S_i и S_j называются сообщающимися. Состояние S_i называется возвратным, если вероятность того, что система, выйдя из этого состояния, вернется в него за конечное число шагов хотя бы один раз, равна единице, и невозвратным, если вероятность возврата за конечное число шагов меньше единицы.