Допущения о пуассоновском характере потока заявок и о показательном распределении времени обслуживания ценны тем, что позволяют применить в теории массового обслуживания аппарат так называемых марковских случайных процессов.
Процесс, протекающий в физической системе, называется марковским (или процессом без последействия), если для каждого момента времени вероятность любого состояния системы в будущем зависит только от состояния системы в настоящий момент и не зависит от того, каким образом система пришла в это состояние.
Рассмотрим элементарный пример марковского случайного процесса. По оси абсцисс случайным образом перемещается точка . В момент времени точка находится в начале координат и остается там в течение одной секунды. Через секунду бросается монета; если выпал герб - точка перемещается на одну единицу длины вправо, если цифра - влево. Через секунду снова бросается монета и производится такое же случайное перемещение, и т. д. Процесс изменения положения точки (или, как говорят, «блуждания») представляет собой случайный процесс с дискретным временем и счетным множеством состояний
Схема возможных переходов для этого процесса показана на рис. 19.7.1.
Покажем, что этот процесс - марковский. Действительно, представим себе, что в какой-то момент времени система находится, например, в состоянии - на одну единицу правее начала координат. Возможные положения точки через единицу времени будут и с вероятностями 1/2 и 1/2; через две единицы - , , с вероятностями 1/4, ½, 1/4 и так далее. Очевидно, все эти вероятности зависят только от того, где находится точка в данный момент , и совершенно не зависят от того, как она пришла туда.
Рассмотрим другой пример. Имеется техническое устройство , состоящее из элементов (деталей) типов и , обладающих разной долговечностью. Эти элементы в случайные моменты времени и независимо друг от друга могут выходить из строя. Исправная работа каждого элемента безусловно необходима для работы устройства в целом. Время безотказной работы элемента - случайная величина, распределенная по показательному закону; для элементов типа и параметры этого закона различны и равны соответственно и . В случае отказа устройства немедленно принимаются меры для выявления причин и обнаруженный неисправный элемент немедленно заменяется новым. Время, потребное для восстановления (ремонта) устройства, распределено по показательному закону с параметром (если вышел из строя элемент типа ) и (если вышел из строя элемент типа ).
В данном примере случайный процесс, протекающий в системе, есть марковский процесс с непрерывным временем и конечным множеством состояний:
Все элементы исправны, система работает,
Неисправен элемент типа , система ремонтируется,
Неисправен элемент типа , система ремонтируется.
Схема возможных переходов дана на рис. 19.7.2.
Действительно, процесс обладает марковским свойством. Пусть например, в момент система находится в состоянии (исправна). Так как время безотказной работы каждого элемента - показательное, то момент отказа каждого элемента в будущем не зависит от того, сколько времени он уже работал (когда поставлен). Поэтому вероятность того, что в будущем система останется в состоянии или уйдет из него, не зависит от «предыстории» процесса. Предположим теперь, что в момент система находится в состоянии (неисправен элемент типа ). Так как время ремонта тоже показательное, вероятность окончания ремонта в любое время после не зависит от того, когда начался ремонт и когда были поставлены остальные (исправные) элементы. Таким образом, процесс является марковским.
Заметим, что показательное распределение времени работы элемента и показательное распределение времени ремонта - существенные условия, без которых процесс не был бы марковским. Действительно, предположим, что время исправной работы элемента распределено не по показательному закону, а по какому-нибудь другому - например, по закону равномерной плотности на участке . Это значит, что каждый элемент с гарантией работает время , а на участке от до может выйти из строя в любой момент с одинаковой плотностью вероятности. Предположим, что в какой-то момент времени элемент работает исправно. Очевидно, вероятность того, что элемент выйдет из строя на каком-то участке времени в будущем, зависит от того, насколько давно поставлен элемент, т. е. зависит от предыстории, и процесс не будет марковским.
Аналогично обстоит дело и с временем ремонта ; если оно не показательное и элемент в момент ремонтируется, то оставшееся время ремонта зависит от того, когда он начался; процесс снова не будет марковским.
Вообще показательное распределение играет особую роль в теории марковских случайных процессов с непрерывным временем. Легко убедиться, что в стационарном марковском процессе время, в течение которого система остается в каком-либо состоянии, распределено всегда по показательному закону (с параметром, зависящим, вообще говоря, от этого состояния). Действительно, предположим, что в момент система находится в состоянии и до этого уже находилась в нем какое-то время. Согласно определению марковского процесса, вероятность любого события в будущем не зависит от предыстории; в частности, вероятность того, что система уйдет из состояния в течение времени , не должна зависеть от того, сколько времени система уже провела в этом состоянии. Следовательно, время пребывания системы в состоянии должно быть распределено по показательному закону.
В случае, когда процесс, протекающий в физической системе со счетным множеством состояний и непрерывным временем, является марковским, можно описать этот процесс с помощью обыкновенных дифференциальных уравнений, в которых неизвестными функциями являются вероятности состояний . Составление и решение таких уравнений мы продемонстрируем в следующем на примере простейшей системы массового обслуживания.
МАРКОВСКИЙ ПРОЦЕСС
Процесс без последействия, - случайный процесс ,
эволюция к-рого после любого заданного значения временного параметра 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
Аналогично, функция
удовлетворяет при 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; Фрейдлин М. И., в кн.: Итоги науки. Теория вероятностей, . - Теоретическая . 1966, М., 1967, с. 7-58; X а с ь м и н с к и й Р. 3., "Теория вероятн. и ее примен.", 1963, т. 8, в
Марковский процесс - дискретный или непрерывный случайный процесс X(t) , который можно полностью задать с помощью двух величин: вероятности P(x,t) того, что случайная величина x(t) в момент времени t равна x и вероятности P(x2, t2½x1t1) того, что… … Экономико-математический словарь
Марковский процесс - Дискретный или непрерывный случайный процесс X(t) , который можно полностью задать с помощью двух величин: вероятности P(x,t) того, что случайная величина x(t) в момент времени t равна x и вероятности P(x2, t2?x1t1) того, что если x при t = t1… … Справочник технического переводчика
Важный специальный вид случайных процессов. Примером марковского процесса может служить распад радиоактивного вещества, где вероятность распада данного атома за малый промежуток времени не зависит от течения процесса в предшествующий период.… … Большой Энциклопедический словарь - 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 русским ученым А.А. Марковым.
Структура и классификация систем массового обслуживания
Системы массового обслуживания
Нередко возникает необходимость в решении вероятностных задач, связанных с системами массового обслуживания (СМО), примерами которых могут быть:
Билетные кассы;
Ремонтные мастерские;
Торговые, транспортные, энергетические системы;
Системы связи;
Общность таких систем выявляется в единстве математических методов и моделей, применяемых при исследовании их деятельности.
Рис. 4.1. Основные сферы применения ТМО
На вход в СМО поступает поток требований на обслуживание. Например, клиенты или пациенты, поломки в оборудовании, телефонные вызовы. Требования поступают нерегулярно, в случайные моменты времени. Случайный характер носит и продолжительность обслуживания. Это создает нерегулярность в работе СМО, служит причиной ее перегрузок и недогрузок.
Системы массового обслуживания обладают различной структурой, но обычно в них можно выделить четыре основных элемента :
1. Входящий поток требований.
2. Накопитель (очередь).
3. Приборы (каналы обслуживания).
4. Выходящий поток.
Рис. 4.2. Общая схема систем массового обслуживания
Рис. 4.3. Модель работы системы
(стрелками показаны моменты поступления требований в
систему, прямоугольниками – время обслуживания)
На рис.4.3 а представлена модель работы системы с регулярным потоком требований. Поскольку известен промежуток между поступлениями требований, то время обслуживания выбрано так, чтобы полностью загрузить систему. Для системы со стохастическим потоком требований ситуация совершенно иная – требования приходят в различные моменты времени и время обслуживания тоже является случайной величиной, которое может быть описано неким законом распределения (рис.4.3 б).
В зависимости от правил образования очереди различают следующие СМО:
1) системы с отказами , в которых при занятости всех каналов обслуживания заявка покидает систему необслуженной;
2) системы с неограниченной очередью , в которых заявка встает в очередь, если в момент ее поступления все каналы обслуживания были заняты;
3) системы с ожиданием и ограниченной очередью , в которых время ожидания ограниченно какими-либо условиями или существуют ограничения на число заявок, стоящих в очереди.
Рассмотрим характеристики входящего потока требований.
Поток требований называется стационарным , если вероятность попадания того или иного числа событий на участок времени определенной длины зависит только от длины этого участка.
Поток событий называется потоком без последствий , если число событий, попадающих на некоторый участок времени, не зависит от числа событий, попадающих на другие.
Поток событий называется ординарным , если невозможно одновременное поступление двух или более событий.
Поток требований называется пуассоновским (или простейшим), если он обладает тремя свойствами: стационарен, ординарен и не имеет последствий. Название связано с тем, что при выполнении указанных условий число событий, попадающих на любой фиксированный интервал времени, будет распределен по закону Пуассона.
Интенсивностью потока заявок λ называется среднее число заявок, поступающих из потока за единицу времени.
Для стационарного потока интенсивность постоянна. Если τ – среднее значение интервала времени между двумя соседними заявками, то В случае пуассоновского потока вероятность поступления на обслуживание m заявок за промежуток времени t определяется по закону Пуассона:
Время между соседними заявками распределено по экспоненциальному закону с плотностью вероятности
Время обслуживания является случайной величиной и подчиняется показательному закону распределения с плотностью вероятности 
где μ – интенсивность потока обслуживания, т.е. среднее число заявок, обслуживаемых в единицу времени,
Отношение интенсивности входящего потока к интенсивности потока обслуживания называется загрузкой системы
Система массового обслуживания представляет собой систему дискретного типа с конечным или счетным множеством состояний, а переход системы из одного состояния в другое происходит скачком, когда осуществляется какое-нибудь событие.
Процесс называется процессом с дискретными состояниями , если его возможные состояния можно заранее перенумеровать, и переход системы из состояния в состояние происходит практически мгновенно.
Такие процессы бывают двух типов: с дискретным или непрерывным временем.
В случае дискретного времени переходы из состояния в состояние могут происходить в строго определенные моменты времени. Процессы с непрерывным временем отличаются тем, что переход системы в новое состояние возможен в любой момент времени.
Случайным процессом называется соответствие, при котором каждому значению аргумента (в данном случае – моменту из промежутка времени проводимого опыта) ставится в соответствие случайная величина (в данном случае – состояние СМО). Случайной величиной называется величина, которая в результате опыта может принять одно, но неизвестное заранее, какое именно, числовое значение из данного числового множества.
Поэтому для решения задач теории массового обслуживания необходимо этот случайный процесс изучить, т.е. построить и проанализировать его математическую модель.
Случайный процесс называется марковским , если для любого момента времени вероятностные характеристики процесса в будущем зависят только от его состояния в данный момент и не зависят от того, когда и как система пришла в это состояние.
Переходы системы из состояния в состояние происходит под действием каких-то потоков (поток заявок, поток отказов). Если все потоки событий, приводящие систему в новое состояние, – простейшие пуассоновские, то процесс, протекающий в системе, будет марковским, так как простейший поток не обладает последствием: в нем будущее не зависит от прошлого.
Эволюция которого после любого заданного значения временно́го параметра t {\displaystyle t} не зависит от эволюции, предшествовавшей t {\displaystyle t} , при условии, что значение процесса в этот момент фиксировано («будущее» процесса не зависит от «прошлого» при известном «настоящем»; другая трактовка (Вентцель): «будущее» процесса зависит от «прошлого» лишь через «настоящее»).
Энциклопедичный YouTube
1 / 3
✪ Лекция 15: Марковские случайные процессы
✪ Происхождение марковских цепей
✪ Обобщенная модель марковского процесса
Субтитры
История
Определяющее марковский процесс свойство принято называть марковским; впервые оно было сформулировано А. А. Марковым , который в работах 1907 г. положил начало изучению последовательностей зависимых испытаний и связанных с ними сумм случайных величин. Это направление исследований известно под названием теории цепей Маркова .
Основы общей теории марковских процессов с непрерывным временем были заложены Колмогоровым .
Марковское свойство
Общий случай
Пусть
(Ω
,
F
,
P)
{\displaystyle (\Omega ,{\mathcal {F}},\mathbb {P})}
- вероятностное пространство с фильтрацией
(F
t
,
t
∈
T)
{\displaystyle ({\mathcal {F}}_{t},\ t\in T)}
по некоторому (частично упорядоченному) множеству
T
{\displaystyle T}
; и пусть
(S
,
S)
{\displaystyle (S,{\mathcal {S}})}
- измеримое пространство . Случайный процесс
X
=
(X
t
,
t
∈
T)
{\displaystyle X=(X_{t},\ t\in T)}
, определённый на фильтрованном вероятностном пространстве, считается удовлетворяющим марковскому свойству
, если для каждого
A
∈
S
{\displaystyle A\in {\mathcal {S}}}
и
s
,
t
∈
T:
s
<
t
{\displaystyle s,t\in T:s
Марковский процесс - это случайный процесс, удовлетворяющий марковскому свойству с естественной фильтрацией .
Для марковских цепей с дискретным временем
В случае, если S {\displaystyle S} является дискретным множеством и T = N {\displaystyle T=\mathbb {N} } , определение может быть переформулировано:
P (X n = x n | X n − 1 = x n − 1 , X n − 2 = x n − 2 , … , X 0 = x 0) = P (X n = x n | X n − 1 = x n − 1) {\displaystyle \mathbb {P} (X_{n}=x_{n}|X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots ,X_{0}=x_{0})=\mathbb {P} (X_{n}=x_{n}|X_{n-1}=x_{n-1})} .Пример марковского процесса
Рассмотрим простой пример марковского случайного процесса. По оси абсцисс случайным образом перемещается точка. В момент времени ноль точка находится в начале координат и остается там в течение одной секунды. Через секунду бросается монета - если выпал герб, то точка X перемещается на одну единицу длины вправо, если цифра - влево. Через секунду снова бросается монета и производится такое же случайное перемещение, и так далее. Процесс изменения положения точки («блуждания ») представляет собой случайный процесс с дискретным временем (t=0, 1, 2, …) и счетным множеством состояний. Такой случайный процесс называется марковским, так как следующее состояние точки зависит только от настоящего (текущего) состояния и не зависит от прошлых состояний (неважно, каким путём и за какое время точка попала в текущую координату).
Под случайным процессом понимают изменение во времени состояний некоторой физической системы заранее неизвестным случайным образом. При этом под физической системой будем понимать любое техническое устройство, группу устройств, предприятие, отрасль, биологическую систему и т.д.
Случайный процесс протекающий в системе называется Марковским – если для любого момента времени ,вероятностные характеристики процесса в будущем (t > ) зависят только от его состояния в данный момент времени (в настоящем ) и не зависят от того, когда и как система пришла в это состояние в прошлом .(Например, счетчик Гейгера, регистрирующий число космических частиц).
Марковские процессы принято делить на 3 вида:
1. Марковская цепь – процесс, состояния которого дискретны (т.е. их можно перенумеровать), и время, по которому он рассматривается, также дискретно (т.е. процесс может менять свои состояния только в определенные моменты времени). Такой процесс идет (изменяется) по шагам (иначе - по тактам).
2. Дискретный марковский процесс – множество состояний дискретно (можно перечислить), а время непрерывно (переход из одного состояния в другое – в любой момент времени).
3. Непрерывный марковский процесс – множество состояний и время -непрерывные.
На практике Марковские процессы в чистом виде встречаются не часто. Однако нередко приходится иметь место с процессами, для которых влиянием предыстории можно пренебречь. Кроме того, если все параметры из «прошлого»,от которых зависит «будущее» включить в состоянии системы в «настоящем», то ее также можно рассматривать как Марковскую. Однако это часто приводит к значительному росту числа учитываемых переменных и невозможности получить решение задачи.
В исследование операций большое значение занимают так называемые Марковские случайные процессы с дискретными состояниями и непрерывным временем .
Процесс называется процессом с дискретными состояниями , если все его возможные состояния , ,... можно заранее перечислить (перенумеровать). Переход системы из состояния в состояние переходит практически мгновенно –скачком.
Процесс называется процессом с непрерывным временем , если моменты перехода из состояния в состояние могут принимать любые случайные значения на временной оси.
Например : Техническое устройство S состоит из двух узлов , каждый из которых в случайный момент времени может выйти из строя (отказать ). После этого мгновенно начинается ремонт узла (восстановление ),который продолжается случайное время.
Возможны следующие состояния системы:
Оба узла исправны;
Первый узел ремонтируется,второй исправен.
– второй узел ремонтируется,первый исправен
Оба узла ремонтируются.
Переход системы из состояния в состояние происходит в случайные моменты времени практически мгновенно. Состояния системы и связь между ними удобно отобразить с помощью графа состояний .
Состояния
Переходы
Переходы и отсутствуют т.к. отказы и восстановления элементов происходят независимо и случайно и вероятность одновременного выхода из строя (восстановления) двух элементов бесконечно мала и ею можно пренебречь.
Если все потоки событий, переводящие систему S из состояния в состояние –простейшие , то процесс, протекающий в такой системе будетМарковским . Это обуславливается тем, что простейший поток не обладает последействием, т.е. в нем «будущее» не зависит от «прошлого» и, кроме того, он обладает свойством ординарности – вероятность одновременного появления двух и более событий бесконечно мала, т.е невозможен переход из состояния в состояние, минуя несколько промежуточных состояний.
Для наглядности на графе состояний удобно у каждой стрелки перехода проставить интенсивность того потока событий, который переводит систему из состояния в состояние по данной стрелке ( -интенсивность потока событий, переводящего систему из состояния в . Такой граф называется размеченным.
Используя размеченный граф состояний системы можно построить математическую модель данного процесса.
Рассмотрим переходы системы из некоторого состояния в предыдущее или последующее . Фрагмент графа состояний в этом случае будет выглядеть следующим образом:
Пусть система в момент времени t находится в состоянии .
Обозначим (t)- вероятность i-ого состояния системы – вероятность того, что система в момент времени t находится в состоянии . Для любого момента времени t справедливо =1.
Определим вероятность того, что и в момент времени t+∆t система будет находиться в состоянии . Это может быть в следующих случаях:
1) и за время ∆ t из него не вышла. Это означает, что за время ∆t не возникло события, переводящего систему в состояние (поток с интенсивностью ) или события, переводящего её в состояние (поток с интенсивностью ). Определим вероятность этого при малых ∆t.
При экспоненциальном законе распределения времени между двумя соседними требованиями, соответствующему простейшему потоку событий вероятность того, что на интервале времени ∆t не возникнет ни одного требования в потоке с интенсивностью λ 1 будет равна
Разлагая функцию f(t) в ряд Тейлора (t>0) получим (для t=∆t)
f(∆t)=f(0)+ (0)* ∆t + *∆ + *∆ +…=
= +(-l) *∆t+ (∆ + *(∆ +…»1-l*∆t при ∆t®0
Аналогично для потока с интенсивностью λ 2 получим
.
Вероятность, что на интервале времени ∆t (при ∆t®0) не возникнет ни одного требования будет равна
(∆t)/ = (∆t/ * (∆t/ = (1- *∆t)(1- *∆t) =
1 - - *∆t + 
1 - (
+
)*∆t + б.м.
Таким образом, вероятность того, что система за время ∆t не вышла из состояния , при малых ∆t будет равна
P( / )=1 – ( + )* ∆t
2) Система находилась в состоянии S i -1 и за время перешла в состояние S i . То есть в потоке с интенсивностью возникло хотя бы одно событие. Вероятность этого равна для простейшего потока с интенсивностью λ будет
Для нашего случая вероятность такого перехода будет равна
3)Система находилась в состоянии и за время ∆tперешла в состояние . Вероятность этого будет
Тогда вероятность, что система в момент времени (t+∆t) будет в состоянии S i равна
Вычтем из обеих частей P i (t), разделим на ∆tи, перейдя к пределу, при ∆t→0, получим
Подставив соответствующие значения интенсивностей переходов из состояний в состояния, получим систему дифференциальных уравнений, описывающих изменение вероятностей состояний системы как функций времени.
Данные уравнения называются уравнениями Колмогорова-Чепмена для дискретного марковского процесса.
Задав начальные условия (например, P 0 (t=0)=1,P i (t=0)=0 i≠0) и решив их, получим выражения для вероятностей состояния системы как функций времени. Аналитические решения достаточно просто получить, если число уравнений ≤ 2,3. Если их больше, то обычно решают уравнения численно- на ЭВМ (например методом Рунге-Кутта).
В теории случайных процессов доказано , что если число n состояний системы конечно и из каждого из них можно (за конечное число шагов) перейти в любое другое, то существует предел , к которому стремятся вероятности при t→ . Такие вероятности называются финальными вероятностями состояний, а установившийся режим - стационарным режимом функционирования системы.
Так как в стационарном режиме все 
, следовательно, все =0. Приравняв в системе уравнений левые части 0 и, дополнив их уравнением =1, получим систему линейных алгебраических уравнений, решив которую найдём значения финальных вероятностей.
Пример. Пусть в нашей системе интенсивности отказов и восстановления элементов следующие
Отказы
1эл: 
2эл: 
Ремонт
1эл: 
2эл: 
P 0 +P 1 +P 2 +P 3 =1
0=-(1+2)P 0 +2P 1 +3 P 2
0=-(2+2)P 1 +1P 0 +3P 3
0=-(1+3)P 2 +2P 0 +2P 3
0=-(2+3)P 3 +2P 1 +1P 2
Решив данную систему, получим
P 0 =6/15=0.4; P 1 =3/15=0.2; P 2 =4/15=0.27; P 3 =2/15≈0.13.
Т.е. в стационарном состоянии система в среднем
40% находится в состоянии S 0 (оба узла исправны),
20%- в состоянии S 1 (1-й эл-т ремонтируется, 2-й исправен),
27%- в состоянии S 2 (2-й эл-тремонтируется, 1исправен),
13%- в состоянии S 3 – оба эл-та в ремонте.
Знание финальных вероятностей позволяет оценить среднюю эффективность работы системы и загрузку службы ремонта.
Пусть система в состоянии S 0 приносит доход 8 усл.ед. в единицу времени; в состоянии S 1 -доход 3 усл.ед.; в состоянии S 2 - доход 5;в состоянии S 3 -доход=0
Стоимость ремонта в единицу времени для эл-та 1- 1(S 1, S 3) усл.ед., эл-та 2- (S 2, S 3) 2 усл.ед. Тогда в стационарном режиме:
Доход системы в единицу времени будет:
W дох =8P 0 +3P 1 +5P 2 +0P 3 =8·0.4+3·0.2+5·0.27+0·0.13=5.15 усл.ед.
Стоимость ремонта в ед. времени:
W рем =0P 0 +1P 1 +2P 2 +(1+2)P 3 =0·0.4+1·0.2+2·0.27+3·0.13=1.39 усл.ед.
Прибыль в единицу времени
W= W дох -W рем =5.15-1.39=3.76 усл.ед
Проведя определённые расходы можно изменить интенсивности λи μ и, соответственно, эффективность системы. Целесообразность таких расходов можно оценить, проведя пересчёт P i . и показателей эффективности системы.
