Комбинаторные методы в теории случайных процессов - Такач Л.
Скачать (прямая ссылка):
распределение величины немедленно получается из равенства
P{S"+*+iO|?o"fl = P{?n+i <?|?0 = /}. (3)
Действительно, при ?0 = i каждое из событий {?"+*+1 и
{?"-и <!?} происходит тогда и только тогда, когда (" + &+1)-е требование
поступает после окончания (" + /)-го требования.
Число обслуживаний (среди первых "), которым предшествует период
бездействия прибора, равно
а" = max{0 и r-Nr+ 1 -?0 для r = 0, 1, ..., "- 1}, (4)
и pff = n - а". Кроме того, очевидно, что
Р" = ?о + Nn - е". (5)
Число обслуживаний в начальный период занятости прибора
равно
p0 = min{r: ?>0 + Nr = r и г = 0, 1, ...}, (6)
а если такого г нет, то р0 = оо.
Между распределениями случайных величин а" и р0 существует интересная
связь: для 0^k<n
Р {а" > k |?0 = /} = Р {р0 < "1C,, = / + k) (7)
и
Р = 01S0 = i) = Р {р0 >"|Со== i). (8)
g 28. Флуктуации длины очереди
109
Равенство (8) очевидно. Для доказательства (7) заметим, что из (4)
вытекает, что
Р {ап >k} = Р {g0 + Nr + k ^.г для некоторого г = 0, 1 ti- 1},
(9)
а из (6), что
Р (Ро < п)= Р (So + Nr ^ г для некоторого г = 0, 1,..., п- 1}. (10)
Сравнивая (9) и (10), видим, что вероятность того, что а">йдля процесса с
начальной длиной очереди t,0 = i, равна вероятности того, что ро < п для
процесса с начальной длиной очереди ?0 = = i + k. Отсюда и следует (7).
Процесс Q
Далее мы будем предполагать, что {vr} - либо переставляемые случайные
величины, принимающие неотрицательные целые значения, либо, в частности,
взаимно независимые и одинаково распределенные случайные величины,
принимающие неотрицательные целые значения. Для них мы будем использовать
те же обозначения, что и в гл. 2, а именно Р (vr =/} = л;-, / = 0, 1, 2,
...,
Е {zVr} = л (z), Е {vr} = Y. E{vr(vr - 1)} = Y2. Var {vr} = а2 и 2 = 6 -
наименьший неотрицательный вещественный корень уравнения л (2) = = 2.
Если у ^ 1 и 1, то 6 = 1. Если у> 1 или Лч = 1, то 0 ^ <6< 1.
Теорема 1. Если vb v2, ..., vn -переставляемые случайные величины, то при
i ^ 1
PK"<*|&> = *'} = P{Wn<n + *-i}-
n-in-i-j
-Е Е(1-7rh~)p{Ni=i+k' Nn=i+k+l]'
/=1 1=0
Р{?п<6|?о = 0} = Р{?"<6|?о=1} . (П)
и, в частности,
n-i
р {?"= о|?" = я = Е (1 - i) р М. = Л (12)
/=о
при 0.
Доказательство. Рассмотрим соотношение (1) для
Если заменить v,, v" на v", vn-i> • ••> vi. получим новую
случайную величину
ln = max{Nr-r + 1 для r = 1 п и Nn-n + ?0}, (13)
110
Г л. 5. Теория очередей
распределение которой совпадает с распределением величины Таким образом,
р {Sn ^ * I So == ^"} = P{N,<r + k для г = 1, .. п и N'n^n + k - i).
(14)
Для 1 правую часть равенства (14) можно найти из формулы (2) § 6, При / =
0 и i= 1 значения (14) совпадают. Если же k = = 0, то (14) можно получить
из формулы (4) § 6. Теорема .доказана.
Если vb v2, vn - взаимно независимые и одинаково распределенные случайные
величины, то в соотношении (11) можно написать Р {Nj = j + k, Nn = j + k
+ /} = P {jV= / + 6} P {ЛД_/ = /}. Тогда (11) и (12) дают
Р {?* ^ k |?о = /} = Р [Nn < п + к - /} -
П - I
- 2 Р К*-/ = 0|?о = I) Р [Nj = j+k} (15)
/ = 1
для /^0. Устранив условие ?0 =/\ получим
п
P{En<*} = P{5o+(V"<n + *}-S Р{?"-у = 0}Р{^ = /+*}. (16)
/=1
Теорема 2. Если {vr} - взаимно независимые и одинаково распределенные
случайные величины и у<1, то предельное рас-пределение lim Р {?" = k) =
Pk, k = 0, 1,2, ..., существует и не за-
П->оо
висит от распределения начальной длины очереди. Для | z | < 1
рМ-Ёр"г'- 07)
k=0
где Р0 - 1 - у, a Pk, /г = 1, 2, ..., задаются формулами (15) и (16) § 7.
Вероятности Qk = Р0+ ... +Pk,k = 0, 1,2, ..., задаются формулами (10) и
(11) § 7. Кроме того, для k = 0, 1,2, ...
оо
Qft"l-(1-V)2 P{Nj = j + k}. (18)
-/=i
Если у> 1 и n^l, то limP{|" = fe} = 0 для любого k вне за-
П-> оо
висимости от распределения начальной длины очереди.
Доказательство. Предельные распределения для {?"} и {?"} совпадают, ибо
из (3) вытекает, что
lim Р {?" < k | ?о = г} = lim Р {?" < k | ^ = г} (19)
П ОО П->0о
§ 28. Флуктуации длины очереди
Ш
для любого г. Далее, в силу (14)
Р {Nr< г + k для г = 1, ..., п) - Р {?0 + Nn > п + Уг}<
<Р{?"<6}<Р {Nr<r + k для г = 1, п}. (20)
Согласно слабому закону больших чисел, ПтЛД/п = у п0 ве"
ГС->оо
роятности. Если у<1> то из этого следует, что lim Р {?0 + >
П-> оо
>я + й} = 0 для любой случайной величины ?0 и для любого k. Пусть
положим в (20) п-> сю. Тогда по теореме о непре-
рывности для вероятностей
lim Р {?"<?} = Р {jV, < г + k для г = 1, 2, . ..} = Qft, (21)
П-> оо
вне зависимости от распределения начальной длины очереди. Вероятности
{Qft} заданы в теореме 3 (или теореме 4) § 6. Явные формулы для Qk, k =
0, 1, 2, и Pk = Qk - Qk^u k=\, 2, приведены в § 7.
При и щф\ по теореме 3 § 6 правая часть неравен-
ства (20) стремится к нулю при м-> сю. Отсюда следует, что lim Р {?" k) =
0 для всех k, и теорема доказана.
п-> оо
Замечание. При л0>0 и ло + n^l теорему 2 можно доказать также с помощью
теории цепей Маркова. В этом случае п = 0, 1,2,...} является неприводимой
