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

1.3.3 Цепи Маркова с дискретным временем

Приведем необходимые нам краткие сведения из теории таких цепей. Более подробная информация о цепях Маркова с дискретным временем может быть почерпнута, например, в [117].

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

Определение 12. Однородная цепь Маркова с дискретным временем считается заданной, если:

• задано начальное распределение вероятностей состояний цепи:

• задана матрица Р вероятностей одношаговых переходов цепи, состоящая из элементов определенных следующим образом:

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

Матрица вероятностей переходов цепи за шагов является степенью матрицы Р.

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

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

Существует целый ряд результатов (теоремы Феллера, Фостера, Мустафы, Твиди и т.д.), позволяющих по конкретному виду переходных вероятностей определить, существуют стационарные вероятности (пределы (1.15)) или нет. Если в результате исследования переходных вероятностей установлено, что при некоторых условиях на параметры цепи пределы (1.15) существуют, считают эти условия выполненными и решают систему уравнений равновесия (1.16), (1.17), после чего цепь Маркова считается исследованной.

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

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