Главная > Разное > Теоретические основы проектирования компьютерных сетей
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

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

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

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

Параметр t процесса будем рассматривать как время. Если - будущий момент времени, t - настоящий момент времени, - прошлые моменты времени, то условие (1) можно трактовать следующим образом: будущее поведение марковского процесса полностью определяется его состоянием в настоящий момент времени. У немарковского процесса будущее поведение зависит также от состояний процесса в прошлом.

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

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

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

Определение 11. Случайный процесс называется процессом гибели и размножения, если он удовлетворяет условиям:

• пространство состояний процесса есть множество неотрицательных целых чисел (или его некоторое подмножество);

• время пребывания процесса в состоянии имеет показательное распределение с параметром и не зависит от предыдущего поведения процесса;

• после завершения пребывания процесса в состоянии он переходит в состояние вероятностью и в состояние с вероятностью Вероятность полагается равной 1.

Состояние процесса в момент времени t можно трактовать как размер некоторой популяции в этот момент времени. Переход из состояния i в состояние трактуется как рождение нового члена популяции, а переход в состояние - как гибель члена популяции. Такая трактовка процесса и объясняет его название.

Обозначим вероятность того, что в момент t процесс находится в состоянии .

Утверждение 8. Вероятности удовлетворяют следующей системе линейных дифференциальных уравнений:

где

Для доказательства применим так называемый - метод». Этот метод широко используется при анализе цепей Маркова и марковских процессов с непрерывным временем.

Сущность этого метода состоит в следующем. Фиксируется некоторый момент времени t и некоторое малое приращение времени Распределение вероятностей состояний марковского процесса в момент времени выражается через его распределение вероятностей в момент t и вероятности возможных переходов процесса за время . В результате получается система разностных уравнений для вероятностей Деля обе части этих уравнений на и устремляя величину к нулю, получаем систему дифференциальных уравнений для искомых вероятностей.

Применяем этот метод для вывода уравнений (1.3). Обозначим через вероятность перехода процесса из состояния в состояние j за интервал времени Поскольку распределение времени пребывания процесса в состоянии i имеет показательное распределение, обладающее свойством отсутствия последействия, то время до окончания пребывания в состоянии , начиная с момента времени t, также распределено по показательному закону с параметром

Вероятность того, что процесс осуществит переход из состояния i за время есть вероятность того, что за время показательно распределенное с параметром время закончилось. По определению функции распределения эта вероятность равна

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

Используя приведенные рассуждения и формулу полной вероятности, мы получаем соотношения:

Из описания процесса и формулы (1.4) следует, что:

Подставляя соотношения (1.6) в (1.5) и используя введенные обозначения переписываем (1.5) в виде:

Деля обе части этого уравнения на и устремляя к нулю, получаем уравнение (1.3). Уравнение (1.2) выводится аналогично.

Утверждение 8 доказано.

Для решения бесконечной системы дифференциальных уравнений (1.2), (1.3) путем перехода к преобразованиям Лапласа (см. ниже) вероятностей ее сводят к бесконечной системе линейных алгебраических уравнений.

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

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

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

Утверждение 9. Стационарное распределение вероятностей (1.8) рассматриваемого процесса гибели и размножения существует, если сходится ряд

где

и расходится ряд

При этом стационарные вероятности вычисляются следующим образом:

Последняя часть утверждения доказывается элементарно. Предполагаем, что условия (1.9) и (1.10) выполняются и пределы (1.8) существуют. Устремляем в (1.2), (1.3) t к бесконечности. При этом производные стремятся к нулю.

Существование пределов этих производных следует из существования пределов в правой части системы (1-2), (1.3). Равенство пределов производных нулю следует из того, что предположение о том, что пределы ненулевые, противоречит ограниченности вероятностей:

В результате, из (1.2), (1.3) получаем систему линейных алгебраических уравнений для распределения

Введя обозначение , систему (1.12),(1.13) можно переписать в виде:

откуда следует, что что влечет выполнение соотношений

Отсюда следует, что . Формула для вероятности следует из условия нормировки.

<< Предыдущий параграф Следующий параграф >>
Оглавление