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

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

Пусть в объекте моделирования определены состояния , например, в системе массового обслуживания:

– в СМО нет заявок,

– в СМО одна заявка,

– в СМО две заявки и т.д.

C течением времени СМО переходит из одного состояния в другое.

Рассмотрим марковские процессы с дискретными состояниями (число состояний конечно или счетно). При этом выделим:

а) марковские процессы с дискретным временем перехода (моменты перехода заранее определены);

б) марковские процессы с непрерывным временем перехода (момент перехода не определен, случаен).

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

1.3.1. Марковские процессы с дискретными состояниями и дискретным временем перехода

Пусть система находится в состоянии , где .

Для задания марковского процесса необходимо определить матрицу вероятностей перехода из одного состояния в другое.

Пример матрицы переходов:

Для заданной матрицы граф переходов имеет вид:

Так как на каждом следующем шаге система переходит в другое состояние, то .

Пусть задан вектор вероятностей в первый момент времени:

.

Какова вероятность нахождения системы в состоянии i после первого перехода?

. (1.6)

В векторном виде (1.6): .

На шаге получим уравнение:

. (1.7)

Если (не зависит от шага), то процесс называется однородным.

При устремлении к бесконечности получим вектор предельных вероятностей:

.

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

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

Пример неприводимой матрицы переходов:

1.3.2. Марковские процессы с дискретными состояниями и непрерывным временем перехода

Пусть система может находиться в состояниях().

Время перехода – случайная величина.

– интенсивность перехода из состоянияв .

За время вероятность перехода .

Если (не зависит от времени), то это однородный марковский процесс.

Рассмотрим случай с двумя состояниями:

 

Составим конечно–разностное уравнение для определения .

Для первого состояния:

(1.8)

. (1.9)

Из (1.8)получим:

,

. (1.10)

Из (1.9) получим

. (1.11)

Следует иметь в виду, что в любой момент .

Примем за начальное состояние системы , тогда решением дифференциального уравнения (1.10) будет:

(1.12)

. (1.13)

Графически (1.12) и (1.13) представлены на рис. 1.6.

При стремлении к бесконечности получим предельные вероятности: .

Для определения и приравняем производные из системы уравнений (1.10) и (1.11) к нулю:

Получим:

Рассмотрим случай для четырех состояний (рис. 1.7). Для простоты изображения размеченного графа будем опускать.

Рис.1.7. Размеченный граф

 

Система уравнений для данного графа приведена ниже.

.

В общем случае, когда число состояний , система уравнений примет вид:

.

Эту систему уравнений по имени автора называют системой уравнений Колмогорова.

Для определения предельных вероятностей получим систему линейных уравнений:

(),

.

1.3.3. Процессы гибели и размножения

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

Рис.1.8. Размеченный граф процессов гибели и размножения

 

− интенсивности размножения, − интенсивности гибели.

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

(по Колмогорову), (1.14)

. (1.15)

Подставляя (1.14) в (1.15), получим:

Для всех последующих состояний уравнения будут иметь одинаковый вид:

().

Чтобы определить все предельные вероятности, воспользуемся условием: . Для этого выразим через :

. (1.16)

Введем обозначение , тогда (1.14) и (1.16) запишутся в виде: .

Все оставшиеся вероятности выражаются через :

.

В результате получим выражение для :

.

Определив , можем рассчитать все .

Пример анализа процесса гибели и размножения.

Пусть задан процесс гибели и размножения:

Расчет предельных вероятностей:

;

;

;