Цепи Маркова (1121219), страница 65
Текст из файла (страница 65)
Po(Λ (t)) для любого t > 0. Аналогично можно показать,h min[f(x)F (x) n−1 : u 6 x 6 u + h] 66 P (Xn является рекордным значением и Xn ∈ (u, u + h)) 66 h max[f(x)F (x) n−1 : u 6 x 6 u + h] .и при n → ∞ и max[tj − tj−1 ] → 0 для любого заданногоuXn−1= h f(u) ++ o(h) =f(u)F (u)n>1hf (u)+ o(h).1 − F (u)Заключаем, что процесс рекордов (R(t)) является неоднородным процессом Пуассона НПП ( (t)) с интенсивностью (t) = f(u) / (1 − F (u)).416Глава 2. Цепи Маркова с непрерывным временемТогда1 − F (u)001 − F (u)0ϕAn (x) = E xAn = E [E (xAn | Sn)] =+∞ +∞+∞ZZX ( t) mm− t=xedFS (t) =em=00t(x−1)m!0dFS (t) = M( (s − 1)),и она задает распределение An единственным образом.
Далее, с.в. A1 , A2 ,. . . являются н.о.р.. Согласно описанию очередиQn+1 = An + Qn − h(Qn) и h(Qn) = min [2, Qn ] ,где An не зависит от Qn (на самом деле и от всей последовательностиQ1 , . . . , Qn−1). Следовательно, (Qn) образует ц.м.д.в.Далее, если = ( n) — инвариантное распределение, то в состоянииравновесия выполняются соотношения2x G(x) = M( (x − 1))1x1+2++∞Xixi0+ (x2 − x)ixi− 2i=3=+ (x2 − x2) 2 + G(x)] =X2i= M( (x − 1)) G(x) +(x − x ) i ,1−имеемСледовательно,=1.1+ − x1[G(x) + (x2 − 1)(1 + − x)x2G(x) =+ − x. Тогда при0+ (x2 − x)1] .что и требовалось.Предположим теперь, что Sn ∼ Exp( ) и M( ) =< 2.2i=2+M( (x − 1)) =Решение.
Пусть An — число клиентов, прибывших в течение n-го периода обслуживания, а Sn — длительность n-го периода обслуживания,FS (t) = P (Sn < t) — функция распределения, а M( ) = Ee Sn — п.ф.м..+∞Xi=0,1=0x2= M( (x − 1)) [(x2 − 1)=G(x) = (1 − ) / (1 − x),2p=, где1+ 1+4|x| 6 1.В случае, когда времена обслуживания имеют показательное распределение с параметром , покажите, что0i=0,1= M( (x − 1))иiX(x2 − xi) i ,x2 G(x) = M( (x − 1)) G(x) +=Ex ExQn −h(Qn)где соответствующую величину An следует определить, а h(x) = min{2, x}.Покажите, что Q = (Qn : n > 1) является ц.м.д.в., и найдите выражениедля п.ф.м. E xAn , x 6 1.=Покажите, что если Q имеет инвариантноеP распределениеi= ( i : i > 0) и производящую функцию G(x) =i x , тоG(x) = E xAnQn+1 = An + Qn − h(Qn),Qn+1при условии, что F (t) < 1.
Мы используем тот факт, что F (0) = 0,следовательно, ln [1 − F (0)] = 0, в силу того что F имеет плотность f,сосредоточенную на (0, +∞).Задача 2.12.24. Клиенты прибывают в кондитерскую согласно процессу Пуассона ПП ( ). Единственный продавец кондитерской может виртуозно обслуживать одновременно двух клиентов. Таким образом, всякийраз, когда в очереди находятся два или более клиента, продавец обслуживает сразу двух клиентов; если же в очереди находится лишь один клиент,то обслуживают его одного. Периоды обслуживания S — независимыеслучайные величины, имеющие общую производящую функцию моментовM( ) = E exp( S). Пусть Qn — число людей в кондитерской в момент,когда завершен n-й период обслуживания. Представьте Qn+1 в видегде417Тогда при условии Sn = t с.в. An имеет распределение Пуассона Po( t).Следовательно, вероятностная производящая функция имеет видE R(t) = среднее число рекордных значений на (0, t) =ZtZtZtZtf (u)dF (u)=(u) du =du == d ln[1 − F (u)] = − ln[1 − F (t)]0§ 2.12.
Вопросы к теории цепей Маркова с непрерывным временем=Глава 2. Цепи Маркова с непрерывным временем§ 2.12. Вопросы к теории цепей Маркова с непрерывным временем419418решают их рекуррентно:илиiТогда,NN,== 1+...,0=+ ...+ NN. N −1.(2.12.6)Процесс ухода клиентов образует процесс Пуассона с интенсивностью; формулу (2.12.6) называют теоремой Бурке для системы с потерямиM/M/1/N.0+ (x2 − x)01{1 + (1 − x) [x2 − 1 + (x2 − x)] } =(1 + − x)x21=(1 − x +1+ − x1=N−1h10+ (x2 − 1)(1 + − x)x2 1 − x1− x=00Учитывая предложенное выражение для G(x), положим G(x) =1− xи 1 = 0 . В самом деле, это соответствует геометрическому инвариантному распределению i = i 0 , i > 1, и 0 = 1 − . Тогда мы получаем222x,p1+4.2Если< 1, то инвариантное распределение является геометрическим:i=i(1 − ),=1− .0Задача 2.12.25.
В баре имеется N стульев для посетителей. Посетители входят в бар согласно процессу Пуассона с интенсивностью .Если есть свободный стул, прибывший посетитель на нем располагается,а если нет ни одного свободного — посетитель уходит. Времена пребыванияпосетителей в баре — независимые показательные случайные величиныс параметром . Вычислите вероятность того, что прибывший посетительнаходит свободный стул, при условии, что система находится в равновесии.Для системы в состоянии равновесия опишите процесс ухода клиентов(не считая при этом тех, кто ушел, не найдя свободный стул).Решение. В задаче описан процесс рождения и гибели на{0, 1, . . .
, N}, который является обратимой ц.м.д.в. Уравнения детальногобаланса таковы:0 = 1 , . . . , N−1 = N ;√5−1и2Очевидно, следует положить < 1, т. е. < 2 (что является необходимыми достаточным условием существования (и единственности) инвариантногораспределения). При = , = 1 имеем=Задача 2.12.26. Опишите применение теории ц.м.д.в. и ц.м.н.в. дляочередей с одним сервером. Следует обсудить вопрос существованияустойчивой длины очереди, а также вычислить величины, характеризующиеочередь в состоянии равновесия.Решение.
1. Очередь M/M/1. Это простейший пример: времена между прибытиями являются н.о.р.с.в. Exp( ), а времена обслуживания —н.о.р.с.в. Exp( ). При этом число клиентов Xt в системе в момент t образуетц.м.н.в. на Z+ = {0, 1, . . .} (процесс рождения и гибели) с интенсивностями вида qii+1 = , i > 0, и qii−1 = , i > 1. Если>невозвратной,== 1, то цепь являетсяс нулевой возвратностью,<с положительной возвратностью.=−1 +x= x+откуда получаеми2=1+ +1+x+С. Джонсон (1709–1784), английский издатель и драматургПриравнивая коэффициенты при нулевой и первой степенях x, находимпару (идентичных) соотношенийВсе аргументы против этого, а вера — за это.(О появлении духа человека после его смерти.)).−i > 0.2. Очередь M/G/1. Здесь времена между прибытиями An являютсян.о.р.с.в.
Exp( ), а времена обслуживания Sn — н.о.р.с.в. с заданным распределением. Число клиентов в очереди Xn в момент сразу же после n-гоухода образует ц.м.д.в.:Xn+1 = Xn + Yn+1 − 1(Xn > 1).Здесь Yn — число прибытий за время n-го периода обслуживания; Yn независит от Xn и Yn ∼ Po( s) условно по Sn = s.
Вероятностная производящая функция имеет видϕY (z) = EzY = E [E (zY | S)] = E (e(z−1)S) = MS ( (z − 1)).где Zn — число попаданий в состояние 0 к моменту времени n. В предположении, что X0 = 0, получаемi=1Мы видим, что EZn /n → 1/m0 , гдеСледовательно, состояние 0 положительно возвратно. Поскольку цепь (X n)неприводима, она положительно возвратна. Следовательно, ц.м.д.в. (Xn) имеет единственное инвариантное распределение.Лемма 2.12.28. В состоянии равновесия 0 = 1 − и(1 − ) (1 − z)GY (z)(1 − ) (1 − z)MS ( (z − 1))=.GY (z) − zMS ( (z − 1)) − zzGX (z) = z EzX = EzX+1 = E (zY zX+1(X=0) ) =0 (1− z)GY (z).GY (z) − zlimz→01−z0=.GY (z) − z1 − EYПо правилу Лопиталя эта дробь равна0 / (1− ), т. е.=1− .0i>0гдеподставляяi=i(1 − ), получаемX(1 − ) k =(1 − )k+i−1pi ,0),или, что эквивалентно,Xk=k+i−1pi , т.
е.=Xipi = GY ( ).i>0Задача 2.12.30. Следующее утверждение известно как основная теорема восстановления для процесса восстановления с дискретным временем.Пусть S1 , S2 , . . . — положительные целочисленные н.о.р.с.в. и pk == P (S1 = k). Положим1=EA.Теорема 2.12.29. Если< 1, то ц.м.д.в. Xn положительно возвратна с инвариантным распределением i = (1 − ) i , где —единственный корень уравнения = GY ( ) на интервале (0, 1).Д о к а з а т е л ь с т в о. Запишем GY (0) = P (Y = 0) > 0 и GY (1) = 1.Далее, G0Y (1) = EY = 1/ > 1, а также G00 (z) > 0, т.
е. GY — выпуклаяфункция. Следовательно, уравнение = GY ( ) имеет единственное решение на (0, 1). Далее, P (Xn+1 = k) = P (Xn − Yn = k − 1).Если = ( i) — инвариантное распределение, тоXk =k+i−1 pi ,i> 0При z → 1 имееми EY =i> 0= GY (z) EzX+1(X=0) = GY (z) ( 0 z + GX (z) −GX (z) =GY (z) = MA ( (z − 1)),pi = P (i обслуживаний за типичное время между прибытиями);Д о к а з а т е л ь с т в о. В состоянии равновесия Xn+1 ∼ Xn . Используяэтот факт и вышеприведенное уравнение, запишемоткуда следует, чтогде Yn — число обслуженных клиентов за n-е время между прибытиями.С.в.
Yn вновь не зависят от Xn . Далее Yn ∼ Po( ) условно по An = .Используя те же рассуждения, что и выше, получаемm0 = E 0 (время возвращения в 0) < ∞.GX (z) =Xn+1 = max [Xn − Yn + 1, 0] ,X.nYin + E (Xn /n) = = 1 − + E (Xn /n) > 1 − > 0.E (Zn /n) = 1 − E3. Очередь G/M/1. Предположим теперь, что времена между прибытиями An — н.о.р.с.в. с заданным распределением, а времена обслуживанияSn — н.о.р.с.в. Exp( ). Пусть Xn — число клиентов в очереди в моментсразу же после n-го прибытия. Тогда (Xn) — ц.м.д.в.:Xn = X 0 + Y 1 + Y 2 + .
. . + Y n − n + Z n421Отсюда следует, что EY = ES; это значение вновь обозначим .= EY < 1, то цепь (Xn) положительноЛемма 2.12.27. Есливозвратна.Д о к а з а т е л ь с т в о. Производя итерации вышеприведенного равенства, находим§ 2.12. Вопросы к теории цепей Маркова с непрерывным временемГлава 2.
Цепи Маркова с непрерывным временем4200J0 = 0, Jn = S1 + . . . + Sn , n > 1,Yn = inf{m > 0 : m + n = Jk для некоторого k} == время от момента n до следующего прибытия, n = 1, 2, . . .Переходные вероятности задаются следующим образом:P (Yn+1 = i|Yn = 0) = pi+1 , i > 0,P (Yn+1 = i − 1|Yn = i) = 1, i > 1.Ц.м.д.в. неприводима и апериодична благодаря условию, что НОД (k : p k >> 0) = 1. Она имеет единственное инвариантное распределение0=1,E [S1 ]k=1 Xpi ,E [S1 ]k > 1,i> kа следовательно, положительно возвратна. Тогда приP (An) = P (Yn = 0) →0=1n → ∞.ES1б) Будем считать, что восстановления происходят в моменты появленияцепочек 000100, не налегающих одна на другую. Вероятность появлениятакой цепочки до момента n > 6 равна 1/26 .
С другой стороны,111= P (An) + P (An−4) 4 + P (An−5) 5 .2622Согласно основной теореме восстановления при n → ∞ правая частьстремится к1111+ 4 + 5 ,E [S1 ]22и что S0 = N − 1, I0 = 1.а) Покажите, что (Rt) t>0 при больших временах стремится к постояннойи для конечного значения R∞ вероятность P (R∞ > r) возрастает с ростоминтенсивности инфицирования (s,i) при всех r > 0.б) В стандартной модели эпидемии полагают(s,i)=is,Ni=iдля некоторых постоянных,> 0.Обоснуйте такой выбор интенсивностей.в) Покажите, что в пределе при N → ∞ стандартная эпидемия, начавшаяся с одного инфицированного, приводит к положительной пропорцииинфицированного населения тогда и только тогда, когда > .Решение. а) Интенсивности перехода гарантируют, что сумма S t + It невозрастает по t. Следовательно, траектории ц.м.н.в. R t не убывают.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
