Марковские случайные процессы с дискретными состояниями и дискретным временем

Случайный процесс называется процессом с дискретным временем, если переходы системы из состояния в состояние возможны только в строго определенные, заранее фиксированные моменты времени t ₁, t ₂, …. В промежутке времени между этими моментами система сохраняет свое состояние.

Рассмотрим физическую систему S, которая может находиться в любом из множества состояний: S ₁, S ₂, …, S_n. Моменты перехода из состояния в состояние фиксированы: t ₁, t ₂, t ₃, …, t_k, ….

Будем называть эти моменты шагами и рассматривать случайный процесс, происходящий в системе S как функцию целочисленного аргумента: 1, 2, …, k, … (номер шага). Случайный процесс, происходящий в системе, состоит в том, что в последовательные моменты времени t ₁, t ₂, t ₃, … система S оказывается в тех или других состояниях, ведя себя, например, следующим образом:

.

В общем случае в моменты времени t ₁, t ₂, t ₃, … система может не только менять состояние, но и оставаться в прежнем, например:

.

Обозначим через событие, состоящее в том, что после k -го шага система находится в состоянии S_i. Очевидно, что при любом k события образуют полную группу (то есть система обязательно будет находиться в одном из состояний) и несовместны (система не может находиться в двух и более состояниях в один момент времени).

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

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

Марковская цепь описывается с помощью вероятностей состояний. Обозначим через вероятность того, что после k -го шага система окажется в состоянии:

.

Например, вероятности состояний после первого шага:

,

вероятности состояний после второго шага:

,

…

вероятности состояний после k -го шага:

Очевидно, что для каждого шага k сумма вероятностей состояний равна единице:

,

так как это вероятности несовместимых событий, образующих полную группу.

Для удобства расчетов запишем вероятности состояний системы после k -го шага в виде вектора вероятностей состояний v (k):

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

В качестве примера рассмотрим некоторую систему S со следующим графом состояний:

S1

S2

S3

S4

S5

S6

Рис. 5.

Случайный процесс (марковскую цепь) можно представить себе так, как будто точка, изображающая систему, случайным образом перемещается (блуждает) по графу состояний, перескакивая из состояния в состояние в моменты времени t ₁, t ₂, …, а иногда и задерживаясь на какое-то число шагов в одном и том же состоянии. Например, последовательность переходов

можно изобразить на графе состояний пунктирными дугами, взвешенными номерами шагов:

S1

S2

S3

S4

S5

S6

Рис. 6.

(Задержка системы в состоянии на третьем шаге обозначена петлей при вершине.)

Для любого шага (момента времени t ₁, t ₂, …, t_k, … или номера 1, 2, …, k, …) существует вероятности перехода системы из любого состояния в любое другое (некоторые из них равны нулю, если непосредственный переход за один шаг невозможен), а также вероятности задержки системы в данном состоянии. Эти вероятности называются переходными вероятностями марковской цепи и обозначаются p_ij (вероятность перехода из состояния в за один шаг).

Разница между и p_ij:

· – вероятность состояния (вероятность, что после k-го шага система окажется в состоянии);

· p_ij – вероятность перехода (вероятность перехода из состояния в за один шаг).

Переходную вероятность p_ij можно записать как условную вероятность наступления события при условии, что перед этим произошло событие:

.

Существует два вида марковских цепей:

· однородная – если переходные вероятности не зависят от номера шага (одинаковые для каждого шага);

· неоднородная – если переходные вероятности зависят от номер шага (различаются от шага к шагу).