Элементы теории случайных процессов

МИНОБРНАУКИ РОССИИ –––––––––––––––––– Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» ––––––––––––––––––––––––––––––––––––––– Е. А. БУРКОВ П. И. ПАДЕРНО ЭЛЕМЕНТЫ ТЕОРИИ СЛУЧАЙНЫХ ПРОЦЕССОВ Учебное пособие Санкт-Петербург Издательство СПбГЭТУ «ЛЭТИ» 2015 МИНОБРНАУКИ РОССИИ –––––––––––––––––– Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» ––––––––––––––––––––––––––––––––––––––– Е. А. БУРКОВ П. И. ПАДЕРНО ЭЛЕМЕНТЫ ТЕОРИИ СЛУЧАЙНЫХ ПРОЦЕССОВ Учебное пособие Санкт-Петербург Издательство СПбГЭТУ «ЛЭТИ» 2015 УДК ББК Б 91 Бурков Е. А., Падерно П. И. Б 91 Элементы теории случайных процессов: учеб. пособие. СПб.: Изд-во СПбГЭТУ «ЛЭТИ», 2015. 64 с. ISBN 978-5-7629Рассмотрены основные определения, понятия и свойства случайных процессов, являющихся математическим аппаратом для описания и оценки (построения моделей) систем, процессов функционирования различных объектов и технологий. Предназначено для студентов различных форм обучения направлений 220100 «Системный анализ и управление», 220400 «Управление в технических системах» и 230400 «Информационные системы и технологии» как на уровне бакалаврской подготовки, так и на уровне ряда магистерских программ, а также полезно для инженерно-технических и научных работников этой предметной области и аспирантов смежных специальностей. УДК ББК Рецензенты: кафедра АСУ Обнинского института атомной энергетики – филиала Национального исследовательского ядерного университета «МИФИ» (ИАТЭ НИЯУ «МИФИ»); засл. деятель науки РФ, д-р техн. наук, проф. А. Н. Печников (Военная академия связи им. С. М. Буденного). Утверждено редакционно-издательским советом университета в качестве учебного пособия ISBN 978-5-7629© СПбГЭТУ «ЛЭТИ», 2015 Оглавление ВВЕДЕНИЕ .............................................................................................................. 5 1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ СЛУЧАЙНЫХ ПРОЦЕССОВ .............. 6 1.1. Основные определения ................................................................................ 6 1.2. Основные виды случайных процессов ....................................................... 9 1.2.1. Стационарные случайные процессы .................................................... 9 1.2.2. Гауссовы (нормальные) случайные процессы .................................. 10 1.2.3. Процессы с независимыми приращениями ....................................... 12 1.2.4. Марковские случайные процессы ...................................................... 13 1.3. Классификация случайных процессов ..................................................... 14 2. НЕПРЕРЫВНЫЕ СЛУЧАЙНЫЕ ПРОЦЕССЫ ............................................. 17 2.1. Взаимосвязь сечений случайных процессов ............................................ 17 2.2. Спектральная плотность ............................................................................ 19 2.3. Векторный случайный процесс ................................................................. 20 3. СЛУЧАЙНЫЕ ПРОЦЕССЫ С ДИСКРЕТНЫМ ВРЕМЕНЕМ .................... 24 3.1. Граф состояний, классификация состояний и их вероятности .............. 24 3.2. Марковские случайные процессы с дискретными состояниями и дискретным временем (цепи Маркова) ........................................................... 29 3.3. Поглощающие состояния ........................................................................... 37 4. СЛУЧАЙНЫЕ ПОТОКИ .................................................................................. 40 4.1. Процесс гибели и размножения ................................................................ 40 4.2. Потоки событий .......................................................................................... 41 4.3. Потоки Пальма и потоки Эрланга ............................................................. 48 5. ПОЛУМАРКОВСКИЕ ПРОЦЕССЫ ............................................................... 50 5.1. Основные понятия и определения ............................................................ 50 5.2. Однородный процесс марковского восстановления и полумарковское ядро ...................................................................................................................... 52 5.3. Классификация полумарковских процессов и их состояний ................. 58 5.4. Применение полумарковских процессов ................................................. 59 ЗАКЛЮЧЕНИЕ ..................................................................................................... 62 Список рекомендуемой литературы .................................................................... 63 3 Перечень сокращений в.к.ф. н.к.ф. м.о. МП ПМП с.в. с.п. с.к.о. – – – – – – – – взаимная корреляционная функция нормированная корреляционная функция математическое ожидание марковский процесс полумарковский процесс случайная величина случайный процесс среднее квадратическое отклонение 4 ВВЕДЕНИЕ Повышение качества и эффективности современных сложных систем требует проведения всестороннего анализа специфики их использования, с целью построения адекватных моделей для описания и оценки качества их функционирования. Одним из наиболее разработанных математических аппаратов для моделирования систем различного назначении являются случайные процессы. В первой главе приведены основные понятия теории случайных процессов (определения, виды, классификация). Во второй главе описаны непрерывные случайные процессы: проведен анализ взаимосвязи сечений случайных процессов, дано понятие спектральной плотности, определен векторный случайный процесс (гауссовский процесс). В третьей главе проведен анализ специфических особенностей случайных процессов с дискретным временем. Рассмотрены графы состояний и дана их классификация. Проведен анализ особенностей марковских случайных процессов с дискретными состояниями и дискретным временем (цепей Маркова). В четвертой главе дано описание основных особенностей случайных потоков (процесс гибели и размножения, потоки событий, потоки пальма и потоки Эрланга). В пятой главе описаны общие свойства полумарковских процессов (основные понятия и определения, классификация полумарковских процессов и их состояний, однородный процесс марковского восстановления). Приведен ряд примеров описания и оценки функционирования различных систем (процессов, технологий). Настоящее учебное пособие поддерживает изучение дисциплины «Случайные процессы и системы массового обслуживания» направления 220100 «Системный анализ и управление». Кроме того, оно может быть полезно для студентов направлений 220400 «Управление в технических системах» и 230400 «Информационные системы и технологии» как на уровне бакалаврской подготовки, так и на уровне ряда магистерских программ, а также инженерно-технических и научных работников этой предметной области и аспирантов научных специальностей 05.13.01, 05.13.06, 19.00.03 и др. 5 1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ СЛУЧАЙНЫХ ПРОЦЕССОВ 1.1. Основные определения Определение 1.1. Случайным процессом (с. п.) X(t) называется процесс, значение которого при любом фиксированном t = t0 является случайной величиной (с. в.) X(t0). Случайная величина X(t0), в которую обращается с. п. при t = t0, называется сечением случайного процесса, соответствующим данному значению аргумента t. В дальнейшем, говоря о сечении с. п., мы не всегда будем отмечать нулевым индексом то значение аргумента t, которому оно соответствует, а будем по мере надобности говорить об одном и том же выражении, то как о случайном процессе (при переменном t), то как о случайной величине (при фиксированном t). Замечание 1.1. Для процесса с «качественными состояниями» роль случайной величины играет «случайное состояние системы, в которой протекает процесс», т. е. одно из множества возможных в момент t состояний. Аналогично тому, как представлялась с. в. в виде функции элементарного события ω, появляющегося в результате опыта, можно и с. п. записать в виде функции двух аргументов – времени t и элементарного события ω. X (t )  φ(t,ω), ω , t T , X (t )  S (1.1) где ω – элементарное событие,  – пространство элементарных событий, Т – область (множество) значений аргумента t функции X(t), S – множество возможных значений случайного процесса X(t). Пусть опыт, в ходе которого с. п. протекает так или иначе, уже произведен, т. е. произошло элементарное событие ω . Это значит, что с. п. уже не случаен, и зависимость его от t приняла вполне определенный вид: это уже обычная, неслучайная функция аргумента t. Такая функция носит название реализации случайного процесса X(t) в данном опыте. Реализацией случайного процесса X(t) называется неслучайная функция x(t), в которую превращается случайный процесс X(t) в результате опыта; другими словами, конкретный вид, принятый с. п. X(t), который наблюдался на отрезке времени от 0 до τ . 6 x(t) x(τ) x(0) t τ Рис. 1.1. Реализация случайного процесса Пользуясь формулой (1.1), можно записать реализацию как функцию φ от аргумента t, изменяющегося в пределах множества Т, при фиксированном элементарном событии ω0 : x(t )  φ(t,ω0 ), t T . (1.2) Любая реализация случайного процесса x(t) принадлежит множеству S возможных значений случайного процесса X(t): x(t )  S . Если произведено несколько опытов, в результате каждого из которых наблюдалась какая-то реализация с. п. xi(t) (i – номер опыта), то получим семейство реализаций случайного процесса: x1(t), x2(t), …, xi(t) (рис. 1.2). xi(t) x3(t) x1(t) x2(t) t Рис. 1.2. Семейство реализаций случайного процесса Семейство реализаций случайного процесса – основной экспериментальный материал, на основе которого можно получать основные 7 (необходимые) характеристики с. п. Семейство реализаций с. п. аналогично совокупности наблюденных значений с. в. X, с той разницей, что здесь наблюдаются не числовые значения, а функции. Пример 1.1. Производится n опытов, в каждом из которых регистрируется число X(t) отказов (сбоев) ЭВМ от начала работы до момента t. Случайный процесс X(t) принимает целочисленные значения 0, 1, 2, 3, ..., сохраняя их в промежутках между скачками, происходящими в моменты, когда происходит очередной отказ; его сечение X(t) при любом фиксированном t – дискретная случайная величина, с множеством возможных значений S = {0, 1, 2, 3, ...}. Реализация Xi(t) с. п. X(t) в i-м опыте представляет собой неслучайную ступенчатую функцию, скачки единичной величины которой происходят в моменты времени ti1, ti2, …, tin, … (рис. 1.3). xi(t) 4 3 2 1 ti1 ti2 ti3 t ti4 τ t Рис. 1.3. Реализация случайного процесса (пример) Реализации x1(t), x2(t), …, xi(t), …, xn(t) различны между собой (моменты скачков не совпадают), поэтому изобразить на графике семейство реализаций трудно. Следует представить наложение друг на друга n ступенчатых функций, различающихся моментами скачков, с величиной, равной единице. Понятие случайного процесса (пояснения). С. п. X(t) представляет собой функцию, которая при любом t является с. в. (сечением случайного процесса). Понятие с. п. является обобщением понятия с. в. на случай, когда условия опыта не постоянны, а меняются (время t «течет»). С. в. X соответствует случайному явлению в неизменных условиях опыта, а с. п. X(t) – в изменяющихся условиях опыта. Каждое сечение с. п. X(t) при заданном t есть с. в., а совокупность всех сечений при всевозможных t и есть с. п. X(t). 8 Таким образом, с. п. представляет собой систему с. в. – всех сечений этого процесса. Так как существует бесконечное число сечений, то анализировать такую систему с. в. практически невозможно. Однако заметим, что произвольную функцию f(t) аргумента t можно достаточно точно (хотя и приближенно) представить последовательностью ее значений в точках t1, t2, … , tk: f(t1), f(t2), … , f(tk). Чем больше количество k этих точек, тем точнее будет замена функции f(t) последовательностью значений f(t1), f(t2), … , f(tk) (рис. 1.4). f(t) t1 t2 t tk t3 Рис. 1.4. Разбиение функции на последовательность значений Аналогично будет обстоять дело и со с. п. X(t). Его можно приближенно заменить совокупностью (системой) с. в. X(t1), X(t2), …, X(tk) – его сечений в точках t1, t2, …, tk. Чем больше сечений будет рассматриваться, тем более подробное представление о с. п. мы получим. На практике всегда приходится упрощать задачу (модель), заменяя ее более доступной. Необходимо при изучении интересующих нас свойств с. п. обойтись как можно меньшим числом сечений. 1.2. Основные виды случайных процессов 1.2.1. Стационарные случайные процессы Определение 1.2. С. п. X  , t   t  T  называется стационарным в узком смысле, если  n  1: tk T , k  1, n  h  R : tk  h T имеет место тождество FX  x1, x2 , , xn , t1, t2 , , tn   FX  x1, x2 , или (если существует плотность вероятности) 9 , xn , t1  h, t2  h, , tn  h  (1.3) f X  x1, x2 , , tn   f X  x1, x2 , , xn , t1  h, t2  h, , tn  h  . (1.4) Таким образом, для стационарного процесса X  , t  смещение начала , xn , t1, t2 , момента отсчета времени не меняет его функцию распределения. Любая числовая характеристика стационарного с. п. не зависит от t, в частности: 1) mX  t   M  X  t   M  X  0  const ; 2) D X  t   const ; 3) K X  t1, t2   K X  t2  t1   K  τ  , т.е. K X  t1, t2  зависит от разности аргументов τ  t2  t1 . Определение 1.3. Если для с. п. X  ω, t  выполняются свойства (1) и (3), то процесс называется стационарным в широком смысле. Стационарность в узком смысле влечет стационарность в широком смысле. Обратное, вообще говоря, неверно. 1.2.2. Гауссовы (нормальные) случайные процессы Определение 1.4. Пусть ξ   ξ1,ξ 2 ,…,ξ n  n-мерный случайный вектор, T ν=  ν1, ν2 ,…,νn   Rn . Характеристическая функция  определяется как T n (ν)  Mei (ν,ξ)  Mei (ν1ξ1 +…+νnξn ) , где  ν,ξ  – скалярное произведение векторов. Случайный вектор (n-мерный) ξ=  ξ1,ξ 2 ,…,ξ n  T имеет нормальное распределение, если его характеристическая функция имеет вид  n  1 T 1 n   n (ν)  exp i  m, ν   ν K ν   exp i  mk ν k   K jk ν j ν k  , 2 2   j , k 1  k 1  (1.5) где ν =  ν1, ν2 ,…,νn  , T mT   Mξ1, Mξ 2 , , Mξ n  , K  ( K jk ) – ковариационная матрица случайного вектора ξ=  ξ1,ξ 2 ,…,ξ n  : T K jk  M  ξ j mj   ___  ξk  mk   M ξ j ξ k , j, k  1, n . Определение 1.5. С. п. ξ  ω, t   t  T  называется гауссовым или нормальным, если все его конечномерные законы распределения являются 10 нормальными, т.е. характеристическая функция совместного распределения вероятностей с.в. ξ  ω, t1  , ξ  ω, t2  , n  ν1, ν2 ,   , ξ  ω, tn   ti  T i  1, n имеет вид  n  1 n , tn   exp i  mξ  tk  ν k   K  tk , tl  νk νl  2 k , l 1  k 1  , νn ; t1, t2 , . Пример 1.2. Пусть n  1 , тогда 1  ν   M  ei ξ ν        ei x ν f1  x  dx , где   x  m 2  – плотность одномерного нормального f1  x   exp   2  2 2σ   2πσ распределения. Плотность f1  x  находится по формуле обращения 1 1  i x ν f1  x   1  ν  dν . e 2  1 i m ν  σ 2 ν2 2 Покажем, что 1  ν   e . Имеем:   e ixν    1 2πσ imν e 2    2πσ 2  e e  x  m 2 2σ 2 x m y  dx y i σ 2 ν  2 2σ 1 2   e i  y m ν  y2 1 2 i m ν  i y ν y e 2σ 2 dy  e 2σ dy  e  2πσ 2 2πσ 2  1  2 2 σ 2 ν2 z  y i σ 2 ν i m ν σ 2 ν2 i σ 2 ν  z 1  i m ν  σ 2 ν2 e 2 2 e 2 dy e 2 .   e 2σ dz  e 2 2 2πσ i σ ν  Для с. п. вводят последовательность характеристических функций i ξ ω, t ν 1  ν1; t1   M  e  1  1  ,    i ξ  ω, t1  ν1  ξ  ω, t2  ν2   2  ν1, ν2 ; t1, t2   M  e  ,   3  i ξ ω, t ν    j j   3  ν1, ν 2 , ν3; t1, t2 , t3   M  e j 1 ,     11 (1.6) Характеристическую функцию можно разложить в ряд. Будем разлагать в ряд не саму характеристическую функцию, а ее натуральный логарифм ψ  ν   ln 1  ν  : ψ(ν)   λ k  kk!  iν  . k 1 (1.7) Коэффициенты разложения λ k называются комулянтами. Они связаны с моментами следующим образом: λ1  M  x   m λ2  D  x  M 2 λ3  M 3 λ 4  M 4  3M 22 λ 5  M 5  10 M Если случайная величина распределена по Гауссу, то все комулянты выше второго порядка равны нулю. Замечание 1.2 (к определению гауссова процесса). Многомерный с. п. ξ  ω, t    ξ1  ω, t  , , ξ k  ω, t   называется гауссовым, если гауссовым является совместное распределение любых величин ξi1  ω, t1  , ξi2  ω, t2  , , ξin  ω, tn  . T Замечание 1.3. Комплексным гауссовым с. п.  K  , t  называется с. п. ξ K  ω, t   ξ1  ω, t   iξ 2  ω, t  , ξ1  ω, t  , ξ 2  ω, t  образуют в совокупности двумерный гауссов процесс. Для комплексного гауссова процесса корреляционная функция комплексна: вида где      Kξ  t1, t2   M  ξ K  ω, t1   m  t1  ξ K  ω, t2   m  t2   .   1.2.3. Процессы с независимыми приращениями Определение 1.6. Процесс ξ  ω, t   t  T  называется процессом с независимыми приращениями, и  tk T , k  1, n : t1  t2   tn если случайные для величины  n 1 ξ  ω, t1  ,  ξ  ω, t2   ξ  ω, t1   , ,  ξ  ω, tn   ξ  ω, tn 1   являются независимыми, т.е.: 12 P  ξ  ω, tk   ξ  ω, tk 1   1 ξ ω, tk 1   ξ ω, tk   2    P  ξ  ω, tk   ξ  ω, tk 1   1   P  ξ  ω, tk 1   ξ  ω, tk    2  . Определение 1.7. Процесс с независимыми приращениями называется однородным, если: а) он определен при t  R  [0, ) и ξ  ω, 0   0; б) закон распределения случайной величины ξ  ω, t  h     ω, t  не зависит от t. ξ  ω, t1  , Определение 1.8. Если случайные величины ξ  ω, t2   ξ  ω, t1  , , ξ  ω, tn   ξ  ω, tn 1  являются, вообще говоря, зависимыми, но некоррелированными, то процесс ξ  ω, t  называется процессом с ортогональными приращениями. Замечание 1.4. Процесс с независимыми приращениями полностью определяется одномерным распределением Ft  x  и распределением приращений процесса, т.е. для задания такого процесса достаточно знать только двумерную функцию распределения Ft1, t2  x1, x2  . 1.2.4. Марковские случайные процессы С. п., эволюция которого после любого фиксированного момента времени t и до момента времени t является условно независимой при известном состоянии процесса в момент времени t (в настоящем), называется марковским случайным процессом, а свойство условной независимости «будущего» от «прошлого» при заданном «настоящем» называется марковским свойством. Определение 1.9. Пусть ξ  ω, t   t  T  – с. п., конечномерные функции плотности вероятности которого ft1, t2 , , tn  x1, x2 , n 1 и tk  T , k  1, n : 0  t1  t2  функция плотности вероятности f  xn | xn 1, xn  2 , , xn  заданы для всех  tn . Если при этом условная , x1   f  xn | xn 1  , (1.8) где xn 1 – состояние в данный момент; xn – состояние в будущем; xn 2 , xn 3, , x1 – прошлые состояния, то с. п. называется марковским процессом. 13 Пример 1.3 (марковского процесса, используемого в модели расчета риска столкновений воздушных судов). Рассмотрим полет воздушного судна, с которым может произойти катастрофа, которую мы рассматриваем здесь как мгновенное событие. Введем некоторую случайную функцию   ,t  , описывающую состояние воздушного судна 0, если к моменту времени t катастрофы нет, ξ  ω, t    1, если к моменту времени t катастрофа произошла. Покажем, что ξ  ω,t  – марковский с. п. Если в момент времени t ξ  , t   0 , то прошлое – нормальный полет, не дает никакой информации о том, произойдет катастрофа в будущем или нет. Прошлое не информативно для будущего. Если же в момент времени t   , t   1, то есть на текущий момент факт катастрофы имеет место, то для описания состояния в будущем неважна информация из прошлого о том, когда эта катастрофа произошла. 1.3. Классификация случайных процессов С. п. принято классифицировать по различным признакам, учитывая плавность или скачкообразность реализации, фиксированность или случайность моментов, в которые происходят скачки, вид закона распределения отдельного сечения или совокупности сечений процесса и др. Самая элементарная классификация с. п. – «по времени» и «по состояниям». Определение 1.10. С. п. X(t) называется процессом с дискретным временем, если система, в которой он протекает, может менять свои состояния только в моменты t1, t2, …, ti, …, число которых конечно или счетно. Множество Т является дискретным. Пример с. п. с дискретным временем – процесс работы технического устройства, которое осматривается в моменты t1, t2, … и переводится в результате осмотра из одной категории в другую. Если рассматривается одномерный с. п. X(t) с дискретным временем, то его сечения в моменты t1, t2, … образуют последовательность с. в.: X(t1), X(t2), ... В качестве аргумента последовательности может быть выбран номер значения момента перехода: X(1), X(2), ... 14 Определение 1.11. С. п. X(t) называется процессом с непрерывным временем, если переходы системы из состояния в состояние могут происходить в любой момент t наблюдаемого периода τ . Для процесса с непрерывным временем множество Т моментов, когда система меняет свое состояние, несчетно (они непрерывно заполняют рассматриваемый участок оси абсцисс). Примеры с. п. с непрерывным временем: 1) X(t) – число отказов технического устройства от начала работы до момента t; 2) число N(t) заболевших в ходе развития эпидемии к моменту времени t. Определение 1.12. Одномерный с. п. X(t) называется процессом с непрерывными состояниями, если его сечение в любой момент t представляет собой не дискретную, а непрерывную (или смешанную) с. в., и, значит, множество ее значений S несчетно. Аналогично, многомерный (векторный) с. п. называется процессом с непрерывными состояниями, если при любом t множество возможных значений случайного вектора, определяющего состояние системы S, в которой протекает процесс, несчетно. Примеры с. п. с непрерывными состояниями: 1) напряжение U(t) питания ЭВМ в момент t; 2) давление газа P(t) в заданном резервуаре в момент t; 3) параметры, характеризующие в момент t состояние космической ракеты, выводимой на орбиту (многомерный с. п. с непрерывными состояниями). Определение 1.14. С. п. называется процессом с дискретными состояниями, если в любой момент времени t множество его состояний S конечно или счетно; другими словами – его сечение в момент t характеризуется дискретной с. в. X(t) (в многомерном случае – несколькими дискретными с. в.). Замечание 1.5. Все с. п. с «качественными» состояниями относятся к категории процессов с дискретными состояниями; сечение такого процесса представляет собой случайное событие – аналог дискретной случайной величины. Вывод. В зависимости от характера множества Т значений аргумента t, в которые возможны переходы системы из состояния в состояние, а также множества S самих состояний все случайные процессы можно разделить на четыре класса (вида): A) Процессы с дискретными состояниями и дискретным временем. B) Процессы с дискретными состояниями и непрерывным временем. 15 C) Процессы с непрерывными состояниями и дискретным временем. D) Процессы с непрерывными состояниями и непрерывным временем. Примеры процессов разных видов. А: Некто купил m билетов выигрышного займа, которые могут выигрывать и погашаться в заранее известные моменты тиражей t1, t2, … С.п. X(t) – число билетов, выигравших до момента t. B: Техническое устройство состоит из n узлов, которые могут в ходе работы устройства отказывать (выходить из строя). Случайный процесс X(t) – число узлов, отказавших до момента t. Еще пример процесса вида B: устройство может под действием случайных факторов находиться в одном из состояний: S1 – работает исправно; S2 – работает с перебоями; S3 – остановлено, ведется поиск неисправности; S4 – ремонтируется; S5 – окончательно вышло из строя, списано. Сечение такого процесса представляет собой, как для любого процесса с «качественными состояниями», обобщенную с. в. дискретного типа, «возможные значения» которой описываются не числами, а словами. C: В определенные моменты времени t1, t2, … регистрируется температура воздуха Q(t) в заданной точке пространства. Последовательность значений этой величины – с. п. Q(t) с непрерывными состояниями и дискретным временем. D: Процесс изменения напряжения U(t) в электросети представляет собой с. п. с непрерывными состояниями и непрерывным временем. Для различных видов с. п. разработаны различные методы их изучения и описания. 16 2. НЕПРЕРЫВНЫЕ СЛУЧАЙНЫЕ ПРОЦЕССЫ 2.1. Взаимосвязь сечений случайных процессов Известно, что степень линейной зависимости (связи) между двумя с. в. X и Y определяется их ковариацией: K xy  M ( x  mx )( y  m y )   M  XY   mx m y . (2.1) Аналогичная характеристика вводится и для с. п. Рассмотрим две с. в. – два сечения с. п. для моментов t и t': X(t) и X(t'). Для этих двух с. в. можно найти ковариацию (обозначим ее Kx(t, t')): 0  K x  t , t '   M  X (t ) X (t )   M  X (t ) X (t )   m x (t )m x (t ) . (2.2)   Определение 2.1. Корреляционной функцией (к. ф.) с. п. X(t) называется неслучайная функция Kx(t, t'), которая при каждой паре значений аргументов t и t' равна ковариации соответствующих сечений с. п.: X(t) и X(t'). Основные свойства корреляционной функции Kx(t, t') с. п. X(t): 1. При равенстве аргументов t и t' к. ф. равна дисперсии с.п. (по 2.2): K x  t , t   M  X (t ) X (t )   m x (t )m x (t )  M  X 2 (t )   m 2x (t )  Dx (t ) .   (2.3) 2. К. ф. Kx(t, t') симметрична относительно своих аргументов: Kx(t, t')= Kx(t', t). (2.4) Это свойство непосредственно вытекает из определения к. ф. Kx(t, t') и аналогично свойству симметричности ковариационной матрицы системы с. в. относительно главной диагонали. 3. К. ф. с. п. X(t) является положительно определенной, т. е. выполняется соотношение (2.5)   a (t )a (t ) K (t, t )dtdt   0 , BB где а(t) – произвольная функция аргумента t; В – произвольное подмножество множества T, на котором определен с. п. X(t). Это свойство аналогично свойству положительной определенности корреляционной матрицы Kij системы с. в. (X1, ..., Xn): 17 n n   ai a j Kij  0 , (2.6) i 1 j 1 справедливому для любых чисел al, a2, ... , аn. Последнее неравенство вытекает из условия, что дисперсия линейной функции случайных величин n  n n a X D a X не может быть отрицательной, т. к.  i i   i i     ai a j Kij  0 . i 1  i 1 j 1 i 1 n При увеличении числа сечений n с. п. X(t) корреляционная матрица Kij в пределе переходит в к. ф. Kx(t, t'), последовательность чисел аi – в функцию a(t), a двойная сумма – в двойной интеграл. К. ф. Kx(t, t') может быть как положительной, так и отрицательной, она характеризует не только степень тесноты линейной зависимости между двумя сечениями X(t) и X(t') с. п., но и разброс этих сечений относительно м. о. mx(t). Тесноту линейной зависимости двух с. в. X и Y характеризует коэффициент корреляции: rxy  K xy σ xσ y . Аналогичная характеристика вводится и для с. п. X(t). Определение 2.2. Нормированной корреляционной функцией (н. к. ф.) rx(t, t') с. п. X(t) называется функция, полученная делением к. ф. Kx(t, t')на произведение с.к.о.: rx (t , t ')  K x (t , t ')  σ x (t )σ x (t ') K x (t , t ') Dx (t ) Dx (t ') . Свойства н. к. ф. rx(t, t') вытекают из ее определения: 1. При равенстве аргументов (t = t') н. к. ф. равна единице: rx(t, t) = 1. (2.7) 2. Н. к. ф. rx(t, t') симметрична относительно своих аргументов: rx(t, t') = rx(t', t). 3. Н. к. ф. по модулю не превосходит единицу: rx (t , t ')  1 . 4. Имеет место соотношение: (2.8) (2.9)   a (t )a (t )rx (t, t )σ x (t )σ x (t )dtdt   0 . BB Чтобы найти к. ф. Kx(t, t') с. п. X(t) (и его н. к. ф. rx(t, t')), недостаточно знать одномерный закон распределения с. п. X(t); в общем случае требуется 18 знание его двумерного закона распределения для двух сечений – X(t) и X(t'). Если этот закон распределения известен, то можно для любой пары значений t и t' найти корреляционный момент: 0  K x  t , t '   M  X (t ) X (t )   M ( X (t )  m x (t ))( X (t )  m x (t ))  . (2.10)   Или выражая его через смешанный первый начальный момент: 0  K x  t , t '   M  X (t ) X (t )   M  X (t ) X (t )   m x (t )m x (t ) . (2.11)   Например, если известна совместная плотность распределения двух сечений с. п. X(t): f (t , t , x, x ) , то формулы (2.10) и (2.11) примут вид: K (t , t )        K (t , t )  ( x  m x (t ))( x   m x (t )) f (t , t , x, x )dxdx  ,       xx f (t , t , x, x )dxdx   m x (t )m x (t ) . (2.12) (2.13) Определение 2.3. С. п. X(t), у которого м.о. постоянно (mx(t) = const), а к. ф. зависит только от разности аргументов (Kx(t, t') = Kx(t' – t) = Kx(τ), где τ = t' – t), будем называть стационарным в широком смысле. 2.2. Спектральная плотность При изучении с. п. иногда используется их спектральное представление в виде спектральной плотности, которая базируется на преобразовании Фурье. Для одной реализации с. п. можно определить преобразование Фурье как случайную комплексную функцию частоты (если процесс имеет конечную энергию и квадратично интегрируем): X( f )    x (t )e i 2πft dt. (2.14)  Но для описания ансамбля реализаций данная функция практически бесполезна. В этом случае используется спектральная плотность реализации – функция, характеризующая распределение энергии с. п. по оси частот: 2 Sx ( f )  X ( f ) . (2.15) Получить спектральную плотность процесса можно, рассчитав среднее функции (2.15) по всем реализациям. 19 Спектральная плотность стационарного в широком смысле центрированного с. п. может быть найдена как преобразование Фурье от корреляционной функции: Sx ( f )     k x ( )e i 2πfτ dτ. (2.16) В свою очередь, обратное преобразование Фурье позволяет найти корреляционную функцию на основе функции спектральной плотности: Sx ( f )     k x ( )e i 2πfτ dτ. (2.17) Если принять в формулах (2.16) и (2.17) f    0 , то:   S x (0)  σ 2x  k x (0)  k x (τ)dτ, (2.18) S x ( f )df . (2.19)     Свойства спектральной плотности: 1. Энергетический спектр стационарного процесса (вещественного или комплексного) – неотрицательная величина: (2.20) S x ( f )  0. 2. Энергетический спектр вещественного стационарного в широком смысле с. п. есть действительная и четная функция частоты: (2.21) S x ( f )  S x ( f ). 3. Чем «шире» энергетический спектр стационарного в широком смысле с. п., тем «уже» его корреляционная функция (и наоборот). 2.3. Векторный случайный процесс Ранее рассматривались только характеристики одного (скалярного) с. п. X(t). Рассмотрим векторный с. п., у которого имеется k составляющих: X (t )  ( X1(t ), X 2 (t ),..., X k (t )) . (2.22) Пусть с. п. Xi(t) имеет характеристики mi(t) и Ki(t, t') (i =1,2, ..., k). Эти характеристики в какой-то степени описывают поведение только отдельного с. п. Xi(t) (i = 1,2, ... ,k), но не определяют «взаимных характеристик» (зависимостей между составляющими) векторного с. п. X (t ) . В качестве 20 такой характеристики рассматривается взаимная корреляционная функция Rij(t, t') двух случайных (скалярных) процессов: Xi(t) и Xj(t'):  0  Rij  t , t '   M  X i (t ) X j (t )  . (2.23)   Определение 2.4. Взаимной корреляционной функцией Rij(t, t') двух с. п. Xi(t) и Xj(t') называется неслучайная функция двух аргументов t и t', которая при каждой паре значений t и t' равна ковариации двух сечений с. п. Xi(t) и Xj(t'). Эти сечения на рис. 2.1 изображены условно точками 1 и 2. xi (t ), x j (t ) xi ( t ) xi (t ') xi ( t ) 1 3 x j (t ') x j (t ) x j (t ) 2 4 t t' t Рис. 2.1. Сечения двух случайных процессов Cвойства взаимной корреляционной функции (в. к. ф.): 1. Взаимная корреляционная функция  0  Rij  t , t '   M  X i (t ) X j (t )    в  0  R t ', t  M X ( t ') X общем случае не равна в. к. ф.   i ij  j (t )  , так как   ковариация между сечениями Xi(t) и Xi(t') (точки 1 и 2) на рис. 2.1) в общем случае не равна ковариации между сечениями Xj(t) и Xj(t') (точки 3 и 4 на рис. 2.1): Rij  t, t '   Rij  t ', t  . (2.24) 2. При одновременной перемене мест индексов и аргументов в. к. ф. не изменяется: Rij  t, t '   R ji  t ', t  . 21 Это следует из соотношения: 0   0  Rij  t , t '   M  X i (t ) X j (t )   M  X j (t ) X i (t )   R ji  t ', t  . (2.25)     3. При равенстве индексов (j = i) в. к. ф. равна к. ф. с. п. Xi(t) (см. точки 1 и 4 на рис. 2.1):  0  Rii  t , t '   M  X i (t ) X i (t )   Ki  t , t '  . (2.26)   Нормированная взаимная корреляционная функция определяется по следующей формуле: rij  t , t '   Rij  t , t '  σi (t )σ j (t ') , (2.27) где σi (t )  Di (t )  Ki (t, t ) – с.к.о. Xi(t); σ j (t )  D j (t )  K j (t , t ) – с.к.о. Xj(t). Из свойств (2.25) – (2.27) вытекают свойства нормированной взаимной корреляционной функции: rij  t, t '   r ji  t , t  , (2.28) rii  t , t '   ri  t , t  . В качестве характеристик векторного с. п. X (t )  ( X1(t ), X 2 (t ),..., X k (t )) рассматриваются: 1. М. о. векторного с. п. – неслучайный вектор, зависящий от t: m(t )  (m1(t ), m2 (t ),..., mk (t )) , составляющие которого равны м.о. соответствующих с. п. mi (t )  M  X i (t ) , i  1,2,..., k . (2.29) (2.30) 2. Квадратная матрица (размерности k  k ) взаимных корреляционных функций векторного с. п. X (t ) : 22  R11  t , t '  R12  t , t '    R21  t , t '  R22  t , t '   . . Rij  t , t '     Ri1  t , t '  Ri 2  t , t '   . .   R  t, t '  R  t, t '  k2  k1 ... R1 j  t , t '  ... ... R2 j  t , t '  . . ... Rij  t , t '  . ... . Rkj  t , t '  R1k  t , t '    ... R2k  t , t '    . .  . (2.31). ... Rik  t , t '    . .  ... Rkk  t , t '   Элементы матрицы Rij  t , t '  определяются формулой (2.23). В общем случае матрица Rij  t , t '  несимметрична, т. е. Rij  t, t '   R ji  t , t '  . По главной диагонали матрицы Rij  t , t '  стоят k корреляционных функций соответствующих с. п.: 0  Rii  t , t '   Ki  t , t '   M  X i (t ) X i (t )  . (2.32)   С. п. Xi(t) и Xj(t) называются некоррелированными, если их в. к. ф. Rij  t, t '  равна нулю при любых значениях t (для i  j ). Векторный с. п. X (t ) называется процессом с некоррелированными составляющими, если матрица в. к. ф. Rij  t , t '  является диагональной, т. е. Rij  t, t '   0, i  j . 23 3. СЛУЧАЙНЫЕ ПРОЦЕССЫ С ДИСКРЕТНЫМ ВРЕМЕНЕМ 3.1. Граф состояний, классификация состояний и их вероятности Рассмотрим некоторую систему S, в которой протекает с. п. с дискретными состояниями: (3.1) s1, s2 , ... , si , ... , число которых конечно (или счетно). Эти состояния могут быть качественными (т. е. описываться словами) или же каждое из них характеризуется с. в. (либо случайным вектором). Проанализируем множество состояний (3.1) с точки зрения его структуры, т.е. возможности системы S переходить из состояния si в некоторое состояние sj либо непосредственно, либо через другие состояния. Для этого удобно пользоваться наглядной схемой – графом состояний. Графы состояний бывают неориентированными и ориентированными. Неориентированный граф – совокупность точек (вершин графа) с соединяющими некоторые из них отрезками (ребрами графа). Ориентированный граф – это совокупность точек (вершин) с соединяющими некоторые из них ориентированными отрезками (стрелками). Вершины графа соответствуют состояниям системы. Вершину будем изображать кругом, в который вписано обозначение состояния; стрелка (направленная дуга), ведущая из вершины si в вершину sj, будет обозначать возможность непосредственного (прямого) перехода системы S из состояния si, в состояние sj (рис. 3.1). Сам граф системы S будем обозначать буквой G. Кроме стрелок, связывающих различные состояния si и sj, возможны и обратные стрелки (петли), возвращающие систему из состояния si в то же состояние si (рис. 3.2). Переход по петле, ведущей из состояния si в него же, означает задержку системы в состоянии si. 24 s1 s2 s6 s5 s4 s3 s4 Рис. 3.1. Пример графа состояний Рис. 3.2. Вершина с петлей Пример 3.1. Система S представляет собой техническое устройство (ТУ), с возможными состояниями: s1 – ТУ исправно; s2 – ТУ неисправно, но это не обнаружено; s3 – неисправность обнаружена, ведется поиск ее источника; s4 – источник неисправности найден, ведется ремонт; s5 – проводится послеремонтный осмотр (после этого осмотра, если ТУ восстановлено в прежнем виде, то оно возвращается в состояние s1, если нет, то признается негодным и списывается); s6 – ТУ списано; s7 – ведется профилактический осмотр (если обнаружена неисправность, ТУ направляется в ремонт). Граф состояний ТУ приведен на рис. 3.3. s1 s5 s2 s6 s3 s7 s4 Рис. 3.3. Граф возможных состояний технического устройства В дальнейшем будем полагать, что переход системы S из состояния si в другое состояние sj осуществляется мгновенно и в любой момент времени система S может находиться только в одном из возможных состояний. Классификация состояний. 25 s1 s2 s9 s3 s4 s6 s5 s7 s8 Рис. 3.4. Пример графа с источником, поглощающим и изолированным состояниями Состояние si называется источником, если система S может выйти из этого состояния, но попасть в него обратно уже не может, т. е. на графе G в состояние si не ведет ни одна стрелка. На рис. 3.4 источником является состояние s2. Состояние si называется поглощающим, если система S может попасть в это состояние, но выйти уже не может. Для графа G это означает, что из этого состояния не ведет ни одна стрелка к другому состоянию (для графа состояний ТУ, приведенного на рис. 3.3, состояние s6 – поглощающее; для графа, приведенного на рис. 3.4, поглощающее состояние s8). Если система S может непосредственно перейти из состояния si в состояние sj, то состояние sj называется соседним по отношению к состоянию si. Если система S может непосредственно перейти из состояния si в состояние sj и из состояния sj в состояние si, то состояния si, sj называются соседними. Для графа состояний ТУ (рис. 3.3) состояние s3 является соседним по отношению к состоянию s2, а состояния s1 и s4 нет (по отношению к состоянию s2), так как на графе нет стрелок, непосредственно исходящих из состояния s2 в эти состояния. Состояния s1 и s7 также являются соседними. Состояние si называется транзитивным, если система S может войти в это состояние и выйти из него, т. е. на графе состояний есть хотя бы одна стрелка, ведущая в si и хотя бы одна стрелка, ведущая из si. На рис. 3.3 все состояния, кроме поглощающего s6, являются транзитивными. На рис. 3.4 транзитивными являются все состояния кроме источника – s2, поглощающего состояния s8, а также изолированного состояния s9. Состояние si называется изолированным, если из него нельзя попасть ни в одно из других состояний и 26 в него нельзя попасть ни из какого другого состояния. На графе изолированное состояние si не связано ни с каким другим состоянием. Наряду с отдельными состояниями системы S рассмотрим подмножества ее состояний. Обозначим W множество всех состояний системы S (конечное или бесконечное, но счетное) и рассмотрим подмножество V  W . Подмножество V называется замкнутым (концевым), если система S, попав в одно (или находясь в одном) из состояний si V , не может выйти из этого подмножества. Например, на рис. 3.4 подмножество состояний V = {s7, s8} является концевым. Концевое подмножество состояний может включать в себя поглощающее состояние, а может и не включать. Подмножество состояний V  W называется связным или эргодическим, если из любого состояния, входящего в него, можно попасть в любое другое состояние, принадлежащее этому подмножеству. На рис. 3.4 подмножество состояний V = {s3, s4, s5, s6} является эргодическими. Эргодическим может быть и все множество W состояний системы S (например, рис. 3.1). В эргодическом множестве нет ни источников, ни поглощающих состояний. Подмножество состояний V называется транзитивным, если система S может войти в это подмножество и выйти из него, т. е. из любого состояния si V можно (за то или другое число переходов) выйти из этого подмножества – эргодическое подмножество состояний V = {s3, s4, s5, s6} (рис.3.4) является также и транзитивным. С. п., протекающий в системе S, можно трактовать как процесс блуждания системы по множеству состояний W. Если подмножество V  W является концевым, то, попав в него, система будет продолжать блуждание уже по подмножеству состояний V. Если все множество W эргодично, то блуждание будет происходить по всем его состояниям. Определение 3.1. Вероятностью i-го состояния в момент времени t называется вероятность события, состоящего в том, что в момент t система S будет находиться в состоянии si. Обозначим ее pi(t): pi (t )  p S (t )  si  , (3.2) где S(t) – случайное состояние системы S в момент t. Очевидно, что для системы с дискретными состояниями в любой момент t сумма вероятностей состояний равна единице: (3.3)  pi (t )  1 , i 27 как сумма вероятностей полной группы несовместных событий. В ряде практических задач нас интересует установившийся или стационарный режим работы системы, который устанавливается, когда от начала процесса прошло достаточно большое время. Аналогично этому и в некоторых с. п. через некоторое достаточно большое время τ устанавливается стационарный режим, в котором состояния системы хотя и меняются случайным образом, но их вероятности pi (t ) (i  1,2, ...) остаются постоянными. Обозначим эти вероятности pi : pi  lim pi (t ) . (3.4) t  Вероятности pi (i  1,2, ...) , если они существуют, называются финальными (предельными) вероятностями состояний. Финальную вероятность pi можно интерпретировать как среднюю долю времени, которую в стационарном режиме проводит система S в состоянии si. Определение 3.2. С. п., протекающий в системе S с дискретными состояниями s0, s1, …, si, …, называется марковским, если для любого момента времени t0 вероятность каждого из состояний системы в будущем (при t > t0) зависит только от ее состояния в настоящем (при t = t0) и не зависит от того, когда и как она пришла в это состояние (не зависит от прошлого (при t < t0)). Марковское свойство с. п. не следует понимать как полную независимость «будущего» от «прошлого»; т. к. в общем случае «будущее» зависит от «настоящего», т. е. вероятности pi (t ) при t > t0 зависят от того, в каком состоянии si находится система в настоящем (при t = t0) само же это «настоящее» зависит от «прошлого», от того, как вела себя система S при t < t0. Это можно сформулировать следующим образом: для марковского с. п. «будущее» зависит от «прошлого» только через «настоящее (рис. 3.6). При фиксированном «настоящем» условные вероятности всех состояний системы в «будущем» не зависят от предыстории процесса, т.е. от того, когда и как система S к моменту t0 пришла в состояние si. 28 Прошлое Будущее t < t0 t > t0 t t = t0 Настоящее Рис.3.6. Будущее зависит от прошлого только через настоящее «Настоящее» может быть задано не одним каким-то состоянием si, а целым подмножеством состояний V  W , где W – множество всех возможных состояний системы. «Настоящее» может быть задано не только одним состоянием системы S в момент t, в него можно включить те элементы из «прошлого», от которых, при заданном «настоящем», зависит будущее. Например, вероятности состояний в «будущем» могут зависеть не только от состояния si системы, но и от того, из какого состояния sj система перешла к моменту t0 в состояние si; в этом случае настоящее характеризуется не только состоянием si, в которое система перешла к моменту t0, но и состоянием sj, из которого она перешла в si. Вводя в состав параметров, характеризующих настоящее, те параметры из прошлого, от которых зависит будущее, можно «марковизировать» многие немарковские процессы, что обычно приводит к усложнению математического аппарата, ввиду увеличения числа состояний. 3.2. Марковские случайные процессы с дискретными состояниями и дискретным временем (цепи Маркова) Пусть имеется система S с дискретными состояниями s0, s1, …, si, … , sn. Предположим, что случайные переходы системы из состояния в состояние могут происходить только в определенные моменты времени t0, t1, t2, ..., которые мы будем называть шагами процесса; t0 = 0 – его началом. Сам процесс представляет собой случайное блуждание системы S по состояниям. После первого шага система может оказаться в одном (и только в одном) из своих возможных s1(2) , s2(2) , ... , sn(2) ; на состояний: s1(1) , s2(1) , ... , sn(1) ; на втором шаге – k-м шаге – s1(k ) , s2(k ) , ... , sn(k ) . Заметим, что число 29 состояний может быть бесконечным (счетным). Пока ограничимся конечным числом состояний n. Пусть граф состояний системы S имеет вид, представленный на рис. 3.7. s1 s2 s3 si sn-1 s4 s5 s6 sn Рис. 3.7 Пример графа состояний Процесс блуждания системы S по состояниям можно представить как последовательность или «цепь» событий, состоящих в том, что в начальный момент t0 = 0 система находится в одном из состояний (в состоянии s1(0) ); после первого шага перешла состояние s5(1) , на втором шаге перешла в s3(2) и т. д. «Траектория» системы, блуждающей по состояниям S выделена на рис. 3.7 жирными линиями, а возможные переходы показаны пунктирными стрелками. На каких-то шагах система может задерживаться в том или другом из своих состояний si, что показано «возвратной стрелкой» на рис. 3.7 или может вернуться в него после ряда шагов. «Траектория» блуждания системы по графу состояний, представляет собой реализацию с. п., полученную в результате одного опыта. При повторении опыта, естественно, реализации в общем случае не совпадают. Пример 3.2. Рассматривается с. п.: система представляет собой техническое устройство (ТУ), которое осматривается в определенные моменты времени (скажем, через сутки), и ее состояние регистрируется в отчетной ведомости. Каждый осмотр с регистрацией представляет собой «шаг» процесса. Возможны следующие состояния ТУ: s1 – полностью исправно; s2 – частично неисправно, требует наладки; s3 – обнаружена серьезная неисправность, требует ремонта; s4 – признано непригодным, списано. 30 Допустим, что и наладка, и ремонт продолжаются менее суток и после их выполнения ТУ возвращается в состояние s1 (полностью исправно) или списывается. Граф состояний ТУ имеет вид, изображенный на рис. 3.8. s1 s2 s3 s4 Рис. 3.8. Граф состояний ТУ Состояние s4 на рис. 3.8 поглощающее. Если известно, что в начальный момент ТУ полностью исправно, то P S (0)  s1  1 ; далее процесс протекает случайным образом: после каждого шага (осмотра, контроля) ТУ с какой-то вероятностью может оказаться в одном из своих состояний. Реализация случайного процесса блуждания системы по состояниям может иметь, например, такой вид: s1(0) , s1(1) , s2(2) , s1(3) , s3(4) , s1(5) , s4(6) , что означает, что ТУ в начальный момент исправно; при первом осмотре – также исправно; при втором – частично неисправно, требует наладки; при третьем исправно; при четвертом – обнаружена серьезная неисправность, требует ремонта; при пятом – снова исправно; при шестом – признано неисправным, списано (дальнейшее развитие процесса невозможно, так как он дошел до поглощающего состояния s4). Рассмотренный в примере процесс не вполне отражает действительность, т. к. предполагается, что в результате наладки или ремонта ТУ полностью восстанавливается полностью. Общий случай. Происходит с. п. в системе S с дискретными состояниями s0, s1, … , si, …, sn, которые она может принимать в последовательности шагов с номерами 0, 1, 2, ..., k, ... . С. п. представляет собой некоторую последовательность («цепь») событий S (k )  si , k  0,1,2, ...; i  1,2, ..., n . Основной характеристикой этой последовательности («цепи») событий являются вероятности состояний: P S (k )  si , (k  0,1, 2, ..., i  1, 2, ... , n ) , (3.5) 31 где P S (k )  si  – вероятность того, что на k-м шаге система S будет находиться в состоянии si . Распределение вероятностей (3.5) представляет собой одномерный закон распределения с. п. S(t), протекающего в системе S с «качественными» дискретными состояниями и дискретным временем t0, t1, t2, ..., tk, … . Процесс, протекающий в такой системе S, называется марковским процессом с дискретными состояниями и дискретным временем (или марковской цепью), если выполняется условие, сформулированное в п. 3.1: для любого фиксированного момента времени (любого шага k0) условные вероятности состояний системы в будущем (при k > k0) зависят только от состояния системы в настоящем (при k = k0) и не зависят от того, когда (на каком шаге, при k < k0) и откуда система пришла в это состояние. Марковская цепь представляет собой разновидность марковского процесса, в котором будущее зависит от прошлого только через настоящее. Понятие «настоящего» может быть сформулировано по-разному; например, «на k0-м шаге система находится в состоянии si », если вероятности состояний системы на последующих шагах зависят только от si , а не от предыдущих состояний системы. Если же эта вероятность зависит еще и от того, откуда (из какого состояния s j ) система пришла в состояние si , можно включить это состояние s j в описание «настоящего». Цепь, в которой условные вероятности состояний в будущем зависят только от состояния на последнем, шаге и не зависят от предыдущих, иногда называют простой цепью Маркова, в отличие от той, где будущее зависит от состояний системы не только в настоящем, но и от ее состояний на нескольких предыдущих шагах (сложная цепь Маркова). Из определения марковской цепи следует, что вероятность перехода системы S в состояние s j на (k + 1)-м шаге зависит только от того, в каком состоянии si находилась система на предыдущем k-м шаге и не зависит от ее предыстории. Одной из основных задач исследования марковской цепи является нахождение безусловных вероятностей нахождения системы S на kм шаге в состоянии si ; обозначим эту вероятность pi (k ) : pi (k )  P S (k )  si , (k  0,1,2, ... ; i  1,2, ... , n) 32 (3.6) Для нахождения этих вероятностей необходимо знать условные вероятности перехода системы S на k-м шаге в состояние s j , если известно, что на предыдущем (k–1)-м шаге она была в состоянии si . Обозначим эти вероятности   pij (k )  P S (k )  s j S (k  1)  si , (k  0,1,2, ... ; i, j  1,2, ... , n) . Вероятности называются pij (k ) переходными (3.7) вероятностями марковской цепи на k-м шаге. Вероятность pii (k ) есть вероятность того, что на k-м шаге система задержится (останется) в состоянии si . Переходные вероятности pij (k ) можно записать в виде квадратной таблицы (матрицы) размерности n  n :  p11 ( k )   p21 (k )  . P  pij ( k )    pi1 ( k )   .  p (k )  n1 p12 (k ) ... p1 j (k ) ... p22 (k ) ... p2 j (k ) ... . . pi 2 ( k ) ... . pij (k ) . . pn 2 (k ) ... . ... . . pnj (k ) ... p1n (k )   p2n (k )  .   (k  0,1,2, ...) .(3.8) pin ( k )   .  pnn (k )  На главной диагонали матрицы Р (3.8) стоят вероятности задержки системы в данном состоянии (вероятности петли) si (i = 1, 2, …, n) на k-м шаге. p11(k ), p22 (k ), ..., pii (k ), ..., pnn (k ) . (3.9) Так как на каждом шаге система S может находиться только в одном из взаимно исключающих состояний, то для любой i–й строки матрицы (3.8) сумма всех стоящих в ней вероятностей pij (k ) равна единице: n  j 1 pij (k )  1 . (3.10) Матрица Р, обладающая таким свойством, называется стохастической. Все элементы стохастической матрицы отвечают условию 0  pij (k )  1 . В силу условия (3.10) можно в матрице (3.8) не задавать вероятности задержки, а получать их как дополнения до единицы остальных членов строки: pii ( k )  1   pij ( k ) (3.11) j i 33 (это свойство будет использоваться в дальнейшем). Чтобы найти безусловные вероятности pi (k ) , недостаточно знать матрицу переходных вероятностей Р (3.8); нужно знать и начальное распределение вероятностей, т. е. вероятности состояний pi (0) , соответствующие началу процесса (t0 = 0): p1(0), p2 (0), ..., pi (0),..., pn (0), (3.12) в сумме образующие единицу: n  pi (0)  1 . (3.13) i 1 Если известно, что в начальный момент система S находится в состоянии si , то вероятность pi (0) этого состояния в формуле (3.12) равна единице, а все остальные – нулю: pi (0)  1, p1(0)  p2 (0)  ...  pi 1(0)  pi 1(0)  ...  pn (0)  0 . (3.14) Цепь Маркова называется однородной, если переходные вероятности pij (k ) не зависят от номера шага k: pij (k )  pij . Матрица переходных вероятностей для однородной цепи Маркова имеет вид:  p11   p21  . P  pij    pi1   . p  n1 p12 ... p1 j ... p22 ... p2 j ... . pi 2 . ... . pij . ... . pn 2 ... . pnj . ... . p1n   p2n  .   . pin   .  pnn  (3.15) При выводе формул далее будут рассматриваться только однородные цепи Маркова (в случае, когда цепь неоднородна, можно все переходные вероятности в формулах просто положить зависящими от номера шага k). При нахождении вероятностей состояний марковской цепи на k-м шаге pi (k ) (k = 1, 2, ...) удобно пользоваться размеченным графом состояний системы S, где возле каждой стрелки, ведущей из состояния si в состояние s j , проставлена переходная вероятность pij ; вероятности задержки на размеченном графе не проставляются, а получаются дополнением до единицы суммы вероятностей, стоящих у всех стрелок, ведущих из данного состояния si . Пример размеченного графа состояний показан на рис. 3.9. 34 p12 p23 s1 s2 p14 p41 s3 p32 p42 p25 p45 s4 p35 s5 p54 Рис. 3.9. Пример размеченного графа Для этого графа состояний вероятности задержек равны: p11  1  ( p12  p14 ), p22  1  ( p23  p25 ), p33  1  ( p32  p35 ), p44  1  ( p41  p42  p45 ), p55  1  p54 , (на размеченном графе эти вероятности обычно не обозначены, хотя иногда рисуют петли, которые выходят из состояния и обратно в него входят). Если состояние si является поглощающим (на графе из него не выходит ни одной стрелки), то вероятность задержки в этом состоянии pii  1 . Определим безусловную вероятность нахождения системы S на k-м шаге в состоянии s j (j = 1,2,…,n):   p j (k )  P S (k )  s j , (3.16) если задана матрица переходных вероятностей P  pij (или, что равнозначно, размеченный граф состояний) и начальное распределение вероятностей pi (0), (i  1, 2, ... , n ), n  pi (0)  1 . i 1 (3.17) Пусть в начальный момент (k = 0) система находилась в состоянии si . Вероятность этого события из (3.16) равна pi (0)  P S (0)  si  . Условная вероятность того, что система S на первом шаге будет находиться в состоянии s j при условии, что она находилась в состоянии si , равна переходной вероятности   pij  P S (1)  s j S (0)  si . Тогда по формуле 35 полной вероятности можно получить распределение вероятностей системы S на первом шаге   p j (1)  P S (1)  s j   n  P S (1)  s j i 1  S (0)  si  P S (0)  si   .(3.18) n  pi (0)  pij ( j  1, 2,..., n) i 1 Найдем распределение вероятностей на втором шаге, которое для цепи Маркова зависит только от распределения вероятностей на первом шаге и матрицы переходных вероятностей. Пусть на первом шаге система находится в состоянии si ; вероятность этого события уже известна (из 3.18) и равна pi (1)  P S (1)  si , i  1,2, ... , n . Условная вероятность того, что на втором шаге система S будет в состоянии s j , если на первом шаге она была в   состоянии si равна pij  P S (2)  s j S (1)  si . По формуле полной вероятности находим p j (2)  n  pi (1)  pij i 1 ( j  1, 2, ... , n ) . (3.19) Таким образом, мы выразили распределение вероятностей (3.19) на втором шаге через распределение вероятностей на первом шаге и матрицу pij . Переходя аналогично от k = 2 к k = 3 и т. д., получим рекуррентную формулу: p j (k )  n  pi (k  1)  pij ( k  1, 2, ... j  1, 2, ... , n ) . (3.20) i 1 Замечание 3.1. Если рассматривается неоднородная цель Маркова, то переходные вероятности будут зависеть от номера шага k (см. (3.7)):   pij (k )  P S (k )  s j S (k  1)  si , (k  0,1,2, ... , i, j  1,2, ... , n) . Для нахождения распределения вероятностей состояний системы на k-м шаге нужно знать начальное распределение вероятностей и k матриц переходных вероятностей pi (0), (i  1,2, ... , n), pij (1) , pij (2) , ... , pij (k ) . Рассуждения при выводе подобных формул для 36 вероятностей p j (1), p j (2), ... , p j (k ) j  1,2, ... , n состояний остаются прежними. Поэтому   p j (1)  P S (1)  s j   n  pij (1)  pi (0) n  P S (1)  s j i 1  S (0)  si  P S (0)  si   , ( j  1, 2,..., n ) i 1 а рекуррентные формулы (3.20), определяющие распределение вероятностей на k -м шаге для неоднородной цепи Маркова, принимают вид: p j (k )  n  pij (k )  pi (k  1) ( j  1, 2, ... , n; k  1, 2 ...) . i 1 3.3. Поглощающие состояния Пример 3.3. Пусть в условиях примера 1 имеет место следующая матрица переходных вероятностей: 0,7 0,1 0,1 0,1 0,2 0,6 0 0,2 . pij  0,2 0 0,5 0,3 1 Этой матрице соответствует размеченный граф состояний ТУ, изображенный на рис. 3.10. В начальный момент (t0 = 0) ТУ находится в состоянии s1 (исправно). Необходимо найти распределение вероятностей состояний ТУ для первых четырех шагов (k = 1, 2, 3, 4) и убедиться, что вероятность поглощающего состояния p j (k ) с увеличением k растет. s2 p31=0,2 s1 p21=0,2 2 p13=0,1 p12=0,1 s3 p14=0,1 p24=0,2 p34=0,3 s4 Рис. 3.10. Размеченный граф состояний ТУ для примера 1 37 Решение. Так как в начальный момент (t0 = 0) ТУ находится в состоянии s1, то p1(0)  1, p2 (0)  p3(0)  p4 (0)  0 . По формуле (3.20), полагая в ней k = 1, получим p1(1)  0,7, p2 (1)  0,1, p3(1)  0,1, p4 (1)  0,1. Снова применяя формулу (3.20), находим вероятности состояний на втором шаге: p1 (2)  0,7  0,7  0,1  0,2  0,1  0,2  0,53, p2 (2)  0,7  0,1  0,1  0,6  0,1  0  0,1  0  0,13, p3 (2)  0,7  0,1  0,1  0  0,1  0,5  0,1  0  0,12, p4 (2)  1  p1(2)  p2 (2)  p3 (2)  0,22. Еще раз, применяя формулу (3.20), находим вероятности состояний на третьем шаге: p1 (3)  0,53  0,7  0,13  0,2  0,12  0,2  0,421, p2 (3)  0,53  0,1  0,13  0,6  0,12  0  0,22  0  0,131, p3 (3)  0,53  0,1  0,13  0  0,12  0,5  0,22  0  0,113, p4 (3)  1  p1(3)  p2 (3)  p3 (3)  0,335. Таким же образом, находим вероятности состояний на четвертом шаге: p1 (4)  0, 421  0,7  0,131  0, 2  0,113  0, 2  0,3435, p2 (4)  0, 421  0,1  0,131  0,6  0,113  0  0,335  0  0,1207, p3 (4)  0, 421  0,1  0,131  0  0,113  0,5  0,335  0  0,0986, p4 (4)  1  p1(4)  p2 (4)  p3 (4)  0, 4372. Из полученного, очевидно, что возрастанием k вероятность поглощающего состояния p4(k) растет, а вероятность p1(k) состояния s1 убывает. Число блужданий. Рассмотрим нахождение числа блужданий системы S до попадания в множество невозвратных состояний. Пусть у нас имеется некоторое множество состояний системы W, с числом элементов n, которое можно разбить на множество поглощающих состояний V с числом элементов k и множество сообщающихся состояний Z (число элементов n–k). Будем полагать, что каждое состояние из V является поглощающим. Перенумеруем состояния так, чтобы поглощающие состояния имели меньшие номера. Тогда матрицу переходных вероятностей Р можно представить в виде E 0 P ,  R Q 38 где Е – квадратная единичная матрица размерности k×k, где k – число поглощающих состояний; 0 – матрица, состоящая из одних нулей (k строк и n – k столбцов), показывающая, что из поглощающих состояний (множество V) нет выхода в множество Z; R –матрица размерности (n – k строк и k столбцов), показывающая на переходы из состояний множества Z в множество поглощающих состояний V; Q – квадратная матрица размерности (n – k)×(n – k), характеризующая переходы внутри множества Z. Введем в рассмотрение li – число шагов до попадания в множество поглощающих состояний при условии, что в начальный момент времени процесс находился в состоянии i. Для состояния i имеет место равенство li  1  n  j  k 1 pij  l j (i  k  1, k  2, ... , n ) , (3.21) где суммирование производится по вероятностям из матрицы Q. Выражение (3.21) можно записать в матричном виде: l  1  Ql , (3.22) где l – вектор столбец, компонентами которого являются неизвестные li, а 1 – вектор столбец, состоящий из одних единиц. Переписывая уравнение в виде l  Ql  1 , т.е. ( E  Q)l  1 , можно получить его решение в следующем виде: l  (E  Q)11 . 39 (3.23) 4. СЛУЧАЙНЫЕ ПОТОКИ 4.1. Процесс гибели и размножения На практике очень часто встречаются системы, состояния которых образуют цепь (рис. 4.1), в которой каждое состояние si (кроме двух крайних s0 и sn ) связано прямой и обратной связью с двумя соседними, а каждое из двух крайних связано прямой и обратной связью только с одним соседним. Такая схема с. п. называется схемой гибели и размножения, а сам процесс – процессом гибели и размножения. s0 s1 s2 … si-1 si si+1 … sn-2 sn-1 sn Рис. 4.1. Процесс гибели и размножения Пример 4.1. Техническое устройство (ТУ) состоит из n одинаковых узлов. Каждый из узлов может в момент времени t быть исправным или неисправным; если узел неисправен, его ремонтируют. Состояния si системы S (ТУ) могут быть перенумерованы по числу неисправных узлов: s0 – в ТУ нет неисправных узлов; s1 – в ТУ один неисправный узел (какой – неважно); si – в ТУ i неисправных узлов 0 < i < n); sn – в ТУ все n узлов неисправны. Состояния si организованы по схеме гибели и размножения (рис. 4.1); стрелки, идущие слева направо, отвечают увеличению числа неисправных узлов; перемещения системы S по этим стрелкам происходят под влиянием отказов узлов, т. е. перехода какого-то узла из исправного состояния в неисправное; стрелки, идущие справа налево – под влиянием ремонтов (восстановлений) узлов. Считаем, что «переход» системы S из состояния si не в соседнее с ним состояние, а в какое-то другое из состояний, практически невозможен (это обычно связано с ординарностью потоков отказов и восстановлений). Многие с. п. (в частности, процессы, протекающие в системах массового обслуживания) организованы по схеме гибели и размножения. Термин «процесс гибели и размножения» ведет начало от биологических задач, где такими процессами описывается изменение численности биологических популяций; стрелки, ведущие слева направо, соответствуют 40 увеличению численности популяции (размножению), а справа налево – гибели входящих в нее особей. Использование схемы гибели и размножения далеко выходит за пределы биологических задач. Если на графе состояний системы S (рис. 4.1) стрелки, ведущие справа налево, отсутствуют, то говорят о процессе «чистого размножения», в противном случае – о процессе «чистой гибели». «Процесс чистого размножения» получится в условиях примера, если предположить, что узлы, составляющие ТУ, не восстанавливаются после выхода из строя. Процесс гибели и размножения может в некоторых случаях иметь не конечное число состояний, а бесконечное (счетное): s0 , s1, ..., si , ... . При анализе с. п., протекающих в системах с дискретными состояниями, важную роль играют вероятности состояний. Обозначим S(t) состояние системы S в момент t. 4.2. Потоки событий Одним из важных понятий теории с. п. является понятие потока событий. Потоком событий называется последовательность однородных событий, появляющихся одно за другим в случайные моменты времени (поток вызовов на телефонной станции, поток автомашин, подъезжающих на заправочную станцию, поток заболеваний гриппом в зимний сезон, поток заявок на ремонт, поступающих в ремонтную организацию, поток отказов (сбоев) ЭВМ в ходе ее работы). События, образующие ноток, в общем случае могут быть и неоднородными, например, если в потоке автомашин, прибывающих на заправку, различать легковые и грузовые. Заметим, что термин «событие» в понятии поток событий совершенно отличен по смыслу от широко применяемого в теории вероятностей понятия случайное событие, под которым разумеется «всякий факт, который в опыте со случайным исходом может произойти или не произойти». О событиях, образующих поток, так говорить нельзя. В частности, не имеет смысла говорить о вероятностях событий, образующих поток (например, о вероятности вызова на телефонной станции; ясно, что рано или поздно вызов придет, и не один). С потоком событий можно связывать различные случайные события, например: А = {в течение времени от t0 до t0 + x придет хотя бы один вызов на телефонную станцию) или В = {в течение того же времени придет ровно два вызова на телефонную станцию) и т. д. Вероятности таких событий можно вычислять. 41 Поток событий представляет собой в общем случае просто последовательность случайных точек 1, 2 ,..., n , ... на оси времени (рис. 4.2), с разделяющими их случайными интервалами T1, T2 , ... , Tn ,... , такими, что T1  2  1, T2  3  2 , ... , Tn  n 1  n . T1 1 T2 2 Tn 1 3  n 1  n Tn n1 t Рис. 4.2. Поток событий Потоки событий различаются по внутренней структуре: по законам распределения интервалов T1, T2 ,..., Tn , ... между событиями, их взаимной зависимости или независимости и т. д. С потоком однородных событий можно связать с. п. их накопления. Обозначим X(t) число событий потока, появившихся до момента времени t. Каждая реализация xi(t) с. п. X(t) представляет собой ступенчатую ломаную линию, «подскакивающую» на единицу в момент появления очередного события и сохраняющую свое значение до появления следующего события в потоке (рис. 4.3); здесь моменты появления событий уже не случайны и обозначены ν1, ν2 , ... , νn , ... . Для удобства будем полагать, что в точках разрыва процесс X(t) и его реализация xi(t) сохраняют значение, которое было у них слева от точки разрыва (про такую функцию говорят, что она непрерывна слева). Обычно наиболее простым (хотя это и не так) представляется поток событий, в котором интервалы между событиями одинаковы и равны определенной (неслучайной) величине 42 xi(t) 4 3 2 1 v1 v2 v3 t v4 Рис. 4.3. Реализация случайного процесса (пример) Такой поток событий называется регулярным (интервалы между событиями равны величине τ (рис. 4.4). Примеры регулярных (почти регулярных) потоков представляют собой поток изменений минутной цифры на электронных часах, поток изменений состояний ЭВМ и др. τ 1 2 τ 3 τ τ 4 5 6 t Рис. 4.4. Регулярный поток событий Регулярный поток событий редко встречается на практике; он представляет определенный интерес как предельный случай для других потоков. Однако, несмотря на свою видимую простоту, регулярный поток не имеет преимуществ при анализе, так как сильно проигрывает в простоте проведения расчетов другим типам потоков. Некоторые свойства потоков. 1. Ординарность потока. Поток событий называется ординарным, если события в нем появляются поодиночке, а не «пачками» по 2, по 3 и т. д. Рассмотрим элементарный участок Δt, примыкающий к точке t (рис. 4.5). Ординарность потока означает, что вероятность попадания на участок Δt двух или более событий пренебрежимо мала по сравнению с вероятностью попадания на него ровно одного события, т. е. при t  0 эта вероятность представляет собой бесконечно малую высшего порядка. Обозначим 43 через p1(t, t ) вероятность попадания на участок (t , t  t ) ровно одного события, p0 (t, t ) – вероятность непопадания на него ни одного события, p1(t, t ) – вероятность попадания на него двух или более событий. t t  t t Рис. 4.5. Ординарный поток событий Очевидно, для любого Δt (большого или малого) выполняется соотношение (4.1) p0 (t, t )  p1(t, t )  p1(t, t )  1 , так как это сумма вероятностей полной группы несовместных событий. Из этих вероятностей, очевидно, при малом Δt вероятность p0 (t, t ) самая большая. Для ординарного потока событий вероятность p1(t, t ) пренебрежимо мала по сравнению с другими слагаемыми: (4.2) p1(t, t )  o( p1(t, t )) , где символом «о малое» обозначается бесконечно малая высшего порядка малости. Для ординарного потока можно пренебречь возможностью совмещения на элементарном участке t двух или более событий, в частности, возможностью одновременного появления двух или более событий. Примерами ординарных потоков событий могут служить: поток деталей, поступающих на конвейер для сборки, поток отказов технического устройства, поток автомашин, прибывающих на станцию техобслуживания. Пример неординарного потока – поток пассажиров, прибывающих в лифте на данный этаж. В дальнейшем будем рассматривать лишь ординарные потоки событий. 2. Интенсивность потока. Рассмотрим ординарный поток событий. Обозначим X (t, t ) случайное число событий, попадающих на элементарный участок (t , t  t ) (рис. 4.5). Ряд распределения этой с. в. имеет вид: X (t , t ) : 1 2 ... p0 (t , t ) p1(t , t ) p2 (t, t ) ... где в столбце с проставленными многоточиями стоят сверху значения, а внизу – соответствующие им вероятности, которые пренебрежимо малы по 44 сравнению с p1(t, t ) . Найдем математическое ожидание с. в. X (t, t ) . Можно написать M  X (t , t )  0  p0 (t , t )  1  p1(t, t )  a  p1(t, t ) , где а – сколь угодно большая, но не стремящаяся к бесконечности при t  0 величина. Найдем предел отношения M  X (t , t )  к длине участка t : M  X (t, t )  p (t, t ) a  p1(t, t )   lim  1  . t t t 0 t 0  t  Так как при t  0 вероятность p1(t, t ) стремится к нулю быстрее, lim чем p1(t, t ) , то вторым слагаемым под знаком предела можно пренебречь: M  X (t, t ) p1(t, t ) (4.3) t t 0 t 0 t Если этот предел существует, то он называется интенсивностью (плотностью) ординарного потока событий в момент t: M  X (t, t ) (4.4) λ(t )  lim . t t 0 Физический смысл интенсивности λ(t ) потока событий – среднее число событий, приходящееся на единицу времени, для элементарного участка t , примыкающего к t. Интенсивность потока событий λ(t ) является lim  lim неотрицательной функцией времени: λ(t )  0 размерности 1/время. Очевидно, среднее число событий ординарного потока, приходящееся на интервал времени τ , примыкающий к точке t (рис. 4.6), равно: t τ M  X (t , τ)   λ(t )dt . (4.5) t τ t t Рис. 4.6. Среднее число событий ординарного потока за время τ В частности, при постоянной интенсивности потока: M  X (t , τ)  t τ  λdt  λτ . (4.6) t 3. Отсутствие последействия. Поток событий называется потоком без последействия, если для любых неперекрывающихся участков времени 45 τ1, τ2 , ... , τn X n = X (tn ,τn ) (рис. 4.7) числа попадающих событий на эти X1 = X (t1,τ1), X 2 = X (t2 ,τ2 ), ... , участки, представляют собой независимые случайные величины, т. е. вероятность попадания любого числа событий на один из участков не зависит от того, сколько их попало на другие. τ2 τ1 t1 t t2 X1 X2 Рис. 4.7. Поток без последействия Отсутствие последействия означает, что для любого момента времени t0 будущие моменты наступления событий (при t > t0) не зависят от того, в какие моменты наступали события в прошлом (при t < t0, см. рис. 4.8). Настоящее t = t0 Прошлое t < t0 Будущее t > t0 t Рис. 4.8. Принцип отсутствия последействия Если поток без последействия, ординарен и имеет постоянную интенсивность λ , то число событий X(t, τ), попадающих на участок времени длины τ , имеет распределение Пуассона с параметром а = λτ : P  X (t , τ)  k   a k e  a k ! ( k  0,1, 2, ...) . (4.7) Замечание 4.1. При непостоянной интенсивности потока λ(t ) число событий X(t, τ) попадающих на участок времени τ, примыкающий к моменту t, также распределено по закону Пуассона (4.7), но в нем параметр а зависит не только от длины участка τ, но и от того, где этот участок расположен: a  a (t , τ)  t τ  λ(t )dt , (4.8) t так что распределение случайной величины X(t, τ) – числа событий на участке (t, t + τ) – имеет следующий вид P  X (t , τ)  k   a (t , τ )k e  a (t , τ) k ! ( k  0,1, 2, ...) . 46 (4.9) Ординарный поток событий, в котором отсутствует последействие, называется пуассоновским потоком. Его связь с распределением Пуассона ясна из формул (4.7) и (4.9) 4. Стационарность потока. Поток событий называется стационарным, если его вероятностные характеристики не меняются со временем. Для стационарного потока событий вероятность попадания того или иного числа событий на участок длины τ зависит только от длины участка и не зависит от того, где участок расположен. Это значит, что числа событий X1(t1,τ) и X 2 (t2 ,τ) , попадающих на два участка длины τ (рис. 4.9), будут иметь одинаковое распределение. τ t1 τ t2 X 1 (t1 ,τ) t X (t ,τ) 2 2 Рис. 4.9 Стационарный поток Для стационарного λ(t ) = λ = const . потока событий интенсивность постоянна: Поток событий, обладающий свойствами ординарности, стационарности и отсутствием последействия, называется простейшим потоком (или стационарным пуассоновским потоком). Для простейшего потока событий вероятность того, что на участке времени длины τ наступит ровно k событий, определяется по формуле (4.7), где а = λτ , λ – интенсивность потока. Простейшим этот поток назван потому, что исследование систем, находящихся под воздействием простейших потоков, проводится самым простым образом. Следующей ступенью сложности по сравнению с простейшим является поток с ограниченным последействием. Будем так называть поток, у которого случайные интервалы T1, T2 ,..., Tn , ... (рис. 4.2) между соседними событиями представляют собой независимые случайные величины. Иногда поток с ограниченным последействием называют рекуррентным; это связано с тем, что при его моделировании применяется рекуррентная (последовательная) процедура: сначала разыгрывается величина T1 , затем T2 и т.д. Стационарный поток с ограниченным последействием называется потоком Пальма. Для такого потока интервалы T1, T2 ,..., Tn , ... между 47 событиями представляют собой последовательность независимых одинаково распределенных с. в. Простейший (стационарный пуассоновский) поток является также и потоком Пальма. 4.3. Потоки Пальма и потоки Эрланга Поток событий называется потоком Пальма (или потоком с ограниченным последействием), если промежутки времени между последовательными событиями T1, T2 ,..., Tn , ... представляют собой независимые, одинаково распределенные случайные величины. Простейший поток есть частный случай потока Пальма: в нем расстояния представляют собой с. в., распределенные по одному и тому же показательному закону; их независимость следует из того, что простейший поток есть поток без последействия, и расстояние по времени между любыми двумя событиями не зависит от того, каковы расстояния между другими. Первый пример потока Пальма. Некоторый элемент технического устройства работает непрерывно до своего отказа (выхода из строя), после чего он мгновенно заменяется новым. Срок работы элемента случаен. Если отдельные экземпляры элементов выходят из строя независимо друг от друга, то поток отказов (или «поток восстановлений», так как отказ и восстановление происходят в один и тот же момент) представляет собой поток Пальма. Если к тому же срок работы элемента распределен по показательному закону, поток Пальма превращается в простейший (стационарный пуассоновский) поток. Второй пример потока Пальма. Группа самолетов идет в боевом порядке «колонна» с одинаковой для всех самолетов скоростью V. Каждый из них, кроме ведущего, обязан выдерживать строй, т. е. держаться на заданном расстоянии от впереди идущего. Это расстояние, измеряемое дальномером, выдерживается с ошибками. Моменты пересечения самолетами заданного рубежа при этих условиях образуют поток Пальма, так как случайные величины независимы. Заметим, что тот же поток не будет потоком Пальма, если самолеты стремятся выдержать заданное расстояние не от соседа, а от ведущего всю колонну. Многие потоки событий, встречающиеся на практике, хотя и не являются в точности потоками Пальма, но могут быть ими приближенно заменены. 48 Важными для практики образцами потоков Пальма являются так называемые потоки Эрланга. Эти потоки образуются в результате «просеивания» простейших потоков. Потоком Эрланга k-го порядка называется поток, получающийся, если в простейшем потоке сохранить каждую k-ю точку, а остальные выбросить. Очевидно, простейший поток представляет собой частный случай потока Эрланга, а именно поток Эрланга 1-го порядка. Интервал времени Т между соседними событиями в потоке Эрланга kго порядка представляет собой сумму k независимых случайных величин – расстояний между событиями в исходном простейшем потоке: T  T1  T2  ...  Tk  k  Ti . (4.10) i 1 Каждая из этих случайных величин распределена по показательному закону: (4.11) f (t )  λeλt (t  0). Закон распределения интервала Т между соседними событиями в потоке Эрланга называется законом Эрланга k - го порядка. 49 5. ПОЛУМАРКОВСКИЕ ПРОЦЕССЫ 5.1. Основные понятия и определения Определение 5.1. Полумарковским процессом (ПМП) называется с. п. с дискретными состояниями, переходы между которыми описываются вложенной марковской матрицей, а условные функции распределения времени пребывания ПМП в конкретном состоянии зависят от состояния, в которое он перейдет. Таким образом, для описания ПМП достаточно знания двух следующих матриц p12 ... p1 j ... p1n   0   0 ... p2 j ... p2n   p21  . . . . . .   , P  pij  (5.1)  pi1 pi 2 ... pij ... pin    . . . . .   .  pn1 pn 2 ... pnj ... 0    F12 (t )  0   F21 (t )  . . F  Fij (t )    Fi1 (t ) Fi 2 (t )  .  .  Fn1 (t ) Fn 2 (t )  F1n (t )   ... F2 j (t ) ... F2n (t )  . . . .  , ... Fij (t ) ... Fin (t )   . . . .  ... Fnj (t ) ... 0  ... F1 j (t ) ... (5.2) а также вектора начальных распределений p(0)   p1(0), p2 (0),..., pn (0) . Замечание 5.1. Нули на главных диагоналях матриц P и F свидетельствуют о том, что рассматриваются только переходы из состояния в состояние, т.е. на соответствующем графе состояний вложенной марковской цепи отсутствуют петли. Замечание 5.2. Fij (t )  P( xij  t ) , где xij условное время пребывания ПМП в состоянии i при условии, что следующий переход будет в состояние j. Введем μij – условное среднее время пребывания ПМП в состоянии i при условии, что следующий переход будет осуществлен в состояние j: 50  μij   tFij (t )dt . (5.3) Тогда μi – безусловное среднее время пребывания ПМП в состоянии i: n  μi  j 1 pij  μ ij . (5.4) Стационарный случай. Пусть вложенная марковская матрица является эргодической. Тогда существует единственный вектор финальных вероятностей π  (π1,π2 ,...,πi ...,πn ) для вложенной марковской цепи, для которого выполняются условия πP  π, n  πi  1 (0  πi  1). (5.5) i1 В отличие от обычного марковского процесса в ПМП средние времена пребывания в отдельных состояниях ( μi ) различны. Таким образом, для нахождения вероятностей пребывания в конкретных состояниях в стационарном режиме следует использовать следующую формулу πi  μ i . (5.6) pi  n  πi  μ i j 1 Данная формула учитывает не только финальные (предельные) вероятности вложенной марковской цепи, но и средние продолжительности пребывания ПМП в отдельных состояниях. Поглощающий случай. В данном случае некоторые состояния (множества состояний) ПМП являются поглощающими (невозвратными). Перенумеровывая состояния исходную вложенную матрицу можно привести к следующему виду E 0 (5.7) P  pij   ,  R Q где Е – квадратная единичная матрица размерности k×k, где k – число поглощающих состояний ПМП; 0 – матрица, состоящая из одних нулей (k строк и (n – k) столбцов), показывающая, что из поглощающих состояний нет выхода; R –матрица ((n – k) строк и k столбцов), показывающая на переходы 51 из множества сообщающихся состояний в множество поглощающих состояний; Q – квадратная матрица размерности (n – k)×(n – k), характеризующая переходы внутри множества сообщающихся состояний. Введем в рассмотрение hi – среднее время до попадания в множество поглощающих состояний (до поглощения) при условии, что в начальный момент времени процесс находился в состоянии i. Тогда можем для состояния i записать следующее равенство hi  μ i  n  j  k 1 pij  h j (i  k  1, k  2, ... , n ) , (5.8) где суммирование производится по элементам матрицы Q. Выражение (5.8) можно записать в матричном виде: h  μ  Qh , (5.9) где h – вектор-столбец, компонентами которого являются неизвестные hi , а μ – вектор-столбец, состоящий из средних длительностей пребывания ПМП в отдельных состояниях ( μi ). Переписывая это уравнение в виде (E  Q)h  μ , где E – единичная матрица размерности (n – k)×(n – k), можно получить его решение в следующем виде: h  (E  Q)1μ . (5.10) 5.2. Однородный процесс марковского восстановления и полумарковское ядро Рассматриваемые ПМП являются более общим объектом, чем исследованные выше процессы восстановления и процессы Маркова. Начнем с определения ПМП с конечным множеством состояний. Математическим объектом исследования является ПМП (t) с конечным множеством состояний E  {e1, e2 ,..., eN }, N  . Без ограничения общности множество Е можно отождествить с множеством E  {1,2,..., N }, N  . ПМП (t ) определяется однородной двумерной марковской цепью или однородным процессом марковского восстановления (ξ n ,θn ), n  0, ξ n  E , θn  R   [0, ). (5.11) Однородная марковская цепь (ξn ,θn ) определяется переходными вероятностями, которые будем в дальнейшем называть полумарковским ядром, 52 P{ξn 1  j,θn 1  t / ξn  i,θn  τ)  P{ξn 1  j,θn 1  t / ξ n  i)  Qij (t ), (5.12) где n  1, i, j  E, t [0, ), и некоторым начальным распределением pi  P{ξ0  i}  0, i  E ,  iE pi  1, (5.13) кроме этого полагаем P{θ0  0}  1. Отметим, что из однородности процесса марковского восстановления следует независимость вероятностей Qij (t ) от n. Из включения θn  R   [0, ), n  1 следует неотрицательность случайных величин n , поэтому Qij (t )  0 при t  0. Нетрудно заметить, что переходная вероятность (5.11) определяет марковскую двумерную цепь специального вида, у которой будущее зависит только от первой компоненты ξ n и не зависит от второй компоненты  (вероятность Qij (t ) не зависит от параметра  Из (5.12) получаем условное распределение случайных величин θn : Fi (t )  P{θn  t / ξ n 1  i}   P{ξ n  j,θn  t / ξ n 1  i}   Qij (t ), (5.14) jE iE в силу несовместности событий {ξ n  j} при различных j. Для любой пары i, j  E справедливо неравенство Qij (t )  Fi (t ). Тогда существует функция F j ( x, i ) , для которой выполняется соотношение t Qij (t )   F j ( x, i )dFi ( x ) . Функцию F j ( x, i ) можно трактовать как условную вероятность F j ( x, i )  P{ξn 1  j / ξn  i,θn 1  x}. (5.15) Из марковского свойства последовательности (ξn ,θn ), n  0 для K > 0 и любых { jk , tk }, k  1,2,..., K , jk  E , tk  R  наборов следует справедливость равенства K P{ {k  jk , k  tk }}  k 1 K P{  iE piQij1 (t1 )  Q jk 1 , jk (tk ), {k  jk , k  tk } / 0  j0}  k 1 53 K k 2 K  Q jk 1 , jk (tk ), k 1 (5.16) K P{ k 0 {k  jk , k  tk } / n  jn , n  tn }  P{ n 1 k 0  jn , n  tn }P{ K {k  jk , k  tk } / n  {k  jk , k  tk } / n  jn , n  tn }. k  n 1 Последнее равенство формулируется как свойство марковских процессов с дискретным временем: при известном настоящем для марковского процесса с дискретным временем прошлое и будущее независимы. При t  из определения (5.12) получаем матрицу pij  lim Qij (t )  P{ξ n 1  j / ξ n  i}, i, j  E . (5.17) t  Для i, j  E , для которых pij  0, можно определить условную вероятность Fij (t )  P{θn  t / ξ n  j ,ξ n 1  i )  Qij (t ) pij , (5.18) и в новых обозначениях далее использовать равенство Qij (t )  pij Fij (t ). Если для некоторых i, j  E (5.19) справедливо равенство pij  0, то отношение (5.18) не определено и условное распределение Fij (t ) нужно доопределить, например, можно считать его вырожденным распределением. Таким образом, процесс марковского восстановления можно задавать тремя способами: 1) заданием полумарковского ядра Qij (t ) ; 2) заданием матрицы переходных вероятностей Маркова P  { pij } и распределениями вложенной цепи Fij (t )  P{θn  t / ξn  j,ξn 1  i ), i, j  E, t  0; 3) заданием Fi (t )  P{θn  t / ξn 1  i}, распределений и F j ( x, i )  P{ξn 1  j / ξn  i,θn 1  x}, i, j  E, x  0, t  0. Отметим, что во всех перечисленных случаях необходимо задавать начальное распределение первой компоненты процесса марковского восстановления. 54 Полумарковское ядро Qij (t ) обладает при любых i, j  E , x  0 следующими свойствами, вытекающими из свойств вероятностей: 1) 0  Qij (t )  1, Qij (0)  0 в силу того, что случайные величины θn неотрицательные; 2) Qij (t ) – неубывающие по x, непрерывные слева функции; 3) 0  4)  jE  jE Qij (t ) 1; Qij (  )   jE pij  1. Заметим, что элементы полумарковского ядра Qij (t ) определяют поведение процесса марковского восстановления за один период (шаг) между соседними моментами изменения состояний, причем предполагается однородность переходных вероятностей (нет зависимости от номера шага n). Определим свертку полумарковского ядра равенствами t t ( n 1)   Qik (t  x )dQkj ( x )    Qik (t  x )dQkj( n 1) ( x ), (5.20) kE 0 kE 0 n  1, Qij(1) (t )  Qij (t ). Qij( n ) (t )  Нетрудно заметить, что функция Qij( n ) (t ) определяет вероятность перехода процесса марковского восстановления из состояния i в состояние j за n переходов (для первой компоненты) и суммарное время  θk меньше t k n (для второй компоненты). Т.е. при любом n > 0 имеем: Qij( n ) (t )  P{m  n  j, n  θm  s  t / m  i}. (5.21) s 1 В силу однородности процесса марковского восстановления эта вероятность не зависит от параметра m. Далее исследуем свойства пределов pij( n )  limt Qij( n ) (t ). Из равенств (5.20) и (5.21) получаем при t  с учетом обозначений (5.17): 55 pij( n )  lim Qij( n ) (t )  Qij( n ) ()  P{ξ m  n  j / ξ m  i}  t    kE ( n 1) pik pkj   ( n 1) pik pkj , n  1, m  0, (5.22) kE pij(1)  pij . Равенства (5.22) доказывают, что последовательность {ξn }, n  0,1,2, ... , определяющая эволюцию первой компоненты, является однородной цепью Маркова с матрицей переходных вероятностей (5.17). Таким образом, определенная однородная цепь Маркова называется вложенной цепью Маркова. Она характеризует эволюцию первой компоненты введенной выше двумерной цепи Маркова {ξn ,θn }, n  0,1,2, ... . Отметим, что выше приведенные рассуждения не ограничивают возможность перехода вложенной цепи Маркова из состояния i в то же самое состояние i. Кроме этого, следует заметить, что известная классификация цепей Маркова и их состояний позволяет использовать ее в дальнейшем для классификации полумарковских процессов и их состояний. Из марковского свойства (5.16) двумерной цепи {ξn ,θn }, n  0,1,2, ... и равенств (5.17) и (5.18) следует, что при любом K > 0 и tm > 0, 0  m  K: K  K  K P  {θk  tk } / {ξ k  jk }   F jk 1, jk (tk ). (5.25) k 1  k 0  k 1 Последнее равенство означает, что последовательность случайных величин {θn }, n  0 является условно независимой, то есть при известной траектории изменения первой компоненты {ξm  jm}, 0  m  K , совместное распределение последовательности представляется {θn }, 0  m  K , произведением условных распределений F jm1, jm (t ), 1  m  K. Суммированием первого равенства (5.16) распределение случайных величин {θn }, 0  m  K K P{ {θk  tk }}  k 1    ... jE j1 E j 2 E  jK E получаем совместное K p j  Q jk 1 , jk (tk ). (5.24) k 1 Определим при t > 0 ПМП ξ(t ) как значение первой компоненты марковского процесса восстановления ξ(t )  ξ ν(t ) , 56 (5.25) где ν(t )  sup{n :  θk  t}, k n θ0  0. (5.26) Процесс ν(t ) , определяемый равенством (5.26), называется считающим процессом. Траектории этого процесса непрерывные справа ступенчатые неубывающие функции, в общем случае скачки (высота ступенек) равны целым числам, а ширина – есть случайная величина, определяемая второй компонентой процесса марковского восстановления θn . Если распределение, определяемое равенством (5.26), непрерывно при tm = 0, 1  m  K, то скачки (высота ступенек) равны единице для почти всех траекторий. Замечание 5.3. Компоненты ПМП ξ(t ) и введенный выше считающий процесс ν(t ) имеют ступенчатые траектории, для которых совпадают моменты разрывов (разрывы происходят в моменты tn   θk , n  1 ), k n только значения считающего процесса ν(t ) целые положительные числа, а ПМП ξ(t ) принимает значения из моментами tn  конечного множества E  {1,2,,,,, N}, N  . Замечание 5.4. Между  θk k n и tn 1   k  n 1 θk считающий процесс ν(t ) и, следовательно, ПМП ξ(t )  ξ ν(t ) , не меняют своих состояний. Замечание 5.5. Для ПМП tn   θk , (t ) моменты изменения состояний n  1 являются марковскими моментами. Будущее ПМП k n определяется состоянием, в которое он перешел в момент tn   θk , k n временем пребывания в этом состоянии θn1 и состоянием, в которое он перейдет в момент tn 1   θk Если известно, что ξ(tn )  i, то из k  n 1 определения полумарковского ядра (5.12) следует, что совместное распределение будущего состояния и времени θn1 зависит только от i. Следовательно, будущее процесса ξ(t ) в момент tn зависит только от i. 57 5.3. Классификация полумарковских процессов и их состояний Как [tn  было  θk , k n tn 1  отмечено  k  n 1 выше, ПМП ξ(t ) в полуинтервале θk ), n  1, θ0  0, не меняет своих состояний, то есть θn можно рассматривать как время непрерывного пребывания ПМП ξ(t ) в некотором фиксированном состоянии. В силу однородности марковского процесса восстановления (5.11) условное распределение случайной величины θn при условии ξ(tn 1)  i не зависит от n. Тогда из (5.14) имеем Fi (t )  P{  t / (0)  i}   jE Qij (t ), (5.27) где через  обозначено время непрерывного пребывания ПМП в некотором фиксированном состоянии. Определение 5.2. Состояние iE называется мгновенным, если Fi (t )  P{θ  t / ξ(0)  i}   Qij (t )  1, t  0. (5.28) jE С учетом свойств полумарковского ядра  jE (5.28) получаем P{θ  0 / ξ(0)  i}  1. для мгновенного Qij (0)  0 из равенства состояния iE равенство В мгновенном состоянии случайный ПМП ξ(t ) с вероятностью единица проводит время, равное нулю. Для мгновенного состояния из (5.19) получаем равенство при t > 0: Qij (t )  pij . С понятием мгновенного состояния связано понятие регулярности ПМП. Прежде всего, отметим, что считающий с. п. ν(t ) для любого t > 0 определяет число состояний (число переходов), которые принимал ПМП ξ( x) за время t, включая момент t (с. п. ν(t ) и ξ(t ) непрерывны справа). Определение 5.3. ПМП ξ(t ) называется регулярным, если с вероятностью единица он за конечное время совершает конечное число переходов, то есть для любого t > 0 и iE справедливо равенство P{ν(t )   / ξ(0)  i}  1. Увяжем понятие регулярности с понятием мгновенности состояний. 58 Очевидно, что, если все состояния ПМП являются мгновенными, то за конечное время произойдет бесконечно много переходов. По существу, эволюции такого процесса во времени не происходит, то есть такого процесса не существует. В дальнейших рассуждениях предполагаем, что все состояния ПМП не могут быть мгновенными. Определение 5.4. Состояние iE называется поглощающим, если при любом конечном t Fi (t )  P{θ  t / ξ(0)  i}   Qij (t )  0, t  0. (5.29) jE Для поглощающего состояния i справедливо равенство Qij (t )  pij Fij (t )  0, j  E, t  0, (5.30) поскольку каждое слагаемое неотрицательно, Qij (t )  0. Попав в поглощающее состояние i, случайный ПМП с вероятностью единица проводит в нем бесконечное время. Определение 5.5. ПМП ξ(t ) называется обрывающимся, если с вероятностью единица его эволюция продолжается конечное время. Замечание 5.6. Решение вопроса о конечном или бесконечном времени эволюции процесса зависит от конкретной реальной ситуации, которую описывает исследуемый ПМП. 5.4. Применение полумарковских процессов Одна из сфер применения ПМП – анализ и описание систем массового обслуживания (СМО). Рассмотрим, например, исследование с помощью вложенного ПМП однолинейную систему с ожиданием (M|G|1), в которой обслуживание протекает партиями объема K в течение случайного промежутка времени с функцией распределения H(x). Если в очереди имеется меньше, чем K требований, и обслуживающее устройство свободно, то очередное обслуживание начинается в момент времени, когда в очереди станет K требований. Пусть X(t) – число требований в системе в момент t. Стационарные вероятности Pi  lim P{ X (t )  i | X (0)} x  определяются через стационарные вероятности ρi и pi для вложенной цепи Маркова ξn  X (tn  0), n  1, 2, ..., и вложенного ПМП, где в качестве 59 точек регенерации выбираются моменты τn ухода требования из системы. Для производящей функции π( z )    ρi z i i 0 вложенной цепи Маркова получена следующая формула φ(1)k ( z ) π( z )  , φ( z ) где k ( z)    k jz j, j 0  kj   e  λu (λu ) j! j dH (u ), z K  k ( z) φ( z )  , ( z  1)( z  ω1 )...( z  ω K 1 ) ω1,ω2, ..., ω K 1  корни внутри единичного круга уравнения z K  k ( z ). Вложенный ПМП ξ(t) строится таким образом, что его переходы происходят в моменты τn и моменты τ 'n , когда длина очереди равна K. Для вложенного ПМП  H ( x ), i  K ,  Pi ( x )   K i 1 (λt ) j  λt e , i  K, 1   j ! j 0  где λ – интенсивность входящего потока, а стационарные вероятности ПМП равны:  cρ , i  K ,  i  ρ*i  c(ρi  ρ K ), i  1,  cρi , i  K , 1 c , 1 ρ ρ= K 1  i 0 ρi . 60 Стационарные вероятности Fi(x) для линейчатого Марковского процесса {ξ(t), U(t)} равны:  x K i 1 (λu ) j  λu e du, i  K ,  c ρi   j !  0 j 0  x  Fi ( x )  c(ρ+ρk )  [1  H (u )] du, i  K ,   x cρ [1  H (u )] du, i  K .  i  0 Стационарные вероятности Pi определяются следующим образом: c i Pi   ρ j , i  K , λ j 0   (λu )i  j  λu (λu )i  K  λu Pi  c  ρ j  e [1  H (u )] du  ρ  e [1  H (u )] du, i  K . ( i  j )! ( i  K )! jK i 61 ЗАКЛЮЧЕНИЕ Учебное пособие поддерживает изучение дисциплины «Случайные процессы и системы массового обслуживания» направления 220100 «Системный анализ и управление», а также может быть полезно для студентов направлений 220400 «Управление в технических системах» и 230400 «Информационные системы и технологии», как на уровне бакалаврской подготовки, так и на уровне ряда магистерских программ, и инженерно-технических и научных работников этой предметной области и аспирантов специальностей 05.13.01, 05.13.06, 19.00.03 и др. Приведены основные понятия теории случайных процессов (определения, виды, классификация). Во второй главе описаны непрерывные случайные процессы: проведен анализ взаимосвязи сечений случайных процессов, дано понятие спектральной плотности, определен векторный случайный процесс (гауссовский процесс). Показан соответствующий математический аппарат. В третьей главе проведен всесторонний анализ специфических особенностей случайных процессов с дискретным временем. Рассмотрены графы состояний и дана классификация состояний и множеств состояний.. Проведен анализ особенностей марковских случайных процессов с дискретными состояниями и дискретным временем (цепей Маркова). В четвертой главе дано описание основных особенностей случайных потоков (процесс гибели и размножения, потоки событий, потоки пальма и потоки Эрланга). В пятой главе описаны общие свойства полумарковских процессов (основные понятия и определения, классификация полумарковских процессов и их состояний, однородный процесс марковского восстановления). Приведен ряд примеров описания и оценки функционирования различных систем (процессов, технологий). 62 Список рекомендуемой литературы Антонов А. В. Системный анализ: учеб. для вузов по направлению "Информатика и вычисл. техника" и специальности "Автоматизированные системы обработки информации и управления" / А. В. Антонов. Изд. 2-е, стер. М.: Высшая школа, 2004. 453 с. Информационно-управляющие человекомашинные системы. Исследование, проектирование, испытания: справ. /А. Т. Ашеров, А. И. Губинский, В. Г. Евграфов и др.; под общ. ред. А. И. Губинского, В. Г. Евграфова. М.: Машиностроение, 1993. 512 с. Исследование операций: задачи, принципы, методология: учеб. пособие для вузов / Е.С. Вентцель. 3-е изд., стер. М.: Дрофа, 2004. 208 с. Клейнрок Л. Теория массового обслуживания Л. Клейнрок; пер.с англ. И. И. Грушко; под ред. В. И. Неймана. М.: Машиностроение, 1979. 431 с. Теория вероятностей и ее инженерные приложения: учеб.пособие для втузов / Е. С. Вентцель, Л. А. Овчаров. 3-е изд., перераб. и доп. М.: Academia, 2003. 459 с. Теория случайных процессов и ее инженерные приложения/ Е. С.Вентцель, Л. А.Овчаров. М.: Наука, 1991. 383 с. 63 Бурков Евгений Александрович, Падерно Павел Иосифович Элементы теории случайных процессов Учебное пособие Редактор И. Г. Скачек Подписано в печать: хх.хх.хх. Формат 60х84 1/16. Бумага офсетная. Печать офсетная. Печ. л. 4.0. Тираж хх экз. Заказ хх. Издательство СПбГЭТУ «ЛЭТИ» 197376, С.-Петербург, ул. Проф. Попова, 5 64