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

Оглавление

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

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

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

Итак, марковский процесс  удобно задавать графом переходов из состояния в состояние. Мы рассмотрим два варианта описания марковских процессов  — с дискретным и непрерывным временем.

В первом случае переход  из одного состояния в другое происходит в заранее известные моменты времени — такты (1, 2, 3, 4, …). Переход осуществляется на каждом такте, то есть исследователя интересует только последовательность состояний, которую проходит случайный процесс в своем развитии, и не интересует, когда конкретно происходил каждый из переходов.

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

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

 

 

 

 

 

Понятие случайного процесса

 

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

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

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

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

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

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

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

Обозначим через g(t) случайный процесс с дискретными состояниями, а возможные значения g(t), т.е. возможные состояния цепи, - через символы E₀, E₁, E₂, … . Иногда для обозначения дискретных состояний используют числа 0, 1, 2,... из натурального ряда.

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

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

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

 

а)   б)     в)

 

  E_i  E_j  E_i  E_k  E_k  E_i

   

          

E_m  E_m               

Рис.1. Фрагменты графа переходов.

2. Понятие  марковского случайного процесса

 

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

Pr{g(t_n+1)=E_n+1|g(t₀)=E₀, g(t₁)=E₁, …, g(t_n)=E_n}=

=Pr{g(t_n+1)=E_n+1|g(t_n)=E_n},

где t₁<t₂< … <t_n<t_n+1, а E_n - текущее состояние. Иными словами, в марковских случайных процессах влияние (воздействие) всей предыстории процесса на его будущее полностью сосредоточено в текущем состоянии процесса. Это свойство называется свойством отсутствия последействия или применительно к случайным процессам марковским свойством.

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

Рассмотрим марковский случайный  процесс g(t) с конечным числом состояний E₀, E₁, …, E_n. Обозначим через P_i(t) вероятность того, что случайный процесс в момент времени t находится в состоянии E_i:

P_i = Pr{g{t} = E_i}, i = 0,n.

Очевидно, что в любой  момент времени t процесс находится в одном из n+1 возможных состояний, т.е. события g{t}=E_i, i = 0,n заключающиеся в том, что в момент времени t процесс находится в состояниях E₀, E₁ ,…, E_n, образуют полную группу несовместных событий. Отсюда следует, что в любой момент времени t выполняется условие:

1,

которое называется нормировочным.

Совокупность вероятностей P_i(t), i=0,n, может быть представлена вектором, называемым вектором состояний, с числом компонент, равным числу возможных состояний процесса:

P(t)={P₀(t), P₁(t),  …,  P_n(t)}.

Главная задача изучения марковских случайных процессов заключается в определении вероятностей P_i(t), i = 0,n, нахождения процесса в любой момент времени t в том или ином состоянии, что дает полную информацию о случайном процессе. Для решения данной задачи необходимо:

1. указать в каком состоянии находится процесс в начальный момент времени;
2. описать переходы между состояниями.

Состояние процесса в  начальный момент времени t=0 задается вектором начальных вероятностей

P(0)={P₀(0), P₁(0),  …,  P_n(0)}.

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

Очень часто при изучении марковских случайных процессов  достаточно определить не вероятности P₀(t), P₁(t), …, P_n(t) в любой момент времени t, а их предельные значения (если они существуют) при .

Если при  вероятности P_i(t), i=0,n, стремятся к предельным значениям P_i , i=0,n, не зависящим от распределения начальных вероятностей P_i(0), i=0,n, то говорят, что случайный процесс обладает эргодическим свойством. Таким образом, для процессов, обладающих эргодическим свойством, существуют пределы

, i=0,n.

Предельные вероятности P_i, i=0,n, часто называют вероятностями состояний равновесия или стационарными вероятностями.

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

 

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

p_ij(t_k)=Pr{g(t_k+1)=E_j|g(t_k)=E_i}, i,j=0,n.

Вероятность перехода (за один шаг) p_ij(t_k) задет вероятность того, что случайный процесс на следующем (k+1)-ом шаге перехода (в момент времени t_k+1) окажется в состоянии E_j при условии, что на текущем k-ом шаге (в момент времени t_k) он находится в состоянии E_i.

Если вероятности переходов p_ij(t_k) не зависят от момента времени t_k, т.е. p_ij(t_k)=p_ij, то цепь Маркова называется однородной, в противном случае - неоднородной. Далее будем рассматривать только однородные цепи Маркова.

Вероятности переходов p_ij, i,j=0,n, обычно задаются в виде квадратной матрицы T размерности (n+1)´(n+1):

    

элементы которой удовлетворяются  условиям:

, i=0,n;

, i,j=0,n.

Условие (5) означает, что  в любой момент времени t₀, t₁, t₂, … процесс обязательно (с вероятностью 1) перейдет из состояния E_i в какое-либо другое состояние E₀, E₁,×××, E_n, причем не исключается возможность перехода в то же самое состояние.

Матрица, удовлетворяющая условиям (5) и (6), называется стохастической. Поскольку элементами стохастической матрицы Т являются вероятности переходов p_ij, то эта матрица называется матрицей вероятностей переходов.

Наряду с вероятностями переходов p_ij за один шаг, определим вероятности переходов за m шагов в виде

, m=1, 2, …

Здесь задет вероятность того, что через m переходов случайный процесс окажется в состоянии E_j при условии, что на текущем шаге он находится в состоянии E_i. В силу однородности марковской цепи вероятности , i,j=0,n, не зависят от текущего времени t_k.

Используя марковское свойство, легко вывести следующую формулу  для вычисления вероятностей :

, m=2, 3, …

Это равенство означает, что для попадания из состояния E_i в состояние E_j за m шагов необходимо сначала попасть из состояния E_i  в некоторое состояние E_k за m-1 шагов, а затем за один шаг перейти из E_k в E_j. Вероятность этих двух независимых событий (они независимы в силу марковского свойства) равна произведению вероятностей каждого из них, и, если просуммировать эти произведения по всем возможным промежуточным состояниям E_k, то получится вероятность .

Цепь Маркова называется неприводимой, если каждое ее состояние может быть достигнуто из любого другого состояния, т.е. для каждой пары состояний E_i  и E_j существует целое число m₀ такое, что . Состояние E_i называется поглощающим, если процесс достигнув это состояние, не покидает его. Очевидно, для поглощающего состояния p_ii=1. Состояние E_i называется невозвратным, если случайный процесс после какого-то числа переходов непременно покидает его.

Вернемся к вопросу определения  вероятностей состояний P_i(t_k), i=0,n, предполагая, что начальные вероятности P_i(t₀), i=0,n, при t₀=0 известны.

Используя доводы, аналогичные  тем, что были приведены для обоснования равенства (7), легко определить, что искомые вероятности после первого шага, т.е. на момент времени t₁