4. Марковские системы обслуживания (стр. 1 )

4. МАРКОВСКИЕ СИСТЕМЫ ОБСЛУЖИВАНИЯ

4.1. Цепи Маркова

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

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

(4.1)

В дальнейшем элементы множества будем называть состояниями процесса .

Очевидно, свойство (4.1) означает, что при установленном состоянии процесса в момент времени его дальнейшее поведение не зависит от того, каким образом процесс оказался в этом состоянии (будущее при известном настоящем не зависит от прошлого).

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

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

.

Ясно, таким образом, что ЦМ – это марковский процесс, множество состояний которого конечно или счетно. Понятно также, что можно анализировать многомерные ЦМ. Далее для простоты изложения мы будем говорить об одномерных ЦМ, соответствующие обобщения являются очевидными с точки зрения теории.

В дальнейшем будем считать, что (например, все состояния процесса перенумерованы). Типичным примером такого процесса является процесс , где – число требований, находящихся в системе в момент времени t.

Цепь Маркова называется однородной, если условная вероятность , где , при известных состояниях не зависит от , а зависит только от t.

В частности, для однородной ЦМ имеет место соотношение , где . В дальнейшем мы будем анализировать только однородные ЦМ.

Несколько более общим является понятие однородного марковского процесса: марковский процесс называется однородным, если функция не зависит от t, а зависит только от , х и А.

ЦМ, для которой называется ЦМ с дискретным временем; ЦМ, для которой , называется ЦМ с непрерывным временем.

Введем обозначения , , где ; . Функции называются вероятностями перехода из состояния i в состояние j за время t. Функции представляют собой безусловные вероятности того, что в момент времени t процесс находится в состоянии j. В случае ЦМ с дискретным временем примем обозначения , . Величины называются вероятностями переходов из состояния i в состояние j за n шагов. Вероятность перехода из состояния i в состояние j за один шаг будем называть просто вероятностью перехода из состояния i в состояние j.

Набор вероятностей , где , называется начальным распределением ЦМ.

Определение 2. Цепь Маркова называется эргодичной, если при для всех ее состояний существуют пределы .

Если для всех имеем , то эргодичная ЦМ называется строго эргодичной. Набор чисел {} называется эргодическим распределением ЦМ, вероятности называются конечными (финальными) вероятностями ЦМ.

Определение 3. Вероятностное распределение , где , называется стационарным распределением цепи Маркова, если для любого состояния и любого выполняется равенство .

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

Эргодическое распределение ЦМ (если оно существует), очевидно, является стационарным, следовательно, его финальные вероятности также определяются системой уравнений, представленных в определении 3. Это означает, что если ЦМ с начальным распределением и переходными вероятностями , , эргодична и характеризуется финальными вероятностями , то существует стационарная ЦМ с такими же переходными вероятностями и начальным распределением .

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