Gorbachev_OsnoviTeoriiSluchajProtces[1]

m j (n) = min pij (n) = pi′,

j (n);

i

M

j

(n) = max p

ij

(n) = p

′′ (n);

i

i j

i;0 ≤ m j (n) ≤ pij (n) ≤ M j (n).

Выясним, как ведут себя m j (n) и M j (n) при

n → ∞ .

Оче-

видны соотношения

m

(n +1) = p ′ (n +1) =

p ′

p (n) ≥

p ′ m

(n) = m

j

(n);

j

i j

∑ i l

lj

∑ i l

j

l S

l S

M j (n +1) = pi′′j (n +1) = ∑pi′′l plj (n) ≤ M j (n),

l S

т.е.

m j (n) и M j (n) – монотонные (соответственно – неубы-

вающая и невозрастающая) функции n.

Покажем теперь, что lim[M j (n) − m j (n)] = 0 . Выберем

n→∞

(пока – произвольно) i

и i

; пусть n > n( j) .

1

2

0

Запишем

pi1 j (n) = ∑pi1l (n0( j) ) plj (n − n0( j) ); l S

pi2 j (n) = ∑pi2l (n0( j) ) plj (n − n0( j) ), l S

и вычтем первое равенство из второго:

pi2 j (n) − pi1 j (n) = ∑[ pi2l (n0( j) ) − pi1l (n0( j) )] plj (n − n0( j) ). l S

Имеет место очевидное равенство

∑[ pi2l (n0( j) ) − pi1l (n0( j) )] = 0.

l S

Обозначим

αl = pi2l (n0( j) ) − pi,l (n0( j) )

и пусть L += {l : αl ≥ 0} и L −= {l : αl < 0} (эти множества не пусты, поскольку тривиальный случай αl = 0 не пред-

ставляет интереса). Тогда

81

pi2 j (n) − pi1 j (n) = ∑αl plj (n − n0( j) ) + ∑αl plj (n − n0( j) ) ≤

l L+

l L−

≤ M j (n − n0( j) ) ∑αl + m j (n − n0( j) ) ∑αl =

l L+

l L−

= h [M j (n − n0( j) ) − m j (n − n0( j) )],

где h = ∑αl = −∑αl <1

l L+

l L−

Полагая теперь i1 = i

′

и

′′

получим

i2 = i ,

M

j

(n) − m

j

(n) ≤ h [M

j

(n − n( j) ) − m

j

(n − n( j) )]

0

0

Если n > kn0( j)

(где k- положительное целое число), то по ин-

дукции:

M j (n) − m j (n) ≤ hk [M j (n − kn0( j) ) − m j (n − kn0( j) )].

Отсюда вытекает предельное соотношение

lim [M j (n) − m j (n)] = 0

n→∞

(k→∞)

Полученный результат означает, что вероятность pij (n)

ограничена снизу и сверху сходящимися при n → ∞ к общему пределу монотонными функциями, причем этот предел отличен от нуля, т.к. при достаточно больших n m j (n) > 0.

Обозначая этот предел p*j , получим предельное распреде-

ление цепи {p*j }Nj=1 (здесь N – число состояний цепи). Пока-

жем, что это распределение совпадает с её стационарным распределением. Для этого составим систему уравнений

pij (n +1) = ∑pil (n) plj l S

Переходя к пределам при n → ∞, получим
p*j = ∑pi* pij ,	j =1,2,...	(3.21)
i S
что совпадает с (3.19), т.е. { p*j } j S	= { p j } j S .

82

Докажем единственность решения (3.21). Пусть наряду с

решением {p j }Nj=1 существует решение {q j }Nj=1. Покажем, что

оно совпадает с {pj }Nj =1. Справедливы равенства

N	N N	N
qj = ∑ql plj	= ∑∑ql1	pl1l plj = ∑ql plj (2) =
l =1	l =1 l1 =1	l =1
N		N
= ∑ql plj (3) = ... = ∑ql plj (n).
l =1		l =1

Устремляя n → ∞ , получим

N

ql =∑q j p j = p j , l=1

что завершает доказательство теоремы 3.4.

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

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

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

Класс всех дискретных однородных неразложимых непериодичных марковских цепей с счетным множеством состояний состоит из двух подклассов:

– подкласс A: цепи, все состояния которых нулевые; для них имеет место предельное соотношение

i, j lim pij (n) = 0;	(3.22)
n→∞

83

– подкласс B: цепи, все состояния которых ненулевые;

для них существуют пределы
i, j lim pij (n) = u j > 0	(3.23)
n→∞

(здесь u j = m−j 1, mj – по-прежнему среднее время возврата в

j-ое состояние; для ненулевого состояния mj<∞).

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

Теорема 3.5

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

–если цепь принадлежит к подклассу A, то она неэргодична, т.е. для неё не существуют ненулевое предельное и стационарное распределения вероятностей состояний;

–если цепь принадлежит к подклассу B, то она эргодична, т.е. имеет ненулевое предельное распределение состояний, которое одновременно является единственным стационарным распределением состояний цепи.

Справедливость теоремы относительно свойств марковских цепей подкласса A проверяется просто. Ввиду (3.21) для

предельного распределения цепи {pj}j S для j имеем
lim p j (n +1) = lim ∑pi (1) pij (n) = ∑pi (1) lim pij (n) = 0 ,
n→∞	i S	i S	n→∞
		n→∞
т.е. цепь имеет нулевое предельное распределение.
Пусть теперь распределение {p j }j S			претендует на роль

стационарного распределения; тогда для j, n должно выполняться равенство

p j = ∑pi pij (n)

и снова, устремляя n→∞, для j получаем pj = 0 (здесь и далее используется признак мажорируемой сходимости функциональных рядов, приводящей к их равномерной сходимо-

84

сти и допустимости применения в них почленных предельных переходов).

Перейдем к доказательству утверждения теоремы относительно цепей подкласса B.

Существование ненулевого предельного распределения цепи следует из (3.23).

Покажем существование и единственность стационарного распределения цепи подкласса B.

Как нетрудно видеть, для каждого целого L (L > 0) имеет место неравенство

L	L
∑uk	= lim ∑pik (n) ≤1
k=1	k=1
	n→∞
∞
(поскольку для n,j ∑pik (n) =1 ).
k=1
Составим соотношение
	L
pik (n +1) = ∑pij (n) p jk ≥ ∑ pij (n) p jk ,
j S	j=1

где L снова произвольное положительное целое. Переходя к пределам при n→∞ (что допустимо для конечной суммы без дополнительных условий), получим

L

uk ≥ ∑u j pjk , k S.

j =1

Суммируя полученные неравенства по всем k, приходим к неравенству

L

∑ uk ≥ ∑ ∑u j p jk

k S k S j=1

L	L
= ∑u j ∑p jk . = ∑u j .
j=1 k S	j=1

В пределе при L→∞ (когда j пробегает все значения из S) левая и правая части последнего неравенства оказываются равными, что возможно лишь в том случае, если при таком

85

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

uk = ∑u j p jk , k S.

j S

Если	бы для чисел {u j }j S выполнялось		условие
∑u j =1 ,	то они представляли бы собой стационарное рас-
j S
пределение цепи. Однако пока лишь известно, что			∑u j ≤1 .
			j S
Поэтому перейдем к набору чисел {v }		, где v =	u j	. Эти
	j j S	j	∑ui

i S

числа удовлетворяют условию нормировки и системе уравнений

vk = ∑vj pjk , k S,	(3.24)
j S

т.е. представляют собой стационарное распределение цепи. Покажем единственность этого распределения.

Пусть {w j }j S – произвольное стационарное распределе-

ние цепи, удовлетворяющее, следовательно, системе уравнений (3.24). Начиная с этой системы, легко перейти (по индукции) к системе уравнений

wk = ∑wj pjk (n), k S

j S

для любого n. Устремляя n→∞, получим

wk = ∑wjuk = uk , k S,

j S

т.е. набор {u j }j S является единственным стационарным распределением цепи, если она принадлежит подклассу B. Заме-

86

тим, еще раз, что предельное и стационарное распределения такой цепи совпадают.

Практическое значение теоремы 3.5 состоит в том, что эргодичность конкретной счетной марковской цепи можно проверять существованием для неё ненулевого положительного решения системы уравнений (3.23).Этот факт иллюстрируется в следующем примере.

Пример дискретной марковской цепи: модель системы массового обслуживания с дискретным временем.

Рассмотрим модель некоторой организационной системы, предназначенной для массовой обработки однотипных объектов и состоящей из устройства обработки УО и бункера Б, способного хранить NБ объектов, ожидающих обработки (рис.3.1). На вход системы в дискретные моменты времени t,t +τ, t + 2τ,... (t ≥ 0), могут поступать объекты, обра-

зующие случайный поток: в каждый дискретный момент времени с вероятностью 1 - p на входе системы объекты не появляются и с вероятностью p появляется один (и только один) объект, независимо от их поступления в другие моменты времени.

Z1						Z2
		Б			УО

Z3

Рис. 3.1

Б – бункер, УО – устройство обработки, Z1 – поток объектов, поступающих на обработку, Z2 – поток обработанных объектов, Z3 – поток объектов, отклоненных от обра ботки из-за занятости бункера

87

Обработка объектов в УО представляет собой случайный процесс с отсутствием последействия: вероятность того, что обработка объекта, находящегося в УО в момент t, будет завершена до момента t + τ , равна q и не зависит от того,

сколько времени уже велась его обработка до момента t, и от поступления других объектов в систему.

Постоянство вероятностей p и q выражает стационарность процессов поступления и обработки объектов.

Дисциплина обслуживания простая: объект, пришедший позже – позже и обслуживается, причем объекты из Б в УО поступают также в дискретные моменты времени (следующие после освобождения последнего).

Пусть нас интересует существование стационарного режима обслуживания объектов и способность системы обслуживать в этом режиме поступающие в неё объекты. Поскольку эта способность определяется числом находящихся в системе объектов и динамикой его изменения, будем обозначать состояние процесса событием Ai(t) – нахождением в системе в момент t ровно i объектов. Когда емкость бункера конечна (NБ < ∞), множество состояний процесса S конечно ( S = {A0 , A1,.., ANБ +1}); при неограниченной емкости бункера

(NБ = ∞), множество S счетно.

Итак, задача состоит в выяснении условий существования и в определении стационарного распределения описанного процесса.

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

Если NБ < ∞, то выполнены все условия теоремы 3.4 и

цепь эргодична. Рассматривая связь состояний цепи для двух смежных моментов t и t + τ, получим:

88

A0 (t + τ) = A0 (t) [B B C] A1(t) B C;

Ai (t + τ) = Ai−1(t) B C Ai (t) [B C B C] Ai+1(t) B C; (i =1, N − 2)

AN −1(t + τ) = AN −2 (t) B C AN −1(t) [B C B C] AN (t) C,

A0 ( ) A1( ) ...... AN ( ) =V ,

где событие B – появление на входе системы в момент t нового объекта, событие С – окончание к моменту t +τ обработки объекта, находящегося в УО, V –достоверное событие

(P(V) = 1) N = NБ +1.

Переходя	к вероятностям состояний системы
Pi (t) = P( Ai (t))	(с учетом сделанных предположений о неза-

висимости событий B и С между собой и от всех Ai(t), а также об отсутствии последействия процесса обработки), получаем

P0 (t + τ) = P0 (t)(1− p + pq) + P1(t)(1− p)q;

Pi (t + τ) = Pi−1(t) p(1−q) + Pi (t)[(1− p)(1−q) + pq] + Pi+1(t)(1− p)q; (i =1, N −1)

PN−1(t + τ) = PN−2 (t) p(1−q) + PN−1(t)[(1− p)(1−q) + pq] + PN (t)q;

N	N
∑Pi (t + τ) =∑Pi (t) =1.
i=0	i=0

Для стационарного режима, который при N < ∞, как мы

убедились, существует, эти равенства переходят в следующие:

89

P0 = P0 (1 − p + pq) + P1 (1 − p)q;

P1 = Pi−1 p(1 − q) + Pi [(1 − p)(1 − q) + pq] + Pi+1 (1 − p)q;

(i =

1, N − 2

)

(3.25)

PN −1 = PN −2 p(1 − q) + PN −1[(1 − p)(1 − q) + pq] + PN q;

N

∑Pi =1.

i=0

Полученная система уравнений есть не что иное, как (3.24). Ее решение имеет вид:

P

=

p(1

− q) i

P

(i =

);

1, N −1

i

0

q(1

− p)

P =

(1 − p)

p(1

− q) N

P ;

N

0

q(1

− p)

P0

=

1

.

N −1

p(1

− q) i

p(1 − q) N

∑

+ (1 − p)

i=0

q(1

− p)

q(1 − p)

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

Пусть теперь NБ = ∞, т.е. бункер обладает неограничен-

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

90