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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вычислительные технологии

Том 13, Специальный выпуск 5, 2008

Исследование полумарковского потока событий

А. А. Назаров, С. В. Лопухова Томский государственный университет, Россия e-mail: nazarov@f pmk. tsu. ru, lopuchovasv@mail. ru

И.Р. Гарайшина

Филиал Кемеровского государственного университета в г. Анжеро-Судженске, Россия e-mail: [email protected]

In the submitted work, the semimarkovian process is considered. Limiting model is considered. Results of analytical treatment of limiting model are compared with results, obtained by the asymptotical method.

Введение

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

1. Математическая модель

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

t\ < ¿2 < ■ ■ ■

случайных величин tm - моментов наступления событий в потоке.

Пусть задана полумарковская матрица A(x) с элемента ми Aklk2 (x), Матрн ца P = lim A(x) является стохастической, поэтому при заданном начальном распределении

она определяет некоторую цепь Маркова k (tm) с дискретным временем, которую будем называть вложенной в полумарковский поток цепью Маркова,

© Институт вычислительных технологий Сибирского отделения Российской академии наук, 2008.

А. А. Назаров, С. В. Лопухова, И. Р. Гарайшина

Случайный поток однородных событий будем называть полумарковским, если вероятностный закон формирования последовательности (1) определяется начальным распределением и равенствами

Ак1к2 (х) = Р {к(Ьт+1) = к2, Ьт+1 - Ьт < х ^^т) = к\ }

при всех т > 1.

Обозначим п(Ь) число событий полу марко веко го потока, наетуп ивших за время Ь па интервале .

Задачей исследования данной работы является установление распределения вероятностей Р(п, Ь) = Р{п(Ь) = п} при стационарном функционировании эргодичеекой цепи Маркова к (1т). Очевидно, процесс п(Ь) - немарковский, поэтому определим еще два случайных процесса: г(Ь) - длину интервала от момента времени Ь до момента наступления очередного события в рассматриваемом потоке, к(Ь) - непрерывный слева процесс с непрерывным временем, значение которого на интервале (Ьт,Ьт+1] постоянны и определяются равенствами к (Ь) = к (Ьт+1). В силу сделанных определений случайный процесс {к(Ь), п(Ь), г(Ь)} является трехмерным марковским процессом с непрерывным временем.

Заметим, что случайный процесс к(Ь) не является полумарковским в классическом определении , так как полумарковский процесс Б(Ь) непрерывен справа и, как указано в , для его переходных вероятностей не существует дифференциальных эволюционных уравнений Колмогорова, в то время как предложенный выше процесс {к(Ь), п(Ь), г(Ь)} - марковский, поэтому для его распределения вероятностей

Р (к, п, г,Ь) = Р {к(Ь) = к, п(Ь) = п, г(Ь) < г} (2)

нетрудно составить систему дифференциальных уравнений Колмогорова дР (к,п,г,Ь) дР (к,п,г,Ь) дР (к,п, 0,Ь) ^ дР (и,п - 1,0,Ь)

^ дГ (и,1Ь - 1, 0,Ь) А (\ 2-^-

дЬ дг дг ^ дг

Обозначим

Н(к, и, г, г) = ^ е"иПР(к,п,г,Ь),

где ] = ¡~ ~~ мнимая единица. Для этих функций из системы дифференциальных уравнений Колмогорова можно записать

дН (к,и,г,Ь) дН (к,и,г,Ь) дН (к, и, 0,Ь) ,и ^ дН (и, и, 0,Ь)

дЬ дг дг ^ дг

Обозначим Н (и,г,Ь) = {Н (1,и,г,Ь) ,Н (2,и,г,Ь),...} строку вектор-функции, тогда систему уравнений (3) перепишем в матричном виде

дН{и,г,г) _ дН{и,г,г) дН{и,0,г) Мц,г ч п т

дг дг + дг 1 [) "" [ }

решение которой удовлетворяет начальному условию H(u,z, 0) = R(z), где I - единичная матрица, а стационарное распределение R(z) двумерного марковского процесса {k(t), z(t)} является решением задачи Коши

<Ш = <Ш(1-Мг)),

и определяется равенством R{z) = seiт / (Р - A(x))dx, где aei = Здесь г - вектор-

строка стационарного распределения вероятностей значений вложенной цепи Маркова

k(tm); E - единичный вектор-столбец и матрица A = (P - A(x))dx.

2. Допредельная модель

Пусть имеем дифференциальное уравнение (4), решение H (u,z,t) которого удовлетворяет начальному условию H(u, z, 0) = R(z). Тогда преобразование Фурье - Стилтьесса

ф>(u,a,t) = / ejaz dz H (u, z, t) вектор-функ ции H (u,z,t) удовлетворяет уравнению

дф(и,а,Ь) . . дН (и, 0,Ь) , .*. . гЛ, .

т = ~заф{щ а, +-(е?иА*{а) - /) (5)

и начальному условию

ф(и,а, 0) = R*(a) = ^ ё>а2

где А*(а) = J е>а"2dA(z). Решение уравнения (5) имеет вид о

ф(и, а,1) = е~заЬ [ II*{а) + I (¿>иА*{а) - I) dт ] . (6)

Устремив Ь в бесконечность в выражении (6), получим преобразование Фурье по т

дН (и, 0,т) ^ ^ " л

от вектор-функции---. Выполнив обратное преобразование Фурье, определим,

I e-j*A*{aj) 1 da.

А. А. Назаров, С. В. Лопухова, И. Р. Рарайшшиа

Теперь равенство (6) можно записать в виде

ф(ща,г) = е-аЬ Я*(а) +

+ - / е]ат I е~зутК*(у) (/ - е>иА*(у)) 1 Ау (е"иА*(а) - /) <*г). (7)

Зная, что Н(и, ж,г) = Н(и,г) = ф(и, 0,1), получим выражение для вектор-функции Н (и,г):

Тогда распределение вероятностей Р(п, г) числа событий, наступивших за время г, явля-

ции Н(и,Ь) = МеЭип(Ь = Н(и,Ь)Е, оно имеет вид

1 С а1 Г 1 - е-™Ь

Р(п,1) = - е~зипНШ)Е(1и = - / -^-5

I - А* (у) А*(у)п-1Ейу, (8)

I - А* (у) Е<1у

Заключение

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

МеГап(1) = ^«(ге^+^ае^+^аез*)

где коэффициенты 831, а2, аз3 для полумарковского потока определяются аналогично тому, как это сделано в работах . Полученные равенства (8) определяют распределение вероятностей Р(п,г) числа событий, наступивших в стационарном полумарковском потоке, заданном полумарковской матрицей А(х) и ее преобразованием А*(х) Фурье - Стилтьесса, Численная реализация формул (8) позволяет находить численные значения вероятностей Р(п, г) для достаточно широкого клаееа матриц А* (х) и значений г. Но возможности численной реализации ограничены вычислительными ресурсами. Для достаточно больших значений г естественно применить метод асимптотического анализа полумарковского потока аналогично тому, как это выполнено для потока марковского восстановления в работе и просеянного потока марковского восстановления в работе . Наличие численного алгоритма (8) позволяет определить область применения асимптотических результатов. Для рассмотренных потоков с тремя состояниями вложенной цепи Маркова расстояние Колмогорова - Смирнова между распределениями,

полученными асимптотически и по формулам (8), не превосходит 2-3 % для определенных значений t = Т, это позволяет утверждать, что при t > Т эффективно применение асимптотических результатов, а при t < Т целесообразно использовать формулы (8), полученные в данной работе.

Список литературы

Королюк B.C. Стохастические модели систем. Киев: Наук, думка, 1989. 208 с.

Назаров A.A., Лопухова C.B. Исследование потока марковского восстановления асимптотическим методом второго порядка // Матер. Междунар. науч. конф. "Математические методы повышения эффективности функционирования телекоммуникационных сетей". Гродно, 2007. С. 170-174.

Лопухова C.B. Исследование полумарковского потока асимптотическим методом третьего порядка // Матер. VI Междунар. научно-практ. конф. "Информационные технологии и математическое моделирование". Томск: Изд-во Том. ун-та, 2007. Ч. 2. С. 30-34.

Процесс работы СМО представляет собой случайный процесс. Под случайным (вероятностным или стохастическим) процессом понимается процесс изменения во времени состояния какой-либо системы в соответствии с вероятностными закономерностями.

Процесс называется процессом с дискретными состояниями, если его возможные состояния S1, S2, S3… можно заранее перечислить, а переходы системы из состояния в состояние происходит мгновенно (скачком). Процесс называется процессом с непрерывным временем, если моменты возможных переходов системы из состояния в состояние не фиксированы заранее, а случайны.

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

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

Пример марковского процесса: система S - счетчик в такси. Состояние системы в момент t характеризуется числом километров, пройденных автомобилем до данного момента. Пусть в момент t0 счетчик показывает S0. Вероятность того, что в момент t>t0 счетчик покажет то или иное число километров (точнее соответствующее число рублей) S1 зависит от S0, но не зависит от того, в какие моменты времени изменялись показания счетчика до момента t0.

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

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

Рисунок 1 - Граф состояний

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

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

Примерами могут быть:

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

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

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

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

Поток событий называется потоком без последействия, если для любых двух непересекающихся участков времени и _ число событий, попадающих на один из них, не зависит от числа событий, попадающих на другие. Например, поток пассажиров, входящих в метро, практически не имеет последствия. А, скажем, поток покупателей, отходящих с покупками от прилавка, уже имеет последствия (хотя бы потому, что интервал времени между отдельными покупателями не может быть меньше, чем минимальное время обслуживания каждого из них).

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

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

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

Рассмотрим на оси времени простейший поток событий как неограниченную последовательность случайных точек. (Рис. 2)

Рисунок 2 - Поток событий

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

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

В частности, вероятность того, что за время ф не произойдет ни одного события (m = 0), равна

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

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

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

Плотность вероятности случайной величины есть производная ее функции распределения:

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

и обратно по величине интенсивности потока л.

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

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

Для простейшего потока с интенсивностью л вероятность попадания на элементарный (малый) отрезок времени?t хотя бы одного события потока равна согласно

Транскрипт

1 АН Моисеев АА Назаров Асимптотический анализ высокоинтенсивного полумарковского потока 9 УДК 5987 АН Моисеев АА Назаров Асимптотический анализ высокоинтенсивного полумарковского потока событий Представлено исследование высокоинтенсивного полумарковского потока событий Показано что для рассматриваемого потока распределение вероятностей числа событий наступивших за фиксированный интервал времени при условии неограниченного роста интенсивности потока может быть аппроксимировано нормальным распределением В работе получены параметры этого распределения Ключевые слова: высокоинтенсивный поток событий полумарковский поток асимптотический анализ Одним из базовых элементов систем и сетей массового обслуживания является входящий поток заявок Современные телекоммуникационные сети и системы распределенной обработки информации предполагают высокую пропускную способность каналов передачи информации Таким образом в этих системах количество пакетов данных поступающих на обработку в единицу времени очень высоко В терминах теории массового обслуживания в таких случаях говорят о высокой интенсивности входящего потока В частности в работе модель высокоинтенсивного потока применяется для моделирования потока входящих сообщений многофазной системы распределенной обработки данных В работах были изучены свойства высокоинтенсивных рекуррентных MMPP- и MAPпотоков В настоящей же работе представлен анализ свойств высокоинтенсивного полумарковского (Semi-Markovian или SM-) потока как наиболее общей модели потоков событий Математическая модель Рассмотрим полумарковский поток однородных событий заданный следующим образом Пусть {ξ n τ n } стационарный двумерный марковский процесс с дискретным временем Здесь ξ n дискретная компонента принимающая значения от до K τ n непрерывная компонента принимающая неотрицательные значения Будем полагать что эволюция процесса определяется элементами так называемой полумарковской матрицы A (x) = { Ak ν } k ν= следующим K образом: x Akν (x) = P ξ n+ =ν τ n+ < ξ n = k N Здесь N некоторая большая величина которая введена искусственно чтобы явным образом подчеркнуть малость величин τ n В теоретических исследованиях будем полагать N и таким образом τ n На практике полученные результаты можно использовать для аппроксимации соответствующих величин при достаточно больших значениях N (в условии высокой интенсивности потока) Пусть в момент времени t = произошло изменение состояния процесса {ξ n τ n } Последовательность моментов времени t n определяемая рекуррентным выражением tn+ = tn+τ n+ для n = называется полумарковским потоком случайных событий определяемым полумарковской матрицей A(x) Процесс ξ n =ξ(t n) называют вложенной в полумарковский поток цепью Маркова Поскольку средняя длина интервалов τ n обратно пропорциональна N то при N интенсивность наступления событий в таком потоке будет неограниченно расти Такой поток событий будем называть высокоинтенсивным полумарковским или HISM-потоком (от High-Intensive Semi- Markovian) Ставится задача нахождения числа событий m(t) наступивших в этом потоке в течение интервала времени (t) Вывод уравнений Колмогорова Пусть z(t) длина интервала времени от момента t до момента наступления следующего события в потоке; k(t) случайный процесс значения которого на каждом из интервалов = () Отсюда получаем матричное дифференциальное уравнение относительно функции R(z): R (z) = R ()[ I A (z) ] (3) граничное условие для которого при z имеет вид R () = λr (4) где λ некоторый коэффициент вектор-строка r есть стационарное распределение состояний вложенной цепи Маркова Этот вектор является решением уравнения Колмогорова r= r P где P= lim A (z) есть стохастическая матрица определяющая вероятности переходов вложенной цепи z Маркова Таким образом решение уравнения (3) имеет вид z R() z = R ()[ I A () x ] dx (5) Пусть R= R () есть стационарное распределение значений полумарковского процесса k(t) тогда при z из (5) получаем R= R ()[ I A(x) ] dx=λ r[ I A(x) ] dx=λr [ P A(x) ] dx=λra (6) где A матрица с элементами Akν = [ Pkν Akν(x) ] dx Умножая левую и правую части равенства (6) на единичный вектор-столбец E получим RE = =λrae откуда находим значение коэффициента λ: λ= (7) rae Доклады ТУСУРа 3 (9) сентябрь 3

3 АН Моисеев АА Назаров Асимптотический анализ высокоинтенсивного полумарковского потока jum Введем обозначение Hkuzt () = e Pkmzt () где j = мнимая единица а u некоторая переменная Умножая () на e jum и суммируя по m от до получаем m= Hkuzt () Hkuzt () Hku (t) K ju Hku (t) = + e Aν k (z) N ν= С учетом обозначения в виде вектор-строки H(u z t) = {H(u z t) H(K u z t)} данное уравнение примет вид H(uzt) H(uzt) H(u t) ju = + e A(z) I (8) N Дифференциальное матричное уравнение (8) будем решать асимптотически методом в условии неограниченно растущей интенсивности λn рассматриваемого полумарковского потока те при N Асимптотика первого порядка Введем обозначения N =ε u= ε w H(uzt) = F (wzt ε) Из (8) получим F(wzt ε) F(wzt ε) F(w t ε) jwε ε = + e A(z) I (9) Теорема Асимптотическое решение F(wzt) = lim F (wzt ε) уравнения (9) имеет вид ε () () jw λ F wzt = R ze t () где R(z) определяется выражением (5) Доказательство Выполним в (9) предельный переход ε получим уравнение F(wzt) F(w t) = + [ A(z) I ] которое имеет вид аналогичный () Следовательно функцию F (w z t) можно представить в виде F(wzt) = R (z) Φ(wt) () где Φ (w t) некоторая скалярная функция Выполним в (9) предельный переход z и просуммируем все компоненты этого уравнения (для этого умножим справа обе его части на единичный вектор-столбец E) Получим F(w t ε) F(w t ε) ε E= e P I E Подставим сюда выражение () воспользуемся разложением e = + jε w+ O(ε) поделим обе части на ε и произведем предельный переход ε: Φ(wt) RE = jwr () PE Φ(wt) откуда с учетом (4) получаем дифференциальное уравнение относительно функции Φ (w t): Φ(wt) = jwλφ (wt) Решая это уравнение при начальном условии Φ (w) = получаем решение jwλt Φ (wt) = e Подставим это выражение в () получим () Теорема доказана ju Nt Асимптотика второго порядка Выполним в (8) замену H(uzt) = H (uzte) λ: H(uzt) H(uzt) H(u t) ju + juλ H(u z t) = + e A(z) I () N Введем обозначения N =ε u= ε w H(uzt) = F (wzt ε) (3) Доклады ТУСУРа 3 (9) сентябрь 3

4 УПРАВЛЕНИЕ ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА И ИНФОРМАТИКА Тогда () перепишется в виде F(wzt ε) F(wzt ε) F(w t ε) ε + λf (wzt ε) = + e A(z) I (4) Теорема Асимптотическое решение F(wzt) = lim F (wzt ε) уравнения (4) имеет вид ε (jw) F (wzt) = R (z)exp (λ+κ) t (5) где R(z) определяется выражением (5) κ= fe (6) вектор-строка f удовлетворяет системе линейных алгебраических уравнений f I P =λ rp R λ a (7) f AE= a = rae A = x da (x) Доказательство Выполним в (4) предельный переход ε получим уравнение F(wzt) F(w t) = + [ A(z) I ] которое имеет вид аналогичный () Следовательно функцию F (w z t) можно представить в виде F(wzt) = R (z) Φ(wt) (8) где Φ (w t) некоторая скалярная функция Решение уравнения (4) будем искать в виде разложения F(wzt ε) =Φ (wt) R(z) + jε wf (z) + O(ε) (9) где f(z) некоторая вектор-функция (строка) Подставляя это выражение в (4) и применяя разложение e = + jε w+ O(ε) после некоторых преобразований получим { } λφ (wt) R() z=φ (wt) R() z+ f () z+ R() A() z I + R() A() z+ f () A() z I+ A () z + O(ε) Учитывая (3) (4) поделив обе части на jεw и сокращая Φ (w t) получаем λ R(z) = f (z) +λ ra(z) + f ()[ A(z) I ] + O(ε) Отсюда при ε получаем дифференциальное уравнение относительно неизвестной векторфункции f(z) f (z) = f ()[ I A(z) ] λ[ ra(z) R (z) ] интегрируя которое при начальном условии f() = получаем выражение z f(z) = { f ()[ I A(x) ] λ[ ra(x) R (x) ]} dx () Будем искать f(z) в классе функций удовлетворяющих условию lim { f ()[ I A(x) ] λ[ ra(x) R (x) ]} = x Отсюда получаем f ()[ I P] λ[ rp R ] = () Вычитая левую часть этого равенства из подынтегрального выражения () с учетом (6) получаем f() = f () A+λrA λ [ R R (x) ] dx () Можно показать что [ R R (x) ] dx= λ ra где A = x da (x) С учетом этого умножая обе части () справа на единичный вектор E получим Доклады ТУСУРа 3 (9) сентябрь 3

5 АН Моисеев АА Назаров Асимптотический анализ высокоинтенсивного полумарковского потока 3 λ a [ f () A f()] E = (3) где a = rae Полагая что f() E = и обозначая f = f () из () и (3) получаем систему уравнений (7) Выполним в (4) предельный переход z и домножим обе части уравнения на E справа получим F(w t ε) F(w t ε) jw (w t) jw jw (w t) ε ε e F ε ε E+ ε λf ε E= P I E= E (e) () 3 Подставим сюда (9) и применим разложение e = + jε w+ + O(ε) получаем Φ(wt) (jεw) 3 ε RE+ λφ (wt) RE =Φ (wt)[ R () + f ()] E jw ε + + O(ε) Приводя подобные сокращая на ε используя обозначение (6) и переходя к пределу при ε получаем следующее дифференциальное уравнение относительно неизвестной функции Φ (w t): Φ(wt) (jw) = Φ(wt) (λ+κ) (jw) решая которое при начальном условии Φ (w) = получаем Φ (wt) = exp (λ+κ) t Подставляя это выражение в (8) получаем (5) Теорема доказана Аппроксимация распределения числа событий наступивших в HISM-потоке Выполняя в (5) замены обратные к (3) и возвращаясь к функции H(u z t) получаем (ju) H(u z t) R (z)exp juλ Nt + (λ+κ) Nt Таким образом характеристическая функция числа событий наступивших в высокоинтенсивном полумарковском потоке в течение времени t удовлетворяет соотношению (ju) hut () = H(u t) E exp juλ Nt+ (λ+κ) Nt То есть при достаточно больших значениях N распределение числа событий наступивших в HISM-потоке за время t может быть аппроксимировано нормальным распределением с математическим ожиданием λnt и дисперсией (λ + κ)nt где λ и κ определяются выражениями (7) и (6) Численные результаты В качестве примера для численных расчетов рассмотрим задачу моделирования событий в высокоинтенсивном полумарковском потоке заданном полумарковской матрицей A(x) третьего порядка записанной в форме A(x) = P * G(x) где P стохастическая матрица; G(x) матрица составленная из некоторых функций распределения; операция * адамарово произведение матриц Будем рассматривать пример когда элементы матрицы G(x) соответствуют функциям гамма-распределения с параметрами формы α kν и масштаба β kν k ν = 3 которые представим в виде матриц α и β соответственно Выберем следующие конкретные значения параметров: P = 3 5 α = 5 4 β = В результате расчетов получили следующие значения параметров: λ 99; κ 96 Для данной задачи было выполнено имитационное моделирование потока при значениях N = 3 и построены эмпирические распределения числа событий в интервалах длины t = Ряды распределений эмпирических данных и соответствующих аппроксимаций для N = и N = представлены графически на рис (для остальных значений N графики практически совпадают и на рисунке становятся неразличимы) Доклады ТУСУРа 3 (9) сентябрь 3

6 4 4 УПРАВЛЕНИЕ ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА И ИНФОРМАТИКА 5 8 N = N = Рис Сравнение полигона относительных частот эмпирического распределения () и аппроксимирующего ряда распределения () Для оценки точности аппроксимации распределения будем использовать расстояние Колмогорова Dq = sup Fq(x) F(x) Здесь F q (x) эмпирическая функция распределения F(x) функция x распределения нормальной случайной величины с найденными выше характеристиками В таблице представлены Зависимость качества аппроксимации от величины N N δ относительные погрешности вычисления математического a δ D D q 8% 6% 464 ожидания δ a и дисперсии δ D а также расстояние Колмогорова D q для рассмотренных случаев 9% 7% % 5% На рис представлен график демонстрирующий % 4% 44 убывание расстояния Колмогорова между эмпирическим и 8% % аналитическим (нормальным) распределениями с ростом значения N D q Можно заметить что уже при 5 N > 3 достигается достаточно высокое качество гауссовской аппроксимации числа событий в рассмотренном высокоинтенсивном полумар- 4 ковском потоке (расстояние Колмогорова не превышает) 3 Рис Изменение расстояния Колмогорова D q в зависимости от интенсивности потока (логарифмическая шкала по N) N Заключение В работе представлено исследование высокоинтенсивного полумарковского потока событий Показано что в условии неограниченного роста его интенсивности распределение числа событий наступивших в данном потоке в течение интервала времени фиксированной длины может быть аппроксимировано нормальным распределением В работе получены параметры этого распределения Рассмотренные числовые примеры демонстрируют применимость полученных асимптотических результатов для HISM-потоков событий Аналогичные результаты были получены ранее и для других типов высокоинтенсивных потоков: рекуррентного MMPP MAP Доклады ТУСУРа 3 (9) сентябрь 3

7 АН Моисеев АА Назаров Асимптотический анализ высокоинтенсивного полумарковского потока 5 Литература Гнеденко БВ Введение в теорию массового обслуживания / БВ Гнеденко ИН Коваленко 4-е изд испр М: Изд-во ЛКИ 7 4 с Грачев ВВ Многофазная модель массового обслуживания системы распределенной обработки данных / ВВ Грачев АН Моисеев АА Назаров ВЗ Ямпольский // Доклады ТУСУРа (6) ч С Moiseev A Investigation of High Intensive General Flow / A Moiseev A Nazarov // Proc of the IV International Conference «Problems of Cybernetics and Informatics» (PCI) Baku: IEEE P Moiseev A Investigation of the High Intensive Markov-Modulated Poisson Process / A Moiseev A Nazarov // Proc Of The International Conference On Application Of Information And Communication Technology And Statistics In Economy And Education (ICAICTSEE-) Sofia: University Of National And World Economy P Моисеев АН Исследование высокоинтенсивного MAP-потока / АН Моисеев АА Назаров // Изв Том политехн ун-та 3 Т 3 С Королюк ВС Стохастические модели систем Киев: Наук думка с 7 Назаров АА Теория вероятностей и случайных процессов: учеб пособие / АА Назаров АФ Терпугов -е изд испр Томск: Изд-во НТЛ 4 с 8 Назаров АА Метод асимптотического анализа в теории массового обслуживания / АА Назаров СП Моисеева Томск: Изд-во НТЛ 6 с 9 Корн Г Справочник по математике для научных работников и инженеров / Г Корн Т Корн М: Наука с Рыков ВВ Математическая статистика и планирование эксперимента: учеб пособие / ВВ Рыков ВЮ Иткин М: МАКС Пресс 38 с Моисеев Александр Николаевич Канд техн наук доцент каф программной инженерии Томского государственного университета (ТГУ) Тел: 8 (38-) Эл почта: Назаров Анатолий Андреевич Д-р техн наук профессор зав каф теории вероятностей и математической статистики ТГУ Тел: 8 (38-) Эл почта: Moiseev AN Nazarov AA Asymptotic analysis of the high-intensive semi-markovian arrival process Investigation of the high-intensive semi-markovian arrival process is presented in the paper It is shown that a distribution of the number of arrivals in the process during some period under asymptotic condition of an infinite growth of the process rate can be approximated by normal distribution The characteristics of the approximation are obtained as well The analytical results are supported by numeric examples Keywords: high-intensive arrival process semi-markovian process asymptotic analysis Доклады ТУСУРа 3 (9) сентябрь 3

СПИСОК ЛИТЕРАТУРЫ. Баласанян С.Ш. Стратифицированная модель для оценки и анализа эффективности функционирования сложных технологических систем со многими состояниями // Известия Томского политехнического

АСИМПТОТИЧЕСКИЙ АНАЛИЗ РАЗОМКНУТОЙ НЕМАРКОВСКОЙ СЕТИ МАССОВОГО ОБСЛУЖИВАНИЯ HIMMPP (GI) K А. Назаров, А. Моисеев Томский государственный университет Томск, Россия [email protected] В работе представлено

ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА 2008 Управление вычислительная техника и информатика 3(4) УДК 6239; 592 СВ Лопухова ИССЛЕДОВАНИЕ ММР-ПОТОКА АСИМПТОТИЧЕСКИМ МЕТОДОМ -го ПОРЯДКА В работе рассматривается

С.А. Матвеев, А.Н. Моисеев, А.А. Назаров. Применение метода начальных моментов 9 УДК 59.87 С.А. Матвеев, А.Н. Моисеев, А.А. Назаров Применение метода начальных моментов для исследования многофазной системы

ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА 7 Управление вычислительная техника и информатика УДК 5987 ТА Карлыханова МЕТОД ПРОСЕЯННОГО ПОТОКА ДЛЯ ИССЛЕДОВАНИЯ СИСТЕМЫ GI/GI/ Для системы массового обслуживания

УДК 6.39.; 59. С.В. Лопухова А.А. Назаров ИССЛЕДОВАНИЕ МАР-ПОТОКА МЕТОДОМ АСИМПТОТИЧЕСКОГО АНАЛИЗА N -го ПОРЯДКА Рассматривается МАР-поток. Выполнено исследование данного потока методом асимптотического

ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА 8 Управление вычислительная техника и информатика 4(5) МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ УДК 59.87 В.А. Вавилов А.А. Назаров МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НЕУСТОЙЧИВЫХ

Филиал Кемеровского государственного университета в г. Анжеро-Судженске Национальный исследовательский Томский государственный университет Кемеровский государственный университет Институт проблем управления

ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА Управление вычислительная техника и информатика 3() УДК 59.87 И.А. Ивановская С.П. Моисеева ИССЛЕДОВАНИЕ МОДЕЛИ ПАРАЛЛЕЛЬНОГО ОБСЛУЖИВАНИЯ КРАТНЫХ ЗАЯВОК

ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА 2011 Управление, вычислительная техника и информатика 3(16) ОБРАБОТКА ИНФОРМАЦИИ УДК 519.872 И.Л. Лапатин, А.А. Назаров ХАРАКТЕРИСТИКИ МАРКОВСКИХ СИСТЕМ МАССОВОГО

А.А. Назаров И.А. Семенова. Сравнение асимптотических и допредельных характеристик 187 УДК 4.94:519.872 А.А. Назаров И.А. Семенова Сравнение асимптотических и допредельных характеристик системы МАР/М/

Филиал Кемеровского государственного университета в г Анжеро-Судженске Национальный исследовательский Томский государственный университет Кемеровский государственный университет Институт проблем управления

Статистическая радиофизика и теория информации Лекция 7 8.Марковские цепи с непрерывным временем Марковские цепи с непрерывным временем представляют собой марковский случайный процесс X t, состоящий из

ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА 9 Управление вычислительная техника и информатика (7) МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ УДК 5987 ВА Вавилов МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НЕУСТОЙЧИВЫХ СЕТЕЙ СЛУЧАЙНОГО

ГЛАВА 5. МАРКОВСКИЕ ПРОЦЕССЫ С НЕПРЕРЫВНЫМ ВРЕМЕНЕМ И ДИСКРЕТНЫМ МНОЖЕСТВОМ СОСТОЯНИЙ В результате изучения данной главы студенты должны: знать определения и свойства Марковских процессов с непрерывным

На правах рукописи Задиранова Любовь Александровна ИССЛЕДОВАНИЕ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ ПОТОКОВ В БЕСКОНЕЧНОЛИНЕЙНЫХ СМО С ПОВТОРНЫМ ОБСЛУЖИВАНИЕМ ТРЕБОВАНИЙ 05.13.18 Математическое моделирование, численные

ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА 7 Управление вычислительная техника и информатика УДК 59 НВ Степанова АФ Терпугов УПРАВЛЕНИЕ ЦЕНОЙ ПРИ ПРОДАЖЕ СКОРОПОРТЯЩЕЙСЯ ПРОДУКЦИИ Рассматривается управление

ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА Управление, вычислительная техника и информатика () УДК 59.865 К.И. Лившиц, Я.С. Бублик ВЕРОЯТНОСТЬ РАЗОРЕНИЯ СТРАХОВОЙ КОМПАНИИ ПРИ ДВАЖДЫ СТОХАСТИЧЕСКОМ

УДК 6-5 Спектральные характеристики линейных функционалов и их приложения к анализу и синтезу стохастических систем управления К.А. Рыбаков В статье вводится понятие спектральных характеристик линейных

На правах рукописи Лапатин Иван Леонидович ИССЛЕДОВАНИЕ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ ВЫХОДЯЩИХ ПОТОКОВ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ С НЕОГРАНИЧЕННЫМ ЧИСЛОМ ПРИБОРОВ 05.13.18 Математическое моделирование, численные

Оглавление Глава Случайные процессы Простая однородная цепь Маркова Уравнение Маркова Простая однородная цепь Маркова 4 Свойства матрицы перехода 5 Численный эксперимент: стабилизация распределения вероятностей

ИНСТИТУТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ГЕОФИЗИКИ СИБИРСКОГО ОТДЕЛЕНИЯ РОССИЙСКОЙ АКАДЕМИИ НАУК МАРЧУКОВСКИЕ НАУЧНЫЕ ЧТЕНИЯ 017 5 июня 14 июля 017 года Труды Редакционная коллегия академик

ИССЛЕДОВАНИЕ RQ-СИСТЕМЫ M GI 1 МЕТОДОМ АСИМПТОТИЧЕСКОГО АНАЛИЗА В УСЛОВИИ БОЛЬШОЙ ЗАГРУЗКИ Е. Моисеева, А. Назаров Томский государственный университет Томск, Россия [email protected] В работе рассмотрена

УДК 6-5:59 НС Демин СВ Рожкова ОВ Рожкова ФИЛЬТРАЦИЯ В ДИНАМИЧЕСКИХ СИСТЕМАХ ПО НЕПРЕРЫВНО-ДИСКРЕТНЫМ НАБЛЮДЕНИЯМ С ПАМЯТЬЮ ПРИ НАЛИЧИИ АНОМАЛЬНЫХ ПОМЕХ II НЕПРЕРЫВНО-ДИСКРЕТНЫЕ НАБЛЮДЕНИЯ В данной работе

Численные методы Тема 2 Интерполяция В И Великодный 2011 2012 уч год 1 Понятие интерполяции Интерполяция это способ приближенного или точного нахождения какой-либо величины по известным отдельным значениям

Український математичний вiсник Том 5 (28), 3, 293 34 О краевых задачах для обыкновенного дифференциального оператора с матричными коэффициентами Анна В Агибалова (Представлена М М Маламудом) Аннотация

Лекция 2. Статистики первого типа. Точеченые оценки и их свойства Буре В.М., Грауэр Л.В. ШАД Санкт-Петербург, 2013 Буре В.М., Грауэр Л.В. (ШАД) Лекция 2. Статистики первого типа. Точеченые Санкт-Петербург,

Управление вычислительная техника и информатика УДК 6-5:59 ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ ДИСКРЕТНОГО КАНАЛА НАБЛЮДЕНИЯ С ПАМЯТЬЮ В ЗАДАЧЕ ЭКСТРАПОЛЯЦИИ НС Дёмин ОВ Рожкова* Томский государственный университет

Статистическая радиофизика и теория информации Лекция 6 7. Марковские* случайные процессы и марковские цепи. *Марков Андрей Андреевич (род. 1890) русский математик, академик Марковский случайный процесс

Сибирский математический журнал Июль август, 2003 Том 44, 4 УДК 51921+5192195 О КОМПОНЕНТАХ ФАКТОРИЗАЦИОННОГО ПРЕДСТАВЛЕНИЯ ДЛЯ ВРЕМЕНИ ПРЕБЫВАНИЯ ПОЛУНЕПРЕРЫВНЫХ СЛУЧАЙНЫХ БЛУЖДАНИЙ В ПОЛОСЕ В С Лугавов

На правах рукописи Горбатенко Анна Евгеньевна ИССЛЕДОВАНИЕ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ С КОРРЕЛИРОВАННЫМИ ПОТОКАМИ В СПЕЦИАЛЬНЫХ ПРЕДЕЛЬНЫХ УСЛОВИЯХ 05.13.18 Математическое моделирование, численные методы

Управление вычислительная техника и информатика УДК 59. ИНФОРМАЦИОННЫЙ АСПЕКТ В СОВМЕСТНОЙ ЗАДАЧЕ НЕПРЕРЫВНО-ДИСКРЕТНОЙ ФИЛЬТРАЦИИ И ИНТЕРПОЛЯЦИИ. АНАЛИЗ С.В. Рожкова О.В. Рожкова Томский политехнический

Сибирский математический журнал Июль август, 2005. Том 46, 4 УДК 519.21 О ФАКТОРИЗАЦИОННЫХ ПРЕДСТАВЛЕНИЯХ В ГРАНИЧНЫХ ЗАДАЧАХ ДЛЯ СЛУЧАЙНЫХ БЛУЖДАНИЙ, ЗАДАННЫХ НА ЦЕПИ МАРКОВА В. И. Лотов, Н. Г. Орлова

Лекция 3 Устойчивость равновесия и движения системы При рассмотрении установившихся движений уравнения возмущенного движения запишем в виде d dt A Y где вектор-столбец квадратная матрица постоянных коэффициентов

Глава 1 Дифференциальные уравнения 1.1 Понятие о дифференциальном уравнении 1.1.1 Задачи, приводящие к дифференциальным уравнениям. В классической физике каждой физической величине ставится в соответствие

Лекция ХАРАКТЕРИСТИЧЕСКАЯ ФУНКЦИЯ ЦЕЛЬ ЛЕКЦИИ: построить метод линеаризации функций случайных величин; ввести понятие комплексной случайной величины и получить ее числовые характеристики; определить характеристическую

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

1. КОНЕЧНЫЕ ОДНОРОДНЫЕ ЦЕПИ МАРКОВА Рассмотрим последовательность случайных величин ξ n, n 0, 1,..., каждая из коорых распределена дискретно и принимает значения из одного и того же множества {x 1,...,

Глава 6 Основы теории устойчивости Лекция Постановка задачи Основные понятия Ранее было показано, что решение задачи Коши для нормальной системы ОДУ = f, () непрерывно зависит от начальных условий при

Sin cos R Z cos ImZ cos sin sin Найденные таким образом решения образуют фундаментальную систему решений и следовательно общее решение системы имеет вид или подробнее sin cos cos sin cos cos cos sin sin

Структурная надежность. Теория и практика Каштанов В.А. УПРАВЛЕНИЕ СТРУКТУРОЙ В МОДЕЛЯХ МАССОВОГО ОБСЛУЖИВАНИЯ И НАДЕЖНОСТИ С использованием управляемых полумарковских процессов исследуется оптимальная

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ СТРАХОВОЙ КОМПАНИИ В ВИДЕ СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ M M И. Синякова, С. Моисеева Национальный исследовательский Томский государственный университет Томск, Россия [email protected]

УДК 59. ТЕОРЕМА РАЗДЕЛЕНИЯ В СЛУЧАЕ НАБЛЮДЕНИЙ С ПАМЯТЬЮ Н.С. Демин, С.В. Рожкова Томский государственный университет Томский политехнический университет E-mail: [email protected] Приводится доказательство

По условию теоремы L B (m Тогда в силу линейности оператора L имеем: m m m L L ] B [ Системы линейных дифференциальных уравнений с постоянными коэффициентами Собственные значения и собственные векторы

СПИСОК ЛИТЕРАТУРЫ Калашникова ТВ Извеков НЮ Интеграция метода ориентации на спрос в систему ценообразования сети розничной торговли // Известия Томского политехнического университета Т 3 6 С 9 3 Фомин

ИНСТИТУТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ГЕОФИЗИКИ СИБИРСКОГО ОТДЕЛЕНИЯ РОССИЙСКОЙ АКАДЕМИИ НАУК МАРЧУКОВСКИЕ НАУЧНЫЕ ЧТЕНИЯ 217 25 июня 14 июля 217 года Труды Редакционная коллегия академик

ТЕМА 7. Случайные процессы. Цель контента темы 7 дать начальные понятия о случайных процессах и цепях Маркова в частности; очертить круг экономических задач, которые используют в своем решении модели,

Лекция 4. Доверительные интервалы Буре В.М., Грауэр Л.В. ШАД Санкт-Петербург, 2013 Буре В.М., Грауэр Л.В. (ШАД) Лекция 4. Доверительные интервалы Санкт-Петербург, 2013 1 / 49 Cодержание Содержание 1 Доверительные

Сибирский математический журнал Январь февраль, 2. Том 41, 1 УДК 517.948 АСИМПТОТИКА РЕШЕНИЯ СИНГУЛЯРНО ВОЗМУЩЕННЫХ НЕЛИНЕЙНЫХ ИНТЕГРОДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ М. К. Дауылбаев Аннотация: Рассмотрено сингулярно

Лекция Моделирование систем с использованием Марковских случайных процессов Основные понятия Марковских процессов Функция X(t) называется случайной, если ее значение при любом аргументе t является случайной

7 (), 9 Г. В. Бойкова Î íåêîòîðîì íåèçâåñòíîì ðåøåíèè îäíîðîäíîãî äèôôåðåíöèàëüíîãî óðàâíåíèÿ âòîðîãî ïîðÿäêà Аннотация: для дифференциального уравнения второго порядка найдено решение, которое представляет

ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ УДК 57977 ОБ УПРАВЛЯЕМОСТИ ЛИНЕЙНЫХ СИНГУЛЯРНО ВОЗМУЩЕННЫХ СИСТЕМ С МАЛЫМ ЗАПАЗДЫВАНИЕМ Канд физ-мат наук доц КОПЕЙКИНА Т Б ГУСЕЙНОВА А С Белорусский национальный технический

Компьтерное моделирование. СМО. Лекция 2 1 Оглавление Глава 2. Представление СМО марковским случайным процессом... 1 I. Классификация СМО по Кендалл... 1 II. Марковский случайный процесс... 2 III. Марковские

48 Вестник РАУ Серия физико-математические и естественные науки, 1, 28, 48-59 УДК 68136 ОЦЕНКА ХАРАКТЕРИСТИК НАДЕЖНОСТИ СИСТЕМ ДИСТАНЦИОННОГО ОБУЧЕНИЯ ЧАСТЬ 2 ХВ Керобян, НН Хубларян, АГ Оганесян Российско-Армянский

Основные понятия теории разностных схем. Примеры построения разностных схем для начально-краевых задач. Большое количество задач физики и техники приводит к краевым либо начальнокраевым задачам для линейных

4 (0) 00 Байесовский анализ когда оцениваемый параметр является случайным нормальным процессом Рассмотрена задача байесовского оценивания последовательности неизвестных средних значений q q... q... по

РОССИЙСКИЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ МИРЭА ДОПОЛНИТЕЛЬНЫЕ ГЛАВЫ ВЫСШЕЙ МАТЕМАТИКИ ГЛАВА 3. СИСТЕМЫ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ Работа посвящена моделированию динамических систем с использованием элементов

СИСТЕМЫ ЛИНЕЙНЫХ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ С ПОСТОЯННЫМИ КОЭФФИЦИЕНТАМИ Приведение к одному уравнению -го порядка С практической точки зрения очень важны линейные системы с постоянными коэффициентами

1 Заглавие документа Овсянников А.В. СТАТИСТИЧЕСКИЕ НЕРАВЕНСТВА В СВЕРХРЕГУЛЯРНЫХ СТАТИСТИЧЕСКИХ ЭКСПЕРИМЕНТАХ ТЕОРИИ ОЦЕНИВАНИЯ // Вест нацыянальнай акадэм навук Беларус, 009. Сер фз-мат. навук. С.106-110

УДК 59 ЕВ Новицкая АФ Терпугов ОПРЕДЕЛЕНИЕ ОПТИМАЛЬНОГО ОБЪЕМА ПАРТИИ ТОВАРА И РОЗНИЧНОЙ ЦЕНЫ ПРОДАЖИ НЕПРЕРЫВНО ПОРТЯЩЕЙСЯ ПРОДУКЦИИ Рассматривается задача определения оптимального объема партии товара

ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ Московский государственный технический университет имени НЭ Баумана Факультет «Фундаментальные науки» Кафедра «Математическое моделирование» ÀÍ Êàíàòíèêîâ, ÀÏ Êðèùåíêî ÀÍÀËÈÒÈ

Math-Net.Ru Общероссийский математический портал А. А. Назаров, Т. В. Любина, Немарковская динамическая RQ-система с входящим MMP-потоком заявок, Автомат. и телемех., 213, выпуск 7, 89 11 Использование

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ КРАСНОЯРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ УДК ББК Составитель: Н.А. Пинкина КАФЕДРА ВЫСШЕЙ МАТЕМАТИКИ Линейная алгебра. Решение типовых примеров. Варианты контрольных

Лекция 2 Решение систем линейных уравнений. 1. Решение систем 3-х линейных уравнений методом Крамера. Определение. Системой 3-х линейных уравнений называется система вида В этой системе искомые величины,

Рассмотрим некоторую физическую систему S={S 1 ,S 2 ,…S n }, которая переходит из состояния в состояние под влиянием каких-то случайных событий (вызовы, отказы, выстрелы). Будем себе это представлять так, будто события, переводящие систему из состояния в состояние, представляют собой какие-то потоки событий.

Пусть система S в момент времени t находится в состоянии S i и может перейти из него в состояние S j под влиянием какого-то пуассоновского потока событий с интенсивностью ij: как только появляется первое событие этого потока, система мгновенно переходит из S i в S j . Как мы знаем, вероятность этого перехода за элементарный промежуток времени (элемент вероятности перехода) равна, отсюда вытекает, что плотность вероятности перехода ij в непрерывной цепи Маркова представляет собой не что иное, как интенсивность потока событий, переводящих систему по соответствующей стрелке. Если все потоки событий, переводящие систему S из состояния в состояние пуассоновские, то процесс, протекающий в системе, будет марковским.

Проставим интенсивности пуассоновских потоков (плотности вероятностей переходов) на графе состояний системы у соответствующих стрелок. Получим размеченный граф состояний. На его основе можно написать уравнения Колмогорова и вычислить вероятности состояний.

Пример. Техническая система S состоит из двух узлов I и II, каждый из которых независимо от другого может отказывать. Поток отказов первого узла пуассоновский с интенсивностью I , второго также пуассоновский с интенсивностью II . Каждый узел сразу после отказа начинает ремонтироваться (восстанавливаться). Поток восстановлений (окончаний ремонта узла) для обоих узлов - пуассоновский с интенсивностью. Составить граф состояний системы и написать уравнение Колмогорова. Состояния системы: S 11 - оба узла исправны; S 21 - первый узел ремонтируется, второй исправен; S 12, S 22 .

t=0 p 11 =1 p 21 =p 22 =p 12 =0

p 11 +p 12 +p 21 +p 22 =1.

Предельные вероятности состояний для непрерывной марковской цепи

Пусть имеется физическая система S={S 1 ,S 2 ,…S n }, в которой протекает марковский случайный процесс с непрерывным временем (непрерывная цепь Маркова). Предположим, что ij =const, т.е. все потоки событий простейшие (стационарные пуассоновские). Записав систему дифференциальных уравнений Колмогорова для вероятностей состояний и проинтегрировав эти уравнения при заданных начальных условиях, мы получим p 1 (t), p 2 (t),… p n (t), при любом t. Поставим следующий вопрос, что будет происходить с системой S при t. Будут ли функции p i (t) стремиться к каким-то пределам? Эти пределы, если они существуют, называются предельными вероятностями состояний. Можно доказать теорему: если число состояний S конечно и из каждого состояния можно перейти (за то или иное число шагов) в каждое другое, то предельные вероятности состояний существуют и не зависят от начального состояния системы. Предположим, что поставленное условие выполнено и предельные вероятности существуют (i=1,2,…n), .

Таким образом, при t в системе S устанавливается некоторый предельный стационарный режим. Смысл этой вероятности: она представляет собой не что иное, как среднее относительное время пребывания системы в данном состоянии. Для вычисления p i в системе уравнений Колмогорова, описывающих вероятности состояний, нужно положить все левые части (производные) равными 0. Систему получающихся линейных алгебраических уравнений надо решать совместно с уравнением.

Схема гибели и размножения

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

Граф состояний для схемы гибели и размножения имеет вид, показанный на рис. 19.1. Особенность этого графа в том, что все состояния системы можно вытянуть в одну цепочку, в которой каждое из средних состояний (S 1 , S 2 , ..., S n-1) связано прямой и обратной стрелкой с каждым из соседних состояний -- правым и левым, а крайние состояния (S 0 , S n) -- только с одним соседним состоянием. Термин «схема гибели и размножения» ведет начало от биологических задач, где подобной схемой описывается изменение численности популяции.

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

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

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

Для второго состояния S 1:

В силу (8.1) последнее равенство приводится к виду

где k принимает все значения от 0 до n. Итак, финальные вероятности р 0 , p 1 ,..., р n удовлетворяют уравнениям

кроме того, надо учесть нормировочное условие

p 0 + р 1 + р 2 +…+ р n =1 (8.3)

Решим эту систему уравнений. Из первого уравнения (8.2) выразим р 1 через р 0 .

Из второго, с учетом (8.4), получим:

из третьего, с учетом (8.5),

и вообще, для любого k (от 1 до N):

Обратим внимание на формулу (8.7). В числителе стоит произведение всех интенсивностей, стоящих у стрелок, ведущих слева направо (с начала и до данного состояния S k), а в знаменателе -- произведение всех интенсивностей, стоящих у стрелок, ведущих справа налево (с начала и до S k).

Таким образом, все вероятности состояний p 1 , р 2 , …, p n выражены через одну из них (p 0). Подставим эти выражения в нормировочное условие (8.3). Получим, вынося за скобку p 0:

отсюда получим выражение для р 0 .

(скобку мы возвели в степень -1, чтобы не писать двухэтажных дробей). Все остальные вероятности выражены через р 0 (см. формулы (8.4) -- (8.7)). Заметим, что коэффициенты при p 0 в каждой из них представляют собой не что иное, как последовательные члены ряда, стоящего после единицы в формуле (8.8). Значит, вычисляя р 0 , мы уже нашли все эти коэффициенты.

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

Задачи теории массового обслуживания. Классификация систем массового обслуживания и их основные характеристики

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

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

В СМО происходит какой-то СП с дискретными состояниями и непрерывным временем; состояние СМО меняется скачком в моменты появления каких-то событий (или прихода новой заявки, или окончания обслуживания, или момента, когда заявка, которой надоело ждать, покидает очередь). Чтобы дать рекомендации по рациональной организации этого процесса и предъявить разумные требования к СМО, необходимо изучить СП, описать его математически. Этим и занимается теория МО.

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

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

Похожие статьи