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

Понятие случайного процесса Понятия: Cостояние Переход Дискретный случайный процесс Непрерывный случайный процесс

Марковский случайный процесс Рассматриваются случайные процессы с дискретными состояниями S 1, S 2, …, S n Случайный процесс в некоторой системе называется марковским, если вероятность перехода системы в новое состояние зависит только от состояния системы в настоящий момент и не зависит от того, когда и каким образом система перешла в это состояние. По сути то, что процесс – марковский, означает, что описание системы достаточно полное, то есть нет факторов (на которые влияют предшествующие события), от которых зависит поведение системы, но которые не учтены в описании системы.

Марковский случайный процесс Параметры: Состояния S 1, S 2, …, S n Матрица переходов, содержащая вероятности переходов для процессов с дискретным временем q ij интенсивности переходов для процессов с непрерывным временем Начальные вероятности p 1 (0), … p n (0) Зависимость вероятностей от времени: Однородные процессы Неоднородные процессы

Процессы с дискретным и случайным временем Случайный процесс Z(t) называется случайным процессом с дискретным временем (стохастическими последовательностями или случайными цепями), если переходы из состояния в состояние возможны только в строго определенные заранее фиксированные моменты времени, которые можно пронумеровать: t 1, t 2. Если промежуток времени между переходами из состояния в состояние является случайным и переход возможен в любой заранее не известный момент времени t, то процесс называется случайным процессом с непрерывным временем.

Процессы с дискретным временем (марковские цепи) Система имеет n возможных состояний S 1, S 2, …, S n Для определения поведения системы необходимо задать вероятности перехода из одного состояния в другое (возможно, зависящие от времени): q ij – вероятность перехода из состояния S i в S j Целью является вероятности нахождения системы в различных состояниях (в определённый момент времени) Соотношение:

Процессы с непрерывным временем Система имеет n возможных состояний S 1, S 2, …, S n p ij – вероятность перехода из состояния S i в S j в каждый определённый момент равна 0, поэтому используют понятие интенсивности (плотности вероятности) перехода из одного состояния в другое Целью является вероятности нахождения системы в различных состояниях (в определённый момент времени) Соотношение:

Процессы однородные и неоднородные Процесс называется однородным, если вероятности (плотности вероятностей) от времени не зависят. Иначе процесс называется неоднородным. Если по истечении достаточно большого промежутка времени вероятности состояний стремятся к предельным значениям p 1, …, p n, не зависящим от начальных вероятностей p 1 (0), …, p n (0) и от текущего момента времени t, то говорят, что случайный процесс обладает эргодическим свойством. – стационарные вероятности

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

Схема гибели и размножения Один из распространённых частных случаев марковских процессов Стационарные вероятности:

Пример: надёжность системы из двух компьютеров t – среднее время работы без отказов, t р – среднее время восстановления 12 = 2 1/t, 23 = 1/t 21 = 1/t р, 32 = 2 1/t р Стационарные вероятности: P 1 = 1/ (1+2 t р /t + t р 2 / /t 2 ) P 2 = 2 t р /t P 1

Разработка марковской модели системы с дискретным временем Этапы: кодирование состояний случайного процесса; построение размеченного графа переходов; формирование матрицы интенсивностей переходов; составление системы линейных алгебраических уравнений.