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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- i -тое состояние системы зависит от k параметров.

Следует учесть, что переход из состояния S i в состояние S j носит стохастический характер. Функционирование системы начинаем рассматривать с начального состояния S 0 , которому соответствует момент времени t 0 . То есть, то, что было с системой до момента времени t 0 , относится к «прошлому оной», к предыстории.

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

Полагаем, что состояние системы описывается функцией S (t ), аргумент этой функции, - время t непрерывно, известны моменты времени перехода системы из одного состояния в другое t : t 1 <t 2 < … <t n . Причем переход из одного состояния в другое происходит «скачком», практически мгновенно.

Пришли к тому, что процессу функционирования системы ставится в соответствие цепь дискретных состояний: S 1 ®S 2 ® … ®S n-1 ®S n (последовательный переход из одного состояния в другое, без «перескакивания» через какое-либо состояние). То есть, рассматриваемая система описывается марковским случайным процессом с дискретными состояниями и непрерывным временем.

Из теории вероятности мы знаем, что функция плотности вероятности для n -го состояния ищется как совместная функция плотности для всей «предыстории» процесса прихода системы в это состояние: .

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

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

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

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

Определение. Граф – это совокупность множества вершин V и множество упорядоченных пар вершин A ={(a 1 a i) (a 2 a j) … }, элементы которого называются ребрами G (V ,A ).

Состояниям системы ставятся в соответствие вершины графа, а переходам из одного состояния в другое – верви с указанием «направления протекания» процесса.

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

Пример №1. ТЭА техническая эксплуатация автомобиля.

Упрощенная модель ТЭА подразумевает наличие хотя бы четырех следующих состояний: S 1 – диагностика состояния автомобиля, S 2 – работа на линии (автомобиль исправен), S 3 – техническое обслуживание, S 4 – устранение неисправности (ремонт).

Соответствующий данной системе размеченный граф

m ij плотность вероятности перехода из состояния S i в состояние S j (S i ®S j ), где P ij (Dt ) – вероятность того, что за промежуток времени Dt произойдет данный переход.

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

Значения вероятностей переходов определяются из системы дифференциальных уравнений (Колмогорова) по следующим правилам:

1) каждой вершине ставится в соответствие соответствующее состояние, описываемое вероятностью нахождения системы в оном, поэтому количество состояний определяет количество уравнений в системе;

2) в левой части уравнения – производная вероятности соответствующего состояния;

3) в правой части столько слагаемых, сколько переходов (ветвей) в размеченном графе связано с данным состоянием;

4) каждый элемент правой части равен произведению плотности вероятности перехода на плотность вероятности того состояния, из которого осуществлялся переход;

5) в правой части со знаком «+» идут (складываются) элементы, описывающие попадание системы в данное состояние, и со знаком «-» (вычитаются) элементы, описывающие «выход» системы из данного состояния;

6) для упрощения «решаемости» в систему вводится нормирующее уравнение, описывающее полную группу событий: , где N-количество вершин в размеченном графе состояний.

Данная система уравнений будет легче решаема в случае, когда она описывает стационарный процесс работы исследуемой технической системы (обычно вхождение системы в стационарный режим функционирования занимает от 2-х до 4-х тактов).

На практике считаем, что предположение о стационарности функционирования системы правомерно, если время функционирования системы в целом на порядок выше, чем (20¸40)×тактов работы системы («последовательное» одинарное прохождение по ветвям графа).

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

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

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

Пример №2.

Рассмотрим техническую систему S , состоящую из двух параллельно работающих узлов (два поста на СТО, два заправочных автомата на АЗС). Будем полагать, что переходы системы из одного состояния в другое происходят мгновенно, в случайные моменты времени. Как только узел выходит из строя, он «мгновенно» поступает на ремонт и после приведения его в рабочее состояние он также «мгновенно» начинает эксплуатироваться.

Полагаем, что данная система полностью описывается всего четырьмя состояниями: S 0 – оба узла исправны; S 1 – первый узел ремонтируется, второй исправен; S 2 – второй узел ремонтируется, первый исправен; S 3 – ремонтируются оба узла.

l 1 , l 2 – плотность вероятности выхода из строя первого и второго поста, m 1 , m 2 – плотность вероятности восстановления первого и второго узла соответственно.

Составим систему дифференциальных уравнений по Колмогорову для вероятностей состояний данной системы.

Чтобы решить уравнения Колмогорова и найти численные значения для вероятностей соответствующих состояний, необходимо задаться начальными условиями.

Будем полагать, что в начальный момент времени оба узла исследуемой системы исправны, система находится в состоянии S 0 , т.е. P 0 (t =0)=1, а все остальные начальные вероятности равны нулю: P 1 (0)=P 2 (0)=P 3 (0)=0.

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

Стационарность режима работы предполагает равенство нулю от производных по времени от вероятностей состояния, т.е., i =1, 2, … , n , , где n – количество возможных состояний. А с учётом полной группы событий добавляется уравнение

Последнее, так называемое нормировочное условие, позволяет исключить из системы одно из уравнений…

Решим данную систему при следующих данных: l 1 =1, l 2 =2, m 1 =2, m 2 =3. Запишем систему без четвертого уравнения.

Решая их, получим: P 0 =0,4; P 1 =0,2; P 2 @0,27; P 3 @0,13.

Т.е. в стационарном режиме работы наша система в среднем 40% времени будет находиться в состоянии S 0 – оба узла исправны, и т.д..

Значения этих финальных вероятностей могут помочь оценить среднюю эффективность работы системы и загрузку ремонтных органов. Предположим, что система S в состоянии S 0 приносит доход 8 условных единиц (у.е.) в единицу времени, в состоянии S 1 3у.е., в S 2 5у.е., а в состоянии S 3 не приносит дохода.

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

СМО делят на два основных типа (класса) : СМО с отказами и href="cmo_length.php">СМО с ожиданием (очередью). В СМО с отказами заявка, поступившая в момент, когда все каналы заняты, получает отказ, покидает СМО и в дальнейшем процессе обслуживания не участвует (например, заявка на телефонный разговор в момент, когда все каналы заняты, получает отказ и покидает СМО необслуженной). В СМО с ожиданием заявка, пришедшая в момент, когда все каналы заняты, не уходит, а становится в очередь на обслуживание.
СМО с ожиданием подразделяются на разные виды в зависимости от того, как организована очередь: с ограниченной или неограниченной длиной очереди, с ограниченным временем ожидания и т.п.
Процесс работы СМО представляет собой случайный процесс.
Под случайным (вероятностным или стохастическим) процессом понимается процесс изменения во времени состояния какой-либо системы в соответствии с вероятностными закономерностями.
Процесс называется процессом с дискретными состояниями, если его возможные состояния S 1 , S 2 , S 3 … можно заранее перечислить, а переход системы из состояния в состояние происходит мгновенно (скачком). Процесс называется процессом с непрерывным временем, если моменты возможных переходов системы из состояния в состояние не фиксированы заранее, а случайны.
Процесс работы СМО представляет собой случайный процесс c дискретными состояниями и непрерывным временем. Это означает, что состояние СМО меняется скачком в случайные моменты появления каких-то событий (например, прихода новой заявки, окончания обслуживания и т.п.).
Математический анализ работы СМО существенно упрощается, если процесс этой работы - марковский. Случайный процесс называется марковским или случайным процессом без последствия, если для любого момента времени t 0 вероятностные характеристики процесса в будущем зависят только от его состояния в данный момент t 0 и не зависят от того, когда и как система пришла в это состояние.

Пример марковского процесса: система S - счетчик в такси. Состояние системы в момент t характеризуется числом километров (десятых долей километров), пройденных автомобилем до данного момента. Пусть в момент t 0 счетчик показывает S 0 . Вероятность того, что в момент t > t 0 счетчик покажет то или иное число километров (точнее, соответствующее число рублей) S 1 , зависит от S 0 , но не зависит от того, в какие моменты времени изменялись показания счетчика до момента t 0 .
Многие процессы можно приближенно считать марковскими. Например, процесс игры в шахматы; система S - группа шахматных фигур. Состояние системы характеризуется числом фигур противника, сохранившихся на доске в момент t 0 . Вероятность того, что в момент t > t 0 материальный перевес будет на стороне одного из противников, зависят в первую очередь от того, в каком состоянии находится система в данный момент t 0 , а не того, когда и в какой последовательности исчезли фигуры с доски до момента t 0 .
В ряде случаев предысторией рассматриваемых процессов можно просто пренебречь и применять для их изучения марковские модели.
При анализе случайных процессов с дискретными состояниями удобно пользоваться геометрической схемой - так называемым графом состоянии. Обычно состояния системы изображаются прямоугольниками (кружками), а возможные переходы из состояния в состояние - стрелками (ориентированными дугами), соединяющими состояния.
Задача 1 . Построить граф состояний следующего случайного процесса: устройство S состоит из двух узлов, каждый из которых в случайный момент времени может выйти из строя, после чего мгновенно начинается ремонт узла, продолжающийся заранее неизвестное случайное время.

Решение. Возможные состояния системы: S 0 - оба узла исправны; S 1 - первый узел ремонтируется, второй исправен; S 2 - второй узел ремонтируется, первый исправен; S 3 - оба узла ремонтируются. Граф системы приведен на рис.1.
Рис. 1
Стрелка, направленная, например, из S 0 в S 1 означает переход системы в момент отказа первого узла, из S 1 в S 0 - переход в момент окончанияремонта этого узла.
На графе отсутствуют стрелки из S 0 , в S 3 и из S 1 в S 2 . Это объясняется тем, что выходы узлов из строя предполагаются независимыми друг от друга и, например, вероятностью одновременного выхода из строя двух узлов (переход из S 0 в S 3) или одновременного окончания ремонтов двух узлов (переход из S 3 в S 0) можно пренебречь.

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

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

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

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

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

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

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

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

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

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

Пример

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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