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

где - одно из возможных пространств состояний .

Вероятность перехода на m-шаге (условная вероятность):

Таким образом, для вычисления совместных вероятностей Р(Q 0 , ..,Q n) необходимо задать начальное состояние системы и указать физический механизм осуществления смены состояний, позволяющий вычислить вероятности перехода .

1. Частный (вырожденный) случай цепи Маркова. Смена всех состояний происходит независимо, то есть вероятность какого-либо состояния на m-м шаге не зависит от того, в каких состояниях находилась система в предыдущие моменты времени.

– последовательность независимых испытаний.

2. Вероятность фазового состояния параметра Q n в момент времени t n зависит лишь от того, в каком состоянии находилась система в непосредственно предшествующий ему момент времени t n-1 , и не зависит от того, в каких состояниях находилась система в более ранние моменты времени t 0 ,…,t n-2 .

3. Цепь Маркова порядка , если вероятность нового состояния зависит только от m состояний системы, непосредственно ему предшествующих:

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

Простейшей вероятностной характеристикой случайного процесса служит набор вероятностей состояний P 1 (t), P 2 (t), ... P n (t), где P i (t) – вероятность перехода системы в состояние S i в момент времени t . Условие нормировки P 1 +P 2 +...+P n =1 .

Если в процессе функционирования система оказывается в состоянии S i , то вероятность перехода ее в состояние S j в общем случае зависит не только от состояния S i , но и от предыдущего состояния.

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

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

Переход системы в некоторое состояние является событием .

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

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

Интервалы времени t 1 , t 2 , ... t n ординарного потока могут быть одинаковыми или различными, дискретными или непрерывными, случайными или неслучайными.

Если интервалы времени t 1 , t 2 , ... t n – неслучайные величины, то поток называется регулярным или детерминированным, и этот поток описывается путем задания значений T 1 ,T 2 , ... T n .

Если T 1 ,T 2 , ... T n являются случайными, то поток называется случайным и он характеризуется законом распределения величин T 1 ,T 2 ,... T n .

На практике часто встречаются системы, в которых T i – непрерывная случайная величина. В этих случаях система может быть описана плотностью вероятности f(t 1 , t 2 , ... t n) , где t i – конкретное значение случайной величины T i .

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

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

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

Если случайные величины t i независимые, то такой поток называется потоком с ограниченным последействием и плотность вероятности этого потока равна произведению плотностей вероятности:

f(t 1 ,t 2 , ...t n) = f 1 (t 1) f 2 (t 2) ... f n (t n) (6.5)

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

f i (t i) = f(t i) (6.6)

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

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

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

P m = e - a , (6.7)

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

Пуассоновский поток является стационарным, если плотность событий l постоянна, тогда среднее число событий равно lt , иначе поток будет нестационарным.

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

Просеянные потоки

Процесс переходов системы с дискретным временем функционирования может рассматриваться как воздействие дискретного потока событий, которое характеризуется тем, что в моменты времени t 1 , t 2 , ..., t n события происходят с вероятностью P i . Функция распределения такого потока:

Просеяние потока событий S 1 , S 2 , ... S n , которые наступают в определенные моменты времени с вероятностями p 1 , p 2 , ... p n , означает преобразование этих вероятностей в , , ..., . Если поток является стационарным, то эти вероятности равны: = =...=1-p.

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

Примерами потоков с ограниченным последействием являются потоки Эрланга. Они образуются закономерным просеиванием простейшего потока, при этом под закономерным просеиванием понимается процедура, в результате которой происходит исключение нескольких последующих событий в исходном потоке. Если у простейшего потока исключается каждое нечетное событие, то оставшиеся события образуют поток Эрланга II порядка. Промежуток времени между соседними событиями в таком потоке представляет собой сумму независимых случайных величин и , распределенных по показательному закону ( = + ).

Если в простейшем потоке сохранить только каждое третье событие, то получим поток Эрланга III порядка и т.д. В общем случае, потоком Эрланга k -порядка называется простейший поток, полученный исключением (k- 1) событий и сохранением k -го события.

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

Марковский случайный процесс с дискретными состояниями и дискретным временем функционирования описывает систему S с конечным числом состояний. При этом переходы возможны в фиксированные моменты времени t 1 , t 2 , ..., t k . Процесс, происходящий в этой системе, можно представить в виде цепочки случайных событий

S 1 (0) ® S 2 (1) ® ... ® S i (n) ® ... ® S n (k).

Эта последовательность называется дискретной Марковской цепью, если для каждого шага n=1,2, ... k вероятность переходов из любого состояния (S i ®S j) не зависит от того, как система пришла в состояние S i . Каждому переходу системы соответствует условная вероятность

P . (6.9)

Для каждого номера шага n возможные переходы образуют полную группу событий .

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

и вектор начального распределения вероятностей для всех состояний в момент времени t=0.

= . (6.10)

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

Дискретная Марковская цепь называется неоднородной , если переходные вероятности меняются с изменением номера шага. Для описания таких цепей необходимо задать k матриц переходных вероятностей P ij (k – число рассматриваемых шагов). Главной задачей анализа Марковских процессов является определение вероятность всех состояний системы после любого количества шагов. При этом если известна матрица переходных вероятностей и вектор начального распределения, то вероятности состояний системы после каждого шага определяются по формуле полной вероятности:

P(A) = P(B i)*P(A/B i) (6.11)

После первого шага вероятность P i может быть определена следующим образом:

P i (1) = P j (0)P ji , (6.12)

где P j (0) – вектор начальных состояний,

P ji – строка матрицы условных вероятностей.

P i (2) = P j (1)P ji = P j (0)P ji (1) (6.13)

После k шагов:

P i (k) = P j (k-1)P ji = P j (0)P ji (k), (6.14)

где P ji (k) – вероятности переходов системы из состояния S i в S j за k шагов.

Если возможен переход из состояния S i в состояние S j за k шагов, то величина P ji (k)>0 . Если при этом возможен обратный переход за то же число шагов, то состояние S i называется возвратным . Вероятность того, что система выйдет из состояния S i и за k шагов вернется в него же, равна 1 для возвратных состояний.

Состояние S i - невозвратное , если эта вероятность отлична от 1.

Состояния S i и S j называются сообщающимися , если возможен переход S i ®S j за конечное число шагов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

. (5.7)

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

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

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

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

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

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

(5.10)

. (5.11)

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

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

(5.12)

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

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

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

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

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

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

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

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

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

(5.13)

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

. (5.14)

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

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

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

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

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

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

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

(5.17)

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

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

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

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

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

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

, (5.19)

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

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

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

(5.20)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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