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

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

Поясним понятие марковского случайного процесса.

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

Примеры случайных процессов:

флуктуации цен на фондовом рынке;

обслуживание клиентов в парикмахерской или ремонтной мастерской;

выполнение плана снабжения группы предприятий и т. д.

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

поступление на фондовый рынок непредсказуемых известий о политических изменениях;

случайный характер потока заявок (требований), поступающих со стороны клиентов;

случайные перебои в выполнении плана снабжения и т. д.

ОПРЕДЕЛЕНИЕ. Случайный процесс, протекающий в системе, называется марковским (или процессом без последствия ), если он обладает следующим свойством: для каждого момента времени t 0 вероятность любого состояния системы в будущем (при t > t 0) зависит только от ее состояния в настоящем (при t = t 0) и не зависит от того, когда и каким образом система пришла в это состояние (т. е. как развивался процесс в прошлом).

Другими словами, в марковском случайном процессе будущее развитие его зависит только от настоящего состояния и не зависит от “предыстории” процесса.

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

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

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

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

ОПРЕДЕЛЕНИЕ. Случайный процесс называется процессом с дискретными состояниями, если возможные состояния системы s x , s 2 , s v ... можно перечислить (пронумеровать) одно за другим, а сам процесс состоит в том, что время от времени система S скачком (мгновенно) перескакивает из одного состояния в другое.

Например, разработку проекта S осуществляют совместно два отдела, каждый из которых может совершить ошибку. Возможны следующие состояния системы:

5, - оба отдела работают нормально;

s 2 - первый отдел совершил ошибку, второй работает нормально;

s 3 - второй отдел совершил ошибку, первый работает нормально;

s 4 - оба отдела совершили ошибку.

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

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

Мы будем рассматривать только случайные процессы с дискретными состояниями.

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

Пусть имеется система S с дискретными состояниями:

Каждое состояние будем изображать прямоугольником, а возможные переходы (“перескоки”) из состояния в состояние - стрелками, соединяющими эти прямоугольники. Пример графа состояния приведен на рис. 4.1.

Заметим, что стрелками отмечаются только непосредственные переходы из состояния в состояние; если система может перейти из состояния s 2 в 5 3 только через s y то стрелками отмечаются только переходы s 2 -> и л, 1 -> 5 3 , но не s 2 -» s y Рассмотрим несколько примеров:

1. Система S - фирма, которая может находиться в одном из пяти возможных состояний: s ] - работает с прибылью;

s 2 - утратила перспективу развития и перестала приносить прибыль;

5 3 - стала объектом для потенциального поглощения;

s 4 - находится под внешним управлением;

s 5 - имущество ликвидируемой фирмы продается на торгах.

Граф состояний фирмы показан на рис. 4.2.

Рис. 4.2

  • 2. Система S - банк, имеющий два отделения. Возможны следующие состояния системы:
  • 5, - оба отделения работают с прибылью;

s 2 - первое отделение работает без прибыли, второе работает с прибылью;

5 3 - второе отделение работает без прибыли, первое работает с прибылью;

s 4 - оба отделения работают без прибыли.

Предполагается, что улучшение состояния не происходит.

Граф состояний представлен на рис. 4.3. Отметим, что на графе не показан возможный переход из состояния s ] непосредственно в s 4 , который осуществится, если банк сразу будет работать в убыток. Возможностью такого события можно пренебречь, что и подтверждает практика.

Рис. 4.3

3. Система S - инвестиционная компания, состоящая из двух трейдеров (отделов): I и II; каждый из них может в какой-то момент времени начать работать в убыток. Если это происходит, то руководство компании немедленно принимает меры для восстановления прибыльной работы отдела.

Возможные состояния системы: s - деятельность обоих отделов прибыльна; s 2 - первый отдел восстанавливается, второй работает с прибылью;

s 3 - первый отдел работает с прибылью, второй восстанавливается;

s 4 - оба отдела восстанавливаются.

Граф состояний системы показан на рис. 4.4.

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

Состояния системы будем для удобства нумеровать не одним, а двумя индексами; первый будет означать состояния первого трейдера (1 - работает с прибылью, 2 - его деятельность изучается руководством, 3 - восстанавливает прибыльную деятельность отдела); второй - те же состояния для второго трейдера. Например, s 23 будет означать: деятельность первого трейдера изучается, второй - восстанавливает прибыльную работу.

Возможные состояния системы S:

s u - деятельность обоих трейдеров приносит прибыль;

s l2 - первый трейдер работает с прибылью, деятельность второго изучается руководством компании;

5 13 - первый трейдер работает с прибылью, второй восстанавливает прибыльную деятельность отдела;

s 2l - деятельность первого трейдера изучается руководством, второй работает с прибылью;

s 22 - деятельность обоих трейдеров изучается руководством;

  • 5 23 - работа первого трейдера изучается, второй трейдер восстанавливает прибыльную деятельность отдела;
  • 5 31 - первый трейдер восстанавливает прибыльную деятельность отдела, второй работает с прибылью;
  • 5 32 - прибыльная деятельность отдела восстанавливается первым трейдером, работа второго трейдера изучается;
  • 5 33 - оба трейдера восстанавливают прибыльную работу своего отдела.

Всего девять состояний. Граф состояний показан на рис. 4.5.

Эволюция к-рого после любого заданного значения временного параметра 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; Фрейдлин М. И., в кн.: Итоги науки. Теория вероятностей, математическая статистика. - Теоретическая кибернетика. 1966, М., 1967, с. 7-58; X а с ь м и н с к и й Р. 3., "Теория вероятн. и ее примен.", 1963, т. 8, в . 1, с. 3-25; Вентцель А. Д., Фрейдлин М. И., Флуктуации в динамических системах под действием малых случайных возмущений, М., 1979; Blumenthal R. М., G e t о о r R. К., Markov processes and potential theory, N.Y.- L., 1968; Getоor R. K., Markov processes: Ray processes and right processes, В., 1975; Кузнецов С. Е., "Теория вероятн. и ее примен.", 1980, т. 25, в. 2, с. 389-93.

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

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

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

В первом случае переход из одного состояния в другое происходит в заранее известные моменты времени — такты (1, 2, 3, 4, …). Переход осуществляется на каждом такте, то есть исследователя интересует только последовательность состояний, которую проходит случайный процесс в своем развитии, и не интересует, когда конкретно происходил каждый из переходов.

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

И еще. Если вероятность перехода не зависит от времени, то марковскую цепь называют однородной .

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

Итак, модель марковского процесса представим в виде графа, в котором состояния (вершины) связаны между собой связями (переходами из i -го состояния в j -е состояние), см. рис. 33.1 .

Рис. 33.1. Пример графа переходов

Каждый переход характеризуется вероятностью перехода P ij . Вероятность P ij показывает, как часто после попадания в i -е состояние осуществляется затем переход в j -е состояние. Конечно, такие переходы происходят случайно, но если измерить частоту переходов за достаточно большое время, то окажется, что эта частота будет совпадать с заданной вероятностью перехода.

Ясно, что у каждого состояния сумма вероятностей всех переходов (исходящих стрелок) из него в другие состояния должна быть всегда равна 1 (см. рис. 33.2 ).

Рис. 33.2. Фрагмент графа переходов
(переходы из i-го состояния являются
полной группой случайных событий)

Например, полностью граф может выглядеть так, как показано на рис. 33.3 .

Рис. 33.3. Пример марковского графа переходов

Реализация марковского процесса (процесс его моделирования) представляет собой вычисление последовательности (цепи) переходов из состояния в состояние (см. рис. 33.4 ). Цепь на рис. 33.4 является случайной последовательностью и может иметь также и другие варианты реализации.

Рис. 33.4. Пример марковской цепи, смоделированной
по марковскому графу, изображенному на рис. 33.3

Чтобы определить, в какое новое состояние перейдет процесс из текущего i -го состояния, достаточно разбить интервал на подынтервалы величиной P i 1 , P i 2 , P i 3 , … (P i 1 + P i 2 + P i 3 + … = 1 ), см. рис. 33.5 . Далее с помощью ГСЧ надо получить очередное равномерно распределенное в интервале случайное число r рр и определить, в какой из интервалов оно попадает (см. лекцию 23).

Рис. 33.5. Процесс моделирования перехода из i-го
состояния марковской цепи в j-е с использованием
генератора случайных чисел

После этого осуществляется переход в состояние, определенное ГСЧ, и повтор описанной процедуры для нового состояния. Результатом работы модели является марковская цепь (см. рис. 33.4 ) .

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

Определим следующие три состояния: S 0 — цель не повреждена; S 1 — цель повреждена; S 2 — цель разрушена. Зададим вектор начальных вероятностей:

S 0 S 1 S 2
P 0 0.8 0.2 0

Значение P 0 для каждого из состояний показывает, какова вероятность каждого из состояний объекта до начала стрельбы.

Зададим матрицу перехода состояний (см. табл. 33.1).

Таблица 33.1.
Матрица вероятностей перехода
дискретного марковского процесса
В S 0 В S 1 В S 2 Сумма вероятностей
переходов
Из S 0 0.45 0.40 0.15 0.45 + 0.40 + 0.15 = 1
Из S 1 0 0.45 0.55 0 + 0.45 + 0.55 = 1
Из S 2 0 0 1 0 + 0 + 1 = 1

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

Наглядно модель марковского процесса можно представить себе в виде следующего графа (см. рис. 33.6 ).

Рис. 33.6. Граф марковского процесса,
моделирующий стрельбу из пушки по цели

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

Проимитируем, используя таблицу случайных чисел, процесс стрельбы. Пусть начальное состояние будет S 0 . Возьмем последовательность из таблицы случайных чисел: 0.31, 0.53, 0.23, 0.42, 0.63, 0.21, … (случайные числа можно взять, например, из этой таблицы).

0.31 : цель находится в состоянии S 0 и остается в состоянии S 0 , так как 0 < 0.31 < 0.45;
0.53 : цель находится в состоянии S 0 и переходит в состояние S 1 , так как 0.45 < 0.53 < 0.45 + 0.40;
0.23 : цель находится в состоянии S 1 и остается в состоянии S 1 , так как 0 < 0.23 < 0.45;
0.42 : цель находится в состоянии S 1 и остается в состоянии S 1 , так как 0 < 0.42 < 0.45;
0.63 : цель находится в состоянии S 1 и переходит в состояние S 2 , так как 0.45 < 0.63 < 0.45 + 0.55.

Так как достигнуто состояние S 2 (далее цель переходит из S 2 в состояние S 2 с вероятностью 1), то цель поражена. Для этого в данном эксперименте потребовалось 5 снарядов.

На рис. 33.7 приведена временная диаграмма, которая получается во время описанного процесса моделирования. Диаграмма показывает, как во времени происходит процесс изменения состояний. Такт моделирования для данного случая имеет фиксированную величину. Нам важен сам факт перехода (в какое состояние переходит система) и не важно, когда это происходит.
Рис. 33.7. Временная диаграмма переходов
в марковском графе (пример имитации)

Процедура уничтожения цели совершена за 5 тактов, то есть марковская цепь этой реализации выглядит следующим образом: S 0 —S 0 —S 1 —S 1 —S 1 —S 2 . Конечно, ответом задачи это число быть не может, так как в разных реализациях получатся разные ответы. А ответ у задачи может быть только один.

Повторяя данную имитацию, можно получить, например, еще такие реализации (это зависит от того, какие конкретно случайные числа выпадут): 4 (S 0 —S 0 —S 1 —S 1 —S 2 ); 11 (S 0 —S 0 —S 0 —S 0 —S 0 —S 1 —S 1 —S 1 —S 1 —S 1 —S 1 —S 2 ); 5 (S 1 —S 1 —S 1 —S 1 —S 1 —S 2 ); 6 (S 0 —S 0 —S 1 —S 1 —S 1 —S 1 —S 2 ); 4 (S 1 —S 1 —S 1 —S 1 —S 2 ); 6 (S 0 —S 0 —S 1 —S 1 —S 1 —S 1 —S 2 ); 5 (S 0 —S 0 —S 1 —S 1 —S 1 —S 2 ). Всего уничтожено 8 целей. Среднее число циклов в процедуре стрельбы составило: (5 + 4 + 11 + 5 + 6 + 4 + 6 + 5)/8 = 5.75 или, округляя, 6. Именно столько снарядов, в среднем, рекомендуется иметь в боевом запасе пушки для уничтожения цели при таких вероятностях попаданий.

Теперь следует определить точность. Именно точность может нам показать, насколько следует доверять данному ответу. Для этого проследим, как сходится последовательность случайных (приближенных) ответов к правильному (точному) результату. Напомним, что, согласно центральной предельной теореме (см. лекцию 25 , лекцию 21), сумма случайных величин есть величина неслучайная, поэтому для получения статистически достоверного ответа необходимо следить за средним числом снарядов, получаемых в ряде случайных реализаций.

На первом этапе вычислений средний ответ составил 5 снарядов, на втором этапе средний ответ составил (5 + 4)/2 = 4.5 снаряда, на третьем — (5 + 4 + 11)/3 = 6.7. Далее ряд средних величин, по мере накопления статистики, выглядит следующим образом: 6.3, 6.2, 5.8, 5.9, 5.8. Если изобразить этот ряд в виде графика средней величины выпущенных снарядов, необходимых для поражения цели, в зависимости от номера эксперимента, то обнаружится, что данный ряд сходится к некоторой величине, которая и является ответом (см. рис. 33.8 ).

Рис. 33.8. Изменение средней величины в зависимости от номера эксперимента

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

Алгоритм имитации будет иметь следующий вид (см. рис. 33.9).

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

Марковские случайные процессы с непрерывным временем

Итак, снова модель марковского процесса представим в виде графа, в котором состояния (вершины) связаны между собой связями (переходами из i -го состояния в j -е состояние), см. рис. 33.10 .

Рис. 33.10. Пример графа марковского
процесса с непрерывным временем

Теперь каждый переход характеризуется плотностью вероятности перехода λ ij . По определению:

При этом плотность понимают как распределение вероятности во времени.

Переход из i -го состояния в j -е происходит в случайные моменты времени, которые определяются интенсивностью перехода λ ij .

К интенсивности переходов (здесь это понятие совпадает по смыслу с распределением плотности вероятности по времени t ) переходят, когда процесс непрерывный, то есть, распределен во времени.

С интенсивностью потока (а переходы — это поток событий) мы уже научились работать в лекции 28 . Зная интенсивность λ ij появления событий, порождаемых потоком, можно сымитировать случайный интервал между двумя событиями в этом потоке.

где τ ij — интервал времени между нахождением системы в i -ом и j -ом состоянии.

Далее, очевидно, система из любого i -го состояния может перейти в одно из нескольких состояний j , j + 1 , j + 2 , …, связанных с ним переходами λ ij , λ ij + 1 , λ ij + 2 , ….

В j -е состояние она перейдет через τ ij ; в (j + 1 )-е состояние она перейдет через τ ij + 1 ; в (j + 2 )-е состояние она перейдет через τ ij + 2 и т. д.

Ясно, что система может перейти из i -го состояния только в одно из этих состояний, причем в то, переход в которое наступит раньше.

Поэтому из последовательности времен: τ ij , τ ij + 1 , τ ij + 2 и т. д. надо выбрать минимальное и определить индекс j , указывающий, в какое именно состояние произойдет переход.

Пример. Моделирование работы станка . Промоделируем работу станка (см. рис. 33.10 ), который может находиться в следующих состояниях: S 0 — станок исправен, свободен (простой); S 1 — станок исправен, занят (обработка); S 2 — станок исправен, замена инструмента (переналадка) λ 02 < λ 21 ; S 3 — станок неисправен, идет ремонт λ 13 < λ 30 .

Зададим значения параметров λ , используя экспериментальные данные, получаемые в производственных условиях: λ 01 — поток на обработку (без переналадки); λ 10 — поток обслуживания; λ 13 — поток отказов оборудования; λ 30 — поток восстановлений.

Реализация будет иметь следующий вид (см. рис. 33.11 ).

Рис. 33.11. Пример моделирования непрерывного
марковского процесса с визуализацией на временной
диаграмме (желтым цветом указаны запрещенные,
синим — реализовавшиеся состояния)

В частности, из рис. 33.11 видно, что реализовавшаяся цепь выглядит так: S 0 —S 1 —S 0 —… Переходы произошли в следующие моменты времени: T 0 —T 1 —T 2 —T 3 —… , где T 0 = 0 , T 1 = τ 01 , T 2 = τ 01 + τ 10 .

Задача . Поскольку модель строят для того, чтобы на ней можно было решить задачу, ответ которой до этого был для нас совсем не очевиден (см. лекцию 01), то сформулируем такую задачу к данному примеру. Определить долю времени в течение суток, которую занимает простой станка (посчитать по рисунку) T ср = (T + T + T + T )/N .

Алгоритм имитации будет иметь следующий вид (см. рис. 33.12 ).

Рис. 33.12. Блок-схема алгоритма моделирования непрерывного
марковского процесса на примере имитации работы станка

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

Эволюция которого после любого заданного значения временно́го параметра 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,

P (X t ∈ A | F s) = P (X t ∈ A | X s) . {\displaystyle \mathbb {P} (X_{t}\in A|{\mathcal {F}}_{s})=\mathbb {P} (X_{t}\in A|X_{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, …) и счетным множеством состояний. Такой случайный процесс называется марковским, так как следующее состояние точки зависит только от настоящего (текущего) состояния и не зависит от прошлых состояний (неважно, каким путём и за какое время точка попала в текущую координату).

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

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

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

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

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

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

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

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

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

Пример

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

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

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

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

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

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

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

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

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

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

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

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

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