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

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

Когда множество состояний процесса s={s1..s2} конечно, Марковская цепь называется конечной. Конечная Марковская цепь может быть определена в непрерывном или дискретном времени. В первом случае переходы процесса из одного состояния в другое связываются с произвольными моментами времени t0, t1, t2… и цепь называют непрерывной; во втором переходы идут только в фиксированные моменты времени, обозначаемые порядковыми номерами t = 0, 1, 2, .., и цепь называется дискретной.

Дискретная Марковская цепь определяется: 1) множеством состояний s={s1..s2}; 2) матрицей вероятностей переходов (или переходных вероятностей), характеризующей вероятности перехода процесса с текущим состоянием si в следующее состояние sj; 3) вектором начальных вероятностей P = {p1,…,pk}, определяющим вероятность рi того, что в начальный момент времени t = 0 процесс находится в состоянии si.

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

Поглощающая Марковская цепь содержит поглощающее состояние, достигнув которого процесс уже никогда его не покидает, по сути дела это моделирует прекращение процесса. Из какого бы состояния ни начался процесс, при n стрелочка: с вероятностью 1 он окажется поглощающем состоянии s0. Основная характеристика процесса, порождаемого поглощающей Марковской цепью, - число пребывания процесса в состояниях s1,…,sk до момента поглощения. Поглощающие Марковские цепи используются в качестве моделей программ. При моделировании программы состояния цепи отождествляются с блоками программы, а матрица переходных вероятностей определяет порядок переходов между блоками, зависящий от структуры программы и распределения исходных данных, значения которых влияют на развитие вычислительного процесса. В результате удается вычислить число обращений к блокам программы и время выполнения программы. Аналогично можно представить и работу с аппаратурной частью, когда состояния отображают использование отдельных устройств компьютера.

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

Марковский процесс, в котором переходы между состояниями разрешаются в любой момент времени, называется непрерывной Марковской цепью. Однородная непрерывная Марковская цепь, поведение которой в любой момент времени подчиняется одному и тому же закону, задается матрицей интенсивности переходов Q=[q(ij)]i,j=1..k .

Интенсивность переходов определяется следующим образом:

q(i,j)=lim((pi,j(дельта t)-1)/(дельта t))

где pi,j(дельта t) – вероятность перехода процесса из состояния si в состояние sj за время дельта t.

Вероятность перехода процесса в любое новое состояние равна – pi,j(дельта t) .

Основная характеристика непрерывной Марковской цепи – стационарное (финальное) распределение вероятностей состояний А = {a1,…,ak}, где ai – вероятность пребывания процесса в состоянии si.