Теория случайных процессов (1042226), страница 4
Текст из файла (страница 4)
В процессе своегофункционирования система в дискретные моменты времени, называемые шагами и обозначаемые n = 0, 1, 2, ... , переходитиз состояния ξn = i в состояние ξn+1 = j с условной вероятностью pij . Эта вероятность не зависит ни от состояний системы в предшествующие моменты времени (свойство марковости),Лекция 4. Основные понятия25ни от текущего времени (свойство однородности). Предполагается, что в нулевой момент времени (n = 0) система находитсяв одном из состояний пространства S с распределением(0)(0) (0)π1 , π2 , ... πN .Итак, СП ξ0 , ξ1 , ...
ξn , ... смены состояний называется простой однородной дискретной (конечной) цепью Маркова, еслидля всех n > 1 и i, j , i0 , i1 , ... ∈ S выполняется марковское свойствоP {ξn = j | ξ0 = i0 , ξ1 = x1 , ... , ξn−1 = i} ==P {ξn = j | ξn−1 = i} = pij . (4.1)(0) (0)0Вероятности π1 , π2 , ...
, πN и (pi1 , pi2 , ... , piN ) ∀ i образуюттак называемые стохастические векторы, т. е. векторы с неотрицательными элементами, удовлетворяющими условию нормиNNPP(0)рованностиπi = 1 иpij = 1.i=1j=1Матрица P = (pij ), состоящая из стохастических векторовстрок, сама является стохастической и называется матрицейвероятностей перехода (МВП).При анализе ДЦМ широко используется геометрическая наглядная схема, называемая размеченным графом состояний(РГС), или просто графом состояний (ГС). Каждому состояниюДЦМ на схеме соответствует круг (прямоугольник) с номеромсостояния внутри него или рядом. Если из состояния i в состояние j возможен одношаговый переход (pij > 0), то из вершины iв вершину j проводится дуга со стрелкой, рядом с которой можетбыть указано значение pij .Пример 4.1.
Рассмотрим вычислительный центр с тремяЭВМ. Их состояние контролируется ежесуточно. Если контролерпризнает ЭВМ исправной, то она продолжает работать, в противном случае направляется в ремонт. Вероятность исправной ЭВМвыйти из строя за истекшие сутки обозначим r, а вероятностьремонтируемой ЭВМ войти в строй за то же время q . Процессывыхода из строя и восстановления ЭВМ независимы. Введемв рассмотрение состояния:i = 0 — все три ЭВМ исправны,i = 1 — ровно одна ЭВМ неисправна,i = 2 — ровно две неисправны,i = 3 — все три неисправны.26Разд.
2. Дискретные цепи МарковаПостроим МВП и РГС. Для этого найдем вероятности перехода. Очевидно,p00 = (1 − r)3 , p01 = 3r (1 − r)2 , p02 = 3r2 (1 − r), p03 = r3 ,p10 = q (1 − r)2 , p11 = 2qr (1 − r) + (1 − q) (1 − r)2 ,p12 = qr2 + 2(1 − q)r(1 − r), p13 = (1 − q) r2 ,p20 = q 2 (1 − r) , p21 = q 2 r + 2 (1 − r) q (1 − q) ,p22 = (1 − q)2 (1 − r) + 2rq (1 − q) , p23 = (1 − q)2 r,p30 = q 3 , p31 = 3q 2 (1 − q) , p32 = 3q (1 − q)2 , p33 = (1 − q)3 .3XЛегко проверить, чтоpij = 1, i = 0, 1, 2, 3.i=0При r = 0, 2 и q = 0, 3 получаем МВП0,512 0,384 0,096 0,008 0,192 0,544 0,236 0,028P = 0,072 0,354 0,476 0,0980,027 0,189 0,441 0,343РГС имеет вид, представленный на рис.
5..p111p10p12p01p20p000p212p02 p31p30p13p32p03p22p233p33Рис. 5Пример 4.2. Задача о холодильниках (управление запасами).Магазин электротоваров в начале каждой недели размещает заказы на два холодильника. Еженедельный спросЛекция 4. Основные понятия27нахолодильникизадаетсяраспределением вероятностей:спрос012. Пусть в состоянии i магазинвероятность 0,2 0,5 0,3имеет для продажи i холодильников.
Пространство состоянийS = {0, 1, 2}. Процесс функционирования магазина моделируетсяДЦМ с МВП100P = 0,8 0,2 0 0,3 0,5 0,2и РГС, представленным на рис. 6.100,80,30,210,520,2Рис. 6Две задачи теории дискретных цепейПусть последовательность ξn , n = 0, 1, 2, ... , образуетДЦМ с МВП P , векторомначальных вероятностей (ВНВ)(0) (0)(0)(0)π = π1 , π2 , ... , πNи пространством состояний S == {0, 1, 2, ... , N }. Рассмотрим две задачи.(n)Задача 1.
Найти для всех i, j ∈ S вероятности перехода pi,jсистемы из состояния i в состояние j за n шагов — другимисловами, построить (N × N )-матрицу вероятностей перехода за(n)n шагов P = pij .Решение. Рассмотрим три момента времени (три шага) 0, m, n(0 < m < n), зафиксируем состояния в моменты 0 и n: ξ0 = i,ξn = j , и обозначим произвольное состояние в момент m: ξm = d;i, j , d ∈ S (рис. 7). В принятых обозначениях28Разд. 2. Дискретные цепи Маркова(n)— вероятность перехода системы из i в j за n шагов,(m)— вероятность перехода системы из i в d за m шагов,(n−m)— вероятность перехода системы из d в jза (n − m) шагов.pijpidpdjid)(mp idpd(jn−m)j0m(n − m){{imn−m(m)nnРис. 7По формуле полной вероятности получимКолмогорова–ЧепменаNX(n)(m) (n−m)pij =pid pdj, i, j ∈ S ,уравнение(4.2)d=1или в матричной формеP (n) = P (m) P (n−m) ,гдеИз (4.3) следуетP (0) = I = (4.3)11...1.P (n) = P (n−m) P (m) ;(4.4)действительно, достаточно в (4.3) положить m : = n − m, n −− m : = m.Из (4.3) и (4.4) следует: при m = 1 и m = n − 1 получаемP (n) = P n−1 P = P P (n−1) .(4.5)29Лекция 4.
Основные понятияИз (4.5) следует: P (n) = P P (n−1) = P P P (n−2) = ... = P n , т. е.МВП ДЦМ за n шагов есть n-я степень матрицы одношаговыхпереходов.Читателю рекомендуется доказать, что P n — стохастическаяматрица (доказав предварительно, что произведение стохастических матриц есть стохастическая матрица).Задача 2. Найти для всех j ∈ S вероятности состояний(n)системы πj через n шагов — другими словами, построитьN -вектор вероятностей состояний системы (ВВС) через n шагов(n) (n)(n)π (n) = π1 , π2 , ... , πN .Решение. Рассмотрим события {ξ0 = i}, i ∈ S , как гипотезы(0)с вероятностями πi .
Тогда события {ξn = j} могут произойтисовместно с каждой из перечисленных гипотез с условными(n)вероятностями pij (рис. 8). По формуле полной вероятностиполучаемNX(n)(0) (n)πj =πi pij , j ∈ S(4.6)i=1или в векторно-матричной формеπ (n) = π (0) P n .(4.7)ij(n)iπj(n)pij(0)πin0nРис. 8Из (4.7) следуетπ (n) = π (0) P n = π (0) P n−1 P = π (n−1) P ,или(n)πj=NXi=1(n−1)πipij ,j ∈ S.(4.8)(4.9)30Разд. 2. Дискретные цепи МарковаПример 4.3 (продолжение примера 4.2).11 0,8 0,2⇒P = 0,3 0,5 0,2 ⇒ P 2 = 0,96 0,040,76 0,20 0,041.⇒ P 3 = 0,992 0,0080,932 0,06 0,008(n)Легко видеть, что при n → ∞ и при j 6= i имеем pi0 → 1,(n)pij → 0.
В лекции 6 эта закономерность будет обоснована.Если π (0) = (0,167; 0,333; 0,500), то согласно (4.7)π (2) = π (0) P 2 = (0,867; 0,113; 0,02) ⇒⇒ π (3) = π (0) P 3 = (0,963; 0,033; 0,004) ;(n)заметим, что при n → ∞ и при i 6= 0 π0(n)→ 1, πi→ 0.Пример 4.4.
Доказать, что последовательность ξ0 , ξ1 , ..., ξn , ...состоит из независимых СВ тогда и только тогда, когда МВПP = (pij ) состоит из одинаковых строк pij = pj ∀ i, j.Действительно, пусть СВ ξi независимы, тогдаpij = P {ξn = j | ξn−1 = i} = P {ξn = j} = pj ∀ i, j , n.Обратно, пусть pij = pj ∀ i, j , т. е. P {ξn = j | ξn−1 = i} = P {ξn == j} ∀ i, j . Таким образом, условная вероятность события совпадает с безусловной, что свидетельствует о независимости СВ ξi .Лекция 5.
Анализ структуры пространства состоянийи классификация цепейСтруктура ДЦМ нас интересует с точки зрения механизмавозможных переходов системы из состояния в состояние. Но возможные переходы полностью отражены в графе состояний (ГС),так как для их анализа существенно не значение вероятностейперехода pij , а факт pij = 0 или pij > 0. Отсюда следует, чтоанализ структуры ДЦМ сводится к анализу ее ГС.Лекция 5.
Анализ структуры пространства состояний31Итак, рассмотрим ГС (рис. 9). Вершины i и j соединеныдугой, если pij > 0. В нашем графе p22 > 0, p23 > 0, p51 > 0и т. д. Дуга (i, i) называется петлей. Путем длины n, связывающим i с j (в этом случае говорят, что j следуетза i), называется последовательность n дуг вида Пn (i, j) == {(i, k) , (k , l) , ...
, (m, j)}. Существование Пn (i, j) означает возможность перехода в ДЦМ из состояния i в состояние j за nшагов. Путь Пn (i, i) называется контуром длины n. В нашемграфе имеются петли (2,2) и (1,1),пути (5,3), (3,2), (2,2), (2,3),(3,4) или (4,3), (3,4). Последний является контуром.23541Рис. 9Говорят, что вершина j достижима из вершины i, еслисуществует путь Пn (i, j). Обозначение достижимости: i → j .Вершины i и j сообщаются друг с другом (обозначение: i ↔ j),если (i → j) ∧ (j → i). Другими словами, вершины iи j сообщаются, если возможны как переход i → j , так и возвращениеj → i.
Вершина i, сообщающаяся с любой следующей за ней, называется существенной, в противном случае несущественной.Таким образом, каждая вершина может быть либо существенной,либо несущественной.В нашем ГС вершина 2 достижима из вершин 2, 3, 4 и 5;вершина 1 достижима из вершин 1 и 5; пары вершин (2, 2), (2, 3),(2,4), (3, 4), (1, 1) являются сообщающимися.
Других сообщающихся нет. Вершина 5 является несущественной, все остальные — существенные.Основная теорема структурного анализа. 1) За любойвершиной следует хотя бы одна вершина.2) За существенной вершиной следуют только существенные.3) Для всякой несущественной вершины найдется существенная, следующая за ней.32Разд. 2. Дискретные цепи МарковаД о к а з а т е л ь с т в о. 1) Если за вершиной i не следует ниNPодна вершина, то pij = 0 ∀ i ⇒pij = 0, что противоречитj=1определению МВП конечной цепи.2) Пусть i — существенная вершина.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
