Потоком событий называют последовательность однородных собы­тий, появляющихся одно за другим в случайные моменты времени. При­меры: поток вызовов на телефонной станции; поток сбоев ЭВМ; поток заявок на проведение расчетов в вычислительном центре и т.п.

Поток событий наглядно изображается рядом точек с абсциссами Q 1, Q 2 , ..., Q n , ... (рис. 6.15) с интервалами между ними: Т 1 = Q 2 - Q 1, T 2 = Q 3 -Q 2 , ..., Т п = Q n +1 - Q n . При его вероятностном описании поток событий может быть представлен как последовательность случайных ве­личин:

Q 1 ; Q 2 = Q 1 + T 1 ; Q 3 = Q 1 + T 1 + T 2 ; и т.д.

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

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

Рисунок 6.15 – Реализация потока событий

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

Рисунок 6.16 – Поток событий как случайный процесс

Ординарный поток событий можно интерпретировать как случайный процесс Х(t) - число событий, появившихся до момента t(рис. 6.16). Случайный процесс Х(t) скачкообразно возрастает на одну единицу в точках Q ,Q 2 ,...,Q n .

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

Поток событий называется простейшим, если он стационарен, ордина­рен и не имеет последействия. Интервал времени T между двумя соседними событиями простейшего потока имеет показательное распределение

(при t>0 ); (6.21)

где / М [Т] -величина, обратная среднему значению интервала Т.

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

Марковские случайные процессы . Случайный процесс называют марковским , если он обладает следующим свойством: для любого момента времени t 0 вероят­ность любого состояния системы в будущем (при t >t 0 ) зависит только от ее состояния в настоящем (при t =t 0 ) и не зависит от того, каким обра­зом система пришла в это состояние.

В данной главе будем рассматривать только марковские процессы c дискретными состояниями S 1, S 2 , ...,S n . Такие процессы удобно иллюст­рировать с помощью графа состояний (рис. 5.4), где прямоугольниками (или кружками) обозначены состояния S 1 , S 2 , … системы S, а стрелками - возможные переходы из состояния в состояние (на графе отме­чаются только непосредственные переходы, а не переходы через другие состояния).

Рисунок 5.4 – Граф состояний случайного процесса

Иногда на графе состояний отмечают не только возможные пере­ходы из состояния в состояние, но и возможные задержки в прежнем состоянии; это изображается стрелкой («петлей»), направленной из данного состояния в него же, но можно обходиться и без этого. Число состояний системы может быть как конечным, так и бесконечным (но счетным).

Марковский случайный процесс с дискретными состояниями и дис­кретным временем обычно называют марковской цепью. Для такого про­цесса моменты t 1 , t 2 ..., когда система S может менять свое состояние, удобно рассматривать как последовательные шаги процесса, а в качестве аргумента, от которого зависит процесс, рассматривать не время t, а номер шага: 1, 2, . . ., k;…. Случайный процесс в этом случае характеризуется последовательностью состояний

если S(0) - начальное состояние системы (перед первым шагом); S(1) - состояние системы непосредственно после первого шага; ...; S(k) - со­стояние системы непосредственно после k-го шага....

Событие S i , (i= 1,2,...) является случайным событием, поэтому последо­вательность состояний (5.6) можно рассматривать как последователь­ность случайных событий. Начальное состояние S(0) может быть как заданным заранее, так и случайным. О событиях последовательности (5.6) говорят, что они образуют марковскую цепь.

Рассмотрим процесс с n возможными состояниями S 1, S 2 , ..., S n . Если обозначить через Х(t) номер состояния, в котором находится система S в мо­мент t, то процесс описывается целочисленной случай­ной функцией Х(t)>0 , возможные значения которой равны 1, 2,...,n . Эта функция совершает скачки от одного целочисленного значения к другому в заданные моменты t 1 , t 2 , ... (рис. 5.5) и является непрерывной слева, что отмечено точками на рис. 5.5.

Рисунок 5.5 – График случайного процесса

Рассмотрим одномерный закон распределения случайной функции Х(t). Обозначим через вероятность того, что после k -го шага [и до (k+1 )-го] система S будет в состоянии S i (i=1,2,...,n) . Веро­ятности р i (k) называются вероятностями состояний цепи Маркова. Очевидно, для любого k

. (5.7)

Распределение вероятностей состояний в начале процесса

p 1 (0) ,p 2 (0),…,p i (0),…,p n (0) (5.8)

называется начальным распределением вероятностей марковской цепи. В частности, если начальное состояние S(0) системы S в точности извест­но, например S(0)=S i , то начальная вероятность P i (0) = 1, а все остальные равны нулю.

Вероятностью перехода на k -м шаге из состояния S i в состояние S j называется условная вероятность того, что система после k -го шага окажется в состоянии S j при условии, что непосредственно перед этим (после k - 1 шагов) она находилась в состоянии S i . Вероятности перехода иногда называются также «переходными вероятностями».

Марковская цепь называется однородной, если переходные вероятности не зависят от номера шага, а зависят только от того, из какого состоя­ния и в какое осуществляется переход:

Переходные вероятности однородной марковской цепи Р ij образуют квадратную таблицу (матрицу) размером n * n :

(5.10)

. (5.11)

Матрицу, обладающую таким свойством, называют стохастической. Вероятность Р ij есть не что иное, как вероятность того, что система, при­шедшая к данному шагу в состояние S j , в нем же и задержится на очеред­ном шаге.

Если для однородной цепи Маркова заданы начальное распределение вероятностей (5.8) и матрица переходных вероятностей (5.10), то вероятности состояний системы могут быть опреде­лены по рекуррентной формуле

(5.12)

Для неоднородной цепи Маркова вероятности перехода в матрице (5.10) и формуле (5.12) зависят от номера шага k .

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

При фактических вычислениях по формуле (5.12) надо в ней учитывать не все состояния S j , а только те, для которых переходные вероятности отличны от нуля, т.е. те, из которых на графе состояний ведут стрелки в состояние S i .

Марковский случайный процесс с дискретными состояниями и непрерывным временем иногда называют «непрерывной цепью Маркова» . Для такого процесса вероятность перехода из состояния S i в S j для любого момента времени равна нулю. Вместо вероятности перехода p ij рассматривают плотность вероятности перехода которая определяется как предел отношения вероятности перехода из состояния S i в состояние S j за малый промежуток времени , примыкающий к моменту t, к длине этого промежутка, когда она стремится к нулю. Плотность вероятности перехо­да может быть как постоянной (), так и зависящей от времени . В первом случае марковский случайный процесс с дискретными состояниями и непрерывным временем называется однородным. Типичный пример такого процесса - случайный процесс Х(t), представ­ляющий собой число появившихся до момента t событий в простейшем потоке (рис. 5.2).

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

Рассматривая марковские случайные процессы с дискретными со­стояниями и непрерывным временем, удобно пользоваться гра­фом состояний, на котором против каждой стрелки, ведущей из состоя­ния S i , в S j проставлена интенсивность потока событий, переводящего систему по данной стрелке (рис.5.6). Такой граф состояний называ­ют размеченным.

Вероятность того, что система S, находящаяся в состоянии S i , за эле­ментарный промежуток времени () перейдет в состояние S j (эле­мент вероятности перехода из S i в S j ), есть вероятность того, что за это время dt появится хотя бы одно событие потока, переводящего систему S из S i в S j . С точностью до бесконечно малых высших порядков эта вероятность равна .

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

Рассмотрим случай, когда система S имеет конечное число состояний S 1, S 2 ,..., S п. Для описания случайного процесса, протекающего в этой системе, применяются вероятности состояний

(5.13)

где р i (t) - вероятность того, что система S в момент t находится в состоя­нии S i:

. (5.14)

Очевидно, для любого t

Для нахождения вероятностей (5.13) нужно решить систему диф­ференциальных уравнений (уравнений Колмогорова), имеющих вид

(i=1,2,…,n),

или, опуская аргумент t у переменных р i ,

(i=1,2,…,n ). (5.16)

Напомним, что интенсивности потоков ij могут зависеть от времени .

Уравнения (5.16) удобно составлять, пользуясь размеченным гра­фом состояний системы и следующим мнемоническим правилом: произ­водная вероятности каждого состояния равна сумме всех потоков веро­ятности, переводящих из других состояний в данное, минус сумма всех потоков вероятности, переводящих из данного состояния в другие. Напри­мер, для системы S, размеченный граф состояний которой дан на рис. 10.6, система уравнений Колмогорова имеет вид

(5.17)

Так как для любого t выполняется условие (5.15), можно любую из вероятностей (5.13) выразить через остальные и таким образом уменьшить число уравнений на одно.

Чтобы решить систему дифференциальных уравнений (5.16) для вероятностей состояний р 1 (t) p 2 (t ), …, p n (t ), нужно задать начальное распределение вероятностей

p 1 (0),p 2 (0), …,p i (0), …,p n (0 ), (5.18)

сумма которых равна единице.

Если, в частности, в начальный момент t = 0 состояние системы S в точности известно, например, S(0) =S i , и р i (0) = 1, то остальные вероятноcти выражения (5.18) равны нулю.

Во многих случаях, когда процесс, протекающий в системе, длится достаточно долго, возникает вопрос о предельном поведении ве­роятностей р i (t) при . Если все потоки событий, переводящие систему из состояния в состояние, являются простейшими (т.е. стацио­нарными пуассоновскими с постоянными интенсивностями ), в неко­торых случаях существуют финальные (или предельные) вероятности со­стояний

, (5.19)

независящие от того, в каком состоянии система S находилась в началь­ный момент. Это означает, что с течением времени в системе S устанавли­вается предельный стационарный режим, в ходе которого она переходит из состояния в состояние, но вероятности состояний уже не меняются. В этом предельном режиме каждая финальная вероятность может быть истолкована как среднее относительное время пребывания системы в дан­ном состоянии.

Систему, в которой существуют финальные вероятности, называют эргодической. Если система S имеет конечное число состояний S 1 , S 2 , . . . , S n , то для су­ществования финальных вероятностей достаточно, чтобы из любого со­стояния системы можно было (за какое-то число шагов) перейти в любое другое. Если число состояний S 1 , S 2 , . . . , S n , бесконечно, то это условие перестает быть достаточным, и существование финальных вероятностей зависит не только от графа состояний, но и от интенсивностей .

Финальные вероятности состояний (если они существуют) могут быть получены решением системы линейных алгебраических уравнений, они получаются из дифференциальных уравнений Колмогорова, если по­ложить в них левые части (производные) равными нулю. Однако удобнее составлять эти уравнения непосредственно по графу состояний, пользу­ясь мнемоническим правилом: для каждого состояния суммарный выхо­дящий поток вероятности равен суммарному входящему. Например, для системы S, размеченный граф состояний которой дан на р ис. 5.7, уравнения для финальных вероятностей состояний имеют вид

(5.20)

Таким образом, получается (для системы S с п состояниями) система n однород­ных линейных алгебраических уравнений с n неизвест­ными р 1, р 2 , ..., р п. Из этой системы можно найти неизвестные р 1 , р 2 , . . . , р п с точностью до произвольного множителя. Чтобы найти точные значения р 1 ,..., р п, к уравнениям добавляют нормировочное условие p 1 + p 2 + … + p п =1, пользуясь которым можно выразить любую из ве­роятностей p i через другие (и соответственно отбросить одно из уравне­ний).

Вопросы для повторения

1 Что называют случайной функцией, случайным процессом, сечением случайного процесса, его реализацией?

2 Как различаются случайные процессы по своей структуре и характеру протекания во времени?

3 Какие законы распределения случайной функции применяют для описания случайной функции?

4 Что представляет собой функция математического ожидания случайной функции, в чем ее геометрический смысл?

5 Что представляет собой функция дисперсии случайной функции, в чем ее геометрический смысл?

6 Что представляет собой корреляционная функция случайного процесса, и что она характеризует?

7 Каковы свойства корреляционной функции случайного процесса?

8 Для чего введено понятие нормированной корреляционной функции?

9 Объясните как по опытным данным получить оценки функций характеристик случайного процесса?

10 В чем отличие взаимной корреляционной функции от автокорреляционной функции?

11 Какой случайный процесс относят к стационарным процессам в узком смысле и в широком?

12 В чем заключается свойство эргодичности стационарного случайного процесса?

13 Что понимают под спектральным разложением стационарного случайного процесса и в чем его необходимость?

14 Какова связь между корреляционной функцией и спектральной плотностью стационарной случайной функции?

15 Что называют простейшим потоком событий?

16 Какой случайный процесс называют марковской цепью? В чем заключается методика расчета ее состояний?

17 Что представляет собой марковский случайный процесс с дискретными состояниями и непрерывным временем?

M(U)=10, D(U)=0.2 .

6.5 Найти нормированную взаимную корреляционную функцию случайных функций X(t)=t*U и Y(t)=(t+1)U , где U – случайная величина, причем дисперсия D(U)=10 .

МАРКОВСКИЙ ПРОЦЕСС

Процесс без последействия, - случайный процесс , эволюция к-рого после любого заданного значения временного параметра tне зависит от эволюции, предшествовавшей t, при условии, что значение процесса в этот фиксировано (короче: "будущее" н "прошлое" процесса не зависят друг от друга при известном "настоящем").

Определяющее М. п. свойство принято наз. марковским; впервые оно было сформулировано А. А. Марковым . Однако уже в работе Л. Башелье можно усмотреть попытку трактовать броуновское как М. п., попытку, получившую обоснование после исследований Н. Винера (N. Wiener, 1923). Основы общей теории М. п. с непрерывным временем были заложены А. Н. Колмогоровым .

Марковское свойство. Имеются существенно отличающиеся друг от друга определения М. п. Одним из наиболее распространенных является следующее. Пусть на вероятностном пространстве задан случайный процесс со значениями из измеримого пространства где Т - подмножество действительной оси Пусть N t (соответственно N t ).есть s-алгебра в порожденная величинами X(s).при где Другими словами, N t (соответственно N t ) - это совокупность событий, связанных с эволюцией процесса до момента t(начиная с t). Процесс X(t).наз. марковским процессом, если (почти наверное) для всех выполняется марковское свойство:

или, что то же самое, если для любых

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

В дальнейшем для определенности речь будет идти только о случае Формулы (1) и (2) дают ясную интерпретацию принципа независимости "прошлого" и "будущего" при известном "настоящем", но основанное на них определение М. п. оказалось недостаточно гибким в тех многочисленных ситуациях, когда приходится рассматривать не одно, а набор условий типа (1) или (2), отвечающих различным, хотя и согласованным определенным образом, мерам Такого рода соображения привели к принятию следующего определения (см. , ).

Пусть заданы:

а) где s-алгебра содержит все одноточечные множества в Е;

б) измеримое снабженное семейством s-алгебр таких, что если

в) (" ") x t =x t (w), определяющая при любых измеримое отображение

г) для каждых и вероятностная мера на s-алгебре такая, что функция измерима относительно если и

Набор наз. (необрывающимся) марковским процессом, заданным в если -почти наверное

каковы бы ни были Здесь - пространство элементарных событий, - фазовое пространство или пространство состояний, Р(s, x, t, В ) - переходная функция или вероятность перехода процесса X(t). Если Енаделено топологией, а - совокупность борелевских множеств в Е, то принято говорить, что М. п. задан в Е. Обычно в определение М. п. включают требование, чтобы и тогда истолковывается как вероятность при условии, что x s =x.

Возникает вопрос: всякую ли марковскую переходную функцию Р(s, x ; t, В ), заданную в измеримом пространстве можно рассматривать как переходную функцию нек-рого М. п. Ответ положителен, если, напр., Еявляется сепарабельным локально компактным пространством, а - совокупностью борелевских множеств в Е. Более того, пусть Е - полное метрич. пространство и пусть

для любого где
а - дополнение e-окрестности точки х. Тогда соответствующий М. п. можно считать непрерывным справа и имеющим пределы слева (т. е. таковыми можно выбрать его траектории). Существование же непрерывного М. п. обеспечивается условием при (см. , ). В теории М. п. основное внимание уделяется однородным (по времени) процессам. Соответствующее определение предполагает заданной систему объектов а) - г) с той разницей, что для фигурировавших в ее описании параметров sи u теперь допускается лишь значение 0. Упрощаются и обозначения:

Далее, постулируется однородность пространства W, т. е. требуется, чтобы для любых существовало такое что (w) при Благодаря этому на s-алгебре N, наименьшей из s-алгебр в W, содержащих любое событие вида задаются операторы временного сдвига q t , к-рые сохраняют операции объединения, пересечения и вычитания множеств и для к-рых

Набор наз. (необрывающимся) однородным марковским процессом, заданным в если -почти наверное

для Переходной функцией процесса X(t).считается Р(t, x, В ), причем, если нет специальных оговорок, дополнительно требуют, чтобы Полезно иметь в виду, что при проверке (4) достаточно рассматривать лишь множества вида где и что в (4) всегда F t можно заменить s-алгеброй , равной пересечению пополнений F t по всевозможным мерам Нередко в фиксируют вероятностную меру m ("начальное ") и рассматривают марковскую случайную функцию где - мера на заданная равенством

М. п. наз. прогрессивно измеримым, если при каждом t>0 функция индуцирует измеримое в где есть s-алгебра

борелевских подмножеств в . Непрерывные справа М. п. прогрессивно измеримы. Существует способ сводить неоднородный случай к однородному (см. ), и в дальнейшем речь будет идти об однородных М. п.

Строго . Пусть в измеримом пространстве задан М. п.

Функция наз. марковским моментом, если для всех При этом относят к семейству F t , если при (чаще всего F t интерпретируют как совокупность событий, связанных с эволюцией X(t).до момента т). Для полагают

Прогрессивно измеримый М. п. Xназ. строго марковским процессом (с. м. п.), если для любого марковского момента т и всех и соотношение

(строго марковское свойство) выполняется -почти наверное на множестве W t . При проверке (5) достаточно рассматривать лишь множества вида где в этом случае С. м. п. является, напр., любой непрерывный справа феллеровский М. п. в топологич. пространстве Е. М. п. наз. феллеровским марковским процессом, если функция

непрерывна всякий раз, когда f непрерывна и ограничена.

В классе с. м. п. выделяются те или иные подклассы. Пусть марковская Р(t, x, В ), заданная в метрическом локально компактном пространстве Е, стохастически непрерывна:

для любой окрестности Uкаждой точки Тогда если операторы переводят в себя непрерывных и обращающихся в 0 в бесконечности функций, то функции Р(t, х, В ).отвечает стандартный М. п. X, т. е. непрерывный справа с. м. п., для к-рого

и - почти наверное на множестве а - неубывающие с ростом пмарковские моменты.

Обрывающийся марковский процесс. Нередко физич. системы целесообразно описывать с помощью необрывающегося М. п., но лишь на временном интервале случайной длины. Кроме того, даже простые преобразования М. п. могут привести к процессу с траекториями, заданными на случайном интервале (см. Функционал от марковского процесса). Руководствуясь этими соображениями, вводят понятие обрывающегося М. п.

Пусть - однородный М. п. в фазовом пространстве имеющий переходную функцию и пусть существуют точка и функция такие, что при и в противном случае (если нет специальных оговорок, считают ). Новая траектория x t (w) задается лишь для ) посредством равенства a F t определяется как в множестве

Набор где наз. обрывающимся марковским процессом (о. м. п.), полученным из с помощью обрыва (или убивания) в момент z. Величина z наз. моментом обрыва, или временем жизни, о. м. п. Фазовым пространством нового процесса служит где есть след s-алгебры в Е. Переходная функция о. м. п.- это сужение на множество Процесс X(t).наз. строго марковским процессом, или стандартным марковским процессом, если соответствующим свойством обладает Необрывающийся М. п. можно рассматривать как о. м. п. с моментом обрыва Неоднородный о. м. п. определяется аналогичным образом. М.

Марковские процессы и . М. п. типа броуновского движения тесно связаны с дифференциальными уравнениями параболич. типа. Переходная р(s, x, t, у ).диффузионного процесса удовлетворяет при нек-рых дополнительных предположениях обратному и прямому дифференциальным уравнениям Колмогорова:

Функция р(s, x, t, у ).есть функция Грина уравнений (6) - (7), и первые известные способы построения диффузионных процессов были основаны на теоремах существования этой функции для дифференциальных уравнений (6) - (7). Для однородного по времени процесса L(s, x ) = L (x).на гладких функциях совпадает с характеристич. оператором М. п. (см. Переходных операторов полугруппа ).

Математич. ожидания различных функционалов от диффузионных процессов служат решениями соответствующих краевых задач для дифференциального уравнения (1). Пусть - математич. ожидание по мере Тогда функция удовлетворяет при s уравнению (6) и условию

Аналогично, функция

удовлетворяет при s уравнению

и условию и 2 ( Т, x ) = 0.

Пусть тt - момент первого достижения границы дD области траекторией процесса Тогда при нек-рых условиях функция

удовлетворяет уравнению

и принимает значения ср на множестве

Решение 1-й краевой задачи для общего линейного параболич. уравнения 2-го порядка

при довольно общих предположениях может быть записано в виде

В случае, когда Lи функции с, f не зависят от s, аналогичное (9) представление возможно и для решения линейного эллиптич. уравнения. Точнее, функция

при нек-рых предположениях есть задачи

В случае, когдгг оператор Lвырождается (del b(s, х ) = 0 ).или дD недостаточно "хорошая", граничные значения могут и не приниматься функциями (9), (10) в отдельных точках или на целых множествах. Понятие регулярной граничной точки для оператора L имеет вероятностную интерпретацию. В регулярных точках границы граничные значения достигаются функциями (9), (10). Решение задач (8), (11) позволяет изучать свойства соответствующих диффузионных процессов и функционалов от них.

Существуют методы построения М. п., не опирающиеся на построение решений уравнений (6), (7), напр. метод стохастических дифференциальных уравнений, абсолютно непрерывная замена меры и др. Это обстоятельство вместе с формулами (9), (10) позволяет вероятностным путем строить и изучать свойства краевых задач для уравнения (8), а также свойства решении соответствующего эллиптич. уравнения.

Так как решение стохастического дифференциального уравнения нечувствительно к вырождению матрицы b(s, x ), то вероятностные методы применялись для построения решений вырождающихся эллиптических и параболических дифференциальных уравнений. Распространение принципа усреднения Н. М. Крылова и Н. Н. Боголюбова на стохастические дифференциальные уравнения позволило с помощью (9) получить соответствующие результаты для эллиптических и параболических дифференциальных уравнений. Нек-рые трудные задачи исследования свойств решений уравнений такого типа с малым параметром при старшей производной оказалось возможным решить с помощью вероятностных соображений. Вероятностный смысл имеет и решение 2-й краевой задачи для уравнения (6). Постановка краевых задач для неограниченной области тесно связана с возвратностью соответствующего диффузионного процесса.

В случае однородного по времени процесса (Lне зависит от s) положительное решение уравнения с точностью до мультипликативной постоянной совпадает при нек-рых предположениях со стационарной плотностью распределения М. п. Вероятностные соображения оказываются полезными и при рассмотрении краевых задач для нелинейных параболич. уравнений. Р. 3. Хасьминский.

Лит. : Марков А. А., "Изв. физ.-мат. об-ва Казан. ун-та", 1906, т. 15, №4, с. 135-56; В а с h e l i е r L., "Ann. scient. Ecole norm, super.", 1900, v. 17, p. 21-86; Колмогоров А. Н., "Math. Ann.", 1931, Bd 104, S. 415- 458; рус. пер.-"Успехи матем. наук", 1938, в. 5, с. 5-41; Ч ж у н К а й - л а й, Однородные цепи Маркова, пер. с англ., М., 1964; Р е 1 1 е r W., "Ann. Math.", 1954, v. 60, p. 417-36; Д ы н к и н Е. Б., Ю ш к е в и ч А. А., "Теория вероятн. и ее примен.", 1956, т. 1, в. 1, с. 149-55; X а н т Дж.-А., Марковские процессы и потенциалы, пер. с англ., М., 1962; Д е л л а ш е р и К., Емкости и случайные процессы, пер. с франц., М., 1975; Д ы н к и н Е. В., Основания теории марковских процессов, М., 1959; его же, Марковские процессы, М., 1963; Г и х м а н И. И., С к о р о х о д А. В., Теория случайных процессов, т. 2, М., 1973; Фрейдлин М. И., в кн.: Итоги науки. Теория вероятностей, - важный специальный вид случайных процессов. Примером марковского процесса может служить распад радиоактивного вещества, где вероятность распада данного атома за малый промежуток времени не зависит от течения процесса в предшествующий период.… … Большой Энциклопедический словарь

Марковский процесс случайный процесс, эволюция которого после любого заданного значения временного параметра не зависит от эволюции, предшествовавшей, при условии, что значение процесса в этот момент фиксировано («будущее» процесса не… … Википедия

Марковский процесс - 36. Марковский процесс Примечания: 1. Условную плотность вероятности называют плотностью вероятности перехода из состояния xn 1в момент времени tn 1 в состояние хпв момент времени tn. Через нее выражаются плотности вероятностей произвольного… … Словарь-справочник терминов нормативно-технической документации

марковский процесс - Markovo procesas statusas T sritis automatika atitikmenys: angl. Markovprocess vok. Markovprozeß, m rus. марковский процесс, m; процесс Маркова, m pranc. processus markovien, m … Automatikos terminų žodynas

марковский процесс - Markovo vyksmas statusas T sritis fizika atitikmenys: angl. Markov process; Markovian process vok. Markow Prozeß, m; Markowscher Prozeß, m rus. марковский процесс, m; процесс Маркова, m pranc. processus de Markoff, m; processus marcovien, m;… … Fizikos terminų žodynas

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

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

Выдающееся открытие в области математики, сделанное в 1906 русским ученым А.А. Марковым.

Лекция 9

Марковские процессы
Лекция 9
Марковские процессы



1

Марковские процессы

Марковские процессы
Случайный процесс, протекающий в системе, называется
марковским, если он обладает отсутствием последствия. Т.е.
если рассматривать текущее состояние процесса (t 0) - как
настоящее, совокупность возможных состояний { (s),s t} - как
прошлое, совокупность возможных состояний { (u),u t} - как
будущее, то для марковского процесса при фиксированном
настоящем будущее не зависит от прошлого, а определяется
лишь настоящим и не зависит от того, когда и как система
пришла в это состояние.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
2

Марковские процессы

Марковские процессы
Марковские случайные процессы названы по имени выдающегося русского математика А.А.Маркова, впервые начавшего изучение вероятностной связи случайных величин
и создавшего теорию, которую можно назвать "динамикой
вероятностей". В дальнейшем основы этой теории явились
исходной базой общей теории случайных процессов, а также таких важных прикладных наук, как теория диффузионных процессов, теория надежности, теория массового обслуживания и т.д.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
3

Марков Андрей Андреевич Марков Андрей Андреевич Марков Андрей Андреевич

Марковские процессы
Марков Андрей Андреевич
1856-1922
Русский математик.
Написал около 70 работ по
теории
чисел,
теории
приближения функций, теории
вероятностей. Существенно расширил сферу применения закона
больших чисел и центральной
предельной теоремы. Является
основоположником теории случайных процессов.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
4

Марковские процессы

Марковские процессы
На практике марковские процессы в чистом виде обычно
не встречаются. Но имеются процессы, для которых влиянием «предыстории» можно пренебречь, и при изучении
таких процессов можно применять марковские модели. В
настоящее время теория марковских процессов и ее приложения широко применяются в самых различных областях.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
5

Марковские процессы

Марковские процессы
Биология: процессы рождения и гибели - популяции, мутации,
эпидемии.
Физика:
радиоактивные
распады,
теория
счетчиков
элементарных частиц, процессы диффузии.
Химия:
теория
следов
в
ядерных
фотоэмульсиях,
вероятностные модели химической кинетики.
Images.jpg
Астрономия: теория флуктуационной
яркости млечного пути.
Теория массового обслуживания: телефонные станции,
ремонтные мастерские, билетные кассы, справочные бюро,
станочные и другие технологические системы, системы управления
гибких производственных систем, обработка информации серверами.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
6

Марковские процессы

Марковские процессы
Пусть в настоящий момент t0 система находится в
определенном состоянии S0. Мы знаем характеристики
состояния системы в настоящем и все, что было при t < t0
(предысторию процесса). Можем ли мы предсказать будущее,
т.е. что будет при t > t0?
В точности – нет, но какие-то вероятностные характеристики
процесса в будущем найти можно. Например, вероятность того,
что через некоторое время
система S окажется в состоянии
S1 или останется в состоянии S0 и т.д.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
7

Марковские процессы. Пример.

Марковские процессы
Марковские процессы. Пример.
Система S – группа самолетов, участвующих в воздушном бою. Пусть x – количество
«красных» самолетов, y – количество «синих» самолетов. К моменту времени t0 количество сохранившихся (не сбитых) самолетов
соответственно – x0, y0.
Нас интересует вероятность того, что в момент времени
t 0 численный перевес будет на стороне «красных». Эта вероятность зависит от того, в каком состоянии находилась система
в момент времени t0, а не от того, когда и в какой последовательности погибали сбитые до момента t0 самолеты.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
8

Дискретные цепи Маркова

Марковские процессы
Дискретные цепи Маркова
Марковский процесс с конечным или счетным числом
состояний и моментов времени называется дискретной
цепью Маркова. Переходы из состояния в состояние возможны только в целочисленные моменты времени.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
9

10. Дискретные цепи Маркова. Пример

Марковские процессы

Предположим,
что
речь
идет
о
последовательных бросаниях монеты при
игре "в орлянку"; монета бросается в
условные моменты времени t =0, 1, ... и на
каждом шаге игрок может выиграть ±1 с
одинаковой
вероятностью
1/2,
таким
образом в момент t его суммарный выигрыш есть случайная величина ξ(t) с возможными значениями j = 0, ±1, ... .
При условии, что ξ(t) = k, на следующем шаге выигрыш будет
уже равен ξ(t+1) = k ± 1, принимая значения j = k ± 1 c одинаковой вероятностью 1/2. Можно сказать, что здесь с соответствующей вероятностью происходит переход из состояния ξ(t) = k в состояние ξ(t+1) = k ± 1.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
10

11. Дискретные цепи Маркова

Марковские процессы
Дискретные цепи Маркова
Обобщая этот пример, можно представить себе систему со
счетным числом возможных состояний, которая с течением
дискретного времени t = 0, 1, ... случайно переходит из состояния в состояние.
Пусть ξ(t) есть ее положение в момент t в результате цепочки случайных переходов
ξ(0) -> ξ(1) -> ... -> ξ(t) -> ξ(t+1) ->...-> ... .
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
11

12. Дискретные цепи Маркова

Марковские процессы
Дискретные цепи Маркова
При анализе случайных процессов с дискретными состояниями удобно пользоваться геометрической схемой – графом
состояний. Вершины графа – состояния системы. Дуги графа
– возможные переходы из состояния в состояние.
Игра «в орлянку».
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
12

13. Дискретные цепи Маркова

Марковские процессы
Дискретные цепи Маркова
Обозначим все возможные состояния целыми i = 0, ±1, ...
Предположим, что при известном состоянии ξ(t) =i на следующем шаге система переходит в состояние ξ(t+1) = j с условной вероятностью
P{ (t 1) j (t) i}
независимо от ее поведения в прошлом, точнее, независимо
от цепочки переходов до момента t:
P{ (t 1) j (t) i; (t 1) it 1;...; (0) i0 }
P{ (t 1) j (t) i}
Это свойство называется марковским.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
13

14. Дискретные цепи Маркова

Марковские процессы
Дискретные цепи Маркова
Число
pij P{ (t 1) j (t) i}
называется вероятностью
перехода системы из состояния i в состояние j за один шаг в
момент времени t 1.
Если переходная вероятность не зависит от t , то цепь
Маркова называется однородной.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
14

15. Дискретные цепи Маркова

Марковские процессы
Дискретные цепи Маркова
Матрица P , элементами которой являются вероятности
перехода pij , называется переходной матрицей:
p11 ... p1n
P p 21 ... p 2n
p
n1 ... p nn
Она является стохастической, т.е.
pij 1 ;
i
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
p ij 0 .
15

16. Дискретные цепи Маркова. Пример

Марковские процессы
Дискретные цепи Маркова. Пример
Матрица переходов для игры «в орлянку»
...
k 2
k 2
0
k 1
1/ 2
k
0
k 1
k
k 1
k 2
0
1/ 2
0
0
1/ 2
0
1/ 2
0
1/ 2
0
0
0
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
...
k 1 k 2
0
0
0
1/ 2
0
1/ 2
...
0
0
1/ 2
0
16

17. Дискретные цепи Маркова. Пример

Марковские процессы
Дискретные цепи Маркова. Пример
Садовник в результате химического анализа почвы оценивает
ее состояние одним из трех чисел - хорошее (1), удовлетворительное (2) или плохое (3). В результате наблюдений на протяжении многих лет садовник заметил,
что продуктивность почвы в текущем
году зависит только от ее состояния в
предыдущем году. Поэтому вероятности
перехода почвы из одного состояния в
другое можно представить следующей
цепью Маркова с матрицей P1:
0.20 0.50 0.30
0.00 0.50 0.50
0.00 0.00 1.00
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
17

18. Дискретные цепи Маркова. Пример

Марковские процессы
Дискретные цепи Маркова. Пример
Однако в результате агротехнических мероприятий садовник может изменить переходные вероятности в матрице P1.
Тогда матрица P1 заменится
на матрицу P2:
0.30 0.60 0.10
0.10 0.60 0.30
0.05 0.40 0.55
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
18

19. Дискретные цепи Маркова

Марковские процессы
Дискретные цепи Маркова
Рассмотрим, как изменяются состояния процесса с течением времени. Будем рассматривать процесс в последовательные моменты времени, начиная с момента 0. Зададим начальное распределение вероятностей p(0) { p1 (0),..., pm (0)} , где m число состояний процесса, pi (0) - вероятность нахождения
процесса в состоянии i в начальный момент времени. Вероятность pi (n) называется безусловной вероятностью состояния
i в момент времени n 1.
Компоненты вектора p (n) показывают, какие из возможных состояний цепи в момент времени n являются наиболее
вероятными.
m
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
pk (n) 1
k 1
19

20. Дискретные цепи Маркова

Марковские процессы
Дискретные цепи Маркова
Знание последовательности { p (n)} при n 1,... позволяет составить представление о поведении системы во времени.
В системе с 3-мя состояниями
p11 p12 p13
P p21
p
31
p22
p32
p23
p33
p2 (1) p1 (0) p12 p2 (0) p22 p3 (0) p32
p2 (n 1) p1 (n) p12 p2 (n) p22 p3 (n) p32
В общем случае:
p j (1) pk (0) pkj
p j (n 1) pk (n) pkj
k
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
k
p(n 1) p(n) P
20

21. Дискретные цепи Маркова. Пример

Марковские процессы
Дискретные цепи Маркова. Пример
Матрица
0.20 0.50 0.30
0.00 0.50 0.50
0.00 0.00 1.00
Шаг
{ p (n)}
n
0
1, 0, 0
n
1
0.2 , 0.5 , 0.3
n
2
0.04 , 0.35 , 0.61
n
3
0.008 , 0.195 , 0.797
n
4
0.0016 , 0.1015 , 0.8969
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
21

22. Дискретные цепи Маркова

Марковские процессы
Дискретные цепи Маркова
n
Матрица перехода за n шагов P(n) P .
0.20 0.50 0.30
0.00 0.50 0.50
0.00 0.00 1.00
p(2) p(0) P
2
p (2)
P(2) P 2
1, 0, 0
0.0016
0.
0.
0.0016
0.
0.
0.1015
0.0625
0.
0.1015
0.0625
0.
0.8969
0.9375
1.
0.8969
0.9375
1.
0.04 , 0.35 , 0.61
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
22

23. Дискретные цепи Маркова

Марковские процессы
Дискретные цепи Маркова
Как ведут себя марковские цепи при n ?
Для однородной марковской цепи при определенных условиях выполняется следующее свойство: p (n) при n .
Вероятности 0 не зависят от начального распределения
p(0) , а определяются только матрицей P . В этом случае называется стационарным распределением, а сама цепь – эргодической. Свойство эргодичности означает, что по мере увеличения n
вероятность состояний практически перестаёт изменяться, а система переходит в стабильный режим функционирования.
i
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
23

24. Дискретные цепи Маркова. Пример

Марковские процессы
Дискретные цепи Маркова. Пример
0.20 0.50 0.30
0.00 0.50 0.50
0.00 0.00 1.00
0 0 1
P() 0 0 1
0 0 1
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
p () (0,0,1)
24

25. Дискретные цепи Маркова. Пример

Марковские процессы
Дискретные цепи Маркова. Пример
0.30 0.60 0.10
0.10 0.60 0.30
0.05 0.40 0.55
0.1017 0.5254 0.3729
P() 0.1017 0.5254 0.3729
0.1017 0.5254 0.3729
p () (0.1017,0.5254,0.3729)
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
25

26. Марковские процессы с непрерывным временем

Марковские процессы

Процесс называется процессом с непрерывным временем, если
моменты возможных переходов из состояния в состояние не фиксированы заранее, а неопределенны, случайны и могут произойти
в любой момент.
Пример. Технологическая система S состоит из двух устройств,
каждое из которых в случайный момент времени может выйти из
строя, после чего мгновенно начинается ремонт узла, тоже продолжающийся заранее неизвестное, случайное время.
Возможны следующие состояния системы:
S0 - оба устройства исправны;
S1 - первое устройство ремонтируется, второе исправно;
S2 - второе устройство ремонтируется, первое исправно;
S3 - оба устройства ремонтируются.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
26

27. Марковские процессы с непрерывным временем

Марковские процессы
Марковские процессы с непрерывным временем
Переходы системы S из состояния в состояние происходят
практически мгновенно, в случайные моменты выхода из строя
того или иного устройства или
окончания ремонта.
Вероятностью одновременного
выхода из строя обоих устройств
можно пренебречь.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
27

28. Потоки событий

Марковские процессы
Потоки событий
Поток событий – последовательность однородных событий, следующих одно за другим в какие-то случайные моменты времени.
– это среднее число событий,
Интенсивность потока событий
приходящееся на единицу времени.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
28

29. Потоки событий

Марковские процессы
Потоки событий
Поток событий называется стационарным, если его вероятностные характеристики не зависят от времени.
В частности, интенсивность
стационарного потока постоянна. Поток событий неизбежно имеет сгущения или разрежения, но они не носят закономерного характера, и среднее число событий, приходящееся на единицу времени, постоянно и от времени не зависит.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
29

30. Потоки событий

Марковские процессы
Потоки событий
Поток событий называется потоком без последствий, если для
любых двух непересекающихся участков времени и число событий, попадающих на один из них, не зависит от того, сколько событий попало на другой. Другими словами, это означает, что события, образующие поток, появляются в те или иные моменты
времени независимо друг от друга и вызваны каждое своими собственными причинами.
Поток событий называется ординарным, если вероятность появления на элементарном участке t двух и более событий пренебрежимо мала по сравнению с вероятностью появления одного
события, т.е. события в нем появляются поодиночке, а не группами по нескольку сразу
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
30

31. Потоки событий

Марковские процессы
Потоки событий
Поток событий называется простейшим (или стационарным пуассоновским), если он обладает сразу тремя свойствами: 1) стационарен, 2) ординарен, 3) не имеет последствий.
Простейший поток имеет наиболее простое математическое описание. Он играет среди потоков такую же особую
роль, как и закон нормального распределения среди других
законов распределения. А именно, при наложении достаточно большого числа независимых, стационарных и ординарных
потоков (сравнимых между собой по интенсивности) получается поток, близкий к простейшему.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
31

32. Потоки событий

Марковские процессы
Потоки событий
Для простейшего потока с интенсивностью
интервал
времени T между соседними событиями имеет показательное
распределение с плотностью
p(x) e x , x 0 .
Для случайной величины T, имеющей показательное распределение, математическое ожидание есть величина, обратная параметру.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
32

33. Марковские процессы с непрерывным временем

Марковские процессы
Марковские процессы с непрерывным временем
Рассматривая процессы с дискретными состояниями и непрерывным временем, можно считать, что все переходы системы S из состояния в состояние происходят под действием
простейших потоков событий (потоков вызовов, потоков отказов, потоков восстановлений и т.д.).
Если все потоки событий, переводящие систему S из состояния в состояние простейшие, то процесс, протекающий в
системе, будет марковским.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
33

34. Марковские процессы с непрерывным временем

Марковские процессы
Марковские процессы с непрерывным временем
Пусть на систему, находящуюся в состоянии, действует
простейший поток событий. Как только появится первое событие этого потока, происходит «перескок» системы из состояния
в состояние.
- интенсивность потока событий, переводящий систему
из состояния
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
в
.
34

35. Марковские процессы с непрерывным временем

Марковские процессы
Марковские процессы с непрерывным временем
Пусть рассматриваемая система S имеет
возможных состояний
. Вероятность p ij (t) является вероятностью перехода из состояния i в состояние j за время t.
Вероятность i - го состояния
- это вероятность того,
что в момент времени t система будет находиться в состоянии
. Очевидно, что для любого момента времени сумма
всех вероятностей состояний равна единице:
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
35

36. Марковские процессы с непрерывным временем

Марковские процессы
Марковские процессы с непрерывным временем
Для нахождения всех вероятностей состояний
как
функций времени составляются и решаются дифференциальные уравнения Колмогорова – особого вида уравнения, в которых неизвестными функциями являются вероятности состояний.
Для переходных вероятностей:
p ij (t) p ik (t) kj
k
Для безусловных вероятностей:
p j (t) p k (t) kj
k
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
36

37. Колмогоров Андрей Николаевич

Марковские процессы
Колмогоров Андрей Николаевич
1903-1987
Великий русский
математик.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
37

38. Марковские процессы с непрерывным временем

Марковские процессы
Марковские процессы с непрерывным временем
- интенсивности потока отказов;
- интенсивности потока восстановлений.
Пусть система находится в состоянии
S0. В состояние S1 ее переводит поток
отказов первого устройства. Его интенсивность равна
где
- среднее время безотказной работы устройства.
Из состояния S1 в S0 систему переводит поток восстановлений
первого устройства. Его интенсивность равна
где
- среднее время ремонта первого станка.
Аналогично вычисляются интенсивности потоков событий, переводящих систему по всем дугам графа.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
38

39. Системы массового обслуживания

Марковские процессы

Примеры систем массового обслуживания (СМО): телефонные станции, ремонтные мастерские,
билетные
кассы,
справочные
бюро,
станочные и другие технологические системы,
системы
управления
гибких
производственных систем,
обработка информации серверами и т.д.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
39

40. Системы массового обслуживания

Марковские процессы
Системы массового обслуживания
СМО состоит из какого – то количества обслуживающих
единиц, которые называются каналами обслуживания (это
станки, роботы, линии связи, кассиры и т.д.). Всякая СМО
предназначена для обслуживания потока заявок (требований), поступающих в случайные моменты времени.
Обслуживание заявки продолжается случайное время, после чего канал освобождается и готов к приему следующей
заявки.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
40

41. Системы массового обслуживания

Марковские процессы
Системы массового обслуживания
Процесс работы СМО – случайный процесс с дискретными
состояниями и непрерывным временем. Состояние СМО меняется скачком в моменты появления каких - то событий
(прихода новой заявки, окончания обслуживания, момента,
когда заявка, которой надоело ждать, покидает очередь).
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
41

42. Системы массового обслуживания

Марковские процессы
Системы массового обслуживания
Классификация систем массового обслуживания
1. СМО с отказами;
2. СМО с очередью.
В СМО с отказами заявка, поступившая в момент, когда все каналы заняты, получает отказ, покидает СМО и в дальнейшем не
обслуживается.
В СМО с очередью заявка, пришедшая в момент, когда все каналы заняты, не уходит, а становится в очередь и ожидает возможности быть обслуженной.
СМО с очередями подразделяются на разные виды в зависимости
от того, как организована очередь – ограничена или не ограничена. Ограничения могут касаться как длины очереди, так и времени
ожидания, «дисциплины обслуживания».
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
42

43. Системы массового обслуживания

Марковские процессы
Системы массового обслуживания
Предмет теории массового обслуживания – построение
математических моделей, связывающих заданные условия
работы СМО (число каналов, их производительность, правила
работы, характер потока заявок) с интересующими нас характеристиками – показателями эффективности СМО. Эти показатели описывают способность СМО справляться с потоком
заявок. Ими могут быть: среднее число заявок, обслуживаемых СМО в единицу времени; среднее число занятых каналов; среднее число заявок в очереди; среднее время ожидания обслуживания и т.д.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
43

44.

СПАСИБО
ЗА ВНИМАНИЕ!!!
44

45. Построить граф переходов

Марковские процессы
Построить граф переходов
0.30
0.70
0.0
0.10
0.60
0.30
0.50
0.50
0.0
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»

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

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

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

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

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

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

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

Ниже представлены два примера матриц переходных вероятностей.

Матрицы переходных вероятностей можно изобразить графами переходных состояний, как показано на рисунке.

Пример

Предприятие выпускает продукт, насытивший рынок. Если предприятие от реализации продукта в текущем месяце получит прибыль (П), то с вероятностью 0,7 получит прибыль и в следующем месяце, а с вероятностью 0,3 – убыток. Если в текущем месяце предприятие получит убыток (У), то с вероятностью 0,4 в следующем месяце оно получит прибыль, а с вероятностью 0,6 – убыток (вероятностные оценки получены в результате опроса экспертов). Рассчитать вероятностную оценку получения прибыли от реализации товара через два месяца работы предприятия.

В матричной форме эта информация будет выражена следующим образом (что соответствует примеру матрицы 1):

Первая итерация – построение матрицы двухступенчатых переходов.

Если предприятие в текущем месяце получит прибыль, то вероятность того, что в следующем месяце оно снова получит прибыль, равна

Если предприятие в текущем месяце получит прибыль, то вероятность того, что в следующем месяце оно получит убыток, равна

Если предприятие в текущем месяце получит убыток, то вероятность того, что в следующем месяце оно получит прибыль, равна

Если предприятие в текущем месяце получит убыток, то вероятность того, что в следующем месяце оно вновь получит убыток, равна

В результате расчетов получаем матрицу двухступенчатых переходов:

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

Для проведения этих процедур в среде Excel необходимо выполнить следующие действия:

• 1) формировать матрицу;
• 2) вызывать функцию МУМНОЖ;
• 3) указывать первый массив – матрицу;
• 4) указывать второй массив (эта же матрица или другая);
• 5) ОК;
• 6) выделить зону новой матрицы;
• 7) F2;
• 8) Ctrl+Shift+Enter;
• 9) получить новую матрицу.

Вторая итерация – построение матрицы трехступенчатых переходов. Аналогично рассчитываются вероятности получения прибыли или убытка на следующем шаге и рассчитывается матрица трехступенчатых переходов, она имеет следующий вид:

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

Случайный процесс X (t), tÎT называется марковским, если любых t l < t 2 < ... < t n , принадлежащих области Т, условная функция распределения случайной величины X(t n) относительно X(t 1), . . ., X(t n -1) совпадает с условной функцией распределения X(t n) относительно X(t n -1) в том смысле, что для любого x n ÎX справедливо равенство

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

Аналогично свойство марковости (3.1.1), (3.1.2) может быть записано и для плотностей вероятности

Таким образом, для марковского процесса функция распреде­ления или плотность вероятности любой мерности n может быть найдена, если известна его одномерная плотность вероятности при t = t 1 и последовательность условных плотностей для моментов t i >t 1 , i = .Эта особенность по существу и определяет практи­ческое удобство аппарата марковских случайных процессов.

Для марковских процессов полностью справедлива общая клас­сификация, приведенная в параграфе 1.1. В соответствии с этой классификацией обычно выделяется четыре основных вида про­цессов Маркова :

- цепи Маркова - процессы, у которых как область значе­ний X, так и область определения Т - дискретные множества;

- марковские последовательности - процессы, у которых об­ласть значений X - непрерывное, а область определения Т -дис­кретное множество;

- дискретные марковские процессы - процессы, у которых область значений X - дискретное, а область определения Т - не­прерывное множество;

- непрерывнозначные марковские процессы - процессы, у ко­торых как область значений X, так и область определения Т - непрерывные множества.

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

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

ЦЕПИ МАРКОВА

Пусть случайный процесс X (t) может принимать конечное (L < ) множество значений

{q l , l = } = С. Конкретное зна­чениеq l ; Î С, которое принял процесс X (t) в момент t, определя­ет его состояние при данном значении аргумента. Таким образом,

в рассматриваемом случае процесс X (t) имеет конечное мно­жество возможных состояний.

Естественно, что с течением времени процесс X (t) будет слу­чайным образом изменять свое состояние. Допустим, что такое изменение возможно не при любом t, а лишь в некоторые дискрет­ные моменты времени t 0 X (t) скачком изменяет свое состояние. Иначе говоря, в моменты времени t t имеют место переходы X(t 0) ®X(t 1) ® ..., причем X(t)Î C, i = 0,1,2,…

Два указанных признака определяют последовательность ди­скретных случайных величин X i - X (t i), i = 0.1, ... (дискретную случайную последовательность в терминах, параграфа 1.1), у ко­торой область значений представляет собой дискретное конечное множество С ={q l , l = ], а область определения - дискрет­ное бесконечное множество t i , i = 0,1, 2,...

Если для определенной таким образом дискретной случайной последовательности справедливо основное свойство (3.1.1) про­цессов Маркова, приобретающее в данном случае вид

то такая последовательность называется простой цепью Маркова.

Отметим, что из выражения (3.2.1) непосредственно вытекает

такое же равенство и для условных вероятностей нахождения

простой цепи Маркова в некотором состоянии

Р{х 1 /х 0 ,х 1 , ...,x i -1 } = Ρ{x i /x i -1 }, i = 1,2,....

Введенное определение допускает некоторое обобщение. По­ложим, что значение х i Î С рассматриваемого процесса X (t) за­висит не от одного, а от m(l£ m < i ) непосредственно предшест­вующих ему значений. Тогда, очевидно, что

Процесс, определяемый соотношением (3.2.2), называется сложной цепью Маркова порядка т. Соотношение (3.2.1) выте­кает из (3.2.2) как частный случай. В свою очередь, сложная цепь Маркова порядка т может быть сведена к простой цепи Маркова для m-мерного вектора. Для того чтобы показать это, положим, что состояние процесса в момент i i описывается с помощью m-мерного вектора.

(3.2.3)

На предыдущем шаге аналогичный вектор запишется как

Сравнение (3.2.3) и (3.2.4) показывает, что «средние» компо­ненты этих векторов (кроме X l в (3.2.3) и Х l - m в (3.2.4)) совпадают. Отсюда следует, что условная вероятность попадания про­цесса X (t) в состояние `X i в момент t 1 , если он находился в состоя­нии `X i -1 в момент t i -1 , может быть записана в виде

В (3.2.5) символ обозначает j-ю компоненту вектора `x i ; α (μ, ν) - символ Кронекера: α(μ, ν) = 1 при ν = μ и α(μ, ν) = ϋ при μ ¹ν. Возможность указанных обобщений позволяет ограничить­ся в дальнейшем рассмотрением только простых цепей Маркова.

Как система дискретных случайных величин простая цепь Мар­кова X i , i = 0, 1, 2, ... ,i, ... при любом фиксированном i может быть исчерпывающим образом описана i-мерной совместной вероят­ностью

ρ {θ 0 L , θ ίκ ,... , θ ί m ,} = P{Х 0 =θ L ,X 1 =θ k ,…,X j =θ m }, (3.2.6)

где индексы l , k,..., т принимают все значения от 1 до L неза­висимо друг от друга. Выражение (3.2.6) определяет матрицу с L строками и i+1 столбцом, элементами которой являются вероят­ности совместного пребывания системы случайных величин Χ 0 ,Χ 1 ,...,Χ ί в некотором конкретном состоянии. Данная матрица по аналогии с рядом распределения скалярной дискретной слу­чайной величины может быть названа матрицей распределения системы дискретных случайных величин

Χ 0 ,Χ 1 ,...,Χ ί .

На основании теоремы умножения вероятностей вероятность (3.2.6) может быть представлена в виде

Но согласно основному свойству (3.2.1) цепи Маркова

P{X l = m/X 0 = l ,X 1 = k ,…,X i -1 = r }=P{X i = m /X i -1 = r }

Повторение аналогичных рассуждений для входящей в (3.2.8) вероятности r } позволяет привести это выра­жение к виду

Отсюда окончательно получаем

(3.2.9)

Таким образом, полное вероятностное описание простой цепи Маркова достигается заданием вероятностей начального состояния цепи в момент t 0 , Ρ{Θ 0 l ,} = Р{Х 0 = Θ l }, l= и условных вероятностей

Ρ {X l = Θ k /X i-1 = Θ m }, i = 1 , 2, . .. · k, m =

Отметим, что поскольку возможные состояния Θ l Î`C цепи X (t) фиксированы и известны, для описания ее состояния в лю­бой момент времени достаточно указать номер l этого состояния. Это позволяет ввести для безусловных вероятностей нахождения цепи в l -м состоянии в момент t i (на i -м шаге) упрощенное обоз­начение

Для этих вероятностей, очевидно, имеют место свойства неот­рицательности и нормированности к единице

P l (i )>0,l = , i = 0, 1,2,...; (3.2.11)

При использовании матричных обозначений совокупность без­условных вероятностей записывается в виде матрицы-строки

(3.2.12)

Как следует из ранее изложенного, фундаментальную роль в теории цепей Маркова (и процессов Маркова вообще) играют ус­ловные вероятности вида В соответствии с физическим смыслом их принято называть вероятностями пере­хода и обозначать как

Выражение (3.2.13) определяет вероятность прихода цепи в состояние l , в момент t за ν - μ шагов при условии, что в момент t μ цепь находилась в состоянии A . Нетрудно видеть, что для вероятностей перехода также имеют место свойства не­отрицательности и нормированности, поскольку на любом шаге цепь всегда будет находиться в одном из L возможных состояний

(3.2.14)

Упорядоченная совокупность вероятностей перехода для любой пары может быть представлена в виде квадратной мат­рицы

(3.2.15)

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

Таким образом, вероятностное описание цепи Маркова может быть задано матрицей-строкой (3.2.12) и стохастической матри­цей (3.2.15).

С использованием введенных обозначений решим основную задачу теории цепей Маркова - определим безусловную вероят­ность Ρ l (ί) того, что за i -μ шагов процесс придет в некото­рое состояние l , l = . Очевидно, что в момент t m процесс может находиться в любом из L возможных состояний с вероятностью P k (m), k = . Вероятность же перехода из k-гo в l -е состояние задается вероятностью перехода p k l (m,i) . Отсюда на основании теоремы о полной вероятности получаем

; (3.2.16)

или в матричной форме

P(i )=P(m)P(m,i ); (3.2.17)

Рассмотрим в соотношении (3.2.16) вероятность перехода π kl (m,i ). Очевидно, что переход цепи из состояния k в момент t m в состояние l в момент t i за несколько шагов может осущест­вляться различными путями (через различные промежуточные со­стояния). Введем в рассмотрение промежуточный момент времени t m , t m Β этот момент процесс может находиться в любом из L возможных состояний, причем вероятность его попадания в r-е состояние в момент t m при условии, что в момент t m он был в состоянии k, равна π kr (μ,m). В свою очередь, из состояния r в состояние l процесс переходит с вероятностью π rl (m,i ). Отсю­да с использованием теоремы о полной вероятности получаем уравнение Маркова для вероятностей перехода

матричная форма которого имеет вид

П(m, ί) = П(μ, m) П(m,I) ; 0£m < m < I; (3.2.19)

Уравнения (3.2.18), (3.2.19) определяют характерное для це­пей Маркова свойство вероятностей перехода, хотя справедливос­ти (3.2.18) еще недостаточно, чтобы соответствующая цепь была марковской.

Расписывая последовательно формулу (3.2.19), получаем

П(μ, i ) = П (μ, i - 1) П (i - 1, ί) = П (μ, μ + 1) ... П (ί - 1, i ), (3.2.20)

где p(ν, μ), μ -n= 1- одношаговая вероятность перехода. Полагая теперь в выражении (3.2.17) μ =0, получаем

(3.2.21)

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

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

p kl (m,i ) =p kl (i-m) ,i>m>0; (3.2.22)

и не зависят от номера шага. Все остальные виды простых цепей Маркова, не удовлетворяющие условию (3.2.22), относятся к клас­су неоднородных,.

Поскольку для однородной цепи вероятность перехода опре­деляется лишь разностью аргументов и не зависит от номера ша­га, очевидно, что для произвольных пар (μ,m), (j ,i ), удовлетво­ряющих условиям т - μ = 1, ί- j = 1, m¹i, справедливо

p kl (m-m) =p kl (i-j)= p kl (1) =p kl ;

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

(3.2.23)

Кроме того, очевидно, что

(3.4.7)

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

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

Подставив выражение (3.4.9) в (3.4.8), разделив обе части полученного выражения на ∆t и перейдя к пределу при Δt → 0, получим

Уравнение (3.4.10) определяет широкий класс непрерывных марковских процессов, причем нетрудно видеть, что совокупность коэффициентов А ν (x 0 ,t 0) определяет физические свойства каждо­го из них. Так, коэффициент A 1 (x 0 , t 0) может трактоваться как среднее значение локальной (в точке x (t 0)) скорости изменения процесса, коэффициент A 2 (x 0 , t 0) - как локальная скорость изме­нения дисперсии его приращения и т. д. Однако марковские про­цессы такого общего вида сравнительно редко рассматриваются в приложениях. Наибольшее практическое значение имеет под­множество марковских процессов, удовлетворяющее условию

A ν (x 0 , t 0)¹0; n=1,2, A ν (x 0 , t 0)=0, n³3; (3.4.12)

При исследовании марковских процессов первоначально было установлено, что уравнению (3.4.10) при условии (3.4.12) удовле­творяют законы движения (диффузии) броуновских частиц, вслед­ствие чего соответствующие марковские процессы назвали диф­фузионными. Исходя из этого, коэффициент A 1 (x 0 , t 0)=a (x 0 , t 0) назвали коэффициентом сноса, о A 2 (x 0 , t 0)=b(x 0 , t 0) -- коэффици­ентом диффузии. В рамках (3.4.12) уравнение (3.4.10) приобре­тает окончательный вид

Это уравнение, в котором переменными являются х 0 и t 0 , носит название первого (обратного) уравнения Колмогорова.

Аналогичным образом может быть получено и второе урав­нение

Это уравнение, в честь впервые исследовавших его ученых, называется уравнением Фоккера, - Планка - Колмогорова или прямым уравнением Колмогорова (поскольку в нем фигурирует производ­ная по конечному моменту времени t>t 0).

Таким образом; показано, что плотности вероятности перехода диффузионных марковских процессов удовлетворяют уравнениям (3.4.13), (3.4.14), которые и являются основным инструментом их исследования. При этом- свойства конкретного процесса опреде­ляются «коэффициентами» a(x,tί) и b(x,t) которые, согласно уравнения (3.4.11), равны

Из выражений (3.4.15), (3.4.16) следует, что эти «коэффици­енты» имеют смысл условных математических ожиданий, опре­деляющих характер изменений реализаций процесса за бесконеч­но малый промежуток времени Δt. Допускаются весьма быстрые изменения процесса X (t) , но в противоположных направлениях, в результате чего среднее приращение процесса за малое время Δt конечно и имеет порядок .