3. Основы теории случайных процессов. Карлин (1971) (3. Основы теории случайных процессов. Карлин (1971).djvu), страница 10
Описание файла
DJVU-файл из архива "3. Основы теории случайных процессов. Карлин (1971).djvu", который расположен в категории "". Всё это находится в предмете "теория массового обслуживания (асвк)" из 11 семестр (3 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр DJVU-файла онлайн
Распознанный текст из DJVU-файла, 10 - страница
Рассмотрим все возможные реализации процесса, для которых Х„= 1, Х„= й а первое возвращение в состояние ! происходит на й-м шаге. Обозначим зто событие символом Ем События Ео (й = 1, 2, ..., и), очевидно, являются несовместными. Вероятность события, состоящего в том, что первое возвращение происходит на й-м шаге, есть, согласно определению, гвч. РассмотРим тепеРь те Реализации, котоРые в течение оставшихся п — й шагов ведут себя так, что Х„= й Используя марковское свойство, имеем Р(Ев)= Р(первое возвращение происходит на й-м шаге ! Х,=- с) Х ХР(Х вЂ” ~)Х вЂ” г) — )..Р.
1<А<и (напомним, что Ри = 1). Следовательно, Р (Х„=-1~ Хо 1) = ~ Р (Ед) ~с;~ (нР— ~) ~ Р поскольку по определению )оч = О. Введем теперь ироизводящине функции. О п р е д е л е и и е. Производящая функция РО(в) последовательности (Рй, п=О, 1, 2, ...) задается формулой (5.2) Аналогично определяется производящая функция последовательности ((и, и =- О, 1, 2, ...) (определение вероятностей С для рли 2. Марковские Чеки случая, когда с'час, следует ниже непосредственно за формулой (5.9) ): Р, (в)= ~)",,в"> (в(<1. (5.3) в=о Мы уже приводили (см.
стр. 1б гл. 1) ') следующее свойство производящих функций: если А(в) = с..с аово и В(в) = ~ Ьсв', о=о с-о (5А) то А (в) В (в) = С (в) =- ~ с,в', ( в (< 1, с=о (5.5) где с, = аойс + асЬ, с + ... + а,Ь,. (5.6) Бели а„положить равными соц а Ь, равными Р,', то из (5.1) и (5.6) следует, что Рсс (в) Рсс (в) = Рсс (в) — 1, (в ~ < 1, (5.7) нли 1 Рц(в)=,, (в(<!.
(5.8) В (5,7) единица вычитается потому, что (5.1) не выполняется при а =- О. Точно так же, как мы получили соотношение (5.1), приходим к соотношению Рсс= Х 1цРсс с~ / а)0, (5,9) ! у! ') Л(е) СС се) =~~ а ео) ~~ ЬРс о=о с-о = ссоЬо+ (аьЬо+ Ь,ао) е+ (аоьо+ а,Ьс — аоЬо) во+ ...
= е ' ~ аСЬ„С вЂ” — ~ЧЗ„сие, Ь-о ,С-о ! О-о где сц есть вероятность того, что процесс впервые достигнет состояния 1 из состояния с на й-м шаге. Как и ранее, полагаем )вс =- О для всех 1 и 1. Из (5.9) и (5.5) получаем Рсс(в)=Рсс(в)Р(с(в), (в)<1, (5.10) ф Б. Возвратность Будем называть состояние ! возвратныл!, если ~ !",'!==1. Это ь ! означает, что состояние ! является возвратным тогда и !олька тогда, когда вероятность вернуться в исходное состояние ! после некоторого конечного числа шагов равна единице.
Если лл (и<1, ь ! то состояние ! будем называть невозвратным. Ниже мы докажем теорему, связывающчю свойство возвратности состояния с поведекием и-шатовых переходных вероятностей Р!!ь Для доказательства этой теоремы нам понадобится следующая Лемма 5.! (Абель). (а) Если ряд ~ аь сходится, то о-о !!гп ~~~ аозо = ~ а„= а оф! о=о о-о (5.!!) (Йп означает, что з стремится к ! слева, т. е. по значего! ниям, меньшим 1). (б) Если ао>0 и !1гп ~~'.~ аоз" = а< со, то оь! о-о ~а„= !пп ~ ао=а.
о о Д о к а з а т е л ь с т в о. (а) Мы покажем, что Ит ~~~~~ ао(зо — 1) = О. оФ! ! ь-о (5.12) ~ ао(зо — 1) = ~ ао(зо — 1)+ ~ч.'~ ао(в~ — 1) ( о=о !о-о ь я+! ( ~ ао(зо — 1) + ~ ао(зо — 1) . (5,13) !о-о ! о-не! Поскольку ряд ~ ао сходится, то для любого е>О можно найти о-о Аг(е), такое, что ~ ао <в/4 для всех А!'>А!. Выберем такое А!.
Далее, Гл. 2. Марковское Чева Для 0 ( (з <! ~я~~ ао(зо — 1) (Мй11з" — 1 1, к-о (5.!4) где М= щах ~а„~<со, так что для з, достаточно близких к 1, о<о<о> имеем ! ~ ао(зо — 1) <е/2. о=о Для оценки ~ ао(в" — 1) просуммируем по частям: ! ь= оо> 1 ао(з~ — 1)~ = ~ ~ (Ао — Ао+>)(зо — 1) = о-Фв> о-лч> — Акт, (ело' — 1) — ~ Ао(зо — в"о') > (5.15) где Ао= ~ а,. Легко видеть, что для (5.15) имеет место оценка > о 41( ) 4 2' Вместе с предыдущей оценкой это дает ~ а,(е' — 1) <е а значит, и 2~ ао а для всех а.
о-о Кроме того, ~ ао является монотонно возрастающей функцией п. о-о > Таким образом, ряд ~ а„сходится. Пусть сумма ряда равна а'. о-о Обращаясь к первой части леммы, получаем, что а'= а. а при условии, что з достаточно близко к 1. ° (б) Поскольку ~ аово( ~ ао для 0<в<1, случай а= оо очек=о о-о виден. Если а< со, то в силу исходного предположения имеем ~2~ авэо<а< во для 0<в<1, о-о Э Б. Воэвротногть оз С помощью этой леммы легко доказывается Т е о р е и а 5.1.
Состояние !' является возвратным тогда и только тогда, когда ~ Р",! =- Д о к а з а т е л ь с т в о. Пусть ! — возвратное состояние, т. е. ~ ~!,. = 1. В силу леммы 5.! (а) имеем о=о ! пп ~ ! "нз" = !1ш Р!, (з) = 1; 5Ф! о о яф! тогда из (5.8) следует, что !!ш Рн(з) = 1пп ~ Р!;з"= оо, оФ! яФ! о-о Обращаясь к лемме 5.1(б), заключаем, что ~~'., Р,"! = оо. о=о Чтобы доказать достаточность, предположим, что состояние ! невозвратное, т. е. ~~~ !!!<1.
Используя лемму 5.1(а) и соотношео=! иие (5.8), получаем !пп Рн(з) < оо, 5А! Отсюда в силу леммы 5.1(б) следует, что ~ Рн<оо. ° о-! Из теореллы 5.1 непосредственно вытекает Следствие 5.1. Если ! ! и ! — возвратное состояние, то состояние ! также является возвратным. Доказательство. Так как ! ~1, то существуют такие целые числа и, п > 1, что Р!г>0 и Р!;>О. Пусть о — положительное целое число. С помощью аргументов, к которым мы уже прибегали (см. стр, 52), нетрудно получить неравенство РО$ ! ото > р'орч ро !! г! !! пр Гл. 2.
Марковские цепи бо Суммирование по т дает О ~~'~~ Р! > ~~~~ РПРНРН вЂ” Р! Рц ~ Рп. и-о о-о Таким образом, если ~ Р„ расходится, то расходится и о-о ~чз Р'„. и Доказав это следствие, мы установили, что возвратность, как и периодичность, является свойством класса эквивалентности, т. е. все состояния в классе эквивалентности либо возвратны, либо невозвратны одновременно. й б. ПРИМЕРЫ ВОЗВРАТНЫХ МАРКОВСКИХ ЦЕПЕЙ П р и м е р 1.
Рассмотрим одномерное случайное блуждание по одномерной целочисленной решетке. За каждый переход частица с вероятностью р перемещается на единицу вправо и с вероятностью д — на единицу влево (р + д = 1); следовательно, имеем Реа =О, Ров=~„)РЧ = —,',' Рд, п=О, 1, 2, ....
(6.1) опв-1 2и (2п~ л и (2пН и и Воспользуемся формулой Стирлинга 1 и! — и 'е и )с2В (6.2) и запишем (6.1) в виде (рц) 2 и (Чрд)в )с пп )Гпп Легко проверить, что р(1 — р) = Рд ('/„, причем равенство имеет место тогда и только тогда, когда р = д = '/ь Следовательно, ~~Л„Ров= во тогда и только тогда, когда Р = Ъ Таким обРазом, од-а номерное случайное блуждание возвратно тогда и только тогда, когда р = д = '/в (Вспомним, что возвратность является свойством класса!) Интуитивно ясно, что если р Ф- д, то положительна вероятность того, что частица, отправляясь из начала координат, будет смещаться к + со, если р ) д (к — во, если р ( д), ни разу не возвращаясь в исходное состояние. П р и м е р 2.
Обратимся теперь к двумерному случайному блужданию по двумерной целочисленной решетке. Пусть вероятности смещения на единицу влево, вправо, вверх, вниз — все рав- Гл 2. Марковские цели 62 где и! с„= !пах =66..„,.„~,.(.- -, 1 (6.7) Здесь мы воспользовались тем фактом, что -- 0= -ч и! Л /! (и — 1 — /)! ( 3 / — — (, ) а, 1, О<а+/жи (6.8) Для больших п значение с„ достигается при ! = / — п/3 Действительно, пусть !', и /, — те значения ! и !, на которых достигается максимум выражения и! !! 1! (и — 1 — /И и! и! /о 1а+ !И ( !а! (1а — !И (и— и! /о' 'а' (и !о — /о)' л! !а !а !И ( /а! (1о+ !И (и и! /о! !а! (и /о !аИ л! !о-й+ !И (/а !И !о! (и и! !о! /а! (и 1о /о)! и! — ( 1а !а !)' !а! 1а! (и — /о !аИ Оо+ !И!о! (и Эти неравенства сводятся к следующим двум: п — !о — 1(2/о(п — с,+1, п — /о — 1 ( 2!о ( п — /, + 1.
Следовательно, ао — п/3 и /о — п/3 при больших п. Подставляя в (6.7), преобразуем (6.6) к виду рал ( (и/3)! (и/3)! (л/3)! 2 "3" ( и / Воспользовавшись формулой Стирлинга, для правой части (6.9) получаем следующее асимптотическое выражение: 3~ 3 2л "и !' Суммируя такие члены, получаем л ! при 0 (! + / ( и, Сразу же можно выписать следующие четыре неравенства: й' а' Сlрссивры вооврлсньсх,лоркооокох цьнвй Следовательно, ~ Ров< оо, и в силу теоремы 5.1 состояние, предл-! ставляемос началом координат, является невозвратным. Поскольку возвратность — свойство класса, а все состояния сообщаются, частица, совершающая одно- или двумерное симметричное случайное блуждание, с достоверностью вернется во всякое состояние, в котором она когда-либо пребывала.
В трехмерном симметричном случайном блуждании частица, покинув состояние, с положительной вероятностью не вернется в него никогда. П р имер 4. Рассмотрим марковскую цепь, описывающую серии успехов при биномиальных испытаниях. сЫатрица переходных вероятностей этой цепи имеет вид 0 0 Ра ! Р, р, О р, О ! — р, О О 1 — р, (О < Рс <1). Р„О (' — Ра)(1 — Р!) . (1 — рл), п) О, ил= 1, п= — 1.
Теперь если мы просуммируем вероятности Щ, то получим л!н-! л!н-! ~с С'оо — — Х (ил 2 — иь,,) =(1 — и,)+(ио — и,)+ ... +(и„,, — сс„), л ! л ! Состояния цепи образуют единственный класс эквивалентности (всякое состояние цепи можно достичь из любого другого состояния) Поэтому в силу следствия 5.1 нам достаточно исследовать возвратность одного состояния, например нулевого. Имеем Сов= ро=( (1 Ро) (6,10) С ~=(П(! Р!) Р -! п)1. ~ !=а Уравнения (5.10) можно переписать в виде л-2 ~"в= П(1 — Р;)(! — (1 — Рл,)], п)1. ! о соо = (! Ро) (! Р!) ° ° (1 Р -2) (! Ра) (1 — Р!) (1 Рл-!) Положим рл.
2, Марковские цели 64 или (6.11) Для завершения наших рассуждений полезной окажется следующая Лемм а 6.1. Если 0 < р; < 1 (1 = О, 1, 2, ...), то и = Ц (1-р,)- 0 1=0 при си-асс тогда и только тогда, когда ~ Р, = сс. 1=О Доказательство. Предположим, что ~ р,= сс, Так как 1=О степенное разложение. функции ехр( — р,) представляет собой знакопеременный ряд с уменьшающимися по абсолютной величине членами, то справедливо неравенство 1 — Р;<1 — Р1+ — „— — „+ "=ехр( — Р;), 1'=-О, 1, 2, ... (6.12) Р1 Р; Так как (6.12) выполняется при всех 1', то Ц (1 — р;) <ехр — ~ли р1 . 1-0 1-О Но по предположению 1ип ~з~ р, = сс; следовательно, т -О 1-О 1!гп Ц (1 — р;) = О. 1-О Для доказательства необходимости воспользуемся следующим легко выводимым неравенством: Ц(! — Р,)>(! — р! — Р„,— ...
— Р„), 1=! справедливым при всех 1 и и=!+1, /+2, .... Предположим теперь, что ~ р,<сс; тогда 0< ~ р;<1 при некотором 1. От- 1 1=1 сюда следует, что !пп Ц (1 — рс) > 1!гп (! — ~с'.~ рс >О. тО 1! т.+ 1=/ Это противоречит предположенио о том, что и — О О. И Возвращаясь к (6,11) и применяя лемму 6.1, заключаем, что ~~~~ ~,"а= 1 тогда и только тогда, когда ~О р, = сс, или, что то же и-1 1-О 65 Э" 7. Еже о возвратности самое, состояние 0 возвратно тогда и только тогда, когда ряд ~ р, расходится.