Марковские случайные процессы. Марковские цепи

Рассмотрим частный случай случайных процессов – марковские случайные процессы. Такие процессы называют марковскими, потому что они впервые были систематически изучены известным российским математиком А.А. Марковым в начале XX века.

Определение 6.2.1. Случайный процесс X(t) называется марковским, если для любых n моментов времени t₁< t₂< ... < t_n условная функция распределения последнего значения X(t_n) при фиксированных значениях X(t₁), ... , X(t_n-1) в моменты времени t₁,…,t_n-1 зависит лишь от значения X(t_n-1) в непосредственно предшествующий ему момент времени t_n-1 и не зависит от его значений в более ранние моменты времени t₁, …, t_n-2.  Это свойство марковского процесса называют свойством отсутствия последействия.

Значения случайного процесса удобно отождествлять с состояниями системы, которую описывает данный случайный процесс. При этом переход системы из одного состояния в другое происходит в фиксированные или случайные моменты времени. Поэтому в терминах состояний особенность марковского случайного процесса состоит в том, что вероятность состояния системы в момент времени t_n зависит лишь от того, в каком состоянии находилась система в непосредственно предшествующий ему момент времени t_n-1, и не зависит от того, в каких состояниях находилась система в более ранние моменты времени t₁,...,t_n-₂.

Укажем еще одно общее и важное свойство марковских процессов: для них эволюция вероятности перехода из одного состояния в другое описывается дифференциальным уравнением вида

,                                       (6.2.1)

где А - некоторая квадратная матрица.

Это свойство позволяет исследовать поведение марковских процессов при помощи хорошо разработанных методов решения соответствующих дифференциальных уравнений.

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

В случае дискретного множества состояний марковский случайный процесс называется марковской цепью.

Цепь Маркова представляет собой последовательность испытаний, в каждом из которых система принимает одно и только одно из n состояний полной группы s₁,s₂, …, s_n (или, иначе, состояния 1,2,.. .,n ). При этом вероятность p_ij(k) того, что после k-го испытания система будет находиться в состоянии j, при условии, что после (k-l)-гo испытания она находилась в состоянии i, не зависит от результатов остальных, ранее произведенных испытаний.

Различают марковские цепи с дискретным временем, если изменение состояний происходит в определенный фиксированный момент времени, и марковские цепи с непрерывным временем, если изменение состояний происходит в любые случайные моменты времени.

Цепь Маркова называют однородной, если условная вероятность р_ij(k) не зависит от номера испытания; в этом случае вместо нее пишут р_ij и называют ее переходной вероятностью. Все переходные вероятности могут быть представлены матрицей перехода системы, имеющей следующий вид:

.                                    (6.2.2)

Так как в любой строке матрицы помещены вероятности перехода из одного состояния i в любое возможное состояние j, сумма переходных вероятностей каждой строки матрицы перехода равна 1, т.е.    (i = 1,2, …,n).

Пусть Р_ij(m) - вероятность того, что в результате m испытаний (шагов) система перейдет из состояния i в состояние j (если m=1, то P_ij(1) = p_ij). По формуле полной вероятности (с использованием вероятностей перехода в промежуточное состояние P_{i j} (m) имеем формулу:

                                         .                                      (6.2.3)

Формулу (6.2.3) называют формулой Маркова.

Если положить m=2, k=l, формула (6.2.3) превращается в следующую:

                                               .                                             (6.2.4)

Очевидно, что матрица вероятностей перехода за 2 шага может быть получена умножением матрицы (6.2.2) на себя:

                                                                                     (6.2.5)

Обобщением формулы (6.2.5) является следующая формула для матрицы вероятностей перехода за m шагов:

                                                                                     (6.2.6)

Введем p _i ( k ) как вероятность того, что на k-м шаге система будет находиться в состоянии s_i,. Тогда матрица - строка p(k) = ( p₁(k); …; p_n(k) ) является матрицей состояния системы на k-м шаге. Для однородной цепи Маркова имеет место следующая формула:

^,                                         (6.2.7)

где p (0) определяет начальное состояние системы.

В цепях Маркова с конечным числом состояний находят применение графы состояний, в которых показаны возможные состояния системы (изображаются кружками) и переходные вероятности (изображаются стрелками).

Задача.6.3.1 В моменты времени t₁, t₂, t₃ происходит осмотр  ЭВМ, возможные состояния которой: s₁ – полностью исправная ЭВМ; s₂ – незначительные неисправности, которые позволяют эксплуатировать ЭВМ; s₃ – существенные неисправности, но дающие возможность решать ограниченное число задач; s₄ – ЭВМ вышла из строя. Граф состояний имеет следующий вид:

 

Найти: а) матрицу переходных вероятностей; б) вероятности состояний ЭВМ после 1,2 осмотров, если вначале (при t=0) ЭВМ была исправна.

Решение. а) по графу состояний построим матрицу переходных вероятностей

 

                б) p(0) = (1;0;0;0); p(1) = p(0) ; p(1) =(0,5; 0,3; 0,2; 0);

 

                      p(2) = (0,25; 0,27; 0,28; 0,2).

6.3. Марковские процессы с дискретными состояниями и
непрерывным временем.
Уравнения Колмогорова

Пусть переход системы из одного состояния в другое может происходить в любой случайный момент времени. Марковский случайный процесс с дискретными состояниями и непрерывным временем часто называют непрерывной цепью Маркова. В этом случае не имеет смысла говорить о вероятностях перехода из одного состояния в другое, т.к. для любого момента времени t p_ij ( t )=0. Вместо неё вводят плотность вероятности перехода из i-го в j-е состояние по формуле

Плотность вероятности перехода может быть как постоянной (λ_ij=const), так и зависящей от времени (λ_ij = λ_ij(t)). В первом случае непрерывную цепь Маркова называют однородной, во втором - неоднородной. Простейшим примером однородной непрерывной цепи Маркова является случайный процесс X(t), представляющий собой число наступлений события А (успеха) до момента времени t в простейшем (пуассоновском) потоке событий.

При рассмотрении непрерывных цепей Маркова удобно представлять переходы системы из состояния в состояние как происходящие под влиянием потоков событий; при этом плотность вероятности перехода приобретает смысл интенсивностей λ_ij соответствующих потоков событий. Потоком вероятности перехода из состояния s_i в состояние s_j называется величина λ_ij p_i(t).

Для описания непрерывной цепи Маркова введем вероятности состояний

p₁(t), p₂(t), …,p_n(t),                              (6.3.2)

где p_i(t) вероятность того, что система в момент времени t находится в состоянии s_i. Очевидно, что в любой момент времени

.                                                         (6.3.3)

Для нахождения вероятностей состояния нужно решить систему дифференциальных уравнений (уравнений Колмогорова), имеющих вид:

                     , i = 1, 2, 3, …, n.                  (6.3.4)

В уравнениях (6.3.4) интенсивности потоков могут зависеть от времени t.

Уравнения Колмогорова (6.3.4) можно составить, пользуюсь размеченным графом состояний и следующим мнемоническим правилом: производная вероятности каждого состояния равна сумме всех потоков вероятности, входящих в данное из других состояний, минус сумма всех выходящих из данного состояния потоков.

Пример 6.3.1. Пусть граф состояний непрерывной цепи Маркова имеет вид

Рис. 6.3.1.

Составить уравнения Колмогорова.

Решение. Пользуясь вышеуказанным правилом, имеем

;

;

;

;

.

Часто возникает вопрос о предельном поведении вероятностей p_i(t) при t ® ∞. В некоторых случаях существуют предельные (финальные) вероятности. Это означает, что со временем устанавливается стационарный режим, в ходе которого система переходит из одного состояния в другое, но вероятности состояний уже не меняются. Финальные вероятности могут быть интерпретированы как среднее относительное время пребывания системы в данном состоянии. В этом случае непрерывная цепь Маркова называется эргодической.

По графу состояний можно определить, существует финальные состояния или нет. Для этого вводятся существенные и несущественные состояния. Впервые такая классификация состояний для цепей Маркова была введена российским математиком А.Н. Колмогоровым.

Состояние s_i называется несущественным, если существуют такое состояние s_j и такое n, что p_ij(n) > 0, но p_ji(m) = 0 для всех m. Иными словами, несущественное состояние обладает тем свойством, что из него можно с положительной вероятностью попасть в некоторое другое состояние, но из этого другого состояния вновь вернуться в первоначальное (несущественное) состояние уже нельзя.

Все состояния, отличные от несущественных, называются существенными. Пусть s_i  и s_j являются существенными и существуют такие натуральные m и n, что наряду с неравенством p_ij(m) > 0 выполняется неравенство p_ji(n) > 0; в этом случае они называются сообщающимися. Очевидно, что если s_i сообщается с s_j, а s_j сообщается s_k, то s_i сообщается с s_k. Таким образом, все существенные состояния разбиваются на классы ; все существенные состояния , принадлежащие одному классу, сообщаются, а принадлежащие разным классам – не сообщаются между собой. Если все состояния системы существенные, они образуют единственный класс.

Состояние s_i называют поглощающим, если p_ii = 1. Если для марковской цепи существует хотя бы одно поглощающее состояние и из любого не поглощающего состояния можно перейти в какое-нибудь поглощающее, цепь Маркова называют поглощающей.

Имеет место следующий результат:

Теорема 6.3.1. Для того, чтобы при конечном числе состояний для непрерывной цепи Маркова существовали предельные вероятности состояний, необходимо и достаточно, чтобы из каждого существенного состояния можно было перейти (за какое-нибудь определенное число шагов) в другое существенное состояние.

Из несущественных состояний система рано или поздно уйдет в одно из существенных состояний и больше в них не вернется. Финальные вероятности для них равны нулю.

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

Теорема 6.3.2. Для существования предельных вероятностей достаточно, чтобы из любого состояния системы можно было (за определенное число шагов) перейти в любое другое.

Финальные вероятности могут быть получены из уравнений Колмогорова, если положить в них производные по времени равными нулю. В этом случае уравнения (6.3.4) можно записать в следующем виде:

, i = 1,2, …, n.                        (6.3.5)

Систему линейных алгебраических уравнений (6.3.5), из которых определяются финальные вероятности, можно составить непосредственно, руководствуясь следующим правилом: для каждого состояния суммарный входящий поток равен суммарному выходящему. Чтобы получить единственное решение системы (6.3.5), к ним следует добавить нормированное условие (6.3.3).

⇐ Предыдущая567891011121314Следующая ⇒

Поделиться: