Цепи Маркова (1121219), страница 54

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 54)

Покажем, что EMt = exp[t ( − 1)] . Для этого, положив g(t) = EMt ,применим условное математическое ожидание по предыдущему моменту u:Xg(t + u) = E [E (Mt+u | Mu)] =(k E Mt) P (Mu = k) =k>1= (EMt)Xk P (Mu = k) = E [Mt ] E [Mu ] = g(t)g(u).k>0Действительно,ϕt+h (s) = ϕh [ϕt (s)] , t, h > 0.Для h, близкого к 0, имеемXpk sk + o(h)ϕt+h (s) = (1 − h) ϕt (s) + hXpk [ϕt (s)] k + o(h),ϕh (s) = (1 − h)s + hиВ первом томе мы затронули теорию ветвящихся процессов с дискретным временем. Основной моделью являлся процесс деления частицили живых организмов, ведущий к образованию некоторого числа потомков.

Непрерывный аналог этой теории в основных чертах представленниже.Предположим, что в момент времени t = 0 в биологический растворпомещена живая клетка. Через показательно распределенное время с интенсивностьюпроисходит деление клетки и образуется k новыхPклеток с вероятностью pk , k = 0, 1, . . ., со средним значением =kpkdtАристотель (384–322 до н.э.), греческий философВероятные невозможности предпочтительнееневероятных возможностей.т. е.ϕt+h (s) − ϕt (s) = h§ 2.10. Ветвящиеся процессы с непрерывным временем.Марковские процессы миграции и сетис очередями ДжексонаТот факт, что ц.м.н.в. (Xt , 0 6 t 6 T) и (Yt , 0 6 t 6 T), где Yt = XT −t , одинаково распределены, проверяется стандартным образом.

Итак, цепь (X t)обратима во времени тогда и только тогда, когда она находится в (единственном) стационарном состоянии.§ 2.10. Ветвящиеся процессы с непрерывным временемk>0k>0X− ϕt (s) +k>0pk [ϕt (s)]k+ o(h).Разделив на h и перейдя к пределу при h → 0, получим уравнение (2.10.1);начальное условие ϕ0 (s) = s очевидно.Ветвящиеся процессы — это примеры процессов рождения и гибели,которые не являются процессами Пуассона. Например, предположим, чтокаждая клетка делится на две (p2 = 1).

Пусть Nt = M1 − 1 — число клеток,образовавшихся в растворе к моменту времени t. Оказывается, N t имеетгеометрическое распределение. В самом деле,k>1g(t) = 1 − t + t + o(t) = 1 + t( − 1) + o(t).Мы видим, что функция g(t) дифференцируема в точке t = 0, положительнаP (Nt = 0) = P (нет ни одного деления на (0, t)) = e− t ,P (Nt = 1) = P (единственное деление на (0, t)) =Zt=e− s e−2 (t−s) ds = e−2 t (e t − 1),Далее, для t, близких к 0, опять применим условные математические ожидания относительно момента 0:0344Глава 2. Цепи Маркова с непрерывным временеми общая формула такова:§ 2.10. Ветвящиеся процессы с непрерывным временемгде1и2— корни уравненияx = p 0 + p1 x + p 2 x2 ;s1(2 )e−2(s2 −s1)sn−1× ....

. . × (n )e−n= n!e− (n+1)tZt0...Zt0 s1e−ne(s1 +...+sn)0= n!e− (n+1)tZt(sn −sn−1)e− (n+1)(t−sn)dsn . . . ds1 =× 1(s1 < . . . < sn) dsn . . . ds1 =...=ZtP (Nt = n) = P (n делений на (0, t)) =Zt Zte s ds0!n ,один корень всегда равен 1. Не теряя общности, можно предположить, что1 6 2.Случай а): надкритический. Здесь 2 = 1 и 0 < 1 < 1. Видим, что в этомслучае 1 = вымир , где вымир — вероятность вымирания популяции с течением времени.Случай б): критический. Здесь 1 = 2 = 1.Случай в): докритический. Здесь 1 = 1, 2 > 1.В случаях а) и в) имеем:n! = e− (n+1) t (e t − 1) n .Это указывает на то, что (Nt) действительно не является неоднороднымпроцессом Пуассона.

Напротив, инфинитезимальная вероятность скачкаϕt (s) =ϕt (s) =ϕ0 (s) = s,dϕt (s)= − ϕt (s) + ϕt (s) 2 ,dts,e t − (e t − 1)s−1 6 s 6 1.dϕt (s)2= − ϕt (s) + ϕt (s) 2 ,dt33ϕ0 (s) = s,находим, что для s ∈ (−1, 1) выполняется соотношение(s − 1)e t/3 − (2s − 1)1и ϕt (s) →при t → ∞.2(s − 1)e t/3 − (2s − 1)2В случае квадратичного полинома общего вида запишем уравнение(2.10.1) в видеdϕ (s) = p2 (ϕt (s) −dt t1) (ϕt (s)−2),t→∞1=(вымир1t > 0, −1 < s < 1.в случае а),в случае в)и сходимость имеет экспоненциальную скорость.В случае б) имеем:ϕt (s) = 1 −1−s,1 + (1 − s) t(1 − p1) /2t > 0, −1 < s < 1.Здесьlim ϕt (s) = 1t→∞При p0 = 1/3, p2 = 2/3, интегрируя уравнениеϕt (s) =2)lim ϕt (s) =зависит от k, т.

е. от значения Nt , тогда как для неоднородного процессаПуассона эта вероятность должна иметь вид (t)h + o(h) независимо от k.Пример 2.10.1. Продолжим предыдущую тему и найдем точное выражение для ϕt (s) в случае, когда функция в уравнении (2.10.1) квадратичная.При p2 = 1, интегрируя уравнение− 2 (s − 1)e− p2 ( 2 − 1)t,(s − 2) − (s − 1)e− p2 ( 2 − 1)t1 (s −Видим, чтоP (Nt+h − Nt = 1 | Nt = k) = kh + o(h)получаем345ϕ0 (s) = s, −1 < s < 1,и сходимость будет обратного степенного типа: (ϕ t (s) − 1) ≈ O(1/t).Бо́льшая часть этого параграфа посвящена марковским сетям.

Какмы упоминали ранее, примеры таких сетей играют все возрастающую рольв современных приложениях, таких как телекоммуникации, банковскиеоперации, промышленное производство с одной стороны, биология и экологические исследования с другой стороны.Мы начнем с простого случая замкнутых сетей. Рассматриваются J «станций» («узлов» или «колоний») и K «мигрирующих объектов»(«заданий», «заявок» или «клиентов»). Состояние системы описываетсявекторомn = (n1 , . . .

, nJ), где ni ∈ {0, 1, . . . , K } и n1 + . . . + nJ = K;значение ni равно числу заявок на станции i. См. рис. 2.69346Глава 2. Цепи Маркова с непрерывным временем§ 2.10. Ветвящиеся процессы с непрерывным временем347Число C (K, J) состояний n в этой модели возрастает с ростом K и J,а именно(K + 1) (K + 2)C (K, 2) = K + 1, C (K, 3) =, ...2Общая формула такова:C (K, J) =Рис. 2.69So many paths that wind and wind.Е. У.

Уилкокс (1855–1919), американский журналист и писательУдобно представлять нашу модель в терминах сети из серверов (обслуживающих устройств): сервер i находится в узле i, и его длительностьвремени обслуживания распределена как ∼ Exp(−r ii) независимо от различных клиентов и от других серверов. Клиенты бесконечно блуждают отсервера к серверу.Как и следовало ожидать, уравнения детального баланса (2.10.2) влекутза собой уравнения для стационарного распределения (2.10.3).Мы ищем инвариантные вероятности n в виде< 1 ∀ k = 1, . . . , J, то правая часть — это произведение геоJPni = K; еслиметрических вероятностей с параметрами k при условииi=1= 0 для некоторого k, то получаем дополнительное условие n k = 0.

Теперь следует определить постоянные k .Подставляя вероятности (2.10.4) в уравнения (2.10.2), находимnkk rijJackson J. R. Jobshop-like queueing systems // Management Sci. 1963. V. 10.P. 131–142.=k=1Ynk nj +1 ni −1rji ;ik jJYkk6=i,jэти равенства выполняются тогда и только тогда, когдаi rij(2.10.5)= j rji ∀ i 6= j.Далее, уравнения инвариантностиJYk=1nkkX16j6Jrjj 1(nj > 1) +XJY16i,j6J i6=j k=1n k −1i rij 1(njk j13 См.(2.10.3)16i,j6J : i6=j(2.10.4)k=116j6Jnkk .С другой стороны, уравнения инвариантности имеют видXXrjj 1(nj > 1) +nn− j + i rij 1(nj > 1) = 0 ∀ n.(2.10.2)JYn+ j −rji ∀ n, ni > 1.i∝kn rij =Если 0 <Уравнения детального баланса для любых i, j, i 6= j, имеют видnj=1сивность, с которой заявки покидают узел i.Будем называть (N(t)) замкнутым процессом миграций, или замкнутойсетью Джексона по имени Дж.

Р. Джексона13 . Удобно задать генераторц.м.н.в. (N(t)), не фиксируя заранее число заявок K, циркулирующих всети. Им является (полу)бесконечная производящая матрица Q = (q nn0)с элементами0rij , если ni > 1 и n = n + j − iqnn0 =для некоторых i, j = 1, . . . , J, где i 6= j,0в противном случае.C (i, J − 1).(заявка переходит из узла i в j). Здесь и далее j обозначает вектор с единственной ненулевой компонентой 1 в позиции j. По определению случайнаявеличина Nj (t) задает число заявок на станции j в момент времени t.Далее, R = (rij) задает Q-матрицу размера J × J, которая определяетJPгенератор этой ц.м.н.в. Сумма ri = −rii =rij задает суммарную интен-i=0Эта модель описывается векторнозначной цепью Маркова с непрерывным временем (N(t)), где N(t) = (N1 (t), .

. . , NJ (t)); она характеризуется(скачками n 7→ n + j − i ,1 6 i, j 6 J, i 6= jинтенсивностями rij 1(ni > 1),KX> 1) = 0Глава 2. Цепи Маркова с непрерывным временем 1=  ...  с компо-i riji : i6=jnkk1Jn0 = (n0 ,...,n0):1Jn01 +...+n0J =KJYj=1nkkXn0jk ∀ n = (n1 , .

. . , nJ),n1 + . . . + nJ = K.(2.10.7)Тогда { n } определяет единственное инвариантное распределениедля замкнутого процесса миграций (N(t)) с общим число заявок K.Кроме того,lim P N(t) = n = n(2.10.8)Векторным:j> 0,jположитель-> 0, j = 1, . . . , J.Как и ранее, продолжительности времен обслуживания в узле i являютсян.о.р.с.в. Exp( i). Вектор n имеет неограниченные компоненты nj , j == 1, . .

Характеристики

Список файлов лекций