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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

СМО – система, подразумевающая наличие в ней 2х процессов: поступления заявок и обслуживания заявок.

Условно схема представляется в виде

И Накопитель К

Обслуживающий прибор

Процесс поступления заявок – процесс по времени.

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

С любой СМО связаны 3 потока:

1) входной поток. Последовательность моментов времени поступления заявок

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

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

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

Поток наз-ся регулярным , если интервалы времени между событиями в нём одинаковы. Нерегулярный – если интервалы времени м\ду событиями – случайные величины.

Поток рекуррентный , если интервалы времени между событиями – случайные величины, распределённые по одному и томуже закону.

Поток наз-ся однородным , если он х-ся только множеством {ti} наступивших событий. Неоднородный – если он описывается множеством {ti,fi}, где ti – моменты времени наступления событий, fi – признак заявки.

Сами СМО подразделяются на СМО с отказами и СМО с очередями . СМО с очередями подразделяется на с ограниченной очередью и с неограниченной очередью. Частный случай – ограниченное время ожидания в очереди.

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

1) FIFO (first in – first out) – в порядке поступления;

2) LIFO (last in – first out) – первой обслуживается поступившая последней;

3) SIRO (service in random order) – в случайном порядке;

4) – приоритетные системы. (абсолютный и относительный приоритеты. При относительном заявки выстраиваются по значению приоритета – вначале высокие, потом ниже.)

Для краткой характеристики СМО Д.Кендалл ввел символику (нотацию)

m - число обслуживающих каналов;

n – количество мест ожидания (емкость накопителя).

k – кол-во источников.

A и B характеризуют соответственно входной поток и поток обслуживания, задавая функцию распределения интервалов между заявками во входном потоке и функцию распределения времен обслуживания.

А и В могут принимать значения:

D – детерминированное распределение;

М – показательное;

Е r – распределение Эрланга;

H r - гиперпоказательное;

G – распределение общего вида.

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

9. Простейший поток, его свойства и значение при исследовании смо.

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

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

2)Поток ординарный , если вероятность появления двух или более событий в течение элементарного интервала времени
→0 есть величина бесконечно малая по сравнению с вероятностью появления одного события на этом интервале.

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

Поток, удовлетворяющий этим трем условиям, называется простейшим.

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

вероятность того, что за интервал времени τ произойдет ровно m событий.

Условие отсутствие последствия (заявки поступают независимо друг от друга) наиболее существенно для простейшего потока.

пуассоновского распределения.

Вероятность того, что за не произойдет не одного события

Вероятность, что за времяпроизойдет хотя бы одно событие

Иногда удобней анализировать систему, рассматривая интервалы между событиями T:

Это показательный закон с интенсивностью .

Математическое ожидание и среднее квадратичное для T:

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

Введем состояния системы следующим образом – считаем систему, находящейся в состоянии S, если в момент времени t в системе находится S заявок.

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

(S=0, 1, 2…)

Разлагая в ряд, получим:

Вероятность получения хотя бы одной заявки

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

Простейшие или близкие к ним потоки часто встречаются на практике.

При суммировании достаточно большого кол-ва потоков с последействием, получается поток с последействием. В простейшем потоке приблизительно 68% маленьких интервалов

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

10. Непрерывно-стохастические модели (Q -схемы). Одноканальная СМО с блокировкой. Построение графа состояний .

При построении моделей такого рода как правило, используются рассмотрения моделируемых объектов, как Систем Массового Обслуживания (СМО).

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

В СМО можно выделить два стохастических процесса:

Поступление заявок на обслуживание;

Обслуживание заявок.

Поток событий – последовательность событий, происходящих одно за другим в некоторые моменты времени. В СМО будем выделять два потока:

Входной поток: множество моментов времени поступления в систему заявок;

Поток обслуживания: множество моментов окончания обработки системой заявок.

В общем случае СМО элементарного вида может быть представлено следующим образом

Обслуживающий прибор

И – источник;

О – очередь;

К – канал обслуживания.

Одноканальная СМО с блокировкой . Система M / M / 1/ n

Рассмотрим двухфазную систему, для которой при исследовании P – схем полагали детерминированный входной и просеянный поток обслуживания.

Считаем, что теперь входной поток пуассоновский с интенсивностью, а поток обслуживания – пуассоновский с интенсивностью.

Как и прежде, дисциплина обслуживания FIFO с блокировкой источника.

Состояние – число заявок в системе.

Всего возможно n +3 состояния: от 0 до n +2 .

Обозначим
- вероятность прихода за
i заявок;

- вероятность обслуживания за
i заявок.

ввиду ординарное

Аналогично

+
=

1-
+

Система уравнений:
и
- вероятности состояний.

при
получим

Ввиду стационарности потоков имеем:

и
,

Аналогично для остальных строк системы.

Окончательно имеем:

Получена система алгебраических уравнений.

Преобразуем её, начиная со второго и заканчивая предпоследним - новое уравнение получаем сложением старого с новым предыдущим.

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

i=0, 1,….n+1

Обозначим

,

Используем уравнеие нормировки

;

;

Это сумма геометрической прогрессии:

Cреднее время обсл. заявки

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

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

Возникает вопрос: а нельзя ли свести искусственно (хотя бы приближенно) немарковский процесс к марковскому?

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

Поясним идею метода «псевдосостояний» на конкретном примере.

Пример 1. Рассматривается система S - Техническое устройство, которое может выходить из строя под влиянием простейшего потока неисправностей с интенсивностью к. Отказавшее устройство немедленно начинает восстанавливаться. Время восстановления (ремонта) Т распределено не по показательному закону (как надо было бы для того, чтобы процесс был марковским), а по закону Эрланга порядка:

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

Решение. Случайная величина Т - время восстановления - распределена по закону Эрланга и, значит, представляет собой сумму трех случайных величин распределенных по показательному закону (см. § 5 гл. 4) с параметром

Истинных состояний системы всего два:

Устройство исправно;

Устройство восстанавливается.

Граф этих состояний показан на (он относится к циклической схеме).

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

Чтобы искусственно свести это процесс к марковскому, введем в цепочку состояний, вместо одного состояния три последовательных «псевдосостояния».

Ремонт начинается;

Ремонт продолжается;

Ремонт заканчивается, т. е. разделим ремонт на три этапа или «фазы», причем время пребывания системы в каждой из фаз будем считать распределенным по показательному закону (10.2). Граф состояний будет иметь вид, показанный на рис. 4.48, где роль одного состояния будут играть три псевдосостояния Процесс, протекающий в такой системе, уже будет марковским.

Обозначим - предельные вероятности пребывания системы в псевдосостояниях тогда

Обозначая

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

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

Переходя в формулах для от средних времен к интенсивностям потоков, по формулам получим:

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

Следующий пример будет несколько сложнее.

Пример 2. Техническое устройство S состоит из двух одинаковых узлов, каждый из которых может выходить из строя (отказывать) под влиянием простейшего потока неисправностей с интенсивностью 1. Отказавший узел немедленно начинает ремонтироваться. Время ремонта Т распределено по закону Эрланга второго порядка:

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

Решение. Истинных состояний системы три (нумеруем их по числу отказавших узлов).

Оба узла работают;

Один узел работает, другой ремонтируется;

Оба узла ремонтируются.

Разделим условно ремонт на две фазы: ремонт начинается и ремонт заканчивается.

Один узел работает, другой начинает ремонтироваться;

Один узел работает, другой кончает ремонтироваться;

Оба узла начинают рамонтироваться;

Один узел начинает ремонтироваться, а другой кончает;

Оба узла кончают ремонтироваться.

Граф состояний системы с псевдосостояниями показан на рис. 4.49. На стрелках, ведущих из и из написано а не потому что перейти в следующую фазу ремонта (окончание ремонта) может любой из двух узлов.

Уравнения для предельных вероятностей состояний имеют вид:

Из третьего, пятого и шестого уравнений (10.4) имеем:

что дает возможность уменьшить число неизвестных: подставляя (10.5) в оставшиеся три уравнения (10.4), получим:

Из этих трех уравнений с тремя неизвестными можно по произволу отбросить любое, например, последнее, и добавить нормировочное условие:

или, с учетом (10.5),

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

. (5.7)

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

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

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

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

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

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

(5.10)

. (5.11)

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

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

(5.12)

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

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

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

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

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

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

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

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

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

(5.13)

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

. (5.14)

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

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

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

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

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

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

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

(5.17)

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

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

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

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

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

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

, (5.19)

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

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

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

(5.20)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

СМО делят на два основных типа (класса) : СМО с отказами и 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) можно пренебречь.

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

Для математического описания марковского случайного процесса с дискретными состояниями и непрерывным временем, протекающего в СМО, познакомимся с одним из важных понятий теории вероятностей - понятием потока событий.
Под потоком событий понимается последовательность однородных событий, следующих одно за другим в какие-то случайные моменты времени (например, поток вызовов на телефонной станции, поток отказов ЭВМ, поток покупателей и т.п.).
Поток характеризуется интенсивностью l - частотой появления событий или средним числом событий, поступающих в СМО в единицу времени.
Поток событий называется регулярным, если события следуют одно за другим через определенные равные промежутки времени. Например, поток изделий на конвейере сборочного цеха (с постоянной скоростью движения) является регулярным.
Поток событий называется стационарным, если его вероятностные характеристики не зависят от времени. В частности, интенсивность стационарного потока есть величина постоянная: l(t)= l. Например, поток автомобилей на городском проспекте не является стационарным в течение суток, но этот поток можно считать стационарным в течение суток, скажем, в часы пик. Обращаем внимание на то, что в последнем случае фактическое число проходящих автомобилей в единицу времени (например, в каждую минуту) может заметно отличаться друг от друга, но среднее их число будет постоянно и не будет зависеть от времени.
Поток событий называется потоком без последействия, если для любых двух непересекающихся участков времени t 1 и t 2 - число событий, попадающих на один из них, не зависит от числа событий, попадающих на другие. Например, поток пассажиров, входящих в метро, практически не имеет последействия. А, скажем, поток покупателей, отходящих с покупками от прилавка, уже имеет последействие (хотя бы потому, что интервал времени между отдельными покупателями не может быть меньше, чем минимальное время обслуживания каждого из них).
Поток событий называется ординарным, если вероятность попадания на малый (элементарный) участок времени Dt двух и более событий пренебрежимо мала по сравнению с вероятностью попадания одного события. Другими словами, поток событий ординарен, если события появляются в нем поодиночке, а не группами. Например, поток поемов, подходящих к станции, ординарен, а поток вагонов не ординарен.
Поток событий называется простейшим (или стационарным пуассоновским), если он одновременно стационарен, ординарен и не имеет последействия. Название "простейший" объясняется тем, что СМО с простейшими потоками имеет наиболее простое математическое описание. Заметим, что регулярный поток не является "простейшим", так как он обладает последействием: моменты появления событий в таком потоке жестко зафиксированы.
Простейший поток в качестве предельного возникает в теории случайных процессов столь же естественно, как в теории вероятностей нормальное распределение получается в качестве предельного для суммы случайных величин: при наложении (суперпозиции) достаточно большого числа n независимых, стационарных и ординарных потоков (сравнимых между собой по интенсивностям l 1 (i=1,2, ..., п) получается поток, близкий к простейшему с интенсивностью l, равной сумме интенсивностей входящих потоков, т.е.
Рассмотрим на оси времени Ot (рис. 2) простейший поток событий как неограниченную последовательность случайных точек.
Рис. 2
Можно показать, что для простейшего потока число т событий (точек), попадающих на произвольный участок времени t, распределено по закону Пуассона , (1)
для которого математическое ожидание случайной величины равно ее дисперсии: a= s 2 = l t.
В частности, вероятность того, что за время t не произойдет ни одного события (m=0), равна (2)
Найдем распределение интервала времени Т между произвольными двумя соседними событиями простейшего потока.
В соответствии с (15.2) вероятность того, что на участке времени длиной t не появится ни одного из последующих событий, равна (3)
а вероятность противоположного события, т.е. функция распределения случайной величины Т, есть (4)
Плотность вероятности случайной величины есть производная ее функции распределения (рис. 3), т.е. (5)
Рис. 3
Распределение, задаваемое плотностью вероятности (5) или функцией распределения (4), называется показательным (или экспоненциальным). Таким образом, интервал времени между двумя соседними произвольными событиями имеет показательное распределение, для которого математическое ожидание равно среднему квадратическому отклонению случайной величины (6)
и обратно по величине интенсивности потока l.
Важнейшее свойство показательного распределения (присущее только показательному распределению) состоит в следующем: если промежуток времени, распределенный по показательному закону, уже длился некоторое время t, то это никак не влияет на закон распределения оставшейся части промежутка (T-t): он будет таким же, как и закон распределения всего промежутка Т.
Другими словами, для интервала времени Т между двумя последовательными соседними событиями потока, имеющего показательное распределение, любые сведения о том, сколько времени протекал этот интервал, не влияют на закон распределения оставшейся части. Это свойство показательного закона представляет собой, в сущности, другую формулировку для "отсутствия последействия" - основного свойства простейшего потока.
Для простейшего потока с интенсивностью l вероятность попадания на элементарный (малый) отрезок времени Dt хотя бы одного события потока равна согласно (4)
(7)
(Заметим, что эта приближенная формула, получаемая заменой функции e - l Dt лишь двумя первыми членами ее разложения в ряд по степеням Dt, тем точнее, чем меньше Dt).