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

Глава 2

Моделирование экономических систем с использованием марковских случайных процессов

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

Функция ДО называется случайной, если ее значение при лю­бом аргументе / является случайной величиной.

Случайная функция ДО, аргументом которой является время, называется случайным процессом.

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

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

Классификация марковских процессов.Классификация марков­ских случайных процессов производится в зависимости от непре­рывности или дискретности множества значений функции X(t) и параметра /.

Различают следующие основные виды марковских случайных процессов:

• с дискретными состояниями и дискретным временем (цепь Маркова);

• с непрерывными состояниями и дискретным временем (мар­ковские последовательности);

• с дискретными состояниями и непрерывным временем (не­прерывная цепь Маркова);

• с непрерывным состоянием и непрерывным временем.

В данной работе будут рассматриваться только марковские про­цессы с дискретными состояниями S_b S₂, ..., S_n.

Ц)аф состояний.Марковские процессы с дискретными состоя­ниями удобно иллюстрировать с помощью так называемого графа состояний (рис. 2.1), где кружками обозначены состояния Si, S₂, ... системы S, а стрелками — возможные переходы из состо­яния в состояние. На графе отмечаются только непосредственные переходы, а не переходы через другие состояния. Возможные за­держки в прежнем состоянии изображают «петлей», т. е. стрелкой, направленной из данного состояния в него же. Число состояний системы может быть как конечным, так и бесконечным (но счет­ным). Пример графа состояний системы Ј представлен на рис.2.1.

Рис. 2.1. Граф состояний системы S

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

Марковский случайный процесс с дискретными состояниями и дискретным временем называют марковской цепью. Для такого про­цесса моменты t_x, t₂, ..., когда система 5 может менять свое состо­яние, рассматривают как последовательные шаги процесса, а в ка­честве аргумента, от которого зависит процесс, выступает не время /, а номер шага 1, 2, ..., к, ... Случайный процесс в этом случае ха­рактеризуется последовательностью состояний 5(0), 5(1), 5(2), ..., S(k), ..., где 5(0) — начальное состояние системы (перед первым шагом); 5(1) - состояние системы после первого шага; S(k) - со­стояние системы после Л-го шага...

Событие {S(k) = Si}, состоящее в том, что сразу после к-го ша­га система находится в состоянии 5/(/ = 1, 2, ...), является случай­ным событием. Последовательность состояний 5(0), 5(1), ..., 5(&), ... можно рассматривать как последовательность случайных собы­тий. Такая случайная последовательность событий называется мар­ковской цепью, если для каждого шага вероятность перехода из лю­бого состояния 5/ в любое Sj не зависит от того, когда и как систе­ма пришла в состояние 5/. Начальное-состояние 5(0) может быть заданным заранее или случайным.

Вероятностями состояний цепи Маркова называются вероятнос­ти P_t(k) того, что после k-то шага (и до (к + 1)-го) система 5 будет находиться в состоянии 5,(/ =1,2, ..., п). Очевидно, для любого к

(2.1)

Начальным распределением вероятностей марковской цепи назы­вается распределение вероятностей состояний в начале процесса:

(2.2)

В частном случае, если начальное состояние системы S в точ­ности известно S(0) = S_h то начальная вероятность РДО) = 1, а все остальные равны нулю.

Вероятностью перехода (переходной вероятностью) на к-м шаге из состояния Si в состояние Sj называется условная вероятность то­го, что система S после к-го шага окажется в состоянии Л при ус­ловии, что непосредственно перед этим (после к — 1 шага) она на­ходилась в состоянии 5/.

Поскольку система может пребывать в одном из п состояний, то для каждого момента времени / необходимо задать п вероятно­стей перехода Ру, которые удобно представить в виде следующей матрицы:

(2.3)

где - вероятность перехода за один шаг из состояния Sj в состояние S/, — вероятность задержки системы в состоянии Sj.

Матрица (2.3) называется переходной или матрицей переходных вероятностей.

Если переходные вероятности не зависят от номера шага (от времени), а зависят только от того, из какого состояния в какое осуществляется переход, то соответствующая цепь Маркова назы­вается однородной.

Переходные вероятности однородной марковской цепи Ру об­разуют квадратную матрицу размера п х п. Отметим некоторые ее особенности:

1. Каждая строка характеризует выбранное состояние системы, а ее элементы представляют собой вероятности всех возможных переходов за один шаг из выбранного (из /-го) состояния, в том числе и переход в самое себя.

2. Элементы столбцов показывают вероятности всех возмож­ных переходов системы за один шаг в заданное (j-e) состояние (иначе говоря, строка характеризует вероятность перехода системы из состояния, столбец — в состояние).

3. Сумма вероятностей каждой строки равна единице, так как переходы образуют полную группу несовместных событий:

(2.4)

4. По главной диагонали матрицы переходных вероятностей стоят вероятности того, что система не выйдет из состояния а останется в нем.

Если для однородной марковской цепи заданы начальное рас­пределение вероятностей (2.2) и матрица переходных вероятностей

(2.3), то вероятности состояний системы определяются по рекуррентной формуле:

(2.5)

Пример 2.1.Рассмотрим процесс функционирования систе­мы автомобиля. Пусть автомобиль (система) в течение одной сме­ны (суток) может находиться в одном из двух состояний: исправ­ном и неисправном . Граф состояний системы представлен на рис. 2.2.

Рис. 2.2. Граф состояний автомобиля

В результате проведения массовых наблюдений за работой ав­томобиля составлена следующая матрица вероятностей перехода:

(2.6)

где

вероятность того, что автомобиль останется в исправном состоянии;

вероятность перехода автомобиля из состояния «испра­вен» в состояние «неисправен»;

вероятность перехода автомобиля из состояния «неиспра­вен» в состояние «исправен»;

вероятность того, что автомобиль останется в состоянии «неисправен».

Вектор начальных вероятностей состояний автомобиля задан

Требуется определить вероятности состояний автомобиля через трое суток.

Используя матрицу переходных вероятностей, определим веро­ятности состояний РХк) после первого шага (после первых суток):

Вероятности состояний после второго шага (после вторых су­ток) таковы:

Вероятности состояний после третьего шага (после третьих су­ток) равны

Таким образом, после третьих суток автомобиль будет нахо­диться в исправном состоянии с вероятностью 0,819 и в состоянии «неисправен» с вероятностью 0,181.

Пример 2.2.В процессе эксплуатации ЭВМ может рассматри­ваться как физическая система S, которая в результате проверки может оказаться в одном из следующих состояний:

ЭВМ полностью исправна;

ЭВМ имеет неисправности в оперативной памяти, при ко-

торых она может решать задачи;

—ЭВМ имеет существенные неисправности и может решать
ограниченный класс задач;

—ЭВМ полностью вышла из строя.

В начальный момент времени ЭВМ полностью исправна (со­стояние S_x). Проверка ЭВМ производится в фиксированные мо­менты времени t_b t₂, ty Процесс, протекающий в системе S, может рассматриваться как однородная марковская цепь с тремя шагами (первая, вторая, третья проверки ЭВМ). Матрица переходных веро­ятностей имеет вид:

Определите вероятности состояний ЭВМ после трех проверок.

Решение

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

Рис. 2.3. Граф состояний ЭВМ

По формуле (2.5), учитывая в сумме вероятностей только те со­стояния, из которых возможен непосредственный переход в данное состояние, находим:

Итак, вероятности состояний ЭВМ после трех проверок следу­ющие: