А.Н. Зубков - Курс лекций по теории случайных процессов, страница 3

. . , ξm = j, ξm+1 6= j, . . . , ξm+n = j} =XX=P {ξm+1 = y1 , . . . , ξm+n = j | ξ0 = j, ξ1 = x1 , . . . , ξm = j} P {ξ0 = j, . . . , ξm = j} =x1 ,...,xm−1 6=j y1 ,...,yn−1 6=j= P {∆1 = m}Xy1 ,...,yn−1 6=jP {ξm+1 = y1 , . . . , ξm+n = j | ξm = j} = P {∆1 = m} P {∆2 = n} .Докажем теперь нашу теорему.

[Доказательство теоремы 3.2] При условии ξ0 = j {ω : ∃t > 0 : ξt = j} = {ω : ∆1 < ∞}.Поэтому j возвратно ⇔ P {∆1 < ∞} = 1.Положим(1, ξn = j,In (ω) =0 иначе.PN∀ N < ∞ положим ν(N ) = n=1 In = max {k | Tk 6 N }.M {In | ξ0 = j} = P {ξn = j | ξ0 = j} = pjj (n), Mν(N ) =9NXn=1pjj (n).Если P {∆1 < ∞} = 1, то ∀ k < ∞ P {Tk < ∞} = 1, следовательно,∀ k < ∞∃ N (k) : P {Tk < N (k)} = P {ν(N (k)) > k} >Так как N (k) −→ ∞ (k −→ ∞), тоNXn=11k⇒ M (ν(N (k))) > .22pjj (n) −→ ∞ (N −→ ∞).Если же p = P {∆1 < ∞} < 1, то рассмотримν = lim ν(N ) = max {k : Tk < ∞}N−→∞P {ν = N } = P {min {k : ∆k = ∞} = N + 1} = pn (1 − p),так как ∆i независимы.

Но тогда∀NNXpjj (k) = Mν(N ) 6 Mν =k=1p< ∞,1−pчто завершает доказательство. Пример 4.1. Случайное блуждание по целочисленным точкам. ξ1 , ξ2 , . . . — независимые случайные величины; P{ξk = 1} = p, P{ξk = −1} = q = 1 − p. S0 = 0, Sn = Sn−1 + ξn = ξ1 + · · · + ξn — случайное блуждание. Этоцепь Маркова с множеством состояний S = Z. Из симметрии задачи ясно, что либо все состояния будут возвратными, либо все не будут возвратными одновременно. Применим ранее доказанный критерий для определениявозвратности состояния 0.(0,если n нечётно;np00 (n) = P{Sn = 0} =nn222Cn p q , если n чётно.Нас интересует сходимость рядапри k −→ ∞.

Отсюда получаем:∞Pn=1√n n nC2np q . Из анализа известна формула Стирлинга: k! = (1 + o(1)) 2πknC2n∼√2π · 2n2πn2n 2nen 2nek ke22n= √ ,πn∞ (4pq)nP(4pq)n n n√откуда C2np q ∼ √, то есть сходимость нашего ряда равносильна сходимости ряда.πnπnn=11Если p 6= q, то pq = p(1 − p) < P4 , следовательно 4pq < 1 и ряд сходится как геометрическая прогрессия. Если√1же p = q, то ряд принимает види расходится. Применяя критерий возвратности, получаем, что любоеπnсостояние возвратно тогда и только тогда, когда блуждание симметрично (p = q).nПример 4.2. Двумерное целочисленное случайное блуждание.

ξ1 , ξ2 , . . . независимы; P{ξk = 1} = p, P{ξk =−1} = q = 1 − p. S0 = (0, 0), Sn = Sn−1 + (ξ2n−1 , ξ2n ) = (ξ1 , ξ2 ) + (ξ3 , ξ4 ) + · · · + (ξ2n−1 , ξ2n ). Множество состоянийS = Z2 .nnPP(1)(2)(1)(2)(1)(2)Sn = (Sn , Sn ), Sn =ξ2k−1 , Sn =ξ2k . Sn и Sn суть одномерные блуждания из предыдущегоk=1k=1(1)(2)примера.

p(0,0)(0,0) (2n − 1) = 0. В силу независимости p(0,0)(0,0) (2n) = P{Sn = 0, Sn = 0} = p200 (n) ∼Условия сходимости/расходимости ряда те же, что и в первом случае.А вот в трёхмерном случае соответствующая вероятность возврата ∼то есть трёхмерное блуждание уже всегда будет невозвратным.(4pq)2n.πn(4pq)3n— ряд сходится при всех p, q,(πn)3/23.5.

Предельная теорема для конечных цепей МарковаТеорема 3.4. Пусть {ξk } — цепь Маркова со множеством состояний S = {1, . . . , n} и матрицей переходных вероятностей P = (pij ). Если существует такое v < ∞, что все элементы матрицы P v положительны,то существует предел lim pij (t) = πj > 0, j ∈ S, не зависящий от начального состояния i, причём (π1 , . .

. , πn )t→∞— единственное решение системы уравнений:(Pnxk pkj = xj ,Pk=1nk=1 xk = 110j∈S p(t) = (p1 (t), . . . , pn (t)) = p(0)P t для всех натуральных t (p(0) — произвольное начальное состояние).Нужно показать, что p(0)P t −→ π = (π1 , . . . , πn ) при всех возможных p(0).Поделим t на v с остатком: t = kv + r, 0 6 r < v. pP t = pP kv+r = (pP r )(P v )k . Если мы докажем, что длявсех x x(P v )k −→ π, то это будет верно и для pP t (разбиваем P t на подпоследовательности).

Поэтому далее всевыкладки будут производиться с матрицей P v .PРассмотрим оператор A : Rn −→ Rn , действующий так: Ax = xP v . Gn = {(x1 , . . . , xn ) ∈ Rn | xj > 0, xj =1} ⊂ Rn — множество вероятностных распределений на n-элементном множестве. Покажем, что Gn инвариантноотносительно A.Утверждение 3.5. A(Gn ) ⊆ Gn .nP Пусть x ∈ Gn . y = Ax = xP v = (y1 , . .

. , yn ). yj =xk pkj (v) > 0. Первое свойство проверено. Далее,k=1nXyj =j=1n XnXxk pkj (v) =j=1 k=1Отсюда y ∈ Gn . Введём в Rn метрику ρ(x, y) =nPk=1XkxkX|jpkj (v) ={z=1}Xxk = 1.k|xk − yk |.Утверждение 3.6. В метрике ρ отображение A c матрицей P v является сжимающим с коэффициентомсжатия 6 1 − ε, где ε = min pij (v) > 0.i,jВычислим ρ(xP v , yP v ): n nn Xnn X XXXρ(xP , yP ) =xi pik (v) −yi pik (v) = (xi − yi )pik (v) .vvk=1 i=1Далее, т.к. x, y ∈ Gn ,сумме совпадают:nPi=1k=1 i=1(xi − yi ) = 1 − 1 = 0. Поэтому суммы положительных и отрицательных разностей в этойi=1nXi=1max{xi − yi , 0} = −nXi=1nmin{xi − yi , 0} =Значит, существуют такие индексы r и s, что1X1|xi − yi | = ρ(x, y).2 i=1211ρ(x, y) > 0 > − ρ(x, y) > xs − ys .2n2nДля всех a, b, c, d > 0 верны следующие соотношения: |a − b| = a + b − 2 min{a, b}, min{ac, bd} >> min{a, b} min{c, d}. Отсюда |(xr − yr )prk (v) + (xs − ys )psk (v)| 6 (xr − yr )prk (v) + |xs − ys |psk (v) − 2 min{|xr −yr |, |xs − ys |} · min{psk (v), prk (v)} 6 (xr − yr )prk (v) + |xs − ys |psk (v) − n1 ρ(x, y)ε.

Итак, nnnXXXεε|xi −yi |pik (v)+|xr −yr |prk (v)+|xs −ys |psk (v)− ρ(x, y) =|xi −yi |pik (v)− ρ(x, y). (xi − yi )pik (v) 6nni=1i=1xr − yr >i=1,i6=r,sДалее,vvρ(xP , yP ) 6!ε|xi − yi |pik (v) − ρ(x, y) = (1 − ε)ρ(x, y),ni=1nnXXk=1что и требовалось. Сжимающее отображение имеет единственную неподвижную точку, поэтому имеет место предельное соотношение. Осталось разобраться с системой уравнений.π — неподвижная точка отображения A. Следовательно, πP v = π и для всех p pP t −→ π (t −→ ∞). В частности,(πP )P vt −→ π, поэтому πP — неподвижная точка матрицы P v , а эта точка единственна, следовательно πP = π,то есть π — неподвижная для P . Пример 5.1.

Исправленная модель Эренфестов для диффузии. ξt — число частиц в первом сосуде в моментt (всего n частиц). Случайно выбираем частицу и с вероятностью 21 перекладываем её (с вероятностью 12 ничегоне делаем). Матрица имеет вид: 1100...

022111 10... 0 22 − 2n 2n.2112 0−... 0 2n222n... ............ ...11(Мы исправили модель, чтобы появилась диагональ и выполнялись условия теоремы.) Вычислим предельныераспределения π = (π1 , . . . , πn ) из системы уравнений2π1 = 12 π0 + 12 π1 + 2nπ2...π = n−k+1 π1k+1(1 6 k 6 n − 1)kk−1 + 2 πk + 2n πk+12n. . .1πn−1 + 12 πnπn = 2nPπk = 1Преобразуем:1π0 = n π1π1 = π0 + n2 π2. . .πk−1 +πk = n−k+1n...πn = n1 πn−1k+1n πk+1Индукцией показываем, что πk = Cnk π0 :nn − k + 1 k−1nk−1 nCnk −Cnπ0 =Cn−1− 1 π0 = Cnk+1 π0 .πk+1 =k+1nk+1kPP kИз соотношенияπk = 1 получаем: 1 =Cn π0 = 2n π0 , откуда π0 = 21n , πk = Cnk 21n , т.е предельное распределение цепи биномиально.При больших значениях n (числа частиц) вероятность того, что все молекулы соберутся в одном сосуде,(равная π0 = 21n ) исчезающе мала.4.

Ветвящиеся процессыИмеются частицы, которые делятся на поколения. В каждом поколении каждая частица порождает некоторое (случайное) количество потомков, а сама погибает.Обозначим через µ(t) число частиц в t-м поколении, γ — случайное число потомков у одной частицы (γ —неотрицательная целочисленная случайная величина). k-я частица в t-м поколении порождает γtk частиц; всевеличины γtk независимы и распределены так же, как γ. В начальный момент имеется µ(0) частиц (обычноµ(0) = 1). Каждая частица независимо порождает потомков:(0,если µ(t) = 0,µ(t + 1) =γt1 + · · · + γtk , если µ(t) = k.Возникают следующие вопросы:1.

Когда процесс вырождается?2. Насколько быстро растёт µ(t)?4.1. Производящие функцииПусть ξ — целочисленная неотрицательная случайная величина. Положимfξ (s) =∞Xsk P{ξ = k} = Msξ .k=0Функция fξ называется производящей функцией случайной величины ξ.Свойства производящей функции:1. fξ (0) = P{ξ = 0}, fξ (1) = 1;Pd2. dsfξ (s) = ksk−1 P{ξ = k},3.2dds2 fξ (1)dds fξ (1)= Mξ;= Mξ(ξ − 1) — второй факториальный момент;4. если ξ1 , . . . , ξn независимы, то fξ1 +···+ξn (s) = Msξ1 +···+ξn = Msξ1 . . . Msξn =nQk=112fξk (s).Лемма 4.1.

Пусть ν, γ1 , γ2 , . . . — независимые целочисленные неотрицательныеслучайные величины;(0,ν = 0,γ1 , γ2 , . . . одинаково распределены; f (s) = Msν , g(s) = Msγ1 . Тогда если µ =, то Msµ =γ1 + · · · + γk , ν = k.f (g(s)). Применяя формулу полной вероятности и пользуясь независимостью, получаем:Msµ =∞XP{ν = k}Msγ1 +···+γk =k=0∞XkP{ν = k} (Msγ1 ) = f (g(s)).k=0Если ветвящийся процесс начинается с одной частицы, то µ(1) = γ, f (s) = M sµ(1) | µ(0) = 1 . Положимϕ(t, s) = Msµ(t) .Теорема 4.2. Последовательность {ϕ(t, s)}∞t=0 удовлетворяет рекуррентному соотношениюϕ(0, s) = Msµ(0) ,ϕ(t + 1, s) = ϕ(t, f (s)), t > 0Если при этом P {µ(0) = 1} = 1, тоϕ(0, s) = s,ϕ(t + 1, s) = f (ϕ(t, s)), t > 01.

ϕ(t + 1, s) = Msγt1 +...+γtµ(t)= ϕ(t, f (s)) в силу предыдущей леммы.2. Каждый из непосредственных потомков 1-й частицы порождает свой ветвящийся процесс с теми же свойствами, поэтому µ(t + 1) распределена, как сумма µ(1) независимых экземпляров µ(t):ϕ(t + 1, s) = Msµ1 (t)+...+µµ(1) (t) = f (ϕ(t, s)),т.к. γ = µ(1).Следствие 4.1. Если µ(0) = 1, то ϕ(t, s) = ft (s) = f (f (.

. . f (s) . . .) (t раз)dОбозначим Mγ = A = f ′ (1). Mµ(t) = dsMsµ(t). Из рекуррентного соотношения имеемs=1Mµ(t + 1) =ϕ′s (t"#d′′+ 1, s)=ϕ(t, f (s))= ϕu (t, u)f (s)dss=1s=1u = f (s)s=1= Mµ(t) · A,Определение.• Если A < 1, то процесс называется докритическим. В этом случае Mµ(t) −→ 0, P {µ(t) > 0} −→0(t −→ ∞).• В случае A = 1 процесс называется критическим. P {µ(t) > 0} −→ 0, если P {γ = 1} 6= 1 (это мы докажемпотом).• Если, наконец, A > 1, то Mµ(t) −→ ∞ (t −→ ∞) с экспоненциальной скоростью. Такие процессы называются надкритическими.4.2.

Вероятность вырождения ветвящегося процессаПоложим q = lim P {µ(t) = 0 | µ(0) = 1}t−→∞Теорема 4.3. q является наименьшим неотрицательным корнем уравнения f (s) = s.Pk= ϕ(t, 0) = ft (0). P {µ(t) = 0 | µ(0) = 1} = ∞k=0 P {µ(t) = k} ss=0Лемма 4.4. Если f (s) =∞Pk=0kpk s — производящая функция распределения {pk }, f (s) 6≡ s, то1. A = f ′ (1) 6 1 ⇒ ∀s ∈ [0, 1) f (s) > s.2. A = f ′ (1) > 1 ⇒ ∃s0 ∈ [0, 1) f (s0 ) = s0 , f (s) > s при s < s0 , f (s) < s при s0 < s < 1.13PP Заметим, что f ′ (s) = kpk sk−1 > 0, f ′′ (s) = k(k −1)pk sk−2 > 0, поэтому f выпукла вниз и не убывает.Отсюда, так как f (1) = 1, видно, что в случае A 6 1 график f (s) лежит выше диагонали на [0, 1), а в случаеA > 1 обязательно на [0, 1) её пересекает.

(Если кто-нибудь нарисует картинку, будет очень хорошо) Докажем по индукции, что 0 6 ft (0) 6 s0 . При t = 0 это очевидно. Из леммы имеем0 6 ft (0) 6 f (ft (0)) = ft+1 (0) 6 f (s0 ) = s0 ,т.е. ft+1 (0) > ft (0) ∀t, следовательно, существует limt−→∞ ft (0) = q 6 s0 .q = lim ft (0) = lim f (ft (0)) = f ( lim ft (0)) = f (q),t−→∞t−→∞t−→∞т.к. f непрерывна. Следовательно, q = s0 . 1).Следствие 4.2. Вероятность вырождения q < 1 ⇔ A = f ′ (1) > 1 (кроме вырожденного случая P {γ = 1} =Пример 2.1. P {ребёнок — девочка} = 0.486, P {девочка доживёт до 18 лет} = 0.97, A — среднее числодетей. Если A · 0.486 · 0.97 > 1, то есть до 18 лет доживает в среднем хотя бы одна девочка, то A > 2.124.

Издемографии известно, что A примерно равно 2.14.Теорема 4.5. Все положительные состояния ветвящегося процесса с f (s) 6≡ s несущественны:∀k > 0lim P {µ(t) = k} = 0.t−→∞От противного, пусть ∃k0 > 0 lim supt−→∞ P {µ(t) = k0 } = vk0 > 0.1. Пусть P {γ = 0} = p > 0. Тогда вероятность вырождения за один шагP {µ(t + 1) = 0 | µ(t) = k} = pk > 0.∀t P {µ(t + 1) = 0} > P {µ(t) = 0} + P {µ(t) = k0 } pk0 (оцениваем сумму снизу двумя слагаемыми)Таким же образом оценивая снизу P {µ(t) = 0} и т.д., получаемP {µ(t + 1) = 0} > pk0tXr=0P {µ(r) = k0 } −→ ∞ (t −→ ∞),так как lim supt−→∞ P {µ(t) = k0 } > 0. Противоречие.2.