Случайным процессом называется множество или семейство случайных величин, значения которых индексируются временным параметром. Например, число студентов в аудитории, атмосферное давление или температура в этой аудитории как функции времени являются случайными процессами.
Случайные процессы находят широкое применение при изучении сложных стохастических систем как адекватные математические модели процесса функционирования таких систем.
Основными понятиями для случайных процессов являются понятия состояния процесса иперехода его из одного состояния в другое.
Значения переменных, которые описывают случайный процесс, в данный момент времени называются состоянием случайного процесса . Случайный процесс совершает переход из одного состояния в другое, если значения переменных, задающих одно состояние, изменяются на значения, которые определяют другое состояние.
Число возможных состояний (пространство состояний) случайного процесса может быть конечным или бесконечным. Если число возможных состояний конечно или счетно (всем возможным состояниям могут быть присвоены порядковые номера), то случайный процесс называется процессом с дискретными состояниями . Например, число покупателей в магазине, число клиентов в банке в течение дня описываются случайными процессами с дискретными состояниями.
Если переменные, описывающие случайный процесс, могут принимать любые значения из конечного или бесконечного непрерывного интервала, а, значит, число состояний несчетно, то случайный процесс называется процессом с непрерывными состояниями . Например, температура воздуха в течение суток является случайным процессом с непрерывными состояниями.
Для случайных процессов с дискретными состояниями характерны скачкообразные переходы из одного состояния в другое, тогда, как в процессах с непрерывными состояниями переходы являются плавными. Далее будем рассматривать только процессы с дискретными состояниями, которых часто называют цепями .
Обозначим через g (t ) случайный процесс с дискретными состояниями, а возможные значенияg (t ), т.е. возможные состояния цепи, - через символыE 0 , E 1 , E 2 , … . Иногда для обозначения дискретных состояний используют числа 0, 1, 2,... из натурального ряда.
Случайный процесс g (t ) называетсяпроцессом с дискретным временем , если переходы процесса из состояния в состояние возможны только в строго определенные, заранее фиксированные моменты времениt 0 , t 1 , t 2 , … . Если переход процесса из состояния в состояние возможен в любой, заранее неизвестный момент времени, то случайный процесс называетсяпроцессом с непрерывным временем . В первом случае, очевидно, что интервалы времени между переходами являются детерминированными, а во втором - случайными величинами.
Процесс с дискретным временем имеет место либо, когда структура системы, которая описывается этим процессом, такова, что ее состояния могут изменяться только в заранее определенные моменты времени, либо когда предполагается, что для описания процесса (системы) достаточно знать состояния в определенные моменты времени. Тогда эти моменты можно пронумеровать и говорить о состоянии E i в момент времени t i .
Случайные процессы с дискретными состояниями могут изображаться в виде графа переходов (или состояний), в котором вершины соответствуют состояниям, а ориентированные дуги - переходам из одного состояния в другое. Если из состояния E i возможен переход только в одно состояниеE j , то этот факт на графе переходов отражается дугой, направленной из вершиныE i в вершинуE j (рис.1,а). Переходы из одного состояния в несколько других состояний и из нескольких состояний в одно состояние отражается на графе переходов, как показано на рис.1,б и 1,в.
МАРКОВСКИЙ ПРОЦЕСС
Процесс без последействия, - случайный процесс ,
эволюция к-рого после любого заданного значения временного параметра tне зависит от эволюции, предшествовавшей t,
при условии, что значение процесса в этот фиксировано (короче: "будущее" н "прошлое" процесса не зависят друг от друга при известном "настоящем").
Определяющее М. п. свойство принято наз. марковским; впервые оно было сформулировано А. А. Марковым . Однако уже в работе Л. Башелье можно усмотреть попытку трактовать броуновское как М. п., попытку, получившую обоснование после исследований Н. Винера (N. Wiener, 1923). Основы общей теории М. п. с непрерывным временем были заложены А. Н. Колмогоровым .
Марковское свойство. Имеются существенно отличающиеся друг от друга определения М. п. Одним из наиболее распространенных является следующее. Пусть на вероятностном пространстве задан случайный процесс со значениями из измеримого пространства где Т -
подмножество действительной оси Пусть N t
(соответственно N t
).есть s-алгебра в
порожденная величинами X(s).при
где
Другими словами, N t
(соответственно N t
) - это совокупность событий, связанных с эволюцией процесса до момента t(начиная с t).
Процесс X(t).наз.
марковским процессом, если (почти наверное) для всех выполняется марковское свойство:
или, что то же самое, если для любых
М. п., для к-рого Тсодержится в множестве натуральных чисел, наз. Маркова цепью
(впрочем, последний термин чаще всего ассоциируется со случаем не более чем счетного Е).
Если Тявляется интервалом в а Ене более чем счетно, М. п. наз. цепью Маркова с непрерывным временем. Примеры М. п. с непрерывным временем доставляются диффузионными процессами и процессами с независимыми приращениями, в том числе пуассоновским и винеровским.
В дальнейшем для определенности речь будет идти только о случае Формулы (1) и (2) дают ясную интерпретацию принципа независимости "прошлого" и "будущего" при известном "настоящем", но основанное на них определение М. п. оказалось недостаточно гибким в тех многочисленных ситуациях, когда приходится рассматривать не одно, а набор условий типа (1) или (2), отвечающих различным, хотя и согласованным определенным образом, мерам Такого рода соображения привели к принятию следующего определения (см. , ).
Пусть заданы:
а) где s-алгебра содержит все одноточечные множества в Е;
б) измеримое снабженное семейством s-алгебр таких, что если
в) (" ") x t =x
t
(w),
определяющая при любых измеримое отображение
г) для каждых и вероятностная мера на s-алгебре такая, что функция измерима относительно если и
Набор наз. (необрывающимся) марковским процессом, заданным в если -почти наверное
каковы бы ни были Здесь - пространство элементарных событий, - фазовое пространство или пространство состояний, Р(s, x, t, В
) - переходная функция
или вероятность перехода процесса X(t).
Если Енаделено топологией, а - совокупность борелевских множеств в Е,
то принято говорить, что М. п. задан в Е.
Обычно в определение М. п. включают требование, чтобы и тогда истолковывается как вероятность при условии, что x s =x.
Возникает вопрос: всякую ли марковскую переходную функцию Р(s, x
; t, В
),
заданную в измеримом пространстве можно рассматривать как переходную функцию нек-рого М. п. Ответ положителен, если, напр., Еявляется сепарабельным локально компактным пространством, а - совокупностью борелевских множеств в Е.
Более того, пусть Е -
полное метрич. пространство и пусть
а - дополнение e-окрестности точки х. Тогда соответствующий М. п. можно считать непрерывным справа и имеющим пределы слева (т. е. таковыми можно выбрать его траектории). Существование же непрерывного М. п. обеспечивается условием при (см. , ). В теории М. п. основное внимание уделяется однородным (по времени) процессам. Соответствующее определение предполагает заданной систему объектов а) - г) с той разницей, что для фигурировавших в ее описании параметров sи u теперь допускается лишь значение 0. Упрощаются и обозначения:
Далее, постулируется однородность пространства W, т. е. требуется, чтобы для любых существовало такое что (w) при Благодаря этому на s-алгебре N,
наименьшей из s-алгебр в W, содержащих любое событие вида задаются операторы временного сдвига q t
, к-рые сохраняют операции объединения, пересечения и вычитания множеств и для к-рых
Набор наз. (необрывающимся) однородным марковским процессом, заданным в если -почти наверное
для Переходной функцией процесса X(t).считается Р(t, x, В
), причем, если нет специальных оговорок, дополнительно требуют, чтобы Полезно иметь в виду, что при проверке (4) достаточно рассматривать лишь множества вида где и что в (4) всегда F t
можно заменить s-алгеброй , равной пересечению пополнений F t
по всевозможным мерам Нередко в фиксируют вероятностную меру m ("начальное ") и рассматривают марковскую случайную функцию где - мера на заданная равенством
М. п. наз. прогрессивно измеримым, если при каждом t>0 функция индуцирует измеримое в где есть s-алгебра
борелевских подмножеств в . Непрерывные справа М. п. прогрессивно измеримы. Существует способ сводить неоднородный случай к однородному (см. ), и в дальнейшем речь будет идти об однородных М. п.
Строго .
Пусть в измеримом пространстве задан М. п.
Функция наз. марковским моментом,
если для всех
При этом относят к семейству F t , если при (чаще всего F t интерпретируют как совокупность событий, связанных с эволюцией X(t).до момента т). Для полагают
Прогрессивно измеримый М. п. Xназ. строго марковским процессом (с. м. п.), если для любого марковского момента т и всех и соотношение
(строго марковское свойство) выполняется -почти наверное на множестве W t . При проверке (5) достаточно рассматривать лишь множества вида где в этом случае С. м. п. является, напр., любой непрерывный справа феллеровский М. п. в топологич. пространстве Е.
М. п. наз. феллеровским марковским процессом, если функция
непрерывна всякий раз, когда f непрерывна и ограничена.
В классе с. м. п. выделяются те или иные подклассы. Пусть марковская Р(t, x, В
),
заданная в метрическом локально компактном пространстве Е,
стохастически непрерывна:
для любой окрестности Uкаждой точки Тогда если операторы переводят в себя непрерывных и обращающихся в 0 в бесконечности функций, то функции Р(t, х, В
).отвечает стандартный М. п. X,
т. е. непрерывный справа с. м. п., для к-рого
Обрывающийся марковский процесс.
Нередко физич. системы целесообразно описывать с помощью необрывающегося М. п., но лишь на временном интервале случайной длины. Кроме того, даже простые преобразования М. п. могут привести к процессу с траекториями, заданными на случайном интервале (см. Функционал
от марковского процесса). Руководствуясь этими соображениями, вводят понятие обрывающегося М. п.
Пусть - однородный М. п. в фазовом пространстве имеющий переходную функцию и пусть существуют точка и функция такие, что при и в противном случае (если нет специальных оговорок, считают ). Новая траектория x t
(w) задается лишь для ) посредством равенства a F t
определяется как в множестве
Набор где наз. обрывающимся марковским процессом (о. м. п.), полученным из с помощью обрыва (или убивания) в момент z. Величина z наз. моментом обрыва, или временем жизни, о. м. п. Фазовым пространством нового процесса служит где есть след s-алгебры в Е.
Переходная функция о. м. п.- это сужение на множество Процесс X(t).наз. строго марковским процессом, или стандартным марковским процессом, если соответствующим свойством обладает Необрывающийся М. п. можно рассматривать как о. м. п. с моментом обрыва Неоднородный о. м. п. определяется аналогичным образом. М.
Марковские процессы и .
М. п. типа броуновского движения тесно связаны с дифференциальными уравнениями параболич. типа. Переходная р(s, x, t, у
).диффузионного процесса удовлетворяет при нек-рых дополнительных предположениях обратному и прямому дифференциальным уравнениям Колмогорова:
Функция р(s, x, t, у
).есть функция Грина уравнений (6) - (7), и первые известные способы построения диффузионных процессов были основаны на теоремах существования этой функции для дифференциальных уравнений (6) - (7). Для однородного по времени процесса L(s, x
) = L
(x).на гладких функциях совпадает с характеристич. оператором М. п. (см. Переходных операторов полугруппа
).
Математич. ожидания различных функционалов от диффузионных процессов служат решениями соответствующих краевых задач для дифференциального уравнения (1). Пусть - математич. ожидание по мере Тогда функция удовлетворяет при s
Аналогично, функция
удовлетворяет при s
и условию и 2 ( Т, x
) = 0.
Пусть тt - момент первого достижения границы дD
области
траекторией процесса
Тогда при нек-рых условиях функция
удовлетворяет уравнению
и принимает значения ср на множестве
Решение 1-й краевой задачи для общего линейного параболич. уравнения 2-го порядка
при довольно общих предположениях может быть записано в виде
В случае, когда Lи функции с, f
не зависят от s,
аналогичное (9) представление возможно и для решения линейного эллиптич. уравнения. Точнее, функция
при нек-рых предположениях есть задачи
В случае, когдгг оператор Lвырождается (del b(s, х
) = 0
).или дD
недостаточно "хорошая", граничные значения могут и не приниматься функциями (9), (10) в отдельных точках или на целых множествах. Понятие регулярной граничной точки для оператора L
имеет вероятностную интерпретацию. В регулярных точках границы граничные значения достигаются функциями (9), (10). Решение задач (8), (11) позволяет изучать свойства соответствующих диффузионных процессов и функционалов от них.
Существуют методы построения М. п., не опирающиеся на построение решений уравнений (6), (7), напр. метод стохастических дифференциальных уравнений,
абсолютно непрерывная замена меры и др. Это обстоятельство вместе с формулами (9), (10) позволяет вероятностным путем строить и изучать свойства краевых задач для уравнения (8), а также свойства решении соответствующего эллиптич. уравнения.
Так как решение стохастического дифференциального уравнения нечувствительно к вырождению матрицы b(s, x
), то
вероятностные методы применялись для построения решений вырождающихся эллиптических и параболических дифференциальных уравнений. Распространение принципа усреднения Н. М. Крылова и Н. Н. Боголюбова на стохастические дифференциальные уравнения позволило с помощью (9) получить соответствующие результаты для эллиптических и параболических дифференциальных уравнений. Нек-рые трудные задачи исследования свойств решений уравнений такого типа с малым параметром при старшей производной оказалось возможным решить с помощью вероятностных соображений. Вероятностный смысл имеет и решение 2-й краевой задачи для уравнения (6). Постановка краевых задач для неограниченной области тесно связана с возвратностью соответствующего диффузионного процесса.
В случае однородного по времени процесса (Lне зависит от s) положительное решение уравнения с точностью до мультипликативной постоянной совпадает при нек-рых предположениях со стационарной плотностью распределения М. п. Вероятностные соображения оказываются полезными и при рассмотрении краевых задач для нелинейных параболич. уравнений. Р. 3. Хасьминский.
Лит. : Марков А. А., "Изв. физ.-мат. об-ва Казан. ун-та", 1906, т. 15, №4, с. 135-56; В а с h e l i е r L., "Ann. scient. Ecole norm, super.", 1900, v. 17, p. 21-86; Колмогоров А. Н., "Math. Ann.", 1931, Bd 104, S. 415- 458; рус. пер.-"Успехи матем. наук", 1938, в. 5, с. 5-41; Ч ж у н К а й - л а й, Однородные цепи Маркова, пер. с англ., М., 1964; Р е 1 1 е r W., "Ann. Math.", 1954, v. 60, p. 417-36; Д ы н к и н Е. Б., Ю ш к е в и ч А. А., "Теория вероятн. и ее примен.", 1956, т. 1, в. 1, с. 149-55; X а н т Дж.-А., Марковские процессы и потенциалы, пер. с англ., М., 1962; Д е л л а ш е р и К., Емкости и случайные процессы, пер. с франц., М., 1975; Д ы н к и н Е. В., Основания теории марковских процессов, М., 1959; его же, Марковские процессы, М., 1963; Г и х м а н И. И., С к о р о х о д А. В., Теория случайных процессов, т. 2, М., 1973; Фрейдлин М. И., в кн.: Итоги науки. Теория вероятностей, - важный специальный вид случайных процессов. Примером марковского процесса может служить распад радиоактивного вещества, где вероятность распада данного атома за малый промежуток времени не зависит от течения процесса в предшествующий период.… … Большой Энциклопедический словарь
Марковский процесс случайный процесс, эволюция которого после любого заданного значения временного параметра не зависит от эволюции, предшествовавшей, при условии, что значение процесса в этот момент фиксировано («будущее» процесса не… … Википедия
Марковский процесс - 36. Марковский процесс Примечания: 1. Условную плотность вероятности называют плотностью вероятности перехода из состояния xn 1в момент времени tn 1 в состояние хпв момент времени tn. Через нее выражаются плотности вероятностей произвольного… … Словарь-справочник терминов нормативно-технической документации
марковский процесс - Markovo procesas statusas T sritis automatika atitikmenys: angl. Markovprocess vok. Markovprozeß, m rus. марковский процесс, m; процесс Маркова, m pranc. processus markovien, m … Automatikos terminų žodynas
марковский процесс - Markovo vyksmas statusas T sritis fizika atitikmenys: angl. Markov process; Markovian process vok. Markow Prozeß, m; Markowscher Prozeß, m rus. марковский процесс, m; процесс Маркова, m pranc. processus de Markoff, m; processus marcovien, m;… … Fizikos terminų žodynas
Важный специальный вид случайных процессов. Примером Марковского процесса может служить распад радиоактивного вещества, где вероятность распада данного атома за малый промежуток времени не зависит от течения процесса в предшествующий период.… … Энциклопедический словарь
Важный специальный вид случайных процессов (См. Случайный процесс), имеющих большое значение в приложениях теории вероятностей к различным разделам естествознания и техники. Примером М. п. может служить распад радиоактивного вещества.… … Большая советская энциклопедия
Выдающееся открытие в области математики, сделанное в 1906 русским ученым А.А. Марковым.
В последние годы широкое распространение получили методы статистического анализа, оценивания и оптимального управления стохастическими системами, основанные на использовании результатов теории марковских процессов. В данном разделе рассматривается применение методов теории марковских процессов для статистического анализа линейных и нелинейных стохастических систем.
Уравнение Фоккера - Планка - Колмогорова. В теории марковских процессов получены дифференциальные уравнения в частных производных параболического типа для условной (переходной) и безусловной плотностей распределения вероятностей непрерывного марковского процесса x(t). Применительно к скалярному марковскому процессу x(t) уравнение для плотности , называемое уравнением Фоккера - Планка - Колмогорова (ФПК), имеет вид
Функции а(х, t) и b(x, t) называют соответственно коэффициентами сноса и диффузии марковского процесса x(t).
В многомерном случае уравнение ФПК для векторного марковского процесса x(t), состоящего из п компонент , записывается следующим образом:
где - вектор коэффициентов сноса; -матрица коэффициентов диффузии векторного процесса x(t).
Интегрируя уравнение ФПК при заданном начальном условии , можно определить плотность распределения вероятностей рассматриваемого марковского процесса в последующие моменты времени.
Стохастические дифференциальные уравнения. Среди различных непрерывных марковских процессов в практических задачах особенно большое значение имеют так называемые диффузионные марковские процессы, изменение которых во времени описывается дифференциальными уравнениями вида
где -стандартный белый шум.
Такие уравнения называют стохастическими дифференциальными уравнениями.
Уравнение вида (2.53) можно записать непосредственно для изучаемой динамической системы, если случайное входное воздействие этой системы действительно может быть аппроксимировано стандартным белым шумом. Например, одномерной системе, состоящей из интегрирующего звена 1/p, охваченного нелинейной обратной связью f(x), подверженной воздействию белого шума на входе, соответствует стохастическое дифференциальное уравнение первого порядка
Используя метод формирующих фильтров, к виду (2.53) можно привести уравнения, описывающие поведение систем, подверженных воздействию окрашенных шумов.
Пример. Пусть исследуемая динамическая система описывается передаточной функцией апериодического звена
Внешнее воздействие -случайный процесс со спектральной плотностью
Коэффициент усиления К является гауссовской случайной величиной, характеризуемой параметрами m k и D k .
Чтобы описать эту систему стохастическим дифференциальным уравнением, перепишем соотношение (2.54) в виде дифференциального уравнения в нормальной форме:
Последнее уравнение объединим с уравнением формирующего фильтра для , полученные ранее [см. формулу (2.30")].
и уравнением формирующего фильтра для случайного параметра
В результате получим стохастическое дифференциальное уравнение вида (2.53), описывающее рассматриваемую динамическую систему, в котором векторный случайный процесс x(t), объединяющий в качестве составляющих переменные у, x 1 и К, есть диффузионный марковский процесс. Компоненты вектор-функции f T (x, t) - n в данном случае равны
Белый шум является скалярным случайным процессом, поскольку в; правые части уравнений (2.56) и (2.57) входит одно и то же внешнее случайное воздействие, а
Возникает вопрос, как выражаются коэффициенты сноса а(х, t) и диффузии b(x, t), входящие в уравнение ФПК (2.51) или (2.52),. описывающие изменение плотности р(х, t) распределения вероятностей диффузионного марковского процесса x(t), через f(x, t) и ? В зависимости от ответа на этот вопрос различают стохастические дифференциальные уравнения Ито и Стратоновича_ В уравнении Ито в скалярном случае коэффициенты сноса и диффузии соответственно равны f(x, t) и . Для стохастического дифференциального уравнения Стратоновича эти коэффициенты определяются соотношениями *(* Диментберг М. Ф. Нелинейные стохастические задачи механических колебаний. М.: Наука, 1980. 368 с.)
Конкретный вариант используемой интерпретации стохастического дифференциального уравнения зависит от особенностей анализируемой физической системы.
В рассматриваемом далее в данной главе наиболее широко распространенном случае, когда не зависит от х, флуктуационная поправка к коэффициенту сноса, возникающая при рассмотрении стохастического дифференциального уравнения Стратоновича, обращается в нуль и обе интерпретации приводят к одним и тем же результатам.
Интегрировать аналитически и даже численно уравнение в частных производных параболического типа, каким является уравнение ФПК трудно, особенно в тех случаях, когда размерность вектора х велика. Только в одномерном и в отдельных двумерных случаях удается найти аналитическое решение этого уравнения, соответствующего стохастическому дифференциальному уравнению нелинейной системы. Однако каждое такое решение представляет большой интерес, поскольку оно является наиболее полной характеристикой точности системы, позволяющей оценить точность решений, полученных с помощью приближенных методов - расчета, например, с помощью метода статистической линеаризации.
Рис. 2.1. Нелинейная система первого порядка.
Так, стационарным решением уравнения ФПК, соответствующего нелинейной системе первого порядка, показанной на рис. 2.4, для р(х, ∞)=р ст (х) является выражение
в котором постоянная интегрирования С выбирается из условия нормировки . В случае стационарной линейной системы при f(x). = - х из (2.60) получаем гауссовскую плотность . Если в обратной связи стоит реле с уровнем насыщения А, то
Плотности (2.61) соответствуют и .
Уравнения для моментов диффузионного процесса. Основным применением уравнения ФПК при априорном анализе точности систем является получение с его помощью обыкновенных дифференциальных уравнений для вектора математических ожиданий m x (t) и корреляционной матрицы K x (t) фазового вектора диффузионной марковской системы. Эти уравнения оказываются точными, если стохастическое дифференциальное уравнение (2.53) - линейное, и приближенными в случае нелинейного уравнения (2.53).
Чтобы получить из уравнения ФПК уравнения для и в случае, когда x(t) -скалярный процесс, умножим (2.51) на х и проинтегрируем обе части по этой переменной в бесконечных пределах. Тогда получим
Слева в уравнении (2.62) имеем
а интеграл справа вычисляем, применяя метод интегрирования по частям и учитывая граничные условия . Окончательный результат оказывается следующим:
Уравнение для дисперсии D x получают, умножив левую и правую части (2.51) на и проинтегрировав их по переменной х в бесконечных пределах. В итоге имеем
Соотношениями (2.64) - (2.65) устанавливается связь между производными по времени от m x и D x диффузионного процесса x(t) и его плотностью распределения р(х, t). Из них нельзя найти m x (t) и D x (t), если плотность р(х, t) неизвестна.
Уравнения для моментов в линейной системе. Если коэффициент сноса f(x, t) в правой части стохастического дифференциального уравнения (2.57) - линейный относительно х, т. е. f(x,t)=a(t)x + b(t), то соотношения (2.64) и (2.65) превращаются в уравнения относительно m x и D x , т. е. становятся замкнутыми. Действительно, в этом случае
поэтому для линейной марковской системы первого порядка
Интегрирование уравнений (2.66) и (2.67) при заданных начальных условиях m x (t 0) и D x (t 0) позволяет определить m x (t) и D x (t).
Если рассматриваемая система - стационарная и устойчивая, а искомыми являются m x и D x в установившемся режиме, то эти величины можно найти из алгебраических уравнений
поскольку в установившемся режиме для такой системы и
В многомерном случае уравнения для т х и К х оказываются следующими:
Векторное уравнение (2.69) размерности п совместно с матричным уравнением (2.70) размерности п×п называют корреляционной системой уравнений. Системы (2.69) и (2.70) не зависят друг от друга, поэтому их можно интегрировать раздельно. Учитывая симметричность матрицы К х, Для ее определения достаточно про-янтегрировать п(п+1)/2 уравнений относительно различных ковариационных моментов К х. Начальными условиями для (2.69) и (2.70) являются вектор математических ожиданий m x (t 0) и корреляционная матрица К х (t 0) фазового вектора x(t 0) в начальный момент времени.
Если исследуемая линейная марковская система - стационарная и устойчивая, а искомыми являются т х и К х в установившемся режиме, то их можно найти из систем алгебраических уравнений
Одним из способов решения может служить интегрирование соответствующих им систем дифференциальных уравнений (2.69) и (2.70) при произвольно заданных начальных условиях. Сходимость решения обеспечивается устойчивостью исследуемой динамической системы.
Приближенные уравнения для определения моментов диффузионного процесса в нелинейной системе. Для получения приближенной замкнутой системы уравнений из (2.64) и (2.65) в общем случае нелинейного коэффициента сноса f(x, t) предположим, что плотность р(х, t) распределения вероятностей фазового вектора гауссовская. При р(х, t) =p Г (x, t) интегралы в правых частях соотношений (2.64) и (2.65) можно вычислить. Результирующие функции зависят от m x (t) и D x (t), описывающих p Г (x, t):
Подставив (2.73) и (2.74) в (2.64) и (2.65), получим систему из двух нелинейных обыкновенных дифференциальных уравнений:
Интегрирование этой системы при заданных m x (t 0) и D x (t 0) позволяет найти m x (t) и D x (t), т. е. решить приближенно задачу статистического анализа рассматриваемой нелинейной системы. Для «типовых» нелинейностей f(x) формулы для f 0 (m x , D x) и K(m x , D x) могут быть взяты из таблиц выражений коэффициентов статистической линеаризации.
Пример. Пусть f(x) в (2.53)-релейная характеристика f(x)= -A sign (x).
Для этой нелинейности f (см. пример в разд. 1.1) и
Уравнеиия для m x и D x в такой системе имеют вид
Установившиеся значения и получаем, положив и .
Имеем . Сравнивая приближенное значение с точным, полученным ранее путем решения уравнения ФПК значением, видим, что предположение о гауссовском распределении р(х) в рассматриваемой нелинейной системе с реле в обратной связи приводит к ошибке в дисперсии, равной 22%.
В многомерном случае вектор m x (t) и корреляционную матрицу K x (t) можно найти в результате совместного интегрирования двух систем обыкновенных дифференциальных уравнений
Матричная функция, элементами которой являются частные производные от составляющих вектор-функции по компонентам вектора т х.
Если в состав исследуемой системы входят только линейные звенья и типовые одномерные существенные нелинейности, то корреляционную систему вида (2.76) удобно составить, применяя совместно статистическую линеаризацию нелинейных звеньев и корреляционную систему уравнений (2.69) - (2.70) для статистически линеаризованной системы.
Когда управляемое движение летательного аппарата описывается нелинейными стохастическими дифференциальными уравнениями, правые части которых содержат гладкие многомерные нелинейности, приближенный анализ точности такого движения значительно упрощается по сравнению с непосредственным использованием уравнений (2.76), если пользоваться так называемой квазилинейной корреляционной системой уравнений. При составлении такой системы полное движение исследуемой системы разбивается на два движения: среднее и возмущенное. Для описания среднего движения, характеризующего изменение математических ожиданий составляющих фазового вектора, используются нелинейные уравнения системы при математических ожиданиях (средних значениях) начальных условий и внешних воздействий. Для описания возмущенного движения, характеризующего случайные отклонения составляющих фазового вектора от их средних значений, применяются линеаризованные уравнения, причем в качестве опорных значений при линеаризации берутся математические ожидания фазовых координат в соответствующие моменты времени.
Пример. Рассмотрим задачу баллистического спуска летательного аппарата, т. е. спуска с нулевой подъемной силой, в атмосфере Земли. Продольное движение аппарата описывается нелинейными дифференциальными уравнениями
Требуется оценить рассеивание траекторий аппарата, предполагая случайными переменные V, θ, Н и L в момент t 0 начала спуска; постоянными величины R, С х, S, т и g, а зависимость -показательной вида , где .
Перепишем уравнения движения аппарата в виде векторного уравнения
Представим фазовый вектор х в виде х=т х +Δх, а нелинейную вектор-функцию f(x, t) линеаризуем в окрестности х=т х:
где -матрица 4×4 частных производных вектор-функции f(x, t) по составляющим вектора х, вычисленная при х=т х. Получаем уравнение
из которого в результате усреднения непосредственно находим уравнение для вектора математических ожиданий
по виду совпадающие с (2.77). Вычтя (2.79) из (2.78), получаем линеаризованное уравнение возмущенного движения
на основе которого составляем уравнение для корреляционной матрицы фазового вектора
Совместное интегрирование уравнений (2.80) и (2.81), в совокупности образующих квазилинейную корреляционную систему уравнений, при заданных начальных условиях т х (t 0) и K x (t 0) позволяет определить т х (t) и Kx(t) в последующие моменты времени. Точность решения определяется точностью аппроксимации вектор-функции линеаризованной зависимостью при тех значениях случайных отклонений Δx (t) фазового вектора x(t), которые имеют место в рассматриваемой задаче при заданных статистических характеристиках случайных, начальных условий.
2.6. МЕТОД СТАТИСТИЧЕСКОГО МОДЕЛИРОВАНИЯ (МОНТЕ-КАРЛО)
Метод статистического моделирования - универсальный метод статистического анализа стохастических систем (линейных и нелинейных, стационарных и нестационарных), подверженных воздействию случайных факторов различных типов с произвольными их статистическими свойствами. В литературе данный метод также называют методом статистических испытаний или методом Монте-Карло.
Основу метода статистического моделирования составляет закон больших чисел, заключающийся в том, что результат усреднения, относящийся к случайному фактору (событию, величине, процессу или полю), вычисленный по п его реализациям, при перестает быть случайным и может рассматриваться в качестве оценки соответствующей характеристики рассматриваемого фактора. В частности, в соответствии с теоремой. Бернулли при большом числе опытов (реализаций) частота случайного события приближается к вероятности этого события. Аналогичные теоремы существуют и для статистических характеристик случайных величин, процессов, полей.
Применительно к априорному анализу точности стохастических систем метод статистического моделирования заключается в проведении на ЭВМ статистических экспериментов, имитирующих функционирование исследуемой системы при действии случайных факторов, и в последующей обработке полученных в этих экспериментах результатов с помощью методов математической статистики для определения соответствующих статистических характеристик.
Методика статистического моделирования. Первым этапом подготовки к статистическому моделированию стохастической системы является выбор типа ЭВМ (ЦВМ, АВМ или аналого-цифрового комплекса), на которой целесообразно проводить моделирование. При этом учитываются сложность исследуемой системы, характер и число нелинейностей в ней, скорость протекания процессов в различных частях (звеньях) системы, тип и характеристики действующих на систему случайных возмущений и другие факторы.
Выясняется возможность использования канонических разложений случайных процессов, действующих на исследуемую систему. Если такие разложения известны для всех случайных функций, рассматриваемых в системе, моделирование системы можно заметно упростить, поскольку в этом случае при моделировании требуется получать реализации только случайных величин (начальных условий, параметров системы и коэффициентов канонических разложений).
Более общей и сложной является ситуация, когда в число возмущений системы входят случайные процессы, для которых канонические разложения не известны. В этом случае описывающие исследуемую динамическую систему уравнения сводятся к системе стохастических дифференциальных уравнений в нормальной форме вида
где λ - вектор случайных параметров системы; - векторный белый шум. Вектор начальных условий x(t 0) также может быть случайным.
Некоторые из действующих на систему случайных возмущений могут оказаться не белым шумом. Для таких процессов требуется составить дифференциальные уравнения формирующих фильтров. Эти уравнения при моделировании следует интегрировать совместно с уравнениями системы (2.82).
Далее составляется программа интегрирования на ЦВМ системы (2.82) совместно с уравнениями формирующих фильтров или схема моделирования для АВМ. Характерными элементами программы являются блоки, обеспечивающие получение реализаций случайных факторов, рассматриваемых в системе.
Получение на ЭВМ реализаций случайных величин. При моделировании задачи на АВМ, а иногда и на ЦВМ реализации случайных величин задают с помощью таблиц случайных чисел. Наибольшее распространение получили таблицы случайных чисел, подчиняющихся нормальному (гауссовскому) и равномерному распределениям. Таблица нормально распределенных случайных чисел содержит реализации гауссовской случайной величины соответствующие и .Беря числа из этой таблицы, реализации гауссовской случайной величины с характеристиками и вычисляют по формуле
Таблица равномерно распределенных чисел содержит реализации подчиняющиеся равномерному на интервале распределению вероятностей. Для получения реализаций величины х, распределенной равномерно на интервале числа , взятые из таблицы, преобразуют с помощью соотношения
Основным способом получения реализаций случайных величин на ЦВМ является использование специальных стандартных подпрограмм, называемых датчиками псевдослучайных чисел. При каждом обращении к датчику в нем вычисляется новое случайное число. Расчет проводится с помощью рекуррентной формулы, аргументами которой являются несколько случайных чисел, вычисленных при предыдущих обращениях к данной подпрограмме. При фиксированной начальной (стартовой) совокупности случайных чисел все рекуррентно вычисляемые датчиком последующие числа будут определенными, зависящими от стартовой совокупности, поэтому числа, получаемые с помощью датчика, называют псевдослучайными. Рекуррентная формула, реализованная в датчике, подбирается так, чтобы псевдослучайные числа, получаемые с помощью датчика, обладали требуемыми статистическими свойствами - соответствовали определенной плотности распределения вероятностей р(х), а коэффициент корреляции был равен нулю.
Как правило, в библиотеке стандартных подпрограмм ЦВМ присутствуют два датчика псевдослучайных чисел: равномерно распределенных на интервале и гауссовских с и .
Получение реализаций векторной гауссовской случайной величины затруднений не вызывает, если этот вектор некоррелирован. Реализации отдельных компонент такого вектора можно рассчитывать с помощью датчика гауссовских чисел независимо друг от друга. Если же гауссовский вектор х коррелирован, его реализации получают путем линейного преобразования реализаций некоррелированного гауссовского вектора U той же размерности, формируемого с помощью датчика гауссовских псевдослучайных чисел. У вектора U математическое ожидание - нулевой вектор, а корреляционная матрица - единичная. Матрица линейного преобразования А подбирается так, чтобы результирующая ковариационная матрица К х была равна заданной. При ее определении используется соотношение (1.26).
При из (1.26) получаем следующее уравнение относительно А:
Это уравнение имеет бесчисленное множество решений. Если искать А в виде треугольной матрицы вида
то из (2.83)получим n(n+1)/2 уравнений для элементов этой матрицы, которые можно решить рекуррентно. Результатом являются следующие выражения для элементов матрицы А:
где - элементы заданной корреляционной матрицы .
Пример. Пусть х - двумерный вектор с корреляционной матрицей
Найдем матрицу А, такую, что
где -некоррелированный вектор с .
С помощью соотношений (2.84) находим ац т. е.
В ряде случаев требуется получать реализации случайной величины, распределение которой не является ни равномерным, ни га-уссовским. Наиболее распространенным способом моделирования в данном случае является нелинейное преобразование реализаций, получаемых с помощью датчика равномерно распределенных чисел.
Задача определения нелинейного преобразования y=f(x), связывающего случайные величины х и у с заданными плотностями распределения р(х) и р(у) (плотность р(х) -равномерная), является обратной по отношению к задаче определения распределения нелинейной функции случайной величины, рассмотренной в разд. 1.1. Если распределение р(х) - равномерное, то из соотношения (1.32) имеем , откуда при монотонно возрастающей функции получаем
где F (у) - интегральная функция распределения вероятностей величины у.
Функция является обратной по отношению к искомой функции f(x). Таким образом, определение искомого нелинейного преобразования y = f(x) сводится к нахождению по заданной плотности р(у) интегральной функции F(y) и последующему решению уравнения F (у) =х относительно у.
Пример. Пусть
Тогда в интервале (0, 1) имеем xF(y)=y 2 , откуда ,т. е. .
Иной подход может быть применен в тех случаях, когда требуется получать реализации случайной величины у по имеющейся ее гистограмме или когда распределение р(у) имеет сложную форму, которую целесообразно аппроксимировать ступенчатой зависимостью.
Пусть интервал [у 0 , у п ] практически возможных значений случайной величины у, имеющей распределение р(у), разбит на п участков , в пределах каждого из которых плотность р(у) можно полагать равномерной. Вероятность попадания в каждый интервал
причем . При использовании такой аппроксимации р(у)
реализацию можно определить в результате двукратного обращения к датчику равномерно распределенных псевдослучайных чисел. При первом обращении разыгрывается исход попадания реализации y i в один из интервалов . Для этого вероятностям P l попадания y i в интервалы ставятся в соответствие интервалы значений равномерно распределенных псевдослучайных чисел из общего диапазона . Попаданию случайного числа х i р.р, получаемого в результате обращения к датчику, в интервал ставится в соответствие попадание реализации y i в интервал . При втором обращении к датчику разыгрывается значение реализации y i как случайной величины, распределенной равномерно в интервале .
Моделирование на ЭВМ реализаций случайных процессов. На АВМ реализации случайных процессов получают с помощью генераторов шума. Так называют электронный прибор, электрическое напряжение на выходе которого является случайным процессом с заданными статистическими характеристиками. Генераторы, используемые при статистическом моделировании управляемого движения летательных аппаратов, генерируют шум с равномерной спектральной плотностью в диапазоне инфранизких частот (от до Гц) и с гауссовским одномерным распределением вероятностей. При статистическом моделировании систем, полоса пропускания которых уже, чем , а именно такими, как правило, являются системы управления летательными аппаратами, шум генераторов можно считать белым. Окрашенные шумы, действующие на изучаемую систему, моделируют на АВМ путем пропускания белого шума через соответствующим образом подобранный формирующий фильтр.
На ЦВМ белый шум моделируют, аппроксимируя его приближенно ступенчатым абсолютно случайным процессом x(t). Реализации последнего вычисляются по следующему правилу. Аргумент процесса - время t -изменяется дискретно с шагом Δt. В пределах каждого шага значение реализации задается заново с помощью датчика гауссовских псевдослучайных чисел
где В - постоянный множитель.
На всем интервале значение остается постоянным. Псевдослучайные числа, получаемые при помощи датчика, попарно некоррелированы друг с другом. Следовательно, корреляция между значениями ступенчатого процесса x(t) в различных интервалах и , отсутствует. Поэтому корреляционная функция данного процесса равна
При отношение . Следовательно, при достаточна малой величине интервала процесс x(t) с корреляционной функцией R x (t), определяемой соотношением (2.85), можно рассматривать в качестве приближенной аппроксимации белого шума с интенсивностью . Точность аппроксимации оказывается тем выше, чем меньше интервал .
При численном интегрировании стохастических дифференциальных уравнений (2.82) на ЦВМ величина интервала , используемого при моделировании белого шума , действующего на систему, не может быть задана меньше шага интегрирования . Следовательно, шаг численного интегрирования должен определяться из условия
где - интервал, при котором ступенчатый абсолютно случайный процесс достаточно точно аппроксимирует белый шум; - шаг численного интегрирования, обеспечивающий приемлемую точность вычислений при избранном методе численного интегрирования системы (2.82).
Эксперименты на ЦВМ показывают, что при всех методах численного интегрирования , поэтому для обеспечения аппроксимации белого шума ступенчатым процессом интегрирование системы (2.82) должно вестись с шагом
Среди всех методов численного интегрирования затраты машинного времени на один шаг интегрирования являются наименьшими при интегрировании по методу Эйлера:
Вследствие этого данный метод и следует использовать при статистическом моделировании систем, беря , а коэффициент В рассчитывать по формуле
где - интенсивность белого шума, действующего на систему.
Проведение статистического моделирования и обработка его результатов. Составив программу моделирования исследуемой динамической системы на ЦВМ или набрав схему моделирования на АВМ, с их помощью получают необходимое число реализаций выходных координат исследуемой системы. Обработка результатов^ моделирования может проводиться или при моделировании, или после его завершения с использованием методов математической: статистики . В зависимости от конкретной цели статистического моделирования результатами обработки могут быть оценки математических ожиданий, дисперсий, взаимных корреляционных моментов, корреляционных функций и других статистических характеристик выходных координат системы. Точность оценок будет тем выше, чем большее число реализаций будет статистически обработано. Соотношения для расчета доверительных интервалов и доверительных вероятностей оценок различных параметров в зависимости от числа реализаций, используемых для их получения, приводятся в книгах .
Если исследуемая система и действующие на нее возмущения таковы, что рассматриваемая выходная переменная является эргодическим стационарным процессом, то при моделировании достаточно ограничиться получением одной длинной реализации это» переменной. В иных случаях требуется получать и обрабатывать множество реализаций выходных координат.
МЕТОДЫ ОПРЕДЕЛЕНИЯ ОЦЕНОК СОСТОЯНИЯ ЛЕТАТЕЛЬНЫХ АППАРАТОВ
3.1. ЗАДАЧА ОЦЕНИВАНИЯ КАК ЧАСТНЫЙ СЛУЧАЙ СТАТИСТИЧЕСКОГО РЕШЕНИЯ. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ
Сформулируем задачу построения оценок. Рассмотрим случайный вектор X, плотность распределения которого имеет известную математическую форму, но содержит некоторое число неизвестных параметров. Задана выборка измеренных значений компонент этого вектора, в дальнейшем называемая вектором измерений У.
Если, например, измерены N раз т компонент n-мерного вектора X, то вектор Y будет включать N×m компонент. Вектор Y также является случайным, так как содержит так называемые ошибки измерения , плотность распределения которых считается известной. Требуется, используя вектор измерения У, получить оценки неизвестных параметров плотности распределения X и определить точность этих оценок.
Важно уметь сравнивать свойства различных оценок одного и того же параметра и, в частности, находить оценки максимальной точности. Точность оценок определяем на основе статистических характеристик отклонений оценок от неизвестных «истинных значений» оцениваемых параметров. Плотность распределения X, характеризуемую истинными значениями оцениваемых параметров, называем «истинной».
Данная постановка задачи определения оценок называется статистической и является в настоящее время наиболее широко распространенной в технических задачах. В то же время существуют и другие постановки задач оценивания, когда нельзя сделать никаких предположений о распределении оцениваемой величины. Подобная ситуация рассматривается отдельно.
Вернемся к статистической задаче оценивания. Введем некоторые определения.
Функцию значений оцениваемой величины, т. е. функцию измерений, в дальнейшем будем называть статистикой. Простейшей статистикой является, таким образом, сам вектор измерений У. Оценка случайного вектора X, полученная на основе измерений У, т. е. (Y), также является статистикой. Если статистика содержит.всю необходимую эмпирическую информацию для построения распределения X, то она называется достаточной.
Если оценка сходится по вероятности к оцениваемой величине X при неограниченном возрастании объема выборки, т. е. размерности вектора У, то она называется состоятельной.
Оценка вектора X -функция случайных аргументов. Поэтому для сравнения оценок между собой и выбора наилучшей необходимо рассматривать статистические характеристики функции потерь, так называемые функции риска.
Таких функций можно построить несколько. Наиболее употребительные функции риска следующие.
1. Средний или априорный риск:
где р(х, у) -плотность совместного распределения вероятностей векторов X и У.
Интегрирование в (3.3) ведется по области всех возможных значений X и У. В дальнейшем в подобных случаях не будем указывать пределов интегрирования; х я у - значения случайных векторов X и У. Записью (у) в (3.3) подчеркивает то обстоятельство, что оценка рассматривается как функция у. Если оценка (у) минимизирует функцию риска (3.3), то она называется оптимальной в смысле среднего риска. Средний риск (3.3) R( ) может быть представлен в виде
, максимизирующая или, что то же самое, , называется оценкой максимума апостериорной вероятности, а сам метод оценивания"- методом максимума апостеориорной вероятности.2. Байесовский риск:
где p(x/Y) -апостериорная плотность вероятностей значений X . при заданном (фиксированном) Y, р(х) -априорная плотность вероятностей вектора X, т. е. существующая до опыта, в котором реализовался какой-то вектор у. Таким образом, байесовский риск в силу структуры формулы Байеса (1.9) зависит не только от оценки, но и от априорной плотности вероятностей р(х), что и отражено в записи . Оценка , минимизирующая функцию риска (3.4), называется оптимальной в байесовском смысле или просто ^байесовской. Доказано , что для функции потерь вида (3.1) байесовская оценка минимизирует одновременно функции риска (3.3) и (3.4). Алгоритмы оценивания, обеспечивающие получение байесовских оценок, принято называть байесовскими.
3. Условный риск:
Эта функция риска характеризует ошибки оценки при заданном (фиксированном) значении оцениваемого вектора X. Между условным и средним риском существует связь:
В (3.5) и (3.6) р(у/Х) и р(х) - соответственно условная плотность вероятностей вектора Y и априорная плотность вероятностей вектора X. На основе плотности вероятностей p(y/X) может быть построена оценка максимума правдоподобия. Это оценка, которая максимизирует так называемую функцию правдоподобия. В качестве функции правдоподобия в простейшем случае может быть выбрана функция р(у/Х), в которую подставлены фактические значения измерений у. Для построения р(у/Х) не обязательно знать вид плотности распределения р(х), т. е. вид априорной плотности вероятностей вектора X. X, X на множестве .
Можно также сказать, что минимаксная оценка является байесовской при априорном распределении X, являющемся наименее благоприятным для задачи оценивания. Поясним последнюю мысль-подробнее.
Байесовский риск может быть определен в том случае, если известен вид априорной плотности вероятностей р(х) вектора X, так как в силу (1.9) условная плотность вероятностей
где р(у) -плотность вероятностей вектора Y.
В том случае, когда плотность вероятностей р(х) не существует, можно условно поставить в соответствие каждому X из некоторое априорное распределение , принадлежащее некоторому классу распределений .
Оказывается, для функции потерь вида (3.1) справедливо равенство :
т. е. минимаксная оценка тождественна байесовской оценке вычисленной для априорного распределения, максимизирующего байесовский риск на . Таким образом устанавливается связь между байесовской и минимаксной оценками.
3.2. БАЙЕСОВСКИЕ АЛГОРИТМЫ ОЦЕНИВАНИЯ
Как показывает практика, сложность реализации алгоритмов оценивания зависит, во-первых, от вида математической модели движения оцениваемой динамической системы и измерений и, во-вторых, от способа проведения измерений, т. е. от того, как поступают измерения, непрерывно или дискретно. Рассмотрим линейные (для линейных моделей), квазилинейные (для линеаризованных моделей) и нелинейные (для нелинейных моделей) байесовские алгоритмы. Как правило, будем полагать, что измерительная информация поступает дискретно и соответствующие алгоритмы имеют рекуррентную форму. Эта форма алгоритма наиболее удобна для реализации на ЭВМ, когда поступающие векторы измерений обрабатываются поочередно. В некоторых случаях удобно обобщить полученные результаты на случай непрерывных измерений.
При исследовании операций часто приходится сталкиваться с системами, предназначенными для многоразового использования при решении однотипных задач. Возникающие при этом процессы получили название процессов обслуживания, а системы - систем массового обслуживания (СМО). Примерами таких систем являются телефонные системы, ремонтные мастерские, вычислительные комплексы, билетные кассы, магазины, парикмахерские и т.п.Каждая СМО состоит из определенного числа обслуживающих единиц (приборов, устройств, пунктов, станций), которые будем называть каналами обслуживания. Каналами могут быть линии связи, рабочие точки, вычислительные машины, продавцы и др. По числу каналов СМО подразделяют на одноканальные и многоканальные.
Заявки поступают в СМО обычно не регулярно, а случайно, образуя так называемый случайный поток заявок (требований). Обслуживание заявок, вообще говоря, также продолжается какое-то случайное время. Случайный характер потока заявок и времени обслуживания приводит к тому, что СМО оказывается загруженной неравномерно: в какие-то периоды времени скапливается очень большое количество заявок (они либо становятся в очередь, либо покидают СМО необслуженными), в другие же периоды СМО работает с недогрузкой или простаивает.
Предметом теории массового обслуживания является построение математических моделей, связывающих заданные условия работы СМО (число каналов, их производительность, характер потока заявок и т.п.) с показателями эффективности СМО, описывающими ее способность справляться с потоком заявок.
В качестве показателей эффективности СМО используются: среднее (здесь и в дальнейшем средние величины понимаются как математические ожидания соответствующих случайных величин) число заявок, обслуживаемых в единицу времени; среднее число заявок в очереди; среднее время ожидания обслуживания; вероятность отказа в обслуживании без ожидания; вероятность того, что число заявок в очереди превысит определенное значение и т.п.
СМО делят на два основных типа (класса)
: СМО с отказами и 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).
Многие операции, которые приходится анализировать при выборе оптимального решения, развиваются как случайные процессы, зависящие от ряда случайных факторов.
Для математического описания многих операций, развивающихся в форме случайного процесса, может быть с успехом применен математический аппарат, разработанный в теории вероятностей для так называемых марковских случайных процессов.
Поясним понятие марковского случайного процесса.
Пусть имеется некоторая система S, состояние которой меняется с течением времени (под системой S может пониматься все что угодно: промышленное предприятие, техническое устройство, ремонтная мастерская и т. д.). Если состояние системы S меняется во времени случайным, заранее непредсказуемым образом, говорят, что в системе S протекает случайный процесс.
Примеры случайных процессов:
флуктуации цен на фондовом рынке;
обслуживание клиентов в парикмахерской или ремонтной мастерской;
выполнение плана снабжения группы предприятий и т. д.
Конкретное протекание каждого из этих процессов зависит от ряда случайных, заранее непредсказуемых факторов, таких как:
поступление на фондовый рынок непредсказуемых известий о политических изменениях;
случайный характер потока заявок (требований), поступающих со стороны клиентов;
случайные перебои в выполнении плана снабжения и т. д.
ОПРЕДЕЛЕНИЕ. Случайный процесс, протекающий в системе, называется марковским (или процессом без последствия ), если он обладает следующим свойством: для каждого момента времени t 0 вероятность любого состояния системы в будущем (при t > t 0) зависит только от ее состояния в настоящем (при t = t 0) и не зависит от того, когда и каким образом система пришла в это состояние (т. е. как развивался процесс в прошлом).
Другими словами, в марковском случайном процессе будущее развитие его зависит только от настоящего состояния и не зависит от “предыстории” процесса.
Рассмотрим пример. Пусть система S представляет собой фондовый рынок, который уже существует какое-то время. Нас интересует, как будет работать система в будущем. Ясно, по крайней мере в первом приближении, что характеристики работы в будущем (вероятности падения цен конкретных акций через неделю) зависят от состояния системы в настоящий момент (здесь могут вмешаться самые различные факторы типа решений правительства или результатов выборов) и не зависят от того, когда и как система достигла своего настоящего состояния (не зависят от характера движения цен на эти акции в прошлом).
На практике часто встречаются случайные процессы, которые, с той или другой степенью приближения можно считать марковскими.
Теория марковских случайных процессов имеет широкий спектр различных приложений. Нас будет интересовать главным образом применение теории марковских случайных процессов к построению математических моделей операций, ход и исход которых существенно зависит от случайных факторов.
Марковские случайные процессы подразделяются на классы в зависимости от того, как и в какие моменты времени система S" может менять свои состояния.
ОПРЕДЕЛЕНИЕ. Случайный процесс называется процессом с дискретными состояниями, если возможные состояния системы s x , s 2 , s v ... можно перечислить (пронумеровать) одно за другим, а сам процесс состоит в том, что время от времени система S скачком (мгновенно) перескакивает из одного состояния в другое.
Например, разработку проекта S осуществляют совместно два отдела, каждый из которых может совершить ошибку. Возможны следующие состояния системы:
5, - оба отдела работают нормально;
s 2 - первый отдел совершил ошибку, второй работает нормально;
s 3 - второй отдел совершил ошибку, первый работает нормально;
s 4 - оба отдела совершили ошибку.
Процесс, протекающий в системе, состоит в том, что она случайным образом в какие-то моменты времени переходит («перескакивает») из состояния в состояние. Всего у системы четыре возможных состояния. Перед нами - процесс с дискретными состояниями.
Кроме процессов с дискретными состояниями существуют случайные процессы с непрерывными состояниями : для этих процессов характерен постепенный, плавный переход из состояния в состояние. Например, процесс изменения напряжения в осветительной сети представляет собой случайный процесс с непрерывными состояниями.
Мы будем рассматривать только случайные процессы с дискретными состояниями.
При анализе случайных процессов с дискретными состояниями очень удобно пользоваться геометрической схемой - так называемым графом состояний. Граф состояний геометрически изображает возможные состояния системы и ее возможные переходы из состояния в состояние.
Пусть имеется система S с дискретными состояниями:
Каждое состояние будем изображать прямоугольником, а возможные переходы (“перескоки”) из состояния в состояние - стрелками, соединяющими эти прямоугольники. Пример графа состояния приведен на рис. 4.1.
Заметим, что стрелками отмечаются только непосредственные переходы из состояния в состояние; если система может перейти из состояния s 2 в 5 3 только через s y то стрелками отмечаются только переходы s 2 -> и л, 1 -> 5 3 , но не s 2 -» s y Рассмотрим несколько примеров:
1. Система S - фирма, которая может находиться в одном из пяти возможных состояний: s ] - работает с прибылью;
s 2 - утратила перспективу развития и перестала приносить прибыль;
5 3 - стала объектом для потенциального поглощения;
s 4 - находится под внешним управлением;
s 5 - имущество ликвидируемой фирмы продается на торгах.
Граф состояний фирмы показан на рис. 4.2.
Рис. 4.2
- 2. Система S - банк, имеющий два отделения. Возможны следующие состояния системы:
- 5, - оба отделения работают с прибылью;
s 2 - первое отделение работает без прибыли, второе работает с прибылью;
5 3 - второе отделение работает без прибыли, первое работает с прибылью;
s 4 - оба отделения работают без прибыли.
Предполагается, что улучшение состояния не происходит.
Граф состояний представлен на рис. 4.3. Отметим, что на графе не показан возможный переход из состояния s ] непосредственно в s 4 , который осуществится, если банк сразу будет работать в убыток. Возможностью такого события можно пренебречь, что и подтверждает практика.
Рис. 4.3
3. Система S - инвестиционная компания, состоящая из двух трейдеров (отделов): I и II; каждый из них может в какой-то момент времени начать работать в убыток. Если это происходит, то руководство компании немедленно принимает меры для восстановления прибыльной работы отдела.
Возможные состояния системы: s - деятельность обоих отделов прибыльна; s 2 - первый отдел восстанавливается, второй работает с прибылью;
s 3 - первый отдел работает с прибылью, второй восстанавливается;
s 4 - оба отдела восстанавливаются.
Граф состояний системы показан на рис. 4.4.
4. В условиях предыдущего примера деятельность каждого трейдера перед тем, как он начнет восстанавливать прибыльную работу отдела, подвергается изучению руководством фирмы в целях принятия мер по ее улучшению.
Состояния системы будем для удобства нумеровать не одним, а двумя индексами; первый будет означать состояния первого трейдера (1 - работает с прибылью, 2 - его деятельность изучается руководством, 3 - восстанавливает прибыльную деятельность отдела); второй - те же состояния для второго трейдера. Например, s 23 будет означать: деятельность первого трейдера изучается, второй - восстанавливает прибыльную работу.
Возможные состояния системы S:
s u - деятельность обоих трейдеров приносит прибыль;
s l2 - первый трейдер работает с прибылью, деятельность второго изучается руководством компании;
5 13 - первый трейдер работает с прибылью, второй восстанавливает прибыльную деятельность отдела;
s 2l - деятельность первого трейдера изучается руководством, второй работает с прибылью;
s 22 - деятельность обоих трейдеров изучается руководством;
- 5 23 - работа первого трейдера изучается, второй трейдер восстанавливает прибыльную деятельность отдела;
- 5 31 - первый трейдер восстанавливает прибыльную деятельность отдела, второй работает с прибылью;
- 5 32 - прибыльная деятельность отдела восстанавливается первым трейдером, работа второго трейдера изучается;
- 5 33 - оба трейдера восстанавливают прибыльную работу своего отдела.
Всего девять состояний. Граф состояний показан на рис. 4.5.