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

Марковский случайный процесс с дискретными состояниями и дискретным временем функционирования описывает систему S с конечным числом состояний. При этом переходы возможны в фиксированные моменты времени t₁, t₂,... t_k. Процесс, происходящий в этой системе, можно представить в виде цепочки случайных событий

S ₁ (0) ® S ₂ (1) ®... ® S_i (n) ®... ® S_n(k).

Эта последовательность называется дискретной Марковской цепью, если для каждого шага n =1,2,... k вероятность переходов из любого состояния (S_i ® S_j) не зависит от того, как система пришла в состояние S_i. Каждому переходу системы соответствует условная вероятность

                                                            P [ S_j (n)/ S_i (n -1)].                             (9)

Для каждого номера шага n возможные переходы образуют полную группу событий.

Дискретная Марковская цепь называется однородной, если переходные вероятности не зависят от номера шага. Полным описанием такой цепи может служить квадратная матрица переходных вероятностей

и вектор начального распределения вероятностей для всех состояний в момент времени t=0

                                                [ P_i (0)]=[ P ₁ (0) P ₂ (0)... P_n (0)].                         (10)

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

Дискретная Марковская цепь называется неоднородной, если переходные вероятности меняются с изменением номера шага. Для описания таких цепей необходимо задать k матриц переходных вероятностей P_ij (k – число рассматриваемых шагов). Главной задачей анализа Марковских процессов является определение вероятность всех состояний системы после любого количества шагов. При этом, если известна матрица переходных вероятностей и вектор начального распределения, то вероятности состояний системы после каждого шага определяются по формуле полной вероятности:

                                                      P (A) = P (B_i)* P (A / B_i)                              (11)

После первого шага вероятность P_i может быть определена следующим образом

                                                    P_i (1) = P_j (0) P_ji,                                     (12)

где   P_j (0) – вектор начальных состояний,

P_ji – строка матрицы условных вероятностей.

                                              P_i(2) = P_j(1)P_ji = P_j(0)P_ji(1)                  (13)

После k шагов:

                                         P_i(k) = P_j(k-1)P_ji = P_j(0)P_ji(k),                       (14)

где P_ji(k) - вероятности переходов системы из состояния S_i в S_j за k шагов.

Если возможен переход из состояния S_i в состояние S_j за k шагов, то величина P_ji(k)>0. Если при этом возможен обратный переход за то же число шагов, то состояние S_i называется возвратным. Вероятность того, что система выйдет из состояния S_i и за k шагов вернется в него же, равна 1 для возвратных состояний.

Состояние S_i - невозвратное, если эта вероятность отлична от 1.

Состояния S_i и S_j называются сообщающимися, если возможен переход S_i ® S_i за конечное число шагов.