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

Тема № 3 Марковские процессы с непрерывным временем   Теперь рассмотрим процесс t ; t  T , где T   0;  . Определение. Случайный процесс t ; t  0;  называется цепью Маркова с непрерывным временем, если для любой последовательности моментов времени     0  t1  t2  ...  tn  ... последовательность t , n   является цепью Маркова. n Обозначим, как и ранее, через E множество состояний цепи Маркова, или фазовое пространство. Обозначим p t, x , s, y   P s  y | t  x  - переходные функции, где 0  t  s , x, y  E . Свойства переходных функций: 1. (Свойство неотрицательности) p t, x , s, y   0 для всех 0  t  s , x , y  E . 2. (Свойство стохастичности)  p(t, x, s, y )  1 для всех 0  t  s , x  E . y E 1, x  y 3. p t, x , t, y    . 0, x  y  4. Имеет место уравнение Колмогорова-Чепмена: p(t, x , s, y    p t, x , u, z   p u, z, s, y  z E для всех u таких, что t  u  s . Определение. Цепь Маркова с непрерывным временем называется конечной, если множество E конечно. Определение. Цепь Маркова с непрерывным временем называется однородной во времени, если выполняется: p t, x , s, y   p t  r , x , s  r, y  для всех 0  t  s и для любого r   такого, что t  r, s  r  0 , т. е. переходная функция зависит лишь от разности   s  t . В этом случае переходная функция может обозначаться так: p t, x , s, y   p , x , y   pxy   . Как правило, в случае конечной цепи Маркова с непрерывным временем мы будем считать, что E  1, N . Для однородных цепей Маркова с непрерывным временем с переходной функцией pij   мы будем формулировать свойства следующим образом: 1. pij    0 для всех   0 . 2.  p    1 ij для всех   0 и любого i  E . j 1, i  j 3. pij 0   . 0, i  j  4. Уравнение Колмогорова-Чепмена pij     pik u   pkj   u  k E для любых u  0,   . Дополнительно мы будем предполагать, что выполняется следующее свойство: 5. (Непрерывность переходной функции в нуле) lim pij    pij 0 для всех i, j  E .   0 Для цепей Маркова с непрерывным временем можно ввести матричную переходную функцию (t )  pij (t ) , имеющую тот же смысл, что для дискретных цепей Маркова N ,N имела матрица переходных вероятностей. Интенсивности переходов   Теорема (без доказательства). Пусть t ; t  0;  - однородная цепь Маркова с непрерывным временем, i, j  E , i  j . Тогда существует (но может быть бесконечным) предел lim pii t   1 t t  0 pij t  , который мы обозначим ii , и существует конечный , который мы обозначим ij . t Определение. Величину ij назовем интенсивностью перехода из i -ого состояния в предел lim t  0 j -ое; а величину ii назовем интенсивностью перехода из i -ого состояния в i -ое. Матрица   ij N ,N интенсивностей. Утверждение. Пусть называется инфинитезимальной матрицей, или матрицей  ; t  0;  - однородная цепь Маркова с непрерывным t временем. Тогда для ее интенсивностей выполняется неравенство  j i ij  ii . Доказательство. Это неравенство имеет место не только в случае конечной цепи Маркова с непрерывным временем. Рассмотрим сумму  pij (t )  1 , j  p (t )  1  p (t) . j i ij ii Для любого M   такого, что M  i , имеет место неравенство 1  pii t  1 M   pij t   . t j i t Устремим t  0  , тогда M  j i M Это неравенство для  j i  j i ij ij ij  ii . верно при любом M   , следовательно, верно и для . Утверждение доказано. Следствие. В условиях утверждения для любого i  E выполняется неравенство  j E ij  0. Определение. Состояние i  E из фазового пространства однородной цепи Маркова с непрерывным временем называется мгновенным, если ii   . Состояние i  E называется задерживающим, если   ii  0 . Состояние i  E называется поглощающим, если ii  0 . Состояние i  E называется регулярным, если оно задерживающее и  j i ij  ii . Определение. Цепь Маркова, все состояния которой регулярны, называется консервативной. Теорема (прямая система уравнений Колмогорова). Переходные вероятности консервативной цепи Маркова с конечным множеством состояний E , | E | N , удовлетворяют системе дифференциальных уравнений dpij (t ) dt  N p k 1 ik (t )kj , по всем 1, i  j i, j  E , с начальными условиями pij 0   , i, j  E . 0, i  j  В матричном виде эта система записывается как  ' t    t   , где  ' t  || pij '(t ) || - матрица, состоящая из производных переходных функций с начальными условиями  0  E NN - единичная матрица порядка N . Доказательство. Зафиксируем h  0 . Тогда для любых i, j  E верно равенство N pij t  h   pij t    pik t  pkj h   pij t   k 1   p t  p h   p t  p h   p t  . kj ik kj ij jj ij Разделим левую и правую часть равенства на h . Тогда pij t  h   pij t  pkj h  p jj h   1   pik t   pij t  . h h h kj При h  0  предел правой части существует, значит, существует и предел левой части, который мы обозначим через pij '() t  (производная pij t  справа). pij '() t   N  pik t kj  pij t  jj   pik t kj . k j k 1 Теперь выведем аналогичное уравнение для левой производной. Для любых i, j  E верно равенство N pij t  h   pij t   pij t  h    pik t  h  pkj (h )  k 1  pij t  h   pij t  h  p jj h    pik t  h  pkj h  . kj Разделим левую и правую часть равенства на h . Тогда верны равенства pij t  h   pij t  1  p jj h  pkj h   pij t  h    pik t  h   h h h kj  pij t  h  p jj h   1   pik t  h  pkj h  . h h k j Предел правой части существует при h  0  , значит, существует и предел левой части, который мы обозначим через pij '() t  (производная pij t  слева). pij '() t   pij t  jj   pik t  kj  kj Мы доказали, что N  p t  k 1 ik kj . pij '() t   pij '() t  . Следовательно, производная dpij (t ) dt N существует и равна  p t  k 1 ik kj . Теорема доказана. Теорема (обратная система уравнений Колмогорова). Переходные вероятности консервативной цепи Маркова с конечным множеством состояний E , | E | N , N dpij (t ) удовлетворяют системе дифференциальных уравнений   ik pkj (t ) , по всем dt k 1 1, i  j i, j  E , с начальными условиями pij 0   , i, j  E . 0, i  j  В матричном виде эта система записывается как  ' t    t  с начальными условиями  0  E NN . Докажите эту теорему самостоятельно. Пусть нам дана некоторая матрица   ij N ,N со свойствами: 1. ij  0 и ii  0 при всех i  j из E . N 2.  j 1 ij  0. Рассмотрим вопрос, существует ли цепь Маркова, для которой произвольная матрица  , удовлетворяющая свойствам 1 и 2, является матрицей интенсивностей. Теорема (без доказательства). Если дана   ij N ,N , удовлетворяющая сформулированным выше свойствам 1 и 2, то прямая и обратная системы уравнений Колмогорова имеют единственное решение  t   pij t  N N со свойствами: 1. 0  pij t    . N 2.  p t   1 . j 1 ij 3.  s  t    s    t  . Процессы размножения и гибели Определение. Консервативная цепь Маркова  ; t  0;  называется процессом t размножения и гибели, если для ее переходных функций выполняются следующие условия: 1). pi,i 1 t   i t  o t  . 2). pi,i1 t   i t  o t  , i   . 3). pi ,i t   1  i  i t  o t  . 1, i  j 4). pi, j 0   . 0, i  j  5). 0  0 , 0  0 ; для всех i  1 величины i и i больше нуля. Это пример процесса с бесконечным множеством состояний. Легко видеть, что верно равенство pi,i 1 t   pi,i1 t   pi,i t   1  o t  , а матрица интенсивностей (бесконечного размера) будет иметь вид  0 0 1 (1  1 ) 2   1   (2  2 ) 2     Покажем, как будут выглядеть прямые и обратные системы уравнений Колмогорова для такого процесса. Уравнения из прямой системы  ' t    t   , как легко видеть, для всех i, j  E будут иметь вид dpi, j t   pi, j 1 t  j 1  pi, j t j  j   pi, j 1 t  j 1 . dt Мы будем считать, что 1  0 . 1, i  j Начальные условия стандартны: pi, j 0   . 0, i  j  Уравнения из обратной системы  ' t    t  для всех i, j  E будут иметь вид dpi , j t  dt  i pi1, j t   i  i  pi , j t   i pi 1, j t  0, i  j с теми же начальными условиями pi , j (0)   . 1, i  j  Обозначим pn t   P t  n  , где n   0 . Тогда набор pn 0  P 0  n  по всем n   0 даст начальное распределение процесса размножения и гибели. Очевидно равенство  pn t    pi 0 pi ,n (t ) . i 0 Определение. Вектор q  qo , q1,... , где qi  0 ,  q распределением процесса размножения и гибели i 0 i  1 , называется стационарным  ; t  0;  , t если выполняется  равенство qn   qi pin (t ) для всех n   0 и для любого t  0 . i 0 Если начальное распределение совпадает со стационарным ( pn 0  q n , n   0 ), то распределение в любой момент времени t  0 также будет совпадать со стационарным:  pn t    qi pi,n t   qn n   0 . i 0 Таким образом, если начальное распределение равно стационарному, то pn (t ) не зависит от t . Выведем дифференциальное уравнение для pn (t ) . Будем считать, что 1  0 , тогда для всех n   0 можно выписать   pn t  t   pn 1 t  n1t  o t     pn t  1  n  n  t  o t     pn 1 t   n 1t  o t   o t  . Тогда pn t  t   pn t  t   n 1 pn 1 t   n  n  pn t   n 1pn 1 t   o 1 . Переходя к пределу при t  0 получаем: dpn t    n 1 pn 1 t   n  n  pn t   n 1 pn 1 t  . dt Итак, пусть дано начальное распределение pn 0, n   0 . Найдем стационарное   распределение. Если распределение qn , n   0 - стационарное, и pn (t )  qn , при всех t  0 , то dpn t   0. dt При n  0 получаем, что 0  0  p0 t   1p1 t   0 . Поскольку pn t   qn и 0  0 , то 0q 0  1q1  0 . При n  1 получаем 0q 0  1  1 q1  2q 2  0 и так далее. Получаем бесконечную систему линейных уравнений для отыскания стационарного распределения. Она легко решается последовательно: из уравнения при n  0 получаем q1  0 / 1 q 0 , подставляя его в уравнение при n  1 получаем уравнение 0q0  1  1 0 / 1 q0  2q2  0 , из которого следует, что q 2  01 12 q 0 и т.д. Методом математической индукции можно доказать, что qn   n   . Так как q i 0 n 01 n 1 12  n q 0 для всех  1 , то     i 1    1 . q 0 1   0 1       i 1 1 2 i   Если ряд  01 i1 сходится, то получаем, что стационарное распределение 12  i процесса размножения и гибели имеет вид 1 , q0   01 i1 1 i 1 12  i i 1 01 n 1 1 для всех n   . 12  n 01 i1 1 i 1 12  i Отметим, что в некоторых прикладных дисциплинах (к примеру, в теории массового обслуживания) под процессами размножения и гибели понимают и консервативные цепи Маркова процессы с конечным числом состояний, аналог графа переходов для которых выглядит следующим образом: qn    Здесь вершины S i  i - это значения принимаемые сечениями случайного процесса, стрелки обозначают ненулевые вероятности переходов за малый промежуток времени (нагружены они интенсивностями переходов), а в силу консервативности интенсивности переходов из i -ого состояния в i -ое не отмечены вовсе.