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

В общем случае, случайный процесс описывается n-мерным законом распределения.

- функция распределения;

- плотность распределения;

Умножая на dx, получим вероятности состояний процесса:

, где означает равенство с точностью до dx;

- вероятность движения процесса по заданной траектории.

Таким образом n-мерные законы распределения задают вероятностную меру на множестве реализаций случайного процесса. В статистическом смысле эти распределения являются исчерпывающей характеристикой процесса. Однако, их нахождение и последующие операции с ними могут оказаться чрезмерно сложными. Поэтому можно описывать процесс более упрощенно – на уровне числовых характеристик, т.е. используя так называемую «корреляционную теорию», позволяющую вычислять его м.о., дисперсию и корреляционную функцию между сечениями (m_x, D_x, K_xy). Вероятности состояний процесса в рамках корреляционной теории не вычисляются.

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

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

Выразим n-мерную плотность случайного процесса через одномерные условные распределения:

(3.1)

За счет отсутствия последействия n-мерная плотность марковского процесса равна: (3.2)

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

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

Марковские процессы принято делить на 3 вида:

1. Марковская цепь – процесс, состояния которого дискретны (т.е. их можно перенумеровать), и время, по которому он рассматривается, также дискретно (т.е. он может менять свои состояния только в определенные моменты времени). такой

процесс идет по шагам (иначе: по тактам).

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

3. Непрерывный марковский процесс – множество состояний и время непрерывны.

Рассмотрим эти группы более подробно:

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

Пусть Х = { 0, 1, 2, …i,…n – 1, n } - множество состояний цепи.

Смена состояний (последовательность переходов) определяет траекторию процесса.

Например: 0 2®4®5®1®2®7®6®9®7®8….. и т.д.

Вероятность такой траектории равна :

Для ее вычисления необходимо знать:

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

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

1. Квадратная

2. Ее элементы неотрицательны:

3. Сумма элементов строки равна единице: ,

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

Вероятность, что система за n шагов перейдет в заданное состояние (из i в j):

, где 1< m < N

- матрица переходов за n шагов. Значит .

Пусть m=1, тогда:

...

.

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

Вероятность того, что система окажется в состоянии j после n шагов, в соответствии с формулой полной вероятности, равна:

(3.3)

Предельные свойства марковской цепи:

Если финальное распределение не зависит от начального состояния, то процесс не только стационарный, но и эргодический.

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

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

Р =0,3 , Р =0,5 , Р =0,2

- На каждом такте точка может перемещаться на один шаг влево, вправо или остаться на месте с вероятностями указанными на рисунке. Крайние состояния 1 и 5 принято называть экранами. Они могут быть отражающими (от них точка отскакивает) или поглощающими (в них точка остается навсегда). Составим матрицы перехода за один шаг для каждого из экранов.

1) Отражающий экран:

2) Поглощающий экран:

По диагонали стоят вероятности того, что точка окажется в том состоянии, в котором она находится.

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

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

Классификация состояний цепи:

Состояние i достижимо из состояния j, если P_ij>0. В противном случае, (P_ij=0): i из j недостижимо. Эта связь не взаимна.

При P_ij¹0 и P_ji¹0 состояния сообщающиеся.

Замкнутое множество состояний. Если система находится в состоянии i, принадлежащем некоторому множеству С, а состояние j вне этого множества, и из i в j перейти нельзя, то С - замкнутое множество состояний.

C: P_ij=0, " iÎC, jÏC.

Войдя в состояние С, система оттуда не выйдет. Если замкнутое множество состоит только из одного состояния, его называют поглощающим.

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

Состояния делятся на возвратные и безвозвратные.

b_i(n) – вероятность первого возвращения в состояние i за n шагов. В отличие от b_i(n), введенная ранее P_ii(n) – это вероятность того, что за n шагов из i в i придем, но можно уходить и возвращаться несколько раз.

Если b_i(n)=1, то состояние называется возвратным. Выйдя из него, рано или поздно система в него вернется.

Если b_i(n)<1, то состояние называется безвозвратным.

(1- b_i(n)) – вероятность, что система выйдя из состояния, вновь в него не попадет.

Если для возврата в состояние i системе требуется конечное число шагов, то такое состояние называется ненулевым. В противном случае - нулевым состоянием.

Если цепь неприводима и все ее состояния ненулевые и непериодические, то в системе существует стационарное эргодическое распределение (т.е. финальное распределение будет стационарным и эргодическим).

Если для возврата в состояние требуется число шагов, кратное к¹1, то такое состояние называется периодическим, а к – его периодом.

Эта классификация состояний общая для марковских цепей и марковских процессов.