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

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

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

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

Пусть имеется некоторая система 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.

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

Особенности фактора случайности

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

• диффузионная теория;
• теория массового обслуживания;
• теория надежности и прочего;
• химия;
• физика;
• механика.

Сущностные особенности не запланированного фактора

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

• колебания в цепи;
• скорость движения;
• шероховатость поверхности на заданном участке.

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

Детальный разбор понятия случайности

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

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

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

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

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

Подробное токование понятия

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

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

Структурный разбор процессов

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

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

Описание дискретного состояния и непрерывности времени

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

Дискретный Марковский процесс основан на теории вероятности, а также является переходом системы из одного состояния в другое. Причем данный фактор происходит мгновенно, даже если происходят случайные поломки и ремонтные работы. Чтобы провести анализ такого процесса, лучше использовать графы состояний, то есть геометрические схемы. Системные состояния в таком случае обозначены различными фигурами: треугольниками, прямоугольниками, точками, стрелками.

Моделирование данного процесса

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

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

Вероятностные теории

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

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

Примеры теории вероятности

Примерами Марковских процессов в данной ситуации могут выступать:

• кафе;
• билетные кассы;
• ремонтных цеха;
• станции различного назначения и пр.

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

Скрытые модели процесса

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

Сущностное раскрытие скрытых Марковских моделей

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

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

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

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

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

Марковские случайные процессы названы по имени выдающегося русского математика А.А. Маркова (1856-1922), впервые начавшего изучение вероятностной связи случайных величин и создавшего теорию, которую можно назвать “динамикой вероятностей”. В дальнейшем основы этой теории явились исходной базой общей теории случайных процессов, а также таких важных прикладных наук, как теория диффузионных процессов, теория надежности, теория массового обслуживания и т.д. В настоящее время теория Марковских процессов и ее приложения широко применяются в самых различных областях таких наук, как механика, физика, химия и др.

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

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

Как указывалось, Марковские случайные процессы относятся к частным случаям случайных процессов (СП). В свою очередь, случайные процессы основаны на понятии случайной функции (СФ).

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

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

Как правило, считают, что если аргументом СФ является время, то такой процесс называют случайным. Существует и другое, более близкое к теории принятия решений, определение случайных процессов. При этом под случайным процессом понимают процесс случайного изменения состояний какой-либо физической или технической системы по времени или какому-либо другому аргументу.

Нетрудно заметить, что если обозначить состояние и изобразить зависимость, то такая зависимость и будет случайной функцией.

Случайные процессы классифицируются по видам состояний и аргументу t. При этом случайные процессы могут быть с дискретными или непрерывными состояниями или временем.

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

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

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

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

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

Цепь Маркова считается заданной, если заданы два условия.

1. Имеется совокупность переходных вероятностей в виде матрицы:

2. Имеется вектор начальных вероятностей

описывающий начальное состояние системы.

Кроме матричной формы модель Марковской цепи может быть представлена в виде ориентированного взвешенного графа (рис. 1).

Рис. 1

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

1. Невозвратное множество (рис. 2).

Рис.2.

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

2. Возвратное множество (рис. 3).

Рис. 3.

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

3. Эргодическое множество (рис. 4).

Рис. 4.

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

4. Поглощающее множество (рис. 5)

Рис. 5.

При попадании системы в это множество процесс заканчивается.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Чтобы определить, в какое новое состояние перейдет процесс из текущего 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.4 ) .

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

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

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

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

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

Наглядно модель марковского процесса можно представить себе в виде следующего графа (см. рис. 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 приведена временная диаграмма, которая получается во время описанного процесса моделирования. Диаграмма показывает, как во времени происходит процесс изменения состояний. Такт моделирования для данного случая имеет фиксированную величину. Нам важен сам факт перехода (в какое состояние переходит система) и не важно, когда это происходит.

Процедура уничтожения цели совершена за 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.9).

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

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

Итак, снова модель марковского процесса представим в виде графа, в котором состояния (вершины) связаны между собой связями (переходами из i -го состояния в j -е состояние), см. рис. 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 видно, что реализовавшаяся цепь выглядит так: 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 ).

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

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

Процесс без последействия, - случайный процесс , эволюция к-рого после любого заданного значения временного параметра 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, В ), заданную в измеримом пространстве можно рассматривать как переходную функцию нек-рого М. п. Ответ положителен, если, напр., Еявляется сепарабельным локально компактным пространством, а - совокупностью борелевских множеств в Е. Более того, пусть Е - полное метрич. пространство и пусть

Далее, постулируется однородность пространства 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, в

Марковский процесс - дискретный или непрерывный случайный процесс 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 русским ученым А.А. Марковым.