книги из ГПНТБ / Ганин, М. П. Прикладные методы теории марковских случайных процессов учебное пособие
.pdf
ВОЕННО-МОРСКАЯ орденов ЛЕНИНА и УШАКОВА АКАДЕМИЯ
Доктор технических наук профессор М. П. ГАНИН
ПРИКЛАДНЫЕ МЕТОДЫ ТЕОРИИ МАРКОВСКИХ СЛУЧАЙНЫХ ПРОЦЕССОВ
Утверждено начальником Академии в качестве учебного пособия для слушателей Академии
ЛЕНИНГРАД
1 9 7 4
УДК 519.2
В учебном пособии изложены основы теории марковских случайных процессов с дискретными и непрерывными орди натами и с непрерывным временем. Теория марковских про цессов с дискретными ординатами применена для исследова ния некоторых, часто используемых в приложениях случайных процессов. Большое внимание уделено приложениям этой теории для анализа функционирования различных систем массового обслуживания. Когда функционирование системы описывается стохастическим дифференциальным уравнением или системой таких уравнений, используется теория непре рывных марковских случайных процессов. Рассмотрены не которые точные и приближенные методы определения плот ности распределения непрерывного марковского процесса, являющейся решением дифференциального уравнения в част ных производных при соответствующих граничных и началь ном условиях.
Книга может представлять интерес для лиц, занимаю щихся приложениями теории случайных процессов.
Ответственный редактор кандидат технических паук старший научный сотрудник Е. Г. АЛЕКСЕЕВ
Гос.. пуй 'ичная .
иаучн |
- |
'кс.чоская |
бибг |
о . |
•"'.OOP |
|
’Ор'|. |
|
ЧИТЛ;;ЬНОГО ЗАЛА
ПРЕДИСЛОВИЕ
Марковский случайный процесс X(t) — это случайная функция неслучайного аргумента t, которым в большинстве случаев является время. В зависимости от того, как изменяется аргумент t и непре рывной или дискретной случайной величиной является X(t) при фиксированном значении t, различают марковские процессы трех типов. Если аргумент t изменяется скачками и при любом его фик сированном значении X(t) — дискретная случайная величина, то марковский случайный процесс называется цепью Маркова. При кладные методы теории цепей Маркова изложены в работе [7]. Дру гим типом является марковский случайный процесс с дискретными ординатами и непрерывным временем. В этом случае аргумент t может принимать любые неотрицательные значения, a X(t) при любом фиксированном значении t является дискретной случайной /величиной с ограниченным или бесконечным числом возможных значений. Прикладные методы теории марковских случайных про цессов такого типа изложены в гл. 1, где рассмотрены часто исполь зуемые в приложениях частные виды процессов. Марковские слу чайные процессы с дискретными ординатами и непрерывным вре менем широко используются для описания функционирования большого класса систем массового обслуживания. Анализ работы различных систем массового обслуживания произведен в гл. 2. Третьим типом является непрерывный марковский случайный про
цесс. |
В этом случае аргумент t также изменяется непрерывно, |
a X(t) |
при любом фиксированном значении t является непрерывной |
случайной величиной. Процессы такого типа тесно связаны со сто хастическими дифференциальными уравнениями, с помощью кото рых описывается функционирование многих физических систем. Прикладные методы теории непрерывных марковских процессов изложены в гл. 3.
В работе рассмотрены основные методы теории марковских слу чайных процессов, знание которых необходимо при решении при кладных задач. Для облегчения усвоения применяемых методов и иллюстрации возможностей излагаемой теории в работе приведено большое число примеров.
Г Л А В А 1
ПРИКЛАДНЫЕ МЕТОДЫ ТЕОРИИ МАРКОВСКИХ ПРОЦЕССОВ
СДИСКРЕТНЫМИ ОРДИНАТАМИ
ИНЕПРЕРЫВНЫМ ВРЕМЕНЕМ
Вданной главе излагаются основы прикладной теории Марков ских процессов с непрерывным временем и счетным (ограниченным или бесконечным) числом возможных значений. Эта теория широко используется при изучении функционирования различного рода фи зических систем, которые в произвольные моменты времени могут переходить из одного состояния в другое при счетном числе всех возможных состояний. Вероятности перехода находятся как реше ние соответствующей системы обыкновенных дифференциальных уравнений. Излагается общая методика составления этих уравне ний. Решение уравнений произведено для частных типов марков ских процессов с дискретными ординатами п непрерывным време нем. Получены аналитические выражения для вероятностей пере хода и для других вероятностных характеристик, описывающих
поведение процесса в произвольный момент времени. Исследуется характер изменения различных вероятностных характеристик про цесса размножения и гибщш при стационарном режиме функциони рования физической системы.
§1. МАРКОВСКИЙ СЛУЧАЙНЫЙ ПРОЦЕСС
СДИСКРЕТНЫМИ ОРДИНАТАМИ И НЕПРЕРЫВНЫМ ВРЕМЕНЕМ
Случайным процессом (случайной функцией) называется функ ция Х(^), которая при каждом фиксированном значении неслучай ного аргумента t является случайной величиной. В зависимости от того, дискретная или непрерывная эта случайная величина, разли чают два вида случайных процессов.
Если случайная величина дискретная, т. е. если все ее возмож ные значения можно пронумеровать, то X(t) называется случайным процессом с дискретным пространством состояний или, что то же самое, случайным процессом с дискретными ординатами. Указан ные возможные значения случайной величины одни и те -же при
4
любом аргументе t. Эти значения, являющиеся возможными значе ниями случайного процесса X(t), обычно нумеруются в порядке
возрастания и |
записываются в виде х0, Х\, . . . , |
xN, |
где x-i+i > x-s |
(7 = 0, 1, ... , |
N — 1), причем число N может быть ограниченным |
||
или бесконечным. В частном случае, когда Xj = / |
(/ = |
0, 1, .. ., N), |
|
случайный процесс X(t) называется процессом |
с целочисленными |
||
ординатами. |
|
X(t) |
при каждом t |
Если случайная величина непрерывная, т. е. |
|||
может принимать любые значения из заданного промежутка [а, 6], то X(t) называется действительным случайным процессом или слу чайным процессом с непрерывными ординатами.
Вторым признаком, по которому различаются случайные про цессы, является характер изменения неслучайного аргумента /, условно называемого временем. Если данный аргумент принимает
только |
фиксированные |
значения tQ, tu . .. , где, например, ti = j |
(j — 0, |
1, ...), то X(t) |
называется случайным процессом с дискрет |
ным временем. В случае, когда аргумент t может принимать любые значения из заданного промежутка, например 0 t < оо, случай ный процесс X(t) называется процессом с непрерывным временем.
Следующий признак различия случайных процессов — характер зависимости между случайными величинами X(tl),X(t2), .. ., X(tt) ,
которые |
получаются из случайного процесса X(t) при любом |
числе I |
произвольных значений /j, t2, ... , tL аргумента t, где |
ti <. t2 < |
... < i t. Классификация случайных процессов с непрерыв |
ными ординатами по указанной зависимости будет произведена ниже (см. § 27). В данном параграфе рассмотрим три вида случай ных процессов с дискретными ординатами.
Полной характеристикой введенной выше системы -^(М, X(t2), . . . , X(tt) дискретных случайных величин для процесса X(i)
с дискретными ординатами является /-мерный ряд |
распределения, |
||||||
т. е. совокупность вероятностей |
|
|
|
|
|
||
Р \Х (^i) = -*:к,, |
X {t2) — х Кз, . . |
. , |
X (t[) — |
0-1) |
|||
(*j |
= 0 , |
1, .... N; у = 1 , |
2, |
.. ., /), |
|
|
|
сумма которых равна 1. |
|
|
|
|
|
|
|
Когда ординаты X(tj) |
случайного процесса X(t) |
в произвольные |
|||||
моменты времени |
t3(/= 1, 2, ...) |
независимы, вероятность |
(1.1) |
||||
можно представить в виде |
|
|
|
|
|
||
Р (^l) == |
|
X (t ,) = X Kj, . . |
. , |
X (tt) —Л']^| = |
|
||
|
= П Р[Х(^^хч\ |
|
(1.2) |
||||
|
|
j-i |
|
|
|
|
|
(ki = |
. . . . |
Л/; / = 1 , |
2, . . . , |
/; |
/ = 1, 2, |
...). |
|
|
|
|
|
|
|
|
о |
Из (1.2) следует, что для случайного процесса о независимыми ординатами /-мерный ряд распределения при любом / полностью определяется через вероятности отдельных значений, принимаемых функцией X(t) в любой момент времени /. Следовательно, все ве роятностные характеристики этого процесса однозначно выражаются через зависящие от времени t вероятности
P.s( t ) = P [ X ( t ) = Xj] |
(1.3) |
(/ = 0, 1, ... , /V),
причем согласно свойству одномерного ряда распределения
2 ^ ( / ) = 1. |
(1.4) |
j=o |
|
Другим видом является случайный процессе независимыми при ращениями. Для такого процесса независимыми являются случай ные величины
Y0 = X ( t 0), Kj = * ( * , ) - * ( * , _ , ) ( / = 1 , 2 , . . . , / ) ,
где /о — наименьшее значение аргумента /.
Вероятностные характеристики системы независимых случайных величин Во, У\, ..., В; при любом / однозначно выражаются через одномерные ряды распределения этих случайных величин. Так как
X (/j) = Вк, то закон распределения случайной величины X (/,) к= О
получается в результате композиции законов распределения слагае мых. Через одномерные ряды распределения случайных величин Вк могут быть определены любые вероятностные характеристики слу чайного процесса с независимыми приращениями.
Более общим но сравнению с рассмотренными двумя видами случайныхпроцессов является марковский случайный процесс с дискретными ординатами. Для этого процесса вероятность любого возможного исхода хк[ в будущий момент времени tL при условии,
что точно известно значение JCk в текущий момент времени tt_ u
не изменяется при учете дополнительной информации о прошлом данного процесса, т. е. указанная вероятность не зависит от того, какие значения принимала случайная функция X(t) при / < tl_ l . Можно сказать, что для марковского процесса при известном на стоящем будущее не зависит от прошлого или, что то же самое, бу дущее зависит от прошлого только через настоящее. Вследствие указанных свойств марковский случайный процесс называется также процессом без 'последействия или процессом с отсутствием после действия.
6
Условная вероятность
P[X[tl) — x klj X (tl) = x kl>. . . , * ( * , _ i) = Jckj_J |
(1.5) |
того, что в момент tx случайная функция X(i) равна хк[, вычис ленная в предположении, что в предшествующие моменты tu t2, ...
..., tt—\ эта функция была равна соответственно хк,, х кг, . . . , * kl_, .
для |
марковского |
процесса совпадает |
|
с . условной |
вероятностью |
|||||
Р [X(tt) — хк /Х (ti-i) = |
^кг-1] • |
Поэтому для вероятности |
(1.1) |
|||||||
справедливо равенство |
|
|
|
|
|
|
|
|
||
|
Р[Х(^) = |
х К, |
X { t 2) = |
x k„ . |
. |
. , X{tt) = x ^ |
= |
|
||
|
= Р [ Х ^ ) = х к1\ П P\X(tj) = |
xk.IX(tHl) = |
xk._1}. |
(1.6) |
||||||
1меем: |
|
j=2 |
|
|
|
|
|
|
|
|
|
|
P \ X { t ^ ) = xk._{, |
Х { Ц —= X v ,\ |
|||||||
|
|
|
|
|||||||
P |
хц!х У\-\) — ■Kkj.J |
|
p y x { t ^ ) = |
x k |
|
|
||||
|
|
|
|
|
|
|
|
|
|
(1-7) |
^ [^ (^ j_ 1) = xkj _,] = | оП [^ (^ - 1) = |
хк)._1, * ( ^ ) = *,1 . |
(1.8) |
||||||||
Следовательно, |
все |
сомножители |
из |
правой |
части |
равенства |
||||
(1.6) |
однозначно выражаются через вероятности |
Р [X (^_,) = |
д:к._1? |
|||||||
Х (£j) |= xkj] . Последнее означает, что /-мерный ряд распределе ния дгя марковского случайного процесса при любом / однозначно выражается через вероятности двумерного ряда распределения. Так как моменты t\ ( / = 1 , 2, ...) произвольные, то все вероятностные характеристики марковского случайного процесса с дискретными ординатами полностью определяются через следующие функции двух аргументов:
|
■=) = |
•? [*(*) |
= * k, |
A '(t) = |
Xj] |
(1.9) |
: |
(k, |
/ = 0, 1, |
.. ., N), |
|
|
|
где r^\ t. |
|
вероятность того, что в момент t случай |
||||
Обозначим через Рк (/) |
||||||
ная функция А(/) равна хк, т. е. положим |
|
|
|
|||
Pk(t) = |
P[X(t) = xk] |
( k ~ 0 , |
1, . .. , |
N). |
(1.10) |
|
Кроме того, введем функцию Pkr- {t, т), которая является условной вероятностью того, что случайная функция X(t) в момент т > / равна Xj, если в момент t эта функция была равна хк, т. е.
r) = P[X(r) = xilX(t) = xk] |
(1.11) |
7
Так как |
|
ЯЫ(*. ^) = Pk(t)P»{t, *0, |
(1-12) |
то все вероятностные характеристики марковского случайного про цесса с дискретными ординатами однозначно выражаются через функции Pk (t) и Ркj (t, т) (k, j = 0, 1, .. ., N).
Если аргумент t принимает дискретные значения, то марковский случайный процесс с дискретными ординатами называется цепью Маркова. Прикладные вопросы теории цепей Маркова изложены в работе [7] и потому в дальнейшем не рассматриваются. В после дующем будем рассматривать марковский процесс X(t), аргумент t которого может принимать любые неотрицательные значения. Та кой процесс называется марковским случайным процессом с дискрет
ными ординатами и непрерывным временем или цепью |
Маркова |
|||||||||
с непрерывным временем. |
|
|
|
|
|
|
|
|||
Пример 1.1. Доказать, что процесс с независимыми прираще |
||||||||||
ниями марковский. |
|
|
|
|
процесс |
с независимыми |
||||
Решени е . Если X(t) — случайный |
||||||||||
приращениями, то, согласно |
определению, при любых tь t2, .. |
, tt |
||||||||
и наименьшем значении t0 аргумента |
t случайные величины |
Уо = |
||||||||
= X (t0) , |
Yj — X (£j) — X |
(y'=l, |
2, |
... , /) |
независимые. При |
|||||
этом X (to = 2 |
ys (j = |
0, 1, ...). |
|
|
|
|
|
|
||
|
s=0 |
|
|
|
|
|
|
|
т. е. по |
|
Обозначим через Qt условную вероятность вида (1.5), |
||||||||||
ложим |
|
|
|
x K, . |
. . , X ( t l- 1) = |
|
(1.13) |
|||
Ql= P { X ( t l) = |
xkJX(t0) = |
xkl_ i] . |
||||||||
Заменяя в этом равенстве X(t$) |
соответствующими выражениями1 |
|||||||||
через Ys, получаем |
|
|
|
|
|
г-i |
|
|
||
|
|
|
|
|
|
|
|
— |
|
|
|
|
J |
|
Yо |
Yx— x kl, . |
V у |
|
|||
|
|
|
1 s |
— *к,_ |
||||||
|
|
|
|
|
|
|
|
s=0 |
|
|
что можно переписать в виде |
|
|
|
|
|
( U 4 ) |
||||
|
|
|
|
|
|
|
||||
Qi=P\Yi=--x4 - |
xki_JY0: ■ХК, |
|
Y, — хк, —- хК) |
|
|
|||||
|
|
• ■ ■> KI-1 = |
|
- |
хк1_ 2\ . |
|
(1.15) |
|||
Так |
как случайные |
величины |
То, |
Тц ... , Yi |
независимые, то |
|||||
r |
|
Qi = |
P(T,==x kl — x k |
) . |
|
(1.16) |
||||
1огда |
|
|
|
|
|
|
|
|
|
|
|
Р [X (f0) = jck„, |
X (tx)= Xkl, . |
. |
. , X (tO= x4 ] |
= |
|
||||
|
|
= P (^o = * 0 Г [ Р ( У ^ х к. - x k |
). |
(1.17) |
||||||
|
|
|
|
J-i |
|
|
|
|
|
|
8
Аналогично находим
|
P [ X (t l) = |
xklIX(tl_ l) = |
xh_ l1 = |
|
|||||
|
|
|
/ - 1 |
у |
|
|
|
|
|
|
|
Хъ.1 |
V |
: X- |
|
|
|
|
|
= р ( S |
уш |
^_I |
* « |
ч^ ) = Р[У1 = * Ч - * к н ). (U8) |
|||||
К»/ |
s-0 |
|
|
||||||
VS-0 |
|
1‘ |
|
|
|
|
|
|
|
Из сравнения (1.16) |
с |
(1.18) следует, |
что при любом I справед |
||||||
ливо равенство |
|
|
|
|
|
|
|
|
|
Р [X (tt) = xkJX (f0) =з x Ku, X |
(tt) = х 1(„ |
. . |
. , X (*,_,) = |
Х ^ ] = |
|||||
|
= |
^ [^ U i) = |
JCk,/^(^/-i) = |
JCki_ 1] • |
(1.19) |
||||
Следовательно, случайный процесс с независимыми прираще ниями является марковским случайным процессом.
§ 2. ВЕРОЯТНОСТИ ПЕРЕХОДА
Теория марковских случайных процессов с дискретными ордина тами и непрерывным временем широко используется при анализе функционирования различных физических систем, называемых си стемами массового обслуживания. Каждая из таких систем в любой момент времени t находится в одном из N -{- 1 состояний С0, Си ...
••., CN и переходит скачкообразно из одного состояния в другое в произвольные моменты времени. Вероятность нахождения си стемы в любом состоянии в момент т > t зависит только от номера состояния, в котором находилась система в момент t, и не зависит от того, каким образом система пришла в это состояние и сколько времени уже находилась в этом состоянии. Исследование функцио нирования физической системы, условная вероятность перехода ко торой из одного состояния в другое зависит только от двух момен тов времени — настоящего t и будущего т, эквивалентно исследова нию поведения марковского случайного процесса X(t) с дискрет ными ординатами и непрерывным временем. Равенству X(t) = х к при этом ставится в соответствие нахождение физической системы в момент t в состоянии Ck (k = 0, 1, . .. , N). В этом случае гово рят, что марковский случайный процесс с дискретнымиординатами и непрерывным временем «протекает» в физической системе, т. е. марковский процесс описывает изменение состояний этой системы во времени. Следовательно, можно говорить о функционировании физической системы как об изменении марковского случайного про цесса с дискретными ординатами и непрерывным временем и, наобо рот, об изменении марковского случайного процесса как о функцио нировании физической системы, т. е. эти понятия можно отож дествлять.
9