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

Общие сведения о вероятностных автоматах

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

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

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

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

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

Марковским называется случайный процесс, состояние которого в очередной момент времени t + ∆t зависит только от текущего состояния в момент времени t. Это означает, что поведение марковского процесса в будущем определяется текущим состоянием процесса и не зависит от предыстории процесса – состояний, в которых пребывал процесс до момента t.

В классе марковских процессов выделяют процессы с дискретными состояниями, называемые марковскими цепями.

Когда множество состояний процесса конечно, марковскую цепь называют конечной.

Конечная марковская цепь может быть определена в дискретном или непрерывном времени.

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

Основное отличие определяется целью исследования. Если важна только последовательность смены состояний, то процесс можно представить в виде дискретной марковской цепи, а если важно знать поведение в текущем времени, то в виде цепи с непрерывным временем.

Исходными данными для определения дискретной марковской цепи являются:

· множество состояний _;

· матрица вероятностей переходов (переходных вероятностей), характеризующей вероятности перехода процесса с текущим состоянием s_i в следующее состояние s_j:

· вектор начальных вероятностей (начальное распределение) , определяющим вероятности того, что в начальный момент времени t = 0 процесс находится в состоянии s_i.

Марковская цепь изображается в виде графа, вершины которого соответствуют состояниям цепи и дуги – переходам между состояниями.

Дуги (i, j), связывающие вершины s_t и s_}, отличаются вероятностями переходов . Например, на рис. 1.7.1 представлен граф марковской цепи с множеством состояний , матрицей вероятностей переходов:

и вектором начальных вероятностей .

Рис. 1.7.1 Граф марковской цепи

Марковская цепь порождает множество реализаций случайного процесса f(t), который представляется последовательностью состояний , принадлежащих множеству состояний и соответствующих моментам времени t = 0, 1, 2, ...

Начальное состояние определяется вектором начальных вероятностей . Следующее состояние определяется i-^й строкой матрицы вероятностей переходов Р: процесс f(t) переходит в состояние с вероятностью . Затем процесс переходит в состояние , определяемое вероятностями , соответствующими состоянию S_j, и т. д. В результате n шагов процесс попадает в состояния с вероятностями соответственно.

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

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

Матрица вероятностей переходов поглощающей цепи имеет следующий вид:

Из какого бы состояния ни начался процесс, при n→∞ с вероятностью 1 он окажется в поглощающем состоянии s₀.

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

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

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

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

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

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

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

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