Случайные процессы. Математическое ожидание. Корреляционная функция СП

1. Случайные процессы Функция X(t) называется случайной, если при каждом значении аргумента t = t* X(t*) является случайной величиной (СВ). Если аргументом t является время, то X(t) называют случайным процессом. Функция , полученная в результате одного (i - го) опыта , обозначается xi(t) и называется i – й реализацией случайного процесса X(t). Случайный процесс можно рассматривать либо как совокупность случайных величин, зависящих от параметра t , либо как ансамбль реализаций. X(t) - случайный процесс (СП) x(t) - реализация СП x(t) x(1)(t) x(2)(t) t t* t** xt* xt** Xt*- СВ, соответствующая сечению t*. 1.1 Классификация СП Случайные процессы Дискретные СП Непрерывные СП а) непрерывные по времени а) непрерывные по времени б) дискретные по времени б) дискретные по времени 1.2 Характеристики СП 1.2.1. Математическое ожидание (МО) СП Математическим ожиданием случайного процесса X(t) называется неслучайная функция времени mx(t), которая при каждом значении аргумента t=t равна математическому ожиданию СВ X(t), соответствующей этому сечению процесса X(t). (если X(t) – непрерывный СП) fx(,t) – одномерная плотность распределения X(t). 1.2.2 Корреляционная функция СП Корреляционной функцией случайного процесса X(t) называется неслучайная функция Rx(t,t) двух переменных t и t, значение которой при всяких t и t равно ковариации случайных величин и , соответствующих этим сечениям процесса X(t). , где X(t) – непрерывный СП; - двумерная плотность распределения случайного процесса X(t). Автокорреляционная функция – сечения относятся к одному СП . Автокорреляционная функция характеризует степень линейной связи СВ, соответствующим двум сечениям СП. Если Xt и Xt независимы, то Для автокорреляционной функции справедливо RX(t,t) = RX(t,t). Взаимно корреляционная функция – берутся сечения двух разных СП: X(t) и Y(t). 1.2.3 Дисперсия СП Дисперсией случайного процесса X(t) называется неслучайная функция времени Dx(t), которая при каждом значении аргумента t равна дисперсии случайной величины Xt , соответствующей этому сечению процесса X(t): 1.3 Преобразования СП Центрированный СП: Это процесс получаемый путем вычитания из СП его МО : = X(t) – mX(t) M() = 0 Нормированный СП: M()=0 D()=1 1.3.1 Добавление неслучайной функции Дано: X(t), mX(t), RX(t,t) ,- неслучайная (детерминированная) функция времени Определить: mY(t)-? ,RY(t,t)-? = mX(t)+ RY(t,t)= 1.3.2 Умножение на неслучайную величину Дано: X(t), mX(t), RX(t,t) Определить: mY(t)-? ,RY(t,t)-? Доказательство: В частности, если то и 1.3.3 Сложение СП Дано: X1(t), m1(t), RX1(t,t),X2(t), mX2(t), RX2(t,t) Определить: mY(t)-? ,RY(t,t)-? Доказательство: Если и - независимые СП, то RX1X2(t,t) = 0, RX2X1(t,t) = 0 и . 1.3.4 Дифференцирование СП Дано: X(t), mX(t), RX(t,t) Y(t)= Определить: mY(t)=? RY(t,t)=? mY(t)= RY(t,t)= 1.3.5 Интегрирование СП Дано: X(t), mX(t), RX(t,t) Y(t)= Определить: mY(t)=? RY(t,t)=? mY(t)= RY(t,t)= 1.4 Стационарные СП Процесс X(t) называется стационарным в широком смысле, если его математическое ожидание не зависит от времени, а корреляционная функция зависит только от разности аргументов Свойства RX(): 1) RX()=RX(-) - симметрия относительно оси ординат RX() (четность) 2) max RX() =RX(0)  0  1.5 Свойства эргодичности стационарных СП Усреднение по ансамблю реализаций: x(t) x(t) Усреднение по одной реализации: t  t+  T t 1.5.1 Эргодичность по МО X(t) - обладает свойством эргодичности по М.О. , если с вероятностью равной 1 имеем mX(T)=mX 1.5.2 Эргодичность по корреляционной функции X(t) - обладает свойством эргодичности по корреляционной функции, если с вероятностью равной 1 имеем RX(T)()=RX () . 1.5.3 Достаточное условие эргодичности по М.О. Стационарный СП является эргодическим по М.О., если Это условие имеет место, когда 1.5.4 Примеры Пример1: Дано: СП ;  - константа. Определить: Пример 2: Дано: A, - СВ (независимые) Определить: Следовательно, процесс X(t) является стационарным. Пример 3: Дано:  - равномерно распределена в диапазоне (0,2) mx = 0; процесс стационарный Анализ эргодичности: A – константа;  - СВ  Функция стационарна и эргодична. 1.6 Статистика СП 1.6.1 Оценивание характеристик СП по ансамблю реализаций Вся совокупность возможных реализаций случайного процесса называется ансамблем реализаций. Пусть имеем N реализации X(t) Если tl=tk,то это оценка дисперсии D(). Если процесс стационарный можем получить более точную оценку (если процесс эргодичен): , n – число сечений Стремления к истинному значению при n в последних выражениях не будет , если процесс не эргодичен . 1.6.2 Оценивание характеристик СП по одной реализации (для эргодических СП) 1.6.2.1 Оценка характеристик Измерения в дискретные моменты t , интервалы все одинаковы. m = 0,1,…; N – число сечений 1.6.2.2 Построение аппроксимации корреляционной функции 0 1 2 3 4 Задача заключается в выборе параметров: . Воспользуемся методом наименьших квадратов. Так как задача нелинейна по оцениваемым параметрам, то используем логарифмическое преобразование данных: = , j = 1,2,…,k ; Целесообразно брать точки, при малых значениях аргумента . Оценки находим, решая систему линейных уравнений: 1.6.3 Проверка стационарности - при наличии совокупности реализаций процесса Если СП X(t) является стационарным, то МО и дисперсии СВ X(t1 ), …. , X(tm), соответствующих различным сечениям процесса, будут одинаковыми. Это условие является необходимым для стационарных процессов. • при наличии одной реализации В данном случае можно говорить лишь о «стационарности одной реализации» процесса, т.е. о неизменности во времени МО и корреляционной функции данной реализации процесса. Если полагать , что реализации «почти одинаковые», то убедившись в «стационарности одной реализации», можно делать вывод и о стационарности ансамбля реализаций. - при использовании непараметрического критерия Крускала и Уоллиса При его использовании не делается никаких предположений о виде одномерных законов распределения случайного процесса (то есть в данном случае о виде распределений случайных величин X(t1 ), …. , X(tm)). Рассматривая m сечений процесса , в достаточной степени разнесенных во времени (ясно , что вывод о стационарности будет справедлив лишь для интервала (t1,tm)). Обозначим через xi(tk) значение процесса в i –ой реализации в сечении tk , k=1,2,3,…,m; i=1,2,3,…,n , а общее число наблюдений процесса (nm) через N. Теперь упорядочим N наблюдений, расположив их по убыванию наблюдаемых значений и приписав каждому ранг, равный номеру его места в упорядоченной последовательности. Далее найдем суммы rk , k=1,2,3,…,m рангов для наблюдений из каждого сечения процессаи рассчитаем следующую статистику Где числитель есть умноженная на n сумма квадратов отклонений средних рангов по каждому сечению от среднего ранга по всей последовательности, а знаменатель- средний квадрат отклонений от среднего ранга всех элементов последовательности. Отметим, что если в последовательности из N наблюдений имеют место совпадающие числа, то им приписывают одинаковые ранги, равные среднему номеру мест для совпадающих чисел. При этом, если количество совпадающих чисел не очень велико, то знаменатель можно оставить без изменений. 2. Марковские процессы СП X(t) называется Марковским процессом (МП), если при известном значении x(t*), значения процесса X(t) при t>t*, зависят только от x(t*) и не зависят от значений x(t) при t0 Сообщающиеся состояния Si и Sj сообщающиеся, если хотя бы при каких-либо k1 и k2 , pij(k1)>0 и pji(k2)>0 Замкнутое множество состояний Множество состояний (С) называется замкнутым, если оно состоит из сообщающихся состояний и никакое состояние вне этого множества недостижимо из любого состояния, принадлежащего этому множеству. Пример:( - замкнутое множество состояний Поглощающее состояние Это замкнутое множество состояний, состоящее из одного состояния. Пример: - поглощающее состояние Возвратные состояния Si возвратное, если вероятность того, что процесс, выйдя из этого состояния, когда-нибудь в него вернется равна единице. 2.3 Расчет вероятностей состояний цепи Маркова в стационарном режиме (стационарных вероятностей) р(t) 1 p0(t) p1(t) t переходной стационарный режим режим Пусть система может находиться в состояниях S0, S1, ... Sn Р- матрица одношаговых переходных вероятностей. p0 , p1 , ... pn - стационарные вероятности состояний. т.к. вероятности во времени не меняются, то , i=0,1,2 ... n Получим систему из (n+1) уравнений и (n+1) переменных. Эта однородная система, она всегда имеет тривиальное решение. Здесь существует нормирующее условие. 2.4 Однородные дискретные МП с непрерывным временем S0 ,S1, ... , Sn – состояние МП. Время теперь непрерывное. Переход из состояния в состояние происходит в произвольные моменты времени. pij(t)- вероятность перехода из i в j за время t. t- непрерывная величина. Т.к. МП однородный , то pij(t0 , t )=pij(t) текущий интервал момент времени 2.4.1 Интенсивность перехода из Si в Sj 01 Интенсивность 10 , т.е. ij есть предел отношения 02 21 pij(t) к t, при t0. Интенсивность – среднее число переходов из i – го состояния в j-ое состояние за единицу времени. Единица измерения (1/ед.времени). 2.4.2 Система уравнений Колмогорова для вероятностей состояний Марковского процесса с непрерывным временем Рассмотрим дискретный Марковский процесс на интервале t,t + (t – текущее время); S0 ,…,Sn - состояния МП - элемент матрицы переходных вероятностей. Левую и правую части делим на и переходим к пределу, при , j = 0,1,2…,n; _______________________________________________________________ Это система дифференциальных уравнений Колмогорова для вероятностей состояний дискретного МП с непрерывным временем Для решения (т.е. для нахождения нужно задать начальные условия 2.4.3 Формальное правило записи системы уравнения Колмогорова i i Число слагаемых в уравнении для состояния Si –равно числу дуг связанных с данным состоянием. i i Если дуги выходят из Si, то слагаемое берется со знаком «-», если входит, то «+». Каждое слагаемое равно: произведению интенсивности перехода по дуге на вероятность состояния, из которого дуга выходит: Решение находится обычно операторным методом (путем перехода от оригиналов – функций pi(t) – к их изображениям - p0(s) – путем преобразования Лапласа) 2.4.4 Таблица преобразований по Лапласу Оригинал p(t) Изображение по Лапласу p0(s) 2.4.5 Решение системы уравнений Колмогорова (пример) Пример: Дано:   S0 S1 S2  Преобразуем по Лапласу левые и правые части каждого уравнения из (1) (5) из (3) (6) Подставляем (5) и (6) в (4): s1 и s2 - корни уравнения Переходим от изображения к оригиналу (см.табл. 2.5.4) 2.5 Предельное поведение МП с непрерывным временем 2.5.1 Вычисление предельных (стационарных) вероятностей состояний дискретного Марковского процесса с непрерывным временем В стационарных режимах и j = 0,1,…,n 2.5.2 Схема “гибели и размножения” 0 1  2 m-1 m n-1 ….. ….. 1 2 3 m m+1 n 2.5.3 Определение стационарных вероятностей состояний для схемы “гибели и размножения” Из (0) : Из(1) : Из(k): Из (n): 3 Потоки событий Потоки событий – это последовательность однородных событий, следующих одно за другим: t --- это поток событий • событие Поток называется случайным, если длительность периода между событиями – СВ. Существует 2 способа описания случайных потоков: 1) K1 K2 K3 … Kn t K1,…,Kn - случайные числа событий на последовательных интервалах. Функция распределения векторной случайной величины K=( K1,…,Kn) – является характеристикой потока FK1…Kn(k1…kn) = Вер(K10. Т.к. поток без последействия, то K1,…,Kn (числа событий на последовательных интервалах) – независимые СВ. Найдем функцию распределения интервалов между событиями простейшего потока. Функция плотности вероятности при этом 2)Рекурентный поток (поток Пальма) Это поток с ограниченным последействием, для которого интервалы между событиями независимы и распределены одинаково. . 3)Поток Эрланга: простейший поток  x x x x x x  x – события простейшего потока k=1 0 0 0  0 – события потока Эрланга порядка k=1 - случайное время между событиями потока Эрланга порядка k. Tk - независимые СВ, распределенные по экспоненциальному закону. Если мы суммируется k независимых стационарных потоков с любым последействием, то при k результирующий поток, оказывается простейшим с интенсивностью . x x 1 x x x 2 x x x k x x x x x x х x  результирующий (суммарный) поток 4 Марковские модели систем массового обслуживания Теория массового обслуживания изучает системы, предназначенные для выполнения заказов, поступающих от клиентов систем. 4.1 Классификация моделей СМО Допущения: 1.Поток заявок- случайный (в Марковских системах – простейший). 2.Каждая заявка обслуживается одним прибором и без перерывов. 3.Время обработки одной заявки- СВ (в Марковских системах закон распределения экспоненциальный). Классификация моделей СМО может производиться по различным признакам 1) По способу образования очереди: • очередь не создается (СМО с отказами) • очередь имеет конечную длину (СМО с отказами) • очередь неограничена. 2) По способу выхода из очереди (по дисциплине обслуживания): • прямая очередность (первый пришел, первый попал на обслуживание) • инверсная очередность (последний пришел, первый попал на обслуживание) • случайная очередность • обслуживание по приоритетам (абсолютные и относительные приоритеты). 3) По структуре СМО: • одноканальные и многоканальные СМО • разомкнутые и замкнутые СМО • сети СМО. 4.2 Характеристики СМО 1) Пропускная способность (С) - это максимальное среднее число заявок, которое может быть обслужено системой в единицу времени (интенсивность выходного потока при полной загрузке системы). 2) Коэффициент загрузки (Кз) - это доля времени, когда канал занят обработкой (отношение интенсивности заявок, поступающих на обработку, к пропускной способности). 3) Среднее число занятых каналов ( ). 4) Вероятность отказа от обслуживания ( Pотк ). 5) Среднее время ожидания обслуживания (mw). 6) Средняя длина очереди (Lоч). 7) Среднее число заявок в системе Lсист=Lоч+ 8) Среднее время пребывания (реакции) в системе mv=mw+mx , где mx- среднее время обслуживания. Формулы Литтла число заявок X(t) Y(t) 6 X(t)- число поступивших в систему заявок 5 к моменту t. 4 Y(t)- число ушедших из системы заявок 3 к моменту t. 2 Z(t)=X(t)-Y(t) - число заявок находящихся 1 в системе в момент t. T t Среднее число заявок, находящихся в системе- L сист vi - время пребывания в системе i -ой заявки T- среднее число заявок , поступающих в систему за время T Мы могли бы рассматривать не систему, а очередь, тогда те же рассуждения привели бы нас к другой формуле. , – среднее время ожидания обслуживания 4.3 Одноканальные СМО с неограниченной очередью. (без отказов)  очередь обслуживающий прибор (канал) поток заявок олрдр (простейший)  - интенсивность обслуживания T T обслуж. прибор время время обслуж. обслуж. T- распределено по экспоненциальному закону с параметром >0 , т.е. плотность распределения Т есть  - интенсивность обслуживания (интенсивность потока событий на выходе СМО при полной загрузке). Граф состояний этой системы      ….. ……      Признак выделения состояний - число заявок, находящихся в системе. Число состояний может быть бесконечно большим. Состояния все сообщающиеся. Если бы число n было бы конечно, то всегда существовало бы стационарный режим. В нашем случае возможны ситуации, когда очередь будет постоянно расти; такая ситуация имеет место, когда среднее время обслуживания больше среднего времени между поступающими заявками (т.е. когда > ). Стационарные вероятности состояний (см. разделы 2.6.2, 2.6.3): k=0,1,2, ... n - условие существования стационарного режима Характеристики: 1) С =  2) Кз = 3) 4) Pотк=0 5) (mv получено ниже) 6) 8) 4.4 m - канальная СМО с неограниченной очередью  ……   Граф состояний системы       ….. ……  2 3 m m m В этой системе число состояний неограниченно, и возможны ситуации, когда стационарный режим отсутствует. Вероятности состояния в стационарном режиме: ……………………….. Условие существования стационарного режима: m1 Характеристики: 1) C=m 2) 3) 4) Pотк=0 5) (Lоч получено ниже) 6) 7) 8) 4.5 СМО с отказами m- канальная СМО с ограниченной очередью (1- Pотк.)  k …… Pотк.        ….. ……  2 3 m m m Вероятности состояний в стационарном режиме (стационарный режим всегда имеет место): Характеристики: 1) C=m 2) 3) 4) 5) (Lоч получено ниже) 6) 7) 8) 4.6 Замкнутая СМО (СМО с конечным числом пользователей) В этой системе интенсивность потока заявок, поступающих в очередь, зависит от состояния системы. Полагая, что пользователь, пославший заявку в систему ожидает ответа, (т.е. не посылает следующую заявку до получения ответа на предыдущую).  очередь обслуж.прибор (канал)  пользователи N (N-1) (N-2)  ………     Вероятности состояний в стационарном режиме (стационарный режим всегда существует): Расчет среднего времени пребывания заявки в системе (mv) находим mw: Состояние системы в момент получения заявки ср.вр.ожид. S0 S1 1/ S2 2/ ...... ..... ..... ..... SN-1 N-1/ Рассмотрим длительный интервал времени Т состояния время пребывания число поступающих заявок доля заявок S0 TP0 TP0N S1 TP1 TP1(N-1) S2 TP2 TP2(N-2) ................ ........................... .............................. ..................................... SN-1 TPN-1 TPN-1 SN TPN - среднее время ожидания