Gorbachev_OsnoviTeoriiSluchajProtces[1]

Умножая обе части каждого равенства (3.16) на zn и складывая их, получим

	V (z) −1 =U (z) V (z)
или	V (z) =	1	.
		1 −U (z)

В теории степенных рядов известна лемма Абеля, кото-

∞

рая в наших условиях утверждает, что ряд ∑an сходится к

n=0

a < ∞ тогда и только тогда, когда существует предел

lim ∑an zn = a	(an ≥ 0).
z↑1

∞
Следовательно, если U (1) = ∑un = Fi =1, то limV (z) = ∞,
n=1	z↑1

∞

т.е. Ri = ∑pii (n) = ∞. Этим доказывается необходимость ус-

n=1

ловия теоремы.

Достаточность следует из анализа равенства

		U (z) = V (z) −1.
		V (z)
			∞
Если Ri = ∞ (V (1) = ∞), т.е. ряд			∑vi	расходится,
			i=0
			∞	= F1 =1, что
то limV (z) = ∞	и	limU(z) =1, т.е. . ∑un
z↑1		z↑1

n=0

означает возвратность i-го состояния.

В связи с доказанной теоремой следует особо отметить,

что ввиду недостаточности условия lim Pii (n) = 0 для сходи-

n→∞

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

Теорема 3.2. Однородная дискретная марковская цепь возвращается за бесконечное число шагов в исходное i-ое

71

состояние с вероятностью 1 бесконечное число раз, если это состояние возвратно, и лишь конечное число раз, если оно невозвратно.

Пусть Tk – случайная величина, равная числу шагов, за которое цепь возвратится в i-ое состояние ровно k-ый раз. Событие Ak ={Tk <∞} означает, что цепь вернется за бесконечное число шагов в i-ое состояние хотя бы k раз; наоборот, событие Ak ={Tk =∞} состоит в том, что за бесконечное чис-

ло шагов цепь вернется в i-ое состояние менее k раз. Возврат цепи в i-ое состояние за бесконечное число шагов бесконечное число раз представляет собой возвращение цепи в i-ое состояние не менее k раз, каково бы ни было число k. Это событие можно, следовательно, записать в виде:

∞	∞
B = I{Tk < ∞} = IAk
k=1	k=1

С другой стороны, используя прежнее обозначение, имеем Fi =P( A1 ) = P{T1 < ∞} = v. Далее, согласно формуле пол-

ной вероятности,

P(A2 ) = P{T2 <∞} =

= P{T2 < ∞| T1 < ∞}P{T1 < ∞}+ P{T2 < ∞| T1 = ∞}P{T1 = ∞}.

Но

P{T2 < ∞ | T1 = ∞} = 0 и P{T2 < ∞ | T1 < ∞} = P{T1 < ∞} = v (в

силу однородности цепи, вероятность хотя бы двух возвращений в i при условии, что один возврат произошел, равна вероятности хотя бы одного возвращения).Поэтому P(A2 ) = v2 и (по индукции) P( Ak ) = vk .

В силу монотонности событий {Ak } ( Ak+1 Ak ) , используя теорему о непрерывности вероятности, найдем

∞			n		=lim P( An ) = limvn .
P(B) = P IAk		= lim P IAk
k =1		n→∞	k =1		n→∞	n→∞

72

Когда Fi =V =1, получим P(B) =1, т.е. цепь, находясь

в i-ом исходном состоянии, с вероятностью 1 возвращается в это состояние за бесконечное число шагов бесконечно много

раз. Если же Fi =V <1, то P(B) = 0 или P(B ) =1, где B – событие, состоящее в том, что за бесконечное число шагов цепь вернется в исходное состояние лишь конечное число раз.

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

Нередко представляет интерес вопрос об относительном времени пребывания однородной марковской цепи в данном состоянии, т.е. точнее говоря, об отношении числа шагов n, на которых цепь имела данное состояние, к общему числу шагов N, которое прошла цепь к данному моменту.

Вкладывая в случайную величину Tk прежний смысл, образуем последовательность

T (1) = T1, T (2) = T2 −T1 , ..., T (k ) = Tk −Tk−1 , ...,

элементы которой представляют собой число шагов, за которое цепь, попавшая k-1-ый раз в i-ое состояние, вернется в это состояние k-ый раз. Ясно, что для однородной марков-

ской цепи случайные величины T (1) ,T (2) , ....	имеют одинако-
вое распределение и независимы.
Рассмотрим математическое ожидание
∞
MT (k ) = MT (1) = mT = ∑ jP{T (1)	= j).
j=1

Если i-ое состояние марковской цепи возвратно, то по определению P{T (1) < ∞} =1, в противном случае P{T (1) < ∞} <1 и

P{T (1) = ∞} =1 − P{T (1) < ∞} > 0. Поэтому для невозвратного состояния mT = ∞, а неравенство mT < ∞ с необходимоcтью влечет за собой возвратность i-ого состояния.

73

Предположим, сначала, что mT <∞. В этом случае, в

силу возвратности состояния, n неограниченно растет с ростом Tn = N. Применяя усиленный закон больших чисел, получим

n

∑T (k ) k =1

n

Отсюда

=N вер1→mT .

n N →∞

n

вер1

1

→

.

N

mT

N →∞

Известно, что для последовательности случайных вели-

чин

∞

из

вер1

{Zk }k=1

Zk →a, где a – неслучайная величина,

k→∞

следует

lim

MZk = a. Поэтому

k→∞

n

1

lim M

=

,

mT

N →∞

N

где

n

=

n

имеет смысл относительного времени нахожде-

T

N

n

ния цепи в i-ом состоянии.

Пусть теперь mT = ∞; i-ое состояние при этом может быть как невозвратным, так и возвратным. В первом случае при Tn → ∞ .

n		n вер1			n
	=		→0 и	lim M			= 0.
Tn		N
				N →∞	N

Для случая возвратности i-го состояния рассмотрим последовательность «урезанных» случайных целочисленных

величин {τ(mk ) }∞k=1 , определенных равенством

		(k )	(k)	≤ m;
(k )	T		, если τm
τm	=		(k )
		,		> m,
	0		если τm

где m – некоторое произвольное фиксированное целое число.

74

Для математического ожидания Mτ(mk ) получим

Mτ(mk ) = Mτ(m1)	m
	=∑ jP{T (1) = j};
	j=1

с ростом m Mτ(m1) неограниченно возрастает, так как

∞

∑ jP{T (1) = j} = ∞

j=1

По усиленному закону n → ∞ (N → ∞)

n

∑τ(mk )

k =1 вер1→ Mτ(1)

n m

больших чисел при

→∞

(m→∞)

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

Но T (k ) ≥ τ(mk ) , в силу чего

n
∑T k		N	вер1
k =1
	=		→ ∞,
n		n

т.е.

n вер1→0 .

N N →∞

Отсюда

lim M n =0 .

N →∞ N

Итак, математическое ожидание относительного времени нахождения однородной марковской цепи в i-ом состоянии равно величине, обратной математическому ожиданию времени первого возвращения в это состояние (время здесь исчисляется числом шагов).

75

Можно выразить математическое ожидание M	n		че-
	N

рез переходные вероятности Pii(k ) . Для этого, рассматривая i- ое состояние как исходное, введем случайные величины ξk :

1, еслинаk - ом шаге цепь возвратиласьв i - оесостояние; ξk = 0 впротивном случае.

Ясно, что Mξk = Pii (k). Для фиксированного N получим

M n =N

т.е.

n
M ( ∑ξk	)		N	pii (k)
k=1			= ∑		,
N				N
			k=1

		N
		∑pii (k)		1
	lim	k=1	=
		N		mT
	N →∞

Заметим, что невозвратное состояние необходимо явля-

∞

ется нулевым, поскольку из сходимости ряда ∑pii (k) следу-

k =1

ет, что lim pii (k) = 0 .

k→∞

Докажем важную теорему, характеризующую «солидарность» свойств состояний марковской цепи.

Теорема 3.3. Для неразложимой однородной дискретной марковской цепи справедливы следующие утверждения:

а) если одно из состояний такой цепи нулевое, то и все состояния нулевые;

б) если одно из состояний возвратное, то и все возврат-

ные;

в) если одно из состояний периодическое с периодом d, то и все состояния периодические с периодом d.

Пусть i и j – два различных произвольных состояний цепи. Из условий теоремы следует:

M > 0, N > 0 : α = pij (M ) > 0, β = p ji (N ) > 0

76

С учетом (3.10) можно записать

Pii (M + n + N ) = ∑ ∑pik (M ) pkl (n) pli (N ) ≥

k s l s
≥ pij (M ) p jj (n) p ji (N ) =αβp jj (n).	(3.17)
Аналогично получим
p jj (M + n + N) ≥αβpii (n) .	…(3.18)
Устремим n → ∞. Если i-ое состояние –	нулевое, то

lim pii (M + n + N ) = 0 и из полученного неравенства (3.17)

n→∞

следует

lim pjj (n) = 0.

n→∞

В силу произвольности i и j это доказывает п.а) теоремы. Допустим, далее, что j-возвратное состояние, т.е.

∞
∑p jj (n) = ∞ . Складывая левы и правые части (3.17) при
n=1
n =1,2,..., получим
∞	∞
∑pii (M + n + N ) ≥ αβ∑p jj (n) = ∞,
n=1	n=1

из чего следует, что i-ое состояние также возвратно, т.е. справедлив п. б) теоремы.

Обратимся теперь к доказательству п.в). Пусть di и dj – наибольшие общие делители чисел, образуюших, соответственно, множества Wi и Wj, определенные условиями

Wi = {n : pii (n) > 0} и Wj = {n : p jj (n) > 0} (допускается равенство этих делителей и единице). Очевидно, что M + N Wi и M + N Wj (что это так читатель может проверить самостоятельно). Рассмотрим множество W = {M + N + n}, где n – любой элемент множества Wi. Все

элементы множества W делятся на dj, т.е. W Wj (т.к. p jj (M + N + n) > 0 – см.(3.18)) и одновременно имеют н.о.д., равный di. Поэтому d j ≤ di . Аналогичные рассуждения при-

77

водят к неравенству di ≤ d j , что доказывает равенство di = dj

ип.в) теоремы.

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

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

i, j : lim Pij (n) = 0.

n→∞

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

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

Определение 3.3. Дискретная марковская цепь называется эргодичной, если существует независимое от начального состояния ненулевое предельное (финальное) распределение

вероятностей её состояний {p*j } j S ,	удовлетворяющее усло-
вию
j S; lim pij (n) = p*j	> 0.	(3.19)
n→∞

Определение 3.4. Стационарным распределением дис-

кретной марковской цепи называется такое распределение вероятностей её состояний {p j } j S , которое не изменяется с

течением времени (т.е. не зависит от n).

Это свойство для однородной дискретной марковской цепи можно выразить следующим образом.

Связь между распределениями цепи в моменты n и n+1 определяется системой уравнений

p j (n +1) = ∑pi (n) pij , j =1,2,...

i S

78

Для стационарного распределения, согласно определению, имеют место равенства

j : p j (n +1) = p j (n) = p j ,

p j = ∑pi pij , j =1,2,...	(3.20)
i S

В дальнейшем мы будем полагать, что стационарное распределение цепи существует, если оно является ненулевым (дляj pj > 0). Это вызвано тем, что нулевое решение системы (3.20) не может быть стационарным ввиду требования нор-

мировки ∑p j =1.

j S

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

Теорема 3.4. Для того, чтобы конечная однородная дискретная марковская цепь была эргодичной, необходимо и достаточно, чтобы она была неразложимой и непериодической. При этом её предельное распреде-

ление {p*} совпадает со стационарным распределе-

j j S

нием p j = ∑pi pij , j =1,2,... , которое единственно.

i S

Для доказательства этой теоремы нам потребуется следующая лемма, которую приводим без доказательства.

Лемма 3.1. Для любого конечного набора взаимно простых чисел {ai }ir=1 существует такое k0 , что для любого k ≥ k0 существует совокупность r неотрицательных целых чисел {xi }ir=1 , для которых

k= ∑ai xi .

i=1r

79

Необходимость условия теоремы 3.4. очевидна: если при

n → ∞ для i,j pij(n)→pj > 0, то для i,j,ε > 0 n0 = n0(i,j,ε): для

n > n0 pij(n) > pj - ε.

Отсюда при ε < ε0	~	= max n0	для i,j
	= min p j , n > n0
	j	i, j
pij (n) > 0, p ji (n) > 0,	т.е. все состояния цепи непериодичны

и образуют один класс сообщающихся состояний. Достаточность условия теоремы 3.5. требует более

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

Действительно, из сообщаемости и непериодичности состояний цепи следует, что для любого i cуществуют такие

взаимно простые n1,

…,

nr,

что

pil (nk ) > 0

(k =

1, r

).

Тогда

согласно

лемме

3.1

существует

n0(i) такое что

для

n ≥ n

0

(i) существуют

{x

}r

(x

i

≥ 0),

позволяющие

i i=1

представить n в виде

r

n = ∑xk nk .

Отсюда, для n ≥ n0 (i)

k =1

r

r

pii (n) ≥ ∏ pii (xk nk ) ≥ ∏[ pii (nk )]xk > 0 .

k =1

k =1

Для каждой пары (i,j) имеем:

l = l(i, j) : pi, j (l) > 0.

Отсюда,

полагая n0 =n0 (i) + l(i, j) = n0 (i, j),

легко получаем,

что n ≥ n0 (i, j)

pij (n) ≥ pii (n − l) pij (l) > 0.

Зафиксируем j и найдем n0( j) = max

n0 (i, j).

i S

Теперь i, n > n0( j)

pij (n) > 0 .

Введем величины (при произвольном n):

80