Критерий наличия общих корней у пары полиномов. Кратные корни многочлена. Изучение нового материала

Транскрипт

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-х линейных уравнений называется система вида В этой системе искомые величины,

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

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

Когда событий много и они следуют друг за другом, то они образуют поток . Заметим, что события при этом должны быть однородными, то есть похожими чем-то друг на друга. Например, появление водителей на АЗС, желающих заправить свой автомобиль. То есть, однородные события образуют некий ряд. При этом считается, что статистическая характеристика этого явления (интенсивность потока событий) задана. Интенсивность потока событий указывает, сколько в среднем происходит таких событий за единицу времени. Но когда именно произойдет каждое конкретное событие надо определить методами моделирования. Важно, что, когда мы сгенерируем, например, за 200 часов 1000 событий, их количество будет равно примерно величине средней интенсивности появления событий 1000/200 = 5 событий в час, что является статистической величиной, характеризующей этот поток в целом.

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

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

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

Интенсивность потока λ это среднее число событий в единицу времени. Интенсивность потока можно рассчитать экспериментально по формуле: λ = N /T н , где N число событий, произошедших за время наблюдения T н .

Если интервал между событиями τ j равен константе или определен какой-либо формулой в виде: t j = f (t j 1) , то поток называется детерминированным . Иначе поток называется случайным .

Случайные потоки бывают:

ординарные : вероятность одновременного появления двух и более событий равна нулю;
стационарные : частота появления событий λ (t ) = const(t ) ;
без последействия : вероятность появления случайного события не зависит от момента совершения предыдущих событий.

Пуассоновский поток

За эталон потока в моделировании принято брать пуассоновский поток .

Пуассоновский поток это ординарный поток без последействия.

Как ранее было указано, вероятность того, что за интервал времени (t 0 , t 0 + τ ) произойдет m событий, определяется из закона Пуассона:

где a параметр Пуассона.

Если λ (t ) = const(t ) , то это стационарный поток Пуассона (простейший). В этом случае a = λ · t . Если λ = var(t ) , то это нестационарный поток Пуассона .

Для простейшего потока вероятность появления m событий за время τ равна:

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

Рис. 28.2 иллюстрирует зависимость P 0 от времени. Очевидно, что чем больше время наблюдения, тем вероятность непоявления ни одного события меньше. Кроме того, чем более значение λ , тем круче идет график, то есть быстрее убывает вероятность. Это соответствует тому, что если интенсивность появления событий велика, то вероятность непоявления события быстро уменьшается со временем наблюдения.

Вероятность появления хотя бы одного события (P ХБ1С ) вычисляется так:

так как P ХБ1С + P 0 = 1 (либо появится хотя бы одно событие, либо не появится ни одного, другого не дано).

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

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

Если увеличивать λ , то при наблюдении за событием в течение одного и того же времени τ , вероятность наступления события возрастает (см. рис. 28.4 ). Очевидно, что график исходит из 0, так как если время наблюдения бесконечно мало, то вероятность того, что событие произойдет за это время, ничтожна. И наоборот, если время наблюдения бесконечно велико, то событие обязательно произойдет хотя бы один раз, значит, график стремится к значению вероятности равной 1.

Изучая закон, можно определить, что: m x = 1/λ , σ = 1/λ , то есть для простейшего потока m x = σ . Равенство математического ожидания среднеквадратичному отклонению означает, что данный поток поток без последействия. Дисперсия (точнее, среднеквадратичное отклонение) такого потока велика. Физически это означает, что время появления события (расстояние между событиями) плохо предсказуемо, случайно, находится в интервале m x σ < τ j < m x + σ . Хотя ясно, что в среднем оно примерно равно: τ j = m x = T н /N . Событие может появиться в любой момент времени, но в пределах разброса этого момента τ j относительно m x на [σ ; +σ ] (величину последействия). На рис. 28.5 показаны возможные положения события 2 относительно оси времени при заданном σ . В данном случае говорят, что первое событие не влияет на второе, второе на третье и так далее, то есть последействие отсутствует.

По смыслу P равно r (см. лекцию 23. Моделирование случайного события. Моделирование полной группы несовместных событий), поэтому, выражая τ из формулы (*) , окончательно для определения интервалов между двумя случайными событиями имеем:

τ = 1/λ · Ln(r ) ,

где r равномерно распределенное от 0 до 1 случайное число, которое берут из ГСЧ, τ интервал между случайными событиями (случайная величина τ j ).

Пример 1 . Рассмотрим поток изделий, приходящих на технологическую операцию. Изделия приходят случайным образом в среднем восемь штук за сутки (интенсивность потока λ = 8/24 [ед/час] ). Необходимо промоделировать этот процесс в течение T н = 100 часов . m = 1/λ = 24/8 = 3 , то есть в среднем одна деталь за три часа. Заметим, что σ = 3 . На рис. 28.6 представлен алгоритм, генерирующий поток случайных событий.

На рис. 28.7 показан результат работы алгоритма моменты времени, когда детали приходили на операцию. Как видно, всего за период T н = 100 производственный узел обработал N = 33 изделия. Если запустить алгоритм снова, то N может оказаться равным, например, 34, 35 или 32. Но в среднем, за K прогонов алгоритма N будет равно 33.33 Если посчитать расстояния между событиями t сi и моментами времени, определяемыми как 3 · i , то в среднем величина будет равна σ = 3 .

Моделирование неординарных потоков событий

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

Допустим, что M k = 10 , σ = 4 (то есть, в среднем в 68 случаях из 100 приходит от 6 до 14 вагонов в составе поезда) и их число распределено по нормальному закону. В место, отмеченное (*) в предыдущем алгоритме (см. рис. 28.6 ), нужно вставить фрагмент, показанный на рис. 28.8 .

Пример 2 . Очень полезным в производстве является решение следующей задачи. Каково среднее время суточного простоя оборудования технологического узла, если узел обрабатывает каждое изделие случайное время, заданное интенсивностью потока случайных событий λ 2 ? При этом экспериментально установлено, что привозят изделия на обработку тоже в случайные моменты времени, заданные потоком λ 1 партиями по 8 штук, причем размер партии колеблется случайно по нормальному закону с m = 8 , σ = 2 (см. лекцию 25). До начала моделирования T = 0 на складе изделий не было. Необходимо промоделировать этот процесс в течение T н = 100 часов.

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

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

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

T пр. ср. = 24 · (t 1 пр. + t 2 пр. + t 3 пр. + t 4 пр. + + t N пр.)/T н .

Задание 1 . Меняя величину σ , установите зависимость T пр. ср. (σ ) . Задавая стоимость за простой узла 100 евро/час, установите годовые потери предприятия от нерегулярности в работе поставщиков. Предложите формулировку пункта договора предприятия с поставщиками «Величина штрафа за задержку поставки изделий».

Задание 2 . Меняя величину начального заполнения склада, установите, как изменятся годовые потери предприятия от нерегулярности в работе поставщиков в зависимости от принятой на предприятии величины запасов.

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

В ряде случаев интенсивность потока может меняться со временем λ (t ) . Такой поток называется нестационарным . Например, среднее количество за час машин скорой помощи, покидающих станцию по вызовам населения большого города, в течение суток может быть различным. Известно, например, что наибольшее количество вызовов падает на интервалы с 23 до 01 часа ночи и с 05 до 07 утра, тогда как в остальные часы оно вдвое меньше (см. рис. 28.11 ).

В этом случае распределение λ (t ) может быть задано либо графиком, либо формулой, либо таблицей. А в алгоритме, показанном на рис. 28.6 , в место, помеченное (**), нужно будет вставить фрагмент, показанный на рис. 28.12 .

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

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

Случайный процесс называется марковским процессом (или «процессом без последствия»), если для каждого момента времени t0 вероятность любого состояния системы в будущем (при t > t 0 ) зависит только от её состояния в настоящем (при t = t 0 ) и не зависит от того, когда и каким образом система пришла в это состояние (т. е. как развивался процесс в прошлом). Пусть S техническое устройство, которое характеризуется некоторой степенью изношенности S . Нас интересует, как оно будет работать дальше. В первом приближении характеристики работы системы в будущем (частота отказов, потребность в ремонте) зависят от состояния устройства в настоящий момент и не зависят от того, когда и как устройство достигло своего настоящего состояния.

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

4.1. Классификация марковских процессов

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

Пример. Техническое устройство состоит из двух узлов I и II, каждый из которых может выйти из строя. Состояния: S1 – оба узла работают; S2 – первый узел отказал, второй рабочий; S 3 – второй узел отказал, первый рабочий; S4 – оба узла отказали.

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

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

4.2. Расчет марковской цепи с дискретным временем

S с дискретными состояниями S1, S2, … Sn и дискретным временем t1, t2, … , tk, … (шаги, этапы процесса, СП можно рассматривать как функцию аргумента (номера шага)). В общем случае СП состоит в том, что происходят переходы S1 ® S1 ® S2 ® S3 ® S4 ® S1 ® … в моменты t1, t2, t3 … .

Будем обозначать событие, состоящее в том, что после k – шагов система находится в состоянии Si . При любом k события https://pandia.ru/text/78/060/images/image004_39.gif" width="159" height="25 src=">.

Такая случайная последовательность событий называется марковской цепью. Будем описывать марковскую цепь (МЦ) с помощью вероятностей состояний. Пусть – вероятность того, что после k - шагов система находится в состоянии Si . Легко видеть, что " k DIV_ADBLOCK389">

Пользуюсь введенными выше событиями https://pandia.ru/text/78/060/images/image008_34.gif" width="119" height="27 src=">. Сумма членов в каждой строке матрицы должна быть равна 1. Вместо матрицы переходных вероятностей часто используют размеченный граф состояний (обозначают на дугах ненулевые вероятности переходов, вероятности задержки не требуются, поскольку они легко вычисляются, например P11=1-(P12+ P13) ). Имея в распоряжении размеченный граф состояний (или матрицу переходных вероятностей) и зная начальное состояние системы, можно найти вероятности состояний p1(k), p2(k),… pn(k) " k.

Пусть начальное состояние системы Sm , тогда

p1(0)=0 p2(0)=0… pm(0)=1… pn(0)=0.

Первый шаг:

p1(1)=Pm1 , p2(1)=Pm2 ,…pm(1)=Pmm ,… ,pn(1)=Pmn .

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

p1(2)=p1(1)P11+p2(1)P21+…pn(1)Pn1,

pi(2)=p1(1)P1i+p2(1)P2i+…pn(1)Pni или https://pandia.ru/text/78/060/images/image010_33.gif" width="149" height="47"> (i=1,2,.. n).

Для неоднородной МЦ переходные вероятности зависят от номера шага. Обозначим переходные вероятности для шага k через.

Тогда формула для расчета вероятностей состояний приобретает вид:

4.3. Марковские цепи с непрерывным временем

4.3.1. Уравнения Колмогорова

На практике значительно чаще встречаются ситуации, когда переходы системы из состояния в состояние происходит в случайные моменты времени, которые заранее указать невозможно: например, выход из строя любого элемента аппаратуры, окончание ремонта (восстановление) этого элемента. Для описания таких процессов в ряде случаев может быть с успехом применена схема марковского случайного процесса с дискретными состояниями и непрерывным временем – непрерывная цепь Маркова. Покажем, как выражаются вероятности состояний для такого процесса. Пусть S={ S1, S2,… Sn}. Обозначим через pi(t) - вероятность того, что в момент t система S будет находиться в состоянии ). Очевидно . Поставим задачу – определить для любого t pi(t) . Вместо переходных вероятностей Pij введем в рассмотрение плотности вероятностей перехода

Если не зависит от t , говорят об однородной цепи, иначе - о неоднородной. Пусть нам известны для всех пар состояний (задан размеченный граф состояний). Оказывается, зная размеченный граф состояний можно определить p1(t), p2(t).. pn(t) как функции времени. Эти вероятности удовлетворяют определенного вида дифференциальным уравнениям, (уравнения Колмогорова).

Интегрирование этих уравнений при известном начальном состоянии системы даст искомые вероятности состояний как функции времени. Заметим, что p1+ p2+ p3+ p4=1 и можно обойтись тремя уравнениями.

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

4.3.2. Поток событий. Простейший поток и его свойства

При рассмотрении процессов, протекающих в системе с дискретными состояниями и непрерывным временем, часто бывает удобно представить себе процесс так, как будто переходы системы из состояния в состояние происходят под действием каких-то потоков событий. Потоком событий называется последовательность однородных событий, следующих одно за другим в какие-то, вообще говоря, случайные моменты времени. (Поток вызовов на телефонной станции; поток неисправностей (сбоев) ЭВМ; поток грузовых составов, поступающих на станцию; поток посетителей; поток выстрелов, направленных на цель). Будем изображать поток событий последовательностью точек на оси времени ot . Положение каждой точки на оси случайно. Поток событий называется регулярным , если события следуют одно за другим через строго определенные промежутки времени (редко встречается на практике). Рассмотрим специального типа потоки, для этого введем ряд определений. 1. Поток событий называется стационарным , если вероятность попадания того или иного числа событий на участок времени длиной зависит только от длины участка и не зависит от того, где именно на оси ot расположен этот участок (однородность по времени) – вероятностные характеристики такого потока не должны меняться от времени. В частности, так называемая интенсивность (или плотность) потока событий (среднее число событий в единицу времени) постоянна.

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

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

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

Рассмотрим на оси о t , где наблюдается поток событий, некоторый участок длины t, начинающийся в момент t 0 и заканчивающийся в момент t 0 + t. Нетрудно доказать (доказательство дается во всех курсах теории вероятности), что вероятность попадания на этот участок ровно m событий выражается формулой:

(m =0,1…),

где а – среднее число событий, приходящееся на участок t.

Для стационарного (простейшего) пуассоновского потока а= l t , т. е. не зависит от того, где на оси ot взят участок t. Для нестационарного пуассоновского потока величина а выражается формулой

и значит, зависит от того, в какой точке t 0 начинается участок t.

Рассмотрим на оси ot простейший поток событий с постоянной интенсивностью l. Нас будет интересовать интервал времени T между событиями в этом потоке. Пусть l - интенсивность (среднее число событий в 1 времени) потока. Плотность распределения f (t ) случайной величины Т (интервал времени между соседними событиями в потоке) f (t )= l e - l t (t > 0) . Закон распределения с такой плотностью называется показательным (экспоненциальным). Найдем численные значения случайной величины Т : математическое ожидание (среднее значение) и дисперсию left">

Промежуток времени Т между соседними событиями в простейшем потоке распределен по показательному закону; его среднее значение и среднее квадратичное отклонение равны , где l - интенсивность потока. Для такого потока вероятность появления на элементарном участке времени ∆t ровно одного события потока выражается как . Эту вероятность мы будем называть «элементом вероятности появления события».

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

4.3.3. Пуассоновские потоки событий и

непрерывные марковские цепи

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

Пусть система S в момент времени t находится в состоянии Si и может перейти из него в состояние Sj под влиянием какого-то пуассоновского потока событий с интенсивностью l ij : как только появляется первое событие этого потока, система мгновенно переходит из Si в Sj ..gif" width="582" height="290 src=">

4.3.4. Предельные вероятности состояний

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

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

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

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

https://pandia.ru/text/78/060/images/image044_6.gif" width="73" height="45 src="> (4.4)

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

https://pandia.ru/text/78/060/images/image046_5.gif" width="116" height="45 src="> (4.6)

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

https://pandia.ru/text/78/060/images/image048_4.gif" width="267" height="48 src=">

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

(4. 8)

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

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